[ Pobierz całość w formacie PDF ]

90
curves or bridges are constructed.
6.1 Background
There have been two major approaches to motion planning for manipulators,
i local methods, such as arti cial potential eld methods 50 , which are usually fast
but are not guaranteed to nd a path, and ii global methods, like the rst Roadmap
Algorithm 18 , which is guaranteed to nd a path but may spend a long time doing
it. In this chapter, we present an algorithm which has characteristics of both. Our
method is an incremental construction of a skeleton of free-space. Like the potential
eld methods, the curves of this skeleton locally maximizes a certain potential function
that varies with distance from obstacles. Like the Roadmap Algorithm, the skeleton,
computed incrementally, is eventually guaranteed to contain a path between two
con gurations if one exists. The size of the skeleton in the worst case, is comparable
with the worst-case size of the roadmap.
Unlike the local methods, our algorithm never gets trapped in local extremal
points. Unlike the Roadmap Algorithm, our incremental algorithm can take advan-
tage of a non-worst-case environment. The complexity of the roadmap came from
the need to take recursive slices through con guration space. In our incremental
algorithm, slices are only taken when an initial search fails and there is a bridge"
through free space linking two channels". The new algorithm is no longer recursive
because bridges can be computed directly by hill-climbing . The bridges are built
near interesting" critical points and in ection points. The conditions for a bridge
are quite strict. Possible candidate critical points can be locally checked before a slice
is taken. We expect few slices to be required in typical environments.
In fact, we can make a stronger statement about completeness of the algo-
rithm. The skeleton that the algorithm computes eventually contains paths that are
homotopic to all paths in free space. Thus, once we have computed slices through
all the bridges, we have a complete description of free-space for the purposes of path
planning. Of course, if we only want to nd a path joining two given points, we stop
the algorithm as soon as it has found a path.
91
The tracing of individual skeleton curves is a simple enough task that we
expect that it could be done in real time on the robot's control hardware, as in other
arti cial potential eld algorithms. However, since the robot may have to backtrack
to pass across a bridge, it does not seem worthwhile to do this during the search.
For those readers already familiar with the Roadmap Algorithm, the follow-
ing description may help with understanding of the new method: If the con guration
space is Rk, then we can construct a hypersurface in Rk+1 which is the graph of the
potential function, i.e. if P x1; : : : ; xk is the potential, the hypersurface is the set
of all points of the form x1; : : : ; xk; P x1; : : : ; xk . The skeleton we de ne here is a
subset of a roadmap in the sense of 18 of this hypersurface.
This work builds on a considerable volume of work in both global motion
planning methods 18 54 , 73 , 78 , and local planners, 50 . Our method shares a
common theme with the work of Barraquand and Latombe 6 in that it attempts to
use a local potential eld planner for speed with some procedure for escaping local
maxima. But whereas Barraquand and Latombe's method is a local method made
global, we have taken a global method the Roadmap Algorithm and found a local
opportunistic way to compute it.
Although our starting point was completely di erent, there are some other
similarities with 6 . Our freeways" resemble the valleys intuitively described in 6 .
But the main di erence between our method and the method in 6 is that we have
a guaranteed and reasonably e cient method of escaping local potential extremal
points and that our potential function is computed in the con guration space.
The chapter is organized as follows: Section 6.2 contains a simple and gen-
eral description of roadmaps. The description deliberately ignores details of things
like the distance function used, because the algorithm can work with almost any
function. Section 6.3 gives some particulars of the application of arti cial potential
elds. Section 6.4 describes our incremental algorithm, rst for robots with two de-
grees of freedom, then for three degrees of freedom. Section 6.5 gives the proof of
completeness for this algorithm.
92
6.2 A Maximum Clearance Roadmap Algorithm
We denote the space of all con gurations of the robot as CS. For example,
for a rotary joint robot with k joints, the con guration space CS is Rk , the set of all
joint angle tuples ; : : : ; . The set of con gurations where the robot overlaps some
1 k
obstacle is the con guration space obstacle CO, and the complement of CO is the
set of free non-overlapping con gurations FP. As described in 18 , FP is bounded
by algebraic hypersurfaces in the parameters ti after the standard substitution ti =
i
tan . This result is needed for the complexity bounds in 18 but we will not need
2
it here.
A roadmap is a one-dimensional subset of FP that is guaranteed to be
connected within each connected component of FP. Roadmaps are described in some
detail in 18 where it is shown that they can be computed in time O nk log n dO n2
for a robot with k degrees of freedom, and where free space is de ned by n polynomial
constraints of degree d 14 . But nk may still be too large for many applications, and
in many cases the free space is much simpler than its worst case complexity, which
is O nk . We would like to exploit this simplicity to the maximum extent possible.
The results of 6 suggest that in practice free space is usually much simpler than the
worst case bounds. What we will describe is a method aimed at getting a minimal
description of the connectivity of a particular free space. The original description of
roadmaps is quite technical and intricate. In this paper, we give a less formal and
hopefully more intuitive description.
6.2.1 De nitions
Suppose CS has coordinates x1; : : : ; xk. A slice CSj is a slice by the hy-
v
perplane x1 = v. Similarly, slicing FP with the same hyperplane gives a set denoted
FPj . The algorithm is based on the key notion of a channel which we de ne next:
v
A channel-slice of free space FP is a connected component of some slice
FPj .
v
93
The term channel-slice is used because these sets are precursors to channels. To
construct a channel from channel slices, we vary v over some interval. As we do this,
for most values of v, all that happens is that the connected components of FPj
v
change shape continuously. As v increases, there are however a nite number of
values of v, called critical values, at which there is some topological change. Some
events are not signi cant for us, such as where the topology of a component of the
cross-section changes, but there are four important events: As v increases a connected
component of FPj may appear or disappear, or several components may join, or a
v
single component may split into several. The points where joins or splits occur are
called interesting critical points. We de ne a channel as a maximal connected union
of cross sections that contains no image of interesting critical points. We use the [ Pobierz całość w formacie PDF ]