Self-organized aggregation is the global level gathering of randomly placed robots using local sensing. Developing high performance and scalable aggregation behaviors
for a swarm of mobile robots is non-trivial and still in need, when robots control themselves, perceive only a small part of the arena, and do not have access to
information such as their position, the size of the arena or the number of robots.
In this thesis, we developed a non-spatial probabilistic geometric model for self-organized aggregation as a tool to analyze aggregation. The model consists of
four formulas for predicting the probabilities of aggregation events: creation, growing, shrinking and dissipation of an aggregate. The creation probability is
derived mathematically using kinetic theory of gases. In order to derive formulas for growing, shrinking and dissipation probabilities, first, it is assumed that aggregates
formed by robots are circular. Then, these formulas are derived geometrically using circle packing theory.
We proposed an aggregation behavior and implemented this behavior in the Stage multi-robot simulator. The behavior consists of four sub-behaviors: search,
wait, leave and change direction. The wait sub-behavior is specially designed to force aggregates to be circular so that our assumption for the model holds in simulation experiments.
We verified each formula using simulation experiments conducted in the Stage multi-robot simulator. Through systematic experiments, we showed that model predictions and
simulation results match well and the formulas proposed for growing and shrinking probabilities predict these probabilities better for larger aggregates compared to
predictions of previous self-organized aggregation models.
We also conducted experiments, in which certain aggregation events are disabled systematically, in order to
verify the model further and show that our model can be used to predict the steady-state performance of generic simulation experiments.
We use two different methods to predict the steady state performance with our model: microscopic model execution and steady state analysis.
It is shown that the largest aggregate size, the number of aggregates, the number of searching robots and the aggregate distributions at the steady state-obtained
from microscopic model execution, steady state analysis and simulation experiments are close to each other and our model can be used to predict
steady-state performance of aggregation experiments.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12615181/index.pdf |
| Date | 01 September 2012 |
| Creators | Bayindir, Levent |
| Contributors | Bayindir, Levent |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | Ph.D. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for METU campus |
Page generated in 0.0014 seconds