We consider the coordination of multiple robots in a common environment, each robot having its own (distinct) roadmap. Our primary contribution is a classification of and exact algorithm for computing vector-valued (or Pareto) optima for collision-free coordination. We indicate the utility of new geometric techniques from CAT(0) geometry and give an argument that curvature bounds are the key distinguishing feature between systems for which the classification is finite and for those in which it is not.
Get full access to this article
View all access options for this article.
References
1.
Abrams, A. and Ghrist, R. 2004. State complexes for metamorphic robot systems . International Journal of Robotics Research23(7,8): 809-824 .
2.
Akella, S. and Hutchinson, S. 2002. Coordinating the motions of multiple robots with specified trajectories . Proceedings of the IEEE International Conference on Robotics and Automation, Washington, DC, May 11-15, pp. 624-631 .
3.
Ardema, M. D. and Skowronski, J. M. 1991. Dynamic game applied to coordination control of two arm robotic system. Differential Games - Developments in Modelling and Computation, R. P. Hämäläinen and H. K. Ehtamo, editors, Springer-Verlag, Berlin , pp. 118-130.
4.
Barraquand, J. and Latombe, J.-C. 1991. Robot motion planning: a distributed representation approach . International Journal of Robotics Research10(6): 628-649 .
5.
Başar, T. and Olsder, G. J. 1982. Dynamic Non-cooperative Game Theory, Academic Press, London.
6.
Bien, Z. and Lee, J. 1992. A minimum-time trajectory planning method for two robots . IEEE Transactions on Robotics and Automation8(3): 414-418 .
7.
Bridson, M. and Haefliger, A. 1999. Metric Spaces of Non-positive Curvature, Springer-Verlag, Berlin.
8.
Buckley, S. J. 1989. Fast motion planning for multiple moving robots . Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, AZ, pp. 322-326 .
9.
Canny, J. and Reif, J. 1987. Lower bounds for shortest path and related problems . Proceedings of the 28th Annual IEEE Symposium on Foundation of Computer Science, Los Angeles, CA, pp. 49-60 .
10.
Chang, C., Chung, M. J., and Lee, B. H. 1994. Collision avoidance of two robot manipulators by minimum delay time . IEEE Transactions on Systems, Man, and Cybernetics24(3): 517-522 .
11.
Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L. J., Hershberger, J., Sharir, M., and Snoeyink, J. 1994. Ray shooting in polygons using geodesic triangulations . Algorithmica12: 54-68 .
12.
Chitsaz, H., O'Kane, J. M., and LaValle, S. M. 2004. Exact Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap . Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA.
13.
de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 1997. Computational Geometry: Algorithms and Applications, Springer, Berlin.
14.
Epstein, D.et al. 1992. Word Processing in Groups, Jones & Bartlett Publishers, Boston, MA.
15.
Erdmann, M. and Lozano-Perez, T. 1986. On multiple moving objects . Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, pp. 1419-1424 .
Gromov, M. 1987. Hyperbolic groups. Essays in Group Theory, S. Gersten, editor, Mathematical Sciences Research Institute Publications Vol. 8, Springer, New York , pp. 75-263.
18.
Guibas, L. J., Latombe, J.-C., LaValle, S. M., Lin, D., and Motwani, R. 1999. Visibility-based pursuit-evasion in a polygonal environment . International Journal of Computational Geometry and Applications9(5): 471-494 .
19.
Hatcher, A. 2001. Algebraic Topology, Cambridge University Press, Cambridge.
20.
Hershberger, J. and Suri, S. 1999. An optimal algorithm for Euclidean shortest paths in the plane . SIAM Journal of Computing28(6): 2215-2256 .
21.
Hu, H., Brady, M., and Probert, P. 1991. Coping with uncertainty in control and planning for a mobile robot . Proceedings of the IEEE/RSJ International Workshop on Intelligent Robots and Systems, Osaka, Japan, November, pp. 1025-1030 .
22.
Isaacs, R. 1965. Differential Games, Wiley, New York.
23.
Isler, V., Kannan, S., and Khanna, S. 2004. Randomized pursuit-evasion with limited visibility . Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, January 11-13, pp. 1053-1063 .
24.
Kant, K. and Zucker, S. W. 1986. Toward efficient trajectory planning: the path-velocity decomposition . International Journal of Robotics Research5(3): 72-89 .
25.
Kirkpatrick, D. G. 1983. Optimal search in planar subdivisions . SIAM Journal of Computing12(1): 28-35 .
26.
LaValle, S. M. and Hutchinson, S. A. 1994. Path selection and coordination of multiple robots via Nash equilibria . Proceedings of the IEEE International Conference on Robotics and and Automation, San Diego, CA, May, pp. 1847-1852 .
27.
LaValle, S. M. and Hutchinson, S. A. 1998. Optimal motion planning for multiple robots having independent goals . IEEE Transactions on Robotics and Automation14(6): 912-925 .
28.
Mitchell, J. and Sharir, M. 2004. New results on shortest paths in three dimensions . Proceedings of the 20th ACM Symposium of Computation Geometry, Polytechnic University in Brooklyn, New York, June 9-11, pp. 124-133 .
29.
Miura, J. and Shirai, Y. 1991. Planning of vision and motion for a mobile robot using a probabilistic model of uncertainty . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Osaka, Japan, May, pp. 403-408 .
30.
Niblo, G. A. and Reeves, L. D. 1998. The geometry of cube complexes and the complexity of their fundamental groups . Topology37(3): 621-633 .
31.
O'Donnell, P. A. and Lozano-Pérez, T. 1989. Deadlock-free and collision-free coordination of two robot manipulators . Proceedings of the IEEE International Conference on Robotics and Automation, Scottsdale, AZ, pp. 484-489 .
32.
Parker, L. E. 1998. Cooperative motion control for multitarget observation . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Victoria, BC, Canada, pp. 1591-1598 .
33.
Parsons, T. D. 1976. Pursuit-evasion in a graph. Theory and Application of Graphs, Y. Alavi and D. R. Lick, editors, Springer-Verlag, Berlin , pp. 426-441.
34.
Peng, J. and Akella, S. 2004. Coordinating multiple robots with kinodynamic constraints along specified paths. Algorithmic Foundations of Robotics V, STAR 7, Springer-Verlag, Berlin , pp. 221-237.
35.
Sawaragi, Y., Nakayama, H., and Tanino, T. 1985. Theory of Multi-objective Optimization, Academic Press, NewYork.
36.
Schwartz, J. T. and Sharir, M. 1983. On the piano movers' problem: III. Coordinating the motion of several independent bodies . International Journal of Robotics Research2(3): 97-140 .
37.
Simeon, T., Leroy, S., and Laumond, J.-P. 2002. Path coordination for multiple mobile robots: a resolution complete algorithm . IEEE Transactions on Robotics and Automation18(1): 42-49 .
38.
Suh, S-H. and Shin, K. G. 1988. A variational dynamic programming approach to robot-path planning with a distance-safety criterion . IEEE Transactions on Robotics and Automation4(3): 334-349 .
39.
Suzuki, I. and Yamashita, M. 1992. Searching for a mobile intruder in a polygonal region . SIAM Journal of Computing21(5): 863-888 .
40.
Svestka, P. and Overmars, M. H. 1995. Coordinated motion planning for multiple car-like robots using probabilistic roadmaps . Proceedings of the IEEE International Conference on Robotics and Automation, Nagoya, Japan, pp. 1631-1636 .
