Page 356 - Introduction to AI Robotics

Path planning
9.5.1 9.5 Case Study of Topological Navigation with a Hybrid Architecture 339
The topological map was entered as an ASCII file in Backus-Naur Form. A
sample map is shown in Fig. 9.11. The input map consists of three node types:
room (R), hall (H), and foyer (F). The world is assumed to be orthogonal.
Since edges between nodes can be in only four directions, it is convenient
to refer to them as north (N), south (S), east (E), and west (W), where N is set
arbitrarily in the map. The robot is given its starting node but as an extra
challenge, the robot is not given the direction it is initially facing relative to
the map. The topological map is structurally correct, but does not necessarily
represent if a corridor or door is blocked. Such blockages may occur or be
moved at any time. An additional assumption is that the outside of each
door is marked with a landmark such as a room number or room name.
The Cartographer in SFX is responsible for constructing the route. It takes
as input a gateway type of topological map and a start node and goal node,
and produces a list of nodes representing the best path between the start and
goal. The cartographer operates in two steps: preprocessing of the map to
support path planning, and path planning. The preprocessing step begins by
building a database of the nodes in the input map, reclassifying the corridor
nodes which represent a hall to door connection as Hd.
Once the start and goal nodes are known, the Cartographer eliminates ex-
traneous gateways. A Hd node may be connected to a room which is not
visitable, that is, it is neither the goal room, the start room, or a room with
more than one door. If that occurs, then both the R and Hd node entries are
eliminated from the database. A sample input graphical topological repre-
sentation for a metric map is shown in Fig. 9.11. If R3 was selected as the
start node and R7 the goal, the refined graphical representation is as shown
in Fig. 9.11. Note that Hd3-R1 and Hd4-R6 were eliminated because they
were not associated with the start or goal rooms and could not be used as a
shortcut since they had only one entrance. Gateway nodes such as H10 re-
main in the path because they may be useful if a blocked path occurs. For
example, if the robot is going down the hallway from H11 to H8 and the path
is blocked, the robot will need to return to a known location in order to reori-
ent itself and replan. However, if the H10 is eliminated, then the robot must
return to the very beginning of the corridor, because it does not know where
it is with respect to H10. To solve this dilemma of traveling the same part
of the corridor possibly three times, the cartographer maintains nodes which
represent possible alternative strategies. Different types of gates, tasks, and
robot capabilities will lead to different preprocessing strategies.