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”.