Multi-Value Decision Diagram (MDD)

An MDD compresses the exponential number of possible optimal paths into a directed acyclic graph (DAG). Each node represents a specific location at a specific time step (depth). Edges represent valid moves between locations in consecutive time steps.

• Eliminates Redundancy: Identical path segments from different full paths are merged into a single subgraph.
• Guarantees Optimality: By construction, every root-to-leaf path in the MDD corresponds to a distinct path for the agent that meets the exact cost bound (e.g., shortest path length).

The MDD is organized into layers, where each layer corresponds to a discrete time step from the start (t=0) to the goal at the maximum cost bound (t=C).

• Layer 0: Contains only the start node.
• Layer C: Contains only the goal node.
• Intermediate Layers (1 to C-1): Contain all locations the agent can occupy at that exact time while still reaching the goal on time.

This structure allows algorithms to reason about space-time conflicts efficiently by checking for node collisions within the same layer.

An MDD for cost C is built using a two-pass breadth-first search (BFS) process on the agent's graph (e.g., a 4-connected grid).

1. Forward Pass (BFS from Start): Calculates the minimum distance g(start, v) from the start to every node v.
2. Backward Pass (BFS from Goal): Calculates the minimum distance h(v, goal) from every node v to the goal.
3. Node Inclusion Rule: A node v is included in the MDD at layer t if and only if g(start, v) <= t and g(start, v) + h(v, goal) == C. This ensures every included node lies on some optimal path.

Edges are added between nodes in consecutive layers if they are connected in the underlying graph.

The primary use of MDDs in algorithms like Conflict-Based Search (CBS) is for fast, pairwise conflict detection. Given MDDs for two agents, a conflict exists if:

• Vertex Conflict: The same node appears in both MDDs at the same layer (time step).
• Edge Conflict: An edge (u,v) at layer t in one MDD appears as the reverse edge (v,u) at the same layer t in the other MDD.

Checking for conflicts becomes a linear-time merge operation over the layered structures, far more efficient than comparing lists of individual paths.

When a conflict is found, CBS imposes a constraint (e.g., "Agent 1 cannot be at node X at time t") and the affected agent's MDD must be rebuilt. The MDD structure allows for efficient filtering.

• The constrained node is removed from the corresponding layer.
• A pruning pass then removes any nodes (and connected edges) that no longer have a valid connection from the start layer to the goal layer through the remaining graph.
• If pruning removes all nodes from a layer, the MDD becomes empty, proving no solution exists for the agent under the current constraints.

The size and complexity of an MDD are determined by the cost bound C and the branching factor of the environment.

• Width: The maximum number of nodes in any single layer. In open spaces, this can be large.
• Depth: Equal to the cost bound C + 1.
• Memory Footprint: Typically O(b * C), where b is the average width, which is vastly smaller than the O(b^C) number of full paths it represents.

For very large C or dense graphs, pruned MDDs or partial MDDs that only compute layers up to a planning horizon are used to maintain tractability.

Conflict-Based Search is a two-level optimal MAPF algorithm that uses MDDs as a core component. At the high level, it searches a constraint tree, resolving conflicts (e.g., vertex or edge conflicts) between agents. For each node in this tree, the low level uses an MDD to replan an optimal path for a single agent that respects the imposed constraints. The algorithm's efficiency heavily relies on the compact representation of all optimal paths provided by the MDD for fast constraint validation and cost bounding.

Sum of Costs is the primary optimality criterion for many MAPF problems, defined as the sum of the path lengths (or travel times) for all individual agents from their start to goal locations. An MDD is constructed for a specific cost bound, which is typically the optimal SOC for that agent alone or a value derived from the global solution cost. The MDD explicitly encodes all paths for that agent that meet this exact cost, making it the perfect tool for algorithms like CBS that need to explore alternative optimal paths during conflict resolution.

A Conflict Avoidance Table is a complementary data structure to an MDD in many MAPF solvers. While an MDD encodes the possible paths for one agent, a CAT aggregates the planned space-time reservations for all other agents. During path planning or validation for a single agent (e.g., using its MDD), the algorithm queries the CAT to check for conflicts. The combination allows for efficient multi-agent reasoning: the MDD provides the candidate paths, and the CAT provides the environment of moving obstacles to avoid.

Increasing Cost Tree Search is another optimal MAPF algorithm that leverages the concept behind MDDs. Instead of building explicit MDDs, ICTS searches a tree of possible cost combinations for all agents. For each cost combination, it must verify if a feasible set of paths exists. This verification step often conceptually uses an MDD-like reasoning: for each agent, given its individual cost from the combination, does a path exist? MDDs provide a formal and efficient way to answer this 'path existence' query, which is central to the ICTS paradigm.

Bounded Suboptimal Search refers to MAPF algorithms that trade optimality for speed, guaranteeing a solution cost no worse than a factor (e.g., 1.2) of the optimal cost. MDDs can be adapted for these algorithms by constructing them for a suboptimal cost bound (optimal cost * suboptimality factor). This expanded MDD contains many more paths, giving the low-level planner more flexibility to avoid conflicts quickly. Techniques like Enhanced CBS use this approach to find faster, near-optimal solutions.

A Time-Expanded Graph is a direct alternative modeling approach to using MDDs for temporal planning. It explicitly duplicates the spatial graph for each timestep, turning a dynamic problem into a static one. An MDD can be seen as a highly compressed, lossless representation of the relevant portion of a time-expanded graph for a single agent and a fixed cost. While a full time-expanded graph can be prohibitively large, an MDD extracts only the nodes and edges that lie on some optimal path, offering massive efficiency gains for optimal search algorithms.