Extended Tree Search for Robot Task and Motion Planning

Integrated Task and Motion Planning (TAMP) of- fers opportunities for achieving generalized autonomy in robots but also poses challenges. It involves searching in both symbolic task space and high-dimensional motion space, while also ad- dressing geometrically infeasible actions within its hierarchical process. We introduce a novel TAMP decision-making frame- work, utilizing an extended decision tree for both symbolic task planning and high-dimensional motion variable binding. Employing top-k planning, we generate a skeleton space with diverse candidate plans, seamlessly integrating it with motion variable spaces into an extended decision space. Subsequently, Monte-Carlo Tree Search (MCTS) is utilized to maintain a balance between exploration and exploitation at decision nodes, ultimately yielding optimal solutions. Our approach combines symbolic top-k planning with concrete motion variable binding, leveraging MCTS for proven optimality, resulting in a power- ful algorithm for handling combinatorial complexity in long- horizon manipulation tasks. Empirical evaluations demonstrate the algorithm’s effectiveness in diverse, challenging robot tasks, in comparison with the baseline methods.