Structured Circuit Semantics for Reactive Plan Execution Systems

Jaeho Lee, Edmund H. DurfeeAAAI 1994

Abstract

In the early 1990s, the proliferation of reactive AI systems—such as Procedural Reasoning Systems (PRS) and Reactive Action Packages (RAPs)—created a fragmented landscape where comparing different control logics was difficult. This paper introduces Structured Circuit Semantics (SCS), a formal meta-language designed to unify these diverse approaches. By extending Nilsson’s teleo-reactive programs with hierarchical structures, utility-based selection, and explicit failure handling, SCS provides a rigorous framework for analyzing and building robust robotic controllers.

1. Introduction

The field of artificial intelligence in the early 1990s saw a surge in "reactive" systems designed to enable agents to operate in unpredictable, dynamic environments. While systems like PRS, RAPs, and Universal Plans were effective, they lacked a common formal basis. This "Wild West" of reactive planning meant that the underlying logic was often embedded within the system's interpreter rather than the plan itself, making cross-system comparison nearly impossible.

Jaeho Lee and Edmund H. Durfee’s 1994 work, Structured Circuit Semantics for Reactive Plan Execution Systems, addresses this by proposing SCS. SCS acts as a formal framework that translates the hidden control logic of various systems into a unified language based on circuit-like feedback loops.

2. The Problem: A Lack of Common Denominator

The authors identify a fundamental difficulty in evaluating reactive plan execution: the lack of a shared language. When an autonomous agent, such as an outdoor robotic vehicle, must choose between multiple actions (e.g., driving vs. flying), different systems resolve these choices using disparate mechanisms—some through hard-coded priorities and others through complex hierarchies.

Specifically, the authors highlight four gaps in existing models, particularly Nilsson’s Teleo-Reactive (T-R) programs:

  1. The Execution Cycle Gap: While T-R programs assume continuous feedback, real-world computational cycles are discrete. This discrepancy can lead to logical inconsistencies if not handled carefully.
  2. Rigidity: Static ordering (e.g., "always do A before B") makes systems too brittle for highly dynamic environments.
  3. Lack of Utility: Many systems lack a mechanism to choose the "best" action based on situational context or resource costs.
  4. Opaque Failure: Systems often lack explicit exception handling, leading to "blind" repetition of failing actions without a clear recovery protocol.

3. Structured Circuit Semantics (SCS)

SCS builds upon the concept of Circuit Semantics, where a program behaves like an electrical circuit with continuous feedback. To address the limitations of pure feedback loops, the authors introduce "Structure" through several key innovations:

Atomic Actions

To bridge the execution cycle gap, SCS defines "atomic" steps. These are actions guaranteed to complete within a specific timeframe, preventing the system from entering an inconsistent state during a mid-cycle environment change. This provides a formal way to avoid the "oscillation" problems where a robot flips rapidly between two states.

Hierarchical Constructs

SCS introduces recursive steps to manage complexity and decision-making:

  • do any: Facilitates nondeterministic choice, allowing the system to attempt various actions until one succeeds.
  • do best: Implements utility-based choice, where the system calculates which action has the highest "bid" or value in the current context.
  • do all: Enables parallel execution of multiple circuits.
  • do first: Maintains traditional priority-based execution.

Dynamic Condition Stacking

As an agent executes a plan, conditions are organized into a stack. Upon the completion of every atomic action, the system re-evaluates the entire stack from top to bottom. This ensures that if the environment changes in a way that invalidates the current plan, the system reacts immediately. Conditions in SCS are "durative"—they must remain true throughout an action's execution, not just at the start.

4. Evaluation and Insights

The framework was evaluated through theoretical comparative analysis and the application of the formalism to classic problems.

The BNL Problem

The authors applied SCS to the "B Not Last" (BNL) problem, a classic block-stacking puzzle where physical constraints dictate the order of operations. By translating a T-R program for BNL into SCS, they revealed that the original program contained implicit ordering preferences that were not obvious to the user. SCS made these biases explicit.

Unification of Systems

A primary achievement of the paper was demonstrating that SCS could represent the core features of major reactive systems—including Universal Plans, PRS, and RAPs—within a single, consistent syntax. This proved that SCS could serve as a universal meta-language, allowing researchers to see the "Decision Layer" (utility and logic) as distinct from the "Circuit Layer" (feedback loops).

5. Discussion and Limitations

While SCS offers a powerful formalization, the authors acknowledge several challenges:

  • Computational Overhead: Re-evaluating the condition stack after every atomic action may be computationally taxing for systems operating at extremely high frequencies.
  • Syntactic vs. Semantic Equivalence: While SCS can capture the logic of other systems, proving that two different programs are functionally identical remains a complex task.
  • Multi-Agent Coordination: The current framework focuses on single-agent execution. While the authors suggest SCS could facilitate inter-agent communication, this remains a subject for future research.

6. Conclusion

Structured Circuit Semantics provides a rigorous foundation for the design and analysis of reactive systems. By making the "hidden" logic of plan execution explicit and providing a structured way to handle utility and failure, SCS allows researchers to move beyond ad-hoc system design toward a more principled approach to robotic control.

Summary updated

BibTeX
@inproceedings{lee1994structured,
  author = {Jaeho Lee and Edmund H. Durfee},
  title = {{Structured Circuit Semantics for Reactive Plan Execution Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure