Lifelong Learning (to Plan) by Abstraction

Overview

This project opens the door to an exciting, novel direction in robotics research. Its goal is to unlock a human-like capability in long-lived robots, allowing them to autonomously and improve their problem-solving capabilities throughout their lifetime. To achieve this, we developed a new paradigm for robot learning, called Lifelong Learning by Abstraction (LLbA). This paradigm does not involve statistical learning nor training of policies by trial and error before deployment. Instead, here, learning is done after deployment, by gradually, from one problem to the next, enriching the planner with useful, generalized conclusions, automatically extracted from individual successful experiences; these can later be dynamically matched to, adapted for, and reused in new planning problems, to guide and accelerate their solution. Thus far, we applied this paradigm in the context of geometric path-finding, symbolic task (“AI”) planning (commonly defined in PDDL), and multi-manipulator object rearrangement. Work-in-progress seeks to apply this to various additional contexts, including motion planning for high degree-of-freedom robot arms, and Multi-Agent Path Finding (MAPF).

Unpacking

With a series of publications, we built the theoretical and computational framework underpinning this paradigm. The first paper (Elimelech et al., 2022) introduced the theoretical basis for transfer by abstraction and showed that solutions of successful planning experiences can be abstracted into reusable “planning strategies,” encoded as “Abstract Road Maps (ARMs)”. The second paper (Elimelech et al., 2022) took this into a practical direction and formulated basic algorithms for strategy-accelerated planning, given a library of such planning strategies (encoded as ARMs). The third paper (Elimelech et al., 2023), complementary to the second one, presented practical algorithms for automatically abstracting solution paths into ARMs, i.e., building the planning-strategy library; this importantly introduced the idea of path segmentation through Abstraction Critical State Detection (ACSD). The second and third papers were presented in the context of geometric path-finding problems. The fourth paper (Elimelech et al., 2024), acted as direct continuation of the second one; where the earlier work only leveraged a single strategy from the library in each new solution (meaning, learning to solve similar problems), the strategy-accelerated planning algorithm presented here allowed for chaining multiple strategies, in order to find the complete solution (meaning, learning to solve harder problems, by combining experiences). This paper was presented in the context of task planning, in a “Blocksworld” PDDL domain.

New work (Elimelech et al., 2024) suggested this paradigm applies naturally to multi-manipulator object rearrangement problems, by integrating with the multi-robot planning framework DaSH (for hypergraph-based multi-robot planning).

A sequence of increasingly-harder tower rearrangement planning problems.

Note. This paper series is currently being compiled into a single comprehensive publication. A preprint is expected to be released soon.

Note. Thanks to feedback from the community, some of the terminology has been revised throughout the lifetime of this project, in order to avoid confusion. Earlier publications used the term “abstract skills” to refer to the learned objects; this was later revised to “abstract strategies.” Further, the usage of the terms “public/private abstraction key” was dropped; current work simply use the term “abstraction key.”

References

2024

Conference
Accelerating Long-Horizon Planning with Affordance-Directed Dynamic Grounding of Abstract Strategies

Khen Elimelech, Zachary Kingston, Wil Thomason, Moshe Y. Vardi, and Lydia E. Kavraki

In IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan, May 2024

Abs Bib

Long-horizon task planning is important for robot autonomy, especially as a subroutine for frameworks such as Integrated Task and Motion Planning. However, task planning is computationally challenging and struggles to scale to realistic problem settings. We propose to accelerate task planning over an agent’s lifetime by integrating abstract strategies: a generalizable planning experience encoding introduced in earlier work. In this work, we contribute a practical approach to planning with strategies by introducing a novel formalism of planning in a strategy-augmented domain. We also introduce and formulate the notion of a strategy’s affordance, which indicates its predicted benefit to the solution, and use it to guide the planning and strategy grounding processes. Together, our observations yield an affordance-directed, lazy-search planning algorithm, which can seamlessly compose strategies and actions to solve long-horizon planning problems. We evaluate our planner in an object rearrangement domain, where we demonstrate performance benefits relative to a state-of-the-art task planner.
@inproceedings{Elimelech24icra, bibtex_show = true, author = {Elimelech, Khen and Kingston, Zachary and Thomason, Wil and Vardi, Moshe Y. and Kavraki, Lydia E.}, author+an = {1=KE}, title = {Accelerating Long-Horizon Planning with Affordance-Directed Dynamic Grounding of Abstract Strategies}, booktitle = {{IEEE} International Conference on Robotics and Automation ({ICRA})}, year = {2024}, month = may, location = {Yokohama, Japan} }
Workshop
Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs

Khen Elimelech, James Motes, Marco Morales, Nancy M. Amato, Moshe Y. Vardi, and Lydia E. Kavraki

In 40th Anniversary of the IEEE International Conference on Robotics and Automation (ICRA@40), Rotterdam, Netherlands, Sep 2024

Abs Bib

