Probabilistic Knowledge of External Events in Planning

Jim BlytheAAAI 1994

Abstract

Classical AI planning systems often operate under the assumption that the agent is the sole source of change within a domain. However, real-world environments are frequently subject to "external events"—occurrences outside the agent's control that can jeopardize plan success. This paper presents a framework for modeling these events probabilistically using a STRIPS-like representation. By integrating failure analysis and plan repair into the planning cycle, the system generates robust, contingent plans that account for temporal risks and minimize exposure to environmental hazards.

Introduction

In traditional classical planning, agents typically assume a static world where changes only occur as a direct result of their own actions. When uncertainty is introduced, researchers often rely on reactive strategies—fixing plans as they break—or non-deterministic action models. While useful, these approaches suffer from two primary limitations: state-space explosion and a lack of temporal sensitivity.

Jim Blythe argues that modeling external events (such as a bicycle being stolen while an agent is in a shop) as possible outcomes of every action leads to an exponential growth in the state space. Furthermore, the probability of such events is often tied to duration rather than specific actions; the longer a vulnerable state persists, the higher the risk of failure. This paper introduces a method to proactively "stress-test" plans against these probabilistic events to create more reliable outcomes off-line.

Methodology

The proposed planner is built upon the Prodigy 4.0 architecture and utilizes a three-stage iterative process to refine plan robustness:

  1. Initial Planning: The system generates a "naive" plan, assuming no external interference.
  2. Failure Analysis: The naive plan is subjected to three distinct analytical routines to identify sequences of external events that could cause failure:
  3. Monte Carlo Simulation: Randomly sampling event sequences to find common points of failure.
  4. Markov Chain Analysis: Mathematically modeling state transitions to calculate the probability of reaching a failure state.
  5. Exhaustive Search: Specifically searching for single-event instances that can immediately defeat the plan.
  6. Plan Repair: Once vulnerabilities are identified, the system applies one of three repair strategies:
  7. Conditional Steps: Inserting a "Plan B" (e.g., "if the bike is stolen, hail a cab").
  8. Prevention: Adding actions to negate the preconditions of an external event (e.g., "lock the bike").
  9. Temporal Re-ordering: Shifting the timeline of actions to minimize the duration of high-risk states (e.g., reducing time spent inside a building to shorten the window for theft).

Event Representation

External events are represented using a STRIPS-like framework, consisting of preconditions, add lists, and delete lists. To incorporate uncertainty, each event is assigned a probability $p$, representing the likelihood of the event occurring at any time step where its preconditions are met.

Key Insights

Decoupling Events from Actions

By treating external events as independent entities rather than outcomes of agent actions, the planner avoids the exponential growth of the state space. This separation allows the system to focus on the environment's dynamics without overcomplicating the agent's internal action model.

The "Wait Time" Factor

A significant contribution of this work is the recognition that plan robustness is often a function of time. The probability of failure frequently increases the longer an agent remains in a vulnerable state. Consequently, re-ordering a plan to minimize the duration of these states is a computationally efficient way to increase the probability of success without adding complex new actions.

Efficiency over Exhaustiveness

The author acknowledges that an exhaustive search for all possible failure sequences is computationally prohibitive. By focusing on the most likely or high-impact failures through simulation and targeted search, the system balances the need for robustness with the practicalities of computational limits.

Experimental Evaluation and Results

The planner was evaluated within a transportation domain simulation. Although specific benchmark datasets were not standardized at the time of publication (1994), the experimental trials demonstrated that these techniques "improve the probability of plan success greatly." The system successfully identified high-risk scenarios and generated logical repairs, such as preventative measures or contingency branches, that were not present in the initial naive plans.

Limitations and Future Work

Currently, the model assumes that external events are independent of one another. Future iterations of the work aim to incorporate Bayesian Networks to model complex, interdependent event structures. Additionally, the author intends to formally prove that this iterative "plan-then-repair" algorithm converges toward a plan with maximal utility. While the initial focus was on transportation, expanding the approach to more diverse and complex planning domains remains a priority.

Summary updated

BibTeX
@inproceedings{blythe1994probabilistic,
  author = {Jim Blythe},
  title = {{Probabilistic Knowledge of External Events in Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure