{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:00:55Z","timestamp":1777716055345,"version":"3.51.4"},"reference-count":40,"publisher":"SAGE Publications","issue":"11","license":[{"start":{"date-parts":[[2005,11,1]],"date-time":"2005-11-01T00:00:00Z","timestamp":1130803200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2005,11]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1177\/0278364905059057","type":"journal-article","created":{"date-parts":[[2005,11,3]],"date-time":"2005-11-03T10:29:17Z","timestamp":1131013757000},"page":"997-1010","source":"Crossref","is-referenced-by-count":28,"title":["Computing Pareto Optimal Coordinations on Roadmaps"],"prefix":"10.1177","volume":"24","author":[{"given":"Robert","family":"Ghrist","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Illinois, Urbana, IL 61801, USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason M.","family":"O'Kane","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana, IL 61801, USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven M.","family":"LaValle","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana, IL 61801, USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2005,11,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Abrams, A. and Ghrist, R. 2004. State complexes for metamorphic robot systems . International Journal of Robotics Research 23(7,8): 809-824 .","DOI":"10.1177\/0278364904045468"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"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 .","DOI":"10.1109\/ROBOT.2002.1013428"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"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\u00e4m\u00e4l\u00e4inen and H. K. Ehtamo, editors, Springer-Verlag, Berlin , pp. 118-130.","DOI":"10.1007\/BFb0040233"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1177\/027836499101000604"},{"key":"atypb5","unstructured":"Ba\u015far, T. and Olsder, G. J. 1982. Dynamic Non-cooperative Game Theory, Academic Press, London."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/70.143360"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"Bridson, M. and Haefliger, A. 1999. Metric Spaces of Non-positive Curvature, Springer-Verlag, Berlin.","DOI":"10.1007\/978-3-662-12494-9"},{"key":"atypb8","unstructured":"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 ."},{"key":"atypb9","unstructured":"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 ."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/21.279000"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/ROBOT.2004.1308892"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 1997. Computational Geometry: Algorithms and Applications, Springer, Berlin.","DOI":"10.1007\/978-3-662-03427-9"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Epstein, D.et al. 1992. Word Processing in Groups, Jones & Bartlett Publishers, Boston, MA.","DOI":"10.1201\/9781439865699"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"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 .","DOI":"10.1109\/ROBOT.1986.1087401"},{"key":"atypb16","unstructured":"Ghrist, R. and LaValle, S. M. 2005. Non-positive curvature and Pareto optimal motion planning. Conditionally accepted to SIAM Journal of Control & Optimization (https:\/\/2.zoppoz.workers.dev:443\/http\/www.math.uiuc.edu\/%7Eghrist\/preprints\/pareto.pdf)."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"atypb19","unstructured":"Hatcher, A. 2001. Algebraic Topology, Cambridge University Press, Cambridge."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"atypb21","unstructured":"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 ."},{"key":"atypb22","unstructured":"Isaacs, R. 1965. Differential Games, Wiley, New York."},{"key":"atypb23","unstructured":"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 ."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500304"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"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 .","DOI":"10.1109\/ROBOT.1994.351192"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/70.736775"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"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 .","DOI":"10.1145\/997817.997839"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"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 .","DOI":"10.1109\/IROS.1991.174483"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/S0040-9383(97)00018-9"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"O'Donnell, P. A. and Lozano-P\u00e9rez, 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 .","DOI":"10.1109\/ROBOT.1989.100033"},{"key":"atypb32","unstructured":"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 ."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1007\/BFb0070400"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1007\/978-3-540-45058-0_14"},{"key":"atypb35","unstructured":"Sawaragi, Y., Nakayama, H., and Tanino, T. 1985. Theory of Multi-objective Optimization, Academic Press, NewYork."},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"Schwartz, J. T. and Sharir, M. 1983. On the piano movers' problem: III. Coordinating the motion of several independent bodies . International Journal of Robotics Research 2(3): 97-140 .","DOI":"10.1177\/027836498300200304"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1109\/70.988973"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1109\/56.794"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0221051"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"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 .","DOI":"10.1109\/ROBOT.1995.525508"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364905059057","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364905059057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:13Z","timestamp":1777457833000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/doi\/10.1177\/0278364905059057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["10.1177\/0278364905059057"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1177\/0278364905059057","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11]]}}}