Abstract
This paper introduces a formal framework for agent abstraction in dynamic environments using the Situation Calculus and the ConGolog programming language. By defining "refinement mappings" that link high-level actions to complex low-level programs, the authors provide a mathematically rigorous way to plan at an abstract level while guaranteeing that those plans remain valid and executable in detailed, real-world environments. The framework establishes conditions for sound and complete abstractions, ensuring that high-level reasoning accurately reflects low-level capabilities.
1. Introduction
Intelligent agents, such as autonomous robots or automated logistics systems, often operate in environments too complex to model in exhaustive detail. Planning at the level of individual motor movements or millisecond-scale sensor readings is computationally infeasible. The standard solution is abstraction: creating a simplified high-level model that ignores irrelevant details. However, ensuring a "sound" relationship between these levels is difficult. If a high-level plan specifies a task like "Deliver the package," there must be a guarantee that a sequence of low-level actions (e.g., navigating specific roads, handling cargo) exists to achieve it. This paper formalizes this relationship within the context of dynamic action theories.
2. Formal Framework
The proposed framework is built upon two pillars of automated reasoning: Situation Calculus (SitCalc), a logic-based language for representing change, and ConGolog, a high-level agent programming language for complex behaviors.
The core of the approach is the Refinement Mapping ($m$), which performs two critical functions:
- It associates each high-level action with a ConGolog program that implements it at the low level.
- It translates high-level fluents (dynamic properties) into low-level formulas.
To ensure consistency, the authors employ $m$-bisimulation, a formal method to verify that for every step in the high-level model, there is a corresponding set of steps in the low-level model. The framework distinguishes between Sound Abstraction, where a high-level plan's success implies at least one valid low-level refinement, and Complete Abstraction, where the high-level theory serves as a perfect summary of the low-level knowledge regarding abstract concepts.
3. Illustrative Example: Transport Logistics
The authors demonstrate their theorems using a Transport Logistics scenario. In this example, a high-level agent plans routes between locations, while the low-level system manages the specifics of road segments, weather conditions, and delivery signatures.
As shown in Figure 1, the high-level action of taking a route (e.g., Route B) is refined into a sequence of specific road segments (d, e) and intermediate locations (L3). This mapping allows the agent to reason about the delivery goal without managing every individual turn or road condition in the initial planning phase.
4. Key Theoretical Results
The paper provides several significant contributions to the field of formal methods:
- Executability Guarantee: In a sound abstraction, any sequence of high-level actions that is executable in the abstract model is guaranteed to have an executable refinement in the concrete model.
- Hierarchical Planning without Backtracking: Sound abstractions allow for "refining" high-level plans into low-level actions incrementally. Because the abstraction is sound, a valid refinement is guaranteed to exist, eliminating the need to backtrack to the high-level plan during execution.
- Verification via Theorem 9: The authors provide a set of proof-theoretic conditions that allow developers to verify the soundness of an abstraction using standard logic tools, rather than exhaustive state-space checking.
- Determinism and Monitoring: The framework shows that even with low-level non-determinism, a sound abstraction ensures predictable high-level outcomes. Furthermore, inverse mappings allow for "monitoring," where raw low-level actions are translated back into high-level explanations for human supervisors.
5. Conclusion and Future Work
This research formalizes sound and complete abstractions for dynamic action theories, a significant advancement over previous work limited to static domains. While the current model assumes situation-determined high-level actions and focuses on single-layer mappings, it provides a robust foundation for future extensions. Subsequent work will address multi-layered hierarchies, sensing actions under partial observability, and the automated synthesis of refinement mappings from high-level goals.
Summary updated