Bounded Suboptimal Search

The defining feature is a provable bound on suboptimality, typically expressed as a multiplicative factor ε (epsilon). If C* is the optimal solution cost, the algorithm guarantees a solution with cost C ≤ (1 + ε) * C*. For example, with ε = 0.1, the solution is guaranteed to be no worse than 10% more expensive than the optimal path. This transforms the search from finding the best path to finding a sufficiently good path within a known margin of error, which is often acceptable for real-time robotic systems where computational speed is critical.

A key algorithmic mechanism is Focal Search, which maintains two open lists. The OPEN list contains all generated nodes sorted by an admissible heuristic (e.g., f-cost = g + h). The FOCAL list is a subset of OPEN containing only nodes whose f-cost is within the bound (1+ε) of the best f-cost in OPEN. The search expands nodes from the FOCAL list, often prioritized by a secondary heuristic (e.g., number of conflicts). This structure ensures expansion stays within the suboptimality bound while allowing the use of a faster, more informed secondary heuristic to guide the search toward feasible solutions.

• Primary Heuristic (f): Guarantees bound adherence.
• Secondary Heuristic: Drives quick conflict resolution.

These algorithms explicitly manage the trade-off between computational speed and solution quality. By accepting a bounded cost increase, they avoid exploring the exponentially large number of states required for optimality proofs. The performance improvement is not linear; a small increase in ε (e.g., from 0 to 0.05) can lead to an order-of-magnitude reduction in search time and memory. This makes bounded suboptimal search indispensable for scalable real-time planning in warehouses with dozens or hundreds of agents, where a good solution now is more valuable than a perfect solution too late.

Bounded suboptimal techniques are integrated into leading MAPF frameworks:

• Enhanced Conflict-Based Search (ECBS): A bounded suboptimal variant of CBS. At the high level, it uses focal search to choose which constraint tree node to expand. At the low level, it uses focal search for individual agent path planning. This creates a double-focal search that efficiently finds bounded-suboptimal solutions for the entire fleet.
• Bounded Suboptimal M and A variants**: Adaptations of joint-space search algorithms that prune states outside the focal bound.
• These implementations allow planners to dynamically adjust ε based on available compute time or operational urgency.

Bounded suboptimal search is closely related to anytime algorithms. Many bounded suboptimal planners can operate in an anytime fashion: they quickly return an initial, potentially highly suboptimal solution (large ε) and then iteratively refine it, tightening the bound (reducing ε) as computation continues. This provides a graceful degradation under time pressure—a crucial feature for dynamic environments where replanning must complete within a strict control cycle. The initial bound acts as a performance guarantee from the very first solution.

For heterogeneous fleet orchestration, bounded suboptimal search enables deterministic latency guarantees for the planning subsystem. A system architect can set ε based on operational tolerance (e.g., a 5% longer travel time is acceptable) and know the worst-case planning time. This predictability is more valuable than unpredictable optimal solvers that may timeout. It directly supports:

• Real-Time Replanning Engines: Fast reaction to new orders or agent failures.
• Spatial-Temporal Scheduling: Incorporating the bound into overall makespan calculations.
• Priority-Based Routing: Ensuring high-priority agents get fast, good-enough paths without waiting for optimal plans for lower-priority agents.

A bounded suboptimal variant of A* that selectively expands nodes to reduce memory and computation. Instead of expanding all children of a node, it uses a focal search heuristic to expand only the most promising subset, guided by a suboptimality bound (w). This makes it highly effective for high-dimensional joint state spaces in MAPF.

• Core Mechanism: Operates with an open list and a focal list. The focal list contains nodes from the open list whose cost is within a factor w of the current best estimate.
• Provable Bound: Guarantees a solution cost no worse than w * C*, where C* is the optimal cost.
• Use Case: Ideal for centralized MAPF problems where optimal A* is intractable due to the exponential state space.

A bounded version of the optimal Conflict-Based Search (CBS) algorithm. It uses a focal search at both the high-level constraint tree and the low-level pathfinding to accelerate planning.

• Core Mechanism: The high-level search explores a tree of constraints. Instead of always choosing the node with the lowest sum of costs, w-CBS maintains a focal list of nodes whose cost is within a factor w of the best and selects one based on a secondary heuristic (e.g., number of conflicts).
• Provable Bound: Maintains the w-suboptimality guarantee of the final solution.
• Key Advantage: Can solve large, complex MAPF instances orders of magnitude faster than optimal CBS, making it practical for dynamic environments with dozens of agents.

The foundational bounded suboptimal search algorithm that directly enables techniques like EPEA* and w-CBS. Also known as A*_ε, it explicitly manages the trade-off between optimality and speed.

• Core Mechanism: Maintains two lists: the standard OPEN list sorted by f-cost (g+h), and a FOCAL list containing all nodes in OPEN with f-cost ≤ w * min_f, where min_f is the smallest f-cost in OPEN. The algorithm selects nodes from FOCAL using a secondary, computationally cheaper heuristic.
• Theoretical Guarantee: Any node selected from FOCAL leads to a solution with cost ≤ w * C*.
• Impact: This two-list architecture is the blueprint for most bounded suboptimal algorithms in MAPF and beyond.

A highly scalable, decentralized algorithm that uses bounded planning windows and cooperative reservation tables to find feasible paths quickly. It is inherently suboptimal but highly effective for lifelong MAPF (LMAPF).

