Abstract
This paper presents a foundational effort in AI to move beyond simple sequential planning toward a robust formalism for parallel actions with duration. It introduces "action structures"—sets of actions that can occur concurrently and have lasting effects on the world—centered on the innovation of the prevail condition to model shared resources and non-interference.
Introduction
In the mid-1980s, most AI planning systems, such as STRIPS, operated on the "sequential world" assumption: actions were treated as instantaneous transitions from one state to the next. However, the real world is characterized by actions with duration and multiple simultaneous events. While fields like Operating Systems had developed concurrent programming models, these relied on explicit synchronization primitives (like semaphores) that do not naturally mirror natural language narratives. This paper addresses the gap for a formalism that describes parallel, real-world events without forcing them into a computer program metaphor.
Methods
The authors build their representation on several key formal pillars:
Partial State Descriptions
Instead of defining every detail of the world, the model uses "partial states" where features can be a specific value or "undefined." These states are organized into a lattice, where the ordering relation is "contains more information than."
The Four-Tuple Action
An action is defined as [f, b, v, e]:
- f (Prevail condition): What must hold during the action.
- b (Precondition): What must hold before the action.
- v (Operation): The name of the action itself.
- e (Postcondition): What holds after the action.
Coherence and Admissibility
Action structures are sets of action occurrences partially ordered in time. The authors define mathematical criteria for an action structure to be "coherent" (internally consistent at time points) and "admissible" (guaranteed to be executable without parallel actions interfering with each other's prevail conditions).
Illustrative Example: The Pancake Scenario
As a theoretical paper, the formalism is validated using a "toy world" scenario: preparing a meal of pancakes and coffee. This example demonstrates resource constraints (e.g., one stove burner) and the need for certain conditions (the stove being hot) to prevail during specific tasks.
Key Insights and Results
- The "Prevail Condition" as a Shared Resource: Pre/post-conditions are analogous to "read/write" access, while prevail conditions are like "read-only" access. This allows multiple actions to depend on the same state simultaneously without conflict.
- Natural Language Mapping: Many natural language phrases using "keep" (e.g., "keep the car on the road") map directly to prevail conditions, suggesting the formalism is well-suited for story understanding.
- Alignment for Safety: The "alignment" property ensures that if one action changes a feature, no other parallel action is relying on that feature as a prevail condition at the same time, preventing physical "race conditions."
The paper successfully proves a "Model Existence" property: if an action structure is admissible, there is a guaranteed sequence of world states that satisfies the plan.
Limitations and Future Work
The current model focuses on non-interference rather than "coordinated actions" where two parallel actions must interact to succeed (e.g., two people carrying a heavy table). Additionally, the authors acknowledge that while the current model uses flat domains, future work could extend this to continuous ranges or feedback-loop engineering in "naive control theory."
Summary updated