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.


    Zugriff

    Download

    Verfügbarkeit in meiner Bibliothek prüfen


    Exportieren, teilen und zitieren



    Titel :

    Collaborative graph exploration


    Beteiligte:

    Erscheinungsdatum :

    2016



    Medientyp :

    Sonstige


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629 / 620



    Collaborative graph exploration

    Ortolf, Christian | TIBKAT | 2016

    Freier Zugriff

    Collaborative graph exploration

    Ortolf, Christian | BASE | 2016

    Freier Zugriff

    GRAPH EXPLORATION FORWARD SEARCH

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

    Freier Zugriff

    Mars Exploration Rover/Collaborative Information Portal

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


    Collaborative UAV Exploration of Hostile Environments

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