Multi-Robot Task Planning (MR-TP) is the search for a discrete-action plan a team of robots should take to complete a task. The complexity of such problems scales exponentially with the number of robots and task complexity, making them challenging for online solution. To accelerate MR-TP over a system’s lifetime, this work looks at combining two recent advances: (i) Decomposable State Space Hypergraph (DaSH), a novel hypergraph-based framework to efficiently model and solve MR-TP problems; and (ii) learning-by-abstraction, a technique that enables automatic extraction of generalizable planning strategies from individual planning experiences for later reuse. Specifically, we wish to extend this strategy-learning technique, originally designed for single-robot planning, to benefit multi-robot planning using hypergraph-based MR-TP.
@inproceedings{Elimelech24icra40, bibtex_show = true, author = {Elimelech, Khen and Motes, James and Morales, Marco and Amato, Nancy M. and Vardi, Moshe Y. and Kavraki, Lydia E.}, author+an = {1=KE+jointfirst;2=jointfirst}, title = {Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs}, booktitle = {40th Anniversary of the IEEE International Conference on Robotics and Automation (ICRA@40)}, year = {2024}, month = sep, location = {Rotterdam, Netherlands}, keywords = {workshop} }

2023

Conference
Extracting generalizable skills from a single plan execution using abstraction-critical state detection

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In IEEE International Conference on Robotics and Automation (ICRA), London, UK, May 2023

Abs Bib

Robotic task planning is computationally challenging. To reduce planning cost and support life-long operation, we must leverage prior planning experience. To this end, we address the problem of extracting reusable and generalizable abstract skills from successful plan executions. In previous work, we introduced a supporting framework, allowing us, theoretically, to extract an abstract skill from a single execution and later automatically adapt it and reuse it in new domains. We also proved that, given a library of such skills, we can significantly reduce the planning effort for new problems. Nevertheless, until now, abstract-skill extraction could only be performed manually. In this paper, we finally close the automation loop and explain how abstract skills can be practically and automatically extracted. We start by analyzing the desired qualities of an abstract skill and formulate skill extraction as an optimization problem. We then develop two extraction algorithms, based on the novel concept of abstraction-critical state detection. As we show experimentally, the approach is independent of any planning domain.
@inproceedings{Elimelech23icra, bibtex_show = true, author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.}, author+an = {1=KE}, title = {Extracting generalizable skills from a single plan execution using abstraction-critical state detection}, booktitle = {{IEEE} International Conference on Robotics and Automation ({ICRA})}, year = {2023}, month = may, location = {London, UK} }

2022

Conference
Automatic cross-domain task plan transfer by caching abstract skills

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In Workshop on the Algorithmic Foundations of Robotics (WAFR), College Park, MD, USA, Jun 2022

Abs Bib

Solving realistic robotic task planning problems is computationally demanding. To better exploit the planning effort, and reduce the future planning cost, it is important to increase the reusability of successful plans. To this end, we suggest a systematic and automatable approach for plan transfer, by rethinking the plan caching procedure. Specifically, instead of caching successful plans in their original domain, we suggest transferring them upon discovery to a dynamically-defined abstract domain, and cache them as "abstract skills" there. This technique allows us to maintain a unified, standardized, and compact skill database, to avoid skill redundancy, and to support lifelong operation. Cached skills can later be reconstructed into new domains on demand, and be applied to new tasks, with no human intervention. This is made possible thanks to the novel concept of "abstraction keys". An abstraction key, when coupled with a skill, provides all the necessary information to cache it, reconstruct it, and transfer it across all domains in which it is applicable – even domains we have yet to encounter. We practically demonstrate the approach by providing two examples of such keys, and explain how they can be used in a manipulation planning domain.
@inproceedings{Elimelech22wafr, bibtex_show = true, author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.}, author+an = {1=KE}, title = {Automatic cross-domain task plan transfer by caching abstract skills}, booktitle = {Workshop on the Algorithmic Foundations of Robotics ({WAFR})}, year = {2022}, month = jun, location = {College Park, MD, USA} }
Conference
Efficient task planning using abstract skills and dynamic road map matching

Khen Elimelech, Lydia E. Kavraki, and Moshe Y. Vardi

In International Symposium on Robotics Research (ISRR), Geneva, Switzerland, Sep 2022

Abs Bib

Task planning is the problem of finding a discrete sequence of actions to achieve a goal. Unfortunately, task planning in robotic domains is computationally challenging. To address this, in our prior work, we explained how knowledge from a successful task solution can be cached for later use, as an “abstract skill." Such a skill is represented as a trace of states (“road map") in an abstract space and can be matched with new tasks on-demand. This paper explains how one can use a library of abstract skills, derived from past planning experience, to reduce the computational cost of solving new task planning problems. As we explain, matching a skill to a task allows us to decompose it into independent sub-tasks, which can be quickly solved in parallel. This can be done automatically and dynamically during planning. We begin by formulating this problem of “planning with skills" as a constraint satisfaction problem. We then provide a hierarchical solution algorithm, which integrates with any standard task planner. Finally, we experimentally demonstrate the computational benefits of the approach for reach-avoid tasks.
@inproceedings{Elimelech22isrr, bibtex_show = true, author = {Elimelech, Khen and Kavraki, Lydia E. and Vardi, Moshe Y.}, author+an = {1=KE}, title = {Efficient task planning using abstract skills and dynamic road map matching}, booktitle = {International Symposium on Robotics Research ({ISRR})}, year = {2022}, month = sep, location = {Geneva, Switzerland} }