{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T03:29:55Z","timestamp":1767842995361,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Auton Robot"],"published-print":{"date-parts":[[2005,12]]},"DOI":"10.1007\/s10514-005-4748-1","type":"journal-article","created":{"date-parts":[[2006,1,9]],"date-time":"2006-01-09T10:12:14Z","timestamp":1136801534000},"page":"301-319","source":"Crossref","is-referenced-by-count":35,"title":["Finding Narrow Passages with Probabilistic Roadmaps: The Small-Step Retraction Method"],"prefix":"10.1007","volume":"19","author":[{"given":"Mitul","family":"Saha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Chi","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedrich","family":"Prinz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4748_CR1","first-page":"19","volume-title":"Proc 11th Int. Symp. on Robotics Research","author":"M. Akinc","year":"2003","unstructured":"Akinc, M., Bekris, K.E., Chen, B.Y., Ladd, A.M., Plaku, E., and Kavraki, L.E. 2003. Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps. In Proc 11th Int. Symp. on Robotics Research, Siena, Italy, pp. 19\u201322."},{"key":"4748_CR2","first-page":"155","volume-title":"Robotics: The Algorithmic Perspective","author":"N.M. Amato","year":"1998","unstructured":"Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C., and Vallejo, D. 1998. OBPRM: An obstacle-based PRM for 3D workspace. In P.K. Agarwal et al. (eds.), Robotics: The Algorithmic Perspective, A K Peters, Natick, MA, pp. 155\u2013168."},{"key":"4748_CR3","doi-asserted-by":"crossref","unstructured":"Amenta, N., Choi, S., and Kolluri, R. 2001. The power crust. In Proc. 6th ACM Symp. on Solid Modeling and Applications, pp. 249\u2013260.","DOI":"10.1145\/376957.376986"},{"issue":"4","key":"4748_CR4","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/70.781970","volume":"15","author":"J.M. Ahuactzin","year":"1999","unstructured":"Ahuactzin, J.M. and Gupta, K.K. 1999. The kinematic roadmap: A Motion Planning Based Global Approach for Inverse Kinematics of Redundant Robots. IEEE Tr. on Robotics and Automation, 15(4):653\u2013669.","journal-title":"IEEE Tr. on Robotics and Automation"},{"key":"4748_CR5","doi-asserted-by":"crossref","unstructured":"Amato, N.M. and Wu, Y. 1996. A Randomized Roadmap Method for Path and Manipulation Planning. In Proc. IEEE Int. Conf. on Robotics and Automation, Minneapolis, MN, pp. 113\u2013120.","DOI":"10.1109\/ROBOT.1996.503582"},{"key":"4748_CR6","unstructured":"Baginski, B. 1997. Local Motion Planning for Manipulators Based on Shrinking and Growing Geometry Models. In Proc. IEEE Int. Conf. on Robotics and Automation, Minneapolis, MN, pp. 3303\u20133308."},{"key":"4748_CR7","doi-asserted-by":"crossref","unstructured":"Bohlin, R. and Kavraki, L.E. 2000. Path planning using lazy PRM. In Proc. IEEE Int. Conf. Robotics and Automation, San Francisco, CA.","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"4748_CR8","first-page":"19","volume-title":"11th Int. Symp. on Robotics Research","author":"T. Bretl","year":"2003","unstructured":"Bretl, T., Latombe, J.C., and Rock, S. 2003. Toward Autonomous Free-Climbing Robots. In 11th Int. Symp. on Robotics Research, Siena, Italy, pp. 19\u201322."},{"key":"4748_CR9","first-page":"326","volume-title":"Models for the Perception of Speech and Visual Form","author":"H. Blum","year":"1967","unstructured":"Blum, H. 1967. A Transformation for Extracting New Descriptors of Shape. In W. Wathen-Dunn (ed.), Models for the Perception of Speech and Visual Form, MIT Press, Cambridge, MA, pp. 326\u2013380."},{"key":"4748_CR10","doi-asserted-by":"crossref","unstructured":"Boor, V., Overmars, M.H., and van der Strappen, A.F. 1999. The Gaussian Sampling Strategy for Probabilistic Roadmap Planners. In Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI. pp. 1018\u20131023.","DOI":"10.1109\/ROBOT.1999.772447"},{"key":"4748_CR11","unstructured":"Cohen, J., Lin, M., Manocha, D., and Ponamgi, M. 1995. I-Collide: An Interactive and Exact Collision Detection System for Large Scale Environments. In Proc. ACM Interactive 3D Graphics Conf., pp. 189\u2013196."},{"key":"4748_CR12","unstructured":"Chang, Y.C., Pinilla, J.M., Ramaswami, K., and Prinz, F. 2004. Near parallel computation of MAT of 3D polyhedra. In preparation."},{"key":"4748_CR13","doi-asserted-by":"crossref","unstructured":"Cort\u00e9s, J., Sim\u00e9on, T., and Laumond, J.P. 2002. A Random Loop Generator for Planning the Motions of Closed Kinematic Chains Using PRM methods. In Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2141\u20132146.","DOI":"10.1109\/ROBOT.2002.1014856"},{"key":"4748_CR14","doi-asserted-by":"crossref","unstructured":"Danner, T. and Kavraki, L.E. 2000. Randomized Planning for Short Inspection Paths. In Proc. IEEE Int. Conf. on Robotics and Automation, San Fransisco, CA, pp. 971\u2013976.","DOI":"10.1109\/ROBOT.2000.844726"},{"key":"4748_CR15","doi-asserted-by":"crossref","unstructured":"Dey, T.K. and Zhao, W. 2002. Approximate medial axis as a voronoi subcomplex. In Proc. 7th ACM Symp. on Solid Modeling and Applications, pp. 356\u2013366.","DOI":"10.1145\/566282.566333"},{"key":"4748_CR16","doi-asserted-by":"crossref","unstructured":"Foskey, M., Lin, M., and Manocha, D. 2003. Efficient computation of a simplified medial axis. In Proc. ACM Symposium on Solid Modeling and Applications.","DOI":"10.1145\/781606.781623"},{"key":"4748_CR17","doi-asserted-by":"crossref","unstructured":"Guibas, L., Holleman, C., and Kavraki, L. 1999. A Probabilistic Roadmap Planner for Flexible Objects with a Workspace Medial-Axis Based Sampling Approach. In Proc. IEEE Int. Conf. on Intelligent Robots and Systems.","DOI":"10.1109\/IROS.1999.813013"},{"key":"4748_CR18","unstructured":"Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. In Proc. ACM SIGGRAPH'96, pp. 171\u2013180."},{"key":"4748_CR19","first-page":"233","volume-title":"Algorithmic and Computational Robotics: New Directions","author":"L. Han","year":"2001","unstructured":"Han, L. and Amato, N.M. 2001. A Kinematics-Based Probabilistic Roadmap Method for Closed Chain Systems. In B.R. Donald, K.M. Lynch, and D. Rus (eds.), Algorithmic and Computational Robotics: New Directions, A K Peters, Natick, MA, pp. 233\u2013246."},{"key":"4748_CR20","doi-asserted-by":"crossref","unstructured":"Hoff, K., Culver, T., Keyser, J., Lin, M., and Manocha, D. 1999. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. In Proc. SIGGRAPH '99, pp. 277\u2013286.","DOI":"10.1145\/311535.311567"},{"key":"4748_CR21","doi-asserted-by":"crossref","unstructured":"Hoff III, K.E., Culver, T., Keyser, J., Lin, M., and Manocha, D. 2000. Interactive Motion Planning Using Hardware-Accelerated Computation of Generalized Voronoi Diagrams. In Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA.","DOI":"10.1109\/ROBOT.2000.846473"},{"key":"4748_CR22","doi-asserted-by":"crossref","unstructured":"Hsu, D., Jiang, T., Reif, J., and Sun, Z. 2003. The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners. In Proc. IEEE Int. Conf. on Robotics and Automation, pp. 4420\u20134426.","DOI":"10.1109\/ROBOT.2003.1242285"},{"key":"4748_CR23","doi-asserted-by":"crossref","unstructured":"Holleman, C. and Kavraki, L. 2000. A Framework for Using the Workspace Medial Axis in PRM planners. In Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA, pp. 1408\u20131413.","DOI":"10.1109\/ROBOT.2000.844795"},{"key":"4748_CR24","first-page":"151","volume-title":"Robotics: The Algorithmic Perspective","author":"D. Hsu","year":"1998","unstructured":"Hsu, D., Kavraki, L., Latombe, J.C., Motwani, R., and Sorkin, S. 1998. On Finding Narrow Passages with Probabilistic Roadmap Planners. In P.K. Agarwal et al. (eds.), Robotics: The Algorithmic Perspective, A K Peters, Natick, MA, pp. 151\u2013153."},{"issue":"3","key":"4748_CR25","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1177\/027836402320556421","volume":"21","author":"D. Hsu","year":"2002","unstructured":"Hsu, D., Kindel, R., Latombe, J.C., and Rock, S. 2002. Randomized Kinodynamic Motion Planning with Moving Obstacles. Int. J. of Robotics Research, 21(3):233-255.","journal-title":"Int. J. of Robotics Research"},{"issue":"4\/5","key":"4748_CR26","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1142\/S0218195999000285","volume":"9","author":"D. Hsu","year":"1999","unstructured":"Hsu, D., Latombe, J.C., and Motwani, R. 1999. Path Planning in Expansive Configuration Spaces. Int. J. of Computational Geometry and Applications, 9(4\/5):495\u2013512.","journal-title":"Int. J. of Computational Geometry and Applications"},{"key":"4748_CR27","unstructured":"Hoffman, C. 1994. How to construct the skeleton of CSG Objects. In A. Bowyer (ed.), Computer-Aided Surface Geometry and Design, Oxford University Press, pp. 421\u2013437."},{"key":"4748_CR28","doi-asserted-by":"crossref","unstructured":"Isto, P. 2002. Constructing Probabilistic Roadmaps with Powerful Local Planning and Path Optimization. In Proc. IEEE\/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 2323\u20132328.","DOI":"10.1109\/IRDS.2002.1041614"},{"key":"4748_CR29","doi-asserted-by":"crossref","unstructured":"Ji, X. and Xiao, J. 2001. Planning Motion Compliant to Complex Contact States. In Proc. 2001 IEEE Int. Conf. on Robotics and Automation, Seoul, Korea.","DOI":"10.1177\/02783640122067480"},{"issue":"1","key":"4748_CR30","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1109\/70.660866","volume":"14","author":"L.E. Kavraki","year":"1998","unstructured":"Kavraki, L.E., Kolountzakis, M., and Latombe, J.C. 1998. Analysis of Probabilistic Roadmaps for Path Planning. IEEE Tr. on Robotics and Automation, 14(1):166\u2013171.","journal-title":"IEEE Tr. on Robotics and Automation"},{"issue":"1","key":"4748_CR31","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1006\/jcss.1998.1578","volume":"57","author":"L.E. Kavraki","year":"1998","unstructured":"Kavraki, L.E., Latombe, J.C., Motwani, R., and Raghavan, P. 1998. Randomized Query Processing in Robot Motion Planning. Journal of Computer and System Sciences, 57(1):50\u201360.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"4748_CR32","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"L.E. Kavraki","year":"1996","unstructured":"Kavraki, L.E., Svestka, P., Latombe, J.C., and Overmars, M.H. 1996. Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces. IEEE Tr. on Robotics and Automation, 12(4):566\u2013580.","journal-title":"IEEE Tr. on Robotics and Automation"},{"issue":"5","key":"4748_CR33","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1177\/02783640122067453","volume":"20","author":"S.M. LaValle","year":"2001","unstructured":"LaValle, S.M. and Kuffner, J.J. 2001. Randomized kinodynamic planning. Int. J. of Robotics Research, 20(5):278\u2013300.","journal-title":"Int. J. of Robotics Research"},{"key":"4748_CR34","unstructured":"Lin, M. and Manocha, D. 2004. Collision and proximity queries. In J.E. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, Chapman&Hall\/CRC, 2nd edition, Chapter 35, pp. 787\u2013807."},{"key":"4748_CR35","unstructured":"Lien, J.M., Thomas, S.L., and Amato, N.M. 2003. A General Framework for Sampling on the Medial Axis of the Free Space. In Proc. IEEE Int. Conf. on Robotics and Automation."},{"key":"4748_CR36","doi-asserted-by":"crossref","unstructured":"LaValle, S.M., Yakey, J., and Kavraki, L. 1999. A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains. In Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI, pp. 151\u2013156.","DOI":"10.1109\/ROBOT.1999.770349"},{"key":"4748_CR37","doi-asserted-by":"crossref","unstructured":"Quinlan, S. 1994. Efficient Distance Computation Between Non-Convex Objects. In Proc. IEEE Int. Conf. On Robotics and Automation, pp. 3324\u20133329.","DOI":"10.1109\/ROBOT.1994.351059"},{"key":"4748_CR38","doi-asserted-by":"crossref","unstructured":"S\u00e1nchez-Ante, G. and Latombe, J.C. 2002. A single-query bi-directional probabilistic roadmap planner with lazy collision checking. Int. J. of Robotics Research.","DOI":"10.1007\/3-540-36460-9_27"},{"key":"4748_CR39","doi-asserted-by":"crossref","unstructured":"Wilmarth, S.A., Amato, N.M., and Stiller, P.F. 1999. MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space. Proc. IEEE Int. Conf. on Robotics and Automation Detroit, MI, pp. 1024\u20131031.","DOI":"10.1109\/ROBOT.1999.772448"}],"container-title":["Autonomous Robots"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-005-4748-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10514-005-4748-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-005-4748-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,12]],"date-time":"2020-04-12T00:40:07Z","timestamp":1586652007000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10514-005-4748-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,12]]}},"alternative-id":["4748"],"URL":"https:\/\/doi.org\/10.1007\/s10514-005-4748-1","relation":{},"ISSN":["0929-5593","1573-7527"],"issn-type":[{"value":"0929-5593","type":"print"},{"value":"1573-7527","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}