Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph
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 $\frac{3}{2}m$ 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.
Code (0)
등록된 구현이 없습니다.
Tasks
AllSimilar Papers 제목 키워드 기반
AriadneMem: Threading the Maze of Lifelong Memory for LLM Agents
Long-horizon LLM agents require memory systems that remain accurate under fixed context budgets. However, existing systems struggle with two persistent challenges in long-term dialogue: (i) \textbf{disconnected evidence}…
Energy-Aware Collaborative Exploration for a UAV-UGV Team
We present an energy-aware collaborative exploration framework for a UAV-UGV team operating in unknown environments, where the UAV's energy constraint is modeled as a maximum flight-time limit. The UAV executes a sequenc…
Project Ariadne: A Structural Causal Framework for Auditing Faithfulness in LLM Agents
As Large Language Model (LLM) agents are increasingly tasked with high-stakes autonomous decision-making, the transparency of their reasoning processes has become a critical safety concern. While \textit{Chain-of-Thought…
Aperiodic Communication for MPC in Autonomous Cooperative Landing
This paper investigates the rendezvous problem for the autonomous cooperative landing of an unmanned aerial vehicle (UAV) on an unmanned surface vehicle (USV). Such heterogeneous agents, with nonlinear dynamics, are dyna…
Model Predictive ControlMulti-agent rendezvous in fluid flows via reinforcement learning
Rendezvous is a critical task for multi-agent systems, requiring agents to coordinate to meet at an unspecified location. However, achieving this in fluid environments presents a challenge, as it remains unclear how agen…
Multi-agent Reinforcement Learning