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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ambite, J.L., Knoblock, C.A.: Planning by rewriting. J. Artif. Intell. Res. 15, 207–261 (2001)
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)
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)
Backstrom, Ch.: Computational aspects of reordering plans. J. Artif. Intell. Res. 9, 99–137 (1998)
Basar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory. New York: Academic Press (1982)
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)
Boutilier, C., Brafman, R.I.: Partial-order planning with concurrent interacting actions. J. Artif. Intell. Res. 14, 105–136 (2001)
Bylander, T.: The computational complexity of propositional STRIPS planning. Artif. Intell. 69, 165–204 (1994)
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)
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)
Gałuszka, A., Świerniak, A.: Non-cooperative game approach to multi-robot planning. Int. J. Appl. Math. Comput. Sci. 15(3), 359–367 (2005)
Imai, A., Nishimura, E., Papadimitriou, S.: The dynamic berth allocation problem for a container port. Transp. Res. B 35, 401–417 (2001)
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)
Koehler, J., Schuster, K.: Elevator control as a planning problem. In: AIPS-2000, pp. 331–338 (2000)
Kraus, S., Sycara, K., Evenchik, A.: Reaching agreements through argumentation: a logical model and implementation. Artif. Intell. 104, 1–69 (1998)
Mesterton-Gibbons, M.: An Introduction to Game-Theoretic Modelling. American Mathematical Society, Providence (2001)
Nilson, N.J.: Principles of Artificial Intelligence. Toga, Palo Alto (1980)
Papadimitriou, Ch.: Theory of the Complexity. Warsaw: Polich Scientific Publishers (2001)
Slaney, J., Thiebaux, S.: Block world revisited. Artif. Intell. 125, 119–153 (2001)
Slavin, T.: Virtual port of call. New. Sci. 15, 40–43 (1996)
Smith, D.E., Weld, D.S.: Conformant graphplan. In: Proc. 15th national conf. on AI (1998)
Weld, D.S.: Recent Advantages in AI Planning. AI Magazine (1999)
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)
Wilson, I.D., Roach, P.A.: Container stowage planning: a methodology for generating computerised solutions. J. Oper. Res. Soc. 51, 1248–1255 (2000)
Yale Center for Computational Vision and Control: PDDL—The planning domain definition language. Tech report CVC TR-98-003/DCS TR-1165 (1998)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-009-9364-4