Time-Expanded Graph

The core mechanism of a time-expanded graph is the explicit discretization of time. The original spatial graph (e.g., a warehouse floorplan) is replicated at each discrete time step (t=0, 1, 2...). A node (v, t) represents being at spatial vertex v at time t. An edge from (v, t) to (u, t+1) represents the action of moving from v to u, taking one time unit. This structure converts the challenge of 'when' to move into the simpler problem of 'where' to go in a larger, static graph.

Time-expanded graphs naturally encode temporal constraints that are critical for collision avoidance and scheduling.

• Moving Obstacles: A dynamic obstacle's future path can be blocked by simply removing the corresponding (v, t) nodes from the graph.
• Resource Reservations: A table or machine with a usage schedule is modeled by removing nodes for its location during occupied time steps.
• Agent Interactions: Paths for multiple agents are found by performing a search in the joint state space of the time-expanded graph or by using reservation tables that mark nodes (v, t) as occupied, preventing other agents from planning to use them.

By transforming the problem into a static graph, time-expanded graphs allow the application of classical, optimal graph search algorithms like A* or Dijkstra's algorithm. A path from (start, 0) to (goal, T) in the expanded graph corresponds to a spatio-temporal trajectory that reaches the goal at exactly time T. This facilitates centralized planning where a global optimizer can compute collision-free paths for an entire fleet, optimizing for metrics like makespan (total completion time) or sum-of-costs. Algorithms like Multi-Agent A (MAA)** operate directly on this joint space-time representation.

The primary drawback is exponential state explosion. The graph size is |V| × T, where T is the time horizon. For long horizons or large fleets, the joint state space becomes intractable.

• Key Limitation: The time horizon T must be known or estimated in advance. Planning for an indefinite horizon is not directly possible.
• Comparison to SIPP: Algorithms like Safe Interval Path Planning (SIPP) were developed to address this by grouping contiguous safe time intervals at a location, drastically reducing the search space compared to a full time expansion.
• Use Case: Best suited for problems with a bounded, finite horizon or as a conceptual framework for understanding temporal planning.

Time-expanded graphs are not just a planning method but a conceptual model underlying many advanced Multi-Agent Path Finding (MAPF) techniques.

• Conflict-Based Search (CBS): Uses time-expanded graphs implicitly for planning individual agent paths during its low-level search.
• MDD Construction: A Multi-Valued Decision Diagram (MDD) for an agent is essentially a compact representation of all possible paths for that agent within a cost bound in a time-expanded graph.
• Bounded-Suboptimal Solvers: Algorithms like Windowed Hierarchical Cooperative A (WHCA)** use a time-expanded reservation table for a short planning window to achieve scalability.

In heterogeneous fleet orchestration, time-expanded graphs model the core scheduling challenge.

• AMR & AGV Coordination: Planning routes for Autonomous Mobile Robots and Automated Guided Vehicles to avoid collisions at intersections and docking stations.
• Integrated Human Workers: Modeling the predicted paths of manual pickers or forklift drivers as dynamic obstacles within the graph.
• Temporal Resource Booking: Ensuring a packing station or elevator is only used by one agent at a time by removing its (location, time) nodes for the duration of each reservation.
• Output: The solution is a set of space-time trajectories, providing each agent with a precise timetable: 'Be at location A at time 5, then move to B by time 7.'

This is the canonical application for Time-Expanded Graphs (TEGs). In centralized MAPF, the joint state-space of all agents is constructed as a TEG, where each node represents a specific agent configuration (e.g., positions of all robots) at a discrete time step. This allows algorithms like Multi-Agent A (MAA)** to search for a collision-free plan for the entire fleet by finding a path through this static graph. The TEG explicitly encodes vertex conflicts (two agents in same cell at same time) and edge conflicts (agents swapping places).

TEGs are deployed in Automated Storage and Retrieval Systems (AS/RS) and autonomous mobile robot (AMR) fleets for real-time order fulfillment. The graph models:

• Pick stations, storage racks, and transit lanes as spatial nodes.
• Time steps corresponding to the robots' control cycles.
• Dynamic obstacles like human workers or other robots as pre-reserved nodes. The orchestration platform uses the TEG to compute makespan-optimal or sum-of-costs (SOC)-optimal task sequences, ensuring robots retrieve items and deliver them to packing stations without deadlock.

In aviation, a TEG models airspace sectors (nodes) across discrete time intervals. This is critical for:

• Conflict detection and resolution: Identifying potential mid-air collisions by checking for shared TEG nodes.
• 4D trajectory planning: Assigning unmanned aerial vehicles (UAVs) precise paths in space and time to deconflict dense airspace.
• Ground delay programs: Managing airport arrival slots by expanding the time dimension at runway nodes. The TEG structure allows planners to impose k-robust temporal buffers between aircraft for safety.

Beyond pure navigation, TEGs schedule resources and tasks in smart factories. Nodes can represent:

• A machine tool being available at a specific time.
• A transport robot arriving at a workstation.
• A human operator completing an assembly step. Edges represent feasible transitions between these resource-time states. This model enables job-shop scheduling where the goal is to find a path through the TEG that completes all manufacturing orders while respecting machine capacities, robot delivery times, and operator shifts.

Game engines use TEGs for coordinated squad movement in real-time strategy (RTS) games. The navigation mesh of the game map is expanded over time to plan synchronized maneuvers for multiple units. This allows for complex tactics like:

• Flanking maneuvers where units arrive at positions simultaneously.
• Formation movement through narrow passages.
• Dynamic avoidance of moving environmental hazards or other player units. The static graph search is often performed during the game's planning phase to generate smooth, collision-free group paths.

The TEG is one of several techniques for temporal planning; understanding its trade-offs is key for system design.

• Vs. Space-Time A*: Space-Time A* searches directly in a continuous space-time domain, while a TEG is a fully discretized pre-computation. TEGs guarantee completeness for the discretized problem but can suffer from state explosion.
• Vs. Safe Interval Path Planning (SIPP): SIPP is more memory-efficient for dynamic environments with few moving obstacles. It groups time into safe intervals rather than expanding every time step, but requires more complex reasoning about interval boundaries.
• Vs. Velocity Obstacle (VO) Methods: VO approaches (like ORCA) are decentralized and reactive, suitable for dense, unpredictable crowds. TEGs are better for centralized, optimal planning in structured environments with known agent schedules.

Multi-Agent Path Finding (MAPF) is the core computational problem that Time-Expanded Graphs help solve. It involves finding collision-free paths for multiple agents from their start locations to their goal locations in a shared, typically discretized, environment. The primary objectives are to minimize makespan (total completion time) or sum-of-costs (total travel time for all agents). MAPF is NP-hard, leading to the development of specialized algorithms like CBS, ICTS, and planning models like TEGs.

Conflict-Based Search (CBS) is a leading optimal algorithm for MAPF. It operates on two levels:

• High-level: Searches a constraint tree, where each node contains a set of constraints (e.g., "agent A cannot be at vertex V at time T") and a solution satisfying them.
• Low-level: Performs a Space-Time A* search for each agent, respecting the current constraints. When a vertex conflict or edge conflict is found, CBS branches by adding constraints to resolve it. It is often more efficient than searching the full joint state space directly.

Space-Time A* is a fundamental single-agent path planning algorithm used within MAPF solvers like CBS. It extends the classic A* algorithm by explicitly including time as a third dimension in its search space (x, y, t). This allows it to find paths that avoid reservations made by other agents in a Conflict Avoidance Table (CAT). It is the direct, exhaustive method for searching a Time-Expanded Graph, where each (location, time) pair is a unique node.

Safe Interval Path Planning (SIPP) is a more efficient alternative to Space-Time A* for dynamic environments. Instead of expanding every timestep, SIPP groups time into safe intervals—periods during which a location is continuously free of obstacles or other agent reservations. The algorithm plans paths between these intervals, dramatically reducing the size of the search graph compared to a full Time-Expanded Graph. It is particularly effective for lifelong MAPF (LMAPF) where replanning is frequent.

A Multi-Value Decision Diagram (MDD) is a compact data structure used to represent all possible optimal paths for a single agent within a given cost bound (e.g., its shortest path length). In MAPF, MDDs are used in algorithms like ICTS and for advanced conflict analysis in CBS. By encoding only states reachable via optimal paths, MDDs allow algorithms to reason about agent interactions without enumerating all possible paths, improving pruning efficiency and conflict detection.

Optimal Reciprocal Collision Avoidance (ORCA) is a decentralized, velocity-based approach for local, reactive navigation, contrasting with the centralized, pre-planned nature of TEG-based solutions. Each agent observes the velocities of nearby agents and computes a Velocity Obstacle (VO)—the set of its own velocities that would cause a collision. ORCA then selects the closest collision-free velocity to its preferred velocity, assuming other agents perform a reciprocal calculation. It is used for continuous, real-time control rather than discrete graph planning.