Page 98 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

CHAPTER 3

Motion Planning for a Mobile Robot

Thou mayst not wander in that labyrinth; There Minotaurs and ugly treasons lurk.
—William Shakespeare, King Henry the Sixth

What is the difference between exploring and being lost?
—Dan Eldon, photojournalist

As discussed in Chapter 1, to plan a path for a mobile robot means to find a
continuous trajectory leading from its initial position to its target position. In
this chapter we consider a case where the robot is a point and where the scene
in which the robot travels is the two-dimensional plane. The scene is populated
with unknown obstacles of arbitrary shapes and dimensions. The robot knows
its own position at all times, and it also knows the position of the target that it
attempts to reach. Other than that, the only source of robot’s information about
the surroundings is its sensor. This means that the input information is of a local
character and that it is always partial and incomplete. In fact, the sensor is a
simple tactile sensor: It will detect an obstacle only when the robot touches it.
“Finding a trajectory” is therefore a process that goes on in parallel with the
journey: The robot will finish finding the path only when it arrives at the target
location.
We will need this model simplicity and the assumption of a point robot only
at the beginning, to develop the basic concepts and algorithms and to produce
the upper and lower bound estimates on the robot performance. Later we will
extend our algorithmic machinery to more complex and more practical cases,
such as nonpoint (physical) mobile robots and robot arm manipulators, as well
as to more complex sensing, such as vision or proximity sensing. To reflect the
abstract nature of a point robot, we will interchangeably use for it the term
moving automaton (MA, for brevity), following some literature cited in this
chapter.
Other than those above, no further simplifications will be necessary. We will
not need, for example, the simplifying assumptions typical of approaches that
deal with complete input information such as approximation of obstacles with
Sensing, Intelligence, Motion, by Vladimir J. Lumelsky
Copyright  2006 John Wiley & Sons, Inc.
73