Graph Learning for Planning: The Story Thus Far and Open Challenges
2024
Read Graph Learning for Planning: The Story Thus Far and Open Challenges (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-02136.txt.
Introduction
Dillon Chen, Mingyu Hao, Sylvie Thiébaux, and Felipe Trevizan present a 2024 survey of graph learning for planning tasks. Planning means finding a step order that reaches a goal, a task full of links between objects. Graph learning fits that shape well, since it reads links and handles any count of objects. Their survey asks how choices in setup change both learning and planning results.
Three choice lines get the focus: how a task becomes a graph, which network design learns from it, and how training is set up. The work ties into the team's GOOSE frame, which learns from small tasks to solve far larger ones. The authors close with five open challenges for the wider field. Their map shows where graph methods help planners and where the hard problems sit.
Catalog record
| YEAR | 2024 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-02136
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Learning for Planning: The Story Thus Far and Open Challenges Abstract Graph learning is naturally well suited for use in planning due to its ability to exploit relational structures exhibited in planning domains and to take as input planning instances with arbitrary number of objects. In this paper, we study the usage of graph learning for planning thus far by studying the theoretical and empirical effects on learning and planning performance of (1) graph representations of planning tasks, (2) graph learning architectures, and (3) optimisation formulations for learning. Our studies accumulate in the GOOSE framework which learns domain knowledge from small planning tasks in order to scale up to much larger planning tasks. In this paper, we also highlight and propose the 5 open challenges in the general Learning for Planning field that we believe need to be addressed for advancing the state-of-the-art. 1 LAAS-CNRS, University of Toulouse 2 The Australian National University [email protected] 1 Introduction Learning for Planning (L4P) has gained significant interest in recent years due to advancements of machine learning (ML) approaches across various fields, and also because planning is one of the few problems in AI that has been unsolved by deep learning and large models VMH+ (23) ; VMSK (23) ; VSK (24) . An aim of L4P involves designing automated, domain-independent algorithms for learning domain knowledge from small training problems for scaling up planning to problems of arbitrary size CdlRF+ (12) ; TTTX (18) ; TTTX (20) ; DML+ (19) ; STT (20) ; KS (21) ; SBG (22) ; SBG (23) ; MLTK (23) ; CTT24a () ; CTT24b () ; WT (24) ; HTT+ (24) ; CT24a () . Planning tasks can exhibit arbitrary numbers of objects and are represented with relational languages which begs for the use of learning approaches that operate on relational structures such as graphs. In this paper, we recount the story so far for graph learning for planning. This will be done by studying the contributions in the literature and of the authors thus far regarding the three main components of graph learning for planning as summarised in Fig. 1 : (1) graph representations of planning tasks, (2) graph learning architectures, and (3) optimisation formulations for learning. On the experimental side, we present the GOOSE 1 1 1 G raphs O ptimised f O r S earch E valuation; code available at https://github.com/DillonZChen/goose learning framework for leveraging graph learning for planning. A B C D E F initial state i j k B A goal condition i j k A B D x y on(a,x) on(a,b) on(b,x) on(b,y) on(d,b) capacity(x) capacity(y) A B D x y on(a,x) on(a,b) on(b,x) on(b,y) on(d,b) capacity(x) capacity(y) \mathbb{R}^{d} (1) (2) (3) 10 5 5 10 -5 5 > > \geq \geq \geq Figure 1: Typical graph learning for planning pipeline. (1) Planning tasks are represented as graphs. (2) Graph learning architectures are used to embed graphs. (3) Learning is performed via some optimisation criteria suited for making predictions in planning. This paper summarises previous CTT24a () ; CTT24b () ; HTT+ (24) ; CT24a () and current theoretical and experimental work by the authors. The paper is structured by introducing the general L4P problem setup in Section 2 and the formal background and definitions in Section 3 . Next, we highlight contributions of the authors in graph learning for planning, summarised as follows: (1) We provide a taxonomy and theoretical comparison of graph representations of planning tasks and their expressive power with graph learning approaches. (Section 4 ) (2) We introduce a classical ML approach which outperforms deep learning methods by several orders of magnitude for planning over various metrics. (Section 5 ) (3) We present optimisers better suited for learning for planning by representing heuristic functions as rankings of states rather than cost-to-go estimates. (Section 6 ) Section 7 quantifies the contributions of our work by showcasing experimental results. We conclude by highlighting open problems and challenges for the general L4P field in Section 8 , and avenues for future work in the field. 2 Learning for Planning Here we briefly introduce and describe the general Learning for Planning (L4P) problem statement. The problem setup of L4P involves learning knowledge from a set of training problems in either a supervised, unsupervised, or reinforcement learning fashion that may be helpful for planning. This is in contrast to planning for each individual problem from scratch in typical planning setups GB (13) , and learning to solve a specific problem instance from rewards typical in task-specific reinforcement learning SB (98) or across different initial states FGT+ (22) . Furthermore, as illustrated in Fig. 2 , L4P aims to generalise across an arbitrary number of objects in the planning domain, as opposed to transfer learning across similar-sized tasks or task-specific reinforcement learning. The primary objective of L4P is that by performing either few-shot training or bootstrapping, we can scale up to much larger planning tasks which domain-independent planners cannot handle due to no free lunch. We define an L4P problem as any tuple \left<\mathcal{D},\mathcal{T}_{\text{train}},\mathcal{T}_{\text{test}}\right> where \mathcal{D} is a domain characterising a class of planning tasks, \mathcal{T}_{\text{train}} is a finite set of training tasks from \mathcal{D} , and \mathcal{T}_{\text{test}} is a (possibly infinite) set of testing tasks from \mathcal{D} . An L4P solution is defined as a set of plans corresponding to problems in \mathcal{T}_{\text{test}} . L4P opens a rich array of possibilities for how one may come up with algorithms for solving the problem, and methods for evaluating such algorithms. We can characterise an L4P algorithm as an algorithm with two components: (1) a learner module , whose input is \mathcal{D} and \mathcal{T}_{\text{train}} and output is a knowledge artifact, and (2) a planner module , whose input is a task from \mathcal{T}_{\text{test}} and the knowledge artifact, and output is a plan. train = test train size = test size train size \subset test size \vdots Figure 2: Visualisations of generalisation setups for planning and RL. The axis represents the number of objects in a planning task. Standalone planning and RL commonly follow the task-specific setup (left), with some RL approaches generalising across similar-sized tasks (middle). L4P approaches primarily focuses on generalisation across arbitrary numbers of objects (right). Fig. 3 illustrates the general L4P setup and pipeline. The learner module learns from the training tasks and uses the domain as prior knowledge to produce a knowledge artifact, which can then be used by a planner module to plan for arbitrary tasks from \mathcal{T}_{\text{test}} . Common knowledge artifacts include heuristic or value functions, and global policies. \mathcal{D} \mathcal{T}_{\text{train}} \mathcal{T}_{\text{test}} learner knowledge planner task plan Figure 3: The general Learning for Planning (L4P) setup. 3 Background In this section, we provide the technical background and formalisms of planning used in works described in the paper. However, they may be skipped upon first read as they are not entirely necessary for a majority of the paper. 3.1 Planning Task Let \left[\!\left[n\right]\!\right] denote the set of integers \left\{1,\ldots,n\right\} . A planning task can be understood as a state transition model GB (13) given by a tuple \Pi=\left<S,A,s_{0},G\right> where S is a set of states, A a set of actions, s_{0}\in S an initial state, and G\subseteq S a