Page 336 - Introduction to AI Robotics

319
Part II
Xavier at CMU has learned to avoid cutting through a particular foyer when
classes are changing, since the density of people moving about slows down
its progress.

Criteria for Evaluating Path Planners

Although it should be clear by the end of Part II that navigation is more than
path planning, path planning is the most obvious aspect of navigation from
a programmer’s standpoint. A designer has a wide variety of techniques to
choose from, spanning close to 30 years of research. As with everything else
robotic, the choice of technique depends on the ecological niche the robot
will operate in. The criteria for evaluating the suitability of a path planner
includes:

1. Complexity. Is the algorithm too computationally or space intensive to
execute or reside within the limitations of the robot?

2. Sufficiently represents the terrain. Many researchers work in indoor environ-
ments, which are flat. Outdoor robots may be operating in rough terrain
with steep inclines or undesirable areas, such as slippery sand or mud. If
the path planning algorithm is built to generate paths from a binary rep-
resentation (a region is either navigable or not), then it may lead the robot
into trouble if it is applied to a more diverse environment.

3. Sufficiently represents the physical limitations of the robot platform. Robots
have physical limitations. The most profound limitation which impacts
path planning is whether a robot is holonomic or not. Recall that holo-
nomic robots can turn in place. Since they can spin on a dime, the path
planning algorithm doesn’t have to consider the steering radius of the
robot. Likewise, robots may not be round. Robots made for research pur-
poses such as Nomad 200’s, Khepera, and RWI B-series are often round
so that when they turn in place, they won’t bump into anything. A robot
which is not round introduces more complexity. In order to turn in a nar-
row hall, it may have to “watch its back” to make sure it doesn’t bump
anything.

4. Compatible with the reactive layer. Path planners are deliberative by def-
inition. But in a Hybrid style of architecture, the reactive layer will be
responsible for carrying out the path. A technique which simplifies this
transformation is desirable.