Date: Tue, 05 Nov 1996 00:23:57 GMT Server: NCSA/1.4.1 Content-type: text/html
The problem of path planning for an automaton moving in a
two-dimensional scene filled with unknown obstacles is
considered. The automaton is presented as a point; obstacles
can be of an arbitrary shape, with continuous boundaries and of
finite size; no restriction on the size of the scene is
imposed. The information available to the automaton is limited
to its own current coordinates and those of the target
position. Also, when the automaton hits an obstacle, this fact
is detected by the automaton's ``tactile sensor''. This
information is shown to be sufficient for reaching the target or
concluding in finite time that the target cannot be reached. A
worst-case lower bound on the length of paths generated by any
algorithm operating within the framework of the accepted model
is developed; the bound is expressed in terms of the perimeters
of the obstacles met by the automaton in the scene. Algorithms
that guarantee reaching the target (if the target is reachable),
and tests for target reachability are presented. The efficiency
of the algorithms is studied, and worst-case upper bounds on the
length of generated paths are produced.
This paper presents a survey of one approach to planning
collision-free paths for an automaton operating in an
environment with obstacles. Path planning is one of the central
problems in robotics. Typically, the task is presented in the
two- or three-dimensional space, with the automaton being either
an autonomous vehicle or an arm manipulator with a fixed base.
The multiplicity of approaches one finds in this area revolves
around two basic models: in one, called path planning with
complete information, perfect information about the
geometry and positions of the robot and the obstacles is
assumed, whereas in the other, called path planning with
incomplete information, an element of uncertainty about the
environment is present. The approach surveyed here, called
dynamic path planning, has been developed in the last few
years; it is based on the latter model and gives rise to
algorithmic and computational issues very different from those
in the former model. The approach produces provable
(non-heuristic) path planning algorithms for an automaton
operating in a highly unstructured environment where no
knowledge about the obstacles is available beforehand and no
constraints on the geometry of the obstacles are
imposed.
This work is concerned with planning collision-free
paths for a robot arm moving in an environment filled with unknown
obstacles, where any point of the robot body is subject to collision.
To compensate for the uncertainty, the system is provided with sensory
feedback information about its immediate surroundings. In such a
setting, which presents significant practical and theoretical interest,
human intuition is of little help, and designing algorithms with proven
convergence thus becomes an important task. We show that, given the
target position, local feedback information is sufficient to guarantee
reaching a global objective (the target position), and present a
nonheuristic algorithm which generates reasonable -- if, in general, not
optimal -- collision-free paths. In this approach, the path is being
planned continuously (dynamically), based on the arm's current position
and on the sensory feedback. Here, a case of a planar arm with revolute
joints - vertical or horizontal (SCARA type) - is studied. No
constraints on the shape of the robot links or the obstacles are
imposed. The general idea is to reduce the problem of motion planning
to an analysis of simple closed curves on the surface of an appropriate
two-dimensional manifold.
Most of the work on robot path planning revolves around two
basic models: the model with complete information (often called
the Piano Mover's problem) and the model with incomplete
information (also called path planning with uncertainty). The
approach of dynamic path planning is based on the latter model
and produces nonheuristic (provable) algorithms for simple robot
arm manipulators operating in an environment with unknown
obstacles of arbitrary shapes. The algorithms assume local
on-line input information coming from the arm sensors.
Unfortunately, the existing techniques require that each
kinematic configuration be considered separately, which results
in different algorithms for different kinematics. In this
paper, a unified methodology is presented for designing dynamic
path planning algorithms for two- and three-dimensional two-link
arm manipulators. The approach is independent of the specifics
of the kinematic configuration, and imposes no constraints on
the shape of the arm links or obstacles in the environment. The
methodology exploits some important topological characteristics
of the configuration space. However, no explicit computation of
obstacles in the configurtation space ever takes place, which
results in fast real-time algorithms.
The existing approaches to sensor-based motion planning tend to
deal solely with kinematic and geometric issues, and ignore the
system dynamics. This work attempts to incorporate body dynamics
into the paradigm of sensor-based motion planning. We consider
the case of a mass point robot operating in a planar environment
with unknown arbitrary stationary obstacles. Given the
constraints on the robot's dynamics, sensing, and control means,
conditions are formulated for generating trajectories which
guarantee convergence and the robot's safety at all times. The
approach calls for continuous computation and is fast enough for
real time implementation. The robot plans its motion based on
its velocity, control means, and sensing information about the
surrounding obstacles, and such that in case of a sudden
potential collision it can always resort to a safe emergency
stopping path. Simulated examples demonstrate the algorithm's
performance.
Control schemes in real-time sensor-based systems often operate
under tight time constraints determined by the system sampling
rate. One area where such constraints are especially severe is
the sensor-based motion planning with dynamics in
robotics. Though very important both theoretically and in
practice, this problem has not been addressed so far. The
typical sampling rates in such systems are 20 to 50 per second.
This leaves only 20 to 50 msec for the whole cycle, including
sensing, complex geometric (intelligence) analysis, calculations
due to dynamics and control, and motion execution. As a first
attempt to solve the problem, we show that the time constraints
can be met by a combination of a simple model with a carefully
chosen analytical solution of the dynamic equations. The
resulting control scheme guarantees convergence and safety of
motion, and blends well with kinematic path planning
algorithms. Two such strategies are discussed, one using a
simple heuristic and the other with local optimization.
A model of mobile robot navigation is considered whereby the
robot is a point automaton operating in an environment with
unknown obstacles of arbitrary shapes. The robot's input
information includes its own and the target point coordinates,
as well as local sensing information such as from stereo vision
or a range finder. We address these algorithmic issues: (i) how
can one combine sensing and planning functions thus producing
active sensing quided by the needs of motion planning?
(ii) can richer sensing (say, stereo vision as opposed to
tactile sensing) guarantee better performance -- say, result in
shorter paths? (the general answer is ``no''). A paradigm for
combining range data with motion planning is presented. It
turns out that extensive modifications of simpler ``tactile''
algorithms are needed in order to take full advantage of
additional sensing capabilities. Two algorithms that guarantee
convergence and exhibit different ``styles'' of behavior are
described and their performance is demonstrated in simulated
examples.
This paper presents an approach to decentralized motion planning for
multiple mobile robots operating in a common 2-dimensional environment
with unknown stationary obstacles. Each robot is capable of
translatory motion and is equipped with range sensors which allow it
to sense surrounding objects. Each robot knows its current position,
is able to distinguish a robot from an obstacle, and can assess the
instantaneous motion of any robot it can sense. Other than this, a robot
has no knowledge about the scene, or of the paths or objectives of
other robots; there is no mutual communication among the robots. No
constraints are imposed on the paths or shapes of robots and
obstacles. Each robot plans its path toward its target dynamically,
based on its current position and sensory feedback. Given the
assumptions of incomplete information and decentralized planning, no
provable strategy can be designed (a simple example with a dead-lock
is discussed); this naturally points to heuristic strategies. The
suggested heuristic algorithm demonstrates a remarkable robustness and
ability for successful decentralized real-time motion planning in an
unknown complex environment.
We consider the problem of motion planning for a number of
small, circular robots in a common planar workspace. Each robot
is tethered to a point on the boundary of the workspace by a
flexible cable of finite length. These cables may be pushed and
bent by robots that come in contact with them but remain taut at
all times. The robots each have a target point to reach on the
workspace and, as each moves to its target, its cable gets
stretched out into the workspace. For any set of target points,
there may be many final cable configurations of differing
complexity that allow all robots to reach their targets.
Assuming a final configuration of the cables has been specified,
the motion planning task addressed here is to produce reasonably
short paths for the robots that will achieve this configuration.
This is formulated as a problem in computational geometry and an
O(n-cube \log n) algorithm is presented for achieving this
task for n robots.
An efficient, on-line three-dimensional terrain-covering
algorithm is presented for a robot (AUV) moving in an unknown
three-dimensional underwater environment. The algorithm can be
used, for example, for producing mosaicked images of the ocean
floor. The basis of the strategy is a new planar (2D) algorithm
for nonsimply connected areas with boundaries of arbitrary
shape. The algorithm is shown to generalize naturally to
complex three-dimensional environments in which the terrain to
be covered is projectively planar. Compared to other planar
procedures, this 2D algorithm does not assume a polygonal
environment and produces relatively short paths. The upper
bound on its path length performance is shown to be linear in
the size of the area to be covered; the amount of memory
required by the robot to implement the algorithm is linear in
the size of the description of the area's boundary. An example
is given that demonstrates the algorithm's performance in a
nonsimply connected, nonplanar environment.
A strategy is described for real-time motion planning for a
highly redundant snake-like robot manipulator operating in a
three-dimensional (3D) environment filled with unknown obstacles
of arbitrary shape. The robot consists of many (say 30 or 50)
links serially connected by the universal joints (such a joint
allows a 3D rotation of one link relative to the other). The
robot's sensors allow it to sense objects in the vicinity of any
point of its body. The task is to move the robot's tip point
(its head) from its starting position to a specified
target position, collision-free for the whole robot's body. To
achieve the efficiency necessary for real-time computation, an
iterative procedure is proposed which makes use of a unit motion
for a single link based on the tractrix curve. This
choice also results in automatically achieving a motion that is
``natural'' (in that the joint displacements tend to ``die out''
in the direction from head to tail) as well as locally optimal,
producing a minimum instantaneous total displacement of all the
links/joints.
This work addresses the issues of hardware implementation of a
sensor-based motion planning system for a whole-sensitive robot
arm manipulator operating among unknown obstacles of arbitrary
shape. In order to realize on-line planning algorithms while
protecting the whole arm body from potential collisions with
obstacles, the system includes infrared based proximity
sensitive skin covering the arm body, computer hardware for
signal processing and motion planning, and an interface between
the planning and arm control systems. These components are
described in detail, and their characteristics are discussed.
We consider the problem of sensor-based motion planning for a
three-dimensional robot arm manipulator operating among unknown
obstacles. Every point of the robot body is subject to potential
collisions. The planning system must include these four basic
components: sensor hardware; real-time signal/sensory data
processing hardware and software; a local step planning
subsystem that works at the basic sampling rate of the arm; and
finally, a subsystem for global planning. The arm sensor system
presents a proximity sensitive skin that covers the whole body
of the arm and consists of hundreds of active infra-red sensors
which detect obstacles by processing reflected light. The sensor
data then undergo low level processing via a step planning
procedure, which converts sensor information into local normals
at the contact points in the configuration space of the
arm. This paper presents preliminary results on the fourth
component, a real-time algorithm that realizes the upper, global
level of planning. Based on the current collection of the local
normals, the algorithm generates preferable directions of motion
around obstacles, so as to guarantee reaching the target
position if it is reachable. Experimental results from testing
the developed system are also discussed.
In traditional teleoperation systems, the human operator saddled with two
distinct tasks: 1) moving the robot arm to its desired position, and 2)
avoiding obstacles that can obstruct the arm motion. Current research in
robot teleoperation concentrates on providing the operator with as much
input information about the task site as possible, using, e.g., stereo
vision or contact force feedback. These methods presume that the
operator is capable of planning motion for the entire body of the robot
in a cluttered environment. Studies show, however, that the operators,
first, cannot address both tasks in real time, and second, are not good
at generating collision-free motion in a complex environment. Recent
theoretical work on sensor-based motion planning suggest that the
collision avoidance task can be handled automatically, thus freeing the
operator for global control. To this end, this work considers a
teleoperation system which makes use of a whole-sensitive arm
manipulators whose whole body is covered with a sensitive skin to detect
nearby objects. The data from the skin is processed by motion planning
algorithms, helping the entire arm body to avoid collisions in an unknown
or time-varying environment. The motion of a small operator-controlled
master arm is either executed faithfully by the main
slave arm, or, to avoid collisions, is used as general guidance. In
the latter case the slave arm attempts to be as close as possible to the
positions commanded by the operator, without jeopardizing its safety.
The result is an efficient, safe and robust hybrid system in which
integration of control by the operator and the automatic system is done
transparently and in real time.
Recent attempts of building teleoperated master-slave arm manipulator systems revealed serious difficulties that seem to go beyond the better understood issues of control, sufficiency of input information, and data processing. Namely, a human operator seems to have difficulty interpreting input information (coming, e.g., directly via the visual tract or from fixed or moving TV monitors at the scene), and consequently doing teleoperation decision making. The problem becomes even more pronounced when the slave arm has to operate in a complex environment where every point of the arm body is subject to potential collision. The results of experimental tests with human subjects presented in this paper trace the source of the difficulty to the limitations of human abilities for space orientation and interpretation of geometrical data. The suggested solution capitalizes on the recent developments in sensor-based motion planning for whole-sensitive arm manipulators. The resulting real-time hybrid system would combine the human operator's global motion decisions with the machine intelligence responsible for local planning and collision avoidance.
The problem of robot motion planning in an environment with
obstacles can often be reduced to the study of connectivity of
the robot's free configuration space. In turn, space
connectivity can be analyzed via the corresponding
connectivity graph For two-degrees-of-freedom robots, the free
configuration space presents a two-dimensional (2D)
surface -- a compact subspace of a 2D orientable compact
manifold. This paper addresses the following abstract problem:
given a compact 2D surface bounded by simple closed curves and
lying in an orientable 2D manifold (a sphere, a torus, etc) and
given two points in the subspace, suggest a systematic way of
defining the connectivity graph in the subspace, based on its
topological properties. The use of space topology results in
powerful, from the robotics standpoint, provable algorithms
capable of on-line motion planning in an environment with
unknown obstacles of arbitrary shapes. This makes the method
distinct from other techniques, which require complete
information, algebraic representation of space geometry, and
off-line computation.
We are considering the following problem that appears in
robotics. A number of point robots live in a common planar work
space. Each is attached by a flexible cable of finite length to
a point on the boundary of this work space. Each robot has a
target point on the work space it must reach. As the robots
move, the cables are dragged along into the work space. The
cables remain taut at all times but may bend around other
robots. When all robots are at their targets, their cables may
be bent around other robots. The more robots a cable is bent
around, the more entangled it is. The objective is to find a
configuration of the cables which will minimize the mutual
entanglement of the cables. This problem is shown to reduce to
the analysis of a nearly complete special graph whose nodes are the
robots' start and target positions. An unusual characteristic
of this graph problem is that no path --- where a path is the
set of graph edges representing the corresponding cable --- can
intersect another path. This consideration leads to some
interesting geometric analysis. An algorithm is suggested which
uses a search method with pruning to find a nonoverlapping set
of paths in the graph which is minimal according to a chosen
criterion.
Given two points in the plane, each with the prescribed direction of
motion, the question being asked is to find the shortest smooth path
of bounded curvature that joins them. The classical result by
L. Dubins (1957 ) that is commonly used gives a sufficient set of
paths which is guaranteed to contain the shortest path; the latter
is then found by explicitly calculating every path in the set. In
this paper we show that in the case when the distance between the
two points is above some minimum, the solution sought can be found
via a simple classification scheme. Besides computational savings
(essential, for example, in real-time motion planning), this result
sheds light on the nature of factors affecting the length of paths
in the Dubins's problem.