Planning with graded fluents and actions

Marta Cialdea Mayer, Carla Limongelli, Andrea Orlandini, Valentina PoggioniIJCAI 2005

Abstract

Classical planning typically treats the world as a series of binary states, but real-world problems often involve continuous intensities. This paper introduces a novel planning model and PDDL extension that supports "graded" fluents and actions, where states and intensities exist on a spectrum from 0 to 1. By combining symbolic search with Mixed Integer Programming (MIP), the proposed framework can determine the optimal "dosage" for every action in a plan.

Introduction: Beyond Binary Planning

In classical AI planning, states are boolean: a door is either open or closed, and an action is either performed or it is not. While probabilistic planning models uncertainty, it does not naturally capture intensity—for example, how far a door is open or the specific power level of an engine.

Existing standards like PDDL 2.1 introduced numerical fluents, but they often struggle with actions that have adjustable intensities affecting the world proportionally. This research bridges that gap, allowing planners to reason about "how much" an action is applied and "to what degree" a property holds true.

Methodology: A Hybrid Architecture

The authors propose a framework that decouples the sequence of actions from their specific intensities. This is achieved through a three-stage architecture that combines symbolic search with numerical optimization.

Architecture of the graded planning system
  1. PDDL Extension: A new degree type is introduced. While boolean fluents remain {0, 1}, "graded" fluents can take any real value in the interval [0, 1]. Actions are assigned a degree parameter representing their application intensity.
  2. Linear Effects: The "degree of truth" of a fluent following an action is modeled as a linear combination of its prior value and the action's intensity.
  3. The Three-Stage Pipeline:
    • Plan Extractor: Performs a backward search to find a "candidate plan" sequence. At this stage, action intensities are left as unbound variables.
  4. System Constructor: Translates the candidate plan's preconditions and effects into a Mixed Integer Programming (MIP) problem.
  5. MIP Solver: Finds a valid instantiation of the intensity variables. If successful, it provides the exact degrees required; if it fails, the system backtracks to find an alternative plan sequence.

This decoupling prevents the search space from exploding by letting the symbolic planner handle the "what" and "when," while the MIP solver handles the "how much."

Key Insights

  • Intensity vs. Probability: A "graded" fluent represents a partial state of reality (e.g., a tank 30% full), not a lack of knowledge about a binary state.
  • Computational Tractability: By restricting effects to linear combinations, the resulting optimization problem remains solvable by existing MIP tools.
  • Objective Optimization: The model supports an objective_function, enabling the planner to minimize or maximize specific action degrees, such as fuel consumption.

Results and Future Work

This foundational work establishes the syntax for graded planning within the PDDL ecosystem and demonstrates a viable pipeline for hybrid symbolic-numerical solving. It enhances expressiveness for modeling efficiency and proportional effects that were previously difficult to represent.

Future research aims to address current limitations, including:

  • Intelligent Backtracking: Improving the efficiency of the system when the MIP solver fails by identifying specific actions causing numerical conflicts.
  • Uncertainty and Fuzzy Logic: Incorporating "vague" fluents and handling planning under initial state uncertainty.
  • Empirical Benchmarking: While a prototype exists, future work will involve testing against standard datasets to evaluate scalability and performance.

Summary updated

BibTeX
@inproceedings{mayer2005planning,
  author = {Marta Cialdea Mayer and Carla Limongelli and Andrea Orlandini and Valentina Poggioni},
  title = {{Planning with graded fluents and actions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure