Stanford Robotics

Research on Elastic Motion Planning

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.

These planning methods usually do not accommodate for cases when an unforeseen obstacle appears or a known obstacle deviates from its initial trajectory.  As the initially planned motion becomes invalid, one solution is to plan the new motion from scratch.  However this is impractical for a space whose configurations change frequently.  An alternative is to use an execution based method that performs an on-the-fly adjustment considering local information only.  Though this method might fail to achieve a desired result due to its shortsightedness, it is often the only efficient method for generating complex local behaviors such as walking pattern of a humanoid robot or obstacle avoidance in high-dimensional dynamic environments.

Elastic Strip Framework

The Elastic Strip Framework provides an efficient method for performing local adjustments to a plan in dynamic environments while respecting original goals of the plan.  The approach combines advantages of planning and execution based methods.  The initial trajectory is computed by a global motion planner.  For obstacle avoidance the costly search in high-dimensional configuration space is replaced with a directed exploration in the neighborhood of the planned trajectory.  To modify a motion in reaction to changes in the environment, real-time obstacle avoidance is combined with desired posture behavior.  The modification of motion is performed in a task-consistent manner, leaving task execution unaffected by obstacle avoidance and posture behavior.  See references for more information.

 

Extensions to Contact

The Elastic Strip is a powerful tool for real-time motion generation and motion execution in free space.  To fully complete the set of possible motions however, the framework must allow the robot to come into contact with the environment, and our goal is to revise the work to accommodate for the contact.  Note that in n-dimensional configuration space, the obstacle boundaries to be traced still form an (n-1)-dimensional subspace, and with the transitions between contact and free space the dimensionality of the problem increases and poses many challenges.  First, the initial plan must provide a convenient encoding of motion intensions in both free space and contact space.  Notions such as desirable proximity and contacts must be easily extractable from the plan and incorporated into the framework.  A new local modification scheme is needed and the final model must be able to cope with the uncertainty and imprecision inherent to real robots and environments they live in.  This is a topic of ongoing research.