Consider the Ants Nearby Treasure Search (ANTS) problem introduced by Feinerman, Korman, Lotker, and Sereni (PODC 2012), where @math mobile agents, initially placed at the origin of an infinite grid, collaboratively search for an adversarially hidden treasure. In this paper, the model of is adapted such that the agents are controlled by a (randomized) finite state machine: they possess a constant-size memory and are able to communicate with each other through constant-size messages. Despite the restriction to constant-size memory, we show that their collaborative performance remains the same by presenting a distributed algorithm that matches a lower bound established by on the run-time of any ANTS algorithm.
Graph exploration in general is a fundamental problem in computer science. In the typical case, the goal is for a single agent to visit all nodes in a given graph. As an example, the exploration of trees was studied in @cite_6 , the exploration of finite undirected graphs was studied in @cite_11 @cite_0 , and the exploration of strongly connected digraphs was studied in @cite_2 @cite_9 . When a deterministic agent is exploring a graph, memory usage becomes an issue. With randomized agents, it is well-known that random walks allow a single agent to visit all nodes of a finite undirected graph in polynomial time @cite_5 . The speed up gained from using multiple random walks was studied by @cite_12 . Notice that in an infinite grid, the expected time it takes for a random walk to reach any designated cell is infinite.
@cite_9 @cite_6 @cite_0 @cite_2 @cite_5 @cite_12 @cite_11
2008110774 2017617294 2049516232 2077944048 2156184725 2160504298 2051006450
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [ Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356--361] showed an upper bound for R of dO(d) m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of @math , where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the first subexponential algorithm for this exploration problem, which achieves an upper bound of dO(log d) m. We also show a matching lower bound of @math for our algorithm. Additionally, we give lower bounds of @math , respectively, @math for various other natural exploration algorithms. A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its size, and its aim is to traverse all the edges. While O(log Δ) bits of memory suffice to explore any tree of maximum degree Δ if stopping is not required, we show that bounded memory is not sufficient to explore with stop all trees of bounded degree (indeed Ω (log log log n) bits of memory are needed for some such trees of size n). For the more demanding task requiring to stop at the starting node after completing exploration, we show a sharper lower bound Ω (log n) on required memory size, and present an algorithm to accomplish this task with O(log2 n)-bit memory, for all n-node trees. We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4 3(ṡ) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL e L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity. Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs. We wish to explore all edges of an unknown directed, strongly connected graph. At each point, we have a map of all nodes and edges we have visited, we can recognize these nodes and edges if we see them again, and we know how many unexplored edges emanate from each node we have visited, but we cannot tell where each leads until we traverse it. We wish to minimize the ratio of the total number of edges traversed divided by the optimum number of traversals, had we known the graph. For Eulerian graphs, this ratio cannot be better than two, and two is achievable by a simple algorithm. In contrast, the ratio is unbounded when the deficiency of the graph (the number of edges that have to be added to make it Eulerian) is unbounded. Our main result is an algorithm that achieves a bounded ratio when the deficiency is bounded. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 265–297, 1999 We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.