A probabilistic geometric model of self-organized aggregation in swarm robotic systems


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2012

Öğrenci: LEVENT BAYINDIR

Danışman: EROL ŞAHİN

Özet:

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.