Page 273 - Introduction to Autonomous Mobile Robots

258

6.2 Competences for Navigation: Planning and Reacting Chapter 6

In the artificial intelligence community planning and reacting are often viewed as contrary
approaches or even opposites. In fact, when applied to physical systems such as mobile
robots, planning and reacting have a strong complementarity, each being critical to the
other’s success. The navigation challenge for a robot involves executing a course of action
(or plan) to reach its goal position. During execution, the robot must react to unforeseen
events (e.g., obstacles) in such a way as to still reach the goal. Without reacting, the plan-
ning effort will not pay off because the robot will never physically reach its goal. Without
planning, the reacting effort cannot guide the overall robot behavior to reach a distant goal
– again, the robot will never reach its goal.
An information-theoretic formulation of the navigation problem will make this comple-
i
mentarity clear. Suppose that a robot M at time has a map M i and an initial belief state
b i . The robot’s goal is to reach a position while satisfying some temporal constraints:
p
;
loc R() = p ( g ≤ n) . Thus the robot must be at location at or before timestep n.
p
g
Although the goal of the robot is distinctly physical, the robot can only really sense its
belief state, not its physical location, and therefore we map the goal of reaching location p
to reaching a belief state b g , corresponding to the belief that loc R() = p . With this for-
g
q
mulation, a plan is nothing more than one or more trajectories from b to b . In other
i g
words, plan q will cause the robot’s belief state to transition from b to b if the plan is
i g
executed from a world state consistent with both b i and M i .
Of course the problem is that the latter condition may not be met. It is entirely possible
that the robot’s position is not quite consistent with b , and it is even likelier that M is
i i
either incomplete or incorrect. Furthermore, the real-world environment is dynamic. Even
if M i is correct as a single snapshot in time, the planner’s model regarding how M changes
over time is usually imperfect.
In order to reach its goal nonetheless, the robot must incorporate new information gained
during plan execution. As time marches forward, the environment changes and the robot’s
sensors gather new information. This is precisely where reacting becomes relevant. In the
best of cases, reacting will modulate robot behavior locally in order to correct the planned-
upon trajectory so that the robot still reaches the goal. At times, unanticipated new infor-
mation will require changes to the robot’s strategic plans, and so ideally the planner also
incorporates new information as that new information is received.
Taken to the limit, the planner would incorporate every new piece of information in real
time, instantly producing a new plan that in fact reacts to the new information appropri-
ately. This theoretical extreme, at which point the concept of planning and the concept of
reacting merge, is called integrated planning and execution and is discussed in section
6.3.4.3.