This thesis discusses the exploration of a landscape by a team of robots. The landscape is for that purpose modeled by a graph, along whose edges robots may travel in a round-based model with the goal to visit all vertices of the graph. For this purpose an algorithm chooses for each robot in each round an incident edge to traverse to reach a new vertex with that robot. The special challenge, in contrast to the traveling salesman problem with multiple salesman (mTSP), is, that the considered team is being further restricted. In our first scenario (exploration) the team is forbidden to see an overview of the graph, such that the algorithm must base all its decisions on the already visited part of the graph. We show for this scenario new lower bounds on grid graphs with rectangular obstacles. In addition we extends the lower bounds for these grid graphs and for trees to hold up against randomized algorithms. Furthermore we show efficient algorithms for the exploration of grid graphs as well as for trees. To complete our analysis we present experiments on so called comb trees, a class of graph that forces several algorithms into their worst case behavior. As a second exploration scenario we examine robots which indeed have a map of the graph, but may not communicate with each other (unaware cleaning). This also excludes the perception of other robots. For this scenario it is not only interesting to visit all nodes of the graph once, but to indefinitely repeat visiting them. To achieve this robots have to move in a way, such that their movement is compatible with that of other robots. Collectively this should enable them to efficiently search or clean a graph modeling a landscape. We prove for this scenario an algorithm cleaning grid graphs (without obstacles) in asymptotic optimal time. Additionally we show, how such a cleaning team can tackle a general graph modeling a complex landscape. Finally we evaluate empirically our algorithms on the grid graph to provide an intuition for the efficiency and problems of these cleaning algorithms. ; In der vorliegenden Arbeit wird die Exploration von einer Landschaft mit Hilfe von Teams aus Robotern diskutiert. Die Landschaft wird dabei von einem Graphen modelliert, an dessen Kanten die Roboter in einem rundenbasierten Modell entlanglaufen, mit dem Ziel alle Knoten des Graphen zu besuchen. Ein Algorithmus wählt dazu für jeden Roboter in jeder Runde eine anliegende Kante aus, an der dieser entlanglaufen kann, um zu einem neuen Knoten zu gelangen. Die besondere Schwierigkeit, im Gegensatz zum Problem des Handlungsreisenden mit mehreren Handlungsreisenden (mTSP), ist dabei, dass das betrachtete Team weiter eingeschränkt wird. In unserem ersten Szenario (Exploration) wird dem Team der Überblick über den Graphen verwehrt, so dass der Algorithmus alle Entscheidungen auf dem bereits besuchten Teil des Graphen gründen muss. Wir zeigen für dieses Szenario neue untere Schranken auf Gittergraphen mit rechteckigen Hindernissen. Zudem erweitern wir die unteren Schranken für diese Gittergraphen und auch auf Bäumen damit sie auch gegen randomisierte Algorithmen bestehen. Des Weiteren zeigen wir effiziente Algorithmen für die Erkundung der Gittergraphen als auch für Bäume. Um die Untersuchung mit empirischen Ergebnissen zu ergänzen, zeigen wir noch Experimente auf sogenannten Kammbäumen, eine für viele Algorithmen schwierige Art von Graph. Als weiteres Explorationsszenario behandeln wir Roboter, die zwar eine Karte besitzen, jedoch nicht miteinander kommunizieren können (unaware cleaning). Dies schließt auch die Wahrnehmung anderer Roboter aus. Dabei ist es nicht nur interessant alle Knoten des Graphen einmal abzulaufen, sondern auch diese immer wieder zu besuchen. Dazu müssen Roboter sich so bewegen, dass ihre Bewegung kompatibel mit der der anderen Roboter ist. Gemeinsam soll so ein effizientes Durchsuchen oder Reinigen einer durch einen Graphen modellierten Landschaft ermöglicht werden. Wir zeigen für dieses Szenario einen Algorithmus der asymptotisch optimal Gittergraphen (ohne Hindernisse) reinigen kann. Zudem zeigen wir auch wie ein solches Reinigungsteam eine komplexe Landschaft, die durch einen beliebigen Graphen modelliert wird, angehen kann. Am Ende evaluieren wir noch empirisch unsere Algorithmen auf dem Gittergraphen um eine Intuition zu verschaffen für die Effizienz und Probleme dieser Algorithmen.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Collaborative graph exploration


    Beteiligte:

    Erscheinungsdatum :

    2016-01-01



    Medientyp :

    Hochschulschrift


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Schlagwörter :

    Klassifikation :

    DDC:    004 / 620 / 629



    Collaborative graph exploration

    Ortolf, Christian | TIBKAT | 2016

    Freier Zugriff

    Collaborative graph exploration

    Ortolf, Christian | DataCite | 2016


    GRAPH EXPLORATION FORWARD SEARCH

    ANDERSON HANS / CSERNA BENCE | Europäisches Patentamt | 2024

    Freier Zugriff

    Collaborative UAV Exploration of Hostile Environments

    L. J. Luotsinen / A. J. Gonzalez / L. Boeloeni | NTIS | 2004


    Mars Exploration Rover/Collaborative Information Portal

    J. Walton / R. E. Filman / J. Schreiner | NTIS | 2002