Flowtime

Flowtime is defined as the sum of the finish times for all agents in a Multi-Agent Path Finding (MAPF) solution. For an agent (a_i) with a path cost (or travel time) of (c_i), the Flowtime (F) is calculated as:

[ F = \sum_{i=1}^{k} c_i ]

where (k) is the total number of agents. This makes it mathematically identical to the Sum of Costs (SOC) metric. It measures the cumulative 'waiting time' of the system, where each agent's clock starts at time zero and stops when it reaches its goal.

Flowtime and Makespan are the two fundamental MAPF performance metrics, each serving a different optimization goal.

• Flowtime (SOC): Sum of individual agent completion times. Optimizes for total system throughput and aggregate efficiency. Reducing Flowtime often means getting as many agents to their goals as quickly as possible on average.
• Makespan: The time when the last agent finishes. Optimizes for completion time of the overall mission. A solution can have a low Makespan but a high Flowtime if some agents are delayed so that others can finish quickly.

Engineers choose the metric based on the operational objective: minimizing total work (Flowtime) versus minimizing mission duration (Makespan).

Optimizing for minimal Flowtime directly influences algorithm design and search strategy in MAPF solvers.

• Cost Structure: Algorithms like Conflict-Based Search (CBS) and Multi-Agent A (MAA)** use Flowtime as the primary cost function to minimize during the search in the joint state space.
• Conflict Resolution: When resolving a vertex conflict or edge conflict, the algorithm evaluates which constraint (e.g., forcing agent A to wait vs. agent B) results in the lower overall increase to the total Flowtime.
• Bounded Suboptimality: Some scalable algorithms accept a bounded suboptimal solution (e.g., Flowtime ≤ 1.2 * optimal) to find feasible plans much faster, which is critical for Lifelong MAPF (LMAPF) applications.

In real-world heterogeneous fleet orchestration, a low Flowtime translates to tangible business and operational benefits.

• Total System Delay: Represents the sum of all time agents spend in transit or waiting. Lower Flowtime means less aggregate delay.
• Resource Utilization: Directly correlates with the total productive work done by the fleet. Minimizing Flowtime maximizes the throughput of tasks (e.g., items picked, distance traveled) per unit time.
• Battery & Energy Consumption: In battery-aware scheduling, a lower Flowtime often implies less total distance traveled by the fleet, leading to reduced aggregate energy consumption and more efficient charging cycles.

Flowtime interacts with several other key concepts in multi-agent coordination and performance analysis.

• Sum of Costs (SOC): The direct synonym for Flowtime.
• k-Robust Planning: A strategy that enforces temporal separation between agents to create execution buffers. Increasing robustness (k) typically increases the solution's Flowtime, trading off efficiency for reliability.
• Multi-Value Decision Diagram (MDD): A compact structure encoding all optimal paths for a single agent within a given cost bound. MDDs are used in algorithms like Increasing Cost Tree Search (ICTS) to efficiently explore combinations of agent costs that meet a target Flowtime.
• Load Balancing: In dynamic task allocation, a balanced workload distribution across agents generally contributes to a lower overall Flowtime.

Consider a warehouse where 10 autonomous mobile robots (AMRs) must retrieve items from shelves and deliver them to packing stations.

• Scenario: Each robot is assigned a unique retrieval task. The orchestration middleware runs a MAPF solver to plan collision-free paths.
• Flowtime Calculation: If the planned paths result in completion times of [30s, 45s, 50s, 25s, 60s, 35s, 40s, 55s, 20s, 30s] for the 10 robots, the Flowtime is 390 seconds.
• Optimization Goal: The operations manager wants to minimize the total time robots spend driving (to reduce wear and energy use) and maximize the number of tasks completed per hour. The planning engine continuously re-optimizes for minimal Flowtime as new tasks arrive (real-time replanning), directly improving the site's key performance indicators (KPIs) like orders per hour.

Sum of Costs (SOC) is the foundational performance metric in Multi-Agent Path Finding, defined as the sum of the path costs (typically travel time or number of steps) for all individual agents from their start to their goal. Flowtime is mathematically equivalent to SOC. It is the primary objective for optimal MAPF algorithms like Conflict-Based Search (CBS) and Multi-Agent A* (MAA*), which aim to minimize the total system effort.

Makespan is a critical alternative performance metric in MAPF, defined as the total time elapsed from the start of execution until the last agent reaches its goal. Unlike Flowtime (SOC), which sums all agents' times, Makespan focuses on minimizing the overall completion time of the longest task. This metric is paramount in production scheduling and warehouse throughput scenarios where finishing the entire batch of jobs quickly is the priority.

• Key Difference: Minimizing Makespan can lead to different optimal paths than minimizing Flowtime.

Conflict-Based Search (CBS) is a leading optimal algorithm for solving MAPF problems, explicitly designed to minimize the Sum of Costs (Flowtime). 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 that respects them.
• Low-level: Performs a single-agent path search (e.g., A* or Space-Time A*) for each agent, incorporating the current constraints. When a vertex conflict or edge conflict is found, CBS branches by adding constraints to resolve it, guaranteeing an optimal solution.

Multi-Agent A (MAA)** is a centralized, optimal search algorithm that plans directly in the joint state space of all agents. Each state in the search graph represents the combined locations of all agents at a given time. It applies the classic A* algorithm to this exponentially large space, using a heuristic to estimate the remaining total cost (Flowtime). While guaranteed to find the optimal solution, its complexity grows exponentially with the number of agents, making it suitable only for small fleets or as a subroutine in more scalable algorithms like CBS.

A Cardinal Conflict is the most severe type of conflict in MAPF algorithms like CBS. It occurs between two agents where any feasible resolution inevitably increases the Sum of Costs (Flowtime). For example, if two agents must cross a narrow corridor in opposite directions, one must wait, adding a cost of at least one time step to the system total. Identifying cardinal conflicts allows algorithms to prioritize their resolution, as they represent a hard lower bound on cost increase and are essential for proving optimality.

Bounded Suboptimal Search refers to a class of MAPF algorithms that sacrifice guaranteed optimality for dramatically improved speed and scalability. These algorithms, such as Enhanced CBS (ECBS), find solutions with a cost (Flowtime) that is provably no worse than w * optimal_cost, where w > 1 is a user-defined suboptimality bound (e.g., 1.5). This approach is essential for real-world heterogeneous fleet orchestration, where finding a good-enough plan quickly is more valuable than waiting for a perfect one.