# Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph

arXiv: https://arxiv.org/abs/2403.07748 · HTML: https://mlsanity.com/paper/2403.07748/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 12 Mar 2024.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 10 of 10)

- [The Randomized k-Server Conjecture is False!](https://mlsanity.com/paper/2211.05753/) (2022)
- [Shortest Paths without a Map, but with an Entropic Regularizer](https://mlsanity.com/paper/2202.04551/) (2022)
- [Improved Lower Bound for Competitive Graph Exploration](https://mlsanity.com/paper/2002.10958/) (2020)
- [How to Meet Asynchronously at Polynomial Cost](https://mlsanity.com/paper/1301.7119/) (2013)
- [A general lower bound for collaborative tree exploration](https://mlsanity.com/paper/1610.01753/) (2016)
- [Deterministic Rendezvous Algorithms](https://mlsanity.com/paper/2303.10391/) (2023)
- [Exploration of graphs with excluded minors](https://mlsanity.com/paper/2308.06823/) (2023)
- [Breaking the k/log k Barrier in Collective Tree Exploration via Tree-Mining](https://mlsanity.com/paper/2309.07011/) (2023)
- [Collective Tree Exploration via Potential Function Method](https://mlsanity.com/paper/2311.01354/) (2023)
- [Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs](https://mlsanity.com/paper/2402.13845/) (2024)

## Abstract (arXiv)

We investigate two fundamental problems in mobile computing: exploration and rendezvous, with two distinct mobile agents in an unknown graph. The agents may communicate by reading and writing information on whiteboards that are located at all nodes. They both move along one adjacent edge at every time-step. In the exploration problem, the agents start from the same arbitrary node and must traverse all the edges. We present an algorithm achieving collective exploration in m time-steps, where m is the number of edges of the graph. This improves over the guarantee of depth-first search, which requires 2m time-steps. In the rendezvous problem, the agents start from different nodes of the graph and must meet as fast as possible. We present an algorithm guaranteeing rendezvous in at most frac32m time-steps. This improves over the so-called `wait for Mommy' algorithm which is based on depth-first search and which also requires 2m time-steps. Importantly, all our guarantees are derived from a more general asynchronous setting in which the speeds of the agents are controlled by an adversary at all times. Our guarantees generalize to weighted graphs, when replacing the number of edges m with the sum of all edge lengths. We show that our guarantees are met with matching lower-bounds in the asynchronous setting.