Technical Summary: Bi-Layer Ant Colony Optimization for Multi-Robot Task Allocation and Routing

Problem Definition

The paper addresses the Multi-Robot Task Allocation (MRTA) problem within the context of delivery and logistics applications. The core challenge involves coordinating a fleet of mobile robots to execute a set of delivery tasks, where each task consists of a specific pickup location and a drop-off location.

The optimization problem is defined as a coupled decision process requiring two simultaneous outputs:

1. Task Assignment: Determining which robot performs each specific task.
2. Task Sequencing: Determining the optimal order in which a robot executes its assigned tasks.

The objective is to minimize the total travel distance of the entire fleet while ensuring every task is executed exactly once by a single robot. The authors note that existing approaches often treat assignment, sequencing, and execution as independent stages optimized separately. This separation can lead to suboptimal global coordination, redundant motion, and reduced system efficiency. The paper formulates the MRTA as a unified optimization problem where assignment and sequencing decisions are interdependent.

Methodology: Bi-Layer Ant Colony Optimization (ACO)

To solve the formulated optimization problem, the authors propose a Bi-Layer Ant Colony Optimization (ACO) algorithm. Unlike traditional hierarchical methods that solve layers sequentially, this approach integrates two interdependent decision layers into a single colony process.

Core Framework

The algorithm employs a population-based metaheuristic inspired by ant foraging behavior. Each "ant" in the colony constructs a complete solution by simultaneously navigating two decision layers:

1. Task Assignment Layer:

   • Determines the allocation of tasks to robots ($x_{i,j}$).
   • Utilizes a pheromone matrix $\tau_{assign} \in \mathbb{R}^{m \times n}$ (tasks $\times$ robots) representing the learned desirability of assigning task $j$ to robot $i$.
   • Heuristic information ($\eta_{assign}$) is derived from the inverse of the distance between the robot's start position and the task's pickup location.

2. Task Sequencing Layer:

   • Determines the visiting order ($\pi_i$) for the tasks assigned to each robot.
   • Utilizes a pheromone matrix $\tau_{seq} \in \mathbb{R}^{m \times m}$ representing the desirability of transitioning from task $j$ to task $k$ within the same robot's route.
   • Heuristic information ($\eta_{seq}$) is derived from the inverse of the distance between the drop-off of the current task and the pickup of the next task.

Algorithm Execution

The algorithm proceeds through iterative cycles:

1. Construction: Each ant probabilistically assigns tasks to robots based on the assignment layer's pheromone and heuristic values. Once assignments are made, the sequencing layer constructs the route for each robot. The first task is selected based on proximity to the robot's start, and subsequent tasks are sampled based on the sequencing pheromone and heuristic values.
2. Evaluation: The total travel distance for the constructed solution is calculated, summing the distances for all robots (start-to-pickup, pickup-to-drop-off, and drop-off-to-next-pickup).
3. Pheromone Update: After all ants construct their solutions, pheromone trails on both matrices are updated. This involves:
   • Evaporation: Reducing existing pheromone levels to prevent stagnation.
   • Reinforcement: Depositing new pheromone proportional to the quality of the solution ($Q/C(a)$), where better solutions (lower cost) deposit more pheromone. The update equations ensure that both the assignment pairs and the specific task transitions in the route are reinforced.

Key Contributions

The paper identifies the following primary contributions:

• Unified Objective Function: The formulation of a new cost function that transforms MRTA into a coupled optimization problem, explicitly capturing the interdependence between global task distribution and local route planning.
• Bi-Layer ACO Architecture: The introduction of a novel algorithmic framework that integrates assignment and sequencing into a single colony process using two distinct, interconnected pheromone matrices. This allows for the simultaneous optimization of task allocation and route planning.
• Performance Validation: Comprehensive comparative experiments demonstrating the efficacy of the proposed method against Mixed-Integer Linear Programming (MILP) and Particle Swarm Optimization (PSO).

Experimental Results

The proposed method was evaluated in a ROS 2 Humble and Gazebo simulation environment using three TurtleBot3 robots. Experiments were conducted across three scenarios with 5, 10, and 20 tasks.

Performance Metrics:

• Total Travel Distance: The Bi-Layer ACO consistently achieved the lowest mean total travel distance across all task sizes.
  • Compared to MILP, ACO reduced total distance by approximately 17.7% (at 5 tasks).
  • Compared to PSO, ACO reduced total distance by approximately 9.8%.
• Completion Time: The proposed method also demonstrated faster task completion times.
  • Compared to baseline methods, ACO reduced completion time by nearly 20%.
• Stability and Scalability:
  • ACO exhibited lower standard deviations in both distance and time compared to PSO and MILP, indicating more stable convergence.
  • As task complexity increased (up to 20 tasks), ACO maintained superior performance, whereas MILP and PSO showed increased dispersion and higher costs.

Significance and Claims

The paper claims that the proposed Bi-Layer ACO framework effectively addresses the limitation of separating task assignment and routing in existing MRTA approaches. By optimizing these decisions jointly, the method reduces redundant motion and improves overall mission efficiency.

The authors conclude that the Bi-Layer ACO is a scalable and reliable solution for multi-robot delivery tasks, offering a balance between exploration and exploitation that yields shorter, more consistent routes than traditional exact methods (MILP) or other metaheuristics (PSO). The work suggests that this unified approach is particularly valuable for enhancing the efficiency of real-world logistics and delivery systems. Future work is noted to focus on extending the approach to dynamic environments, heterogeneous robot fleets, and communication constraints.