Abstract
The problem of Multi-Agent Path Finding (MAPF) is to find paths for a fixed set of agents from their current locations to some desired locations in such a way that the agents do not collide with each other. This problem has been extensively theoretically studied, frequently using an abstract model, that expects uniform durations of moving primitives and perfect synchronization of agents/robots. In this paper we study the question of how the abstract plans generated by existing MAPF algorithms perform in practice when executed on real robots, namely Ozobots. In particular, we use several abstract models of MAPF, including a robust version and a version that assumes turning of a robot, we translate the abstract plans to sequences of motion primitives executable on Ozobots, and we empirically compare the quality of plan execution (real makespan, the number of collisions).
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
Similar content being viewed by others
References
Atzmon, D., Felner, A., Stern, R., Wagner, G., Barták, R., Zhou, N.: k-robust multi-agent path finding. In: Fukunaga, A., Kishimoto, A. (eds.) Proceedings of the Tenth International Symposium on Combinatorial Search, 16–17 June 2017, Pittsburgh, Pennsylvania, USA, pp. 157–158. AAAI Press (2017). https://aaai.org/ocs/index.php/SOCS/SOCS17/paper/view/15797
Barták, R., Švancara, J., Vlk, M.: A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, 11–13 July 2018, pp. 748–756. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2018). http://dl.acm.org/citation.cfm?id=3237383.3237494
Barták, R., Zhou, N.F., Stern, R., Boyarski, E., Surynek, P.: Modeling and solving the multi-agent pathfinding problem in picat. In: 29th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 959–966. IEEE Computer Society (2017). https://doi.org/10.1109/ICTAI.2017.00147
Boyarski, E., et al.: ICBS: the improved conflict-based search algorithm for multi-agent pathfinding. In: Lelis, L., Stern, R. (eds.) Proceedings of the Eighth Annual Symposium on Combinatorial Search, SOCS 2015, Ein Gedi, the Dead Sea, Israel, 11–13 June 2015, pp. 223–225. AAAI Press (2015). http://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/10974
desJardins, M., Littman, M.L. (eds.): Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, 14–18 July 2013. AAAI Press (2013). http://www.aaai.org/Library/AAAI/aaai13contents.php
Erdem, E., Kisa, D.G., Öztok, U., Schüller, P.: A general formal framework for pathfinding problems with multiple agents. In: desJardins, Littman [5]. http://www.aaai.org/ocs/index.php/AAAI/AAAI13/paper/view/6293
Evollve Inc., Ozobot & OzoBlockly: Welcome to OzoBlockly (2015). https://ozoblockly.com/
Kautz, H.A., Selman, B.: Planning as satisfiability. In: ECAI, pp. 359–363 (1992). https://dl.acm.org/citation.cfm?id=146725
Ozobot & Evollve Inc.: Ozobot—Robots to code, create, and connect with (2018). https://ozobot.com/
Ryan, M.R.K.: Exploiting subgraph structure in multi-robot path planning. J. Artif. Intell. Res. 31, 497–542 (2008). https://doi.org/10.1613/jair.2408
Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40–66 (2015). https://doi.org/10.1016/j.artint.2014.11.006
Sharon, G., Stern, R., Goldenberg, M., Felner, A.: The increasing cost tree search for optimal multi-agent pathfinding. Artif. Intell. 195, 470–495 (2013). https://doi.org/10.1016/j.artint.2012.11.006
Standley, T.S.: Finding optimal solutions to cooperative pathfinding problems. In: Fox, M., Poole, D. (eds.) Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, 11–15 July 2010. AAAI Press (2010). http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1926
Surynek, P.: On propositional encodings of cooperative path-finding. In: IEEE 24th International Conference on Tools with Artificial Intelligence, ICTAI 2012, Athens, Greece, 7–9 November 2012, pp. 524–531. IEEE Computer Society (2012). https://doi.org/10.1109/ICTAI.2012.77
Surynek, P.: Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs. In: 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, 10–12 November 2014, pp. 875–882. IEEE Computer Society (2014). https://doi.org/10.1109/ICTAI.2014.134
Yu, J., LaValle, S.M.: Planning optimal paths for multiple robots on graphs. In: 2013 IEEE International Conference on Robotics and Automation, ICRA 2013, pp. 3612–3617, May 2013. https://doi.org/10.1109/ICRA.2013.6631084
Yu, J., LaValle, S.M.: Structure and intractability of optimal multi-robot path planning on graphs. In: desJardins, Littman [5]. http://www.aaai.org/ocs/index.php/AAAI/AAAI13/paper/view/6111
Acknowledgement
Roman Barták is supported by the Czech Science Foundation under the project P202/12/G061 and together with Jiří Švancara by the Czech-Israeli Cooperative Scientific Research Project 8G15027. This research was also partially supported by SVV project number 260 453.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Barták, R., Švancara, J., Škopková, V., Nohejl, D. (2018). Multi-agent Path Finding on Real Robots: First Experience with Ozobots. In: Simari, G.R., Fermé, E., Gutiérrez Segura, F., Rodríguez Melquiades, J.A. (eds) Advances in Artificial Intelligence – IBERAMIA 2018. IBERAMIA 2018. Lecture Notes in Computer Science(), vol 11238. Springer, Cham. https://doi.org/10.1007/978-3-030-03928-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-030-03928-8_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03927-1
Online ISBN: 978-3-030-03928-8
eBook Packages: Computer ScienceComputer Science (R0)