text: We investigate initial information, unbounded memory and randomization in gathering mobile agents on a grid. We construct a state machine, such that it is possible to gather, with probability 1, all configurations of its copies. This machine has initial input, unbounded memory, and is randomized. We show that no machine having any two of these capabilities but not the third, can be used to gather, with high probability, all configurations. We construct deterministic Turing Machines that are used to gather all connected configurations, and we construct deterministic finite automata that are used to gather all contractible connected configurations.
  @cite_15: 
  @cite_26: In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the network is anonymous, however, the resulting symmetry can make the problem impossible to solve. Symmetry is typically broken by having the mobile agents run either a randomized algorithm or different deterministic algorithms. We investigate the use of identical tokens to break symmetry so that the two mobile agents can run the same deterministic algorithm. After deriving the explicit conditions under which identical tokens can be used to break symmetry on the n node ring, we derive the lower and upper bounds for the time and memory complexity of the rendezvous search problem with various parameter sets. While these results suggest a possible tradeoff between the mobile agents' memory and the time complexity of the rendezvous search problem, we prove that this tradeoff is limited.
  @cite_33: We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open in a recent paper by We also introduce an interesting variant of the rendezvous problem which we call the deterministic treasure hunt problem. Both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. We call such sequences strongly universal traversal (exploration) sequences. We give an explicit construction of strongly universal exploration sequences. The existence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the deterministic treasure hunt problem, are left as intriguing open problems.
summary: For the deterministic setting, a lot of effort has been dedicated to the study of the feasibility of rendezvous, and to the time required to achieve this task, when feasible. For instance, deterministic rendezvous with agents equipped with tokens used to mark nodes was considered, e.g., in @cite_26 . Deterministic rendezvous of two agents that cannot mark nodes but have unique labels was discussed in @cite_15 @cite_33 . These papers are concerned with the time of rendezvous in arbitrary graphs. In @cite_15 the authors show a rendezvous algorithm polynomial in the size of the graph, in the length of the shorter label and in the delay between the starting time of the agents. In @cite_33 rendezvous time is polynomial in the first two of these parameters and independent of the delay.