Model-Based Attention for Scalable AI Planning (MBASAP)

Planning is one of the core challenges in Artificial Intelligence. Developing systems that can achieve complex goals autonomously requires the capability to find a sequence of actions that accomplishes these goals. While recent advances in generative AI, such as Large Language Models, have shown outstanding performance in many applications, they still fail to solve even simple planning problems. AI planning in the form of model-based reasoning has focused on enabling such capabilities for many years, but, in practice, existing solutions often fail to scale to larger problems of industrial size. The aim of this project is to leverage novel attention mechanisms to overcome this limitation by learning to identify which parts of the planning task are relevant to achieve the desired goals.

Background

The ultimate objective of AI planning is to enable an autonomous system to achieve possibly complex goals by the means of automated sequential decision making. Given a model of its environment, the system shall figure out on its own which actions to take to achieve the goals. Most modern planning systems employ a two-phase approach to solve planning tasks. In the first phase, a lifted first-order representation of the task is transformed into a grounded propositional model that the planners work with internally. This transformation, referred to as grounding, is shared by many symbolic methods. The second phase then applies the actual reasoning to find a plan, i.e., a sequence of actions that achieves the goals. A major drawback of this two-phase approach is that the grounded representation can be exponentially larger than the lifted model. In the extreme case where the grounded model exceeds the available memory, the planner cannot even attempt to solve the task.

The aim of this project is to adapt the grounding phase such that only those parts of a planning task are grounded that are essential to find a solution. We propose to leverage modern machine learning techniques like attention to achieve this. The key idea is to prioritize those parts during grounding that the model predicts to be relevant for finding a plan and skip irrelevant parts. The second phase then runs on a partially grounded task. Many industrial applications do indeed lead to planning models for which grounding is the bottleneck. Optimizing the traffic flow in a large city is such a scenario. With a large number of intersections, growing capabilities to observe the current traffic (e.g., cameras and car-to-infrastructure communication), the planning models that control the traffic lights become increasingly complex and hard to ground. In software-defined networking (SDN), one of the major challenges is to improve the reliability and service availability of huge networks. Upon failure, the system should be able to self-heal, i.e., reconfigure itself to compensate for, e.g., a broken link.

We aim to tackle three main scientific challenges within this project.

Knowledge Representation for Attention Mechanisms

A key aspect of the project is to obtain accurate estimators that can distinguish between relevant and irrelevant parts of a planning task. The first step towards learning such estimators is to develop suitable representations for this kind of knowledge. In planning, the lifted model provides structure to the input of the model that can be exploited for this purpose. We will analyze the expressiveness of logic-based features to describe task properties for relevance prediction. We will explore lifted representations to obtain graph structures usable in graph neural networks (GNNs), extending established integrations of symbolic models. GNNs and graph transformers are of special interest for our approach, since we have the structured models in the lifted planning formalism. We will also explore traditional learning methods, extending our previous work in the spirit of employing human-interpretable techniques, which are less data-hungry and allow for a more targeted and efficient feature generation. The main outcome of this sub-project is a framework in which the relevant parts of planning tasks that are essential to achieve the goals can be identified reliably.

Robustness & Feedback Loop

As the overall planning approach becomes incomplete with partial grounding, we will look into methods that enhance the reliability of the system. We will derive measures that allow characterizing the robustness of partial models. A criterion based on a common relaxation has already been implemented. We will generalize this to more informed abstractions, and train models to estimate robustness. Furthermore, the question arises if we can learn from a failed second phase. If the partial model does not contain a solution, we can incorporate information from the search phase to improve the next iteration. Assuming that the goal is reachable under the relaxation but not in the real semantics, one can identify conflicts in the model that hint at the causes for unsolvability. We will implement methods based on counter-example guided abstraction refinement, explainable AI, and diagnosis to find explanations, and possible repairs, for unsolvability.

Expressive Planning Formalisms

Our initial work on partial grounding is in the scope of classical planning, a formalism in which actions cause deterministic effects to a fully observable environment. Many applications, however, lack these properties and require more complex models. Such models are well-known in the planning community and similar techniques are employed to find solutions. Once our system is more mature and progress has been made towards a scalable partial-grounding planner, we will tackle more expressive planning formalisms such as numeric planning, which allows for complex arithmetic expressions in actions, and non-deterministic planning, where, e.g., actions can fail and lead to undesired outcomes. These settings offer a more natural and compact way to model the applications in dynamic traffic control and autonomous computer networks.

PI: Daniel Gnad

Funding: This project is partially supported by the Zenith research organization from the Faculty of Science and Engineering at Linköping University.

Industry Support: This project is supported by SICK Sensor Intelligence and the Swedish National Road and Transport Research Institute