Time-minimal Paths amidst Moving Obstacles in Three Dimensions

Time-minimal Paths amidst Moving Obstacles in Three Dimensions

Journal Article


A path-planning problem is considered in the presence of moving polygonal obstacles in three dimensions. A particle is to be moved from a given initial position to a destination position amidst polygonal disjoint barriers moving along known linear trajectories. The particle can move in any direction in space with a single constraint that it cannot move faster than a given speed bound. All obstacles are slowly moving, i.e., their speeds are strictly slower than the maximum speed of the particle. The destination point is also permitted to move along a known trajectory and is assumed to be collision-free at all times. Three properties are stated and proved for a time-minimal path amidst moving polygonal barriers. A few extensions are considered, including piecewise linear motions of the obstacles.


Theoretical Computer Science 270, Vol 1-2, 421-440
01 tammikuuta 2002
K. Fujimura