TLDR: This research introduces a new method for automated planning that learns generalized, probabilistic relationships between “landmarks” (necessary conditions for a plan) from multiple planning tasks. Unlike traditional methods that create task-specific landmarks, this approach generates a “Probabilistic Lifted Ordering Graph” (p-LOG) that can be reused across different planning problems within the same domain. When given a new planning task, the system instantiates this learned graph to extract relevant landmark orderings, demonstrating improved recall in identifying true landmarks compared to existing methods.
Automated planning, a core area of artificial intelligence, relies heavily on “landmarks” – crucial conditions that must be met to achieve a goal. Traditionally, extracting these landmarks has been a challenge because they are often specific to individual planning tasks. This means that for every new problem, the system has to start from scratch, limiting the reusability of learned information across different scenarios within the same domain.
A new research paper, titled “From domain-landmark graph learning to problem-landmark graph generation,” addresses this limitation by proposing a novel approach to learn and generalize landmark relationships. The authors, Cristian P ´erez-Corral, Antonio Garrido, and Laura Sebastia, introduce a method that learns from multiple planning tasks within a given domain, leading to the creation of a ‘Probabilistic Lifted Ordering Graph’ (p-LOG).
Understanding the Core Idea: Probabilistic Lifted Ordering Graphs
Imagine you’re teaching a robot to stack blocks. A classical approach might identify that “holding block A” is a landmark if the goal is “block A on block B.” However, this landmark is tied to specific blocks. The new approach generalizes this by using variables, like “holding ?x0,” where ?x0 can be any block. The p-LOG captures these generalized, or ‘lifted,’ relationships between parameterized landmarks, along with their probabilities. These probabilities indicate how often a particular ordering appears across various planning tasks in the domain. While these orderings might not be 100% true in every single plan, they are consistent in many situations and highly reusable.
The process involves three main steps for ‘domain-landmark learning’:
1. Generating Lifted Ordering Graphs (LOGs): For each individual planning task, the system first calculates its Landmark Generation Graph (LGG), which shows relationships between specific landmarks. Then, it creates a ‘lifted’ version (LOG) where specific objects are replaced by variables, making the relationships more general.
2. Generating a Weighted Lifted Ordering Graph (w-LOG): All the individual LOGs from different planning tasks are then merged. This combined graph not only shows the generalized relationships but also assigns a ‘weight’ to each relationship, indicating how many times it appeared across the dataset.
3. Generating the Probabilistic Lifted Ordering Graph (p-LOG): Finally, these weights are converted into probabilities. For example, if “on table (?x0) → holding (?x0)” appears in almost a third of the dataset, it gets a probability of 0.29. A probability of 1.0 means it appeared in every instance of the dataset.
Applying Learned Knowledge to New Problems
Once the p-LOG is built, it can be used to generate landmark orderings for a completely new planning task within the same domain. This ‘problem-landmark graph generation’ also happens in two phases:
1. Instantiating Probabilistic Landmark Generation Graphs (p-LGGs): The system generates two initial graphs, one based on the new task’s initial state (p-LGGI) and another on its goal state (p-LGGG). This involves instantiating the variables from the p-LOG with the specific objects of the new task, while also considering constraints.
2. Combining the Graphs: These two instantiated graphs are then combined into a single, unified p-LGG. This step involves finding equivalent predicates and further refining the variable instantiations to extract the final landmark orderings for the specific planning task.
Also Read:
- Reasoning Core: A Scalable Platform for Training LLMs in Foundational Logic
- A Structured Approach to Generating Comprehensive Software Repositories
Evaluation and Impact
The researchers evaluated their approach against classical landmark extraction methods, LAMA (DS1) and Keyder et al. (DS2), across 11 different planning domains. The results showed that while the new method’s execution time for instantiation was comparable to DS1 and significantly faster than DS2 (which could take hours or even days for some tasks), its main strength lies in its ability to extract more ‘true’ landmarks. In terms of ‘recall’ (the ability to find all relevant landmarks), the probabilistic approach consistently outperformed the classical methods, often extracting landmarks that DS1/DS2 failed to identify. The precision (accuracy of the extracted landmarks) was also high, exceeding 0.9 in most domains.
This work represents a significant step forward in automated planning by enabling the learning of reusable, domain-wide landmark information. While the probabilistic nature might occasionally lead to the instantiation of ‘untrue’ orderings in some domains, the overall benefit of capturing valuable, generalized knowledge and improving landmark extraction recall is substantial. The authors envision future work exploring how to safely combine different types of orders, improve precision, and use these instantiated p-LGGs as a heuristic to guide planning search more effectively. You can read the full research paper for more technical details and results here.
