Project "Biologically-Inspired Multi-Agent Systems"
(scroll down for publications)
Ant robots are simple creatures with limited sensing and computational capabilities as well as very noisy actuation. They have the advantage that they are easy to program and cheap to build. This makes it feasible to deploy groups of ant robots and take advantage of the resulting fault tolerance and parallelism. Ant robots are usually studied in the context of path following. We, on the other hand, study their behavior for one-time or repeated coverage of terrain, as required, for example, for guarding terrain, mine sweeping and surface inspection. Ant robots cannot use conventional planning methods due to their limited sensing and computational capabilities. To overcome these limitations, we study navigation methods that leave markings in the terrain, similar to what real ants do. These markings are shared among all ant robots and allow them to cover terrain even if they do not have any kind of memory, cannot maintain maps of the terrain, nor plan complete paths. Our navigation methods do not require the ant robots to be localized, which completely eliminates solving difficult and time-consuming localization problems. They can be used by single ant robots and groups of ant robots and are robust even if the ant robots are moved without realizing this (say, by people running into them), some ant robots fail, and some markings get destroyed. This project is interesting because it provides a very different approach to the problem that our POMDP-based robot architecture addresses, namely that robots almost never know exactly where they are in the environment. The POMDP-based robot architecture provides robots with the best possible location estimate, while our ant robots achieve their goals without ever worrying about where they are in the terrain. This project not only demonstrates the capabilities of robots with extremely limited sensing, processing, and communication capabilities (these properties make it cost effective to use teams of robots) but also provides a novel (and rather surprising) application of ideas from real-time heuristic search and reinforcement learning (where the values are written on the floor rather than stored in memory). We have mostly worked on understanding possible ant algorithms and their behavior in theory and in simulation. In particular, we have used theoretical results about real-time heuristic search to analyze the behavior of our ant robots. However, we have also built a first prototype of an actual ant robot and run experiments with it.
You can watch the 4-minute movie "Terrain Covering Ant Robots: From Unrealistic Simulations to Physical Robots," either 47 MBytes in DivX avi format (the DivX codec can be downloaded for free) or 29 MBytes in worse quality in the older mpg format (copyright by Jonas Svennebring and Sven Koenig).
Tutorial
Representative Publications on Ant Robotics
Representative Publications on Theoretical Foundations
For publications on the real-time heuristic search foundations of ant robotics, see the project "agent-centered search (real-time heuristic search)."
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.