Answers are grounded in this paper and cite their sources.
Inspired by an idea of Rimon and Koditschek (1992), we develop a motion planning algorithm for a point robot traveling among moving obstacles in an N-dimensional space. The navigating point must meet a goal point at a fixed time T, while avoiding several translating, nonrotating, nonintersecting obstacles on its way. All obstacles, the goal point, and the navigating point are confined to the interior of a star-shaped set in R/sup N/ over the time interval [0, T]. Full a priori knowledge of the goal's location and of the obstacle's trajectories is assumed. We observe that the topology of the obstacle-free space is invariant in the time interval [0, T] as long as the obstacles are nonintersecting and as long as they do not cover the goal point at any time during [0, T]. Using this fact we reduce the problem, for any fixed time t/sub 0//spl isin/[0, T], to a stationary-obstacle problem, which is then solved using the method of Rimon and Koditschek. The fact that the obstacle-free space is topologically invariant allows a solution to the moving-obstacle problem over [0, T] through a continuous deformation of the stationary-obstacle solution obtained at time t/sub 0/. We construct a vector field whose flow is in fact one such deformation. We believe that ours is the first global solution to the moving-obstacle path-planning problem which uses vector fields.
No takes yet. Share an insight, caveat, or question.
Conn et al. (1998) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: