Startseite > Publikationen > Publikationen


Dynia, Miroslaw;Kutylowski, Jaroslaw;Schindelhauer, Christian;Meyer auf der Heide, Friedhelm:

Smart Robot Teams Exploring Sparse Trees.

In: Proc. of the 31st International Symposium of Mathematical Foundations of Computer Science, Springer Lecture Notes in Computer Science LNCS, S. 327-338, Jan. 2006, Springer Verlag


We consider a tree which has to be completely explored by a group of k robots, initially placed at the root. The robots are mobile and can communicate using radio devices, but the communication range is bounded. They decide based on local, partial knowledge, and exchange information gathered during the exploration. There is no central authority which knows the graph and could control the movements of the robots - they have to organize themselves and jointly explore the tree. The problem is that at every point of time the remaining unknown part of the tree may appear to be the worst case setting for the current deployment of robots. We present a deterministic distributed algorithm to explore T and we use a parameter of a tree called density. We compare the performance of our algorithm with the optimal algorithm having a-priori knowledge of the same tree. We show that the above ratio is influenced only by the density and the height of the tree. Since the competitive ratio does not depend on the number of robots, our algorithm truly emphasizes the phenomena of self-organization. The more robots are provided, the faster the exploration of the terrain is completed.


author = {Dynia, Miroslaw and Kutylowski, Jaroslaw and Schindelhauer, Christian and Meyer auf der Heide, Friedhelm},
title = {Smart Robot Teams Exploring Sparse Trees},
booktitle = {Proc. of the 31st International Symposium of Mathematical Foundations of Computer Science},
series = {Springer Lecture Notes in Computer Science LNCS},
pages = {327-338},
publisher = {Springer Verlag},
month = jan,
year = {2006},

BibTeX in die Zwischenablage kopieren