Page 274 - Introduction to Autonomous Mobile Robots

259
Planning and Navigation
A useful concept throughout this discussion of robot architecture involves whether par-
ticular design decisions sacrifice the system’s ability to achieve a desired goal whenever a
solution exists. This concept is termed completeness. More formally, the robot system is
complete if and only if, for all possible problems (i.e., initial belief states, maps, and goals),
when there exists a trajectory to the goal belief state, the system will achieve the goal belief
state (see [27] for further details). Thus when a system is incomplete, then there is at least
one example problem for which, although there is a solution, the system fails to generate a
solution. As you may expect, achieving completeness is an ambitious goal. Often, com-
pleteness is sacrificed for computational complexity at the level of representation or rea-
soning. Analytically, it is important to understand how completeness is compromised by
each particular system.
In the following sections, we describe key aspects of planning and reacting as they apply
to a mobile robot path planning and obstacle avoidance and describe how representational
decisions impact the potential completeness of the overall system. For greater detail, refer
to [21, 30, chapter 25].

6.2.1 Path planning
Even before the advent of affordable mobile robots, the field of path-planning was heavily
studied because of its applications in the area of industrial manipulator robotics. Interest-
ingly, the path planning problem for a manipulator with, for instance, six degrees of free-
dom is far more complex than that of a differential-drive robot operating in a flat
environment. Therefore, although we can take inspiration from the techniques invented for
manipulation, the path-planning algorithms used by mobile robots tend to be simpler
approximations owing to the greatly reduced degrees of freedom. Furthermore, industrial
robots often operate at the fastest possible speed because of the economic impact of high
throughput on a factory line. So, the dynamics and not just the kinematics of their motions
are significant, further complicating path planning and execution. In contrast, a number of
mobile robots operate at such low speeds that dynamics are rarely considered during path
planning, further simplifying the mobile robot instantiation of the problem.

Configuration space. Path planning for manipulator robots and, indeed, even for most
mobile robots, is formally done in a representation called configuration space. Suppose that
k
a robot arm (e.g., SCARA robot) has degrees of freedom. Every state or configuration of
k
the robot can be described with real values: q 1 , …, q k . The k-values can be regarded as
k
p
a point in a -dimensional space called the configuration space C of the robot. This
description is convenient because it allows us to describe the complex 3D shape of the robot
with a single -dimensional point.
k
Now consider the robot arm moving in an environment where the workspace (i.e., its
physical space) contains known obstacles. The goal of path planning is to find a path in the