Rendezvous search on a graph

TLDR

Two agents are randomly placed on a known graph and each knows only its own position up to graph symmetries, extending prior discrete and continuous rendezvous studies. The study seeks to minimize the expected number of steps for the agents to meet, examining both identical and non‑identical strategy scenarios. Agents move each step by either staying or moving to an adjacent node, using mixed strategies to handle random initial placement and symmetry uncertainty.

Abstract

Two agents are placed randomly on nodes of a known graph. They are aware of their own position, up to certain symmetries of the graph, but not that of the other agent. At each step, each agent may stay where he is or move to an adjacent node. Their common aim is to minimize the expected number of steps required to meet (occupy the same node). We consider two cases determined by whether or not the players are constrained to use identical strategies. This work extends that of Anderson and Weber on ‘discrete locations’ (complete graph) and is related to continuous (time and space) rendezvous as formulated by Alpern. Probabilistic notions arise in the random initial placement, in the random symmetries determining spatial uncertainty of agents, and through the use of mixed strategies.