Sum of Costs (SOC)

Sum of Costs (SOC) is calculated as the sum of the individual path lengths (or travel times) for all agents from their start locations to their goal locations. Formally, for N agents, SOC = Σ (cost_i), where cost_i is the number of time steps (or distance) agent i takes to reach its goal. It is mathematically equivalent to the Flowtime metric. A lower SOC indicates a more efficient overall plan that minimizes total fleet travel.

In optimal MAPF, the objective is to find a collision-free solution that minimizes the SOC. Algorithms like Conflict-Based Search (CBS) and Multi-Agent A (MAA)** are designed to produce SOC-optimal plans. This differs from minimizing Makespan (the time until the last agent finishes). A solution optimal for SOC prioritizes getting many agents to their goals quickly, even if the last agent is delayed, whereas a Makespan-optimal solution focuses on the overall completion time.

Optimizing for SOC often involves trade-offs with other system qualities:

• vs. Makespan: A low SOC can sometimes result in a higher Makespan, as agents may take longer, indirect routes to avoid blocking others.
• vs. Computational Cost: Finding the provably optimal SOC is computationally hard (NP-hard). Bounded-suboptimal algorithms (e.g., Enhanced CBS) are often used to find good solutions faster with a small cost bound.
• vs. Robustness: A minimal SOC plan may have agents moving in tight sequence, leaving little margin for error. k-Robust Planning adds temporal buffers, which can increase SOC but improve execution reliability.

MAPF algorithms use SOC as a guiding heuristic and evaluation function:

• In CBS, the high-level search tree is sorted by the SOC of the current solution, always expanding the node with the lowest total cost.
• Increasing Cost Tree Search (ICTS) explicitly searches a tree of possible cost combinations for all agents, where the root's cost vector sums to a lower bound for SOC.
• Multi-Value Decision Diagrams (MDDs) compactly represent all optimal paths for a single agent within a given cost bound, which are then combined and checked for conflicts while tracking SOC.

For real-world heterogeneous fleet orchestration, minimizing SOC directly translates to business efficiency:

• Reduced Energy Consumption: Shorter total travel distance means lower battery/fuel usage for Autonomous Mobile Robots (AMRs) and vehicles.
• Higher Throughput: Agents complete tasks faster on average, increasing the total number of tasks (e.g., picks, deliveries) completed per hour.
• Warehousing & Logistics: In a fulfillment center, a lower SOC for a fleet of robots means less time spent traveling empty and more time spent at workstations, optimizing Spatial-Temporal Scheduling.

Understanding SOC requires context from other key MAPF metrics:

• Makespan: The total time until the last agent finishes. Critical for time-sensitive, batch-oriented operations.
• Flowtime: Synonym for SOC.
• Service Time: Often used in Lifelong MAPF (LMAPF), focusing on the time between task assignment and completion.
• Success Rate: The percentage of agents that reach their goal, a prerequisite for calculating SOC.
• Plan Length: For a single agent, this is its individual contribution to the SOC.

Makespan is the total elapsed time from the start of execution until the last agent in the fleet reaches its goal. It is a critical metric for throughput in time-sensitive operations.

• Key Difference from SOC: While SOC sums individual completion times, Makespan measures the overall mission duration. Optimizing for one does not necessarily optimize the other.
• Use Case: In a warehouse packing station, minimizing Makespan ensures the entire batch of orders is completed as quickly as possible, even if some individual robots take longer routes.

Flowtime is a performance metric mathematically equivalent to the Sum of Costs (SOC). It represents the sum of the finish times for all agents.

• Synonym for SOC: In academic literature, 'Flowtime' and 'SOC' are often used interchangeably to denote the same cumulative cost function.
• Operational Focus: Minimizing Flowtime/SOC reduces the total idle time of agents waiting for the mission to complete, optimizing overall fleet utilization and energy consumption.

Conflict-Based Search (CBS) is a two-level, optimal algorithm for MAPF designed to minimize SOC. It works by:

• High-Level Constraint Tree: Resolving conflicts (e.g., vertex, edge) by imposing constraints on individual agents.
• Low-Level Path Planning: Re-planning paths for constrained agents using a single-agent solver like A*.
• Optimality Guarantee: CBS systematically explores constraint combinations, guaranteeing an optimal solution that minimizes the global Sum of Costs.

Increasing Cost Tree Search (ICTS) is an optimal MAPF algorithm that directly searches for a solution minimizing SOC.

• Mechanism: It searches a tree where each node represents a unique combination of cost budgets for all agents. The root node has the minimum possible sum (SOC).
• Efficiency: For each budget combination, ICTS uses Multi-Value Decision Diagrams (MDDs) to check if feasible, collision-free paths exist for each agent within their individual budget.
• Outcome: It finds the minimal SOC by incrementally increasing the global cost budget until a valid solution is found.

Bounded Suboptimal Search refers to MAPF algorithms that sacrifice optimality for speed, with a provable bound on solution cost.

• Trade-off: These algorithms (e.g., Enhanced CBS, EECBS) find solutions where the SOC is guaranteed to be no worse than w * SOC_optimal, where w >= 1 is a suboptimality factor.
• Practical Application: In large-scale logistics with hundreds of robots, a solution with a 10% higher SOC found in seconds is often preferable to an optimal solution that takes minutes or hours to compute.

k-Robust Planning is a strategy that enforces a temporal buffer of at least k timesteps between agents at any location.

• Impact on SOC: Adding robustness (k > 0) inherently increases the planned SOC, as agents must wait longer to avoid potential conflicts.
• Purpose: It provides a safety margin against execution delays, sensor noise, and timing uncertainties in physical systems, making the plan executable in the real world.
• Engineering Decision: Selecting k involves a direct trade-off between solution robustness (safety) and optimality (minimized SOC).