PLANNING A TIME-MINIMAL MOTION AMONG MOVING OBSTACLES

Motion planning for a point robot is studied in a time-varying environ ment. Each obstacle is a convex polygon that moves in a fixed directio n at a constant speed. The point to be reached (referred to as the des tination point) also moves along a known trajectory. The concept of '' accessibility'' from a point to a moving object is introduced, and is used to define a graph on a set of moving obstacles. If the point robo t is able to move faster than any of the obstacles, then the graph exh ibits an important property: a time-minimal motion is given as a seque nce of edges in the graph. An algorithm is described for generating a time-minimal motion and its execution time is analyzed.