TLDR: A new research paper introduces ‘generalized landmarks’ for automated planning, which learn high-level, reusable goals from solved problem instances. Unlike traditional landmarks tied to specific objects, these generalize across entire problem domains using first-order functions. The method creates a ‘generalized landmark graph’ that includes loops to represent repetitive subplans, allowing it to efficiently handle varying numbers of objects. This approach, which requires only a few training examples, significantly improves planning performance for larger instances by providing long-term guidance to AI planners.
Automated planning is a cornerstone of artificial intelligence, enabling systems to devise sequences of actions to achieve specific goals. However, real-world problems often present significant challenges due to their complexity and the sheer size of the search space for possible solutions. A long-standing technique to tackle this has been the use of ‘landmarks’ – facts that must be true at some point in any successful plan.
Traditionally, these landmarks have been tied to specific problem instances and their unique objects. For example, in a delivery scenario, a traditional landmark might state that ‘truck T1 must carry package P1’. If the problem changes to involve package P2 or a different truck, these landmarks become irrelevant, requiring a complete re-computation. This approach struggles with generalization, especially when dealing with problems that have many similar objects or varying numbers of objects.
Introducing Generalized Landmarks
A new research paper, titled “Revisiting Landmarks: Learning from Previous Plans to Generalize over Problem Instances,” proposes a novel framework for ‘generalized landmarks’ that overcome these limitations. Authored by Issa Hanou, Sebastijan Dumančić, and Mathijs de Weerdt from Delft University of Technology, this work introduces a more expressive language for defining landmarks. Instead of being tied to specific objects like ‘package P1’, generalized landmarks use first-order functions to capture broader concepts, such as ‘carrying any package’. This means a single generalized landmark can apply to all packages in a delivery problem, regardless of their specific names or quantity.
These generalized landmarks are not extracted from problem definitions like their traditional counterparts. Instead, they are ‘discovered’ from a set of already solved problem instances and their corresponding plans. By analyzing the sequence of states visited during successful plan executions, the system identifies intermediate goals that are common across different problems within the same domain. This learning-based approach allows the system to capture human-like reasoning, such as the universal truth that ‘any object needs to be picked up before it can be placed at a different location’.
The Generalized Landmark Graph with Loops
A key innovation is the construction of a ‘directed generalized landmark graph’. This graph not only defines the order in which generalized landmarks should be achieved but also incorporates ‘loop possibilities’. Loops are crucial for representing repetitive subplans, such as delivering multiple packages. For instance, the sequence of ‘get to a package’, ‘pick up the package’, ‘go to the target location’, and ‘drop the package’ can be represented as a loop that is traversed for each package needing delivery. This significantly condenses the representation and allows the system to generalize over varying numbers of objects within an instance.
To ensure these loops are traversed correctly, the framework introduces ‘loop conditions’. These conditions include an ‘exit condition’ to determine when the repetition is complete (e.g., all packages are delivered) and a ‘state progression condition’ to verify that each traversal of the loop represents a meaningful step forward (e.g., a new package has been delivered). A ‘loop landmark counter’ is also used, calculated in the initial state, to predict how many times a loop can be traversed, providing an estimate of the problem’s size and expected plan length.
Also Read:
- Efficient Planning for Deterministic Multi-Agent Systems
- Navigating Complex Tasks with Tree-Guided Diffusion
Enhancing Automated Planning
The practical application of generalized landmarks comes in the form of a new heuristic, the ‘generalized landmark counting heuristic (LMG)’. This heuristic adapts traditional landmark counting by incorporating the progression and loop traversal logic of the generalized landmark graph. Because generalized landmarks provide high-level, long-horizon guidance, they are often combined with other heuristics that offer more immediate, short-term direction during the planning search.
The research demonstrates that generalized landmark graphs learned from just a few small problem instances can be highly effective for solving much larger and more complex instances within the same domain. When a loop indicating repetition is identified, the LMG heuristic shows significant improvements in performance, reducing the number of expanded states required to find a solution. This suggests that the approach effectively captures abstract, interpretable domain information from limited training data.
In summary, generalized landmarks offer several advantages over traditional methods: they generalize across an entire domain, need to be computed only once, scale from small to large instances, and capture more general relations within a planning domain, acting as an abstract plan. This work opens new avenues for more efficient and interpretable automated planning, particularly in complex, real-world scenarios. For more in-depth technical details, you can read the full paper here.
