Distributed Robotics Laboratory
Directors:
William M. Spears and
Diana F. Spears.
Computer Science Department
Engineering Building
Laramie, WY 82071
{wspears,dspears} arobase cs.uwyo.edu
Phone: 307.766.5429 or 307.766.5485
Team Members
Faculty: William M. Spears (CS),
Diana F. Spears (CS), David R. Thayer (Physics), Jerry Hamann (ECE).
Current Students: Suranga Hettiarachchi,
Dimitri Zarzhitsky, Caleb Speiser, Paul Maxim, Christer Karlsson,
Derek Green, and Anton Rebgun
New Maxelbot Project
We are constructing new robots to aid in our swarm robotics research.
These robots use a novel trilateration framework to localize each other,
without the need for beacons, GPS, environmental knowledge, cameras, etc.
Information is provided at the following web page.
Maxelbot Project
Motivation
In response to growing concerns that single, monolithic robotic vehicles
are expensive, brittle, and vulnerable, there has been a trend toward
the development of distributed networks of small, inexpensive vehicles.
The capability of these networks to dynamically monitor and sense
environmental conditions, while maintaining cost-effectiveness, robustness,
and flexibility, is considered to be among their greatest assets.
Dynamic sensor networks are critically needed for various tasks, such as
search and rescue, surveillance, perimeter defense, locating and mapping
chemical and biological hazards, virtual space telescopes, automated
assembly of micro-electromechanical systems,
and medical surgery (e.g., with nanobots). This research is designed
to address this need, with a focus on deploying robust swarms of mobile
ground-based sensing agents (robots). This distributed sensing network
will self-assemble, adapt as needed, collect sensing data, and fuse
the data into an aggregate global picture for situational assessment.
Artificial Physics / Physicomimetics
The core technology we are using to achieve these goals
is a novel approach referred to as ``artificial physics'' or
``physicomimetics''. With physicomimetics,
robotic agents perceive and react to artificial physics forces. By
synthesizing the appropriate virtual forces, various important task-driven
behaviors can be effectively achieved, such as lattice-shaped distributed
antennas, perimeter defense, and dynamic surveillance. Furthermore,
the systems self-organize, can self-repair, and are fault-tolerant.
The motivation for this approach is that any system designed using the
laws of physics is amenable to the full gamut of empirical, analytical,
and theoretical analysis tools used by physicists.
Videos of our Current Research
The leader has an obstacle avoidance module!
(Caleb Speiser, Suranga H., and Paul Maxim).
The leader is RC controlled. The followers are using a version of AP.
(Caleb Speiser, Suranga H., and Paul Maxim).
New Maxelbots! 3 Minute Outdoor Video (thanks to Tom Kunkel and Paul Maxim and Suranga Hettiarachchi).
New Maxelbots! The Rise of the Machine
(thanks to Tom Kunkel, Paul Maxim, Suranga Hettiarachchi and Derek Green).
New Maxelbots! 7 Minute Outdoor Video (thanks to Tom Kunkel and Paul Maxim and Suranga Hettiarachchi).
Artificial Physics at the Naval Research Laboratory! (thanks to Mitch Potter, Paul Wiegand, and Don Sofge).
TV documentary on our work (courtesy of Wyoming Signatures by UW TV)
TV Interview (courtesy of KTWO TV ABC Casper)
TV Interview (courtesy of KCWY TV NBC Casper)
Seven robots getting into formation (thanks to Rod Heil and Paul Hansen).
Seven robots getting into formation and moving towards a goal (thanks to Rod Heil and Paul Hansen).
Two of our small robots on Channel 5 (courtesy of
KWGN TV CBS Cheyenne)!
A video of a prototype outdoor robot, designed and built by Ben Palmer at UWYO.
Java Simulation Tools (by Adam Sciambi)
Our general 2D/3D simulation tool
Our specialized 2D simulation tool
Our perfect lattice tool
Some interesting formations
A short QuickTime movie.
Journal, Conference and Workshop Publications,
1999-current
2008
Maxim, P., S. Hettiarachchi, W. Spears, D. Spears, J. Hamann, T. Kunkel, and C. Speiser,
Trilateration Localization for Multi-Robot Teams. To appear in the Proceedings of ICINCO 2008.
The ability of robots to quickly and accurately localize their neighbors
is extremely important for robotic teams. Prior approaches typically rely
either on global information provided by GPS, beacons and landmarks, or on
complex local information provided by vision systems. In this paper we describe
our trilateration approach to multi-robot localization, which is fully
distributed, inexpensive, and scalable [15]. Our prior research [14] focused
on maintaining multi-robot formations indoors using trilateration. This paper
pushes the limits of our trilateration technology by testing formations of
robots in an outdoor setting at larger inter-robot distances and higher speeds.
2007
Spears, D., W. Kerr, and W. Spears,
Fluid-like Swarms with Predictable Macroscopic Behavior. To appear in the Lecture Notes in Computer Science, Volume 4324.
This paper is concerned with assuring the safety of a swarm of agents
(simulated robots). Such behavioral assurance is provided with the
physics method called "kinetic theory." Kinetic theory formulas
are used to predict the macroscopic behavior of a simulated swarm of
individually controlled agents. Kinetic theory is also the method for
controlling the agents. In particular, the agents behave like particles
in a moving gas.
The coverage task addressed here involves a dynamic search through a
bounded region, while avoiding multiple large obstacles, such as buildings.
In the case of limited sensors and communication, maintaining spatial
coverage -- especially after passing the obstacles -- is a challenging
problem. Our kinetic theory solution simulates a gas-like swarm motion,
which provides excellent coverage. Finally, experimental results are
presented that determine how well the macroscopic-level theory, mentioned
above, predicts simulated swarm behavior on this task.
2006
Spears, D., W. Kerr, and W. Spears,
Physics-based Robot Swarms for Coverage Problems. To appear in the
International Journal on Intelligent Control and Systems, 2006.
One of the biggest issues preventing the acceptability of large,
multiagent systems (i.e., swarms) is that of predictability of
aggregate behavior. This is an especially thorny issue due to the
modern multiagent philosophy of designing swarm behaviors that emerge
spontaneously from local agent interactions, without the invocation of
any global engineering principles. Although this paper agrees with
the notion of emergent swarm behavior, it adopts a more rigorous
approach to multiagent system design that is based on physics principles.
By using physics for multiagent design, traditional physics analysis
techniques are easily applied to predict swarm behavior.
This paper demonstrates that by using a physics-based swarm approach,
one can design systems that are both effective on coverage
tasks and are predictable in the aggregate.
Spears, W., J. Hamann, P. Maxim, T. Kunkel, R. Heil, D. Zarzhitsky, D. Spears, and C. Karlsson, Where Are You? Proceedings of Second Swarm Robotics Workshop.
The ability of robots to quickly and accurately localize their neighbors
is extremely important in swarm robotics. Prior approaches generally rely
either on global information provided by GPS, beacons, and landmarks,
or complex local information provided by vision systems. In this paper
we provide a new technique, based on trilateration. This
system is fully distributed, inexpensive, scalable, and robust.
In addition, the system provides a unified framework
that merges localization with information exchange between robots.
The usefulness of this framework is illustrated on a number of applications.
Wiegand, P., M. Potter, D. Sofge, and W. Spears, A Generalized Graph-Based Method for Engineering Swarm Solutions to Multiagent Problems. Proceedings of PPSN 2006
We present two key components of a principled method for constructing modular, heterogeneous swarms. First, we generalize a well-known technique for representing swarm behaviors to extend the power of multiagent systems by specializing agents and their interactions. Second, a novel graph-based method is introduced for designing swarm-based behaviors for multiagent teams. This method includes engineer-provided knowledge through explicit design decisions pertaining to specialization, heterogeneity, and modularity. We show the representational power of our generalized representation can be used to evolve a solution to a challenging multiagent resource protection problem. We also construct a modular design by hand, resulting in a scalable and intuitive heterogeneous solution for the resource protection problem.
Hettiarachchi S., and W. Spears, DAEDALUS for Agents with Obstructed Perception. Proceedings of the 2006
IEEE Mountain Workshop on Adaptive and Learning Systems
Best Paper Award!
Traditional approaches to designing multi-agent systems are offline (in
simulation), and assume the presence of a global observer. In the online
(real world), there may be no global observer, performance feedback may be
delayed or perturbed by noise, agents may only interact with their local
neighbors, and only a subset of agents may experience any form of
performance feedback. Under these circumstances, it is much more difficult
to design multi-agent systems. DAEDALUS is designed to address these issues,
by mimicking more closely the actual dynamics of populations of agents
moving and interacting in a task environment. This paper addresses the
feasibility of DAEDALUS for agents moving towards a goal through an obstacle
field, where the obstacles can obstruct perception.
Hettiarachchi S., Spears W., Green D., and Kerr W., Distributed Agent Evolution
with Dynamic Adaptation to Local Unexpected Scenarios. Proceedings of the 2005
Second GSFC/IEEE Workshop on Radical Agent Concepts
This paper introduces a novel framework for
designing multi-agent systems, called "Distributed Agent Evolution with Dynamic
Adaptation to Local Unexpected Scenarios" (DAEDALUS). Traditional approaches to
designing multi-agent systems are onine (in simulation), and assume the presence
of a global observer. In the online (real world), there may be no global
observer, performance feedback may be delayed or perturbed by noise, agents may
only interact with their local neighbors, and only a subset of agents may
experience any form of performance feedback. Under these circumstances, it is
much more difficult to design multi-agent systems. DAEDALUS is designed to
address these issues, by mimicking more closely the actual dynamics of
populations of agents moving and interacting in a task environment. We use two
case studies to illustrate the feasibility of this approach.
2005
Hettiarachchi
S. and Spears W., Moving Swarm Formations Through Obstacle Fields. Proceedings
of the 2005 International Conference on Artificial Intelligence, Volume 1,
97-103, CSREA Press.
In prior work we
established how artificial physics can be used to self-organize swarms of mobile
robots into hexagonal formations that move toward a goal. In this paper we
extend the framework to moving formations through obstacle fields. We provide
important metrics of performance that allow us to (a) compare the utility of
different generalized force laws in artificial physics, (b) examine trade-offs
between different metrics, and (c) provide a detailed method of comparison for
future researchers in this area.
Spears, W., D. Zarzhitsky, S. Hettiarachchi, W. Kerr. Strategies for
Multi-Asset Surveillance. IEEE International Conference on Networking,
Sensing and Control, 2005, 929-934.
This paper describes our "sandbox" for the study of
multi-asset surveillance, and explores the performance of rulebased control
strategies on this task. In order to maximize the probability of detection of
targets of interest, it is assumed that the team of unmanned air vehicles (UAVs)
must provide maximum sensory coverage of the terrain. We demonstrate, however,
both through simulation and mathematical analysis, that this is not always the
case.
Spears, W., Heil, R., and D. Zarzhitsky (2005). Artificial Physics for Mobile Robot Formations. IEEE Swarm Intelligence Symposium (SIS'05).
In prior work we established how artificial physics can be used
to self-organize swarms of mobile robots into hexagonal formations.
In this paper we extend the framework to
moving formations, by providing additional theoretical analysis
that facilitates the implementation of
seven robots in a hexagonal formation moving towards a goal.
Zarzhitsky, D., D. Spears, and W. Spears (2005). Swarms for chemical plume
tracing. IEEE Swarm Intelligence Symposium (SIS'05).
This paper presents a physics-based framework for managing
distributed sensor networks of autonomous vehicles, e.g., robots, which
self-organize into structured lattice arrangements using only local information.
The vehicles remain in formation during obstacle avoidance and search for a
chemical emitter that is actively ejecting a toxic chemical into the air. We
discuss a new plume tracing algorithm, based on the principles of fluid physics,
that outperforms the leading biomimetic competitors for this task.
Zarzhitsky, D., D. Spears, and W. Spears (2005b).
Distributed robotics approach to chemical plume tracing.
IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS'05).
This paper presents an application of a physicsbased
framework for distributed control of autonomous vehicles. The autonomous swarm
uses local information to self-organize into dynamic sensing and computation
grids during localization of the source of a toxic plume. Using physics of fluid
flow we develop a new plume-tracing algorithm, and then use computational fluid
dynamics simulations to show that the new approach outperforms the leading
biomimetic competitors for this task.
Kerr, W. and Spears, D. (2005) Robotic simulation of gases for a surveillance task. In Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS'05)
The task addressed here requires a swarm of mobile robots to
monitor a long corridor, i.e., by sweeping through it while avoiding large
obstacles such as buildings. In the case of limited sensors and communication,
maintaining spatial coverage especially after passing the obstacles is a
challenging problem. Note that the main objective of this task is coverage.
There are two primary methods for agents to achieve coverage: by uniformly
increasing the inter-agent distances, and by moving the swarm as a whole. This
paper presents a physics-based solution to the task that is based on a kinetic
theory approach; our solution achieves both forms of coverage. Furthermore, the
paper describes how we transition from our original algorithm to an algorithm
utilizing mostly local sensor information, the latter being more realistic for
modeling robots. To determine how well our kinetic theory approach performs
against a popular alternative controller, experimental comparisons are
presented.
Spears, W., D. Spears, and D. Zarzhitsky (2005, invited).
Physicomimitics positioning
methodology for distributed, autonomous swarms.
GOMACTech-05 Intelligent Technologies
This paper presents a physics-based framework for the
distributed control of a mobile swarm of simple robots tasked with localizing a
source of a toxic chemical plume. The framework, called physicomimetics, is a
robust control scheme built on local interactions between the vehicles, making
it highly scalable, adaptive, and cost effective. The chemical plume-tracing
task discussed here is an example of a problem where vehicle collaboration
improves performance of the system, by acting as a distributed computational
mesh.
Spears, W., D. Spears, R. Heil, W. Kerr, and S. Hettiarachchi (2005). An
overview of physicomimetics. In E. Sahin and W. Spears (Eds.),
Lecture Notes in Computer Science State-of-the-Art
Series.
This paper provides an overview of our framework, called
physicomimetics,
for the distributed control of swarms of robots. We focus on robotic behaviors
that are similar to those shown by solids, liquids, and gases. Solid formations
are useful for distributed sensing tasks, while liquids are for obstacle
avoidance tasks. Gases are handy for coverage tasks, such as surveillance and
sweeping. Theoretical analyses are provided that allow us to reliably control
these behaviors. Finally, our implementation on seven robots is summarized.
2004
Spears, W., R. Heil, D. Spears, and D. Zarzhitsky (2004).
Physicomimetics for mobile robot formations.
Proceedings of the Third International Joint
Conference on Autonomous Agents and Multi Agent Systems (AAMAS-04).
In prior work we established how physicomimetics can be used to
self-organize hexagonal and square lattice formations of mobile robots. In this
paper we extend the framework to moving formations, by providing additional
theoretical analysis and showing how this theory facilitates the implementation
of seven robots in a hexagonal formation moving towards a goal.
Zarzhitsky, D., D. Spears, D. Thayer, and W. Spears (2004).
A fluid dynamics approach to multi-robot chemical plume tracing.
Proceedings of the Third International Joint
Conference on Autonomous Agents and Multi Agent Systems (AAMAS-04).
This paper presents a novel chemical plume tracing algorithm
executed by a distributed network of mobile sensing robots that measure the
ambient fluid velocity and chemical concentration. The algorithm drives the
robotic network to the source of the toxic plume, where measures can be taken to
remove or extinguish the source emitter.
Zarzhitsky, D., D. Spears, D. Thayer, and W. Spears (2004b). Agent-based
chemical plume tracing using fluid dynamics.
Lecture Notes in Artificial Intelligence,
Volume 3228. Springer-Verlag.
This paper presents a rigorous evaluation of a novel,
distributed chemical plume tracing algorithm. The algorithm is a combination of
the best aspects of the two most popular predecessors for this task.
Furthermore, it is based on solid, formal principles from the field of fluid
mechanics. The algorithm is applied by a network of mobile sensing agents (e.g.,
robots or micro-air vehicles) that sense the ambient fluid velocity and chemical
concentration, and calculate derivatives. The algorithm drives the robotic
network to the source of the toxic plume, where measures can be taken to disable
the source emitter. This work is part of a much larger effort in research and
development of a physics-based approach to developing networks of mobile sensing
agents for monitoring, tracking, reporting and responding to hazardous
conditions.
Kerr, W., D. Spears, W. Spears, and D. Thayer (2004). Two formal gas
models for multiagent sweeping and obstacle avoidance.
Lecture Notes in Artificial Intelligence, Volume 3228. Springer-Verlag.
The task addressed here is a dynamic search through a bounded
region, while avoiding multiple large obstacles, such as buildings. In the case
of limited sensors and communication, maintaining spatial coverage, especially
after passing the obstacles, is a challenging problem. Here, we investigate two
physics-based approaches to solving this task with multiple simulated mobile
robots, one based on artificial forces and the other based on the kinetic theory
of gases. The desired behavior is achieved with both methods, and a comparison
is made between them. Because both approaches are physics-based, formal
assurances about the multi-robot behavior are straightforward, and are included
in the paper.
Spears, W., D. Spears, and R. Heil (2004). A formal analysis of potential
energy in a multiagent systems.
Lecture Notes in Artificial Intelligence, Volume 3228. Springer-Verlag.
This paper summarizes our
physicomimetics
framework for robot control. A
theoretical analysis of potential energy is then provided, allowing us to
properly set system parameters a priori. Finally, results of a multi-robot
implementation are presented.
Spears, W., D. Spears, J. Hamann, and R. Heil (2004).
Distributed, Physics-Based Control of
Swarms of Vehicles. Autonomous Robots, Volume 17(2-3).
(JOURNAL PAPER)
We introduce a framework, called "physicomimetics", that provides distributed
control of large collections of mobile physical agents in sensor networks. The
agents sense and react to virtual forces, which are motivated by natural physics
laws. Thus, physicomimetics is founded upon solid scientific principles.
Furthermore, this framework provides an effective basis for self-organization,
fault-tolerance, and self-repair. Three primary factors distinguish our
framework from others that are related: an emphasis on minimality (e.g., cost
effectiveness of large numbers of agents implies a need for expendable platforms
with few sensors), ease of implementation, and run-time efficiency. Examples are
shown of how this framework has been applied to construct various regular
geometric lattice configurations (distributed sensing grids), as well as dynamic
behavior for perimeter defense and surveillance. Analyses are provided that
facilitate system understanding and predictability, including both qualitative
and quantitative analyses of potential energy and a system phase transition.
Physicomimetics has been implemented both in simulation and on a team of seven
mobile robots. Specifics of the robotic embodiment are presented in the paper.
2002
Gordon-Spears, Diana F., and William M. Spears (2002).
Analysis of a Phase Transition in a
Physics-Based Multiagent System. Proceedings of FAABS02.
This paper uses physics-based to
analyze physics-based multi agent system. Both qualitative and
quantitative analyses are provided to better understand and predict a system
phase transition. These analyses yield deep insights into the system behavior.
Furthermore, they have been tested in a practical context on actual robots and
proven to be quite effective for setting system parameters.
1999
Spears, William M. and Diana F. Gordon (1999). Using Artificial
Physics to Control Agents. IEEE International Conference on Information,
Intelligence, and Systems, November, 1999.
We introduce a novel framework called "artificial physics",
which provides distributed control of large collections of agents. The agents
react to artificial forces that are motivated by natural physical laws. This
framework provides an effective mechanism for achieving self-assembly,
fault-tolerance, and self-repair. Examples are shown for various regular
geometric configurations of agents. A further example demonstrates that
self-assembly via distributed control can also perform distributed computation.
Gordon, Diana F., William M. Spears, Oleg Sokolsky, and Insup Lee
(1999). Distributed Spatial Control, Global Monitoring and Steering
of Mobile Physical Agents. IEEE
International Conference on Information, Intelligence, and Systems,
November, 1999.
In this paper, we combine two frameworks in the context of an
important application. The first framework, called "artificial physics," is
described in detail in a companion paper by Spears and Gordon [13]. The purpose
of artificial physics is the distributed spatial control of large collections of
mobile physical agents. The agents can be composed into geometric patterns
(e.g., to act as a sensing grid) by having them sense and respond to local
artificial forces that are motivated by natural physics laws. The purpose of the
second framework is global monitoring of the agent formations developed with
artificial physics. Using only limited global information, the monitor checks
that the desired geometric pattern emerges over time as expected. If there is a
problem, the global monitor steers the agents to self-repair. Our combined
approach of local control through artificial physics, global monitoring, and
"steering" for self-repair is implemented and tested on a problem where multiple
agents form a hexagonal lattice pattern.
|
