Space-Time Continuous Models of Swarm Robotic Systems: Supporting Global-to-Local Programming

Heiko Hamann
University of Karlsruhe, Germany, PhD Thesis (2008)

Abstract:

This work was done within the “Research Training Group” GRK 1194 “Self-organizing
Sensor-Actuator Networks” in the subproject I2 “Decentral Task Processing by Cooperation
and Interaction”. A generic model in as far as possible mathematical closed-form was
developed that predicts the behavior of large self-organizing robot groups (robot swarms)
based on their control algorithm. In addition, an extensive subsumption of the relatively
young and distinctive interdisciplinary research field of swarm robotics is emphasized. The
connection to many related fields is highlighted and the concepts and methods borrowed
from these fields are described shortly.
Large groups of small robots, mostly of limited equipment are applied in swarm robotics
forming a decentral system. All robots are autonomous and act on the basis of locally
available information. The development of the control algorithm, that is to be executed
locally on each robot, has proven to be difficult. This development of the local control
algorithm is defined and constrained by the global task (global-to-local programming,
or also micro-macro problem). The classical reductionistic approach is of limited use
here (problem of designing emergence). For example, the resulting behavior of the robot
swarm often contradicts the intuition of the program developer due to effects of the many
robot–robot interactions that cannot be anticipated.
The support of the swarm algorithm developer by models is an approach that has already
been discussed in the literature several times. The quickly available predictions of the
model are supposed to support the development early before the implementation on the
robots. Even complete parameter intervals can be scanned for optimal values. Furthermore,
the development and the application of models can result in a better understanding of
the effective processes in swarms concerning both the general understanding and in a
particular application. The modeling approach proposed in this work is particularly
distinguished by the explicit representation of space and the, at least partially existent,
formal connection between the micro- and the macro level.
The basic model of the robot positions is motivated by Brownian motion and consists of
a pair of corresponding equations. While the Langevin equation (a stochastic differential
equation) gives a local (microscopic) description of concrete trajectories, the Fokker–Planck
equation (also Kolmogorov forward equation, a partial differential equation), that can be
analytically derived from the Langevin equation, gives a global (macroscopic) description
by means of probability densities. This physical model was extended to a generic model
of communicating robot groups based on heuristic arguments. This model approach
has a variety of applications, however, the adaptation to a specific control algorithm is a
demanding modeling step.
The proposed model is validated against several swarm robotic scenarios applying real
robots and simulations: collision-based adaptive aggregation, collective perception, collec-
tive phototaxis, foraging with virtual pheromones, and tree-like aggregation. The required
adaptation of the model to the according situation is exemplified (modeling state transi-
tions, parameter selection, measurement etc.). The achieved accuracy of the model predic-
tions is good and sufficient to be a support in the algorithm development phase.
 


Download PDF:
Projects: