Time-Saving Tips for Problem Solving with Incomplete Information

Michael R. Genesereth, Illah R. NourbakhshAAAI 1993

Abstract

This paper addresses a fundamental challenge in robotics: planning effectively when the agent has incomplete information about its environment or its own state. We introduce a set of domain-independent pruning rules for state-set graphs that allow AI planners to discard redundant or useless search branches. Furthermore, we propose the Deferred Planning Algorithm (DPA), which interleaves planning and execution. By executing partial "viable" plans to gather information and then re-planning, robots can solve complex problems orders of magnitude faster than traditional methods that attempt to account for every contingency upfront.

Introduction

In classical AI, planners often assume "complete information"—the robot knows exactly where objects are and its own precise coordinates. In the real world, information is qualitative and incomplete (e.g., "the tool is in one of these three rooms"). When information is missing, the search space explodes. A "state" is no longer a single point, but a "belief state" (a set of all possible states the robot might be in). Planning across these sets is computationally expensive because the robot must account for every possible reality, often leading to "analysis paralysis."

Methodology

The approach is built upon State-set Graphs, where each node represents a set of possible world states. Transitions between these nodes are triggered by actions or sensory percepts.

A state-set graph for the Square World domain, showing transitions between belief states via movement (mv), grabbing (gr), and dropping (dr) actions.

Algorithmic Frameworks

  1. MSSPA (Multiple State Sequential Planning): Finds a single sequence of actions that works regardless of which initial state is true.
  2. MSCPA (Multiple State Conditional Planning): Builds a "decision tree" plan that uses sensory input to branch into different sub-plans.
  3. DPA (Deferred Planning Algorithm): The core contribution. Instead of planning to the goal, the robot plans a "viable" partial sequence, executes it to gain information, and then re-plans from its new, more certain position.

Pruning and Termination Rules

To manage the search space, the authors introduce pruning rules based on information theory:

  • Sequential Pruning: Discard plans leading to traps, loops, or "dominated" states where another plan reaches a more specific (informative) state set in fewer steps.
  • Conditional Pruning: Extends domination to sets of result nodes. If Plan A's possible outcomes are all "better" (more certain or closer to the goal) than Plan B's, Plan B is discarded.
  • Termination Rules: DPA stops searching when it finds a "Viable Plan"—one guaranteed to reduce uncertainty without losing the ability to reach the goal (reversibility).
A search tree illustrating how pruning rules are applied to discard branches that lead to less informative or redundant state sets.

Experimental Evaluation

The algorithms were evaluated on several simulated environments, including Square World (a 2x2 grid), Wumpus World, and high-complexity domains like TBOX (Tool Box) and BAT (Bay Area Transit), the latter featuring over 8,000 initial state possibilities.

Key Results

  • Significant Speedups: In the MJH1 navigation task, the standard sequential planner took 34.6 seconds, while DPA solved it in just 1.6 seconds.
  • Handling High Complexity: In the TBOX domain, which has a high branching factor, traditional planners timed out after 24 hours. DPA found a solution in 73.1 seconds.
  • Efficiency: Despite interleaving planning and action, the final execution lengths were remarkably close to the "ideal" lengths calculated with full information.

Discussion and Conclusion

The primary insight of this work is that information itself is a pruning metric. If one path leads to a state set that is a subset of another, the first path is strictly superior. Furthermore, the paper demonstrates that "doing" is often better than "thinking" to the end; by using the world as its own model, a robot can gain information through action that would be too expensive to simulate.

While highly effective, the current framework is limited to state-based goals and qualitative uncertainty. Future work will explore incorporating numerical probabilities and handling conditional goals where the objective itself may change based on new information.

Summary updated

BibTeX
@inproceedings{genesereth1993time,
  author = {Michael R. Genesereth and Illah R. Nourbakhsh},
  title = {{Time-Saving Tips for Problem Solving with Incomplete Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure