Coordinating Multiple Robots
Planning the motions of mulitple robots has become increasingly important in recent years. Examples include warehouse logistics (think of Amazon and Alibaba warehouses), swarms of drones, and autonomous vehicles. Several highlights of our work on multiple robot coordination are:
- Efficiently computing optimal coordination routes for hundreds of robots in a tightly constrained space via integer linear programming (TRO 16).
- Introducing Pareto-optimal coordination for multiple robots having independent goals on a roadmap of paths (TRA 98).
- Controlling multiple vehicles to rendezvous by each loosely observing the general direction of others, without any ability to measure Cartesian coordinates (TAC 07).
- Nearly brainless groups of robots that achieve tasks from simple bouncing laws and small amounts of occasional sensor feedback (ACC 12).
Papers on Coordinating Multiple Robots
A hardware and software testbed for underactuated self-assembling robots. A. Q. Nilles, J. Wasserman, A. Born, C. Horn, J. Born, and S. M. LaValle. In International Symposium on Multi-Robot and Multi-Agent Systems, pages 7-9, 2019. [pdf].
Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics. J. Yu and S. M. LaValle. IEEE Transactions on Robotics, 32(5):1163-1177, 2016. [pdf].
Fast, near-optimal computation for multi-robot path planning on graphs. J. Yu and S. M. LaValle. In AAAI Conference on Artificial Intelligence (AAAI-13), 2013. [pdf].
Structure and intractability of optimal multi-robot path planning on graphs. J. Yu and S. M. LaValle. In AAAI Conference on Artificial Intelligence (AAAI-13), 2013. [pdf].
Planning optimal paths for multiple robots on graphs. J. Yu and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2013. [pdf].
Efficient formation path planning on large graphs. M. Katsev, J. Yu, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2013. [pdf].
Time optimal multi-agent path planning on graphs. J. Yu and S. M. LaValle. In Proc. AAAI Workshop on Multiagent Pathfinding (WoMP), 2012. [pdf].
Distance optimal formation control on graphs with a tight convergence time guarantee. J. Yu and S. M. LaValle. In IEEE Conference on Decision and Control, 2012. [pdf].
Controlling wild mobile robots using virtual gates and discrete transitions. L. Bobadilla, F. Martinez, E. Gobst, K. Gossman, and S. M. LaValle. In Proc. American Control Conference, 2012. [pdf].
Controlling wild bodies using discrete transition systems. L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. 2012. Unpublished manuscript, [pdf].
Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. IEEE Transactions on Automatic Control, 57(2):421-434, 2012. [pdf].
Controlling wild bodies using linear temporal logic. L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. In Proceedings Robotics: Science and Systems, 2011. [pdf].
Manipulating ergodic bodies through gentle guidance. L. Bobadilla, K. Gossman, and S. M. LaValle. In Proceedings IEEE Conference on Robot Motion and Control, 2011. [pdf].
Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. In Proceedings IEEE Conference Decision and Control, pages 1803-1808, 2008. [pdf].
Exact Pareto optimal coordination of two translating polygonal robots on a cyclic roadmap. H. Chitsaz, S. M. LaValle, and J. M. O'Kane. In Proceedings 20th Canadian Conference on Computational Geometry, pages 179-182, 2008. [pdf].
Chapter 7: Extensions of Basic Motion Planning, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].
Nonpositive curvature and pareto-optimal coordination of robots. R. Ghrist and S. M. LaValle. SIAM Journal of Control and Optimization, 45(5):1697-1713, 2006. [pdf].
Computing Pareto Optimal Coordinations on Roadmaps. R. Ghrist, J. M. O'Kane, and S. M. LaValle. International Journal of Robotics Research, 24(11):997-1010, 2005. [pdf].
Pareto optimal coordination on roadmaps. R. Ghrist, J. M. O'Kane, and S. M. LaValle. In M. Erdmann, D. Hsu, M. Overmars, and A. F. van der Stappen, editors, Algorithmic Foundations of Robotics, VI. Springer-Verlag, Berlin, 2005. [pdf].
Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap. H. Chitsaz, J. M. O'Kane, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2004. [pdf].
Optimal motion planning for multiple robots having independent goals. S. M. LaValle and S. A. Hutchinson. IEEE Trans. on Robotics and Automation, 14(6):912-925, December 1998. [pdf].
A game-theoretic framework for robot motion planning. S. M. LaValle. PhD thesis, University of Illinois, Urbana-Champaign, USA, July 1995. [pdf].
Path selection and coordination of multiple robots via Nash equilibria. S. M. LaValle and S. A. Hutchinson. In Proceedings IEEE International Conference on Robotics and Automation, pages 1847-1852, May 1994. [pdf].
Game theory as a unifying structure for a variety of robot tasks. S. M. LaValle and S. A. Hutchinson. In Proceedings IEEE International Symposium on Intelligent Control, pages 429-434, August 1993. [pdf].