OBDD-Based Planning with Real-Valued Variables in Non-Deterministic Environments

AAAI 1999

TL;DR

This paper introduces a novel approach to AI planning that tackles the complexity of non-deterministic actions and real-valued state spaces, common in dynamic real-world scenarios. By leveraging Ordered Binary Decision Diagrams (OBDDs), the authors propose a method to represent and reason about these challenging domains more efficiently than traditional planning techniques.

What Problem Does This Paper Address?

Traditional AI planning methods often struggle with domains that are both non-deterministic (where actions can have multiple possible outcomes) and involve real-valued variables (like continuous positions or quantities). Existing approaches either simplify these domains by treating real variables as discrete booleans, losing crucial information, or resort to explicit enumeration, which quickly leads to an unmanageable "state explosion." This paper aims to bridge this gap by developing a planner that can effectively handle both non-determinism and real-valued variables without these limitations.

Methods

The core of the proposed method is the use of Ordered Binary Decision Diagrams (OBDDs). OBDDs are a data structure well-suited for representing Boolean functions and have been successfully applied in logic synthesis and computer-aided verification. The authors propose extending their use to model non-deterministic domains and plans. They leverage prior work on un-interpreted functions to interpret real variables within the OBDD framework, allowing them to be reasoned about directly without explicit enumeration or lossy boolean approximations. This approach enables the representation of state diagrams and the analysis of satisfiable paths, where finding a plan is equivalent to finding a set of consistent satisfiable paths through the OBDDs representing the domain.

Datasets

Not discussed in the paper. The paper presents a conceptual framework and an example (Figure 1) of a "Shooting Domain" to illustrate their approach, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • OBDDs for Non-Determinism and Real Values: The paper's central idea is that OBDDs, typically used for deterministic logic, can be effectively adapted to represent and reason about the complexities of non-deterministic actions and real-valued state spaces in planning.
  • Avoiding State Explosion: By using OBDDs, the authors aim to overcome the state explosion problem inherent in traditional methods when dealing with large real-valued state spaces. The size of an OBDD is not necessarily tied to the size of the state space it represents.
  • Direct Reasoning with Real Variables: The integration of un-interpreted functions allows for the direct representation and manipulation of real variables within the OBDD framework, avoiding the need for approximations or explicit enumeration.
  • Plan Generation as Path Finding: The concept of finding a plan is reframed as finding a set of satisfiable paths within the OBDD representation of the domain, which is a natural fit for the structure of OBDDs.

Key Results

The paper presents a conceptual framework and a methodology rather than quantitative results from empirical evaluations. The key result is the proposed OBDD-based planning approach that can handle non-deterministic actions and real-valued variables efficiently. The example in Figure 1 demonstrates how a simple "Shooting Domain" can be represented using OBDDs, illustrating the potential for this method.

Limitations and Future Work

The authors acknowledge that a full explanation of their technique for interpreting real variables is beyond the scope of the abstract. They also mention that their work can be used to analyze OBDD-based domain and plan characterizations, suggesting future work in providing mappings between various domain and action representation languages, such as PDDL and a causal representation language like C. The paper does not discuss specific limitations in terms of scalability or performance on complex, real-world benchmarks, as it focuses on the foundational methodology.

Summary updated

BibTeX
@inproceedings{1999obdd,
  title = {{OBDD-Based Planning with Real-Valued Variables in Non-Deterministic Environments}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure