In classical artificial intelligence, the world is typically modeled as a clean, linear sequence of events. An agent finds itself in a state, executes a single action, and transitions to a new state. This foundational abstraction—the sequential action assumption—underpins everything from early automated planning to standard Markov Decision Processes (MDPs).
While mathematically convenient, this linear framing creates a severe mismatch with reality. The physical world is inherently concurrent. A manufacturing plant coordinates multiple machines simultaneously; a human chef chops vegetables with one hand while stabilizing a cutting board with the other; a robot navigates a room while concurrently streaming sensor data. When AI systems force these parallel realities into a strictly sequential bottleneck, their reasoning models break down.
Why Interleaving Fails as a Proxy for Concurrency
Historically, the most common workaround for handling simultaneous events was interleaving. Instead of truly modeling two actions happening at the same time, a system would pretend they occurred in a rapid, arbitrary sequence (e.g., Action A happens split-seconds before Action B, or vice versa).
As Michael P. Georgeff demonstrated in his foundational work (Georgeff, 1984; Georgeff, 1986), interleaving is a flawed approximation. It assumes that no two events occur at the exact same physical instant, failing to capture the true dynamics of simultaneous physical interactions.
Consider a simple physical example: two agents pushing opposite sides of a heavy swinging door with equal force at the exact same moment. The forces cancel out, and the door remains stationary. If we attempt to model this via interleaving—Agent 1 pushes, then Agent 2 pushes—the model will erroneously show the door swinging open and then slamming shut. The final world state is completely inaccurate because the interaction of the concurrent forces was lost in translation.
John McCarthy 0001 framed this as a core epistemological challenge for AI: classical formal logics struggle to express how overlapping actions or environmental changes influence one another over time without generating logical contradictions (McCarthy, 1977).
Formalizing Simultaneous Effects in Logic
To move beyond the sequential constraint, researchers had to fundamentally alter how actions modify state representations.
Instead of treating actions as instantaneous "before-and-after" snapshots, Georgeff introduced Process Models, which represent actions as continuous sequences of states (Georgeff, 1984). This allows a system to reason about mutual interference mid-action.
In the context of the Situation Calculus—a classic logic framework for reasoning about change—Fangzhen Lin et al. solved the "action-oriented frame problem" for concurrent events by introducing a global action sort (Lin et al., 1992). This mathematical construct treats a set of primitive actions executed simultaneously as a single, unified global action. By establishing this symmetry, the framework provides a formal mechanism to inherit or cancel individual effects based on how they interact when co-occurring.
Sequential Model: [State 0] --(Action A)--> [State 1] --(Action B)--> [State 2]
Concurrent Model: [State 0] --(Global Action {A, B})-----------------> [State 1]
Other approaches shifted the underlying ontology entirely. Michael Thielscher proposed a logic for dynamic systems where the environment is not static, but rather evolves continuously on its own (Thielscher, 1995). In this view, instead of being the sole cause of state changes, agents merely "steer" ongoing concurrent processes. Meanwhile, Chitta Baral explored how concurrent state changes conflict or combine non-trivially when actions have non-deterministic effects or are bound by static causal laws (Baral, 1995).
Taming the Combinatorial Explosion
If formalizing the logic of concurrency is difficult, planning with it is computationally brutal. This stems from a severe combinatorial explosion: if an agent can choose from $N$ possible primitive actions at any given step, allowing concurrent execution expands the action space to $2^N$ possible combinations.
Number of primitive actions (N): 3 --> [A], [B], [C]
Sequential choices: 3
Concurrent combinations (2^N): 8 --> [], [A], [B], [C], [A,B], [A,C], [B,C], [A,B,C]
Mausam tackled this bottleneck in the context of Concurrent Markov Decision Processes (Mausam, 2004). To bypass evaluating every possible combination, the author introduced Pruned Real-Time Dynamic Programming (RTDP), which uses provably sound logical rules to eliminate suboptimal action combinations before they are evaluated. Coupled with Sampled RTDP—which heuristically samples the joint action space—this work demonstrated that agents can find near-optimal concurrent plans with massive computational speedups.
In reinforcement learning, actions are often not just simultaneous, but also temporally extended (meaning they take varying amounts of time to complete). Khashayar Rohanimanesh et al. developed the Concurrent Action Model (CAM) to handle this semi-Markov decision environment asynchronously (Rohanimanesh et al., 2002). CAM allows agents to initiate multiple long-running tasks in parallel and defines mathematical strategies for when the agent should re-evaluate its decisions—either waiting for all parallel tasks to finish or dynamically re-deciding the moment a single sub-task terminates.
Modern Manifestations: Robotics and Vision
The sequential execution bias remains a persistent hurdle in modern AI applications, particularly as systems transition from virtual environments to physical deployment.
In computer vision and task verification, systems must determine if a human or robot has successfully executed a multi-step plan based on video data. Standard vision-language models typically rely on linear sequence models. However, RISHI HAZRA et al. demonstrated that this assumption fails when verifying real-world egocentric (first-person) videos, where humans naturally perform multiple actions at once (Hazra et al., 2023). Their Neuro-Symbolic Grounding framework explicitly maps parallel video segments to symbolic task steps to overcome this limitation.
Similarly, in robotics, Large Language Models (LLMs) are frequently used to generate high-level task plans. While LLMs are adept at sequencing text, they often lack the physical common sense required for parallel execution. As highlighted in recent work on pre-execution task plan verification (VerifyLLM, 2025), standard sliding-window analysis techniques assume a linear sequence of events. When a robot must execute sophisticated, real-time behaviors—such as moving a robotic arm while simultaneously reading a sensor (Traverso et al., 1995)—verification frameworks must explicitly accommodate overlapping temporal windows to ensure hardware safety and mission success.
Key Foundational Work
Epistemological Problems of Artificial Intelligence (1977) — contributed 2 concept elements to this direction.
A Theory of Action for MultiAgent Planning (1984) — contributed 1 concept elements to this direction.