Multi-Agent Pathfinding, Heuristic Algorithms, Ricochet Robots, Subgoals

In this contribution, we describe a fast heuristic for a logical game called Ricochet Robots in which multiple robots cooperate in order to reach a goal. The heuristic recursively explores a restricted search space using subgoals that correspond to interactions of two robots. Subgoals are expanded according to an estimated length of a complete solution, which makes the algorithm reminiscent of the A* algorithm. The estimated length is a lower bound of the length of the real solution, and this allows us to prune subgoals using the best solution found thus far. After eliminating all remaining subgoals, we are guaranteed that the best solution found is the shortest solution from the restricted search space. Moreover, we show that the restricted search space contains a large portion of optimal solutions of the empirical distribution of 1 million random problems. We believe that the presented ideas should generalize to other search problems in which multiple independent agents could block or help each other.