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.
Goal Types and Reduction
Programmers define behavior using three primitive goal types:
do(a): Execute an instantaneous action.ach(p): Achieve a specific proposition.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."
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