Semi-Black Box: Rapid Development of Planning Based Solutions

Michael Katz, Dany Moshkovich, Erez KarpasAAAI 2018 · DOI

Automated planning—the process of finding a sequence of actions to reach a goal—is a cornerstone of artificial intelligence. However, developers often face a stark choice: use intuitive but slow "black box" models, or learn complex symbolic languages like PDDL to achieve high performance. This paper, presented at AAAI-18, introduces the Semi-Black Box (SBB) approach, a framework that allows software developers to build efficient planning solutions using standard object-oriented programming in Java while automatically deriving the powerful heuristics usually reserved for symbolic models.

The Usability vs. Performance Trade-off

Traditionally, planning involves two main paradigms:

  1. The Black Box Approach: Developers write procedural code (e.g., a getSuccessors() function). While intuitive, this method lacks "heuristics"—mathematical shortcuts that guide search algorithms. Without them, the search space expands exponentially, causing the system to fail as problems scale.
  2. The Model-Based Approach (PDDL): Problems are described symbolically. This allows for automatic heuristic generation, but PDDL is difficult to master and struggles with dynamic environments where objects are created or destroyed on the fly.

SBB addresses this gap by providing a middle ground that is accessible to non-AI experts yet performant enough for real-world applications.

The SBB Framework: Object-Oriented Planning

The core innovation of SBB is the use of Stereotypes. Instead of an opaque black box, developers inherit from predefined classes that the framework "understands."

  • Entity Stereotypes: Classes like MobileEntity (which tracks location and time) or Place.
  • Operator Stereotypes: Common actions such as move, load, and unload.

Because the framework understands the semantics of these stereotypes, it can automatically "project" procedural Java code into a simplified symbolic representation. From this projection, SBB builds a Lifted Relaxed Planning Graph. Unlike standard planners that must "ground" every possible action-object combination beforehand—often leading to memory crashes—SBB generates relevant instances on the fly. This allows it to derive heuristics (specifically a variant of the $h_{FF}$ heuristic) to guide the search without requiring any symbolic logic from the user.

A visual comparison of a trivial commuter pooling solution (a) versus an optimized solution (b) generated by the planner.

Evaluation and Key Results

The authors evaluated SBB against state-of-the-art planners (LAMA, FF, and OPTIC) using two primary domains: Commuter Pooling (a transportation task with strict constraints) and Evolution (a biological model involving dynamic population growth).

Performance and Quality

In the Commuter Pooling domain, SBB demonstrated superior quality and scaling. While a pure black-box approach failed as the number of participants grew, SBB scaled effectively to the largest test cases. As shown in the performance data, SBB achieved a higher aggregate IPC Quality Score (14.00) than both LAMA (13.51) and FF (6.68).

Comparative performance metrics showing plan cost, quality, and total time across various planners.

Speed and Expressiveness

SBB proved significantly faster than traditional symbolic planners in several instances. For example, in task 04_2, SBB solved the problem in just 1.5 seconds, whereas LAMA required over 93 seconds. Furthermore, SBB successfully handled the Evolution domain—a task involving the creation of new entities that is technically beyond the standard PDDL fragment.

Key Insights

  • Stereotypes as the Missing Link: By identifying objects as "mobile" or actions as "load," the solver can infer enough structure to guide the search without a full symbolic language.
  • Handling Dynamic Populations: Built on Java, SBB naturally handles the creation of new objects (like offspring), whereas PDDL requires "dummy" objects to be defined upfront.
  • Bypassing Grounding Bottlenecks: The "lifted" heuristic approach avoids the memory exhaustion that often plagues PDDL planners in large-scale environments.

Conclusion and Future Work

While the current SBB prototype is optimized for transportation and temporal stereotypes, it proves that developers do not need to sacrifice performance for ease of use. Future work aims to expand the library of stereotypes to include landmarks and abstractions, support non-deterministic actions, and further refine the heuristic engine to capture more complex logic automatically.

Summary updated

BibTeX
@inproceedings{katz2018semi,
  author = {Michael Katz and Dany Moshkovich and Erez Karpas},
  title = {{Semi-Black Box: Rapid Development of Planning Based Solutions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12093},
}
Figure