 |
Distributed Evolution for Swarm RoboticsPOC: Dr. William M. Spears Computer Science DepartmentUniversity of Wyoming Laramie, WY 82071 wspears@cs.uwyo.edu |
Team Members:
|
The focus of our research is to build aggregate sensor systems, specifically, to design rapidly deployable, scalable, adaptive, cost-effective, and robust swarms of autonomous distributed mobile sensing robots. This combines sensing, computation and networking with mobility,thereby enabling deployment, assembly, reconfiguration, and disassembly of the multi-robot swarm. Our objective is to provide a scientific, yet practical, approach to the design and analysis of swarm robotic systems. Our target applications for robot swarms include tracing biological and chemical hazards to their source.
It is assumed that robots can sense and affect nearby robots; thus, a key challenge of this project has been how to design ``local'' control rules. Not only do we want the desired global swarm behavior to emerge from the local interaction between robots (i.e.,self-organization), but we also would like there to be some measure of fault-tolerance i.e., the global behavior degrades very gradually if individual robots are damaged. Self-repair is also desirable, in the event of damage. Self-organization, fault-tolerance, and self-repair are precisely those principles exhibited by natural physical systems. Thus, many answers to the problems of distributed control can be found by studying the natural laws of physics.
In prior work we have shown how our artificial physics framework can be used to self-organize swarms of mobile robots into hexagonal lattices that move towards a goal. We now extend the framework to include motion through an obstacle field. We are also investigating the utility of a second force law, which is a novel generalization of the Lennard-Jones framework.
Traditional approaches to designing multi-agents 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 constraints, designing multi-agent systems is difficult. We present a novel approach called``Distributed Agent Evolution with Dynamic Adaptation to Local Unexpected Scenarios'' or DAEDALUS to address these issues, by mimicking more closely the actual dynamics of populations of agents moving and interacting in a (task) environment.
With the DAEDALUS paradigm, we assume that agents (whether software or hardware) move throughout some environment. As they move, they interact with other agents. These agents may be of the same species or of some other species. Agents of different species have different roles in the environment. The goal is to evolve agent behaviors and interactions between agents, in a distributed fashion, such that the desired global behavior occurs. Let us further assume that each agent has some procedure to control its own actions in response to environmental conditions and interactions with other agents. The precise implementation of these procedures is not relevant, thus they may be programs, rule sets, finite state machines, real-valued vectors, force laws, or any other procedural representation. Agents have a sense of self-worth or "fitness".
Each robot of the swarm is an individual in a population that interacts with its neighbors. Each robot contains a slightly mutated copy of the optimized control procedure found with offline learning with an offline EA. This ensures that our robots are not completely homogeneous. We allowed this slight heterogeneity because when the environment changes, some mutations perform better than others. The robots that perform well in the environment will have higher fitness than the robots that perform poorly. When low fitness robots encounter high fitness robots, the low fitness robots ask for the high fitness robot's rules. Hence, better performing robots share their knowledge with their poorer performing neighbors. To ensure the capability of adapting to further changes in the environment, robots also occasionally mutate their own rules, according to a pre-defined mutation rate attached to that robot. In our original version of DAEDALUS, the robots do not exchange mutation rates when they exchange the rules.
7 Robots moving through 50 obstacles(?) (17MB)
40 Robots moving through 100 obstacles (17MB)
40 Robots moving through 1 large obstacles (45MB)
20 Robots moving through 100 obstacles (11MB)
15 Robots moving through 45 obstacles using LJ force law (36MB)
20 Robots moving through 100 obstacles using Newtonian force law(23MB)
20 Robots moving through 100 obstacles using LJ force law (16MB)
20 Robots moving through 100 obstacles using LJ force law (19MB)
70 Robots moving through 100 obstacles using LJ force law (40MB)
60 Robots moving through 90 large obstacles using LJ force law (116MB)
Hettiarachchi S., Spears W., DAEDALUS for Agents with Obstructed Perception. 2006 Proceedings of the IEEE Mountain Workshop on Adaptive and Learning Systems, Utah State University, Logan, Utah. 2006. (Best Paper Award)
