Lab Meeting September 9th, 2011 (Chih Chung): Identification and Representation of Homotopy (RSS 2011 Best paper)

title: Identification and Representation of Homotopy
Classes of Trajectories for Search-based Path
Planning in 3D

Authors: Subhrajit Bhattacharya, Maxim Likhachev and Vijay Kumar

Abstract: There are many applications in motion planning
where it is important to consider and distinguish between
different homotopy classes of trajectories. Two trajectories are
homotopic if one trajectory can be continuously deformed into
another without passing through an obstacle, and a homotopy
class is a collection of homotopic trajectories. In this paper
we consider the problem of robot exploration and planning in
three-dimensional configuration spaces to (a) identify and classify
different homotopy classes; and (b) plan trajectories constrained
to certain homotopy classes or avoiding specified homotopy
classes. In previous work [1] we have solved this problem for
two-dimensional, static environments using the Cauchy Integral
Theorem in concert with graph search techniques. The robot
workspace is mapped to the complex plane and obstacles are poles
in this plane. The Residue Theorem allows the use of integration
along the path to distinguish between trajectories in different
homotopy classes. However, this idea is fundamentally limited
to two dimensions. In this work we develop new techniques to
solve the same problem, but in three dimensions, using theorems
from electromagnetism. The Biot-Savart law lets us design an
appropriate vector field, the line integral of which, using the
integral form of Ampere’s Law, encodes information about
homotopy classes in three dimensions. Skeletons of obstacles
in the robot world are extracted and are modeled by currentcarrying
conductors. We describe the development of a practical
graph-search based planning tool with theoretical guarantees
by combining integration theory with search techniques, and
illustrate it with examples in three-dimensional spaces such as
two-dimensional, dynamic environments and three-dimensional
static environments.


link