Abstract
We study the planning-acting loop for the multi-agent path finding problem (MAPF). MAPF is a problem of navigating agents from their start positions to specified individual goal positions so that agents do not collide with each other. We focus on executing MAPF plans with a group of Crazyflies, small indoor quadcopters, for which we developed a platform that integrates decision theoretic planning and plan execution modules. Our platform can be used for testing suitability of variants of MAPF for execution with real agents. We show how to modify the existing continuous-time conflict-based search algorithm (CCBS) to produce plans that are suitable for execution with the quadcopters. Our finding is that the CCBS algorithm allows for extensions that can produce safe plans for quadcopters, namely cylindrical protection zone around each quadcopter can be introduced at the planning level.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Agents cannot wait outside vertices hence once the agent starts its (linear) movement between two vertices embedded in the metric space, the agent has to finish its movement and reach the other vertex before it can wait.
- 2.
The original implementation of CCBS supports 2D space with circular agents.
References
Andreychuk, A., Yakovlev, K.S., Surynek, P., Atzmon, D., Stern, R.: Multi-agent pathfinding with continuous time. Artif. Intell. 305, 103662 (2022)
Bitcraze, A.B.: System overview (2022). https://www.bitcraze.io/documentation/system/
Chudý, J., Surynek, P.: ESO-MAPF: bridging discrete planning and continuous execution in multi-agent pathfinding. In: Proceedings of AAAI 2021, pp. 16014–16016. AAAI Press (2021)
Ghallab, M., Nau, D., Traverso, P.: Automated Planning and Acting. Cambridge University Press, Cambridge (2016)
Phillips, M., Likhachev, M.: SIPP: safe interval path planning for dynamic environments. In: Proceedings of ICRA 2011, pp. 5628–5635 (2011)
Ryan, M.R.K.: Exploiting subgraph structure in multi-robot path planning. J. Artif. Intell. Res. (JAIR) 31, 497–542 (2008)
Sharon, G., Stern, R., Felner, A., Sturtevant, N.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40–66 (2015)
Surynek, P.: A novel approach to path planning for multiple robots in bi-connected graphs. In: Proceedigns of ICRA 2009, pp. 3613–3619 (2009)
Acknowledgments
This research has been supported by GAČR - the Czech Science Foundation, grant registration number 22-31346S. We would like to thank anonymous reviewers for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kulhan, M., Surynek, P. (2023). Multi-agent Path Finding for Indoor Quadcopters. In: Mathieu, P., Dignum, F., Novais, P., De la Prieta, F. (eds) Advances in Practical Applications of Agents, Multi-Agent Systems, and Cognitive Mimetics. The PAAMS Collection. PAAMS 2023. Lecture Notes in Computer Science(), vol 13955. Springer, Cham. https://doi.org/10.1007/978-3-031-37616-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-031-37616-0_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-37615-3
Online ISBN: 978-3-031-37616-0
eBook Packages: Computer ScienceComputer Science (R0)