View Full Version : NSF Workshop on Geometric Uncertainty in Motion Planning

H.j. Woltring, Fax/tel +31.40.413 744
08-19-1992, 10:21 AM
Further to Mr Harvey's (Salt Lake City) recent postings on collision
detection and avoidance in Xray systems, the following posting from
Usenet's comp.robotics newsgroup seems relevant. The full ftp report
contains the email addresses of all organisers and participants.



Article 2682 in comp.robotics:
From: goldberg@twister.usc.edu (Kenneth Goldberg)
Subject: Recent NSF Workshop
Date: 18 Aug 1992 13:18:22 -0700
Organization: University of Southern California, Los Angeles, CA
Sender: goldberg@twister.usc.edu (Kenneth Goldberg)
Distribution: world

Anyone interested in current research issues, especially with
regard to factory applications, is invited to read the following.
An expanded version is also available via ftp.

Summary Report and Bibliography
Workshop on Geometric Uncertainty in Motion Planning
Catalina Island, CA. June 15-17, 1992
(Sponsored in part by National Science Foundation grant IRI-9208161)

Goldberg, Ken, USC
Mason, Matt, CMU
Requicha, Ari, USC

NSF Coordinator:
Howard Moraff, NSF IRIS Div.

Agraval, Amit, USC
Brost, Randy, Sandia
Cameron, Alec, Philips
Canny, John, UC Berkeley
Carlisle, Brian, Adept Technology Inc.
Erdmann, Mike, CMU
Gottschlich, Susan, RPI
Jennings, Jim, Cornell
Latombe, Jean-Claude, Stanford
Lozano-Perez, Tomas, MIT
Lumelsky, Vladimir, UWisc
Mishra, Bud, NYU
Peshkin, Mike, Northwestern
Popplestone, Robin, UMass
Rao, Anil, USC
Rimon, Elon, Caltech
Sanderson, Art, RPI
Strip, David, Sandia
Tilove, Bob, GM
Yap, Chee, NYU


In robotics, the problem of planning *collision-free* motions has
received considerable attention in the past decade; results have now
been collected into a textbook (Latombe, 1991). For manufacturing
however, robots must bring parts into contact for grasping, packing
and assembly. As noted by Latombe, the problem of planning reliable
"collisions" is complicated by geometric uncertainty: things differ
from their ideal shapes, and they are not where they're supposed to
be. Since human programmers have difficulty keeping track of all
possible conditions, automated planning methods are needed so that
robots can become more reliable and practical for industry.

There is a formal approach to planning that addresses uncertainties
arising from: sensor noise, control error, and inaccurate models of
the environment. This approach, based on the geometry of
configuration space, is sometimes called *fine motion planning* due to
a seminal paper by Lozano-Perez, Mason, and Taylor (1984).

With the support of several NSF programs (particularly Robotics and
Machine Intelligence and Dynamic Systems and Control) the Catalina
workshop brought together a group of researchers and
representatives from industry to review past work, assess its impact
on industry, and recommend priorities for future research.

Summary of Observations and Recommendations

This section briefly summarizes the observations and recommendations
made during the workshop. Following is a detailed summary of
individual presentations and a list of relevant references.

While sensing has traditionally been used to reduce geometric
uncertainty, mechanical compliance (intentionally sliding parts
against each other) is a useful alternative. Although compliance is
widely used in manufacturing, for example in vibratory bowl feeders,
computational algorithms for applying these techniques are only
beginning to emerge. One fundamental question is how to discretize
the infinite set of robot commands into a manageable set of
equivalence classes. Another question is how to incorporate sensor
queries with robot commands to decide when parts have been
successfully arranged.

Planning for repetitive assembly occurs off-line. The LMT paper and
subsequent publications provide a useful computational framework based
on backchaining from a goal configuration. In its most general form,
motion planning with uncertainty is computationally intractable.
However in non-pathological cases, existing algorithms find robust
plans in a few minutes. Further speedups may be gained with
randomized or approximate algorithms.

It is easier to plan with less information. This follows from the
fact that there are fewer alternatives to consider during planning.
Thus automated planning may be most efficient for robot systems with
few degrees of freedom and simple sensors. Also, detailed geometric
analysis can be avoided during the non-contact phases of assembly.

Planning should not be restricted to robot commands. In a structured
environment such as a factory, the environment itself can be viewed as
a variable, ie, the design of sensors, feeders, and fixtures can be
specified based on part geometry. Furthermore, we can in principle
modify part geometry and tolerances to facilitate manufacture.
Although humans have designed workcells for decades, automated
planning algorithms could greatly reduce set-up times and increase
performance efficiency for competitive manufacturing.

Industrial users require reliable systems. Although the primary
motivation behind autonomous planning is to increase robot
reliability, the algorithms must be rigorously tested with physical
experiments. New planning software should be made accessible to the
manufacturing community. This requires code that is compatible with
existing CAD systems and well-designed user interfaces. A PhD should
not be required to reprogram robots on the factory floor.

Measures of progress are needed in this area. Latombe's text is a
good start. To develop the scientific base for automated manufacture,
it will be important to identify and solve well-formed research
problems that explicitly address geometric uncertainty.

Summary of Presentations:


To get and print a copy of the full (19 pp.) report on
UNIX systems:

% ftp
Connected to palenque.usc.edu.
220 palenque.usc.edu FTP server (SunOS 4.1) ready.
Name (palenque.usc.edu:saavedra): anonymous
331 Guest login ok, send ident as password.
230 Guest login ok, access restrictions apply.
ftp> cd pub
200 PORT command successful.
ftp> get USC_IRIS_297.ps.Z
ftp> quit
% uncompress USC_IRIS_297.ps.Z
% lpr USC_IRIS_297.ps

Or, for a hardcopy contact:

Delsa Castelo
IRIS Group, 204 Powell Hall
University Park, University of Southern California
Los Angeles, CA 90089-0273
End of article 2682 (of 2682)--what next? [npq]