💻 computer science

From Edge to Edge: A Flow-Inspired Scheduling Planner for Multi-Robot Systems

This paper presents a real-time, flow-inspired scheduling planner that coordinates multi-robot systems to efficiently traverse obstacle-rich environments from edge to edge by decomposing the space into a network flow structure, balancing detours and waiting times to minimize overall traversal time, with effectiveness validated through both simulations and real-world drone flight tests.

Original authors: Han Liu, Yu Jin, Mingyue Cui, Boyang Li, Tianjiang Hu, Kai Huang

Published 2026-02-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Han Liu, Yu Jin, Mingyue Cui, Boyang Li, Tianjiang Hu, Kai Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to get a large group of people to walk from one side of a crowded, obstacle-filled room to the other. If everyone just tries to walk in a straight line to their specific destination, they will likely bump into each other, get stuck in traffic jams, and the whole group will take a long time to cross.

This paper presents a new "traffic controller" for robots that solves this problem by thinking like water flowing through a pipe system.

The Problem: The "Straight Line" Trap

Most current robot planners work like a GPS for a single car. They tell each robot, "Go straight to your goal."

The Issue: When you have 100 robots doing this, they all try to squeeze through the same narrow gaps at the same time. It's like 100 people all trying to walk through a single doorway simultaneously. They end up waiting, dodging, and slowing each other down.
The Old Way: Traditional methods either ignore the other robots (causing chaos) or try to calculate the perfect path for everyone at once (which takes too long to compute).

The Solution: The "Water Flow" Planner

The authors propose a system inspired by network flow, a concept used to move water or data through pipes as efficiently as possible. Instead of treating robots as individuals, they treat the whole group like a fluid.

Here is how their system works, broken down into three simple steps:

1. Mapping the "Riverbed" (Network Construction)
First, the system looks at the map and breaks it down. Instead of seeing a complex grid of squares, it identifies "channels" or "pipes" where robots can move.

The Analogy: Imagine a river with rocks. The system doesn't just look at the water; it identifies the specific channels where the water can flow fastest and how wide those channels are. It creates a simplified map of "highways" and "bottlenecks."

2. Choosing the Best Route (Path Selection)
When a robot needs to move, the system doesn't just pick the shortest path. It looks at the "traffic" in the channels.

The Analogy: Think of a highway app that tells you to take a slightly longer route because the main highway is jammed. The system asks: "If I send this robot down the shortest path, will it get stuck in a crowd? If so, let's send it down a slightly longer, emptier path."
It balances two things: Distance (how far to go) and Congestion (how many other robots are there). It uses math to ensure that if one path gets too crowded, the next robot is automatically sent down a different, less crowded path.

3. Picking the Exact Spot (Position Allocation)
Once the path is chosen, the system decides exactly where on that path the robot should enter.

The Analogy: Imagine a line of people waiting to enter a theater. If everyone tries to squeeze through the same door at the same time, it's a mess. This step ensures that if 10 people are entering a hallway, they are spaced out evenly, like beads on a string, rather than clumping together.

Why It's Better

The researchers tested this with simulations of up to 500 robots and real-world tests with 10 drones flying through a room full of boxes.

Speed: The "Water Flow" system got all the robots across the room faster than any other method they tested.
Less Waiting: Because the system spreads the robots out like water in a river, fewer robots had to stop and wait for others to move.
Real-Time: The computer could make these decisions incredibly fast (in less than a second), even with hundreds of robots. This means it can react to changes instantly, unlike older methods that take too long to calculate.

The Bottom Line

This paper introduces a smart scheduling planner that helps groups of robots move from one side of a messy environment to the other without crashing or getting stuck. By treating the group like a flowing liquid rather than a crowd of individuals, it keeps the "traffic" moving smoothly, ensuring the whole group arrives faster and safer.

Note: The paper specifically focuses on scenarios where robots move from one side of an environment to the opposite side (like crossing a street or a warehouse), similar to water flowing from a source to a drain.

Technical Summary: From Edge to Edge: A Flow-Inspired Scheduling Planner for Multi-Robot Systems

Problem Statement

The paper addresses the challenge of coordinating a large number of robots to traverse an obstacle-rich environment from one side (source) to the opposite side (sink). While traditional multi-robot path planning often focuses on point-to-point navigation or static Multi-Agent Path Finding (MAPF), these methods frequently struggle with high robot density, leading to congestion, deadlocks, and inefficient traversal times. Existing front-end planners often rely on simple point-to-point connections or grid-based MAPF algorithms (like A* or CBS variants) that either ignore inter-robot interactions or produce rigid paths unsuitable for dynamic, real-time execution. Furthermore, many flow-based optimization methods are computationally intensive, designed for offline use, and lack the ability to generate executable trajectories for individual robots in real-time.

The core objective is to minimize the makespan (the time at which the last robot reaches its destination) by balancing path length, detours, and waiting times, specifically in scenarios where robots must flow collectively across a congested space.

Methodology

