5: Navigation

“the process of directing a vehicle so as to reach the intended destination — IEEE Standard 172-1983.

Robot navigation is the problem of guiding a robot towards a goal. The human approach to navigation is to make maps and erect signposts, and at first glance it seems obvious that robots should operate the same way. However many robotic tasks can be achieved without any map at all, using an approach referred to as reactive navigation. For example heading towards a light, following a white line on the ground, moving through a maze by following a wall, or vacuuming a room by following a random path. The robot is reacting directly to its environment: the intensity of the light, the relative position of the white line or contact with a wall.

The more familiar human-style map-based navigation is used by more sophisticated robots. This approach supports more complex tasks but is itself more complex. It imposes a number of requirements, not the least of which is a map of the environment. It also requires that the robot’s position is always known. In the next chapter we will discuss how robots can determine their position and create maps. The remainder of this chapter discusses the reactive and map-based approaches to robot navigation with a focus on wheeled robots operating in a planar environment. The chapter covers:

  • Reactive navigation
    • Braitenberg vehicles
    • Bug-style automata
  • Map-based navigation
    • distance transform
    • D*
    • Voronoi roadmap method
    • Probabilistic roadmap method (PRM)
    • Lattice planner
    • Rapidly-exploring random tree (RRT)