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

PROBLEM STATEMENT 143

Within the Piano Mover’s paradigm, a number of kinematic holonomic strate-
gies make use of the artificial potential field. They usually require complete
information and analytical presentation of obstacles; the robot’s motion is affected
by (a) the “repulsive forces” created by a potential field associated with obstacles
and (b) “attractive forces” associated with the goal position [85]. A typical con-
vergence issue here is how to avoid possible local minima in the potential field.
Modifications that attempt to solve this problem include the use of repulsive
fields with elliptic isocontours [86], introduction of special global fields [87],
and generation of a numerical field [88]. The vortex field method [89] allows
one to avoid undesirable attraction points, while using only local information;
the repulsive actions are replaced by the velocity flows tangent to the isocontours,
so that the robot is forced to move around obstacles. An approach called active
reflex control [90] attempts to combine the potential field method with handling
the robot dynamics; the emphasis is on local collision avoidance and on filtering
out infeasible control commands generated by the motion planner.
Among the approaches that deal with incomplete information, a good number
of holonomic techniques originate in maze-search strategies (see the previous
chapters). When applicable, they are usually fast, can be used in real time, and
guarantee convergence; obstacles in the scene may be of arbitrary shape.
There is also a group of nonholonomic motion planning approaches that ignore
the system dynamics. These also require analytical representation of obstacles
and assume complete [91–93] or partial input information [94]. The schemes are
essentially open-loop, do not guarantee convergence, and attempt to solve the
planning problem by taking into account the effect of nonholonomic constraints
on obstacle avoidance. In Refs. 91 and 92 a two-stage scheme is considered:
First, a holonomic planner generates a complete collision-free path, and then this
path is modified to account for nonholonomic constraints. In Ref. 93 the problem
is reduced to searching a graph representing the discretized configuration space.
In Ref. 94, planning is done incrementally, with partial information: First, a
desirable path is defined and then a control is found that minimizes the error in
a least-squares sense.
To design a provably correct dynamic algorithm for sensor-based motion plan-
ning, we need a single control mechanism: Separating it into stages is likely to
destroy convergence. Convergence has two faces: Globally, we have to guarantee
finding a path to the target if one exists. Locally, we need an assurance of col-
lision avoidance in view of the robot inertia. The former can be borrowed from
kinematic algorithms; the latter requires an explicit consideration of dynamics.
Notice an interesting detail: In spite of sufficient knowledge about the piece
of the scene that is currently within the robot’s sensing range, even in this area it
would make little sense at a given step to address the planning task as one with
complete information, as well as to try to compute the whole subpath within the
sensing range. Why not? Computing this subpath would require solving a rather
difficult optimal motion control problem—a computationally expensive task. On
the other hand, this would be largely computational waste, because only the first
step of this subpath would be executed: As new sensing data appears at the next