Planning with External Events

Jim BlytheUAI 1994

TL;DR

This paper introduces a novel AI planning methodology that explicitly models and reasons about unpredictable external events, a common challenge in real-world scenarios. By representing these events probabilistically and integrating them into a Bayesian belief network, the planner can generate plans that are robust to uncertainty and achieve goals with a higher probability of success.

What Problem Does This Paper Address?

Classical AI planning systems often operate under the assumption that the world is deterministic and predictable. This means that once an action is taken, its outcome is known with certainty, and there are no unforeseen events. However, the real world is anything but predictable. External events, like a package being lost, a taxi breaking down, or a sudden change in traffic, can significantly disrupt even the best-laid plans.

This paper tackles the problem of planning in domains where such unpredictable external events are a significant factor. Existing approaches often handle uncertainty in action effects or initial states, but this work focuses specifically on the impact of external events that can occur during plan execution. The challenge is to create plans that don't just succeed in a perfect world, but have a high probability of success even when these unexpected events occur.

Methods

The core of the paper's contribution lies in its novel planning methodology. Here's a breakdown of the key techniques:

  • Probabilistic Representation of External Events: External events are modeled similarly to actions, with enabling conditions and a fixed probability of occurrence within a discrete time unit. This allows the planner to reason about the likelihood of these events.
  • Bayesian Belief Networks for Plan Representation: The planner constructs a Bayesian belief net (BN) from the initial plan. This BN represents the state of the world and the potential outcomes of actions and events. It's built in two stages: first, representing the deterministic plan, and second, incorporating external events and their dependencies.
  • Goal-Directed Repair Strategy: When the BN reveals potential failures due to external events, the planner employs a goal-directed repair strategy. Instead of simply generating a plan that works if no events occur, it aims to achieve a certain threshold probability of success.
  • Plan Repair Techniques: The paper proposes three methods for repairing plans when failures are detected:
  • Conditional Branching: Creating a plan that branches to a different state if an event occurs, effectively making an action optional.
  • Precondition Negation: Adding steps to the plan that negate the preconditions of an external event, thereby preventing it from occurring.
  • Temporal Shifting/Reordering: Adjusting the timing or order of plan steps to reduce the window of opportunity for events to occur.
  • Efficient Probability Estimation: To address the computational expense of evaluating full BNs, two methods are proposed:
  • Exploiting Independence: Using knowledge about independence between domain features and events to decompose the problem into smaller, independent Markov chains.
  • Monte Carlo Simulation: Simulating the plan many times with random event occurrences to estimate probabilities of success and failure.

Datasets

Not discussed in the paper. The paper uses a custom-designed example domain to illustrate its concepts.

Key Insights and Ideas

  • External Events as First-Class Citizens: The paper elevates external events from mere nuisances to integral components of the planning process, requiring explicit representation and reasoning.
  • Probabilistic Planning for Robustness: The shift from deterministic planning to probabilistic planning is crucial for real-world applicability, allowing planners to quantify and manage risk.
  • Bayesian Networks as a Unified Framework: Using BNs provides a powerful and theoretically grounded way to represent the complex interplay between actions, states, and probabilistic events.
  • Goal-Directed Plan Repair: The idea of repairing plans based on decision-theoretic criteria (probability of success) rather than just achieving a goal deterministically is a significant step towards more practical planners.
  • The Power of Negating Event Preconditions: The technique of adding sub-plans to prevent events by negating their preconditions is an elegant way to leverage knowledge about event causes.

Key Results

The paper demonstrates its methodology on a transportation domain involving packages, taxis, and airplanes. The key results are:

  • Successful Plan Generation in Eventful Domains: The planner successfully generates plans that account for external events like packages being lost or taxis moving unexpectedly.
  • Quantification of Failure Probabilities: The system can estimate the probability of specific failure sequences, such as a taxi being in the wrong place (0.477) or a package being lost (0.1) in the example.
  • Demonstration of Plan Repair Effectiveness: The paper illustrates how the repair strategies can lead to a final plan with a higher probability of success by making actions conditional or adding protective measures.
  • Comparison of Probability Estimation Techniques: The paper shows that both independence-based methods and Monte Carlo simulations can be used to estimate failure probabilities, with trade-offs in computational cost and accuracy.

Limitations and Future Work

  • Computational Complexity: While the paper proposes methods for efficiency, evaluating complex Bayesian nets and calculating complete sets of event sequences can still be computationally expensive (NP-hard).
  • Abstraction Barrier: The current approach maintains a strict abstraction barrier between the planner and event reasoning routines. Relaxing this could allow the planner to view external events as opportunities, not just problems.
  • Limited Event Representation: The paper simplifies event representation to fixed probabilities and enabling conditions. More general representations of events with probabilistic effects over time could enhance the system.
  • Future Directions: The authors suggest improving the tractability of inference, better exploiting domain-specific knowledge about event dependencies, and incorporating external events as opportunities rather than solely as threats. They also highlight the need for goal-directed reasoning to generate useful envelopes for policy iteration in complex domains.

Summary updated

BibTeX
@inproceedings{blythe1994planning,
  author = {Jim Blythe},
  title = {{Planning with External Events}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure