Admissible Abstractions for Near-optimal Task and Motion Planning
This work addresses the challenge of scalability in motion planning for robotics and AI, offering a method to handle large state spaces efficiently, though it is incremental in improving existing abstraction techniques.
The paper tackles the problem of accelerating optimal motion planning in continuous domains by introducing admissible abstractions with angelic semantics, which dramatically reduce search complexity while preserving optimality guarantees. The result demonstrates finding near-optimal plans in problems with up to 10^13 states without needing a separate task planner.
We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving $10^{13}$ states without using a separate task planner.