[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Planning in Multi-agent Environment Using Strips Representation and Non-cooperative Equilibrium Strategy

  • Published:
Journal of Intelligent and Robotic Systems Aims and scope Submit manuscript

Abstract

In multi-agent (multi-robot) environment each agent tries to achieve its own goals leading usually to goals conflict. However, there exists a group of problems with conflicting goals, satisfaction of which is possible simultaneously. Such problems can be modelled as a STRIPS system (for instance Block World environment). If STRIPS planning problem is invertible than it is possible to apply planning under uncertainty methodologies to solve inverted problem and then find a plan that solves multi-agent problem. In the paper, a multi-agent Block World environment is presented as an invertible STRIPS problem. Two cases are considered: when goals conflict and do not conflict. A necessary condition of plan existence is formulated. In the case when goals conflict and agents have different goal preferences we show that it is possible to use non-cooperative equilibrium strategy for modification of the plan found previously. This modification guarantees the best solution (in the sense of non-cooperative equilibrium) for all agents in some cases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Ambite, J.L., Knoblock, C.A.: Planning by rewriting. J. Artif. Intell. Res. 15, 207–261 (2001)

    MATH  Google Scholar 

  2. Avriel, M., Penn, M., Shpirer, N., Witteboon, S.: Stowage planning for container ships to reduce the number of shifts. Ann. Oper. Res. 76, 55–71 (1998)

    Article  MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  4. Backstrom, Ch.: Computational aspects of reordering plans. J. Artif. Intell. Res. 9, 99–137 (1998)

    MATH  MathSciNet  Google Scholar 

  5. Basar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory. New York: Academic Press (1982)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  7. Boutilier, C., Brafman, R.I.: Partial-order planning with concurrent interacting actions. J. Artif. Intell. Res. 14, 105–136 (2001)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

  10. Gałuszka, A., Świerniak, A.: STRIPS representation and non-cooperative strategies in multi-agent planning. In: Proc. 15th European simulation symposium (SCS), Delft, October 26–29, 2003, pp. 110–115 (2003)

  11. Gałuszka, A., Świerniak, A.: Non-cooperative game approach to multi-robot planning. Int. J. Appl. Math. Comput. Sci. 15(3), 359–367 (2005)

    MATH  MathSciNet  Google Scholar 

  12. Imai, A., Nishimura, E., Papadimitriou, S.: The dynamic berth allocation problem for a container port. Transp. Res. B 35, 401–417 (2001)

    Article  Google Scholar 

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

    MathSciNet  Google Scholar 

  14. Koehler, J., Schuster, K.: Elevator control as a planning problem. In: AIPS-2000, pp. 331–338 (2000)

  15. Kraus, S., Sycara, K., Evenchik, A.: Reaching agreements through argumentation: a logical model and implementation. Artif. Intell. 104, 1–69 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  16. Mesterton-Gibbons, M.: An Introduction to Game-Theoretic Modelling. American Mathematical Society, Providence (2001)

    MATH  Google Scholar 

  17. Nilson, N.J.: Principles of Artificial Intelligence. Toga, Palo Alto (1980)

    Google Scholar 

  18. Papadimitriou, Ch.: Theory of the Complexity. Warsaw: Polich Scientific Publishers (2001)

    Google Scholar 

  19. Slaney, J., Thiebaux, S.: Block world revisited. Artif. Intell. 125, 119–153 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  20. Slavin, T.: Virtual port of call. New. Sci. 15, 40–43 (1996)

    Google Scholar 

  21. Smith, D.E., Weld, D.S.: Conformant graphplan. In: Proc. 15th national conf. on AI (1998)

  22. Weld, D.S.: Recent Advantages in AI Planning. AI Magazine (1999)

  23. Weld, D.S., Anderson, C.R., Smith, D.E.: Extending graphplan to handle uncertainty & sensing actions. In: Proc. 15th national conf. on AI, pp. 897–904 (1998)

  24. Wilson, I.D., Roach, P.A.: Container stowage planning: a methodology for generating computerised solutions. J. Oper. Res. Soc. 51, 1248–1255 (2000)

    MATH  Google Scholar 

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

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Adam Galuszka.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Galuszka, A., Swierniak, A. Planning in Multi-agent Environment Using Strips Representation and Non-cooperative Equilibrium Strategy. J Intell Robot Syst 58, 239–251 (2010). https://doi.org/10.1007/s10846-009-9364-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10846-009-9364-4

Keywords

Navigation