Planning on Infinite Completion Trees Using Markovian Multi Armed Bandits

Abstract: Task and Motion Planning (TAMP) requires generating symbolic task plans together with feasible motion plans, making it necessary to reason jointly about discrete actions, continuous motion feasibility, and the computational effort required to evaluate candidate plans. Because geometric checks are often expensive and interdependent, a TAMP solver must effectively manage the order in which it performs these computations. This challenge motivates a metareasoning viewpoint in which selecting computations becomes an integral part of the planning problem. A recent formalization captures this metareasoning problem through the infinite completion tree, where each node represents a preemptible computation that must be completed before its successors can be considered. Prior work assumed that the completion times associated with nodes in this tree were completely unknown, which forces planners to rely on blind search methods that cannot exploit regularities across problem instances. In this work, we introduce a data-driven approach for improving the efficiency of metareasoning within the infinite completion tree. Our objective is to minimize the time required to obtain the first valid TAMP solution. To do so, we formalize a metareasoning problem as a Markov Decision Process (MDP) and apply the Gittins index to obtain an optimal computation-search policy. Crucially, the dynamics of this MDP are learned from prior planning data. Empirical results across multiple TAMP benchmarks show that this learned metareasoning approach significantly outperforms blind search. Our method successfully reduces both the invested computation time and the overall wall-clock planning time required to reach the first feasible solution. These findings demonstrate that predictive models of computation behavior can effectively guide search in TAMP and highlight the potential of data-driven metareasoning for accelerating complex robotic planning tasks.