Page 358 - Introduction to AI Robotics

341
Hybrid Architecture
9.5 Case Study of Topological Navigation with a
The Task Manager in SFX uses the path computed by the cartographer to
select the appropriate abstract navigation behavior (Ch. 5) for traveling between
a particular pair of nodes. It maintains a pointer to the current node and the
next intended node from the path. The current and next node type determine
TRANSITION TABLE the appropriate behavior according to the transition table shown below:
To
From H F R H
H Navigate-hall Navigate-hall Undefined Navigate-hall
F Navigate-hall Navigate-foyer Navigate-door Navigate-hall
R Undefined Navigate-door Navigate-door Navigate-door
Hd Navigate-hall Navigate-hall Navigate-door Navigate-hall
The transition table shows that not all combinations of nodes are permit-
ted; by definition, the robot cannot move from a hall node H to a room node
R without going through a Hd node. Also, the table is not necessarily sym-
metrical. In the case of rooms, navigate-door must be employed to either
enter or exit, but the case of moving to a foyer will use different strategies
depending on whether the robot is traversing a hall or a foyer. The ANB it-
self uses the information in the database entries for the nodes as parameters
for instantiating the script to the current waypoint pair.
One novel aspect of this implementation is how the Task Manager han-
dles a blocked path; it does not reverse the currently instantiated abstract
navigation behavior (ANB). If the obstacle avoidance behavior posts to the
whiteboard structure that a BLOCKED condition has occurred, the Task Man-
ager terminates the currently active abstract navigation behavior. Because
the robot is between nodes, the Task Manager directs the robot to return to
the current node. But it triggers a simple move-to-goal behavior, which al-
lows the robot to reorient itself more quickly than reinstantiating the abstract
navigation behavior with new parameters.
Once the robot has returned to approximately the last known location, the
Task Manager requests a new path from the Cartographer. The Cartogra-
pher removes the connection between the current and intended nodes, then
recomputes a new path with the current node as the start. Once the new path
is completed, the Task Manager resumes control.
Fig. 9.12 demonstrates the robot moving through the map handed out at
the actual AAAI Mobile Robot Competition. The start node is R7 and the
goal is R2. The cartographer computes the path as R7-H1-H2-H5-R2, elim-
inating H3 and H4 because they are not relevant for this task.