Symbol Acquisition for Probabilistic High-Level Planning

George Dimitri Konidaris, Leslie Pack Kaelbling, Tomás Lozano-PérezIJCAI 2015 · OpenReview

Abstract

We introduce a framework that enables an agent to autonomously learn its own symbolic representation of a low-level, continuous environment. Propositional symbols are formalized as names for probability distributions, providing a natural means of dealing with uncertain representations and probabilistic plans. We determine the symbols that are sufficient for computing the probability with which a plan will succeed, and demonstrate the acquisition of a symbolic representation in a computer game domain.

Introduction

In robotics, a significant "semantic gap" exists between low-level sensor data and high-level reasoning. While robots operate in continuous, high-dimensional spaces involving joint angles and coordinates, effective planning often requires discrete symbols like "the door is open" or "the key is held." Traditionally, these symbols are hand-coded by human experts. However, real-world environments are inherently noisy and unpredictable, making rigid, set-based symbolic representations (where a condition is either 100% true or false) brittle. This paper addresses the challenge of autonomous symbol acquisition under uncertainty, allowing agents to learn their own "planning language" directly from experience.

Methodology

The proposed framework models the environment as a Semi-Markov Decision Process (SMDP) using "options"—temporally extended actions such as "navigate to the door." The core innovation lies in the definition of Probabilistic Symbols:

  1. Type 1 Symbols (Effect Distributions): Represented as probability distributions over states using Kernel Density Estimation (KDE). These describe the "image" or expected outcome of an action.
  2. Type 2 Symbols (Preconditions): Represented as probabilistic classifiers using Support Vector Machines (SVMs) with Platt scaling. These estimate the probability that a specific condition holds in a given state.
Probabilistic symbol acquisition process showing preconditions and image operators.

The learning pipeline involves four key stages:

  • Data Collection: The agent executes random options and records state transitions.
  • Option Partitioning: Using DBSCAN clustering, the agent groups experiences where actions yielded similar effects.
  • Factoring: The agent identifies independent state variables (e.g., player position vs. a distant door state) to simplify the representation.
  • PPDDL Generation: Learned distributions are compiled into a Probabilistic Planning Domain Definition Language (PPDDL) file, compatible with standard off-the-shelf planners.

Experimental Setup: The Treasure Game

The framework was evaluated in "The Treasure Game," a custom 2D continuous environment. The state space is 9-dimensional, tracking the agent, key, and treasure coordinates, along with handle angles and a lock state. The agent has access to 9 high-level options, such as up-ladder or interact.

The Treasure Game environment used for evaluation.

Crucially, the environment includes stochastic elements: handles flip with only 80% probability, and jumps can fail, causing the agent to fall. This uncertainty necessitates a probabilistic approach to symbol acquisition.

Key Results and Discussion

The agent successfully identified 7 distinct factors from the 9D state space and acquired a vocabulary of 30 probabilistic symbols and 345 PPDDL operators. Once learned, the symbolic representation enabled highly efficient planning:

  • Speed: Complex tasks involving keys, switches, and treasure were solved in under 0.2 seconds.
  • Depth: The agent generated plans requiring up to 42 high-level options, equivalent to approximately 3,800 low-level primitive actions.

By treating symbols as distributions, the agent can calculate the probability of plan success and expected rewards—capabilities missing in purely logical systems. While the current propositional approach is limited to specific objects, future work aims to develop relational symbols for broader generalization across different environments. Additionally, integrating the simultaneous learning of low-level controllers (options) and high-level symbols remains a key frontier for total autonomy.

Summary updated

Abstract

We introduce a framework that enables an agent to autonomously learn its own symbolic representation of a low-level, continuous environment. Propositional symbols are formalized as names for probability distributions, providing a natural means of dealing with uncertain representations and probabilistic plans. We determine the symbols that are sufficient for computing the probability with which a plan will succeed, and demonstrate the acquisition of a symbolic representation in a computer game domain.
BibTeX
@inproceedings{konidaris2015symbol,
  author = {George Dimitri Konidaris and Leslie Pack Kaelbling and Tomás Lozano-Pérez},
  title = {{Symbol Acquisition for Probabilistic High-Level Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=KjhmRwVL1jHA},
}
Figure