Bibliographic Metadata
- TitleCollective graph exploration / Mirosław Dynia
- Author
- Published
- Institutional NotePaderborn, Univ., Diss., 2007
- LanguageEnglish
- Document TypesDissertation (PhD)
- URN
- Social MediaShare
- Reference
- IIIF
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.
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.
- The PDF-Document has been downloaded 84 times.