Abstract
We identify a new class of algorithms for multi-robot problems called “Any-Com” and present the first algorithm belonging to that class: “Any-Com intermediate solution sharing” (or Any-Com ISS) for multi-robot path planning. Any-Com algorithms find a suboptimal solution quickly and then refine that solution subject to communication constraints. This is analogous to the “Any-Time” framework, in which a suboptimal solution is found quickly, and refined as time permits. The current paper focuses on the task of finding a coordinated set of collisionfree paths for all robots in a common area. The computational load of calculating a solution is distributed among all robots, such that the robotic team becomes a distributed computer. Any-Com ISS is probabilistically/resolution complete and a particular robot contributes to the global solution as much as communication reliability permits. Any-Com ISS is “Centralized” in the planning-algorithmic sense that all robots are viewed as pieces of a composite robot; however, there is no dedicated leader and all robots have the same priority. Previous centralized multi-robot navigation algorithms make assumptions about communication topology and bandwidth that are often invalid in the real world. Any-Com allows for collaborative problem solving with graceful performance declines as communication deteriorates. Results are validated experimentally with a team of 5 robots.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aronov, B., de Berg, M., van der Stappen, A.F., Svestka, P., Vleugels, J.: Motion planning for multiple robots. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, USA, pp. 374–382 (1998)
Boddy, M., Dean, T.L.: Solving time-dependent planning problems. In: Proc. Eleventh International Joint Conference on Artificial Intelligence, pp. 979–984 (1989)
Bonert, M.: Motion planning for multi-robot assembly systems. MS dissertation, University of Toronto (1999)
Clark, C.M., Rock, S.: Randomized motion planning for groups of nonholonomic robots. In: Proc. International Symposium of Artificial Intelligence, Robotics and Automation in Space (2001)
Clark, C.M., Rock, S.M., Latombe, J.C.: Motion planning for multiple mobile robots using dynamic networks. In: Proc. IEEE International Conference on Robotics and Automation, pp. 4222–4227 (2003)
Erdmann, M., Lozano-Perez, T.: On multiple moving objects. Algorithmica, 477–521 (1987)
Ferguson, D., Stentz, A.: Anytime rrts. In: Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5369–5375 (2006)
Guo, Y., Parker, L.D.: A distributed and optimal motion planning approach for multiple mobile robots. In: Proc. IEEE International Conference on Robotics and Automation, pp. 2612–2619 (2002)
Hada, Y., Takasa, K.: Multiple mobile robot navigation using the indoor global positioning system (igps). In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Hawaii, United States, pp. 1005–1010 (2001)
Hollinger, G., Singh, S.: Multi-robot coordination with periodic connectivity. In: Proc. IEEE International Conference on Robotics and Automation (2010)
Kant, K., Zuker, S.W.: Toward efficient trajectory planning: the path-velocity decomposition. The International Journal of Robotics Research 5, 72–89 (1986)
LaValle, S., Keffner, J.: Rapidly-exploring random trees: Progress and prospects. In: Algorithmic and Computational Robotics: New Directions, pp. 293–308 (2001)
Leroy, S., Laumond, J.P., Simeon, T.: Multiple path coordination for mobile robots: a geometric algorithm. In: Proc. International Conference on Artificial Intelligence (1999)
Lumelsky, V.J., Harinarayan, K.R.: Decentralized motion planning for multiple mobile robots: The cocktail party model. Autonomous Robots 4, 121–135 (1997)
Sanchez, G., Latombe, J.C.: Using a prm planner to compare centralized and decoupled planning for multi robot systems. In: Proc. IEEE International Conference on Robotics and Automation (2002)
Schwartz, J.T., Sharir, M.: On the piano mover’s problem iii. coordinating the motion of several independent bodies: the special case of circular bodies amidst polygonal barriers. In: Proc. IEEE International Conference on Robotics and Automation, pp. 514–522 (1985)
van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-body collision avoidance. In: Proc. International Symposium on Robotics Research (2009)
Warren, C.W.: Multiple robot path coordination using artificial potential fields. In: Proc. of IEEE International Conference on Robotics and Automation, Cincinnati, OH, pp. 500–505 (1990)
Xidias, E.K., Aspragathos, N.A.: Motion planning for multiple non-holonomic robots: a geometric approach. Robotica 26, 525–536 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Otte, M., Correll, N. (2013). Any-Com Multi-robot Path-Planning: Maximizing Collaboration for Variable Bandwidth. In: Martinoli, A., et al. Distributed Autonomous Robotic Systems. Springer Tracts in Advanced Robotics, vol 83. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32723-0_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-32723-0_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32722-3
Online ISBN: 978-3-642-32723-0
eBook Packages: EngineeringEngineering (R0)