Lifelong Multi-Agent Path Finding

Enhanced Follower Framework for Lifelong Multi-Agent Path Finding: A Hierarchical Turn Penalty Approach

Yihan Zhang¹, Zhaokai Liu¹, Ling Yao¹, Jurong Chen², Lin Wang¹, Guanglin Zhang³

¹ School of Automation and Intelligent Sensing, Shanghai Jiao Tong University

² Technology R&D Department, Guangzhou Saite Intelligent Technology Co., Ltd.

³ Department of Communication Engineering, College of Information Science and Technology, Donghua University

45th Chinese Control Conference · CCC 2026

Explore the method View experimental results

The original framework diagram: Poisson task generation, POGEMA simulation, an A-star planner with a weak turn penalty, an RL policy with turn and stop penalties, and operational evaluation. — **Figure 1.** System architecture of the kinematics-aware LMAPF framework, including Poisson-distributed task sequence generation, POGEMA-based simulation, the hierarchical controller, and task-normalized operational evaluation.

Problem formulation

AGV-Inspired Time-Kinematic Model

The objective of LMAPF is to dynamically assign conflict-free paths to a fleet of automated guided vehicles (AGVs) as they continuously receive new goals.

Conventional LMAPF evaluations mainly count discrete steps and therefore treat straight moves, turns, and waiting as comparable unit actions. This abstraction misses a key physical effect in warehouse AGVs: changing direction requires deceleration, rotation, and re-acceleration. We therefore introduce a lightweight time-kinematic model as an evaluation-level surrogate.

We assume synchronized grid execution. At each simulator step, an AGV either moves to a four-neighboring cell or executes a stop action. A straight one-cell move consumes a base traversal time, a direction change adds a turn-induced delay, and a stop action occupies one control step.

Table I. Kinematic parameters and derived time costs.
Symbol	d_cell	v_max	a	t_rot	t_base	t_turn	t_stop
Value	1.0 m	2.0 m/s	0.6 m/s²	1.5 s	0.50 s	4.83 s	0.50 s

Evaluation Metrics

Throughput: Throughput measures the number of completed tasks per evaluation step.
Turns per Task (TPT): Turns per Task (TPT) measures the average number of executed turns per completed task.
Operational Time per Task (OTT): Operational Time per Task (OTT) measures the average cumulative robot-time required for each completed task after accounting for both physical motion and waiting.
Stop Ratio: Stop Ratio is the number of stop actions divided by the total number of executed actions.

Method

Hierarchical Turn Penalty Mechanism

Our framework is built upon the Follower architecture, a decentralized hybrid pipeline that synergizes global planning with local reactive control.

The Global Planner employs an A* algorithm to generate individual paths which are decomposed into sequences of waypoints for localized navigation. Within this hierarchy, multi-agent conflicts are resolved at the local level through reactive RL actions such as yielding or detouring.

Turn Penalty in the Planning Component

The original implementation penalizes nodes that are heavily occupied by other agents to avoid congestion. We extend this heuristic by modifying the edge cost function during the node expansion phase to mildly penalize tortuous routes.

The planner slightly biases the waypoint prior toward smoother paths without dominating the original congestion-aware cost.
Turn Penalty in the Learning Component

Unlike a blanket turn penalty, our local reward distinguishes efficient turns from inefficient turns. A turn that moves the agent closer to its current waypoint is treated as an efficient turn; otherwise, it is treated as an inefficient turn. A waiting-aware stop penalty increases with consecutive stop actions, up to a fixed cap.

The planning-level penalty shapes a smoother waypoint prior, while the RL-level reward decides whether to follow, wait, or detour under local conflicts. This loose coupling preserves local flexibility while still making the executed trajectory sensitive to the physical cost of turns.

Poisson-Distributed Task Sequence Generation

To emulate variable order-batch sizes in warehouse operations, we use a Poisson-distributed task sequence generator. This generator controls the number of targets assigned to each agent during an episode.

Targets are sampled from traversable cells adjacent to storage racks, which represent pick/replenishment access points. This creates localized task hotspots and variable task-list lengths while preserving a simple reproducible task-generation process.

Experiments

Experimental Setup

Experiments are conducted using POGEMA, a benchmark platform for cooperative multi-agent reinforcement learning (MARL) and MAPF.

We vary the fleet size N ∈ {32, 64, 128} over the three warehouse layouts in Fig. 3. Task sequences use K_i = max(1, X_i) with X_i ∼ Poisson(3). Each model is evaluated over five random seeds that vary task sampling and initial configurations.

Original Figure 3: the three benchmark warehouse grid layouts, labeled Map A, Map B, and Map C. — **Figure 3.** Illustration of the three benchmark grid layouts used in experiments.

