# Effort Level Search in Infinite Completion Trees with Application to Task-and-Motion Planning

Paper Webpage for the ICRA 2024 submission

*Marc Toussaint, Joaquim Ortiz-Haro, Valentin N. Hartmann, Erez Karpas, Wolfgang Hönig*

Learning & Intelligent Systems Lab @ TU Berlin, Cognitive Robotics Lab @ Technion Israel, Science of Intelligence Excellence Cluster @ TU Berlin

**Paper (with appendix):** paper

**Brief:** TAMP problems are typically solved in steps, by solving a series of sub-problems. We to address the decision problem of where to invest compute when searching over possible sequences of sub-problems.

**Abstract:** Solving a Task-and-Motion Planning (TAMP)
problem can be represented as a sequential (meta-) decision
process, where early decisions concern the skeleton (sequence
of logic actions) and later decisions concern what to compute
for such skeletons (e.g., action parameters, bounds, RRT paths,
or full optimal manipulation trajectories). We consider the
general problem of how to schedule compute effort in such
hierarchical solution processes. More specifically, we introduce
infinite completion trees as a problem formalization, where
before we can expand or evaluate a node, we have to solve
a preemptible computational sub-problem of a priori unknown
compute effort. Infinite branchings represent an infinite choice
of random initializations of computational sub-problems. Deci-
sion making in such trees means to decide on where to invest
compute or where to widen a branch. We propose a heuristic to
balance branching width and compute depth using polynomial
level sets. We show completeness of the resulting solver and
that a round robin baseline strategy used previously for TAMP
becomes a special case. Experiments confirm the robustness
and efficiency of the method on problems including stochastic
bandits and a suite of TAMP problems, and compare our
approach to a round robin baseline. An appendix comparing the
framework to bandit methods and proposing a corresponding
tree policy version is found on the supplementary webpage.

**Funding:** The research has been supported by the German-Israeli Foundation for
Scientific Research (GIF), grant I-1491-407.6/2019, as well as the German Research Foundation
(DFG) under Germany’s Excellence Strategy EXC 2002/1–390523135 “Science of Intelligence”.