Page 342 - Introduction to AI Robotics

9 Topological Path Planning

Chapter Objectives:

Define the difference between a natural and artificial landmark andgiveone
example of each.
Given a description of an indoor office environment and a set of behav-
iors, build a relational graph representation labeling the distinctive places
and local control strategies using gateways.
Describe in one or two sentences: gateway, image signature, visual homing,
viewframe, orientation region.

Given a figure showing landmarks, create a topological map showing
landmarks, landmark pair boundaries, and orientation regions.

9.1 Overview

TOPOLOGICAL Topological, route,or qualitative navigation is often viewed as being more sim-
NAVIGATION ple and natural for a behavior-based robot. Certainly people frequently give
other people routes as directives; therefore it seems natural to expect a robot
to be able to parse commands such as “go down the hall, turn to the left at
the dead end, and enter the second room on the right.” Even without a map
of where everything is, there is enough information for navigation as long as
the robot knows what a “hall,” “dead-end,“ and “room” is.
Route representations fall into one of two approaches:
1. Relational. Relational techniques are the most popular, and can be thought
of as giving the robot an abbreviated, “connect the dots” graph-style of
spatial memory.