{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:00:56Z","timestamp":1777716056020,"version":"3.51.4"},"reference-count":30,"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:\/\/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 present an algorithm for complete path planning for translating polyhedral robots in three dimensions. We compute a roadmap of the free space that captures its connectivity. The roadmap is constructed without computing an explicit representation of the free space. It encodes the complete connectivity of free space and allows us to perform exact path planning. We construct a roadmap by performing a sampling of the free space in a deterministic fashion. We obtain a set of deterministic samples by generating an adaptive volumetric grid. Our algorithm is simple to implement and uses two tests: a complex cell test and a star-shaped test during sample generation. These tests can be efficiently performed on polyhedral objects using max-norm distance computation and linear programming. We demonstrate the performance of our algorithm on environments with very small narrow passages or no collision-free paths.<\/jats:p>","DOI":"10.1177\/0278364905059061","type":"journal-article","created":{"date-parts":[[2005,11,3]],"date-time":"2005-11-03T10:29:17Z","timestamp":1131013757000},"page":"983-995","source":"Crossref","is-referenced-by-count":7,"title":["A Simple Algorithm for Complete Motion Planning of Translating Polyhedral Robots"],"prefix":"10.1177","volume":"24","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":[[2005,11,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Aronov, B. and Sharir, M. 1994. On translational motion planning in 3-space . Proceedings of the ACM Symposium on Computational Geometry, Stony Brook, NY, June 6-8, pp. 21-30 .","DOI":"10.1145\/177424.177445"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250755"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Avnaim, F., Boissonnat, J.D., and Faverjon, B. 1988. A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles . Proceedings of the 5th IEEE International Conference on Robotics and Automation, Philadelphia, PA, April 24-29, pp. 1656-1661 .","DOI":"10.1109\/ROBOT.1988.12304"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Branicky, M., Lavalle, S., Olson, K., and Yang, L. 2001. Quasi-randomized path planning . Proceedings of the IEEE International Conference on Robotics and Automation, Seoul, Korea, May 21-26, pp. 1481-1487 .","DOI":"10.1109\/ROBOT.2001.932820"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"Brooks, R. A. and Lozano-P\u00e9rez, T. 1985. A subdivision algorithm in configuration space for find path with rotation . IEEE Transactions on Systems, Man, and Cybernetics 15: 224-233 .","DOI":"10.1109\/TSMC.1985.6313352"},{"key":"atypb6","unstructured":"Canny, J. 1988.\n                      The Complexity of Robot Motion Planning\n                      , ACM Doctoral Dissertation Award, MIT Press, Cambridge, MA."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190153"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Donald, B. R. 1984. Motion planning with six degrees of freedom. Master's thesis, AI-TR-791, MIT Artificial Intelligence Laboratory, Cambridge, MA.","DOI":"10.21236\/ADA181538"},{"key":"atypb9","unstructured":"Edelsbrunner, H. 1987. Algorithms in Combinatorial Geometry, Vol. 10 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00543"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Ghosh, S. K. and Mount, D. M. 1987. An output sensitive algorithm for computing visibility graphs . Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science, Los Angeles, CA, October, pp. 11-19 .","DOI":"10.1109\/SFCS.1987.6"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Guibas, L. J. and Hershberger, J. 1985. Computing the visibility graph of n line segments in O(n2) time . Bulletin of EATCS 26: 13-20 .","DOI":"10.1016\/0020-0190(85)90044-4"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187878"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556412"},{"key":"atypb15","unstructured":"Hoffmann, C. 1989. Geometric and Solid Modeling, Morgan Kaufmann, San Mateo, CA."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Kedem, K. and Sharir, M. 1988. An automatic motion planning system for a convex polygonal mobile robot in 2-d polygonal space . Proceedings of the ACM Symposium on Computational Geometry, Urbana-Champaign, IL, June 6-8, pp. 329-340 .","DOI":"10.1145\/73393.73427"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Latombe, J. 1991. Robot Motion Planning, Kluwer Academic, Dordrecht.","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045481"},{"key":"atypb20","unstructured":"Lee, D. T. 1978. Proximity and reachability in the plane. Report R-831, Department of Electrical Engineering, University of Illinois, Urbana-Champaign, IL ."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"\u00d3'D\u00fanlaing, C., Sharir, M., and Yap, C. K. 1983. Retraction: a new approach to motion-planning . Proceedings of the 15th Annual ACM Symposium on the Theory of Computing, Boston, MA, pp. 207-220 .","DOI":"10.1145\/800061.808750"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1177\/027836499901800104"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"atypb25","unstructured":"Siek, J. G., Lee, L., and Lumsdaine, A. 2002. The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley, Boston, MA."},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"van der Stappen, A. F. and Overmars, M. H. 1994. Motion planning amidst fat obstacles . Proceedings of the ACM Symposium on Computational Geometry, Stony Brook, NY, June 6-8, pp. 31-40 .","DOI":"10.1145\/177424.177453"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"Varadhan, G., Krishnan, S., Sriram, T.V. N., and Manocha, D. 2004. Topology preserving surface extraction using adaptive subdivision . Proceedings of the Eurographics Symposium on Geometry Processing, Nice, France, July 8-10, pp. 235-244 .","DOI":"10.1145\/1057432.1057464"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"Vleugels, J. and Overmars, M. 1997. Approximating Voronoi diagrams of convex sites in any dimension . International Journal of Computational Geometry and Applications 8: 201-222 .","DOI":"10.1142\/S0218195998000114"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/99308.99325"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"Zhu, D. and Latombe, J. 1990. Constraint reformulation in a hierarchical path planner . Proceedings of the International Conference on Robotics and Automation, Cincinnati, OH, pp. 1918-1923 .","DOI":"10.1109\/ROBOT.1990.126288"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364905059061","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364905059061","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:\/\/journals.sagepub.com\/doi\/10.1177\/0278364905059061"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11]]},"references-count":30,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["10.1177\/0278364905059061"],"URL":"https:\/\/doi.org\/10.1177\/0278364905059061","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11]]}}}