What Is Planning in the Presence of Sensing?

AAAI 1996

TL;DR

This paper tackles the challenge of defining what constitutes a "correct" plan when an agent can sense its environment. It proposes a formal specification using the situation calculus, defining plans as executable programs that are guaranteed to achieve a goal, regardless of sensing outcomes. This work provides a foundational framework for understanding and evaluating planning in dynamic, uncertain environments.

What Problem Does This Paper Address?

Traditional AI planning typically deals with deterministic environments where the outcome of actions is known. However, real-world agents, like robots, often operate in environments with uncertainty. They need to sense their surroundings to determine the next best action. While planners exist that can generate "conditional plans" (plans with if-then-else structures based on sensing), there's been a lack of a clear, formal definition of what makes such a plan "correct." This paper aims to fill that gap by providing a rigorous specification for planning in the presence of sensing actions, independent of any particular planning algorithm.

Methods

The authors propose a formal specification built upon the situation calculus, a logical framework for reasoning about actions and change. Key elements include:

  • Extending the Situation Calculus: The framework is extended to incorporate sensing actions. This involves defining a new fluent K(s', s) representing the agent's belief that it might be in situation s' given it's currently in situation s.
  • Robot Programming Language (R): A simple, deterministic programming language R is introduced. Programs in R consist of basic actions, sensing actions, sequential composition (seq), conditional branching (branch), and loops (loop). Crucially, these programs are designed to be trivially executable by an agent, meaning the agent always knows how to execute them without needing to reason about unknown fluents.
  • Formalizing Plan Correctness: A plan is defined as a robot program r such that, given the initial knowledge state K(s, So), the program is guaranteed to terminate in a goal state s'. This is formalized using a second-order predicate Rdo(r, s, s') which captures the legal termination of a robot program.

Datasets

Not discussed in the paper. The paper uses abstract examples like the "Airport Example" and "Omelette Example" to illustrate its concepts, rather than real-world datasets.

Key Insights and Ideas

  • The Need for Executability: A plan isn't just about achieving a goal; the agent executing it must know how to execute it. This leads to the design of the simple, deterministic robot programming language R.
  • Knowledge as a Fluent: Formalizing an agent's knowledge using the K fluent in the situation calculus is crucial for reasoning about what an agent "knows" at any given point.
  • Separation of Specification and Generation: The paper emphasizes that a clear specification of what a plan is and when it's correct is independent of how that plan is generated. This allows for evaluating plans produced by any method.
  • Handling Redundant/Missing Sensing: The formal specification allows for analyzing plans with extra sensing actions (which might be redundant) or missing sensing actions (which might lead to incorrectness), providing a principled way to critique plans.

Key Results

The paper presents a formal definition of planning in the presence of sensing actions. It demonstrates this by:

  • Formalizing the "Airport Example" and showing how a robot program Rair correctly achieves the goal of getting on a specific flight, regardless of which gate it's at, by using a sensing action.
  • Formalizing the "Omelette Example" and outlining a robot program Regg that achieves the goal of getting three good eggs into a bowl, handling uncertainty about egg quality.
  • Proving the logical validity of key theorems that define the semantics of robot programs, enabling the interpretation of these programs.

Limitations and Future Work

  • Plan Generation: The paper explicitly states it does not propose a new planning procedure. While it provides a specification, automatically generating robot programs that satisfy this specification is a significant challenge, especially for complex domains. The paper acknowledges that searching through all possible robot programs is computationally prohibitive.
  • Expressiveness of R: The paper explores the expressiveness of the robot programming language R by introducing extensions for memory (Turing machine tape) to handle more complex goals. However, it raises the question of what constitutes an "effectively achievable" goal and whether R (even with extensions) is sufficient for all such goals.
  • Noisy Sensors: The paper acknowledges that its current framework primarily handles binary sensing actions (yes/no answers). It points to existing work on noisy sensors but notes that defining planning in such contexts remains an open problem.
  • Degrees of Belief: The current framework focuses on knowledge (what is known for sure). Extending it to handle degrees of belief or probabilistic reasoning for uncertain sensing is a direction for future work.

Summary updated

BibTeX
@inproceedings{1996what,
  title = {{What Is Planning in the Presence of Sensing?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure