Bio-Robotics : Elastic Strip Framework

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, Cfree , and illegal, Cobs, configurations of the robot and the goal is to find a continuous path in Cfree 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. 

Elastic Strips: A Framework for Motion Generation in Human Environments”
Brock, O, Khatib, O.
International Journal of Robotics Research, Vol. 21 No. 12, Dec 2002, pp. 1031-1052

“Task-Consistent Obstacle Avoidance and Motion Behavior for Mobile Manipulation”
Brock, O., Khatib, O, Viji, S.
Proc. IEEE International Conference on Robotics and Automation 2002, Washingtion, USA, 11-15 May 2002 Page(s):388 – 393 vol.1

“Task-Consistent Obstacle Avoidance and Motion Behavior for Mobile Manipulation”
Oliver Brock, Oussama Khatib, Sriram Viji
Submitted to IEEE International Conference on Robotics and Automation 2002

“Integrated Planning and Execution: Elastic Strips”
Brock, O, Khatib, O.
Proc. The World Automation Congress, Maui, USA, 2000.

“Real-Time Replanning in High-Dimensional Configuration Spaces Using Sets of Homotopic Paths”
Oliver Brock, Oussama Khatib
Proceedings of the 2000 IEEE International Conference on Robotics and Automation

“Task-Consistent Obstacle Avoidance for Mobile Manipulation”
Oliver Brock, Oussama Khatib, Sriram Viji
Submitted to Video Proceedings of the 2000 International Conference on Robotics and Automation

“Generation of Robot Motion: Integrating Planning and Execution”
Oliver Brock
Ph.D. Thesis. Stanford University. November 1999

“Real-Time Obstacle Avoidance and Motion Coordination in a Multi-Robot Workcell”
Oliver Brock, Oussama Khatib
Proceedings of the 1999 International Symposium on Assembly and Task Planning. July 1999

“Real-Time Obstacle Avoidance and Motion Coordination in a Multi-Robot Workcell”
Brock, O, Khatib, O.
Proc. International Symposium on Assembly and Task Planning, Porto, Portugal, July 1999. Page(s):274 – 279

“Robots in Human Environments: Basic Autonomous Capabilities”
Khatib Oussama, Kazu Yokoi, Oliver Brock, Kyong-Sok Chang, Arancha Casal
International Journal of Robotics Research. July 1999. vol.18, no.7, p. 684-696.

“Robots in Human Environments”
Khatib Oussama, Kazu Yokoi, Oliver Brock, Kyong-Sok Chang, Arancha Casal
Proceedings of the First Workshop on Robot Motion and Control. June 1999. p. 213-221.

“High-Speed Navigation Using the Global Dynamic Window Approach”
Brock, O, Khatib, O.
Proc. IEEE International Conference on Robotics and Automation, Detroit, May 1999, pp. 341-346.

“Elastic Strips: A Framework for Integrated Planning and Execution”
Brock, O, Khatib, O.
Preprints, 6th International Symposium on Experimental Robotics (ISER’99), Sydney, March 1999, pp. 245-254.

“Elastic Strips: A Framework for Integrated Planning and Execution”
Oliver Brock, Oussama Khatib
Proceedings of the 1999 International Symposium on Experimental Robotics. Preprints, pages 245-54

“Mobile Manipulation: Collision-Free Path Modification and Motion Coordination.”
Brock, O, Khatib, O.
Proceedings of the 2nd International Conference on Computational Engineering in Systems Applications, Hammamet, Tunisia, April 1998, vol 4, pp. 839-845.

“Elastic Strip: Real-Time Path Modification for Mobile Manipulation”
Brock, O, Khatib, O.
Robotics Research, The Eighth International Symposium, Y. Shirai and S. Hirose, eds. Springer 1998, pp. 5-13.

“Elastic Strips: Real-Time Path Modification for Mobile Manipulation”
Oliver Brock, Oussama Khatib
In Robotics Research, pages 5-13, Springer Verlag, 1998

“Executing Motion Plans for Robots with Many Degrees of Freedom in Dynamic Environments”
Oliver Brock, Oussama Khatib
Proceedings of the 1998 IEEE International Conference on Robotics and Automation, Volume 1, pages 1-6, 1998

“Elastic Strips: Real-Time Path Modification for Mobile Manipulation”
Brock, O, Khatib, O.
Preprints of ISRR’97, the Eighth International Symposium of Robotics Research, Hayama, Japan, October 1997, pp. 117-122.

“Elastic Bands: Connecting Path Planning and Robot Control.”
Quinlan, S, Khatib, O.
Proc. IEEE International Conference on Robotics and Automation, Atlanta, Georgia 1993, vol 2. pp. 802-807.