Most motion planning algorithms assume complete knowledge of the geometry of environment.  Typically obstacles in the environment are assumed to be static or their motion is known as a function of time.  To generate a motion, the algorithm performs a search in the configuration space of the robot, C..  Such a space encapsulates all legal, C_free , and illegal, C_obs, configurations of the robot and the goal is to find a continuous path in C_free connecting initial and final configurations.  For robots with multiple degrees of freedom, the configuration space is extremely high-dimensional.  To allow planning for environments with moving obstacles the configuration space must be further augmented by the dimension of time.  Performing a search in such high-dimensional spaces is infeasible and people have in the past resorted to probabilistic and randomized approaches that confine the search space to a subset of all possible configurations. Continue reading →