  Task and Motion Planning (TAMP) requires the integration of symbolic
reasoning with metric motion planning that accounts for the robot's actions'
geometric feasibility. This hierarchical structure inevitably prevents the
symbolic planners from accessing the environment's low-level geometric
description, vital to the problem's solution. Most TAMP approaches fail to
provide feasible solutions when there is missing knowledge about the
environment at the symbolic level. The incapability of devising alternative
high-level plans leads existing planners to a dead end. We propose a novel
approach for decision-making on extended decision spaces over plan skeletons
and action parameters. We integrate top-k planning for constructing an explicit
skeleton space, where a skeleton planner generates a variety of candidate
skeleton plans. Moreover, we effectively combine this skeleton space with the
resultant motion parameter 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 minimum-cost 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 manipulation tasks with different domains that require
multi-stage decisions and show how our method can overcome dead-ends through
its effective alternate plans compared to its most competitive baseline method.
