Ω2: Optimal Hierarchical Planner for Object Search in Large Environments via Mobile Manipulation

Abstract

We propose a hierarchical planning algorithm that efficiently computes an optimal plan for finding a target object in large environments where a robot must simultaneously consider both navigation and manipulation. One key challenge that arises from large domains is the substantial increase in search space complexity that stems from considering mobile manipulation actions and the increase in number of objects. We offer a hierarchical planning solution that effectively handles such large problems by decomposing the problem into a set of low-level intra-container planning problems and a high-level key place planning problem that utilizes the low-level plans. To plan optimally, we propose a novel admissible heuristic function that, unlike previous methods, accounts for both navigation and manipulation costs. We propose two algorithms: one based on standard A∗ that returns the optimal solution, and the other based on Anytime Repairing A∗ (ARA*) which can trade-off computation time and solution quality, and prove they are optimal even when we use hierarchy. We show our method outperforms existing algorithms in simulated domains involving up to 6 times more number of objects than previously handled.