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

Abstract

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

How to cite

top

Gał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
  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. Zbl0895.90082
  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. Zbl0962.90049
  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. Zbl0948.68088
  4. Basar T. and Olsder G.J. (1982): Dynamic Noncooperative Game Theory. - New York: Academic Press. Zbl0479.90085
  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. Zbl1007.68160
  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. Zbl1005.90032
  7. 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
  8. Bylander T. (1994): The computational complexity of propositional STRIPS planning. - Artif. Intell., Vol. 69, pp. 165-204. Zbl0821.68065
  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 and Automation, Rhodos, Greece, CD-ROM. Zbl1203.68292
  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. Zbl0785.68046
  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. Zbl1056.68133
  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. Zbl0946.68130
  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. Zbl0908.68033
  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. Zbl0967.91002
  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. Zbl1323.68022
  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. Zbl1083.93041
  26. Slaney J. and Thiebaux S. (2001): Block World revisited. - Artif. Intell., Vol. 125, pp. 119-153. Zbl0969.68136
  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 and 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. Zbl1107.90318
  32. Yale Center for Computational Vision and Control (1998): PDDL - The planning domain definition language. - Tech. Report CVC TR-98-003DCS TR-1165. 
  33. Zhang Y., Wu Ch. and Bai Y. (2001): Implementing prioritized logic programming. - AI Comm., Vol. 14, No. 4, pp. 183-196. Zbl1007.68027

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.