• Core Mechanism: Plans paths for each agent independently using Space-Time A* but only for a short time window (e.g., 10-20 steps). Agents reserve their planned space-time cells in a shared reservation table. After executing the window, the process repeats.
• Suboptimality Source: The myopic window and potential livelock (cyclic conflicts) prevent optimality guarantees, but performance is robust in practice.
• Industrial Relevance: The foundational algorithm for many real-world autonomous warehouse and logistics systems due to its speed and simplicity.

A bounded suboptimal version of the optimal Multi-Agent A (MAA)** algorithm. It applies focal search principles directly to the exponentially large joint state space of all agents.

• Core Mechanism: Instead of always expanding the joint state with the lowest f-cost, it maintains a focal set of states whose cost is within w * best_f and selects one using a heuristic like the number of agents not yet at their goal.
• Challenge & Benefit: While still searching the joint state space, the focal heuristic dramatically prunes the search tree. It provides a weaker but valuable bound compared to decoupled methods like w-CBS, as it searches the true global state space.
• Use Case: Suitable for smaller fleets (5-10 agents) where a strong centralized bound is required, but optimal MAA* is too slow.

A meta-algorithm that decomposes a MAPF problem into smaller, independent groups. When combined with a bounded suboptimal solver (like w-CBS or EPEA*), it creates a powerful hierarchical bounded search.

• Core Mechanism: Initially treats all agents as independent and plans their paths separately. If paths conflict, the conflicting agents are merged into a joint group, which is then solved as a coupled subproblem using the bounded suboptimal solver. This process repeats.
• Scalability Impact: By limiting coupled search to small groups of interdependent agents, it avoids the exponential cost of searching the full joint state space.
• Provable Bound: The final solution's suboptimality bound is the product of the bounds used for solving the individual groups, maintaining a known worst-case performance limit.

Multi-Agent Path Finding is the foundational computational problem of planning collision-free paths for multiple agents from start to goal locations in a shared environment. It is the core problem that bounded suboptimal algorithms aim to solve efficiently.

• Centralized vs. Decoupled: Algorithms can plan in the full joint state space of all agents (centralized) or plan for agents sequentially/independently (decoupled).
• Objective Functions: Solutions are typically evaluated by Makespan (total completion time) or Sum of Costs (total travel distance/time).
• Completeness: A key property is whether an algorithm is guaranteed to find a solution if one exists, which is critical for real-world deployment.

Conflict-Based Search is a leading optimal algorithm for MAPF that uses a two-level search to resolve conflicts. It is often used as a benchmark against which bounded suboptimal algorithms are compared.

• High-Level Constraint Tree: CBS searches a tree where each node contains a set of constraints (e.g., "Agent A cannot be at vertex V at time T") and a solution that respects them.
• Low-Level Path Planner: For each agent, a single-agent path planner (like A*) finds the shortest path that obeys its current constraints.
• Bounded Suboptimal Variants: Algorithms like Enhanced CBS (ECBS) introduce focal search at both levels to find solutions within a suboptimality bound much faster than optimal CBS.

WHCA* is a classic bounded suboptimal MAPF algorithm designed for scalability in large, dense environments. It exemplifies the trade-off between optimality and computational speed.

• Planning Windows: Agents plan paths only for a short, fixed look-ahead window (e.g., 10 timesteps).
• Reservation Table: A shared data structure prevents collisions within the current window by reserving space-time cells.
• Replanning Cycle: At the end of its window, each agent replans from its new position, repeating the process until all goals are reached. This makes it an online algorithm suitable for dynamic changes.

Sum of Costs (also called Flowtime) is the primary cost metric for evaluating MAPF solutions, calculated as the sum of each agent's individual path cost (e.g., travel time). Bounded suboptimality is defined relative to this metric.

• Definition: SOC = Σ (finish_time_i - start_time_i) for all agents i.
• Optimality Bound: A bounded suboptimal algorithm with a suboptimality factor (w) guarantees that its solution's SOC is ≤ w * SOC_optimal.
• vs. Makespan: Unlike Makespan (time until the last agent finishes), SOC incentivizes efficiency for all agents, not just the slowest.

Focal Search (or A*ε) is the fundamental single-agent search algorithm that enables bounded suboptimal planning. It is the engine inside many bounded suboptimal MAPF algorithms like ECBS.

• Two Open Lists: Maintains a FOCAL list containing all nodes with an f-cost ≤ w * f_min, where f_min is the best cost in the standard OPEN list.
• Secondary Heuristic: Expands nodes from the FOCAL list based on a secondary heuristic (e.g., number of conflicts), dramatically speeding up search.
• Provable Bound: Guarantees a solution cost no worse than w times the optimal cost, where w ≥ 1 is the chosen suboptimality factor.

Priority Planning is a decoupled, often suboptimal approach where agents are assigned a static ordering. It represents a different scalability strategy compared to bounded suboptimal search in the joint space.

• Fixed Order: Agents plan sequentially according to a pre-assigned priority. Higher-priority agents plan first.
• Moving Obstacles: Lower-priority agents treat the paths of higher-priority agents as dynamic obstacles.
• Completeness Issues: Simple priority schemes can deadlock, but sophisticated methods like Priority Inheritance can recover completeness. It typically has no optimality bound unless combined with other techniques.