Introduction
Classical AI planning typically operates within a closed-world assumption where the set of objects is fixed and finite. However, modern knowledge-intensive systems—such as business process management suites and database-driven agents—frequently operate in open environments. In these settings, actions can introduce an infinite stream of new individuals, such as new customer IDs, sensor readings, or tracking numbers. This paper addresses the challenge of automated planning in Knowledge and Action Bases (KABs), which combine the expressive power of Description Logics (DLs) with dynamic actions.
The primary obstacle in KAB planning is undecidability: when actions can continuously introduce "fresh" objects from an infinite domain, the state space becomes unbounded. This research identifies the conditions under which planning remains decidable and provides a practical framework for synthesizing plans in these complex environments.
The Framework: Explicit-Input KABs (eKABs)
The authors introduce Explicit-Input KABs (eKABs), a variant where external data inputs are made explicit in the action signatures. An eKAB consists of a description logic knowledge base that maintains the system's state and a set of actions that evolve that state. To manage the complexity of logical reasoning, the framework often utilizes the DL-Lite family of description logics, which is specifically designed for efficient data access and is widely used in industrial applications.
Methodology: Decidability through State-Boundedness
The core theoretical contribution of the paper is the identification of state-boundedness as a sufficient condition for decidability.
1. State-Boundedness
A system is considered state-bounded if, although the total number of objects encountered over the system's lifetime may be infinite, the number of objects involved in any single state is bounded by a constant $b$. This ensures that the "memory" of the system at any given point is finite, preventing the infinite accumulation of information that typically leads to undecidability.
2. Finite-State Abstraction
To handle the infinite domain of potential objects, the authors employ a "lifting" technique. They demonstrate that the infinite world can be mapped onto a sufficiently large but finite set of abstract objects. By proving that a plan exists in this finite abstract space if and only if one exists in the infinite space, the researchers reduce a potentially infinite problem to a finite one.
3. ADL Compilation (LEKAB2ADL)
To bridge the gap between theoretical logic and practical application, the authors developed LEKAB2ADL. This tool compiles eKAB problems into the Action Description Language (ADL), a standard format compatible with high-performance classical planners. A key component of this compilation is FO-rewritability, which allows complex logical queries about the state to be transformed into simple first-order logic formulas. These formulas can be evaluated directly against the state, bypassing the need for computationally expensive theorem proving during the planning process.
Empirical Evaluation
The researchers evaluated their approach using a synthetic benchmark based on a company management scenario involving hiring, task assignment, and record anonymization. The compiled ADL problems were solved using the FastDownward planner.
Key results include:
- Complexity: The plan existence problem for state-bounded eKABs was proven to be PSPACE-complete, placing it in the same complexity class as standard classical planning despite the added logical richness.
- Performance: The system demonstrated high efficiency for moderate bounds. With 9 domain elements (~2,000 atoms), plans were found in under 1 second. At 30 domain elements (~300,000 atoms), the solver required 120 seconds.
- Scalability Limits: The system reached a timeout at 35 elements (~1.2 million atoms), highlighting that while the approach is sound, the state-space explosion remains a significant hurdle as the object bound increases.
Insights and Future Work
The research demonstrates that plan synthesis in knowledge-intensive systems is feasible if the number of objects per state is controlled. Instead of generating plans with specific, hard-coded IDs, the algorithm produces plan templates. These templates can be instantiated "online" with available fresh IDs during execution, provided they satisfy the underlying logical constraints.
Future work aims to address current limitations, such as the strict requirement for state-boundedness and the performance challenges associated with high object counts. Potential avenues include integrating optimization strategies from logic programming languages like Golog and exploring nuanced "open-world" reasoning while maintaining the decidability boundaries established in this study.
Summary updated