Time-minimal paths among moving obstacles

Motion planning for a point robot is studied in a two-dimensional time-varying environment. The obstacle is a convex polygon that moves in a fixed direction at a constant speed. The point to be reached (referred to as the destination point) also moves along a known path. The concept of accessibility from a point to a moving object is introduced, and it is used to define a graph on a set of moving obstacles. The graph is shown to exhibit an important property, that is, if the moving point is able to move faster than any of the obstacles, a time-minimal path is given as a sequence of edges in the graph. An algorithm is described for generating a time-minimal path, and its execution time is analyzed