An Abstract Framework for Non-Cooperative Multi-Agent Planning
Source abstract
Abstract
In non-cooperative multi-agent planning environments, it is essential to have a system that enables the agents’ strategic behavior. It is also important to consider all planning phases, i.e., goal allocation, strategic planning, and plan execution, in order to solve a complete problem. Currently, we have no evidence of the existence of any framework that brings together all these phases for non-cooperative multi-agent planning environments. In this work, an exhaustive study is made to identify existing approaches for the different phases as well as frameworks and different applicable techniques in each phase. Thus, an abstract framework that covers all the necessary phases to solve these types of problems is proposed. In addition, we provide a concrete instantiation of the abstract framework using different techniques to promote all the advantages that the framework can offer. A case study is also carried out to show an illustrative example of how to solve a non-cooperative multi-agent planning problem with the presented framework. This work aims to establish a base on which to implement all the necessary phases using the appropriate technologies in each of them and to solve complex problems in different domains of application for non-cooperative multi-agent planning settings.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: AI-based Problem Solving and Planning · Logic, Reasoning, and Knowledge · Multi-Agent Systems and Negotiation
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Valencian Research Institute for Artificial Intelligence (VRAIN), Universitat Politècnica de València, Camino de Vera s/n, 46022 Valencia, Spain
Departamento de Inteligencia Artificial, Universidad Politécnica de Madrid, Campus Montegancedo, Boadilla del Monte, 28660 Madrid, Spain
References (67)
Show source-provided references
1. Introduction to Planning in Multiagent Systems10.3233/MGS-2009-0133 ↗
2. Brafman, R.I., Domshlak, C., Engel, Y., and Tennenholtz, M. (2009, January 11–17). Planning Games. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), Pasadena, CA, USA.
3. Solving Coalitional Resource Games10.1016/j.artint.2009.09.005 ↗
4. Bercher, P., and Mattmüller, R. (2008, January 21–25). A Planning Graph Heuristic for Forward-Chaining Adversarial Planning. Proceedings of the European Conference on Artificial Intelligence, Patras, Greece.
5. Cote, E.M.D., Chapman, A., Sykulski, A.M., and Jennings, N. (2010, January 8–11). Automated Planning in Repeated Adversarial Games. Proceedings of the Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010), Catalina Island, CA, USA.
6. Shoham, Y., and Leyton-Brown, K. (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press.10.1017/CBO9780511811654 ↗
7. Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V. (2007). Algorithmic Game Theory, Cambridge University Press.10.1017/CBO9780511800481 ↗
8. Cooperative multi-agent planning: A survey
9. Amato, C., Konidaris, G., Cruz, G., Maynor, C.A., How, J.P., and Kaelbling, L.P. (2015, January 26–30). Planning for decentralized control of multiple robots under uncertainty. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.10.1109/ICRA.2015.7139350 ↗
10. Ontanón, S., and Buro, M. (2015, January 25–31). Adversarial hierarchical-task network planning for complex real-time games. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina.
11. Myerson, R.B. (2013). Game Theory, Harvard University Press.10.2307/j.ctvjsf522 ↗
12. Osborne, M.J., and Rubinstein, A. (1994). A Course in Game Theory, MIT Press.
13. Brandenburger, A. (2007). Cooperative Game Theory, New York University. Teaching Materials at New York University.
14. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving10.1016/0004-3702(71)90010-5 ↗
15. Crosby, M., and Rovatsos, M. (2011, January 2–6). Heuristic Multiagent Planning With Self-Interested Agents. Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Taipei, Taiwan.
16. The FF Planning System: Fast Planning Generation Through Heuristic Search10.1613/jair.855 ↗
17. Hybrid mission planning with coalition formation10.1007/s10458-017-9367-7 ↗
18. Group Planning With Time Constraints10.1007/s10472-013-9363-9 ↗
19. Guo, Y., Pan, Q., Sun, Q., Zhao, C., Wang, D., and Feng, M. (2019, January 12–14). Cooperative Game-based Multi-Agent Path Planning with Obstacle Avoidance. Proceedings of the IEEE 28th International Symposium on Industrial Electronics (ISIE), Vancouver, BC, Canada.10.1109/ISIE.2019.8781205 ↗
20. Zur Theorie Der Gesellschaftsspiele10.1007/BF01448847 ↗
21. Von Neumann, J., and Morgenstern, O. (2007). Theory of Games and Economic Behavior, Princeton University Press.
22. Learning Behavior in an Experimental Matching Pennies Game10.1006/game.1994.1037 ↗
23. Games With Unique, Mixed Strategy Equilibria: An Experimental Study10.1006/game.1995.1030 ↗
24. An Architecture for Adversarial Planning10.1109/21.47820 ↗
25. Jensen, R.M., Veloso, M.M., and Bowling, M.H. (2001, January 12–14). OBDD-Based Optimistic and Strong Cyclic Adversarial Planning. Proceedings of the 6th European Conference on Planning, Toledo, Spain.
26. Sailer, F., Buro, M., and Lanctot, M. (2007, January 1–5). Adversarial Planning Through Strategy Simulation. Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Games, Honolulu, HI, USA.10.1109/CIG.2007.368082 ↗
27. Van Den Herik, H.J., and Iida, H. (1998). An Adversarial Planning Approach to Go. Proceedings of the International Conference on Computers and Games, Springer.
28. Applying Adversarial Planning Techniques to Go10.1016/S0304-3975(00)00076-1 ↗
29. Erol, K., Hendler, J., and Nau, D.S. (1994). HTN Planning: Complexity and Expressivity, AAAI.
30. SHOP2: An HTN planning system10.1613/jair.1141 ↗
31. An Analysis of Alpha-Beta Pruning10.1016/0004-3702(75)90019-3 ↗
32. Nissim, R., and Brafman, R.I. (2013, January 14–18). Cost-Optimal Planning by Self-Interested Agents. Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, WA, USA.10.1609/aaai.v27i1.8640 ↗
33. Counterspeculation, Auctions, and Competitive Sealed Tenders10.1111/j.1540-6261.1961.tb02789.x ↗
34. Multipart Pricing of Public Goods10.1007/BF01726210 ↗
35. Incentives in Teams10.2307/1914085 ↗
36. Van Der Krogt, R., and De Weerdt, M. (2005, January 6–10). Self-Interested Planning Agents Using Plan Repair. Proceedings of the ICAPS 2005 Workshop on Multiagent Planning and Scheduling, Monterey, CA, USA.
37. Savaux, J., Vion, J., Piechowiak, S., Mandiau, R., Matsui, T., Hirayama, K., Yokoo, M., Elmane, S., and Silaghi, M. (2016, January 13–16). DisCSPs with Privacy Recast as Planning Problems for Self-Interested Agents. Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (WI), Omaha, NE, USA.10.1109/WI.2016.0057 ↗
38. Coordinating Self-Interested Planning Agents10.1007/s10458-005-6104-4 ↗
39. Mors, A.T., and Witteveen, C. (2005, January 19–22). Coordinating Non Cooperative Planning Agents: Complexity Results. Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Compiegne, France.
40. Ridesharing on Timetabled Transport Services: A Multiagent Planning Approach10.1080/15472450.2014.941759 ↗
41. Planning in Multi-Agent Environment Using Strips Representation and Non-Cooperative Equilibrium Strategy10.1007/s10846-009-9364-4 ↗
42. Bowling, M.H., Jensen, R.M., and Veloso, M.M. (2003, January 9–15). A Formalization of Equilibria for Multiagent Planning. Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico.
43. Larbi, R.B., Konieczny, S., and Marquis, P. (November, January 31). Extending Classical Planning to the Multi-Agent Case: A Game-Theoretic Approach. Proceedings of the 9th European Conference Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU, Hammamet, Tunisia.
44. Jonsson, A., and Rovatsos, M. (2011, January 11–16). Scaling Up Multiagent Planning: A Best-Response Approach. Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS), Freiburg, Germany.10.1609/icaps.v21i1.13461 ↗
45. A class of games possessing pure-strategy Nash equilibria10.1007/BF01737559 ↗
46. Nissim, R., Brafman, R.I., and Domshlak, C. (2010, January 10–14). A General, Fully Distributed Multi-Agent Planning Algorithm. Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, Toronto, ON, Canada.
47. Jordán, J., and Onaindía, E. (2015, January 25–30). Game-theoretic Approach for Non-Cooperative Planning. Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-15), Austin, TX, USA.10.1609/aaai.v29i1.9384 ↗
48. Arrow, K.J. (1963). Social Choice and Individual Values, Yale University Press. Number 12.
49. A better-response strategy for self-interested planning agents10.1007/s10489-017-1046-5 ↗
50. Case-based planning: Selected methods and systems10.3233/AIC-1996-9305 ↗
51. Hammond, K.J. (2012). Case-Based Planning: Viewing Planning as a Memory Task, Elsevier.
52. Ambros-Ingerson, J.A., and Steel, S. (1988). Integrating Planning, Execution and Monitoring, AAAI.
53. Sycara, K., and Pannu, A.S. (1998, January 10–13). The RETSINA multiagent system: Towards integrating planning, execution, and information gathering. Proceedings of the Second International Conference on Autonomous Agents, Minneapolis, MN, USA.10.1145/280765.280858 ↗
54. Haigh, K.Z., and Veloso, M.M. (1998, January 7–10). Planning, Execution and Learning in a Robotic Agent. Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems, Pittsburgh, PA, USA.
55. Cardoso, R.C., and Bordini, R.H. (2019, January 13–17). Decentralised Planning for Multi-Agent Programming Platforms. Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS ’19), Montreal, QC, Canada.
56. Cardoso, R.C., and Bordini, R.H. (2016, January 13–14). A distributed online multi-agent planning system. Proceedings of the Workshop on Distributed and Mutiltiagent Planning (ICAPS), London, UK.
57. Congestion Games and Potentials Reconsidered10.1142/S0219198999000219 ↗
58. Klemperer, P. (2004). Auctions: Theory and Practice, Princeton University Press.10.1515/9780691186290 ↗
59. Krishna, V. (2009). Auction Theory, Academic Press.
60. Consensus-Based Decentralized Auctions for Robust Task Allocation10.1109/TRO.2009.2022423 ↗
61. Potential games10.1006/game.1996.0044 ↗
62. Learning in Games by Random Sampling10.1006/jeth.2000.2694 ↗
63. Case-based reasoning: Foundational issues, methodological variations, and system approaches10.3233/AIC-1994-7104 ↗
64. Kolodner, J. (2014). Case-Based Reasoning, Morgan Kaufmann.
65. The auction algorithm: A distributed relaxation method for the assignment problem10.1007/BF02186476 ↗
66. The auction algorithm for the transportation problem10.1007/BF02216923 ↗
67. Palanca, J., Terrasa, A., Carrascosa, C., and Julián, V. (2019). SimFleet: A New Transport Fleet Simulator Based on MAS. Proceedings of the International Conference on Practical Applications of Agents and Multi-Agent Systems, Springer.10.1007/978-3-030-24299-2_22 ↗