Minimizing the Cost of Team Exploration

A group of mobile agents is given a task to explore an edge-weighted graph G, i.e., every vertex of G has to be visited by at least one agent. There is no centralized unit to coordinate their actions, but they can freely communicate with each other. The goal is to construct a deterministic strategy which allows agents to complete their task optimally. In this paper we are interested in a cost-optimal strategy, where the cost is understood as the total distance traversed by agents coupled with the cost of invoking them. Two graph classes are analyzed, rings and trees, in the off-line and on-line setting, i.e., when a structure of a graph is known and not known to agents in advance. We present algorithms that compute the optimal solutions for a given ring and tree of order n, in O(n) time units. For rings in the on-line setting, we give the 2-competitive algorithm and prove the lower bound of 3/2 for the competitive ratio for any on-line strategy. For every strategy for trees in the on-line setting, we prove the competitive ratio to be no less than 2, which can be achieved by the DFS algorithm.