Non-cooperative game approach to multi-robot planning

Gałuszka, Adam ; Świerniak, Andrzej

International Journal of Applied Mathematics and Computer Science, Tome 15 (2005), p. 359-367 / Harvested from The Polish Digital Mathematics Library

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

Publié le : 2005-01-01

Zbl 1169.91327

EUDML-ID : urn:eudml:doc:207750

Bibliographie

[000] 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. | Zbl 0895.90082

[001] 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. | Zbl 0962.90049

[002] 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. | Zbl 0948.68088

[003] Basar T. and Olsder G.J. (1982): Dynamic Noncooperative Game Theory. - New York: Academic Press. | Zbl 0479.90085

[004] 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. | Zbl 1007.68160

[005] 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. | Zbl 1005.90032

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

[007] Bylander T. (1994): The computational complexity of propositional STRIPS planning. - Artif. Intell., Vol. 69, pp. 165-204. | Zbl 0821.68065

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

[009] 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.

[010] 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.

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

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

[013] Howe A.E. and Dahlman E. (2002): A critical assessment of benchmark comparison in planning. - J. Artif. Intell. Res., Vol. 17, pp. 1-33. | Zbl 1056.68133

[014] 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.

[015] 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.

[016] 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.

[017] 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. | Zbl 0946.68130

[018] 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. | Zbl 0908.68033

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

[020] Mesterton-Gibbons M. (2001): An Introduction to Game-Theoretic Modelling. - Providence, RI: American Mathematical Society. | Zbl 0967.91002

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

[022] Papadimitriou Ch. (2001): Algorithms, games and the Internet. - Proc. ACM Symp. Theory of Computing, Hersonissos, Greece, pp. 749-753. | Zbl 1323.68022

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

[024] 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. | Zbl 1083.93041

[025] Slaney J. and Thiebaux S. (2001): Block World revisited. - Artif. Intell., Vol. 125, pp. 119-153. | Zbl 0969.68136

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

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

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

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

[030] 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. | Zbl 1107.90318

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

[032] Zhang Y., Wu Ch. and Bai Y. (2001): Implementing prioritized logic programming. - AI Comm., Vol. 14, No. 4, pp. 183-196. | Zbl 1007.68027