Planning under Partial Observability by Classical Replanning: Theory and Experiments

Blai Bonet, Hector GeffnerIJCAI 2011 · OpenReview

Abstract

Planning with partial observability can be formulated as a non-deterministic search problem in belief space. The problem is harder than classical planning as keeping track of beliefs is harder than keeping track of states, and searching for action policies is harder than searching for action sequences. In this work, we develop a framework for partial observability that avoids these limitations and leads to a planner that scales up to larger problems. For this, the class of problems is restricted to those in which 1) the non-unary clauses representing the uncertainty about the initial situation are invariant, and 2) variables that are hidden in the initial situation do not appear in the body of conditional effects, which are all assumed to be deterministic. We show that such problems can be translated in linear time into equivalent fully observable non-deterministic planning problems, and that an slight extension of this translation renders the problem solvable by means of classical planners. The whole approach is sound and complete provided that in addition, the state-space is connected. Experiments are also reported.

Introduction

In classical planning, agents operate with perfect knowledge of the world state and the deterministic outcomes of their actions. However, real-world environments are frequently characterized by partial observability, where crucial information—such as whether a door is locked or the specific location of an object—is hidden from the agent.

Traditionally, solving such problems requires searching through belief space, the set of all possible states consistent with the agent's observations. This approach is computationally expensive for two primary reasons: tracking beliefs is significantly more complex than tracking individual states, and searching for policies (contingency plans for every possible observation) is harder than finding a single action sequence. This paper proposes the K-Planner, a framework that bypasses the belief-space bottleneck by translating partially observable problems into classical planning tasks.

Methodology: The K-Planner Framework

The K-Planner utilizes a two-step translation process to leverage the efficiency of off-the-shelf classical planners:

  1. The $K'(P)$ Translation: The authors identify a "simple" class of problems where uncertainty is restricted (e.g., hidden variables do not influence action effects, only preconditions). For these problems, the partially observable task is translated into a fully observable, non-deterministic planning problem in linear time.
  2. The $K(P)$ Translation and Replanning: To solve these tasks deterministically, sensing actions are treated as "assumptions." The planner selects the most favorable assumption (e.g., "the path is clear"), generates a plan, and begins execution.
  3. Online Replanning: The agent follows the generated plan until an observation contradicts its initial assumptions. At this point, the agent updates its knowledge base and invokes the classical planner again to find a new path from its current state.

This approach is sound and complete for "simple" problems, provided the state space is "connected," ensuring the agent cannot reach an irreversible dead-end due to an incorrect assumption.

Benchmark Domains

The K-Planner was evaluated across several diverse domains that test different aspects of spatial and logical reasoning under uncertainty:

  • Freespace & Doors: Navigation tasks in grids with unknown obstacles or door states.
  • Wumpus & Kill-Wumpus: Classic AI benchmarks requiring navigation and monster elimination based on local "smell" sensors.
  • Colored-balls: Delivery tasks involving objects with initially unknown colors.
  • Trail: Following a path of stones with an unknown layout.
Visual representation of the benchmark domains: colored-balls, kill-wumpus, and trail.

Experimental Evaluation

The K-Planner was implemented using the FF (Fast-Forward) classical planner as the underlying engine. The results demonstrate significant scalability and efficiency across the benchmark suite.

Experimental results for the K-Planner across various domains, showing solved instances and search efficiency.

As shown in the table above, the K-Planner successfully solved 462 out of 545 instances. Notably, in the wumpus and kill-wumpus domains, it achieved a 100% success rate with search times often under two seconds. In the kill-wumpus domain, the agent demonstrated the ability to perform complex logical deductions (e.g., inferring a monster's location by process of elimination) without a specialized reasoning engine. Furthermore, the method handled astronomical uncertainty; the colored-balls domain involved over $10^{45}$ possible initial states, a scale far beyond the reach of traditional contingent planners.

Discussion and Future Work

While the K-Planner excels in efficiency, it faces limitations. The "Dead-End" problem remains a challenge: if an optimistic assumption leads to a state from which the goal is unreachable, the planner will fail. Additionally, the current theoretical guarantees are limited to "simple" problems where hidden variables do not have complex interactions with conditional effects.

Future work could involve integrating the $K$-logic directly into a planner's search engine to reduce the overhead of external PDDL parsing and exploring methods to handle domains with irreversible dead-ends.

Summary updated

Abstract

Planning with partial observability can be formulated as a non-deterministic search problem in belief space. The problem is harder than classical planning as keeping track of beliefs is harder than keeping track of states, and searching for action policies is harder than searching for action sequences. In this work, we develop a framework for partial observability that avoids these limitations and leads to a planner that scales up to larger problems. For this, the class of problems is restricted to those in which 1) the non-unary clauses representing the uncertainty about the initial situation are invariant, and 2) variables that are hidden in the initial situation do not appear in the body of conditional effects, which are all assumed to be deterministic. We show that such problems can be translated in linear time into equivalent fully observable non-deterministic planning problems, and that an slight extension of this translation renders the problem solvable by means of classical planners. The whole approach is sound and complete provided that in addition, the state-space is connected. Experiments are also reported.
BibTeX
@inproceedings{bonet2011planning,
  author = {Blai Bonet and Hector Geffner},
  title = {{Planning under Partial Observability by Classical Replanning: Theory and Experiments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=rJE984z_Zr},
}
Figure