Rendezvous search on a graph

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 st eps required to meet (occupy the same node). We consider two cases determin ed by whether or not the players are constrained to use identical strategie s. This work extends that of Anderson and Weber on 'discrete locations' (co mplete graph) and is related to continuous (time and space) rendezvous as f ormulated by Alpern. Probabilistic notions arise in the random initial plac ement, in the random symmetries determining spatial uncertainty of agents, and through the use of mixed strategies.