Abstract

A team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents have no a priori knowledge about the graph topology) multi-agent graph searching and exploration are rapidly expanding. Recent studies have presented new approaches and models to better describe real-life problems like clearing danger areas by a group of robots or constructing a map of an unknown terrain. A centralized searching and exploration in the off-line setting (i.e., when the topology of a graph is known in advance) are well studied, due to their wide applications in robotic and network fields, and many profound results have been established. In this thesis we are focusing on the issues of the monotone connected decontamination problem, the on-line collaborative exploration and the partial exploration of digraphs. Firstly, we provide two comprehensive surveys on the topics of graph searching and exploration. Then in the four subsequent chapters, we present the following results: - We give a distributed algorithm for the searchers that allows them to compute a connected and monotone strategy that guarantees searching any unknown partial grid of order n with the use of O(\sqrt{n}) searchers. Moreover, we give a lower bound of Ω(\sqrt{n}/log n) in terms of achievable competitive ratio of any distributed algorithm. - Checking if the connected pathwidth of any graph is at most some fixed integer k can be done in polynomial time. - Let the cost of a strategy be the total distance traversed by agents coupled with the price of invoking them. We construct two cost-optimal off-line algorithms for rings and trees, respectively. For unknown rings, we give a 2-competitive algorithm. We prove a lower bound of competitive ratio of 3/2 (for rings) and 2 (for trees) for any on-line algorithm. - The problem of establishing if there exists a subgraph, which connects a chosen vertices and can be explored by a given number of agents is NP-hard and FPT.

Author (1)