Abstract

The author discusses important class of dynamic obstacles, that is, obstacles that appear and disappear in the environment. This formulation allows modeling of a number of time-varying situations that can arise in application domains. For example, a motion can be planned in an environment where an agent rearranges the environment by picking up an object and placing it back at another location in the same environment. An algorithm is presented to generate a motion in such a dynamic domain. The algorithm runs in O(n/sup 3/ log n) time, where n is the total number of vertices in the environment.