An Investigation of Multi-Agent Planning in CLP

• Autorzy: Dovier A. , Formisano A. , Pontelli E.
• Języki publikacji: EN

Abstrakty

EN

This paper explores the use of Constraint Logic Programming (CLP) as a platform for experimenting with planning problems in the presence of multiple interacting agents. The paper develops a novel constraint-based action language, B^MAP, that enables the declarative description of large classes of multi-agent and multi-valued domains. B^MAP supports several complex features, including combined effects of concurrent and interacting actions, concurrency control, and delayed effects. The paper presents a mapping of B^MAP theories to CLP and it demonstrates the effectiveness of an implementation in SICStus Prolog on several benchmark problems. The effort is an evolution of previous research on using CLP for single-agent domains, demonstrating the flexibility of CLP technology to handle the more complex issues of multi-agency and concurrency.

Słowa kluczowe

EN

Action Description Languages; multi-agent planning; constraint logic programming (CLP)

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 1/2
• Strony: 79--103
• Opis fizyczny: Bibliogr. 36 poz.

Twórcy

autor

Dovier A.

autor

Formisano A.

autor

Pontelli E.

• Dipartimento di Matematica e Informatica, Universita di Udine, Via delle Scienze 206, 33100 Udine, Italy,

Bibliografia

• [1] Baldoni, M., Baroglio, C., Mascardi, V., Omicini, A., Torroni, P.: Agents, Multi-Agent Systems and Declarative Programming: What, When, Where, Why, Who, How?, in: A 25 Year Perspective on Logic Programming (A. Dovier, E. Pontelli, Eds.), vol. 6125 of Lecture Notes in Computer Science, chapter 10, Springer-Verlag, 2010, 204-230.
• [2] Baral, C.: Knowledge representation, reasoning and declarative problem solving, Cambridge University Press, 2003.
• [3] Baral, C., Gelfond, M.: Reasoning About Effects of Concurrent Actions, Journal of Logic Programming, 31(1-3), 1997, 85-117.
• [4] Baral, C., Son, T., Tuan, L.-C.: A Transition Function Based Characterization of Actions with Delayed and Continuous Effects, in: KR2002: Principles of Knowledge Representation and Reasoning (D. Fensel, F. Giunchiglia, D. L. McGuinness, M.-A. Williams, Eds.), Morgan Kaufmann, 2002, 291-302.
• [5] Bartak, R., Toropila, D.: Reformulating Constraint Models for Classical Planning, in: FLAIRS'08: Twenty-First International Florida Artificial Intelligence Research Society Conference (D.Wilson, H. C. Lane, Eds.), AAAI Press, 2008, 525-530.
• [6] Boutilier, C., Brafman, R.: Partial order planning with concurrent interacting actions, Journal of Artificial Intelligence Research, 14, 2001, 105-136.
• [7] Brenner, M.: From Individual Perceptions to Coordinated Execution, in: ICAPS'05 workshop on Multiagent Planning and Scheduling (B. J. Clement, Ed.), 2005, 80-88.
• [8] Chesani, F., Mello, P., Montali, M., Torroni, P.: Commitment tracking via the reactive event calculus, in: IJCAI'09: Proceedings of the 21st International Joint Conference on Artificial Intelligence (C. Boutilier, Ed.), AAAI Press, 2009, 91-96.
• [9] Chintabathina, S., Gelfond, M.,Watson, R.: Defeasible laws, parallel actions, and reasoning about resources, in: CommonSense'07: Logical Formalizations of Commonsense Reasoning: papers from the AAAI Spring Symposium (E. Amir, V. Lifschitz, R. Miller, Eds.), AAAI Press, 2007, 35-40.
• [10] Chopra, A. K., Singh, M. P.: Contextualizing commitment protocol, in: AAMAS'06: Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems (H. Nakashima, M. P. Wellman, G. Weiss, P. Stone, Eds.), ACM, 2006, 1345-1352.
• [11] Dal Palu, A., Torroni, P.: 25 Years of Applications of Logic Programming, in: A 25 Year Perspective on Logic Programming (A. Dovier, E. Pontelli, Eds.), vol. 6125 of Lecture Notes in Computer Science, chapter 14, Springer-Verlag, 2010, 298-325.
• [12] Desai, N., Chopra, A. K., Singh, M. P.: Representing and reasoning about commitments in business processes, in: AAAI'07: Proceedings of the 22nd AAAI Conference on Artificial Intelligence (A. Howe, R. Holt, Eds.), AAAI Press, 2007, 1032-1333.
• [13] Dovier, A., Formisano, A., Pontelli, E.: Representing Multi-Agent Planning in CLP, in: LPNMR 2009 (E. Erdem, F. Lin, T. Schaub, Eds.), vol. 5753 of Lecture Notes in Computer Science, Springer, 2009, 423-429.
• [14] Dovier, A., Formisano, A., Pontelli, E.: Multivalued Action Languages with Constraints in CLP(FD), Theory and Practice of Logic Programming, 10(2), 2010, 167-235.
• [15] Eiter, T., Faber, W., Leone, N., Pfeifer, G., Polleres, A.: Answer Set Planning Under Action Costs, Journal of Artificial Intelligence Research, 19, 2003, 25-71.
• [16] Gelfond, G., Watson, R.: Modeling Cooperative Multi-Agent Systems, Proceedings of ASP Workshop (S. Costantini, R. Watson, Eds.), 2007.
• [17] Gelfond, M., Lifschitz, V.: Action Languages, Electronic Transactions on Artificial Intelligence, 2, 1998,193-210.
• [18] Gerevini, A., Long, D.: Plan Constraints and Preferences in PDDL3, Technical Report RT 2005-08-47, University of Brescia, 2005.
• [19] Giunchiglia, E., Lee, J., Lifschitz, V., McCain, N., Turner, H.: Nonmonotonic Causal Theories, Artificial Intelligence, 153(5-6), 2004, 49-104.
• [20] Jaffar, J., Yap, R., Zhu, K. Q.: Coordination of Many Agents, in: ICLP'05: Proceedings of the 21st International Conference on Logic Programming (M. Gabbrielli, G. Gupta, Eds.), vol. 3668 of Lecture Notes in Computer Science, Springer, 2005, 98-112.
• [21] Jefferson, C., Miguel, A., Miguel, I., Tarim, S. A.: Modelling and solving English Peg Solitaire, Computers & Operations Research, 33(10), 2006, 2935-2959.
• [22] Kakas, A., Mancarella, P., Sadri, F., Stathis, K., Toni, F.: Computational Logic Foundations of KGP Agents, Journal of Artificial Intelligence Research, 33, 2008, 285-348.
• [23] Kakas, A., Torroni, P., Demetriou, N.: Agent Planning, Negotiation and Control of Operation, in: ECAI'04: Proceedings of the 16th Eureopean Conference on Artificial Intelligence (R. L. de Mántaras, L. Saitta, Eds.), IOS Press, 2004, 28-32.
• [24] Knoblock, C. A.: Generating Parallel Execution Plans with a Partial-Order Planner, in: AIPS'94; Proceedings of the 2nd International Conference on Artificial Intelligence Planning Systems (K. J. Hammond, Ed.), AAAI Press, 1994, 98-103.
• [25] Levesque, H., Pirri, F., Reiter, R.: GOLOG: a logic programming language for dynamic domains, Journal of Logic Programming, 31(1-3), 1997, 59-83.
• [26] Lopez, A., Bacchus, F.: Generalizing GraphPlan by Formulating Planning as a CSP, in: IJCAI'03: Proceedings of the 18th International Joint Conference on Artificial Intelligence (G. Gottlob, T. Walsh, Eds.), Morgan Kaufmann, 2003, 954-960.
• [27] Reiter, R.: Knowledge in Action: Logical Foundations for Describing and Implementing Dynamical Systems, MIT Press, Bradford Books, 2001.
• [28] Sadri, F., Toni, F.: Abductive Logic Programming for Communication and Negotiation Amongst Agents, ALP Newsletter, May 2003.
• [29] Sauro, L., Gerbrandy, J., van der Hoek, W., Wooldridge, M.: Reasoning about Action and Cooperation, in: AAMAS'06: Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems (H. Nakashima, M. P. Wellman, G. Weiss, P. Stone, Eds.), ACM, 2006, 185-192.
• [30] Son, T., Baral, C., McIlraith, S. A.: Planning with Different Forms of Domain-Dependent Control Knowledge - An Answer Set Programming Approach, in: LPNMR'01: Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (T. Eiter, W. Faber, M. Truszczyński, Eds.), vol. 2173 of Lecture Notes in Computer Science, Springer, 2001, 226-239.
• [31] Son, T., Pontelli, E., Sakama, C.: Logic programming for multi-agent planning with negotiation, in: ICLP'09: Proceedings of the 25st International Conference on Logic Programming (P. M. Hill, D. S.Warren, Eds.), vol. 5649 of Lecture Notes in Computer Science, Springer, 2009, 99-114.
• [32] Son, T., Sakama, C.: Reasoning and Planning with Cooperative Actions for Multiagents Using Answer Set Programming, in: DALT'09: Proceedings of the 7th InternationalWorkshop on Declarative Agent Languages and Technologies (M. Baldoni, J. Bentahar, M. B. van Riemsdijk, J. Lloyd, Eds.), vol. 5948 of Lecture Notes in Computer Science, Springer, 2009, 208-227.
• [33] Thielscher, M.: Pushing the envelope: programming reasoning agents, in: AAAI Workshop on Cognitive Robotics, AAAI Press, 2002, 110-117.
• [34] Thielscher, M.: Reasoning about Actions with CHRs and Finite Domain Constraints, in: ICLP'02: Proceedings of the 18th International Conference on Logic Programming (P. J. Stuckey, Ed.), vol. 2401 of Lecture Notes in Computer Science, Springer, 2002, 70-84.
• [35] Vidal, V., Geffner, H.: Branching and Pruning: An Optimal Temporal POCL Planner Based on Constraint Programming, Artificial Intelligence, 170(3), 2006, 298-397.
• [36] Wolpert, D. H., Macready, W. G.: No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, 1(1), 1997, 67-82.