# Non-cooperative game approach to multi-robot planning

Adam Gałuszka; Andrzej Świerniak

International Journal of Applied Mathematics and Computer Science (2005)

- Volume: 15, Issue: 3, page 359-367
- ISSN: 1641-876X

## Access Full Article

top## Abstract

top## How to cite

topGałuszka, Adam, and Świerniak, Andrzej. "Non-cooperative game approach to multi-robot planning." International Journal of Applied Mathematics and Computer Science 15.3 (2005): 359-367. <http://eudml.org/doc/207750>.

@article{Gałuszka2005,

abstract = {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.},

author = {Gałuszka, Adam, Świerniak, Andrzej},

journal = {International Journal of Applied Mathematics and Computer Science},

keywords = {non-cooperative games; STRIPS language; planning complexity; multi-robot environment; planning problems},

language = {eng},

number = {3},

pages = {359-367},

title = {Non-cooperative game approach to multi-robot planning},

url = {http://eudml.org/doc/207750},

volume = {15},

year = {2005},

}

TY - JOUR

AU - Gałuszka, Adam

AU - Świerniak, Andrzej

TI - Non-cooperative game approach to multi-robot planning

JO - International Journal of Applied Mathematics and Computer Science

PY - 2005

VL - 15

IS - 3

SP - 359

EP - 367

AB - 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.

LA - eng

KW - non-cooperative games; STRIPS language; planning complexity; multi-robot environment; planning problems

UR - http://eudml.org/doc/207750

ER -

## References

top- 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. Zbl0895.90082
- 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. Zbl0962.90049
- 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. Zbl0948.68088
- Basar T. and Olsder G.J. (1982): Dynamic Noncooperative Game Theory. - New York: Academic Press. Zbl0479.90085
- 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. Zbl1007.68160
- 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. Zbl1005.90032
- Boutilier C. and Brafman R.I. (2001): Partial-order planning with concurrent interacting. - Actions. J. Artif. Intell. Res., Vol. 14, pp. 105-136. Zbl0970.68164
- Bylander T. (1994): The computational complexity of propositional STRIPS planning. - Artif. Intell., Vol. 69, pp. 165-204. Zbl0821.68065
- Fabricant A., Papadimitriou Ch. and Talvar K. (2004): The complexity of pure Nash equilibria. - Proc. ACM Symp. Theory of Computing, Chicago, pp. 604-612.
- 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.
- 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.
- 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. Zbl1203.68292
- Gupta N. and Nau D.S. (1992): On the complexity of Blocks-World Planning. -Artif. Intell., Vol. 56, No. 2-3, pp. 223-254. Zbl0785.68046
- Howe A.E. and Dahlman E. (2002): A critical assessment of benchmark comparison in planning. - J. Artif. Intell. Res., Vol. 17, pp. 1-33. Zbl1056.68133
- 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.
- 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.
- 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.
- 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. Zbl0946.68130
- 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. Zbl0908.68033
- Mc Kinsey J.C. (1952): Introduction to the Theory of Games. - New York: Mc Graw Hill.
- Mesterton-Gibbons M. (2001): An Introduction to Game-Theoretic Modelling. - Providence, RI: American Mathematical Society. Zbl0967.91002
- Nilson N.J. (1980): Principles of Artificial Intelligence. - Palo Alto,CA: Toga Publishing Company.
- Papadimitriou Ch. (2001): Algorithms, games and the Internet. - Proc. ACM Symp. Theory of Computing, Hersonissos, Greece, pp. 749-753. Zbl1323.68022
- Papadimitriou Ch. (2001a): Theory of the Complexity. - Warsaw:Polish Scientific Publishers.
- 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. Zbl1083.93041
- Slaney J. and Thiebaux S. (2001): Block World revisited. - Artif. Intell., Vol. 125, pp. 119-153. Zbl0969.68136
- Slavin T. (1996): Virtual port of call. - New Scientist, No. 15, pp. 40-43.
- Smith D.E. and Weld D.S. (1998): Conformant graphplan. - Proc. 15th Nat. Conf. Artificial Intelligence, Madison, Wisconsin, USA, pp. 889-896.
- Weld D.S. (1999): Recent Advantages in AI Planning. - AI Mag.Vol. 20, No. 2, pp. 93-123.
- 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.
- 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. Zbl1107.90318
- Yale Center for Computational Vision and Control (1998): PDDL - The planning domain definition language. - Tech. Report CVC TR-98-003DCS TR-1165.
- Zhang Y., Wu Ch. and Bai Y. (2001): Implementing prioritized logic programming. - AI Comm., Vol. 14, No. 4, pp. 183-196. Zbl1007.68027

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.