Rendezvous Search on the Edges of Vertex-Transitive Solids

A classic "rendezvous search" problem is the "astronaut problem," in which two agents are placed on a sphere and move around until they meet. Research focuses on finding an optimal strategy for both agents to use. We consider a model that utilizes discrete units of time, with movement along the edges of vertex-transitive solids. The search ends when the two agents can see each other. We first examine the five platonic solids, then look at several larger Archimedean solids for comparison. We compare the mean times to meet on the solids under an unbiased random walk strategy, and we alter assumptions and strategies in various versions of the search to see how certain changes affect the mean time to end. One version involves the possibility of waiting on any given turn under both biased and unbiased random strategies. We also examine multi-step strategies, which involve a random step and a predetermined sequence of directions. The calculations of expected meeting times all involve first-step Markov chain decompositions