Makespan

Makespan is defined as the total elapsed time from the start of plan execution until the last agent in the fleet reaches its designated goal. It is calculated as max_i(finish_time_i) - start_time, where finish_time_i is the time agent i completes its path. This metric focuses on overall mission completion time rather than individual agent efficiency.

Makespan is often contrasted with Sum of Costs (SOC), another primary MAPF metric. Key differences:

• Makespan: Measures the wall-clock time for the entire operation. Optimizing for makespan minimizes the time the workspace is occupied.
• SOC: Sums the individual path costs (e.g., travel time) for all agents. Optimizing for SOC minimizes total fleet effort or energy consumption. A plan with a low SOC can have a high makespan if one agent is significantly delayed, and vice-versa.

Finding a plan that minimizes makespan is a primary NP-hard optimization objective in MAPF. The challenge stems from the exponential growth of the joint search space as the number of agents increases. Optimal algorithms like MAA* and CBS can minimize makespan but face severe scalability limits. In practice, bounded-suboptimal or windowed algorithms (e.g., WHCA*) are often used to find feasible, low-makespan plans for large fleets in real-time.

Makespan is directly determined by system bottlenecks. A single congested corridor, a shared resource, or a slow-moving agent can become the critical path that dictates the final finish time. Analysis involves:

• Identifying vertex and edge conflicts that cause cascading delays.
• Applying k-robust planning to add temporal buffers, increasing makespan but improving execution robustness.
• Using priority-based planning to sequence agents through choke points efficiently.

In Lifelong MAPF, where agents continuously execute new tasks, minimizing the makespan of each planning iteration is crucial for maintaining high system throughput. A low makespan per batch means agents become available for new assignments more quickly. This requires tight integration with dynamic task allocation and real-time replanning engines to avoid idle time and reduce the finish time of the slowest agent in each cycle.

In operational systems, makespan is a key Service Level Agreement (SLA) metric. Example measurements:

• Warehousing: Time to complete all pick-and-place orders in a wave.
• Autonomous Valet Parking: Time until the last car is parked.
• Robotic Assembly: Cycle time for a complete product assembly. It is monitored via fleet state estimation systems and used to validate the performance of spatial-temporal scheduling algorithms against business requirements for operational tempo.

Minimizing makespan is paramount in automated storage and retrieval systems (AS/RS) and goods-to-person fulfillment centers. A shorter makespan directly translates to higher system throughput, allowing more orders to be processed per hour. For example, in a multi-robot mobile fulfillment system, optimizing for makespan ensures the last item for a batch of orders reaches the packing station as quickly as possible, reducing the order cycle time and increasing the total number of batches completed per shift.

In assembly line kitting and flexible manufacturing systems, multiple autonomous mobile robots (AMRs) deliver components to workstations. A minimized makespan ensures all necessary parts for a production step arrive simultaneously, preventing bottlenecks. This synchronization is critical for just-in-time (JIT) processes, where idle time at a workstation waiting for a single delayed component can halt an entire production line, incurring significant costs.

Makespan and Sum of Costs (SOC) are two primary optimization objectives in MAPF, often in conflict.

• Makespan Focus: Minimizes the completion time of the slowest agent. This may force some agents to take longer, costlier paths to clear space for others, increasing the total SOC.
• SOC Focus: Minimizes the total travel time/distance of all agents. This can lead to a longer tail where one agent is significantly delayed, increasing the makespan. System designers must choose the objective that aligns with business goals: maximizing throughput (makespan) versus minimizing total fleet energy/ware (SOC).

In a heterogeneous fleet containing both fast AMRs and slower manual vehicles or forklifts, makespan optimization becomes more complex. The planner must account for differing:

• Maximum velocities
• Acceleration/deceleration profiles
• Physical dimensions and turning radii A naive makespan-minimizing plan might over-utilize fast robots while leaving slower assets idle, which is inefficient. Advanced schedulers use battery-aware and capability-aware scheduling to balance the load while still targeting an optimal overall completion time.

A theoretically optimal makespan plan is often brittle, assuming perfect timing and execution. In real-world environments with timing uncertainties, communication delays, and minor mechanical variations, such a plan can easily fail, causing deadlocks. To ensure execution robustness, strategies like k-robust planning are employed. This enforces a minimum temporal buffer (k time steps) between agents at any location, sacrificing a marginally longer makespan for a plan that is far more likely to succeed despite real-world perturbations.

