{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:53:03Z","timestamp":1784202783231,"version":"3.55.0"},"reference-count":67,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2002,3,1]],"date-time":"2002-03-01T00:00:00Z","timestamp":1014940800000},"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":[[2002,3]]},"abstract":"<jats:p>This paper presents a novel randomized motion planner for robots that must achieve a specified goal under kinematic and\/or dynamic motion constraints while avoiding collision with moving obstacles with known trajectories. The planner encodes the motion constraints on the robot with a control system and samples the robot's state \u00d7 time space by picking control inputs at random and integrating its equations of motion. The result is a probabilistic roadmap of sampled state \u00d7 time points, called milestones, connected by short admissible trajectories. The planner does not precompute the roadmap; instead, for each planning query, it generates a new roadmap to connect an initial and a goal state\u00d7 time point. The paper presents a detailed analysis of the planner's convergence rate. It shows that, if the state\u00d7 time space satisfies a geometric property called expansiveness, then a slightly idealized version of our implemented planner is guaranteed to find a trajectory when one exists, with probability quickly converging to 1, as the number of milestones increases. Our planner was tested extensively not only in simulated environments, but also on a real robot. In the latter case, a vision module estimates obstacle motions just before planning starts. The planner is then allocated a small, fixed amount of time to compute a trajectory. If a change in the expected motion of the obstacles is detected while the robot executes the planned trajectory, the planner recomputes a trajectory on the fly. Experiments on the real robot led to several extensions of the planner in order to deal with time delays and uncertainties that are inherent to an integrated robotic system interacting with the physical world.<\/jats:p>","DOI":"10.1177\/027836402320556421","type":"journal-article","created":{"date-parts":[[2003,7,19]],"date-time":"2003-07-19T01:53:44Z","timestamp":1058579624000},"page":"233-255","source":"Crossref","is-referenced-by-count":527,"title":["Randomized Kinodynamic Motion Planning with Moving Obstacles"],"prefix":"10.1177","volume":"21","author":[{"given":"David","family":"Hsu","sequence":"first","affiliation":[{"name":"Department of Computer Science Stanford University Stanford, CA 94305, U.S.A.,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Kindel","sequence":"additional","affiliation":[{"name":"Department of Aeronautics & Astronautics Stanford University Stanford, CA 94305, U.S.A.,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Department of Computer Science Stanford University Stanford, CA 94305, U.S.A.,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Rock","sequence":"additional","affiliation":[{"name":"Department of Aeronautics & Astronautics Stanford University Stanford, CA 94305, U.S.A.,"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2002,3,1]]},"reference":[{"key":"atypb1","unstructured":"Agawal, P.K. 1997. Range searching. In Handbook of discrete and computational geometry, eds. J.E. Goodman and J. O'Rourke, 575-598. Boca Raton, FL: CRC Press."},{"key":"atypb2","volume-title":"Le Fil d'Ariane. Une m\u00e9thode de planification g\u00e9n\u00e9rale. Application \u00e0 la planfification des trajectoires","author":"Ahuactzin, J.M.","year":"1994"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/70.781970"},{"key":"atypb4","unstructured":"Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C., and Vallejo, D. 1998. OBPRM: An obstacle-based PRM for 3D workspaces . In Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics, eds. P.K. Agarwal et al. 155-168. Wellesley, MA: A. K. Peters."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600604"},{"issue":"2","key":"atypb6","first-page":"77","volume":"3","author":"Barraquand, J.","year":"1989","journal-title":"Revue d'Intelligence Artificielle"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1177\/027836499101000604"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891837"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1177\/027836498500400301"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.772447"},{"key":"atypb12","unstructured":"Chang, H., and Li, T.Y. 1995. Assembly maintainability study with motion planning . In Proc. IEEE Int. Conf. on Robotics and Automation, pp. 1012-1019."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199437"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4563(199910)16:10<557::AID-ROB3>3.0.CO;2-H"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90069-5"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/174147.174150"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840371"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/70.660867"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.506925"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Fraichard, T. 1993. Dynamic trajectory planning with dynamic constraints: A \"state-time space\" approach. In Proc. IEEE\/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 1394-1400.","DOI":"10.1109\/IROS.1993.583794"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/70.388776"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. In SIGGRAPH 96 Conference Proceedings, pp. 171-180.","DOI":"10.1145\/237170.237244"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1977.1101601"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1994.351060"},{"key":"atypb25","volume-title":"Randomized Single-query Motion Planning in Expansive Spaces","author":"Hsu, D.","year":"2000"},{"key":"atypb26","unstructured":"Hsu, D., Kavraki, L., Latombe, J.C., Motwani, R., and Sorkin, S. 1998. On finding narrow passages with probabilistic roadmap planners. In Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics, eds. P. K. Agarwal et al. 141-154. Wellesley, MA: A. K. Peters."},{"key":"atypb27","unstructured":"Hsu, D., Kindel, R., Latombe, J.C., and Rock, S. 2000. Randomized kinodynamic motion planning with moving obstacles . In Algorithmic and Computational Robotics: New Directions: The Fourth International Workshop on the Algorithmic Foundations of Robotics , eds. B.R. Donald et al. 247-264. Wellesley, MA: A. K. Peters."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1997.619371"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-3282-4_8"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/231731.231732"},{"key":"atypb32","unstructured":"Hwang, Y.K., Xavier, P.G., Chen, P.C., and Watterberg, P.A. 1998. Motion planning with SANDROS and the configuration space toolkit. In Practical Motion Planning in Robotics, eds. K. K. Gupta and A. P. del Pobil, 55-77. John Wiley & Sons."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1002\/9783527617395"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500304"},{"key":"atypb35","volume-title":"Random Networks in Configuration Space for Fast Path Planning","author":"Kavraki, L.E.","year":"1994"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225159"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb39","volume-title":"Motion Planning for Free-Flying Robots in Dynamic and Uncertain Environments. PhD thesis, Dept. of Aeronautics & Astronautics","author":"Kindel, R.","year":"2001"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844109"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/2945.675649"},{"key":"atypb42","unstructured":"Krishnan, S., Pattekar, A., Lin, M., and Manocha, D. 1998. Spherical shell: A higher order bounding volume for fast proximity queries. In Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics, pp. 177-190."},{"key":"atypb43","volume-title":"Autonomous Agents for Real-Time Animation","author":"Kuffner, J.J.","year":"1999"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.509170"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1177\/02783649922067753"},{"key":"atypb46","unstructured":"Laumond, J.P. 1986. Feasible trajectories for mobile robots with kinematic and environmental constraints. In Proc. Int. Conf. on Intelligent Autonomous Systems, pp. 346-354."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1109\/70.326564"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"La Valle, S.M., and Kuffner, J.J. 1999. Randomized kinodynamic planning. In Proc. IEEE Int. Conf. on Robotics and Automation, pp. 473-479.","DOI":"10.1109\/ROBOT.1999.770022"},{"issue":"5","key":"atypb49","first-page":"278","volume":"20","author":"La Valle, S.M.","year":"2001","journal-title":"International Journal of Robotics Research"},{"key":"atypb50","unstructured":"Leven, P., and Hutchinson, S. 2000. Toward real-time path planning in changing environments . In Algorithmic and Computational Robotics: New Directions: The Fourth International Workshop on the Algorithmic Foundations of Robotics , eds. B.R. Donald et al. 363-376. Wellesley, MA: A. K. Peters."},{"key":"atypb51","unstructured":"Li, Z., Canny, J.F., and Heinzinger, G. 1989. Robot motion planning with nonholonomic constraints . In Robotics Research: The Fifth International Symposium, eds. H. Miura et al. 309-316. Cambridge, MA : MIT Press."},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1177\/027836499601500602"},{"key":"atypb53","unstructured":"O'Rourke, J. 1997. Visibility. In Handbook of discrete and computational geometry, eds. J.E. Goodman and J. O'Rourke, 467-479. Boca Raton, FL: CRC Press."},{"key":"atypb54","volume-title":"Numerical Recipes in C","author":"Press, W.H.","year":"1992","edition":"2"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1994.351059"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1990.145.367"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"Reif, J.H. 1979. Complexity of the mover's problem and generalizations . In Proc. IEEE Symposium on Foundations of Computer Science , pp. 421-427.","DOI":"10.1109\/SFCS.1979.10"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.36"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556458"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1109\/70.720344"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1109\/70.105387"},{"key":"atypb62","volume-title":"Move3D: A generic platform for motion planning","author":"Sim\u00e9on, T.","year":"2001"},{"key":"atypb63","volume-title":"Customizing PRMroadmaps at query time","author":"Song, G.","year":"2001"},{"key":"atypb64","volume-title":"Robot Motion Planning Using Probabilistic Roadmaps","author":"\u0160vestka, P.","year":"1997"},{"key":"atypb65","volume-title":"Motion planning for car-like robots using a probabilistic learning approach","author":"\u0160vestka, P.","year":"1994"},{"key":"atypb66","first-page":"225","volume":"229","author":"\u0160vestka, P.","year":"1998","journal-title":"In Lecture Notes in Control and Information Sciences"},{"key":"atypb67","unstructured":"Sekhavat, S. \u0160vestka, P., Laumond, J.P., and Overmars, M.H. 1997. Multi-level path planning for nonholonomic robots using semi-holonomic subsystems. In Algorithms for Robotic Motion and Manipulation: 1996 Workshop on the Algorithmic Foundations of Robotics , eds. J.P. Laumond et al. 79-96. Wellesley, MA: A. K. Peters."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836402320556421","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836402320556421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:44Z","timestamp":1777457804000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836402320556421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,3]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2002,3]]}},"alternative-id":["10.1177\/027836402320556421"],"URL":"https:\/\/doi.org\/10.1177\/027836402320556421","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,3]]}}}