Planning under Uncertainty and Temporally Extended Goals

Alberto CamachoIJCAI 2016

Abstract

Classical AI planning often operates under the assumption of a "closed world," where actions have deterministic outcomes and goals are simple, static destinations. However, real-world applications—such as autonomous transportation and smart city management—demand agents that can navigate non-deterministic environments and satisfy complex, time-dependent constraints. This paper summarizes the research of Alberto Camacho, which introduces two significant advancements: ProbPRP, a probabilistic planner designed for uncertain environments, and a novel translation framework that enables Linear Temporal Logic (LTL) goals to be solved using standard planning techniques. Together, these contributions bridge the gap between theoretical planning and the messy reality of physical systems.

Introduction: The Gap in Classical Planning

In traditional planning models, the objective is typically a single state (e.g., "be at the airport"). In reality, goals are often "temporally extended," meaning they describe requirements over a sequence of states (e.g., "visit the museum before the park" or "ensure the temperature never exceeds a safety threshold"). Furthermore, real-world actions are rarely certain; a bus might be delayed by traffic, or a sensor might fail to trigger.

Existing planners frequently struggle to scale to the large state spaces required for these problems or fail to handle the infinite trajectories often found in continuous monitoring tasks. Camacho’s research addresses these hurdles by treating uncertainty and temporal complexity as primary constraints rather than edge cases.

Probabilistic Planning with ProbPRP

The first major contribution is ProbPRP, an algorithm that treats probabilistic planning as an extension of Fully Observable Non-Deterministic (FOND) planning. Unlike many planners that reason forward from a start state, ProbPRP utilizes plan regression—reasoning backward from the goal—to generate compact and efficient policies.

Deadend Detection and the "HighProb" Objective

A core feature of ProbPRP is its use of "forbidden state-action pairs" (FSAPs) to detect and prune paths that lead to deadends (states from which the goal is unreachable). However, the research revealed a counter-intuitive insight: in highly uncertain environments, performing a final search round with deadend detection disabled could increase the probability of reaching a goal by up to 30%. This occurs because, when no guaranteed safe path exists, an agent must be willing to take "risky" paths that a strict deadend-detector would otherwise block. To support this, the "HighProb" objective was introduced to maximize the likelihood of success even when a 100% guarantee is mathematically impossible.

Translating Temporal Logic into Actionable Plans

To handle complex, time-based goals, the research introduces a framework to translate Linear Temporal Logic (LTL) formulas into standard FOND problems. This allows high-performance, off-the-shelf planners to solve problems that were previously too complex to model.

The Role of Automata

The translation process uses two types of mathematical monitors:

  1. Non-deterministic Finite Automata (NFA): Used to track goal satisfaction over finite sequences.
  2. Alternating Automata (AA): Theoretically more efficient due to their polynomial size.

Interestingly, while AA are more compact in theory, empirical testing showed that planners performed better with NFA-based translations. The NFA approach produced smaller policies and faster run-times, highlighting a distinct gap between theoretical complexity and practical performance in AI planning.

Key Results and Performance

ProbPRP and the LTL translation framework were evaluated against state-of-the-art tools, including the online probabilistic planner RFF and the FOND planner PRP. Key findings include:

  • Scaling and Efficiency: ProbPRP successfully overcomes the scaling difficulties of previous offline algorithms by using partial state representation, resulting in significantly smaller policies.
  • Offline Superiority: Despite the common assumption that online planners (which calculate steps as they go) are better for uncertainty, the offline ProbPRP outperformed RFF in both solution quality and general performance.
  • Full Spectrum LTL: The translation system is the first of its kind capable of solving the "full spectrum" of LTL FOND planning, including goals that must be maintained over infinite state trajectories.

Conclusion and Future Directions

This research provides a robust foundation for agents operating in unpredictable environments with complex requirements. However, several frontiers remain. Future work will focus on Unified Planning, merging probabilistic reasoning and LTL goals into a single, seamless framework. Additionally, there is a need to move from "hard" goals to soft preferences (capturing what an agent prefers to do) and to incorporate hybrid variables—integrating discrete logic with real-valued data like battery levels or temperature—to fully realize the potential of smart city applications.

Summary updated

BibTeX
@inproceedings{camacho2016planning,
  author = {Alberto Camacho},
  title = {{Planning under Uncertainty and Temporally Extended Goals}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure