IN RECENT YEARS, robots play an active role in everyday
life: medical robots assist in complex surgeries;
search-and-rescue robots are employed in mining
accidents; and low-cost commercial robots clean
houses. There is a growing need for sophisticated
algorithmic tools enabling stronger capabilities for
these robots. One fundamental problem that robotic
researchers grapple with is motion planning—which
deals with planning a collision-free path for a moving
system in an environment cluttered with obstacles. 13, 29
TO A LAYMAN, it may seem the wide use of robots in
modern life implies that the motion-planning problem
has already been solved. This is far from true. There is
little to no autonomy in surgical robots and every owner
of a house-cleaning robot has experienced the highly
simplistic (and often puzzling) routes taken by the robot.
Roughly speaking, the complexitya
of a motion-planning problem is primarily governed by two factors: The
dimension of the configuration space
(C-space)—a space defined by the parameters needed to describe the robot’s
position and orientation, and the
tightness of the environment—informally,
an environment is said to be tight if the
robot is required to move with little or
no clearanceb from the obstacles.
algorithms can efficiently construct
paths for low-complexity problems
(that is, either problems whose C-space
is low-dimensional or problems that
do not contain narrow passages). However, as the complexity increases, their
running time may grow in an exponential fashion (exponential in the dimension of the C-space or in the clearance
of the path that the robot needs to
move along13, 25).
Moreover, algorithms that produce high-quality pathsc with optimality guarantees21 require additional overhead both in terms of running time and
memory consumption when compared
to the basic version of these algorithms.
In this article, I provide insight on
why planning (high-quality) paths for
complex robotic systems is computationally challenging. Specifically,
after providing algorithmic background, we examine general computational challenges that arise in
motion planning. This is done by examining sampling-based methods,
a common approach to address the
a Here, the term “complexity” is used loosely
to describe where state-of-the-art planners
struggle—the PSPACE-Hardness proof of the
motion-planning problem13 actually argues
about the complexity of obstacles. However,
in practice, we can deal with a large number of
obstacles using efficient data structures.
b The clearance of the robot is its distance from
the nearest obstacle. The clearance of a ro-
bot’s path is the minimal distance attained
over all points along the path.
c In motion-planning applications, the quality
of a path can be measured in terms of, for ex-
ample, path length, clearance, smoothness or
energy consumption along the path, to men-
tion a few criteria.
To address the computational challenges
that arise when planning for robotic
systems, traditional CS algorithms, tools,
and paradigms must be revisited.
BY OREN SALZMAN