Abstract
Traditional AI planning models often struggle to reconcile the causal consequences of actions with their temporal duration and concurrency. This paper presents a formal semantic model that integrates interval-based temporal logic with a functional "result" structure. By utilizing "world-histories" and a counterfactual-based result function ($F_{cl}$), the model allows for reasoning about actions that overlap in time, depend on continuous external conditions, or interfere with one another.
Introduction: The Gap in AI Planning
In the late 1980s, AI planning research faced a dichotomy between two dominant formalisms. Situation Calculus excelled at describing the state-changes resulting from actions but treated these actions as instantaneous transitions between snapshots of the world. Consequently, it could not represent events occurring during an action's execution or the interaction of concurrent tasks.
Conversely, Temporal Logics (such as those proposed by Allen and McDermott) provided robust frameworks for describing intervals of time and the relationships between them but lacked a formal mechanism to distinguish the consequences of an agent's choices from background events. Pelavin and Allen sought to bridge this gap, modeling agents performing complex, duration-based actions—such as sailing across a lake—where success depends on external conditions (like wind) holding true throughout the interval.
Methodology: World-Histories and the Result Function
The proposed model shifts the focus from discrete "situations" to world-histories. A world-history is a complete description of the state of the world over all time. To model the effect of an action, the authors introduce the $F_{cl}$ function, a "result function" inspired by the counterfactual logic of Stalnaker and Lewis.
The $F_{cl}$ function takes a set of basic action instances ($bai-set$) and a reference world-history ($h$). It returns a set of "closest" world-histories where those actions actually occurred. This approach allows the model to maintain a "Minimal Change Principle": the resulting histories are as similar as possible to the original, changing only what is logically necessary to accommodate the new actions.
As shown in the definition above, if a valid composition of actions exists that satisfies the necessary occurrence conditions ($ALL-OC$), the function returns the modified histories. Otherwise, it returns the original history, effectively modeling a failure where the action fails to change the world.
Key Insights
Interference as Logical Conflict
A significant contribution of this model is its formalization of action interference. Interference is not merely a predefined constraint but a logical consequence. If an agent attempts to perform two actions simultaneously (e.g., moving an object to two different locations) and the model cannot find a consistent world-history where both occur, the actions are deemed to interfere.
Context-Dependent Concurrency
The model recognizes that concurrency is often context-dependent. Two actions might be compatible in one environment but interfere in another due to resource constraints or external environmental factors. By grounding the model in world-histories, these nuances are captured naturally.
Branching Time and Accessibility
To represent choice and possibility, the model employs an accessibility relation ($R$). This allows for a "branching time" structure where different world-histories share a common past up to a certain point but diverge into different possible futures based on the agent's actions.
Results and Framework Integration
The authors successfully unified interval-based temporal logic with a functional result structure. Key achievements include:
- Formal Composition Rules: The introduction of $BA-CMP1$ and $BA-CMP2$ rules for aggregating concurrent or sequential actions into coherent plan instances.
- Dynamic External Events: The ability to represent actions influenced by properties that must hold during execution, rather than just as discrete prerequisites at the start.
Limitations and Future Directions
While providing a rigorous semantic foundation, the paper identifies several areas for further development. The focus remains on "basic" primitive actions; the full extension to complex, hierarchical plans was deferred to subsequent work. Additionally, the model describes the semantics of the logic rather than providing a computationally efficient algorithm for real-time planning. Finally, the framework is primarily deterministic in its logical structure, leaving probabilistic outcomes for future extensions.
Summary updated