Project Description:
Among other natural wonders, fish schools and bird flocks are
amazing from an engineering design perspective. Within a fish school of
enormous size, each fish plans its motion by only sensing its
nearest neighbors' positions. For example, in this movie
where the overall school translates in the fish tank, each fish just
sets its heading direction as the average of its nearest neighbors'
heading directions (More discussion can be found here). The
global behavior of the group emerges from each individual's local
interactions with its neighbors, and this behavior is often termed self-organziation.
From a design perspective, this is a distributed system, offering
advantages of scalability, fault tolerant to individual process
failure, and
higher operational efficiency. However, in a distributed
system
the lack of a central decision maker complicates the design.
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.
Validation:
So far we tested our approach on two sample problems through analysis
and computer simulations :
Task 1 (Formation Control):
We can encode an abstraction of
a robot group formation using a finite set of geometric moments. Each
robot plans its motion so that the overall group
satisfies a predefined set of geometric moments. Here is a block diagram
illustration. Simulations are provided (A small group with 7 robots [mov][avi], and a
large group with 20 robots [mov][avi]):
notice how individual robot reacts when some members die.
Task 2 (Target
Tracking):
A group of mobile robots
cooperatively track the location of one or more targets in the
environment. Each agent takes noisy sensor range and bearing readings
of the target and maintains an estimate of the target location. Each
agent shares its estimate with its neighbors to reach consensus on a
belief distribution of the location of the target. The noise in the
information gathered by each agent’s sensor is dependent on
the
relative location of the target, so each agent moves to maximize the
expected new sensor information relative to the current uncertainty.
Here are some
sample runs: Static
target, moving
target.
Task 3
(Connectivity Maintenance):
In this example of 6 node graph, the 3 big blue nodes are
leaders.
They all follow the same sinusoidal motion model
\dot{x_i}(t)=-0.2,\dot{y_i}(t)=0.5\cos(x_i) with different initial
configurations. The left three small red nodes run a decentralized
connectivity maintenance controller to move along with the leaders and
maintain graph connectivity. [video]
Experiments:
Right now we are building a network of 10-20 mobile robots to test our
algorithms on hardware. Each robot is a differential drive vehicle with
a zigbee module on top to handle the communication via IEEE 802.15.4
Experiment 1: The
differential-drive robot is doing deadreckoning under the vision
position feedback. [video]
Experiment 2:
Under the vision position feedback, two robots try to meet at the
center of their starting positions. In fact, each robot is
always
moving to the estimated center of their starting positions. During
motion each robot is running a PI consensus estimator to update its
estimated center. [video]
Experiment 3
(Task 1 without obstacle avoidance):
Without vision feedback, three robots start at (-300,300),
(600,0) and (600, 600), and move to achieve the desired
statistics of (100, 400, 90000, 60000, 180000). During
motion each robot is running a PI consensus estimator to update its
estimated statistics. Here is the experiment
played back 3 times faster the the actual speed, and here is the animation
based on the real robot position data (again the grey dot and ellipse
visualize the desired statistics, whereas the red ones visualize the
actual statistics).
Experiment 4
(Obstacle avoidance):
Without vision feedback, two pairs of epucks want to swap their positions. Specifically, they start at (0,300),
(300,0), (300, 600) and (600,300), and want to move to (600,300),
(300,600), (300, 0) and (0,300) respectively. This video,
with the positive X and postive Y directions as well as the
origin shown as red, shows how the epucks manuever themselves to
avoid possible collision. The video is played back at 2 times its
original speed.
Publications:
- K. M. Lynch, I. B. Schwartz, P. Yang, and R. A.
Freeman.
Decentralized environmental modeling by mobile sensor networks. To
appear, IEEE Transactions on Robotics,
2008. [pdf]
- P. Yang, R. A. Freeman, and K. M. Lynch.
Multi-agent coordination by decentralized estimation and control. To
appear, IEEE Transactions on Automatic Control,
2008. [pdf]
- P. Yang, R. A. Freeman, G. J.
Gordon, K.
M. Lynch, S. S. Srinivasa and R. Sukthankar,
"Decentralized
estimation and control of graph connectivity in mobile sensor
networks," in Proceedings of the 2008
American Control Conference, Seattle, Washington,
June 2008. [pdf][talk]
- P. Yang, R. A. Freeman, and K. M. Lynch. Distributed
Cooperative Active Sensing Using Consensus Filters. To appear, 2007
IEEE
International Conference on Robotics and Automation. [pdf][talk]
- P. Yang, R. A. Freeman, and K. M. Lynch. A General
Stability Condition for Multi-Agent Coordination by Coupled Estimation
and Control. in Proceedings of the 2007 American
Control Conference. [pdf]
- P. Yang, K.M. Lynch, and
R.A. Freeman, "Optimal information propagation in sensor
networks," in Proceedings of the 2006 IEEE
International Conference on Robotics and Automation, Orlando,
Florida, May 2006. [pdf]
[talk]
- R.A. Freeman, P. Yang, and
K.M. Lynch, "Distributed estimation and control of swarm
formation statistics," in Proceedings of the 2006
American Control Conference, Minneapolis, Minnesota,
June 2006. [pdf]
[talk]
- R. A. Freeman, P. Yang, and K. M. Lynch.
Stability and convergence properties of dynamic average consensus
estimators.
To appear, IEEE Conference on Decision and Control,
2006. [pdf][talk]
|
