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
1516427227 1972775782 2160504298 1543762072
Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active “searcher”, which both executes the algorithm and holds the memory, and the passive “searched graph”, over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavilydloaded, call for a different paradigm, in which most of the burden of computing and memorizing is moved from the searching agent to the nodes of the network. In this paper we suggest a method for searching an undirected, connected graph using the VertexdAntdWalk method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving “pheromone” traces at nodes, and using those traces to guide its exploration. We show that the ant can cover the graph within time O (nd), where n is the number of vertices and d the diameter of G. The use of traces achieves a tradedoff between random and selfdavoiding walks, as it dictates a lower priority for alreadydvisited neighbors. Further properties of the suggested method are: (a) modularity: a group of searching agents, each applying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between thems (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit cycle of the process. Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph. 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. We study the problem of gathering at the same location two mobile agents that are dispersed in an unknown and unlabeled environment. This problem called Rendezvous, is a fundamental task in distributed coordination among autonomous entities. Most previous studies on the subject model the environment as an undirected graph and the solution techniques rely heavily on the fact that an agent can backtrack on any edge it traverses. However, such an assumption may not hold for certain scenarios, for instance a road network containing one-way streets. Thus, we consider the case of strongly connected directed graphs and present the first deterministic solution for rendezvous of two anonymous (identical) agents moving in such a digraph. Our algorithm achieves rendezvous with detection for any solvable instance of the problem, without any prior knowledge about the digraph, not even its size.