MINIMUM-SPEED MOTIONS

We consider the problem of determining how fast an object must be capable of moving for it to be able to reach a given position at a given time while avoiding moving obstacles. The problem is to plan velocity profile along a given path so that collisions with moving obstacles crossing the path are avoided and the maximum velocity along the path is minimized. Suppose the time-varying environment is fully specified, both in space and in time, by n linear constraints. An algorithm is presented that, given a full description of the environment and the initial configuration of the system (that is, initial position and starting time of the object), answers in O(log n) time queries of the form: "What is the lowest speed limit that the object can obey while still being able to reach the query configuration from the initial configuration without colliding with the obstacles?" The algorithm can also be used to compute a motion from the initial configuration to the query configuration that obeys the speed limit in O(n) time. The algorithm requires O(n log n) preprocessing time and O (n) space.