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 ...