Timed elastic bands

Elastic Bands: Connecting Path Planning and Control

Sean Quinlan and Oussama Khatib
Robotics Laboratory
Computer Science Department
Stanford University

Abstract
Elastic bands are proposed as the basis for a new framework to close the gap between global path planning and real-time sensor-based robot control. An elastic band is a deformable collision-free path. The initial shape of the elastic is the free path generated by a planner. Subjected to artificial forces, the elastic band deforms in real time to a short and smooth path that maintains clearance from the obstacles. The elastic continues to deform as changes in the environment are detected by sensors, enabling the robot to accommodate uncertainties and react to unexpected and moving obstacles. While providing a tight connection between the robot and its environment, the elastic band preserves the global nature of the planned path. This paper outlines the framework and discusses an efficient implementation based on bubbles.

We propose a new framework to close the gap between path planning and control. The idea is to implement local sensor based motions by deforming in real time the path computed by the planner. We call such a deforming collision-free path an elastic band [3].

􀀀 Path planning: A world model is used to generate global solutions to specified tasks.
􀀀 Elastic bands: The path from the planner is deformed in real time to handle local changes in the environment detected by sensors and to smooth the path.
Control: A conventional control law is used to move the robot along the elastic band.

By deforming the path when changes in the environment are detected, we avoid the expense of recalling the path planner; the robot can react in real time to information obtained by sensors. However, while performing local behaviors we maintain a complete collision-free path to the goal.

To improve the shape of the path we apply two forces: an internal contraction force and an external repulsive force. The contraction force simulates the tension in a stretched elastic band and removes any slack in the path. To counter the contraction force and to give the robot clearance around the obstacles, the elastic band is repelled from the obstacles. The two forces deform the elastic
until equilibrium is reached as shown in figure

The appearance of new obstacles or the detection of uncertainties in the environment change the forces on the elastic, causing it to deform to a new equilibrium position.

Obviously, if the changes in the environment are large, the elastic band could fail to deform to a collision-free path even if one exists.

In many respects, elastic bands are similar to snakes [4]. A snake, as used in computer vision, is a deformable curve guided by artificial forces designed to pull it towards features in an image. The major difference is that an elastic band must represent a collision free path for the robot.

To check that a curve is collision free, we must examine the configuration space, or c-space, of the robot [5]. The free space of a robot is the area of the c-space in which the robot does not touch any obstacles. The determination of whether a path lies in the free space is difficult for two reasons. First, the free space is computationly expensive to generate and difficult to represent.
For even the simple case of a planar polygonal robot and polygonal obstacles, the boundary of the free space is a complex curved three dimensional manifold. Second, we desire a smooth path for the robot and hence are required to check that curves, rather than line segments, lie in the free space. The complexity of such computations is exemplified by the number of path planners that output
paths as a series of line segments.

we use a model of the environment and robot to generate, on the fly, local subsets of the free space. Each subset, called a bubble, is computed by examining the local freedom of the robot at a given configuration.

An elastic band is represented by a finite series of bubbles, constructed from a series of configurations or via points for the robot

Although the details are not give in this paper, we have developed a closed form solution for determining minimum strain energy splines that can be used to construct a path for the robot that is contained by the bubbles of an elastic band. The resulting path has first order continuity which is required if the robot is to track the path without stopping. Figure 3 depicts a series of bubbles and a path for the robot. The bubble representation of an elastic band has the desirable property that the complexity of the representation is related to the complexity of the situation. When the robot is far from obstacles, the bubbles will tend to be
large and can hence be spaced far apart.

shape, a circular bubble can only coarsely represent the free space around the robot. More complex shapes, such as ellipses, could be used to better represent the local free space but there is a tradeoff. Fewer bubbles may be needed to describe the elastic band, but each bubble is more difficult to compute. The effect of this tradeoff might be interesting to investigate.

shape, a circular bubble can only coarsely represent the free space around the robot. More complex shapes, such as ellipses, could be used to better represent the local free space but there is a tradeoff. Fewer bubbles may be needed to describe the elastic
band, but each bubble is more difficult to compute. The effect of this tradeoff might be interesting to investigate.

shape, a circular bubble can only coarsely represent the free space around the robot. More complex shapes, such as ellipses, could be used to better represent the local free space but there is a tradeoff. Fewer bubbles may be needed to describe the elastic band, but each bubble is more difficult to compute. The effect of this tradeoff might be interesting to investigate.

The magnitude and direction of the motion of a bubble is determined by computing an artificial force. In the current implementation, the artificial force is made up of an internal contraction force to remove slack in the elastic band and an external repulsion force to move the elastic away from the boundary of the free space.

where k c is the global contraction gain. The physical interpretation is a series of springs between the the bubbles. The force from each spring is normalized to reflect a uniform tension along the elastic band.

The size of a bubble gives an indication of how far the robot is from collision so we define the repulsive force such that it
increases this size. In the case of the circular bubbles, r(b) determines the size and one possibility for the repulsion
force is

The idea is that as the bubbles must overlap to form a valid elastic band, small bubbles should move less than large bubbles.
The above update equation implements a form of downhill gradient search to find the equilibrium point for the elastic band.

for example, we have implemented a version in which an inertial term is added to the bubbles to simulate a second order control
system.

Another modification to the elastic band is to remove redundant bubbles. We can scan the series of bubbles for situations in which a bubble’s neighbors overlap each other, allowing the bubble to be removed without breaking the elastic band. Deleting a bubble is desirable because it reduces the number of bubbles that need to be manipulated and thus reduces the computation required to
update the elastic band.The insertion of new bubbles and the removal of redundant bubbles can cause an undesirable side effect

The sequence can continue indefinitely and hence the elastic band oscillates in an unstable fashion. One solution to this problem consists of modifying the total force applied to the elastic band such that the tangential component is removed. Such a modified force inhibits the migration of bubbles along the elastic band. Mathematically, the modified force f* is given by the formula