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

arXiv 2403.07748 ↗First posted 12 Mar 2024cs.MA cs.AIcited by 0

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

10 of 42 references.

References · 10

2022The Randomized k-Server Conjecture is False!cited by 8
2022Shortest Paths without a Map, but with an Entropic Regularizercited by 4
2020Improved Lower Bound for Competitive Graph Explorationcited by 2
2013How to Meet Asynchronously at Polynomial Costcited by 1
2016A general lower bound for collaborative tree explorationcited by 1
2023Deterministic Rendezvous Algorithmscited by 1
2023Exploration of graphs with excluded minorscited by 1
2023Breaking the k/log k Barrier in Collective Tree Exploration via Tree-Miningcited by 1
2023Collective Tree Exploration via Potential Function Methodcited by 1
2024Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way