{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:53:19Z","timestamp":1777715599767,"version":"3.51.4"},"reference-count":49,"publisher":"SAGE Publications","issue":"11","license":[{"start":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T00:00:00Z","timestamp":1162339200000},"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,11]]},"abstract":"<jats:p>We present a new sampling-based algorithm for complete motion planning. Our algorithm relies on computing a star-shaped roadmap of the free space. We partition the free space into star-shaped regions such that a single point, called the guard, can see every point in the star-shaped region. The resulting set of guards capture the intra-region connectivity\u2014the connectivity between points belonging to the same star-shaped region. We capture the inter-region connectivity by computing connectors that link guards of adjacent regions. The guards and connectors are combined to obtain the star-shaped roadmap. We present an efficient algorithm to compute the roadmap in a deterministic manner without explicit computation of the free space. We show that the star-shaped roadmap captures the connectivity of the free space, thereby enabling us to perform complete motion planning. Our approach is relatively simple to implement. We apply our approach to perform motion planning of robots with translational and rotational degrees of freedom (dof). We highlight its performance in challenging scenarios with narrow passages or when there is no collision-free path for robots with low degrees of freedom.<\/jats:p>","DOI":"10.1177\/0278364906071199","type":"journal-article","created":{"date-parts":[[2006,10,23]],"date-time":"2006-10-23T08:41:47Z","timestamp":1161592907000},"page":"1049-1070","source":"Crossref","is-referenced-by-count":5,"title":["A Simple Algorithm for Complete Motion Planning of Translating Polyhedral Robots"],"prefix":"10.1177","volume":"25","author":[{"given":"Gokul","family":"Varadhan","sequence":"first","affiliation":[{"name":"University of North Carolina,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shankar","family":"Krishnan","sequence":"additional","affiliation":[{"name":"AT&T Research Labs,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. V.N.","family":"Sriram","sequence":"additional","affiliation":[{"name":"University of North Carolina,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"University of North Carolina,"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2006,11,1]]},"reference":[{"key":"atypb1","volume-title":"Workshop on Algorithmic Foundations of Robotics","author":"Amato, N."},{"key":"atypb2","first-page":"39","author":"Amenta, N.","year":"1998","journal-title":"ACM Symposium on Computational Geometry"},{"key":"atypb3","first-page":"21","author":"Aronov, B.","year":"1994","journal-title":"ACM Symposium on Computational Geometry"},{"key":"atypb4","first-page":"1656","volume-title":"Proceedings of 5th IEEE International Conference on Robotics and Automation","author":"Avnaim, F."},{"key":"atypb5","first-page":"19","volume-title":"Proceedings of Canadian Conference on Computational Geometry","author":"Avnaim, F."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600604"},{"key":"atypb7","first-page":"1765","volume-title":"International Conference on Robotics and Automation","author":"Basch, J."},{"key":"atypb8","first-page":"1018","volume-title":"Iinternational Conference on Robotics and Automation","author":"Boor, V."},{"key":"atypb9","volume-title":"Quasirandomized path planning","author":"Branicky, M.","year":"2001"},{"key":"atypb10","first-page":"224","volume":"15","author":"Brooks, R. A.","year":"1985","journal-title":"IEEE Transactions on Systems"},{"key":"atypb11","unstructured":"Canny, J. 1988,\n                      The Complexity of Robot Motion Planning\n                      . Series ACM                 Doctoral Dissertation Award. MIT Press."},{"key":"atypb12","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset, H.","year":"2004"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Donald, B. R. 1984. Motion planning with six degrees of freedom.                 Master\u2019s thesis, MIT Artificial Intelligence Laboratory, aI-TR-791.","DOI":"10.21236\/ADA181538"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"atypb15","first-page":"11","volume-title":"Proceedings of 28th Annual IEEE Symposium Foundations of Computer Science","author":"Ghosh, S. K."},{"key":"atypb16","first-page":"13","volume":"26","author":"Guibas, L. J.","year":"1985","journal-title":"Bulletin EATCS"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556412"},{"key":"atypb18","volume-title":"Geometric and Solid Modeling","author":"Hoffmann, C.","year":"1989"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1115\/1.1375815"},{"key":"atypb20","volume-title":"On finding narrow passages with probabilistic roadmap planners","author":"Hsu, D.","year":"1998"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"atypb22","first-page":"4420","volume-title":"International Conference on Robotics and Automation","author":"Hsu, D."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.509171"},{"key":"atypb24","first-page":"2138","volume-title":"IEEE Conference on Robotics and Automation","author":"Kavraki, L."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb26","first-page":"329","author":"Kedem, K.","year":"1988","journal-title":"ACM Symposium on Computational Geometry"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1177\/02783649922067753"},{"key":"atypb29","volume-title":"Proximity and reachability in the plane","author":"Lee, D. T.","year":"1978"},{"key":"atypb30","volume-title":"Handbook of Discrete and Computational Geometry","author":"Lin, M.","year":"2003"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"atypb33","first-page":"207","volume-title":"Proceedings of 15thAn-nual ACM Symposium on Theory of Computing","author":"\u00d3\u2019D\u00fanlaing, C."},{"key":"atypb34","series-title":"The International Series of Monographs on Computer Science","volume-title":"Art Gallery Theorems and Algorithms","author":"O\u2019Rourke, J."},{"key":"atypb35","first-page":"19","volume-title":"WAFR: Proceedings of the Workshop on Algorithmic Foundations of Robotics","author":"Overmars, M. H."},{"key":"atypb36","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Redon, S."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1177\/027836499901800104"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"atypb39","first-page":"733","volume-title":"Handbook of Discrete and Computational Geometry","author":"Sharir, M.","year":"1997"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1163\/156855300741960"},{"key":"atypb41","first-page":"121","volume-title":"Computer Graphics (SIGGRAPH \u201992 Proceedings)","author":"Snyder, J. M."},{"key":"atypb42","first-page":"31","volume-title":"ACM Symposium on Computational Geometry","author":"van der Stappen, A. F."},{"key":"atypb43","unstructured":"Varadhan, G. 2005. Accurate sampling-based algorithms for surface extraction                 and motion planning. Doctoral Dissertation, University of North Carolina at Chapel Hill."},{"key":"atypb44","author":"Varadhan, G.","year":"2004","journal-title":"Eurographics Symposium on Geometry Processing"},{"key":"atypb45","author":"Varadhan, G.","year":"2004","journal-title":"Workshop on Algorithmic Foundations of Robotics"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000114"},{"key":"atypb47","first-page":"1024","volume-title":"IEEE Conference on Robotics and Automation","author":"Wilmarth, S. A."},{"key":"atypb48","volume-title":"Fast c-obstacle query computation for motion planning","author":"Zhang, L.","year":"2005"},{"key":"atypb49","first-page":"1918","volume-title":"Proceedings of International Conference on Robotics and Automation","author":"Zhu, D."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906071199","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906071199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:37Z","timestamp":1777457737000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364906071199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11]]},"references-count":49,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2006,11]]}},"alternative-id":["10.1177\/0278364906071199"],"URL":"https:\/\/doi.org\/10.1177\/0278364906071199","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,11]]}}}