Continuous optimisation problem and game theory for multi-agent pathfinding | International Journal of Game Theory Skip to main content
Springer Nature Link
Log in

Continuous optimisation problem and game theory for multi-agent pathfinding

  • Original Paper
  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

Abstract

In the article, we studied the continuous problem for multi-agent pathfinding. We show continuity of the path-traversing time functional and the existence of the optimal path for a single agent. Also, we consider game theory interpretation for multi-agent pathfinding with continuous routes as a game with strategies in a Banach space. Finally, we briefly discuss near-optimal routes and connection of heuristics for pathfinding and integral geometry problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  • Abramsky S, Mellies PA (1999) Concurrent games and full completeness. In: Proceedings of the 14th symposium on logic in computer science, pp 431–442

  • Andreychuk A, Yakovlev K, Atzmon D, et al (2019) Multi-agent pathfinding with continuous time. In: Proceedings of the twenty-eighth international joint conference on artificial intelligence, IJCAI-19. International joint conferences on artificial intelligence organization, Macao, pp 39–45. https://doi.org/10.24963/ijcai.2019/6

  • Bouyer P, Brenguier R, Markey N et al (2012) Concurrent games with ordered objectives. In: Birkedal L (ed) Foundations of software science and computational structures. Springer, Berlin, pp 301–315

    Chapter  Google Scholar 

  • Bouyer P, Brenguier R, Markey N, et al (2011) Nash equilibria in concurrent games with Büchi objectives. In: Proceedings of of FSTTCS’2011, pp 375–386

  • Brenguier R (2013) PRALINE: a tool for computing Nash equilibria in concurrent games. In: Sharygina N, Veith H (eds) Computer aided verification. Springer, Berlin, pp 890–895

    Chapter  Google Scholar 

  • Carlson DA (2001) The existence and uniqueness of equilibria in convex games with strategies in Hilbert spaces. Birkhäuser Boston, Boston, pp 79–97. https://doi.org/10.1007/978-1-4612-0155-7_6

    Book  Google Scholar 

  • Carlson DA (2002) Uniqueness of normalized nash equilibrium for a class of games with strategies in Banach spaces. Springer US, Boston, pp 333–348. https://doi.org/10.1007/978-1-4757-3561-1_18

    Book  Google Scholar 

  • Ivanová M, Surynek P (2014) Adversarial cooperative path-finding: Complexity and algorithms. In: Proceedings of the 2014 IEEE 26th international conference on tools with artificial intelligence. IEEE Computer Society, USA, ICTAI ’14, Pp 75–82. https://doi.org/10.1109/ICTAI.2014.22

  • Khan MA (1986) Equilibrium points of nonatomic games over a Banach space. Trans Am Math Soc 293(2):737–749. https://doi.org/10.2307/2000034

    Article  Google Scholar 

  • Klančar G, Zdešar A, Blažič S, et al (2017) Chapter 4—path planning. In: Klančar G, Zdešar A, Blažič S, et al (eds) Wheeled mobile robotics. Butterworth–Heinemann, Oxford, p 161–206. https://doi.org/10.1016/B978-0-12-804204-5.00004-4, http://www.sciencedirect.com/science/article/pii/B9780128042045000044

  • Kolmogorov AN, Fomin SV (1957) Elements of the theory of functions and functional analysis, Translated from the 1st (1954-[60]) Russian ed., vol 1. Graylock Press, Rochester

    Google Scholar 

  • Kuznetsov AV, Leshhev AS (2017) Programmnaja sreda mnogoagentnogo modelirovanija “psihohod”. pr. dlja jevm No 2017619605. data registracii: 28.08.2017, nomer i data postuplenija zajavki: 2017616880 11.07.2017. pravoobl. a.v. kuznetsov, a.s. leshhev. Programmy dlja JeVM Bazy dannyh Topologii integral’nyh mikroshem (9)

  • Kuznetsov AV (2017a) Cellular automata-based model of group motion of agents with memory and related continuous model. In: Sazhin S, Shchepakina E, Sobolev V, et al (eds) Mathematical Modeling. Information Technology and Nanotechnology 2017, Aachen, no. 1904 in CEUR Workshop Proceedings, pp 223–231. http://ceur-ws.org/Vol-1904/paper38.pdf

  • Kuznetsov AV (2017b) Generation of a random landscape by given configuration entropy and total edge. Comput Technol 22(4):4–10. http://www.ict.nsc.ru/jct/t22n4

  • Kuznetsov AV (2017d) Organization of an agents’ formation through a cellular automaton. Large-Scale Syst Control 70:136–167. http://mi.mathnet.ru/eng/ubs/v70/p136

  • Kuznetsov AV (2020) Game-theoretic model of agents’ motion over a terrain with obstacles. In: 2020 international conference on information technology and nanotechnology (ITNT). IEEE, Samara, Russia, pp 1–5. https://doi.org/10.1109/ITNT49337.2020.9253281

  • Kuznetsov AV (2017) A model of the joint motion of agents with a three-level hierarchy based on a cellular automaton. Comput Math Math Phys 57(2):340–349. https://doi.org/10.1134/S0965542517020099

    Article  Google Scholar 

  • Kuznetsov AV (2017) A simplified combat model based on a cellular automaton. J Comput Syst Sci Int 56(3):397–409. https://doi.org/10.1134/S106423071703011X

    Article  Google Scholar 

  • Kuznetsov AV (2018) Model of the motion of agents with memory based on the cellular automaton. Int J Parallel Emergent Distrib Syst 33(3):290–306. https://doi.org/10.1080/17445760.2017.1410819

    Article  Google Scholar 

  • Kuznetsov AV (2018) On the motion of agents across terrain with obstacles. Comput Math Math Phys 58(1):137–151. https://doi.org/10.1134/S0965542518010098

    Article  Google Scholar 

  • Kuznetsov AV, Shishkina EL, Sitnik SM (2019) Probabilistic properties of near-optimal trajectories of an agent moving over a lattice. J Optim Theory Appl 182(2):768–784. https://doi.org/10.1007/s10957-018-1374-6

    Article  Google Scholar 

  • Ma H, Kumar TKS, Koenig S (2017) Multi-agent path finding with delay probabilities. In: Proceedings of the thirty-first AAAI conference on artificial intelligence (AAAI-17), San Francisco, California, USA, pp 3605–3612. https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14984

  • McLeod RM (1965) Mean value theorems for vector valued functions. Proc Edinburgh Math Soc 14(2):197 – 209. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S0013091500008786

  • Mylvaganam T, Sassano M, Astolfi A (2017) A differential game approach to multi-agent collision avoidance. IEEE Trans Autom Control 62(8):4229–4235. https://doi.org/10.1109/TAC.2017.2680602

    Article  Google Scholar 

  • Schumann A (2014) Payoff cellular automata and reflexive games. J Cell Autom 9(4):287–313

    Google Scholar 

  • Schumann A, Pancerz K (2015) Interfaces in a game-theoretic setting for controlling the plasmodium motions. In: Proceedings of of BIOSIGNALS’2015, Lisbon, Portugal, pp 338–343

  • Schumann A, Pancerz K, Adamatzky A, et al (2014) Bio-inspired game theory: the case of Physarum polycephalum. In: Suzuki J, Nakano T (eds) Proceedings of BICT’2014, Boston, Massachusetts, USA, pp 9–16

  • Sharon G, Stern R, Felner A et al (2015) Conflict-based search for optimal multi-agent pathfinding. Artif Intell 219:40–66. https://doi.org/10.1016/j.artint.2014.11.006

    Article  Google Scholar 

  • Silver D (2010) Cooperative pathfinding. In: Proceedings of the first AAAI conference on artificial intelligence and interactive digital entertainment. AAAI Press, Palo Alto, California, AIIDE’05, pp 117–122. http://dl.acm.org/citation.cfm?id=3022473.3022494

  • Solomon H (1978) Geometric probability. Society for Industrial and Applied Mathematics, Philadelphia. https://doi.org/10.1137/1.9781611970418

    Book  Google Scholar 

  • Sridharan K, Tewari A (2010) Convex games in banach spaces. In: Kalai AT, Mohri M (eds) COLT 2010—the 23rd conference on learning theory, Haifa, Israel, June 27–29, 2010. Omnipress, Madison, WI, pp 1–13. https://www.cs.cornell.edu/%7Esridharan/cvxgames colt2010.pdf

  • Surynek P (2019) Multi-agent path finding with continuous time and geometric agents viewed through satisfiability modulo theories. In: Proceedings of the 3rd IJCAI workshop on multi-agent path finding (WoMAPF 2019). University of Southern California, Los Angeles, p 16. http://surynek.net/publications/files/Surynek_Continuous-MAPF_WoMAPF-2019.pdf

  • Surynek P (2020) Swarms of mobile agents: from discrete to continuous movements in multi-agent path finding. In: 2020 IEEE international conference on systems, man, and cybernetics, SMC 2020, Toronto, ON, Canada, October 11-14, 2020. IEEE, Toronto, pp 3006–3012. https://doi.org/10.1109/SMC42975.2020.9282891

  • Trivers RL (1971) The evolution of reciprocal altruism. Q Rev Biol 46(1):35–57. http://www.jstor.org/stable/2822435

  • Wang Q, Phillips C (2014) Cooperative path-planning for multi-vehicle systems. Electronics 3:636–660

    Article  Google Scholar 

Download references

Funding

This work was funded by the Ministry of Science and Higher Education of the Russian Federation, State Assignment no. FFGZ-2021-0001.

Author information

Author notes

  1. Alexander V. Kuznetsov, Andrew Schumann and Małgorzata Rataj contributed equally to this work.

Authors and Affiliations

  1. Laboratory 90, V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya street, Moscow, 117997, Russia

    Alexander V. Kuznetsov

  2. Department of Cognitive Science and Mathematical Modeling, University of Information Technology and Management, 2 ul. Sucharskiego, 35-225, Rzeszów, Poland

    Andrew Schumann & Małgorzata Rataj

Authors
  1. Alexander V. Kuznetsov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Schumann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Małgorzata Rataj
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander V. Kuznetsov.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kuznetsov, A.V., Schumann, A. & Rataj, M. Continuous optimisation problem and game theory for multi-agent pathfinding. Int J Game Theory 53, 1–41 (2024). https://doi.org/10.1007/s00182-023-00851-6

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00182-023-00851-6

Keywords

Search

Navigation