Non-cooperative game approach to multi-robot planning

Gałuszka, A. ; Świerniak, A.

International Journal of Applied Mathematics and Computer Science, Tome 15 (2005) no. 3, pp. 359-367.

Résumé

A multi-robot environment with a STRIPS representation is considered. Under some assumptions such problems can be modelled as a STRIPS language (for instance, a Block World environment) with one initial state and a disjunction of goal states. If the STRIPS planning problem is invertible, then it is possible to apply the machinery for planning in the presence of incomplete information to solve the inverted problem and then to find a solution to the original problem. In the paper a planning algorithm that solves the problem described above is proposed and its computational complexity is analyzed. To make the plan precise, non-cooperative strategies are used.

Détail

Keywords: planning problems, multi-robot environment, STRIPS language, non-cooperative games, planning complexity
Mots-clés : zagadnienie projektowe, robot wielofunkcyjny, gra niekooperatywna, planowanie kompleksowe

Bibliographie

[1] Avriel M., Penn M., Shpirer N. and Witteboon S. (1998): Stowage planning for container ships to reduce the number of shifts.— Ann. Oper. Res., Vol. 76, pp. 55–71.

[2] Avriel M., Penn M. and Shpirer N. (2000): Container ship stowage problem: complexity and connection to the coloring of circle graphs. — Discr. Appl. Math., Vol. 103, pp. 271–279.

[3] Baral Ch., Kreinovich V. and Trejo R. (2000): Computational complexity of planning and approximate planning in the presence of incompleteness. — Artif. Intell., Vol. 122, pp. 241–267.

[4] Basar T. and Olsder G.J. (1982): Dynamic Noncooperative Game Theory. — New York: Academic Press.

[5] Belker T., Beetz M. and Cremers. A.B. (2002): Learning of plan execution policies for indoor navigation. — AI Comm., Vol. 15, No. 1, pp. 3–16.

[6] Bish E.K., Leong T.Y., Li C.L., Ng J.W.C. and Simchi-Levi D. (2001): Analysis of a new vehicle scheduling and location problem. —Naval Res. Logist., Vol. 48, pp. 363–385.

[7] Boutilier C. and Brafman R.I. (2001): Partial-order planning with concurrent interacting. — Actions. J. Artif. Intell. Res., Vol. 14, pp. 105–136.

[8] Bylander T. (1994): The computational complexity of propositional STRIPS planning. —Artif. Intell., Vol. 69, pp. 165– 204.

[9] Fabricant A., Papadimitriou Ch. and Talvar K. (2004): The complexity of pure Nash equilibria. —Proc. ACM Symp. Theory of Computing, Chicago, pp. 604–612.

[10] Gałuszka A. and Świerniak A. (2002): Planning in multi-agent environment as inverted STRIPS planning in the presence of uncertainty, In: Recent Advances In Computers, Computing and Communications (N. Mastorakis and V. Maldenov, Eds.).—Athens: WSEAS Press, pp. 58–63.

[11] Gałuszka A. and Świerniak A. (2003): STRIPS representation and non-cooperative strategies in multi-robot planning. — Proc. 15th European Simulation Symposium (SCS), Delft, the Netherlands, pp. 110–115.

[12] Gałuszka A. and Świerniak A. (2003a): Invertible planning and non-cooperative equilibrium strategies in multi-agent planning.—Proc. 11th IEEE Mediterranean Conf. Control Automation, Rhodos, Greece, CD-ROM.

[13] Gupta N. and Nau D.S. (1992): On the complexity of Blocks-World Planning. — Artif. Intell., Vol. 56, No. 2–3, pp. 223–254.

[14] Howe A.E. and Dahlman E. (2002): A critical assessment of benchmark comparison in planning. — J. Artif. Intell. Res., Vol. 17, pp. 1–33.

[15] Imai A., Nishimura E. and Papadimitriou S. (2001): The dynamic berth allocation problem for a container port. — Transp. Res., Vol. B 35, pp. 401–417.

[16] Isil Bozma H. and Koditschek D.E. (2001): Assembly as a noncooperative game of its pieces: Analysis of 1D sphere assemblies. —Robotica, Vol. 19, pp. 93–108.

[17] Karacapilidis N.I. and Papadias D. (1998): A computational approach for argumentative discourse in multi-agent decision making environment.—AI Comm., Vol. 11, No. 1, pp. 21–33.

[18] Koehler J. and Hoffmann J. (2000): On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm. — J. Artif. Intell. Res., Vol. 12, pp. 339–386.

[19] Kraus S., Sycara K. and Evenchik A. (1998): Reaching agreements through argumentation: A logical model and implementation. —Artif. Intell., Vol. 1, No. 4, pp. 1–69.

[20] Mc Kinsey J.C. (1952): Introduction to the Theory of Games. — New York: Mc Graw Hill.

[21] Mesterton-Gibbons M. (2001): An Introduction to Game-Theoretic Modelling.—Providence, RI: American Mathematical Society.

[22] Nilson N.J. (1980): Principles of Artificial Intelligence. — Palo Alto, CA: Toga Publishing Company.

[23] Papadimitriou Ch. (2001): Algorithms, games and the Internet. — Proc. ACM Symp. Theory of Computing, Hersonissos, Greece, pp. 749–753.

[24] Papadimitriou Ch. (2001a): Theory of the Complexity. — Warsaw: Polish Scientific Publishers.

[25] Skrzypczyk K. (2005): Control of a team of mobile robots based on non-cooperative equilibria with partial coordination. — Int. J. Appl. Math. Comp. Sci., Vol. 15, No. 1, pp. 89–97.

[26] Slaney J. and Thiebaux S. (2001): Block World revisited. — Artif. Intell., Vol. 125, pp. 119–153.

[27] Slavin T. (1996): Virtual port of call. — New Scientist, No. 15, pp. 40–43.

[28] Smith D.E. and Weld D.S. (1998): Conformant graphplan. — Proc. 15th Nat. Conf. Artificial Intelligence, Madison, Wisconsin, USA, pp. 889–896.

[29] Weld D.S. (1999): Recent Advantages in AI Planning. — AI Mag. Vol. 20, No. 2, pp. 93–123.

[30] Weld D.S., Anderson C.R. and Smith D.E. (1998): Extending graphplan to handle uncertainty sensing actions. — Proc. 15th Nat. Conf. Artificial Intelligence, Madison, Wisconsin, USA, pp. 897–904.

[31] Wilson I.D. and Roach P.A. (2000): Container stowage planning: A methodology for generating computerised solutions. —J. Oper. Res. Soc., Vol. 51, pp. 1248–1255.

[32] Yale Center for Computational Vision and Control (1998): PDDL – The planning domain definition language. —Tech. Report CVC TR-98-003/DCS TR-1165.

[33] Zhang Y., Wu Ch. and Bai Y. (2001): Implementing prioritized logic programming.—AI Comm., Vol. 14, No. 4, pp. 183–196.