Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem

Heiko Hamann, Heinz Wörn
in Proc. of the tenth International Conference on Simulation of Adaptive Behavior (SAB'08) , LNAI 5040 (2008), 447-456


               It is becoming state-of-the-art to form large-scale multi-agent
systems or artificial swarms showing adaptive behavior by constructing
high numbers of cooperating, embodied, mobile agents (robots). For the
sake of space- and cost-efficiency such robots are typically miniaturized
and equipped with only few sensors and actuators resulting in rather sim-
ple devices. In order to overcome these constraints, bio-inspired concepts
of self-organization and emergent properties are applied. Thus, accuracy
is usually not a trait of such systems, but robustness and fault tolerance
are. It turns out that they are applicable to even hard problems and reli-
ably deliver approximated solutions. Based on these principles we present
a heuristic for the Euclidean Steiner tree problem which is NP-hard. Ba-
sically, it is the problem of connecting objects in a plane efficiently. The
proposed system is investigated from two different viewpoints: computa-
tionally and behaviorally. While the performance is, as expected, clearly
suboptimal but still reasonably well, the system is adaptive and robust.

Download PDF: