Decentralized Estimation and Control of Multi-Agent Systems
We are pursuing a framework for systematic design of emergent
behaviors in sensing and communication networks of mobile agents. The
problem is to design a control law to run on each agent, based on
sensor and communication input, so that the desired collective
behavior emerges. Example tasks include sensor coverage, environmental
monitoring, formation
control, multi-agent pursuer-evader, and other types of
self-organization. The key constraints are that each agent may have
significant dynamics and limited sensing, computation, motion, and
communication capabilities. The behavior of the system should
improve or degrade gracefully as agents are added or deleted; in other
words, the approach should be scalable, robust, and require no central
controller.
Our approach requires each agent to simultaneously (1) estimate
properties of the global behavior of the system and (2) use those
estimates in a motion control law. This suggests a systematic
approach of separately designing the estimator and controller, and
then ensuring that the coupled system retains desired performance
properties.
K. M. Lynch, I. B. Schwartz, P. Yang, and R. A. Freeman.
Decentralized environmental modeling by mobile sensor networks.
IEEE Transactions on Robotics, 24(3):710-724, June 2008.
pdf (664 K)
P. Yang, R. A. Freeman, and K. M. Lynch.
Distributed cooperative active sensing using consensus filters.
IEEE International Conference on Robotics and Automation, 2007.
pdf
P. Yang, R. A. Freeman, and K. M. Lynch.
Multi-agent coordination by decentralized estimation and control.
In revision for IEEE Transactions on Automatic Control, 2007.
pdf
R. A. Freeman, P. Yang, and K. M. Lynch.
Stability and convergence properties of dynamic average consensus estimators.
IEEE Conference on Decision and Control, 2006.
pdf
P. Yang, R. A. Freeman, and K. M. Lynch.
Optimal information propagation in sensor networks.
2006 IEEE International Conference on Robotics and Automation.
pdf
R. A. Freeman, P. Yang, and K. M. Lynch.
Distributed estimation and control of swarm formation statistics.
2006 American Control Conference.
pdf
Underwater Localization
We are developing novel ribbon-fin propulsors for highly-maneuverable
vehicles operating in cluttered environments. To support close-range
sensing in cluttered environments, we are developing an active
electrosensor. This sensor creates an electric field and uses one or
more detectors to detect voltage perturbations in the electric field. These
perturbations are then interpreted to either find a target in the
environment or to localize the vehicle in a known environment.
In the figure at right, the two squares are electrodes that create an
electric field, the diamond is the voltage detector, and the circle is
a perfectly conductive object in water. With Gaussian noise added to
the sensor reading, a single sensor reading allows localization of the
object with >68% likelihood in the regions labeled white and >95%
likelihood in the white + lightest gray regions. Remaining ambiguity
can be eliminated by multiple sensor readings at different locations.
J. Solberg, K. M. Lynch, and M. MacIver.
Active electrolocation for underwater target localization.
International Journal of Robotics Research, submitted.
pdf (4.3 MB)
J. Solberg, K. M. Lynch, and M. MacIver.
Robotic electrolocation: Active underwater target localization with
electric fields.
2007 IEEE International Conference on Robotics and Automation.
pdf
Manipulation by Pushing
For planar manipulation problems, pushing provides an option for
robots lacking the size, strength, or dexterity to grasp and carry an
object. For example, it is usually easier to push a couch into
position than to grasp and lift it. Pushing also provides a mechanism
for manipulating multiple objects simultaneously. Our work on robotic pushing
focuses on three aspects:
Mechanics. How does an object move when it is pushed?
If a mobile robot is pushing an object with a plow, what
directions can the robot move and have the object remain fixed
against the plow? (This is called a stable push.)
These questions depend on the contact geometry
and friction between the pusher and the object, and the mechanics
of sliding friction between the object and the support surface.
Controllability. Can the object be pushed from the start
configuration to the goal configuration? What if there are obstacles?
Conditions for local and global controllability of an object by pushing
can be derived in terms of the geometry of the part, the location of
its center of friction, and the geometry and friction coefficient of the
pusher/object contact.
Planning. How do we plan stable pushing motions to move an
object from a start configuration to a goal configuration, possibly
among obstacles? The stable pushing directions amount to a set of
nonholonomic inequality constraints, and the planning problem is an example
of nonholonomic motion planning.
J. D. Bernheisel and K. M. Lynch.
Stable transport of assemblies by pushing.
IEEE Transactions on Robotics, 22(4):740-750, August 2006.
pdf (840 K)
J. D. Bernheisel and K. M. Lynch.
Stable pushing of assemblies.
2005 IEEE International Conference on Robotics and Automation,
Barcelona, Spain, April 2005.
pdf (740 K)
J. D. Bernheisel and K. M. Lynch.
Stable transport of assemblies: Pushing stacked parts.
IEEE Transactions on Automation Science and Engineering,
v. 1, n. 2, pp. 163-8, October 2004.
pdf (556 K)
J. D. Bernheisel and K. M. Lynch.
Stable transport of assemblies: Pushing stacked parts.
IEEE/RSJ International Conference on Intelligent Robots and Systems
2003, Las Vegas, NV, 2003.
abstract,
pdf
K. M. Lynch.
Locally controllable manipulation by stable pushing.
IEEE Transactions on Robotics and Automation,
15(2):318-327, April 1999.
abstract,
postscript (1322 K),
pdf (281 K)
K. M. Lynch.
Locally controllable polygons by stable pushing.
1997 IEEE International Conference on Robotics and Automation,
pp. 1442-1447, Albuquerque, NM, April 1997.
abstract,
postscript (732 K),
pdf (115 K)
K. M. Lynch and M. T. Mason.
Stable pushing: Mechanics, controllability, and planning.
International Journal of Robotics Research, 15(6): 533-556,
December 1996.
abstract, postscript (2214 K), pdf (3.2 M)
(An earlier version appeared in the First Workshop on the Algorithmic
Foundations of Robotics, A. K. Peters, Boston, 1995.)
K. M. Lynch and M. T. Mason.
Controllability of pushing.
1995 IEEE International Conference on Robotics and Automation,
pp. 112-119, Nagoya, Japan, May 1995.
abstract,
postscript (593 K),
pdf (209 K)
K. M. Lynch.
Planning pushing paths.
International Conference on Advanced Mechatronics,
pp. 451-456, Tokyo, Japan, August 1993.
K. M. Lynch.
Estimating the friction parameters of pushed objects.
1993 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pp. 186-193, Yokohama, Japan, July 1993.
abstract,
postscript (435 K),
pdf (229 K)
K. M. Lynch, H. Maekawa, and K. Tanie.
Manipulation and active sensing by pushing using tactile feedback.
1992 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pp. 416-421, Raleigh, NC, July 1992.
abstract,
postscript (346 K),
pdf (105 K)
K. M. Lynch.
The mechanics of fine manipulation by pushing.
1992 IEEE International Conference on Robotics and Automation,
pp. 2269-2276, Nice, France, May 1992.
abstract,
postscript (300 K),
pdf (97 K)
Dynamic Manipulation
By not grasping, a simple robot with few degrees-of-freedom can
control an object with more degrees-of-freedom by exploiting dynamic
effects. These extra
degrees-of-freedom come from manipulation phases such as controlled
slipping and rolling. In contrast, a robot that carries an object with
a firm grasp requires as many degrees-of-freedom as those of the
object it wishes to control.
Our work on dynamic manipulation has been on motion planning, feedback
control, and implementation of robotic tasks such as dynamically
snatching an object from a table (using inertial forces to keep the
object fixed to the robot), rolling an object on the surface of the
manipulator, and throwing and catching. Nonlinear optimization is
used to plan robot trajectories that achieve the desired motion via
coupling forces through the nonprehensile (graspless) contact.
See our dynamic manipulation testbed
Flatland. References to relevant papers are given below. See our
video gallery
of dynamic tasks.
K. M. Lynch and T. D. Murphey. Control of nonprehensile manipulation.
In Control Problems in Robotics and Automation, A. Bicchi
and H. Christensen, eds. Springer-Verlag.
html,
pdf
P. Choudhury and K. M. Lynch.
Rolling manipulation with a single control.
International Journal of Robotics Research,
21(5-6):475-487, May-June 2002.
K. M. Lynch, M. Northrop, and P. Pan.
Stable limit sets in a dynamic parts feeder.
IEEE Transactions on Robotics and Automation, 18(4):608-615, Augsut 2002.
html,
pdf
K. M. Lynch, M. Northrop, and P. Pan.
Stable limit set behavior in a dynamic parts feeder.
2001 IEEE/RSJ International Conference on Intelligent Robots and Systems,
Maui, Hawaii, November 2001.
abstract,
pdf (113 K)
K. M. Lynch and C. K. Black.
Recurrence, controllability and stabilization of juggling.
IEEE Transactions on Robotics and Automation, 17(2):113-124,
April 2001.
abstract,
pdf (284 K)
P. Choudhury and K. M. Lynch.
Rolling manipulation with a single control.
Conference on Control Applications,
Mexico City, Mexico, September 2001.
abstract,
postscript (3138 K),
pdf (259 K)
P. Choudhury and K. M. Lynch.
Controllability of single input rolling manipulation.
IEEE International Conference on Robotics and Automation 2000
San Francisco, CA, April 2000.
abstract,
postscript (672 K),
pdf (209 K)
K. M. Lynch and C. K. Black.
Control of underactuated manipulation by real-time nonlinear optimization.
9th International Symposium on Robotics Research, Snowbird,
UT, October 1999.
abstract,
postscript (2800 K)
C. K. Black and K. M. Lynch.
Planning and control for planar batting and hopping.
36th Annual Allerton Conference on Communication, Control,
and Computing, September 1998.
abstract,
postscript (3467 K),
pdf (225 K)
K. M. Lynch, N. Shiroma, H. Arai, and K. Tanie.
The roles of shape and motion in dynamic manipulation:
The butterfly example.
1998 IEEE International Conference on Robotics
and Automation, pp. 927-932, Leuven, Belgium, May 1998.
abstract,
postscript (785 K),
pdf (141 K)
K. M. Lynch.
Issues in nonprehensile manipulation.
1998 Workshop on the Algorithmic Foundations of Robotics.
abstract,
postscript (835 K),
pdf (285 K)
K. M. Lynch and M. T. Mason.
Dynamic nonprehensile manipulation: Controllability, planning,
and experiments.
International Journal of Robotics Research,
18(1):64-92, January 1999.
abstract,
postscript (2584 K),
pdf (519 K)
K. M. Lynch and M. T. Mason.
Dynamic manipulation with a one joint robot.
1997 IEEE International Conference on Robotics and
Automation, pp. 359-366, Albuquerque, NM, April 1997.
abstract,
postscript (837 K),
pdf (131 K)
K. M. Lynch and M. T. Mason.
Dynamic underactuated nonprehensile manipulation.
1996 IEEE/RSJ International Conference on Intelligent Robots and
Systems pp. 889-896, Osaka, Japan, November 1996.
abstract,
postscript (1695 K),
pdf (159 K)
M. T. Mason and K. M. Lynch.
Dynamic robotic manipulation: Progress and plans.
Eighth Yale Workshop on Adaptive and Learning Systems, New Haven,
CT, June 1994.
M. T. Mason and K. M. Lynch.
Throwing a club: Early results.
Sixth International Symposium on Robotics Research, Hidden Valley,
PA, October 1993.
M. T. Mason and K. M. Lynch.
Dynamic manipulation.
1993 IEEE/RSJ International Conference on Intelligent Robots and
Systems, pp. 152-159, Yokohama, Japan, July 1993.
Parts Feeding
Some industrial parts feeders, such as bowl feeders and the Sony APOS
system, utilize vibratory dynamics to help orient parts. For instance,
a vibrating pallet of holes can be used to capture parts in a
desired orientation by using an appropriate shaking motion.
Our work on parts feeding has focused on feeding parts on a conveyor
belt using a system that is very simple, yet still programmable to
allow feeding different types of parts; designing agitation
(throwing and catching or vibration) to induce desired equilibria or
generalized equilibria (limit cycles) in a single part
or multiple parts (e.g., throwing together an assembly); and simultaneous manipulation
of one or more parts by creating controlled frictional force fields on
a 6-DOF vibrating plate (see video at right and the project page
here).
References to relevant papers are given below. More videos can be found
here.
T. Vose, P. Umbanhowar, and K. M. Lynch.
Vibration-induced frictional force fields on a rigid plate.
IEEE International Conference on Robotics and Automation, 2007.
pdf(Best Automation
Paper Award)
P. Umbanhowar and K. M. Lynch.
Optimal vibratory stick-slip transport.
To appear in IEEE Transactions on Automation Science and Engineeering (submitted 2006).
pdf
T. D. Murphey, J. Bernheisel, D. Choi, and K. M. Lynch.
An example of parts handling and self-assembly using stable limit sets.
2005 IEEE/RSJ International Conference on Intelligent Robots and Systems,
Edmonton, Canada, August 2005.
pdf (454 K)
T. D. Murphey, D. Choi, J. Bernheisel, and K. M. Lynch.
Experiments in the use of stable limit sets for parts handling.
2004 International Conference on MEMS, NANO, and Smart Systems (ICMENS),
Banff, Alberta, Canada, August 2004.
abstract,
pdf
K. M. Lynch.
Inexpensive conveyor-based parts feeding.
Assembly Automation Journal, 19(3):209-215, 1999.
abstract,
postscript (601 K),
pdf (64 K)
K. M. Lynch.
Toppling manipulation.
1999 IEEE International Conference on Robotics and Automation,
Detroit, MI, April 1999.
abstract,
postscript (624 K),
pdf (81 K)
S. Akella, W. Huang, K. M. Lynch, and M. T. Mason.
Parts feeding on a conveyor with a one joint robot.
Algorithmica, 26(3):313-344, March-April 2000.
abstract, postscript
(2800 K), pdf (193 K),
and final pdf version in Algorithmica
(440 K)
S. Akella, W. Huang, K. M. Lynch, and M. T. Mason.
Sensorless parts orienting with a one-joint manipulator.
1997 IEEE International Conference on Robotics and Automation,
Albuquerque, NM, April 1997.
abstract,
postscript (2900 K),
pdf (115 K)
S. Akella, W. Huang, K. M. Lynch, and M. T. Mason.
Sensorless parts feeding with a one joint robot.
Robotic Motion and Manipulation, J.-P. Laumond and M. Overmars,
eds., A. K. Peters, Boston, MA, 1997.
abstract,
postscript (2269 K),
pdf (129 K)
S. Akella, W. H. Huang, K. M. Lynch, and M. T. Mason.
From robotic juggling to robotic parts feeding.
1996 Yale Workshop on Adaptive and Learning Systems, New Haven, CT.
abstract,
postscript (2364 K),
pdf (134 K)
S. Akella, W. Huang, K. M. Lynch, and M. T. Mason.
Planar manipulation on a conveyor with a one joint robot.
1995 International Symposium on Robotics Research, pp. 265-276,
Munich, Germany, October 1995.
abstract,
postscript (1691 K),
pdf (127 K)
Underactuated Robots
An underactuated robot is a robot with fewer actuators than
degrees-of-freedom. Our work on underactuated robots includes motion
planning for underactuated second-order mechanical systems,
controllability analysis, motion planning, and feedback control of a
three joint manipulator with only two actuators, and a controllability
analysis of a planar body (such as a hovercraft which glides on water
with zero friction) with unilateral thrusters.
See the video
of a 3 DOF robot with a passive (unactuated) joint navigating through an
obstacle field.
J. E. Colgate and K. M. Lynch.
Mechanics and control of swimming: A review.
IEEE Journal of Oceanic Engineering, 29(3):660-673, July 2004.
abstract,
pdf
S. Iannitti and K. M. Lynch.
Minimum control switch motions for the snakeboard: A case study
in kinematically controllable underactuated systems.
IEEE Transactions on Robotics, 20(6):994-1006, Dec. 2004.
pdf (912 K)
S. Iannitti and K. M. Lynch.
Exact minimum control switch motion planning for the snakeboard.
IEEE/RSJ International Conference on Intelligent Robots and
Systems 2003, Las Vegas, NV, 2003.
abstract,
pdf
P. Choudhury and K. M. Lynch.
Trajectory planning for kinematically controllable
underactuated mechanical systems.
2002 Workshop on the Algorithmic Foundations of Robotics,
Nice, France, 2002.
abstract,
pdf
F. Bullo, A. D. Lewis, and K. M. Lynch.
Controllable kinematic reductions for mechanical systems: Concepts,
computational tools, and examples.
2002 International Symposium on Mathematical Theory of Networks and
Systems, August 2002.
abstract,
pdf (216 K)
K. M. Lynch.
Optimal control of the thrusted skate.
Automatica, 39(1):173-176, January 2003.
abstract,
pdf
F. Bullo and K. M. Lynch.
Kinematic controllability for decoupled trajectory planning in
underactuated mechanical systems.
IEEE Transactions on Robotics and Automation, 17(4):402-412, August 2001.
abstract,
pdf (248 K)
F. Bullo and K. M. Lynch.
Kinematic controllability and decoupled trajectory planning for
underactuated mechanical systems.
IEEE International Conference on Robotics and Automation 2001,
pp. 3300-3307, Seoul,
Korea, May 2001.
abstract,
postscript (228 K),
pdf (233 K)
K. M. Lynch, N. Shiroma, H. Arai, and K. Tanie.
Collision-free trajectory planning for a 3-DOF robot with a passive joint.
International Journal of Robotics Research, 19(12):1171-1184, December 2000.
abstract,
postscript (1100 K),
pdf (264 K)
K. M. Lynch.
Controllability of a planar body with unilateral thrusters.
IEEE Transactions on Automatic Control, 44(6):1206-1211, June 1999.
abstract,
postscript (520 K),
pdf (188 K)
K. M. Lynch, N. Shiroma, H. Arai, and K. Tanie.
Motion planning for a 3-DOF robot with a passive joint.
1998 IEEE International Conference on Robotics
and Automation, pp. 1958-1963, Leuven, Belgium, May 1998.
abstract,
postscript (706 K),
pdf (161 K)
Collaborative Manipulation and Materials Handling
Our work on assisted materials handling has focused on the idea that
it is easier for a human to manipulate a load constrained to move
along a (workless) frictionless guide than to manipulate the load
freely. We are interested in designing guides which make the task
as easy (or ergonomic) as possible for the human.
P. Pan, K. M. Lynch, M. A. Peshkin, and J. E. Colgate.
Human interaction with passive assistive robots.
2005 International Conference on Rehabilitation Robotics,
Chicago, IL, June 2005.
pdf (404 K)
P. Pan, M. A. Peshkin, J. E. Colgate, and K. M. Lynch.
Static single-arm force generation with kinematic constraints.
Journal of Neurophysiology, 93:2752-2765, May 2005.
pdf (928 K)
P. Pan, K. M. Lynch, M. A. Peshkin, and J. E. Colgate.
Static single-arm force generation with kinematic constraints.
IEEE International Conference on Robotics and Automation 2004,
New Orleans, LA, 2004.
abstract,
pdf
K. M. Lynch, C. Liu, A. Sorensen, M. Peshkin, J. E. Colgate, T. Tickel,
D. Hannon, and K. Shiels. Motion guides for assisted manipulation.
International Journal of Robotics Research, 21(1):27-43, January 2002.
abstract,
pdf
T. Tickel, D. Hannon, K. M. Lynch, M. A. Peshkin, and J. E. Colgate.
Kinematic constraints for assisted single-arm manipulation.
IEEE International Conference on Robotics and Automation 2002.
abstract,
pdf (132 K)
A. Sorensen, C. Liu, S. M. Kim, K. M. Lynch, and M. A. Peshkin.
Experiments in ergonomic robot-guided manipulation.
IEEE/RSJ International Conference on Intelligent Robots and
Systems 2000.
abstract,
postscript (4031 K),
pdf (338 K)
K. M. Lynch and C. Liu.
Designing motion guides for ergonomic collaborative manipulation.
IEEE International Conference on Robotics and Automation 2000.
abstract,
postscript (964 K),
pdf (239 K)
Haptics
Work in haptics includes displaying realistic dynamic virtual environments
to the sense of touch,
particularly systems with hard, smooth constraints. Examples include
virtual linkages and other virtual devices subject to holonomic and
nonholonomic constraints.
E. L. Faulring, K. M. Lynch, J. E. Colgate, and M. A. Peshkin.
Haptic display of constrained dynamic systems via admittance displays.
IEEE Transactions on Robotics, 23(1):101-111, Feb. 2007.
pdf (1600 K)
E. L. Faulring, K. M. Lynch, J. E. Colgate, and M. A. Peshkin.
Haptic interaction with constrained dynamic systems.
2005 IEEE International Conference on Robotics and Automation,
Barcelona, Spain, April 2005.
pdf (852 K)
T. Worsnopp, J. E. Colgate, M. A. Peshkin, and K. M. Lynch.
Controlling the apparent inertia of passive human-interactive robots.
IEEE International Conference on Robotics and Automation 2004,
New Orleans, LA, 2004.
pdf
V. Chib, J. L. Patton, K. M. Lynch, and F. A. Mussa-Ivaldi.
Haptic discrimination of perturbing fields and object boundaries.
International Symposium on Haptic Interfaces for Virtual Environment
and Teleoperator Systems,
Chicago, IL, March 2004.
pdf
Friction
Systems with Coulomb friction may have multiple solutions
(ambiguity) or no solutions (inconsistency) to their equations of
motion. These properties of rigid-body mechanics with Coulomb
friction are well known. However, a careful analysis of Coulomb
friction in robotic manipulation reveals other unexpected results:
for instance, the perfectly rough surface of classical
mechanics is not equivalent to infinite Coulomb friction,
a common misidentification in textbooks.
K. M. Lynch and M. T. Mason.
Pulling by pushing, slip with infinite friction, and perfectly rough surfaces.
1993 IEEE International Conference on Robotics and Automation, v. 1,
pp. 745-751, Atlanta, GA, May 1993.
abstract,
postscript (231 K),
pdf (86 K)
(A more complete version of this paper appears in the International Journal
of Robotics Research, v. 14, n. 2, pp. 174-183, April 1995.)
Sensing for Manipulation
K. M. Lynch and M. A. Peshkin.
Linear and rotational sensors.
In The Mechatronics Handbook, R. Bishop, ed., CRC Press 2002.
pdf
K. M. Lynch.
Determining the orientation of a painted sphere from a single image:
a graph coloring problem.
pdf (48 K)
Ph.D. Thesis
K. M. Lynch.
Nonprehensile robotic manipulation: Controllability and planning.
Ph.D. thesis, March 1996. Available as CMU-RI-TR-96-05.
abstract, postscript
summary (387 K, 13 pages), postscript
(8312 K, 210 pages), pdf (2000 K)
(For proper page layout, the thesis should be printed double-sided.)