IEEE
TRANSACTIONS
ON
SYSTEMS,
MAN,
AND
CYBERNETICS,
VOL.
SMC-1
1,
NO.
10,
OCTOBER
1981
Automatic
Planning
of
Manipulator
Transfer
Movements
TOMAS
LOZANO-PEREZ
Abstract-The
class
of
problems
that
involve
finding
where
to
place
or
how
to
move
a
solid
object
in
the
presence
of
obstacles
is
discussed.
The
solution
to
this
class
of
problems
is
essential
to
the
automatic
planning
of
manipulator
transfer
movements,
i.e.,
the
motions
to
grasp
a
part
and
place
it
at
some
destination.
For
example,
planning
transfer
movements
requires
the
ability
to
plan
paths
for
the
manipulator
that
avoid
collisions
with
objects
in
the
workspace
and
the
ability
to
choose
safe
grasp
points
on
objects.
The
approach
to
these
problems
described
here
is
based
on
a
method
of
computing
an
explicit
representation
of
the
manipulator
config-
urations
that
would
bring
about
a
collision.
I.
INTRODUCTION
A
N
IMPORTANT
goal
of
research
on
programming
languages
for
computer-controlled
manipulators
is
a
language
in
which
assembly
operations
can
be
described
concisely.
Two
major
approaches
to
manipulator
program-
ming
have
been
identified
[34].
1)
Explicit
programming-in
which
the
user
specifies
all
the
manipulator
motions
needed
to
accomplish
a
task.
2)
Model-based
programming
in
which
the
user
speci-
fies
geometric
models
of
parts
and
a
description
of
the
task
in
terms
of
these
models.
The
detailed
manipulator
motions
are
derived
by
the
assembly
system
from
these
specifications.
This
paper
presents
algorithms
for
some
of
the
central
geometric
problems
that
arise
in
the
model-based
approach
to
manipulator
programming.
In
particular
it
deals
with
the
class
of
problems
that
involve
finding
where
to
place
or
how
to
move
a
solid
object
in
the
presence
of
obstacles.
The
solution
to
this
class
of
problems
is
essential
to
the
automatic
planning
of
manipulator
transfer
movements,
i.e.,
the
motions
to
grasp
a
part
and
place
it
at
some
destination.
For
example,
planning
transfer
movements
requires
the
ability
to
plan
paths
for
the
manipulator
that
avoid
collisions
with
objects
in
the
workspace
and
the
ability
to
choose
safe
grasp
points
on
objects.
The
ap-
proach
to
these
problems
described
here
is
based
on
a
method
of
computing
an
explicit
representation
of
the
manipulator
configurations
that
would
bring
about
a
colli-
sion
[27].
Manuscript
received
March
20,
1981;
revised
July
3,
1981.
This
work
was
supported
by
the
U.S.
Office
of
Naval
Research
under
Contract
N00014-77-C-0389.
The
author
is
with
the
Artificial
Intelligence
Laboratory,
Massachusetts
Institute
of
Technology,
545
Technology
Square,
Cambridge,
MA
02139.
Several
model-based
manipulator
systems
have
been
de-
scribed
in
the
recent
literature:
AL
[10],
[46];
Autopass
[24],
[28];
[39],
LAMA
[25],
[26];
and
RAPT
[38],
[39],
[40].
These
are
experimental
systems
currently
under
develop-
ment.'
Work
on
the
model-based
aspects
of
AL
has
focused
on
techniques
for
making
coding
decisions
in
manipulator
programs.
The
decisions
are
made
among
a
fixed
set
of
strategies
so
as
to
minimize
estimated
execution
times
and
to
bring
estimates
on
the
accuracy
of
part
positions
within
specified
bounds.
A
central
technical
issue
in
this
approach
is
deriving
the
accuracy
estimates
from
geometric
relation-
ships
and
local
accuracy
information.
RAPT
has
focused
on
the
specification
of
manipulator
programs
by
specifying
the
desired
symbolic
spatial
relationships
among
objects.
These
relations
are
then
translated
into
algebraic
con-
straints
on
the
position
parameters
of
the
objects,
which
can
be
solved
by
symbolic
manipulation.
These
algebraic
solution
techniques
are
also
used
to
complete
the
specifica-
tion
of
partially
specified
actions
so
as
to
achieve
the
desired
relationships.
Implementation
work
on
LAMA
and
Autopass
has
focused
on
techniques
for
planning
collision-
free
motions,
e.g.,
grasping
and
parts
transfer
motions,
using
polyhedral
object
models.
The
techniques
reported
in
this
paper
are
extensions
of
the
Autopass
obstacle
avoid-
ance
algorithm
and
LAMA's
grasping
strategies.
A
number
of
important
problems
relevant
to
model-
based
manipulator
programming
have
been
addressed
in-
dependently
of
any
manipulator
system,
for
example,
the
problem
of
specifying
compliant
motion
strategies
based
on
geometric
and
kinematic
models
of
a
task
[30],
the
selection
of
grasping
positions
[5],
[31],
[35],
[51],
and
the
problem
of
collision
detection
and
collision
avoidance
among
obstacles
[3],
[7],
[12],
[33],
[47].
The
algorithms
discussed
in
this
paper
are
based
on
previous
work
on
obstacle
avoidance
algorithms.
In
partic-
ular,
[48]
and
[49]
first
formulated
the
obstacle
avoidance
problem
in
terms
of
an
obstacle
transformation
which
allows
treating
the
moving
object
as
a
point.
A
similar
transformation
was
also
used
in
[1],
[2],
[4],
[45]
for
the
template
layout
problem;
related
applications
are
also
dis-
cussed
in
[11]
and
[16].
Generalizations
of
these
obstacle
transformation
techniques
and
a
review
of
related
work
'The
AL
language,
as
originally
described,
includes
explicit
as
well
as
model-based
programming
capabilities.
The
former
are
currently
availa-
ble,
while
the
latter
are
still
in
the
experimental
stage.
0018-9472/81/1000-0681$00.75
©1981
IEEE
681
