Dynamic Execution of Temporal Plans with Sensing Actions and Bounded Risk

Pedro Henrique Santana, Brian Charles WilliamsIJCAI 2015

Introduction

Autonomous systems operating in high-stakes environments—such as NASA space missions, deep-sea exploration, or collaborative manufacturing—face a fundamental tension between mission efficiency and safety. Traditional approaches often rely on "safest-case" planning, which produces rigid, pre-computed sequences of actions. While safe, these plans are often brittle and inefficient, frequently failing when minor environmental disturbances occur because they lack the capacity to adapt.

This research, presented at IJCAI 2015 by Pedro H. Santana and Brian C. Williams, addresses this limitation by developing a framework for dynamic execution. The goal is to enable agents to adapt to changing environments in real-time while providing mathematical guarantees that the risk of catastrophic failure remains below a user-defined threshold.

The Problem: Balancing Risk and Flexibility

The core challenge lies in moving beyond static plans toward chance-constrained planning. In complex domains, uncertainty is inherent; an agent must make decisions based on partial observations and probabilistic outcomes. The objective is to find a policy that maximizes utility while ensuring that the probability of violating any temporal or safety constraint (e.g., crashing or missing a critical deadline) stays within a specific "risk budget."

Methodological Innovations

The framework integrates several novel techniques to bridge the gap between high-level logical planning and low-level physical execution:

1. Probabilistic Temporal Plan Networks (pTPN)

The authors extend traditional temporal networks to include probabilistic models for uncontrollable events. This allows for the direct placement of "chance constraints" on temporal goals, enabling the system to reason about the likelihood of meeting deadlines under various scenarios.

2. The RAO* Algorithm

To solve chance-constrained Partially Observable Markov Decision Processes (POMDPs), the researchers developed RAO, an extension of the AO heuristic search. RAO* is particularly significant because it allows agents to explicitly plan "sensing actions." By "looking before they leap," agents can reduce uncertainty and update their belief states, ensuring that subsequent risky moves are only taken when the risk is within the allowed budget.

3. Learning Probabilistic Hybrid Automata (PHA)

Accurate planning requires accurate world models. The authors introduced the first algorithm capable of learning Probabilistic Hybrid Automata—models that combine discrete logic with continuous physical dynamics—directly from data. This reduces the reliance on manual engineering and improves the agent's ability to predict complex system behaviors.

4. Dispatchable Scheduling

Rather than a single fixed timeline, the system generates "families" of feasible schedules. This "dispatchable" approach allows the agent to delay or advance tasks in real-time based on live observations, maintaining safety without sacrificing the ability to adapt to minor timing fluctuations.

Key Insights: Risk as a Resource

A pivotal concept in this work is the treatment of risk as a finite resource, much like fuel or battery life. By quantifying the "risk budget," the planner can explore more efficient but slightly riskier paths, provided the cumulative probability of failure is managed.

Furthermore, the framework utilizes a diagnostic search approach. To manage the exponential complexity of failure scenarios, the system identifies specific subsets of conflicting constraints. By generalizing these conflicts, the planner can prune large sections of the search space, significantly improving scalability compared to traditional chronological search methods.

Evaluation and Results

The framework was validated across several real-world-inspired benchmarks:

  • Power Supply Restoration: In this partially observable domain, the RAO* algorithm successfully solved instances that were previously considered too complex for chance-constrained solvers.
  • Collaborative Human-Robot Manufacturing: The system demonstrated the ability to manage fluid interactions between humans and robots, ensuring manufacturing deadlines were met without compromising safety or human workflow.
  • Hybrid Filtering: The learned PHA models provided superior state estimation compared to standard Jump Markov Linear Systems (JMLS), with negligible computational overhead.

Conclusion and Future Directions

The research of Santana and Williams represents a significant step toward truly autonomous, risk-aware systems. By unifying logical planning, temporal scheduling, and active sensing under a single risk-bounded umbrella, they provide a path toward agents that are both flexible and demonstrably safe.

Future work aims to address "latent" failures—violations that are not immediately observable—and to more tightly integrate dispatchable temporal network propagation within the RAO* search process. Additionally, further modeling of human unpredictability will be essential for enhancing fluidity in human-robot collaborative environments.

Summary updated

BibTeX
@inproceedings{santana2015dynamic,
  author = {Pedro Henrique Santana and Brian Charles Williams},
  title = {{Dynamic Execution of Temporal Plans with Sensing Actions and Bounded Risk}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure