Introduction
In the field of autonomous systems, the Belief-Desire-Intention (BDI) model has long served as a standard for developing agents that act based on internal beliefs and goal-oriented intentions. While existing BDI programming languages, such as Jason or JACK, provide robust frameworks for agent development, they typically handle concurrency through interleaving. In an interleaved model, the system simulates parallel execution by rapidly switching between tasks, effectively "cheating" mathematically by ensuring only one action occurs at any specific discrete step.
This paper introduces Concurrent CAN (CCAN), a formal framework designed to move beyond interleaving toward "true concurrency." By providing an operational semantics where actions can physically overlap in time, CCAN enables agents to better exploit modern multi-core hardware and accurately model complex physical interactions, such as those found in multi-robot coordination.
The Problem: Interleaving vs. True Concurrency
The primary limitation of interleaving is its inability to represent scenarios where actions are truly simultaneous. Consider a manufacturing scenario where one robot must hold a workpiece while another engraves it. In an interleaved model, the system represents this as a sequence: Robot A moves, then Robot B moves, then Robot A moves again. While sufficient for high-level software logic, this fails to capture the physical reality of overlapping durations and timing-critical dependencies. Furthermore, interleaving cannot fully leverage parallel processing power, as the underlying logic remains fundamentally sequential. The authors address this by developing a formal mathematical foundation that allows for the simultaneous execution and recording of multiple actions.
The CCAN Framework
Building upon the Cognitive Agent Notation (CAN), the authors propose CCAN, which introduces several technical innovations to manage the complexity of true concurrency:
1. Pomsets and Action History
Traditional BDI models record action history as a linear list. CCAN replaces this with pomsets (partially ordered multisets). This structure allows the agent's history to reflect that Action A and Action B occurred in parallel, while Action C occurred only after both were completed. This provides a more accurate trace of the agent's physical and logical behavior.
2. Dual-Type Transitions
To manage nested concurrency, the semantics utilize two distinct types of transitions:
- ONE: Represents a single execution step within the system.
- ALL: Represents the aggregation of all possible internal steps within a concurrent branch. This "step-into" logic allows the system to track the progress of parallel branches independently before reconciling them.
3. State Merging and Non-Interference
When parallel branches conclude, the system must reconcile their effects on the agent's environment. CCAN defines a MERGE function for the Belief Base and an APPEND function for the action history. To ensure logical consistency and avoid race conditions, the authors impose non-interference constraints: concurrent branches are prohibited from sharing variables that might conflict or attempting to modify the same beliefs simultaneously in contradictory ways.
Key Insights and Theoretical Results
The core contribution of this work is the formal proof that true concurrency is a superset of interleaving. The authors establish that any behavior produced by an interleaved model can be replicated in CCAN, but CCAN can represent schedules—such as overlapping sensor readings or continuous background tasks—that interleaving cannot.
Formal Theorems
- Termination (Theorem 1): The semantics ensure that a concurrent program only succeeds if all internal parallel branches succeed, preventing the agent from proceeding while background tasks are still active.
- Soundness and Completeness (Theorem 2): This establishes that the action history produced by a branch in isolation remains valid when that branch is executed concurrently, ensuring the logic scales without breaking.
- Relationship to Interleaving (Theorem 3): This theorem formally links CCAN to traditional BDI languages, proving it is a valid and more expressive evolution of the standard CAN semantics.
Qualitative Modeling: The Manufacturing Example
To demonstrate the practical utility of CCAN, the authors model a manufacturing station involving a camera, a rotating fixture, and a robotic milling arm. In this scenario, a 25-second camera recording must span across multiple shorter, simultaneous robotic rotations and tool changes. CCAN successfully represents this overlap, a task that is notoriously awkward or impossible to define precisely in standard, interleaved BDI models.
Limitations and Future Work
While CCAN provides a rigorous foundation for true concurrency, it currently requires concurrent branches to be strictly independent. They cannot easily communicate or share variables during execution. Future research will focus on relaxing these constraints to allow for inter-branch communication and more nuanced failure recovery mechanisms, where one parallel branch might dynamically correct an error caused by another. Additionally, the authors aim to integrate these concurrent semantics with advanced planning features, such as Hierarchical Task Network (HTN) planning, to further enhance agent autonomy.
Summary updated