Goals as Parallel Program Specifications

Leslie Pack KaelblingAAAI 1988 · OpenReview

Abstract

Classical planning is often inappropriate for generating actions in a dynamic world due to its computational complexity and serial nature. This paper presents Gapps, a formalism that allows programmers to specify an agent's behavior using symbolic goal-reduction rules. These rules are compiled into efficient, synchronous parallel circuits, enabling real-time response in domains that require parallel actions and lack complete operator descriptions.

The Problem: The Latency of Deliberation

In the late 1980s, the dominant AI paradigm relied on "classical planning": agents would encode world states in logic, search for a sequence of operators to reach a goal, and then execute that plan. However, this approach is fundamentally limited for real-world robotics. Classical planning is often computationally intractable and assumes the environment remains static during the "thinking" phase.

Robots operating in the real world must react to events in milliseconds. A search-based planner taking minutes to find a path is useless if the robot has already collided with an obstacle. Furthermore, classical planners struggle with parallel actions, such as navigating while simultaneously processing speech. Gapps was developed to provide a declarative programming interface that maintains the speed and parallelism of hardware circuits.

The Gapps Formalism

Gapps treats an autonomous agent as a transducer—a system that maps a continuous stream of sensory inputs to a stream of control outputs.

The Transduction Model

The architecture separates the agent into two primary components: Perception and Action. The perception component maintains an internal state based on sensory input, while the action component (defined by Gapps) maps the current state and perceptions directly to actions.

The internal architecture of a Gapps agent, showing the flow from perception and state to action.

Goal Types and Reduction

Programmers define behavior using three primitive goal types:

  1. do(a): Execute an instantaneous action.
  2. ach(p): Achieve a specific proposition.
  3. maint(p): Maintain a proposition over time.

High-level goals are broken down using defgoalr (goal reduction) rules. These rules are recursively evaluated by the Gapps compiler and transformed into a description for a synchronous digital circuit using a lower-level language called Rex. This ensures that the robot's logic is executed in constant time per clock cycle, regardless of the complexity of the original symbolic rules.

Key Insights: Prioritization and Parallelism

A core challenge in reactive systems is handling conflicting goals. Gapps introduces the prio-and operator, inspired by Asimov’s Three Laws of Robotics. This allows an agent to attempt a conjunction of goals while gracefully "dropping" lower-priority ones if they become impossible to satisfy. For example, a robot might prioritize "don't crash" over "reach the target."

A circuit implementation of prioritized conditionals, where conditions (c) and actions (a) are evaluated in a cascaded priority structure.

This prioritized structure is compiled into a series of conditional gates, as shown above, ensuring that the highest-priority valid action is always selected within a single clock cycle.

Another profound shift in Gapps is the view of planning as perception. Rather than planning being the core controller, it is treated as a perceptual process that informs the agent about which actions might lead to a goal. This information then feeds into the reactive Gapps program, allowing for a hybrid of routine behavior and deliberative insight.

Results and Implementation

The Gapps system was successfully implemented on the SRI mobile robot. It demonstrated that complex navigation behaviors could be written as modular, composable rules. Because the output is an action vector (e.g., controlling multiple motors and sensors simultaneously), the agent can perform truly parallel tasks.

While Gapps excels at routine, real-time behavior, it does not natively perform long-term "look-ahead" search. Future work suggests integrating classical planners as sub-components of the perception system, allowing the agent to benefit from high-level reasoning without sacrificing the guaranteed response times of the Gapps reactive core.

Summary updated

Abstract

Classical planning is inappropriate for generating actions in a dynamic world. This paper presents a formalism, called Gapps, that allows a programmer to specify an agent's behavior using symbolic goal-reduction rules that are compiled into an efficient parallel program. Gapps is designed for use in domains that require real-time response, that cannot be completely characterized by operator descriptions, and that allow multiple actions to be carried out in parallel.
BibTeX
@inproceedings{kaelbling1988goals,
  author = {Leslie Pack Kaelbling},
  title = {{Goals as Parallel Program Specifications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
  url = {https://openreview.net/forum?id=rJNjekb_WS},
}
Figure