Multi-Step Strategies for Rendezvous Search on the Edges of the Platonic Solids

The astronaut problem is an open problem in the field of rendezvous search. The premise is that two astronauts randomly land on a planet and want to find one another. Research explores what strategies accomplish this in the least expected time. To investigate this problem, we create a discrete model which takes place on the edges of the Platonic solids. Some baseline assumptions of the model are: (1) The agents can see all of the faces around them. (2) The agents travel along the edges from vertex to vertex and cannot jump. (3) The agents move at a rate of one edge length per unit time. We first explore an unbiased random walk strategy where the agents move in a random direction on each turn. We then explore multi-step strategies, which are strategies where both agents move randomly for one step, and then follow a pre-determined sequence. We compare the performance of multi-step strategies and the unbiased strategy for all of the solids. For the cube and octahedron, we are able to prove optimality of the “Left Strategy”, in which the agents move in a random direction for the first step and then turn left. For a dodechedron, we prove optimality of a multi-step strategy using a lower bound for the expected meeting time. For the icosahedron, we present results for a subset of the multi-step strategies. In an effort to find lower expected times, we explore mixed strategies. Mixed strategies incorporate an asymmetric case which under certain conditions can result in lower expected times. Due to the greater complexity of calculating the expected time of mixed strategy, we again utilize lower bounds to find bounds for the optimal expected time. Most of the calculations were done using first-step decompositions for Markov chains