Page 157 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

132 MOTION PLANNING FOR A MOBILE ROBOT

Moving Obstacles. The model of motion planning considered in this chapter
(Section 3.1) assumes that obstacles in the robot’s environment are all static—that
is, do not move. But obstacles in the real world may move. Let us call an envi-
ronment where obstacles may be moving the dynamic (changing, time-sensitive)
environment. Can sensor-based planning strategies be developed capable of han-
dling a dynamic environment? Even more specifically, can strategies that we
developed in this chapter be used in, or modified to account for, a dynamic
environment?
The answer is a qualified yes. Since our model and algorithms do not include
any assumptions about specifics of the geometry and dimensions of obstacles
(or the robot itself), they are in principle ideally suited for handling a dynamic
environment. In fact, one can use the Bug and VisBug family algorithms in a
dynamic environment without any changes. Will they always work? The answer
is, “it depends,” and the reason for the qualified answer is easy to understand.
Assume that our robot moves with its maximum speed. Imagine that while
operating under one of our algorithms—it does not matter which one—the robot
starts passing around an obstacle that happens to be of more or less complex
shape. Imagine also that the obstacle itself moves. Clearly, if the obstacle’s
speed is higher than the speed of the robot, the robot’s chance to pass around
the obstacle and ever reach the target is in doubt. If on top of that the obstacle
happens to also be rotating, so that it basically cancels the robot’s attempts
to pass around it, the answer is not even in doubt: The robot’s situation is
hopeless.
In other words, the motion parameters of obstacles matter a great deal. We
now have two options to choose from. One is to use algorithms as they are,
but drop the promise of convergence. If the obstacles’ speeds are low enough
compared to the robot, or if obstacles move more or less in one place, like a
tree in the wind, then the robot will likely get where it intends. Even if obstacles
move faster than the robot, but their shapes or directions of motion do not create
situations as in the example above, the algorithms will still work well. But, if
the situation is like the one above, there will be no convergence.
Or we can choose another option. We can guarantee convergence of an algo-
rithm, but impose some additional constraints on the motion of objects in the
robot workspace. If a specific environment satisfies our constraints, convergence
is guaranteed. The softer those constraints, the more universal the resulting algo-
rithms. There has been very little research in this area.
For those who need a real-world incentive for such work, here is an example.
Today there are hundreds of human-made dead satellites in the space around
Earth. One can bet that all of them have been designed, built, and launched at
high cost. Some of them are beyond repair and should be hauled to a satellite
cemetery. Some others could be revived after a relatively simple repair—for
example, by replacing their batteries. For long time, NASA (National Aeronautics
and Space Administration) and other agencies have been thinking of designing a
robot space vehicle capable of doing such jobs.