Bi-Layer Ant Colony Optimization for Multi-Robot Task Allocation and Routing in Delivery Applications

Le Na Nguyen; Thanh Long Nguyen; Thanh Thao Ton Nu; Quan Le; Manh Duong Phung

cs.ROAug 18, 2026

Bi-Layer Ant Colony Optimization for Multi-Robot Task Allocation and Routing in Delivery Applications

Authors: Le Na Nguyen, Thanh Long Nguyen, Thanh Thao Ton Nu, Quan Le, Manh Duong Phung

Organizations: Fulbright University Vietnam Ho Chi Minh City, Vietnam · College of Engineering and Computer Science, VinUniversity Hanoi, Vietnam

Abstract

This paper addresses the multi-robot task allocation (MRTA) problem, which is essential for delivery and logistics applications. Our approach first defines a new cost function that transforms the MRTA into a unified optimization problem capturing both task assignment and routing. A bi-layer ant colony optimization (ACO) algorithm is then introduced, integrating two interdependent decision layers within a single colony process to solve the problem. This hierarchical framework enables simultaneous optimization of task allocation and route planning across multiple robots. Comparative experiments with mixed-integer linear programming (MILP) and particle swarm optimization (PSO) demonstrate that the proposed bi-layer ACO achieves the shortest total travel distance and fastest completion time across all task sizes. Specifically, it reduces total travel distance by up to 17.7% and completion time by nearly 20% compared with baseline methods. These results confirm the efficiency, scalability, and reliability of the proposed bi-layer ACO for multi-robot delivery tasks.

Figures & tables

Panel of Figure 1 — Figure 1. Simulation environment and robot setup.

Tasks	Algorithm	Distance (m)	Time (s)
5	ACO	$\textbf{20.00}\pm\textbf{3.43}$	$\textbf{132.95}\pm\textbf{20.53}$
	PSO	$22.17\pm 3.37$	$138.66\pm 19.37$
	MILP	$24.30\pm 2.69$	$166.88\pm 36.04$
10	ACO	$\textbf{41.10}\pm\textbf{8.10}$	$\textbf{287.62}\pm\textbf{38.78}$
	PSO	$43.19\pm 8.24$	$300.85\pm 21.29$
	MILP	$44.19\pm 8.24$	$319.43\pm 74.03$

Table 1. Comparison results (mean ± std) for total distance and total time.

Panel of Figure 2 — Figure 2. Total travel distance distributions for ACO, PSO, and MILP across different task sizes.

Multi-Robot Task Allocation

Multi-robot task allocation assigns work across robot teams while balancing capabilities, costs, timing, and coordination constraints.

See all 112 papers

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
May 15, 2026Ning Zhou, Nikolai W. F. Bode, Edmund R. HuntMulti-Agent System Optimization Multi-Robot Coordination
University of Bristol
ARMATA: Auto-Regressive Multi-Agent Task Assignment
May 5, 2026Yazan Youssef, Aboelmagd Noureldin, Sidney GivigiMulti-Agent System Optimization Multi-Robot Task Allocation
Department of Electrical and Computer Engineering, Queen’s University, Kingston, ON, Canada · Department of Electrical and Computer Engineering at the Royal Military College of Canada, and the Department of Electrical and Computer Engineering at Queen’s University, both in Kingston, Canada · School of Computing, Queen’s University, Kingston, ON, Canada
Decentralized Multi-Robot Task Allocation Under Degraded Communication: A Benchmark of Performance, Reliability, and Computation
Sep 12, 2026James Lott, Vahraz HonaryMulti-Robot Task Allocation
Department of Electrical Engineering, University of San Diego, San Diego, CA 92110 USA

May 15, 2026J/K move · Enter open · S save

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

Ning Zhou, Nikolai W. F. Bode, Edmund R. Hunt

University of Bristol

Multi-Agent System Optimization Multi-Robot Coordination Conflict-Based Search Multi-Robot Task Allocation Multi-Agent Path Finding Multi-Robot Cargo Transportation

Open paper AskPDF arXiv

Multi-robot systems are integral to modern logistics, but their capabilities are often limited to tasks executable by individual agents. This paper addresses a critical gap in existing frameworks like Multi-Agent Path Finding (MAPF) and Task Allocation and Path Finding (TAPF), which lack true cooperation for transporting large items that require multiple agents. To this end, we formalise the Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) problem, which integrates team formation, task assignment, and collision-free pathfinding. We present an optimal solver, Cooperative Transportation Task Conflict-Based Search (CT-TCBS), which features a novel Incremental Expansion strategy to tackle the combinatorial explosion inherent in team formation. Recognising the computational cost of optimality, we also develop a family of sub-optimal solvers that employ a global, task-centric perspective, selecting the next task to assign based on a global difficulty metric (Best Task or Worst Task). Our comprehensive empirical evaluation demonstrates three key findings: (1) the incremental expansion strategy significantly outperforms the naive combinatorial approach by successfully pruning the dominant task-allocation search space; (2) we identify a task-conflict expansion dilemma, where sophisticated conflict resolvers effective for large-agent pathfinding subproblems can be detrimental in the integrated CT-TAPF setting; and (3) our proposed sub-optimal solvers establish a new, more efficient frontier on the solution quality-runtime spectrum compared to "nn-" agent-centric baselines. This work provides a foundational framework and a set of effective algorithms for a new, practical class of cooperative multi-agent problems.

Abstract

Multi-Robot Task Allocation

Explore similar work

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

ARMATA: Auto-Regressive Multi-Agent Task Assignment

Decentralized Multi-Robot Task Allocation Under Degraded Communication: A Benchmark of Performance, Reliability, and Computation