The authors propose a Flow-Inspired Scheduling Planner that operates as a front-end module, compatible with existing back-end collision avoidance algorithms (specifically ORCA). The framework consists of three main stages:

1. Network Construction

To bridge the gap between grid maps and flow networks, the authors decompose the environment into two complementary representations:

Adjacency Network: Using Boustrophedon Cellular Decomposition, the map is divided into cells. Boundaries between cells are sampled to create "Pos" (positions), which are grouped into "Nodes." Edges connect nodes between adjacent cells, forming a graph $G=\{V, L\}$ that represents potential movement paths.
Congestion Map: The environment is further partitioned into uniform sub-regions to estimate capacity. The capacity of each region is calculated based on its area and the robot safety radius, accounting for a redundancy factor to prevent overestimation. This separation allows for precise modeling of shared spatial constraints without double-counting capacity.

2. Flow Planner Components

The planner executes three sequential modules in real-time:

Path Set Search: Instead of enumerating all possible paths (which is computationally prohibitive), the algorithm identifies a promising subset of candidate paths. It identifies boundary nodes near the robot's current position and the target goal, then uses Dijkstra's algorithm to find paths connecting these specific entry and exit points. This "start-to-exit, entrance-to-destination" strategy reduces search space while maintaining decision quality.
Path Node Selection: The system formulates path selection as a Mixed-Integer Programming (MIP) problem. It evaluates candidate paths based on two costs:
- Queuing Cost ( $f_{Que}$ ): Predicts future congestion by analyzing the initial segments of paths against the congestion map. It penalizes paths that lead to regions where the number of robots exceeds capacity, using a squared overload term to strongly discourage congestion.
- Run Cost ( $f_{run}$ ): Penalizes excessive path length.
  The optimizer selects a set of paths for all robots that minimizes the sum of these costs, effectively balancing detours against waiting times.
Position Allocation: Once a sequence of nodes is selected, the planner assigns specific "Pos" coordinates to each node. A heuristic greedy algorithm is used: for the first node, it balances Euclidean distance against current position occupancy to prevent clustering; for subsequent nodes, it selects the closest available position to the previous one to ensure smooth transitions.

3. Execution

The generated discrete paths are passed to a back-end controller (using ORCA for collision avoidance) which executes the trajectory while ensuring safety. The planner runs periodically (e.g., every 2 seconds in simulation) to adapt to dynamic changes.

Key Contributions

Flow-Inspired Scheduling: A novel front-end planner that decomposes the environment into a flow-based network structure, enabling real-time allocation of robots to paths based on congestion levels.
Real-Time Efficiency: The method achieves high computational efficiency, supporting online operation for large-scale systems (up to 500 robots) by avoiding exhaustive search and utilizing a sparse network abstraction.
Congestion-Aware Optimization: The planner explicitly models regional capacity and predicts future congestion, allowing it to balance detours and waiting times to minimize the overall makespan.
Validation: The framework is validated through extensive simulations across various map types (forest, maze, clutter, corridor) and robot densities (10–500 robots), as well as real-world flight tests with ten drones.

Experimental Results

Small-Scale (10–100 Robots): The proposed "Flow" method consistently outperformed baselines including A*, ECBS, P-SIPP, and TVMA in terms of makespan. It showed particular advantage as robot density increased, reducing makespan by approximately 5–9% compared to the best MAPF baselines.
Large-Scale (100–500 Robots): In large-scale scenarios, the Flow method significantly outperformed state-of-the-art MAPF algorithms (CBSH2-RTC, LNS2) and congestion-aware methods (CMPP). It achieved makespan improvements of 4–15% over baselines. Notably, while LNS2 reduced congestion, it often resulted in excessive detours; the Flow method better balanced congestion avoidance with path length.
Computation Time: The Flow planner demonstrated superior scalability. For 500 robots, the average planning time was under 1 second (approx. 0.9s), whereas offline MAPF methods often required significantly longer or failed to scale.
Real-World Tests: Flight tests with 10 DJI Tello drones in a confined, obstacle-rich environment confirmed the method's practical feasibility. The system successfully navigated all drones from one side to the other without collisions or deadlocks.
Density Analysis: The Flow algorithm maintained lower peak robot densities and fewer robots in a "waiting state" compared to other methods, indicating more efficient utilization of the available space.

Significance and Claims

The paper claims that this work contributes a real-time, flow-inspired scheduling planner tailored for directional multi-robot traversal in complex environments. Its significance lies in addressing the specific gap of coordinating large swarms to move collectively across an environment (edge-to-edge), a scenario common in warehouse logistics and urban delivery but often overlooked by standard point-to-point planners.

The authors emphasize that their method does not replace back-end collision avoidance but rather enhances the front-end planning stage. By leveraging network flow principles to manage congestion proactively, the system achieves smoother, faster collective traversal. The paper modestly notes that the current approach is optimized for unidirectional flows (source to sink) and that extending the framework to support omnidirectional or multi-directional flows remains a direction for future research.