Probabilistic Knowledge-Based Programs

Jérôme Lang, Bruno ZanuttiniIJCAI 2015

Abstract

In the field of AI planning, Partially Observable Markov Decision Processes (POMDPs) are the standard for modeling agents operating under uncertainty. However, the resulting policies often suffer from a "curse of dimensionality," manifesting as massive, uninterpretable structures. This paper introduces Probabilistic Knowledge-Based Programs (PKBPs), a framework that allows for the specification of policies using high-level programming constructs that branch on an agent's internal belief state. We demonstrate that PKBPs can be exponentially more succinct than traditional reactive policies while maintaining the same complexity for formal verification.

1. Introduction

The primary challenge in POMDP planning is the representation of policies. Traditional methods rely on history-based trees or value-based $\alpha$-vectors, both of which lack human interpretability and can grow explosively in size. PKBPs address this by allowing experts to write policies in a natural, code-like language. By branching on probabilistic conditions (e.g., "if I am 90% sure the door is safe"), PKBPs bridge the gap between human intuition and formal logic, particularly in high-stakes domains like medical or military applications.

2. Methodology and Representation

PKBPs extend standard knowledge-based programs by incorporating probabilistic conditions. A PKBP is a program composed of sequences, if-then-else statements, and while loops, where conditions are defined over the agent's belief state. To maintain computational efficiency, the framework employs factored representations:

  • Bayesian Networks (BNs): Used to represent the agent's current belief state.
  • 2-slice Temporal BNs (2TBNs): Used to model how actions change the world and what observations are generated.
Figure 1: A 2-slice Temporal Bayesian Network (2TBN) modeling the transition and observation dynamics for a specific action.

Execution involves a process of "progression," where the agent updates its belief state after each action and observation. The agent then performs a reasoning task to evaluate the next probabilistic condition in the program.

Figure 2: Initial belief state and conditional dependencies represented as a factored Bayesian Network.

The authors illustrate these concepts using a modified "Tiger Problem" benchmark. In a 5-door variant, a complex multi-step strategy can be expressed as a compact, readable PKBP, whereas a traditional policy tree would be significantly larger.

3. Theoretical Results

The paper provides several key theoretical insights regarding the efficiency and complexity of PKBPs:

  • Succinctness Theorem: The authors formally prove that PKBPs can be exponentially more compact than reactive representations. A strategy requiring a billion-node tree can potentially be written in just a few lines of PKBP code.
  • Execution Complexity: Determining the next action in a PKBP is $P^{PP}$-complete. While computationally intensive, this shifts the burden to runtime inference, which can often be handled by modern BN solvers.
  • Verification Complexity: Verifying whether a PKBP achieves a target expected reward over a finite horizon is PSPACE-complete. Crucially, this means that the more compact representation does not increase the fundamental difficulty of verification compared to standard POMDP policies.

4. Discussion and Future Work

While PKBPs offer significant advantages in readability and compactness, they require the agent to perform more "thinking" at runtime. This may limit their use in high-speed robotics unless belief states are kept simple. Future research will focus on the automated synthesis of PKBPs from POMDP models and extending verification results to infinite horizons.

Summary updated

BibTeX
@inproceedings{lang2015probabilistic,
  author = {Jérôme Lang and Bruno Zanuttini},
  title = {{Probabilistic Knowledge-Based Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure