Extended Tree Search for Robot Task and Motion Planning

Abstract

Integrated Task and Motion Planning (TAMP) offers 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 addressing geometrically infeasible actions within its hierarchical process. We introduce a novel TAMP decision-making framework, 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 powerful 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.