In Lifelong MAPF (LMAPF), where agents continuously receive new tasks, a pure makespan objective for a single episode is insufficient. The focus shifts to minimizing the average makespan over time or minimizing the makespan of the current task batch. Online replanning engines must dynamically adjust paths for new tasks while considering the impact on the ongoing makespan of the active batch. This requires efficient conflict detection and resolution and often the use of windowed planning techniques (e.g., WHCA*) to maintain scalability.

Sum of Costs (SOC), also known as Flowtime, is a fundamental MAPF performance metric. It is calculated as the sum of the individual path costs (typically travel time or distance) for all agents from their start to their goal.

• Primary Use: Measures the total fleet effort or cumulative delay. Minimizing SOC prioritizes overall system efficiency.
• Contrast with Makespan: While Makespan focuses on the completion time of the slowest agent (minimizing the longest individual path), SOC focuses on the aggregate of all agent paths (minimizing the total path length).
• Example: In a warehouse, a low SOC indicates efficient total robot travel distance, reducing aggregate wear and energy consumption.

Flowtime is a performance metric synonymous with Sum of Costs (SOC). It represents the sum of the finish times for all agents in a Multi-Agent Path Finding (MAPF) solution.

• Definition: If agent i finishes at time t_i, Flowtime = Σ t_i for all agents.
• Operational Meaning: In logistics, minimizing flowtime is analogous to minimizing the total inventory holding time or the total waiting time of tasks in a system.
• Key Insight: Algorithms optimizing for Makespan (the maximum t_i) and Flowtime can produce different solution characteristics. A schedule with excellent Makespan might have poor Flowtime if many agents are forced to take long detours.

k-Robustness is a robustness metric for MAPF plans that enforces a temporal buffer between agents. A plan is k-robust if, for any space-time conflict, agents are separated by at least k time steps.

• Mechanism: This is achieved by treating each space-time cell as reserved for k+1 timesteps around an agent's planned occupancy.
• Purpose: Provides a safety margin to absorb real-world execution delays, controller latency, and minor localization errors without causing collisions.
• Trade-off with Makespan: Enforcing high k-robustness (e.g., k=2 or 3) typically increases the Makespan, as agents must wait longer to avoid occupying buffers. It is a direct trade-off between solution robustness and temporal efficiency.

Bounded Suboptimality refers to a guarantee on solution quality where an algorithm finds a solution with a cost no worse than w times the optimal cost, where w ≥ 1 is a suboptimality bound.

• Relation to Metrics: This bound can apply to either Makespan or Sum of Costs. An algorithm may guarantee a Makespan ≤ w * (Optimal Makespan).
• Engineering Rationale: Optimal MAPF solvers (like CBS, MAA*) are computationally expensive. Bounded suboptimal algorithms (like Enhanced CBS (ECBS)) sacrifice guaranteed optimality for drastically improved solve times, making them practical for large, real-time fleets.
• Example: With w = 1.5, the algorithm promises a solution whose Makespan is at most 50% longer than the theoretical best, often found orders of magnitude faster.

Throughput is a system-level performance metric measuring the number of tasks completed by the agent fleet per unit of time. While Makespan measures the duration of a single batch of tasks, throughput measures sustained operational capacity.

• Context: Throughput is the critical metric for Lifelong MAPF (LMAPF) systems, where agents are continuously assigned new goals.
• Calculation: Throughput = (Number of Tasks Completed) / (Total Operational Time).
• Interaction with Makespan: For a single batch, a lower Makespan directly enables a higher potential throughput for that batch. In continuous operation, system design focuses on maximizing steady-state throughput, which involves optimizing Makespan for each planning window and minimizing agent idle time.

Solution Cost is the generic term for the objective function being minimized in a MAPF problem. Makespan and Sum of Costs are the two most common specific definitions of solution cost.

• Algorithmic Dependency: The choice of cost function fundamentally changes the search problem. Conflict-Based Search (CBS) and Multi-Agent A (MAA)** can be configured to optimize for either.
• Other Cost Functions: Less common variants include:
  • Maximize the minimum distance to obstacles (safety).
  • Minimize energy consumption.
  • Minimize cumulative risk.
• Practical Selection: In time-critical operations (e.g., emergency evacuation), Makespan is paramount. In cost-sensitive operations (e.g., parcel delivery), Sum of Costs (minimizing total fuel) is often preferred.