nach oben

Scientific and Technical Information Processing

Erschienen in:

01.12.2023

Efficient Bounded-Suboptimal Search for the Multiagent Pathfinding Problem

verfasst von: A. A. Andreichuk

Erschienen in: Scientific and Technical Information Processing | Ausgabe 5/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract—

This article considers the problem of planning a complex of nonconflicting paths for a set of agents that are capable of performing actions of arbitrary duration. Two bounded-suboptimal modifications of a conflict-based search algorithm are proposed as solutions to the problem. The results of model experimental studies demonstrate the high computational efficiency of the proposed modifications.

Nächster Artikel Problems of Combining Multiple Text Recognition Results

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bukhvalov, O.L., Gorodetskii, V.I., Karasev, O.V., et al., Insdustrial logistics: Strategic planning, forecasting, and conflict management, Izv. Yuzhnogo Fed. Univ., 2012, no. 3, pp. 209–218.

Ivanov, A.M., Development of interobject interaction system for smart transport vehicles, Izv. Volgogradsk. Gos. Tekh. Univ. Ser. Nazemnye Transp. Sist., 2013, vol. 7, no. 21, pp. 74–77.

Ronzhin, A.L., Vu, D.K., Nguen, V.V., and Solenaya, O.Ya., Conceptual and algorithmic models of joing functioning of a robotized platform and a UAW set at execution of agricultural operations, IV vserossiiskii nauchno-prakticheskii seminar Bespilotnye transportnye sredstva s elementami iskusstvennogo intellekta (4th All-Russ. Sci.-Pract. Workshop on Unmanned Transport Vehicles with Elements of Artificial Intelligence), Kazan: 2017, pp. 183–192.

Motienko, A.I., Planning of a tactical trajectory of motion of automated robotic tools at emergency mitigation, Nauchn. Vedomosti Belgorodskogo Gos. Univ. Ser.: Ekon. Inf., 2016, vol. 37, no. 2, pp. 139–143. https://doi.org/10.17223/19988605/37CrossRef

Erdmann, M. and Lozano-Pérez, T., On multiple moving objects, Algorithmica, 1987, vol. 2, nos. 1–4, pp. 477–521. https://doi.org/10.1007/bf01840371MathSciNetCrossRef

Standley, T., Finding optimal solutions to cooperative pathfinding problems, Proc. AAAI Conf. Artif. Intell., 2010, vol. 24, no. 1, pp. 173–178. https://doi.org/10.1609/aaai.v24i1.7564

Hart, P.E., Nilsson, N.J., and Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 1968, vol. 4, no. 2, pp. 100–107. https://doi.org/10.1109/tssc.1968.300136CrossRef

Sharon, G., Stern, R., Felner, A., and Sturtevant, N.R., Conflict-based search for optimal multi-agent pathfinding, Artif. Intell., 2015, vol. 219, pp. 40–66. https://doi.org/10.1016/j.artint.2014.11.006MathSciNetCrossRef

Wagner, G. and Choset, H., M*: A complete multirobot path planning algorithm with performance bounds, 2011 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, San Francisco, 2011, IEEE, 2011, pp. 3260–3267. https://doi.org/10.1109/iros.2011.6095022

10.

Sharon, G., Stern, R., Goldenberg, M., and Felner, A., The increasing cost tree search for optimal multi-agent pathfinding, Artif. Intell., 2013, vol. 195, pp. 470–495. https://doi.org/10.1016/j.artint.2012.11.006MathSciNetCrossRef

11.

Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D., and Shimony, E., ICBS: The improved conflict-based search algorithm for multi-agent pathfinding, Proc. Int. Symp. Comb. Search, 2015, vol. 6, no. 1, pp. 223–225. https://doi.org/10.1609/socs.v6i1.18343

12.

Felner, A., Li, J., Boyarski, E., Ma, H., Cohen, L., Kumar, T.S., and Koenig, S., Adding heuristics to conflict-based search for multi-agent path finding, Proc. Int. Conf. Automated Planning Scheduling, 2018, vol. 28, pp. 83–87. https://doi.org/10.1609/icaps.v28i1.13883

13.

Barer, M., Sharon, G., Stern, R., and Felner, A., Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem, Proc. Int. Symp. Comb. Search, 2014, vol. 5, no. 1, pp. 19–27. https://doi.org/10.1609/socs.v5i1.18315

14.

Li, J., Ruml, W., and Koenig, S., EECBS: A bounded-suboptimal search for multi-agent path finding, Proc. AAAI Conf. Artif. Intell., 2021, vol. 35, no. 14, pp. 12353–12362. https://doi.org/10.1609/aaai.v35i14.17466

15.

Yakovlev, K. and Andreychuk, A., Any-angle pathfinding for multiple agents based on sipp algorithm, Proc. Int. Conf. Automated Planning Scheduling, 2017, vol. 27, pp. 586–594. https://doi.org/10.1609/icaps.v27i1.13856

16.

Walker, T., Sturtevant, N., and Felner, A., Extended increasing cost tree search for non-unit cost domains, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, 2018, pp. 534–540. https://doi.org/10.24963/ijcai.2018/74

17.

Cohen, L., Uras, T., Kumar, T.S., and Koenig, S., Optimal and bounded-suboptimal multi-agent motion planning, Proc. Int. Symp. Comb. Search, 2019, vol. 10, no. 1, pp. 44–51. https://doi.org/10.1609/socs.v10i1.18501

18.

Guy, S.J. and Karamouzas, I., Guide to anticipatory collision avoidance, Game AI Pro 2, Rabin, S., Ed., CRC Press, 2015, pp. 224–237. https://doi.org/10.1201/b18373-25CrossRef

19.

Phillips, M. and Likhachev, M., SIPP: Safe interval path planning for dynamic environments, 2011 IEEE Int. Conf. on Robotics and Automation, Shanghai, 2011, IEEE, 2011, pp. 5628–5635. https://doi.org/10.1109/icra.2011.5980306

20.

Pearl, J. and Kim, J.H., Studies in semi-admissible heuristics, IEEE Trans. Pattern Anal. Mach. Intell., 1982, vol. PAMI-4, no. 4, pp. 392–399. https://doi.org/10.1109/tpami.1982.4767270CrossRef

21.

Thayer, J.T. and Ruml, W., Bounded suboptimal search: A direct approach using inadmissible estimates, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-2011), Barcelona, 2011, Walsh, T., Ed., AAAI Press, 2011, pp. 674–679.

22.

Sturtevant, N.R., Benchmarks for grid-based pathfinding, IEEE Trans. Comput. Intell. AI Games, 2012, vol. 4, no. 2, pp. 144–148. https://doi.org/10.1109/tciaig.2012.2197681CrossRef

Titel: Efficient Bounded-Suboptimal Search for the Multiagent Pathfinding Problem
verfasst von: A. A. Andreichuk
Publikationsdatum: 01.12.2023
Verlag: Pleiades Publishing
Erschienen in: Scientific and Technical Information Processing / Ausgabe 5/2023
Print ISSN: 0147-6882
Elektronische ISSN: 1934-8118
DOI: https://doi.org/10.3103/S0147688223050015

Springer Professional

Abstract—

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 5/2023

Reflex or Reflection? The Oculomotor Behavior of the Companion Robot, Creating the Impression of Communicating with an Emotional Being

The IACPaaS Platform for Developing Systems Based on Ontologies: A Decade of Use

Method of Training a Kernel Tree

A Method for Deepfake Detection Using Convolutional Neural Networks

Representation of Syntactic Structures with Coordinating Conjunctions

Formalization of the Structural Synthesis of Technical Systems at the Initial Stage of Design

Premium Partner