Process-Oriented Planning and Average-Reward Opumalirv

IJCAI 1995

TL;DR

This paper argues that many AI planning problems are better framed as "process-oriented" (continuous operation) rather than "goal-oriented" (reaching a specific state). They propose average-reward optimality as the most suitable criterion for these continuous processes and introduce a novel algorithm, Structured Fox-Landi (SFL), to efficiently discover the communicating structure of Markov Decision Processes (MDPs), a crucial step for computing average-optimal policies.

What Problem Does This Paper Address?

Traditional AI planning often focuses on goal-oriented problems: finding a sequence of actions to transition from an initial state to a desired goal state. However, many real-world scenarios, like a robot continuously performing maintenance or a system managing ongoing tasks, don't have a clear termination point. These are "process-oriented" problems where the agent needs to operate effectively indefinitely.

The authors highlight that while Markov Decision Processes (MDPs) are powerful tools for these problems, existing research has largely focused on goal-oriented scenarios. This has led to a neglect of crucial aspects for process-oriented planning, particularly the design of appropriate optimality criteria. Discounted total reward, a common metric, can introduce bias towards immediate rewards and may not accurately reflect long-term performance in continuous processes. Furthermore, computing optimal policies for these scenarios can be computationally intractable due to the potentially exponential state space.

Methods

The paper's core technical contribution is the Structured Fox-Landi (SFL) algorithm. This algorithm aims to discover the "communicating structure" of an MDP, which is essential for computing average-optimal policies. Unlike traditional methods that require explicit enumeration of the entire state space, SFL leverages compact action representations (like Bayes nets) to avoid this.

Here's a breakdown of their approach:

  • Process-Oriented Framing: The authors advocate for viewing problems like robot assistance (mail delivery, coffee service, lab tidiness) as continuous processes rather than sequences of discrete goals. This framing emphasizes the importance of ongoing performance and handling exogenous events (like new requests or system changes).
  • Average-Reward Optimality: They argue that for process-oriented problems, average reward per stage is a more suitable optimality criterion than discounted total reward. This metric directly reflects the long-term, steady-state performance of a policy.
  • Structured Fox-Landi (SFL) Algorithm: This is the novel algorithm presented. It's an extension of the Fox-Landi algorithm for classifying Markov chains, adapted for MDPs with structured action representations.
  • Schematic States and Paths: SFL operates on "schematic states" (s-states) and "schematic paths" (s-paths), which represent groups of states and sequences of states symbolically. This allows for reasoning about large portions of the state space simultaneously.
  • Unification and Path Splitting: Key operations include unification (to check for intersections between s-states) and path splitting (to handle situations where actions and events have conflicting effects or when paths diverge).
  • Cycle Detection: The algorithm efficiently detects cycles in the state space, which are crucial for identifying recurrent classes in the MDP's structure.
  • Exploiting Structure: SFL uses influence graphs to guide the exploration of the state space, prioritizing variables that have more localized influences, thereby improving efficiency.
  • Value Iteration with Structured Representations: The paper also touches upon how to use value iteration (a standard MDP algorithm) in conjunction with structured representations (like Bayes nets) to speed up policy construction, especially for communicating MDPs.

Datasets

Not discussed in the paper. The paper uses a simulated "gopher" robot domain with specific variables (location, tidiness, mail status, coffee request) and actions to illustrate their concepts.

Key Insights and Ideas

  • The "Process" Matters: Many AI planning problems are not about reaching a single destination but about maintaining a continuous, effective operation. This shift in perspective is fundamental.
  • Average Reward is King for Continuous Tasks: For ongoing processes, maximizing the average reward per unit of time is a more intuitive and appropriate goal than maximizing a discounted sum of future rewards. Discounting can lead to suboptimal strategies by overvaluing short-term gains.
  • Structure is Your Friend (and a Computational Lifesaver): The computational complexity of MDPs explodes with the state space size. The paper demonstrates that by exploiting the structure of actions and events (e.g., using Bayes nets), we can avoid enumerating all states and still discover crucial structural properties like communicating classes.
  • Communicating Structure is Key: Understanding which states can reach which other states (and with what probability) is vital for average-reward optimality. SFL provides an efficient way to uncover this structure, even in complex domains.

Key Results

The paper presents a novel algorithm (SFL) for discovering the communicating structure of MDPs. While specific quantitative results are not the primary focus, the authors claim that SFL can achieve significant computational gains (potentially exponential reductions in time and memory) compared to traditional state-space algorithms for structure classification. They illustrate its effectiveness with a detailed example of a "gopher" robot, showing how it can efficiently identify communicating substructures within the problem. The algorithm's ability to handle complex interactions between actions and exogenous events is highlighted.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the SFL algorithm, while efficient, can still be complex to implement and requires careful handling of path splitting and unification.
  • The assumption that users can specify "net effects" for conflicting action-event pairs might be a practical hurdle in some domains.
  • The current SFL algorithm primarily focuses on identifying communicating structures and may require further adaptation for directly computing average-optimal policies in all types of MDPs (e.g., multichain problems).
  • Future Work:
    • Exploring further heuristics for SFL to improve its performance on general problems.
  • Conducting extensive experiments to benchmark SFL against traditional methods and identify problem characteristics that favor SFL.
  • Extending the approach to semi-Markov models where actions have varying durations.
  • Investigating the discovery of "weakly communicating" MDPs, which share some desirable properties with communicating MDPs.
  • Adapting SFL for use with piecewise value iteration to solve general MDPs by decomposing them into recurrent classes.

Summary updated

BibTeX
@inproceedings{1995process,
  title = {{Process-Oriented Planning and Average-Reward Opumalirv}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure