Zur Seitenansicht
 

Titelaufnahme

Titel
Collective graph exploration / Mirosław Dynia
AutorDynia, Mirosław In der Gemeinsamen Normdatei der DNB nachschlagen
Erschienen2007
HochschulschriftPaderborn, Univ., Diss., 2007
SpracheEnglisch
DokumenttypDissertation
URNurn:nbn:de:hbz:466-20080225031 Persistent Identifier (URN)
Dateien
Collective graph exploration [0.65 mb]
abstract [12.55 kb]
zusfasng [11 kb]
Links
Nachweis
Klassifikation

Deutsch

Der Einsatz zahlreicher Ressourcen bringt bei der Lösung komplexer Aufgaben Vorteile, die nicht zu unterschätzen sind. Jedoch muss hierbei noch zusätzlicher Koordinationsaufwand in Kauf genommen werden. Wir erforschen die Möglichkeiten zur Kooperation von Gruppen mobiler Roboter, die eine unbekannte Umgebung (modelliert als ein Graphen) erkunden. Selbst wenn alle Mitglieder der Gruppe komplettes Wissen über das gesamte System haben (alle Positionen von Robotern sind bekannt), kann es noch unbekannte Graphenteile geben, die für die aktuelle Konfiguration der Roboter den worst-case Fall darstellen. In diesem Fall können aufwändige Neuverteilungen der Roboter nicht vermieden werden. Die Lage ist noch anspruchvoller wenn wir Beschränkungen an die Informationsübertragung zwischen Robotern auferlegen. Wir erforschen verschiedene Kommunikationsmodelle und deren Einfluss an die Effizienz der Kooperation. Das ganze Szenario ist unter zwei Kostenmodellen betrachtet, wo wir sowohl effiziente Algorithmen als auch generelle untere Schranken vorstellen.

English

No one can deny the advantages that come from an application of multiple resources by solving some complex problems. However, there is always some additional coordination effort needed to be invested there. We investigate cooperation of group of mobile robots by exploration of an unknown environment modeled by a graph. Even if each team member has a global view on the team (knows positions of all other robots), there is still some unknown part of the graph which might turn out to be the worst possible setting for the current distribution of robots. In this case some costly relocation will have to take place. The situation gets even more challenging by considering various restrictions on the propagation of information. We investigate various communication models and try to observe their impact on the cooperation efficiency. The whole setting is considered under two different cost models and by different restrictions on the graph topology. Moreover, there are general lower bounds presented, proving that there are some graphs that cannot be explored optimally, if their topology not known in advance.