Training Details and Throughput Stability

We kept the same neural network architecture and the same Proximal Policy Optimization (PPO)-style hyperparameters (via Sample Factory) across all four models to ensure a fair comparison.

Baseline: the original Follower-style configuration without planning or learning-level turn awareness (λ_P = 0, λ_R = 0, λ_S = 0).
Ablation-P: planning-only weak turn awareness, using λ_P = 0.01 and disabling the learning-level turn and stop terms (λ_R = 0, λ_S = 0).
Ablation-R: learning-only turn awareness, using λ_P = 0, λ_R = 0.02, α = 0.25, λ_S = 0.003, β = 0.002, and λ_S^max = 0.02.
Main: the full hierarchical design, combining Ablation-P and Ablation-R with λ_P = 0.01, λ_R = 0.02, α = 0.25, λ_S = 0.003, β = 0.002, and λ_S^max = 0.02.

Original Figure 2: average-throughput training curves for Baseline, Ablation-P, Ablation-R, and Main over environment steps. — **Figure 2.** Average-throughput training curves of the four LMAPF configurations over environment steps. The comparable convergence trends indicate that the turn-aware terms do not introduce observable training instability.

Experimental results

Main Performance Comparison

Averaged over the nine map-scale configurations, Main increases throughput by 7.0%, reduces TPT by 24.4%, and reduces OTT by 20.3%.

Original Figure 4: relative changes in throughput, Turns per Task, and Operational Time per Task for three maps and fleet sizes of 32, 64, and 128 agents. — **Figure 4.** Relative changes compared with the Baseline. Positive values indicate higher throughput; negative values indicate lower TPT and OTT.

Table II. Main performance comparison across different maps and densities. Results are averaged over five random seeds. Thr denotes Throughput. Higher Thr is better; lower TPT and OTT are better.
Map	N	Baseline			Ablation-P			Ablation-R			Main
Map	N	Thr	TPT	OTT	Thr	TPT	OTT	Thr	TPT	OTT	Thr	TPT	OTT
Map A	32	4.25	2.84	17.62	4.24	2.82	17.53	4.29	2.56	16.22	4.33	2.43	15.54
Map A	64	9.55	2.95	17.71	9.63	2.93	17.58	9.64	2.60	15.97	9.69	2.45	15.24
Map A	128	22.37	2.84	16.62	22.18	2.88	16.81	22.83	2.47	14.76	23.26	2.29	13.85
Map B	32	4.41	2.52	16.02	4.46	2.52	16.00	4.77	2.15	14.00	4.71	2.16	14.10
Map B	64	9.15	2.81	17.27	9.42	2.77	16.98	9.67	2.37	14.93	9.63	2.29	14.55
Map B	128	19.03	3.11	18.42	19.12	3.06	18.14	19.95	2.47	15.14	20.28	2.27	14.12
Map C	32	3.47	2.92	19.61	3.59	2.65	18.13	3.90	2.18	15.32	3.90	2.05	14.94
Map C	64	5.67	3.71	24.31	5.72	3.38	22.80	6.27	2.65	18.52	6.36	2.36	17.05
Map C	128	11.42	4.23	26.13	11.61	3.69	23.42	12.90	2.74	18.25	12.86	2.44	16.83

Result Analysis

The ablation results show that Ablation-P alone produces only small changes, whereas Ablation-R yields much larger TPT and OTT reductions. This indicates that many inefficient turns arise from local reactive decisions during waypoint following and collision avoidance.

Main consistently outperforms the Baseline, while Ablation-R occasionally achieves comparable or slightly higher throughput. Overall, Main provides the strongest balance between throughput, TPT reduction, and OTT reduction, showing that the global waypoint prior and local reward shaping are complementary.

Table III. Average Stop Ratio over all settings.
Configuration	Baseline	Ablation-P	Ablation-R	Main
Stop Ratio	8.08%	9.35%	10.53%	12.82%

Conclusion

Conclusion and Future Work

We further proposed a Hierarchical Turn Penalty Mechanism: the planning layer injects a weak directional cost into A*, while the learning layer uses an efficient/inefficient turn-aware reward and a waiting-aware stop penalty. Experiments show that Main improves throughput over the Baseline and consistently reduces both TPT and OTT.

We also plan to calibrate the lightweight time-cost model with higher-fidelity robot simulations and physical AGV logs, especially for stop-and-go behavior, acceleration profiles, and continuous turning dynamics. Finally, extending this framework from discrete grid representations to continuous state and action spaces will further enhance its applicability to non-holonomic robotic systems in physical fulfillment centers.