Abstract
In the context of Industry 4.0 and cyber-physical production systems, the role of production logistics is perceived as more and more important in order to reach the overall manufacturing targets. One central aspect in organizing the flow of material consists in task allocation and path planning for transport resources disposing of growing autonomy. There are various approaches for multi-agent path planning as well as the way of dealing with collisions. Collisions are possible due to traffic volume and can either be treated on planning level or in a short-term way on control level.
The paper presents existing strategies for path finding before giving an overview of methods to deal with autonomous transport resources that meet in a manufacturing environment. Then, different existing behaviors and reactions in the case of collision detection based on several criteria are compared. This step allows classifying the strategies depending on the manufacturing environment and its organization.
Chapter PDF
Similar content being viewed by others
References
Kolberg D, Berger C, Pirvu B-C et al. (2016) CyProF - Insights from a Framework for Designing Cyber-Physical Systems in Production Environments. Procedia CIRP 57: 32–37
Reinhart G (ed) (2017) Handbuch Industrie 4.0: Geschäftsmodelle, Prozesse, Technik. Hanser, München
Riechmann C (2013) Reorganisation im Logistikbereich zur Verringerung der Durchlaufzeiten und Lagerbestände: Am Beispiel des Logistikzentrums des Automobilzulieferers HÜCO electronic GmbH. Wirtschaft. Diplomarbeiten Agentur, Hamburg
Delfmann W, ten Hompel M, Kersten W et al. (2018) Logistics as a science: Central research questions in the era of the fourth industrial revolution: Logistics Research, Vol. 11, Bremen
Wiendahl H-P, Reichardt J, Nyhuis P (2014) Handbuch Fabrikplanung: Konzept, Gestaltung und Umsetzung wandlungsfähiger Produktionsstätten, 2., überarb. und erw. Aufl., [elektronische Ressource]. Hanser, München
Kersten W, Seiter M, See Bv et al. (2017) Chancen der digitalen Transformation: Trends und Strategien in Logistik und Supply Chain Management. DVV Media Group GmbH, Hamburg
Günther WA (2012) Algorithmen und Kommunikationssysteme für die Zellurare Fördertechnik. Forschungsbericht / Fml, Lehrstuhl für Fördertechnik Materialfluß Logistik, Technische Universität München. Lehrstuhl für Fördertechnik Materialfluß Logistik (fml) TU München, Garching b. München
Pfeifer H (1989) Grundlagen der Fördertechnik, 5., verbesserte Auflage. Viewegs Fachbücher der Technik. Vieweg+Teubner Verlag, Wiesbaden
Li Q, Adriaansen AC, Udding JT et al. (2011) Design and Control of Automated Guided Vehicle Systems: A Case Study. In: Proceedings of the 18th World Congress, vol 44, pp 13852–13857
Henesey L, Aslam K, Khurum M (2015) Task Coordination of Automated Guided Vehicles in a Container Terminal
Liu C-I, Jula H, Vukadinovic K et al. (2004) Automated guided vehicle system for two container yard layouts. Transportation Research Part C: Emerging Technologies 12(5): 349–368. https://doi.org/10.1016/j.trc.2004.07.014
Draganjac I, Miklic D, Kovacic Z et al. (2016) Decentralized Control of Multi-AGV Systems in Autonomous Warehousing Applications. IEEE Transactions on Automation Science and Engineering 13(4): 1433–1447. https://doi.org/10.1109/tase.2016.2603781
Bordelon Hoff E, Sarker BR (1998) An overview of path design and dispatching methods for automated guided vehicles. Integrated Manufacturing Systems: 296–307
(2019) Drone Automation for Warehouse 4.0: White Paper
Schulze L, Behling S, Buhrs S (2008) Automated Guided Vehicle Systems: a Driver for Increased Business Performance. In: International MultiConference of Engineers and Computer Scientists, IMECS 2008: 19 - 21 March, 2008, Regal Knowloon Hotel, Knowloon, Hong Kong. IAENG, Hong Kong
Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1): 269–271. https://doi.org/10.1007/bf01386390
Hart PE, Nilsson NJ, Raphael B (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions of Systems Science and Cybernetics 2
Warren CW (1993) Fast Path Planning Using Modified A* Method. IEEE: 662–667
Stentz A(T) (1994) The D* Algorithm for Real-Time Planning of Optimal Traverses, Pittsburgh, PA
Koenig S, Likhachev M (2002) D* Lite. AAAI
Stentz A(T) (1995) The Focussed D* Algorithm for Real-Time Replanning. IJCAI proceedings
Fergusin D, Stentz A(T) (2005) The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-Uniform Cost Environments, Pittsburgh, PA
Wagner G, Choset H (2011) M*: A Complete Multirobot Path Planning Algorithm with Performance Bounds. In: Amato NM (ed) RSJ International Conference on Intelligent Robots and Systems: 25 - 30 Sept. 2011, San Francisco, USA. IEEE, Piscataway, NJ, pp 3260–3267
Gonzalez JP, Stentz A(T) (2005) Planning with uncertainty in position: an optimal and efficient planner. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, pp 2435–2442
Wagner G, Choset H (2017) Path Planning for Multiple Agents under Uncertainty. In: Proceedings of the 27th International Conference on Automated Planning and Scheduling, pp 577–585
Nebel B, Bolander T, Engesser T et al. (2019) Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty. jair 64: 497–527. https://doi.org/10.1613/jair.1.11376
Ma H, Kumar TKS, Koenig S (2017) Multi-Agent Path Finding with Delay Probabilities. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp 3605–3612
Wang K-HC (2009) Bridging the Gap Between Centralised and Decentralised Multi-Agent Pathfinding. AAAI
Felner A, Li J, Boyarski E et al. (2018) Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding. In: Proceedings of the 28th International Conference on Automated Planning and Scheduling, pp 83–87
Andreychuk A, Yakovlev K, Atzmon D et al. (2019) Multi-Agent Pathfinding with Continuous Time. IJCAI proceedings
Wei C, Hindriks KV, Jonker CM (2014) Multi-robot Cooperative Pathfinding: A Decentralized Approach. In: Ali M, Pan J-S, Chen S-M et al. (eds) Modern Advances in Applied Intelligence: Proceedings, Part I. Springer International Publishing, Cham Heidelberg New York Drodrecht London, pp 21–31
Trodden P, Richards A (2006) Robust Distributed Model Predictive Control using Tubes. In: Proceedings of the 2006 American Control Conference. IEEE, pp 2034–2039
Desaraju VR, How JP (2011) Decentralized path planning for multi-agent teams in complex environments using rapidly-exploring random trees. In: 2011 IEEE International Conference on Robotics and Automation. IEEE, pp 4956–4961
Liu M, Ma H, Li J et al. (2019) Task and Path Planning for Multi-Agent Pickup and Delivery. In: Proceedings of the 18th International Conference on Autonomous and Multiagent Systems 2019, pp 1152–1160
Kiarostami MS, Daneshvaramoli MR, Monfared SK et al. (2019) Multi-Agent non-Overlapping Pathfinding with Monte-Carlo Tree Search. In: IEEE Conference on Games 2019: London, United Kingdom, 20-23 August 2019. IEEE], [Piscataway, New Jersey]
Sun D, Kleiner A, Nebel B (2014) Behavior-based Multi-Robot Collision Avoidance. In: 2014 IEEE International Conference on Robotics & Automation. IEEE, pp 1668–1673
Gochev I, Nadzinski G, Stankovski M (2017) Path Planning and Collision Avoidance Regime for a Multi-Agent System in Industrial Robotics. In: Scientific technical Union of Mechanical Engineering “Industry 4.0” (ed) Machines. Technologies. Materials.: International journal for science, technics and innovations for the industry, pp 519–522
Chang DE, Shadden SC, Marsden JE et al. (2003) Collision avoidance for multiple agent systems. In: 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475). IEEE, pp 539–543
Chen YF, Liu M, Everett M et al. (2016) Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning
. van den Berg J, Lin M, Manocha D (2008) Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation. In: IEEE International Conference on Robotics and Automation, 2008: ICRA 2008 ; 19 - 23 May 2008, [Pasadena, CA]. IEEE, Piscataway, NJ, pp 1928–1935
Adam D (1998) Produktions-Management. Gabler Verlag, Wiesbaden
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Krä, M., Vogt, L., Spannagl, V., Schilp, J. (2020). Multi-agent path planning: comparison of different behaviors in the case of collisions. In: Schüppstuhl, T., Tracht, K., Henrich, D. (eds) Annals of Scientific Society for Assembly, Handling and Industrial Robotics. Springer Vieweg, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-61755-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-662-61755-7_20
Published:
Publisher Name: Springer Vieweg, Berlin, Heidelberg
Print ISBN: 978-3-662-61754-0
Online ISBN: 978-3-662-61755-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)