{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:53:50Z","timestamp":1777715630404,"version":"3.51.4"},"reference-count":24,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"tdm","delay-in-days":0,"URL":"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":[[2006,3]]},"abstract":"<jats:p>In this paper we consider a motion planning problem that occurs in tasks such as spot welding, car painting, inspection, and measurement, where the end-effector of a robotic arm must reach successive goal placements given as inputs. The problem is to compute a nearoptimal path of the arm so that the end-effector visits each goal once. It combines two notoriously hard subproblems: the collisionfree shortest-path and the traveling-salesman problems. It is further complicated by the fact that each goal placement of the end-effector may be achieved by several configurations of the arm (distinct solutions of the arm's inverse kinematics). This leads to considering a set of goal configurations of the robot that are partitioned into groups. The planner must compute a robot path that visits one configuration in each group and is near optimal over all configurations in every goal group and over all group orderings. The algorithm described in this paper operates under the assumption that finding a good tour in a graph with edges of given costs takes much less time than computing good paths between all pairs of goal configurations from different groups. So, the algorithm balances the time spent in computing paths between goal configurations and the time spent in computing tours. Although the algorithm still computes a quadratic number of such paths in the worst case, experimental results show that it is much faster in practice.<\/jats:p>","DOI":"10.1177\/0278364906061705","type":"journal-article","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:42:43Z","timestamp":1141116163000},"page":"207-223","source":"Crossref","is-referenced-by-count":74,"title":["Planning Tours of Robotic Arms among Partitioned Goals"],"prefix":"10.1177","volume":"25","author":[{"given":"Mitul","family":"Saha","sequence":"first","affiliation":[{"name":"Computer Science Department Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Computer Science Department Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gildardo","family":"S\u00e1nchez-Ante","sequence":"additional","affiliation":[{"name":"Computer Science Department National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2006,3,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Akinc, M., Bekris, K. E., Chen, B. Y., Ladd, A. M., Plaku, E., and Kavraki, L. E. 2005. Probabilistic roadmaps of trees for parallel computation of multiple query roadmaps. Robotics Research, P. Dario and R. Chatila, editors, Springer, Berlin. pp. 80\u201389.","DOI":"10.1007\/11008941_9"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/56.811"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Bonert, M., Shu, L. H., and Benhabib, B. 1999. Motion planning for multirobot assembly systems . Proceedings of the ASME Design Engineering Technical Conferences, LasVegas, NV, September.","DOI":"10.1115\/DETC99\/DAC-8649"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Canny, J. F. and Reif, J. 1987. New lower bound techniques for robot motion planning problems . Proceedings of the 28th IEEE Conference on the Foundations of Computer Science, Los Angeles, pp. 39\u201348 .","DOI":"10.1109\/SFCS.1987.42"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1177\/027836499801700804"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.07.010"},{"key":"atypb7","unstructured":"Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms, MIT Press, Cambridge, MA ."},{"key":"atypb8","unstructured":"Danner, T. and Kavraki, L. E. 2000. Randomized planning for short inspection paths . Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, April 24\u201328."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., and Talwar, K. 2003. A tight bound on approximating arbitrary metrics by tree metrics . Proceedings of the ACM Symposium on Theory of Computing, San Diego, CA, June 9\u201311, pp. 448\u2013455 .","DOI":"10.1145\/780542.780608"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"atypb13","unstructured":"Gonzalez-Ba\u00f1os, H. H. and Latombe, J.C. 2000. A randomized art-gallery algorithm for sensor placement . Proceedingsof the ACM Symposium on Computational Geometry, Hong Kong University of Science and Technology, Hong Kong, June 12\u201314, pp. 232\u2013240 ."},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Halperin, E. and Krauthgamer, R. 2003. Polylogarithmic inapproximability . Proceedings of the ACM Symposium on Theory of Computing, San Diego, CA, pp. 585\u2013594 .","DOI":"10.1145\/780542.780628"},{"key":"atypb15","unstructured":"Hsu, D. 2000.\n                      Randomized Single-Query Motion Planning in Expansive Space\n                      . Ph.D. Thesis, Computer Science Department, Stanford University, Stanford, CA, May."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Hsu, D., Latombe, J.C., and Motwani, R. 1997. Path planning in expansive configuration spaces . Proceedings of the IEEE International Conference on Robotics and Automation, Albuquerque, NM, pp. 2719\u20132726 .","DOI":"10.1109\/ROBOT.1997.619371"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb18","unstructured":"Mitchell, J. S. B. 1997. Shortest paths and networks. Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, editors, CRCPress, Boca Raton, FL , pp. 445\u2013466."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Reich, G. and Widmayer, P. 1990. Beyond Steiner's problem: a VLSI oriented generalization. Proceedings of Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science Vol. 411, Springer-Verlag, Berlin, pp. 196\u2013210.","DOI":"10.1007\/3-540-52292-1_14"},{"key":"atypb21","unstructured":"Saha, M., S\u00e1nchez, G., and Latombe, J.C. 2003. Planning multigoal tours for robot arms . Proceedings of the IEEE International Conference on Robotics and Automation, Taipei, Taiwan, September 14\u201319."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556458"},{"key":"atypb23","unstructured":"Spitz, S. N. and Requicha, A. A. G. 2000. Multiple goals path planning for coordinate measuring machines . Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, April 24\u201328."},{"key":"atypb24","unstructured":"Wurll, C., Henrich, D., and W\u00f6rn, H. 1999. Multigoal path planning for industrial robots . Proceedings of the IEEE International Conference on Robotics and Applications, Santa Barbara, CA."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906061705","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906061705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:44Z","timestamp":1777457744000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364906061705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1177\/0278364906061705"],"URL":"https:\/\/doi.org\/10.1177\/0278364906061705","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]}}}