Abstract
Cooperative pathfinding is often addressed in one of two ways in the literature. In fully coupled approaches, robots are considered together and the plans for all robots are constructed simultaneously. In decoupled approaches, the plans are constructed only for a subset of robots at a time. While decoupled approaches can be much faster than fully coupled approaches, they are often suboptimal and incomplete. Although there exist a few decoupled approaches that achieve completeness, global information (which makes global coordination possible) is assumed. Global information may not be accessible in distributed robotic systems. In this paper, we provide a window-based approach to cooperative pathfinding with limited sensing and communication range in distributed systems (called DisCoF). In DisCoF, robots are assumed to be fully decoupled initially, and may gradually increase the level of coupling in an online and distributed fashion. In some cases, e.g., when global information is needed to solve the problem instance, DisCoF would eventually couple all robots together. DisCoF represents an inherently online approach since robots may only be aware of a subset of robots in the environment at any given point of time. Hence, they do not have enough information to determine non-conflicting plans with all the other robots. Completeness analysis of DisCoF is provided.
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
Ayanian, N., Rus, d., Kumar, V.: Decentralized multirobot control in partially known environments with dynamic task reassignment. In: 3rd IFAC Workshop on Distributed Estimation and Control in Networked Systems (2012)
Bnaya, Z., Felner, A.: Conflict-oriented windowed hierarchical cooperative A\(^*\). In: Proceedings of the 2014 IEEE International Conference on Robotics and Automation (2014)
Clark, C.M., Rock, S.M., Latombe, J.-C.: Motion planning for multiple mobile robots using dynamic networks. In: Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 4222–4227, Sep 2003
de Wilde, B., ter Mors, A.W., Witteveen, C.: Push and rotate: cooperative multi-agent path planning. In: 12th International Conference on Autonomous Agents and Multiagent Systems (2013)
Desaraju, Vishnu R., How, Jonathan P.: Decentralized path planning for multi-agent teams with complex constraints. Auton. Robots 32(4), 385–403 (2012)
Fainekos, Georgios E., Girard, Antoine, Kress-Gazit, Hadas, Pappas, George J.: Temporal logic motion planning for dynamic robots. Automatica 45(2), 343–352 (2009)
Hopcroft, J.E., Schwartz, J.T., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the “warehouseman’s problem”. Int. J. Robot. Res. 3(4), 76–88 (1984)
Jansen, R., Sturtevant, N.: A new approach to cooperative pathfinding. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pp. 1401–1404, Richland, SC, International Foundation for Autonomous Agents and Multiagent Systems (2008)
Liu, L., Shell, A.: Physically routing robots in a multi-robot network: flexibility through a three-dimensional matching graph. Int. J. Robot. Res. 32(12), 1475–1494 (2013)
Luna, R., Bekris, K.: Efficient and complete centralized multirobot path planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (2011)
Otte, M., Bialkowski, J., Frazzoli, E.: Any-com collision checking: sharing certificates in decentralized multi-robot teams. In: Proceedings of the 2014 IEEE International Conference on Robotics and Automation (2014)
Parker, L.E.: Encyclopedia of Complexity and System Science, Path Planning and Motion Coordination in Multiple Mobile Robot Teams. Springer, New York (2009)
Peasgood, M., Clark, C.M., McPhee, J.: A complete and scalable strategy for coordinating multiple robots within roadmaps. IEEE Trans. Robot. 24(2), 283–292 (2008). April
Ryan, M.: Graph decomposition for efficient multi-robot path planning. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, pp. 2003–2008. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2007
Silver, D.: Cooperative pathfinding. In: Conference on Artificial Intelligence and Interactive Digital Entertainment (2005)
Standley, T.: Finding optimal solutions to cooperative pathfinding problems. In: AAAI Conference on Artificial Intelligence (2010)
Standley, T., Korf, R.: Complete algorithms for cooperative pathfinding problems. In: Proceedings of the 22nd International Joint Conference on Artifical Intelligence (2011)
Sturtevant, N., Buro, M.: Improving collaborative pathfinding using map abstraction. In: Artificial Intelligence and Interactive Digital Entertainment (AIIDE), pp. 80–85 (2006)
Wang, K.H.C., Botea, A.: Fast and memory-efficient multi-agent pathfinding. In: International Conference on Automated Planning and Scheduling, pp. 380–387 (2008)
Yu, J., LaValle, S.M.: Multi-agent path planning and network flow. In: Algorithmic Foundations of Robotics X, vol. 86, pp. 157–173. Springer (2013)
Zuluaga, M., Vaughan, R.: Reducing spatial interference in robot teams by local-investment aggression. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005. (IROS 2005), pp. 2798–2805, Aug 2005
Acknowledgments
This research is supported in part by the ARO grant W911NF-13-1-0023, the ONR grants N00014-13-1-0176 and N00014-13-1-0519, and the NSF award CNS 1116136.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Japan
About this paper
Cite this paper
Zhang, Y., Kim, K., Fainekos, G. (2016). DisCoF: Cooperative Pathfinding in Distributed Systems with Limited Sensing and Communication Range. In: Chong, NY., Cho, YJ. (eds) Distributed Autonomous Robotic Systems. Springer Tracts in Advanced Robotics, vol 112 . Springer, Tokyo. https://doi.org/10.1007/978-4-431-55879-8_23
Download citation
DOI: https://doi.org/10.1007/978-4-431-55879-8_23
Published:
Publisher Name: Springer, Tokyo
Print ISBN: 978-4-431-55877-4
Online ISBN: 978-4-431-55879-8
eBook Packages: EngineeringEngineering (R0)