Extended Tree Search for Robot Task and Motion Planning
  Integrated task and motion planning (TAMP) is desirable for generalized
autonomy robots but it is challenging at the same time. TAMP requires the
planner to not only search in both the large symbolic task space and the
high-dimension motion space but also deal with the infeasible task actions due
to its intrinsic hierarchical process. We propose a novel decision-making
framework for TAMP by constructing an extended decision tree for both symbolic
task planning and high-dimension motion variable binding. We integrate top-k
planning for generating explicitly a skeleton space where a variety of
candidate skeleton plans are at disposal. Moreover, we effectively combine this
skeleton space with the resultant motion variable spaces into a single extended
decision space. Accordingly, we use Monte-Carlo Tree Search (MCTS) to ensure an
exploration-exploitation balance at each decision node and optimize globally to
produce optimal solutions. The proposed seamless combination of symbolic top-k
planning with streams, with the proved optimality of MCTS, leads to a powerful
planning algorithm that can handle the combinatorial complexity of long-horizon
manipulation tasks. We empirically evaluate our proposed algorithm in
challenging robot tasks with different domains that require multi-stage
decisions and show how our method can overcome the large task space and motion
space through its effective tree search compared to its most competitive
baseline method.
