# Integrating collision avoidance strategies into multi-robot task allocation for inspection

Hamza Chakraa, Edouard Leclercq, François Guérin, Dimitri Lefebvre

► To cite this version:

Hamza Chakraa, Edouard Leclercq, François Guérin, Dimitri Lefebvre. Integrating collision avoidance strategies into multi-robot task allocation for inspection. Transactions of the Institute of Measurement and Control, 2025, 10.1177/01423312241295828. hal-04921452

HAL Id: hal-04921452

https://hal.science/hal-04921452v1

Submitted on 30 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Integrating collision
avoidance strategies
into Multi-Robot Task
Allocation for
inspection

Journal Title
XX(X):2-22
©The Author(s) 2016
Reprints and permission:
sagepub.co.uk/journalsPermissions.nav
DOI: 10.1177/ToBeAssigned
www.sagepub.com/

SAGE

Hamza Chakraa¹, Edouard Leclercq¹, François Guérin¹, Dimitri Lefebvre¹

Abstract

Recent research topics have been placed on reinforcing security and safety measures within high-risk industries to protect both equipment and the environment. Numerous industries carry substantial implications for their surroundings. During significant incidents like chemical spills, or nuclear accidents, swiftly gathering precise and dynamic data poses a considerable challenge. Subsequently, this paper focus on optimizing a mission involving multiple mobile robots charged with inspecting an industrial zone. The objective is to efficiently collect measurements from diverse positions using a fleet of sensing robots operating from a central depot. The aim is to develop an algorithm for robots decision-making that optimizes mission planning by minimizing an objective function. Initially, we explore our previous proposed solutions and we improve the system by integrating a navigational layer to manage collision avoidance between robots. Then, we delve into scenarios involving multiple similar tasks distributed in a limited geographical environment, corresponding to solving the multiple Traveling Salesman Problems (mTSP). Subsequently, in this case, to address the task allocation while ensuring robots avoid collisions, we propose a clustering-based approach coupled with the 2-Opt local search method.

Keywords

Multi-robot system (MRS), multi-robot task allocation (MRTA), collision avoidance, optimization, industrial inspection.
**Introduction**

Exploring inspection missions within industrial zones using a Multi-Robot System (MRS) is the focus of this paper. Specifically, it delves into on safeguarding high-risk industrial areas where hazardous substances are handled, produced, or stored. Monitoring serves as a key measure in averting unforeseen accidents and ensuring overall security and safety. Coordinating Unmanned Ground Vehicles (UGVs), Unmanned Ariel Vehicles (UAVs), and Unmanned Surface Vehicles (USVs) presents a promising avenue to gather inspection data. Beyond inspection, these missions can also serve for intervention purposes during disasters in industrial areas, aiding firefighters and inspectors. Traditionally, experts manually construct mission plans, but enabling robots with decision-making algorithms is crucial to accelerate this process. These algorithms would allocate tasks among the robots, determine task sequences, and identify necessary information collection.

Various industries and applications have employed MRS to innovate in areas like agriculture (Miloradovic et al., 2022), inspection (Portugal and Rocha, 2022), search and rescue (Mishra et al., 2020), and product distribution in warehouses (Wurman et al., 2008). MRS algorithms exhibit diverse forms and fall into two primary classifications: centralized and decentralized strategies (Verma and Ranga, 2021). Centralized methods rely on a server tasked with transmitting all information to the robots, without the need for direct communication among them. In contrast, decentralized methods depend on a communication network, enabling robots to share information without the need for a supervisory entity.

These scenarios prompt the exploration of the widely recognized Multi-Robot Task Allocation (MRTA) problem (Chakraa et al., 2023a). It involves organizing multiple mobile robots to accomplish numerous tasks while adhering to specific constraints in order to optimize a defined objective. Various taxonomies have been presented to categorize MRTA problems. Gerkey and Matarić (2004) proposed a grouping scheme based on robot capabilities, task requirements, and time, delineating between Single-Task (ST) robots, capable of handling one task at a time, and Multi-Task (MT) robots, capable of handling multiple tasks concurrently. Similarly, task categorization includes Single-Robot (SR) tasks, requiring precisely one robot, and Multi-Robot (MR) tasks, which might involve multiple robots. Time allocation can be Instantaneous (IA), involving immediate task assignments without future planning, or Time-Extended (TA) which involves organizing a series of tasks for individual robots within a planning time frame. MRTA problems are classified by combining these dimensions; for instance, MT-SR-TA signifies problems where robots can execute several tasks at a time, tasks necessitate just one robot, and the allocation is over a planning time frame.

The problem of this study considers multiple mobile sensing robots that must perform
measurement tasks across locations within an industrial zone while optimizing mission

<footnote n="1">¹Université Le Havre Normandie, GREAH, Le Havre, France.</footnote>

<footnote>**Corresponding author:**
Hamza Chakraa, Université Le Havre Normandie, GREAH, 75 Rue Bellot, 76600, Le Havre, France.
Email: hamza.chakraa@univ-lehavre.fr
The terms "robot" and "agent" are employed interchangeably in this paper.</footnote>
time or energy consumption. Each robot, equipped with specific sensors, can execute
multiple measurements simultaneously at a single location. Crafting missions for
multiple robots that capitalize on their collective abilities presents novel challenges
by adding constraints previously unaccounted for. In our specific scenario, assigned
tasks entail gathering measurements via robot-carried sensors. Each robot follows a
task sequence with the global objective of collectively completing all tasks at minimal
cost. This system revolves around a single depot, where the robotic agents begin and
end their mission. We solve this MRTA problem in a centralized and offline way
considering knowing the environment properties. This comprehensive model reflects
the complex structure of real-world multi-robot missions.

Our recent work has extended the optimization in Chakraa et al. (2023b), which introduced a 2-Opt approach with Hybrid Filtered Beam Search (HFBS) to the previously mentioned MRTA problem. Compared to Chakraa et al. (2023b), the main contribution of this paper is to study the collision avoidance among robots across diverse scenarios. Specifically, the innovation lies in addressing the aspect of collision avoidance at different levels of the robots control architectures. First, for few to moderate heterogeneous measurement tasks, an online navigation-based methodology is introduced. Second, for multiple homogeneous tasks, a clustering-based method that operates at the task allocation level is proposed to avoid collisions. In addition, and apart from collision avoidance issues, this paper also highlights how combining clustering algorithms with scheduling techniques may reduce the numerical complexity of the global optimization.

The remainder of this paper is structured as follows: the second section provides a summary of the current state of the art about MRTA and collision avoidance in MRPP (Multi-Robot Path Planning). Section 3 outlines the problem under study and introduces some mathematical models. Additionally, section 4 focuses on addressing the initial problem involving relatively small and medium-sized heterogeneous tasks. Section 5 delves into the specifics of the medium/large sets of homogeneous tasks. Lastly, Section 6 offers conclusions, recommendations, and suggestions for future studies.

## Literature review

### *Multi-Robot Task Allocation*

The resolution of MRTA scenarios can be achieved through three primary methods: market-based, optimization-based, or behavior-based strategies.

**Market-based approaches** provide practical solutions to address MRTA problems. These approaches depend on a bidding process between robots to fulfill specific constraints. They can take on a centralized form, where a central auctioneer (either a supervisory entity or a robotic agent) collects bids and assigns tasks, or a distributed form, where robots autonomously resolve conflicts. One classic market-based technique employed in MRTA is the auction algorithm. An important advancement is the Consensus-Based Bundle Algorithm (CBBA), presented by Choi *et al.* (2009), which integrates auction principles and a consensus process to ensure
conflict-free allocations. Building upon CBBA's framework, Zitouni et al. (2020) proposed alternative algorithms aiming for enhanced optimality and communication efficiency. Observe that several studies have extended market-based methods to tackle intricate coordination constraints (Ye et al., 2021).

**Behavior-based approaches** categorize tasks according to specific behaviors. These methodologies prioritize enabling robots to make independent decisions during missions rather than relying on constant supervision. Parker (1998) introduced the ALLIANCE algorithm, aimed at assessing a sequence of tasks to agents to minimize the time taken to perform the allocated activities. Werger and Mataric (2000) developed the BLE (Broadcast of Local Eligibility) algorithm to manage dynamically assigning tasks, accommodating new ones emerging through the mission. Additionally, Beynier and Mouaddib (2007) demonstrated that Markov decision processes can effectively address certain types of MRTA problems involving dependencies and temporal constraints.

**Optimization-based approaches** encompass two primary categories: exact and approximate methods (Rabiner, 1984). Within this framework, the ST-SR-IA configuration is the only one enabling polynomial-time solutions, making it amenable to exact approaches such as the Hungarian Algorithm (HA) (Ismail and Sun, 2017) or Integer Linear Programming (ILP) (Zhou et al., 2019). Simultaneously, MRTA often leverages approximate techniques like heuristics and meta-heuristics for NP-hard problems and due to their reasonable computational complexities for large-scale problems. Notably, bio-inspired algorithms such as Ant Colony Optimization (ACO) and Bee Colony Optimization (BCO) have found application in solving MRTA problems (Liu et al., 2021). Additionally, a spectrum of heuristic and meta-heuristic methods, including Genetic Algorithms (GA) (Chakraa et al., 2023c), HFBS (Gam et al., 2023), Tabu Search (TS) (Nekovár et al., 2021), Particle Swarm Optimization (PSO) (Chen et al., 2018), and Simulated Annealing (SA) (David and Rögnvaldsson, 2021) has been employed. Despite their ability to solve problems within reasonable time frames, the scalability of meta-heuristics remains a challenge for larger-sized problems. Consequently, researchers proposed a two-stage process, beginning with task assignment and followed by task planning. For instance, in (Janati et al., 2017), a grand-scale problem was addressed by creating partitions within the environment using k-means clustering. This method enabled the HA to efficiently distribute robots among clusters, while GA handled planning within each cluster.

## Multi-Robot Path Planning

Coordinating multiple agents to perform tasks while ensuring free collision navigation demands complex algorithms and strategies. While MRTA and collision avoidance are two distinct aspects, they can influence each other. Task allocation algorithms might consider proximity or potential collision scenarios to optimize assignments and minimize potential conflicts among robots. However, the direct implementation of collision avoidance strategies usually occurs at lower levels, specifically at the level of motion/path planning, where individual robots adjust their trajectories to avoid collisions. MRPP algorithms can be either graph-based methods (Dijkstra, A*, D*), sampling-based methods (e.g., Rapidly-exploring Random Trees (RRT), Probabilistic
Roadmaps (PRM), Artificial Potential Field (APF), Voronoi Diagram) or bio-inspired methods (GA, ACO, PSO, etc.) (Madridano et al., 2021).

In general, researchers modify or add extra layers to MRPP methods to consider collision avoidance in different ways either by adding waiting times or switching trajectories in case of collision situations. Li et al. (2022) presented an extended version of the D* approach to deal with collisions and deadlock situations in a real-time manner considering five conflict types. Besides, the work of Dang et al. (2019) considered APF by combining rotational force field and repulsive force field to design a mechanism so that robots can avoid collisions and escape complex obstacle shapes. Spensieri et al. (2016) utilized the PRM method to compute free collision trajectories in a MRTA context due to its low numerical complexity compared to the high one for bio-inspired methods Bhattacharjee et al. (2011).

Based on the literature review, collision avoidance strategies are a fundamental aspect addressed within the discussed path planning methods. Nevertheless, there exist particular scenarios where implementing collision avoidance at the task allocation level becomes feasible, by passing the need for specific MRPP methodologies. Conversely, challenges arise in certain situations where avoiding these methods isn't possible. This paper aims to explore and analyze both scenarios in depth, exploring the effectiveness of collision avoidance strategies across various operational levels in MRS.

## Problem overview

In this section, we will describe our MRTA problem and formally define it mathematically. Additionally, we will delve into describing and formalizing the special scenario mentioned before where the problem focuses on homogeneous tasks, enabling the allocation without encountering collisions.

<figure><img src="image_2.png" /><figcaption>**Figure 1.** Exemplary scenario: Presenting a situation (left) with a potential solution (right).</figcaption></figure>

We consider a known navigation setting, breaking it down into a grid map consisting of cells within a two-dimensional mesh sized ($N_x \times N_y$) constituted of V cells. Each cell $v_j$ defines a spatial area where a robot can stay and it is defined by its center of gravity spatial coordinates $(x_j, y_j)$. Note that $V = \{v_1, \dots, v_j, \dots, v_V\}$ is the set
of cells. Moreover, the environment may include several types of obstacles where the robots cannot stay.

Several measurements need to be conducted within specific cells, termed "sites" in the forthcoming sections. $\mathcal{A} = \{a_1, \dots, a_i, \dots, a_A\}$ is the group of sites addresses that must be visited ($\mathcal{A}$ is a portion of $\mathcal{V}$). The robots commence and conclude their mission at the same site $a_1$, referred to as the "depot," where no specific tasks are necessary. $\mathcal{M} = \{m_1, \dots, m_q, \dots, m_M\}$ encompasses various measurement types, likely representing diverse data or information required by the robots during their mission. The set of tasks is defined by $\mathcal{J} = \{j_1, \dots, j_t, \dots, j_T\}$, where $T$ denotes the overall quantity of tasks. A task $j_t = (i, q)$ is formally defined as a measurement of type $m_q \in \mathcal{M}$ to be executed at a specified site $a_i \in \mathcal{A}$. Furthermore, the set of all tasks in different sites is defined by the function $\mathcal{T}: \mathcal{M} \times \mathcal{A} \to \{0, 1\}$ in such a way that $\mathcal{T} = [t_{i,q}]$, where $t_{i,q} = 1$ if the measurement $m_q$ is required at site $a_i$, and $t_{i,q} = 0$ otherwise.

$\mathcal{R} = \{r_1, \dots, r_k, \dots, r_R\}$ stands for the set of mobile robots that constitute our MRS. Each one is equipped with particular sensors responsible of task execution and $R$ is the total number of robots. Each sensor is tailored for a specific measurement, aligning with the set $\mathcal{M}$, which also represents the sensor types. The function $\mathcal{P}: \mathcal{M} \times \mathcal{R} \to \{0, 1\}$ defines the sensors carried on by a robot $r_k: \mathcal{P} = [p_{k,q}]$, where $p_{k,q} = 1$ if robot $r_k$ is outfitted with a sensor of type $m_q$, and $p_{k,q} = 0$ otherwise. Furthermore, each robotic agent operates under constraints concerning service time or energy usage. Denoted as $\mathcal{B}_k$, it signifies the maximum allowable travel cost for robot $r_k$, where it could refer to time or energy.

The succeeding stage involves determining the lowest possible cost for traveling between locations. Initially, for each agent, every move between two adjoining cells $v_j$ and $v_{j'}$, is outlined by an elementary cost $\tilde{c}(j, j', k) > 0$. It's important to note that if $v_i$ and $v_j$ are not adjacent, traveling straight between them isn't possible; in such instances, $\tilde{c}(j, j', k) = \infty$. Due to the diversity among robots in the team, each one possesses its individual graph and costs. Each cell is depicted as a node within the graph, and the transitions between cells match possible moves related to the mentioned elementary costs. At this stage, Dijkstra algorithm (Dijkstra, 1959) comes into play to compute the minimal cost $c(i, i', k)$ between every two sites $a_i, a_{i'} \in \mathcal{A}$ for each agent $r_k$. Depending on the context, the costs $c$ and $\tilde{c}$ can indicate either energy units (EU) or time units (TU). The consequent assumptions are accounted for:

* A robotic agent is able to perform one or multiple tasks simultaneously at a single site.

* Each measurement task is accomplished by one robot.

* Every measurement task is executed by a robot equipped with the necessary sensor.

* All robots commence and conclude their missions at the same designated location, referred to as the depot.

* A sequence of tasks is computed for each robot (routing).

* A motion planning technique is implemented to ensure collision-free trajectories for robots during the mission.
This MRTA formulation can be represented using Mixed Integer Linear Programming (MILP) outlined in Equations (1) through (7). The binary decision variable $x_{i,j}^k$ equals 1 when robot $r_k$ transitions from the site $a_i$ to $a_j$; otherwise, it's 0. Moreover, $u_i^k$ is an integer decision variable that represents the visiting order of the site $a_i$ that is visited by robot $r_k$. The reader is referred to Chakraa et al. (2023b) for more details.

$$ \min \sum_{r_k \in \mathcal{R}} \sum_{a_i, a_j \in \mathcal{A}} x_{i,j}^k \times c(i, j, k) \qquad (1) $$

$$ \text{or min} \quad \max_{r_k \in \mathcal{R}} \sum_{a_i, a_j \in \mathcal{A}} x_{i,j}^k \times c(i, j, k) \qquad (2) $$

$$ \text{s.t.} \quad \sum_{a_i \in \mathcal{A}} x_{1,i}^k = 1 \quad \forall r_k \in \mathcal{R} \qquad (3) $$

$$ \sum_{a_j \in \mathcal{A}} x_{i,j}^k = \sum_{a_j \in \mathcal{A}} x_{j,i}^k \quad \forall a_i \in \mathcal{A}, \forall r_k \in \mathcal{R} \qquad (4) $$

$$ u_i^k + x_{i,j}^k \le u_j^k + (A-1) \times (1-x_{i,j}^k) \quad \forall a_i \in \mathcal{A}, \forall a_j \in \mathcal{A}/\{a_1\}, \forall r_k \in \mathcal{R} \qquad (5) $$

$$ \sum_{a_i, a_j \in \mathcal{A}} x_{i,j}^k \times c(i, j, k) \le \mathcal{B}_k \quad \forall r_k \in \mathcal{R} \qquad (6) $$

$$ \sum_{r_k \in \mathcal{R}} \sum_{a_i \in \mathcal{A}} p_{k,q} \times x_{i,j}^k \ge t_{j,q} \qquad (7) $$

$$ \forall m_q \in \mathcal{M}, \forall a_j \in \mathcal{A} $$

A specific configuration exists when numerous tasks with a similar measurement is considered in a limited area with few obstacles. In particular, in an obstacle-free environment, the cost $c'(i, j, k)$ between every two sites $a_i, a_j \in \mathcal{A}$ for every robot $r_k$ is determined using the Euclidean distance formula while adding a penalty rate considering the velocity of the robots $v_k$. The cost $c(i, j, k)$ is replaced by $c'(i, j, k)$.

$$ c'(i, j, k) = \frac{1}{v_k} \times \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \qquad (8) $$

This equation calculates the cost based on the coordinates $a_i = (x_i, y_i)$ and $a_j = (x_j, y_j)$ representing the two-dimensional positions of the sites $a_i$ and $a_j$. The following assumptions are considered:

* Each robot is able to perform all tasks.

* The depot is clearly separated from the task locations.

The second assumption plays a key role in solving the problem of robots collisions. The depot should be located at a certain position such that several areas can be a priory defined to separate the task locations in several sub-regions (see Figure 1 as an example). Such spatial specifications offer the advantage of considering collision issues at the task allocation level. Further, this problem can be modeled as mTSP
utilizing equation (2) as its cost function, wherein the cost variable c is substituted with c' while adhering to the constraints from (3) to (6). Additionally, the Equation (9) replaces Equation (7). In this context, Equation (9) ensures the visitation of each site precisely once (each robot being able to perform all tasks at each site).

$$ \sum_{r_k \in \mathcal{R}} \sum_{a_i \in \mathcal{A}} x_{i,j}^k = 1 \quad \forall a_j \in \mathcal{A} \qquad (9) $$

## Small/Medium sets of heterogeneous tasks

In our previous studies, an heuristic approach employing HFBS as described in (Gam et al., 2023) was used. This heuristic was subjected to additional refinement through the integration of the 2-Opt local search, as detailed in Chakraa et al. (2023b). Furthermore, a comparative study was introduced involving a GA-based approach, HFBS, and the MILP solver Cplex (Chakraa et al., 2023c). In this section, we present these methodologies, integrating the 2-Opt technique within the comparative study. Additionally, we outline a methodology for preventing collisions post-task allocation.

## Optimization-based methods

**Hybrid Filtered Beam Search (HFBS):** addresses problems by structuring and reducing a tree of nodes, each representing a partial or full solution to the MRTA problem. Each solution is characterized by sequences of measurements gathered by robots at various locations. The algorithm explores specific branches of the search tree with local and global filters of size $\beta_l$ and $\beta_g$ according to a cost function. At each node s, the cost function $f(s) = g(s) + h(s)$ sums the cost $g(s)$ from the initial node $s_0$ to the current one s and an estimation of the remaining cost $h(s)$ to the terminal node. The heuristic function is formulated by considering the minimum non-zero costs between locations and deliberately underestimating to converge towards a complete solution. For more details, readers are referred to Chakraa et al. (2023b).

**Genetic Algorithms (GA):** draws inspiration from natural selection to address complex problems. GA simulate evolution by iteratively refining sets of potential solutions using selection, crossover, and mutation operations. In this specific study, the chromosome structure, representing task assignments to robots, is organized as a table with three lines denoting positions, measurements, and assigned robots (Figure 2). Each column forms a gene, encoding details of task allocation based on positions and measurements. The GA initiates with a randomly generated population, and generating suitable robot-task matches to avoid unfit solutions. The fitness function evaluates solution quality, and selection processes guide evolution toward more fit solutions, considering both parents and offspring. Recombination involves crossover and mutation, altering task assignments and introducing minor changes to maintain diversity. The developed approach ensures a balanced population for efficient exploration and exploitation (Chakraa et al., 2023c).

**2-Opt local search** is a method that was initially introduced by Croes (1958) to solve the TSP by iteratively replacing two edges within a tour to create a shorter path, aiming to improve upon an existing or randomly generated solution. This process involves
<table><caption>**Figure 2.** Encoding a candidate solution in GA</caption><thead><tr><th>Position</th><th>2</th><th>2</th><th>3</th><th>3</th><th>3</th><th>4</th><th>4</th><th>5</th></tr></thead><tbody><tr><th>Measure</th><td>1</td><td>3</td><td>1</td><td>2</td><td>3</td><td>1</td><td>2</td><td>3</td></tr><tr><th>Assigned robot</th><td>1</td><td>2</td><td>1</td><td>2</td><td>2</td><td>1</td><td>1</td><td>2</td></tr></tbody></table>

identifying intersections within the path and swapping two edges until no further enhancements are possible, exhausting all potential permutations.

<figure><img src="image_3.png" /><figcaption>**Figure 3.** The initial solution (left) compared to the solution after applying the 2-Opt operation (right).</figcaption></figure>

When considering two edges ($a_i \to a_{i+1}$) and ($a_j \to a_{j+1}$) within a robot tour, there are specific options for replacing these edges with two additional ones. The selection can be between ($a_i \to a_j$) and ($a_{i+1} \to a_{j+1}$), or ($a_i \to a_{j+1}$) and ($a_j \to a_{i+1}$). However, only one pair will yield the subsequent sequence. It's essential to choose the swap that maintains the tour as an oriented cycle, where each site has precisely one incoming and outgoing edge. The criterion for this swap, ensuring the new set of edges forms a tour again, is essential. This criterion applies to both edges ($a_i \to a_j$) and ($a_{i+1} \to a_{j+1}$), as depicted in Figure 3. Such replacements are performed as long as there exists pairs ($a_i \to a_{i+1}$) and ($a_j \to a_{j+1}$) such that inequality (10) holds. A sequence is considered 2-optimal if the 2-Opt method cannot improve it further. However, if this condition is violated, a shorter sequence can be achieved by replacing the edges ($a_i \to a_{i+1}$), ($a_j \to a_{j+1}$) with ($a_i \to a_j$), ($a_{i+1} \to a_{j+1}$).

$$c(i, i+1, k) + c(j, j+1, k) > c(i, j, k) + c(i+1, j+1, k) \quad (10)$$

Moreover, within the modified sequence, reversing the route between the sites $a_{i+1}$ and $a_j$ proves to be an effective transformation. This reversal reduces permutations and enhances execution time. In Figure 3, the orientation of the tour edges between $a_{i+1}$ and $a_j$ has been inverted. The choice of permutation strategies can vary, ranging from selecting the first found option to choosing the best or worst option based on the scenario or even randomly selecting from a pool of potential permutations.

Given the complexity of our task allocation problem, which involves both assignment and routing aspects, solutions derived from HFBS and GA may yield to sub-optimal results. To improve the quality of these solutions, we employ the 2-Opt local search method. Its primary purpose is to refine the routing aspect of the HFBS or GA-derived
solution. By applying 2-Opt as a post-processing step for each robot's sequence, we aim to improve the efficiency and optimality of the routing scheme, thus enhancing the overall performance of our task allocation system.

Collision avoidance

When it comes to the complex orchestration of multiple robots operating in shared spaces, ensuring collision avoidance becomes paramount (Madridano et al., 2021). Navigational collision avoidance methods are crucial in robotics, particularly when multiple robots operate in common areas. One effective approach involves leveraging real-time GPS coordinates exchanged over a communication network to anticipate and avoid potential collisions with both static and dynamic obstacles (other robots are considered as dynamic obstacles).

<figure><img src="image_4.png" /><figcaption>**Figure 4.** Collision avoidance strategy: activating repulsive action when robot proximity falls below the threshold $D_{max}$.</figcaption></figure>

A fundamental concept involves the computation of distances between robots. When considering two robots $r_k$ and $r_l$, we denote as $D_{kl}$ the distance between $r_k$ and $r_l$. Note that $D_{kl}$ can be obtained from GPS coordinates, using Haversine formulas (Robusto, 1957). By establishing a threshold distance $D_{max}$, robots can define a protected spherical area around themselves. When another robot breaches this predefined safe zone, triggering $D_{kl}$ to fall below the threshold, it activates a repulsive effect. This effect generates a repulsive speed, modifying on of the robots trajectory to avoid collision. The intensity of this repulsion dynamically adjusts based on the distance between the robots: as the breaching robot gets closer, the repulsive force strengthens, guiding it away from the defined safe zone. The intensity of the repulsive effect is presented in Equation (11) where $V_k$ stands for the maximal repulsive velocity intensity for the robot $r_k$ (adjustable parameter). This velocity is added to the normal velocity of the robot's in the control law.
$$ \|\vec{v}_{kl}\| = \begin{cases} V_k \cdot \cos(\frac{\pi D_{kl}}{2D_{max}}) & \text{if } D_{kl} < D_{max} \\ 0 & \text{else} \end{cases} \qquad (11) $$

This presented approach aligns with the APF method, wherein the repulsive effect created among robots mimics a repulsive potential field, shaping the robots behaviors to evade collisions while navigating narrow areas. Its primary strength resides in its inherent simplicity and efficacy. Through the simulation of a virtual force field around each robot, these repulsive potential fields guarantee that robots instinctively avoid one another, minimizing collision risks without necessitating intricate centralized coordination. This decentralized approach not only ensures effectiveness but also facilitates scalability. Moreover, the APF method is adapted in dynamic environments. As repulsive forces dynamically adjust based on proximity to other robots, obstacles, or altering conditions. Additionally, its computational efficiency and simplicity provide a highly appealing choice for practical implementation in various applications. The reader is referred to (Petitprez et al., 2023) for more details about the approach in a multi-UAVs team application.

In summary, the method presented for ensuring a collision free mission harnesses real-time GPS coordinates, establishing protective zones and dynamically adjusting repulsive forces based on the proximity of neighboring robots. Such an approach not only promotes safer robot interactions but also enables efficient and reliable navigation in shared spaces.

## Results and discussion

First of all, we present the results derived from the task allocation part using the Cplex solver in conjunction with HFBS and 2-Opt. Following that, we present the results obtained from the GA combined with the 2-Opt approach. This exhaustive comparative analysis of the three optimization methodologies applied to address the investigated problem is detailed in Table 1. The analysis encompasses diverse scenarios involving varying numbers of robots, tasks, measurement types, and sites. Table 1 presents the cost and run-time associated with each approach across 16 scenarios. Through result analysis, we evaluate the performances in terms of cost, identifying disparities in cost values, and evaluate the computational efficiency of each method based on their corresponding running times. Simulations were executed on an Intel(R) Core(TM) CPU i5 @ 2.6GHz.

This study extends the research detailed in (Chakraa et al., 2023c) by integrating the 2-Opt algorithm. The previous one showed the distribution of costs and running times for each method without the 2-Opt phase across the 16 scenarios detailed in Table 1. The analysis reveals that the HFBS method typically entails higher costs, closely trailed by the GA method, while the Cplex method consistently demonstrates the lowest costs. In terms of execution times, the GA and HFBS methods generally exhibit shorter durations compared to the Cplex solver, which notably presents notably longer run-times (Figure 5(a)).

From Table 1, it's obvious that the proposed combination of HFBS and 2-Opt methods consistently returns good solutions compared to just applying HFBS. The challenge of HFBS lies in determining the ideal combination of $\beta_g$ and $\beta_l$. Specifically,
<table><caption>**Table 1.** Comparative study</caption><thead><tr><th rowspan="2">Robots<br>(R)</th><th colspan="3">Scenario</th><th colspan="3">GA + 2-Opt</th><th colspan="3">HFBS + 2-Opt</th><th colspan="3">Cplex</th></tr><tr><th>Measurements<br>(M)</th><th>Tasks<br>(T)</th><th>Sites<br>(A)</th><th>GA Parameters<br>(τ<sub>p</sub>, τ<sub>g</sub>)</th><th>Cost<br>(EU)</th><th>Time<br>(s)</th><th>HFBS Parameters<br>(β<sub>g</sub>, β<sub>l</sub>)</th><th>Cost<br>(EU)</th><th>Time<br>(s)</th><th>Cost<br>(EU)</th><th>Time<br>(s)</th><th>Cost<br>(EU)</th><th>Time<br>(s)</th></tr></thead><tbody><tr><td>1</td><td>3</td><td>13</td><td>10</td><td>(20,30)</td><td>74</td><td>1.18</td><td>(20,4)</td><td>74</td><td>1.37</td><td>74</td><td>0.5</td><td></td><td></td></tr><tr><td>1</td><td>4</td><td>15</td><td>10</td><td>(20,30)</td><td>74</td><td>1.07</td><td>(3,3)</td><td>74</td><td>0.97</td><td>74</td><td>0.66</td><td></td><td></td></tr><tr><td>1</td><td>4</td><td>30</td><td>13</td><td>(200,80)</td><td>130</td><td>3.4</td><td>(23,19)</td><td>132</td><td>1.9</td><td>130</td><td>0.5</td><td></td><td></td></tr><tr><td>1</td><td>5</td><td>33</td><td>13</td><td>(300,80)</td><td>130</td><td>4.2</td><td>(23,6)</td><td>132</td><td>1.7</td><td>130</td><td>0.92</td><td></td><td></td></tr><tr><td>2</td><td>3</td><td>13</td><td>10</td><td>(30,30)</td><td>138</td><td>1.08</td><td>(11,8)</td><td>138</td><td>1.25</td><td>138</td><td>1.04</td><td></td><td></td></tr><tr><td>2</td><td>4</td><td>15</td><td>10</td><td>(30,30)</td><td>140</td><td>1.07</td><td>(5,4)</td><td>140</td><td>1.71</td><td>140</td><td>2.33</td><td></td><td></td></tr><tr><td>2</td><td>4</td><td>30</td><td>13</td><td>(250,80)</td><td>234</td><td>3.37</td><td>(22,20)</td><td>238</td><td>2.38</td><td>232</td><td>10.58</td><td></td><td></td></tr><tr><td>2</td><td>5</td><td>33</td><td>13</td><td>(350,80)</td><td>236</td><td>4.5</td><td>(27,10)</td><td>244</td><td>2.02</td><td>232</td><td>7.82</td><td></td><td></td></tr><tr><td>3</td><td>3</td><td>13</td><td>10</td><td>(40,30)</td><td>136</td><td>1.18</td><td>(21,5)</td><td>140</td><td>1.95</td><td>136</td><td>588</td><td></td><td></td></tr><tr><td>3</td><td>4</td><td>15</td><td>10</td><td>(40,30)</td><td>140</td><td>1.4</td><td>(16,8)</td><td>152</td><td>1.3</td><td>140</td><td>3.09</td><td></td><td></td></tr><tr><td>3</td><td>4</td><td>30</td><td>13</td><td>(450,100)</td><td>230</td><td>7.74</td><td>(25,21)</td><td>226</td><td>2.65</td><td>214</td><td>9.35</td><td></td><td></td></tr><tr><td>3</td><td>5</td><td>33</td><td>13</td><td>(550,100)</td><td>236</td><td>10.02</td><td>(12,7)</td><td>232</td><td>2.48</td><td>214</td><td>17.93</td><td></td><td></td></tr><tr><td>4</td><td>3</td><td>13</td><td>10</td><td>(80,50)</td><td>124</td><td>1.97</td><td>(18,2)</td><td>138</td><td>1.36</td><td>124</td><td>375.19</td><td></td><td></td></tr><tr><td>4</td><td>4</td><td>15</td><td>10</td><td>(80,50)</td><td>140</td><td>1.47</td><td>(28,25)</td><td>152</td><td>2.65</td><td>140</td><td>5.42</td><td></td><td></td></tr><tr><td>4</td><td>4</td><td>30</td><td>13</td><td>(650,100)</td><td>224</td><td>12.48</td><td>(9,7)</td><td>230</td><td>1.8</td><td>214</td><td>21.95</td><td></td><td></td></tr><tr><td>4</td><td>5</td><td>33</td><td>13</td><td>(750,100)</td><td>226</td><td>12.91</td><td>(24,9)</td><td>232</td><td>3.6</td><td>214</td><td>29.94</td><td></td><td></td></tr></tbody></table>

conducting multiple iterations with various parameter combinations, unrestricted by time constraints, can lead to computational issues. So, this practice is impractical as it would demand extensive computing time, ultimately compromising the algorithm's efficiency. Simply increasing these values doesn't consistently yield better solutions. Thus, conducting multiple tests becomes imperative to identify the most suitable values, as they vary based on specific scenario nuances. Subsequently, the integration of a local search mechanism immediately reduces the necessity for exhaustive parameter selection tests. Notably, this approach revises poor choices that could lead to poor solutions, resulting in acceptable ones through the TSP-based method. While the assignment phase remains changeless in the second stage, the overall optimality of the outcome relies on the quality of the assignment generated by HFBS. Nevertheless, it's observed that even in the worst-case scenario, where the assignment isn't optimal, the system manages to produce near-optimal solutions. In Figure 5(b), the gap between HFBS and the Cplex method has narrowed, leading to a reduced cost distribution for HFBS + 2-Opt compared to the one observed solely for HFBS in Figure 5(a).

For GA, it is obvious that combining it with the 2-Opt method produces better solutions compared to solely employing GA. The challenge with GA lies in its computational demands, often requiring significant time, a large population size, and numerous generations to converge toward the optimal solution. Integrating the 2-Opt method allows for using the GA process with smaller parameters to derive an initial solution, which can then be further improved through 2-Opt refinement. In Figure 5(b), the gap between GA and the Cplex method has diminished, resulting in a reduced cost
<figure><img src="image_5.png" /><figcaption>(a)) Comparative study between GA, HFBS, and Cplex</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b)) Comparative study between GA+2-Opt, HFBS+2-Opt, and Cplex</figcaption></figure>

**Figure 5.** The variations in results (cost and run-time) for the considered approaches in diverse set of scenarios

distribution for GA + 2-Opt in contrast to the distribution observed solely for GA in Figure 5(a).

The application of repulsive forces to avoid collisions among robots constitutes a method that, while robust against disturbances, may alter the overall cost of the mission, even when the task allocation is initially optimal. This collision avoidance approach operates independently from the optimization process, introducing adjustments that may deviate from the pre-defined optimal scheme. However, its resilience against unforeseen events and its capacity to prevent collisions remain significant assets in ensuring the safety operation of robots.
# Medium/Large sets of homogeneous tasks

## Clustering-based method

Cluster analysis is an unsupervised machine learning method used to organize data into distinct groups or clusters. Its aim is to group data points that share similarities while keeping those that are dissimilar in separate clusters. The primary objective is to identify specific structures within the data set. Commonly employed clustering algorithms, like k-means and hierarchical clustering, work towards this goal by iteratively assigning data points into clusters based on certain criteria such as proximity or similarity measures (Berkhin, 2006).

**K-means clustering** (Hartigan and Wong, 1979) stands as one of the widely used and efficient techniques among the clustering algorithms. Its mechanism involves a straightforward yet effective approach. Initially, it selects *k* initial cluster centers from the data set, typically chosen randomly or using a predefined method. These initial centers act as representatives of the clusters. Following this initialization, the algorithm iteratively moves these selected centers to refine the clusters. In each iteration, it assigns data points to the nearest cluster center based on a distance metric, often using Euclidean distance. Once data points are allocated to their nearest centers, the algorithm recalculates the cluster centers by computing the mean of all the data points assigned to each cluster. This process continues until convergence or until a specified stopping criterion is met.

The goal throughout these iterations is to minimize the clustering error criterion, usually the within-cluster maximum variance (WCM) or sum of squared distances of data points from their respective cluster centers. By optimizing this criterion, *k*-means aims to form clusters in such a way that the data points within a cluster are close to their cluster center while being sufficiently distant from other cluster centers. The strength of *k*-means lies in its simplicity, speed, and effectiveness in handling large data sets. However, it does have limitations, such as sensitivity to the initial choice of cluster centers and its tendency to produce spherical clusters due to its reliance on distance measures. Despite these limitations, *k*-means remains a foundational and widely used clustering method in various domains due to its practicality and ease of implementation. In this work, we opted for a straightforward approach by selecting the first *k* sites as the initial centroids. In our problem, the following parameters are considered:

* $\mathcal{L}$ denotes the set of *R* clusters.

* $L_i$ stands for the cluster set $i$.

* $L^{(i)}$ represents the cluster assignment of data point $a_i$.

* $\mu_j$ signifies the centroid of cluster $j$.

* $| \cdot |$ denotes the cardinal of a set.

* $\| \cdot \|^2$ denotes the squared Euclidean distance.

The objective function of k-means clustering aims to minimize the within-cluster maximum variance (WCM) that represents the sum of the squared distances between each data point $a_i$ and the centroid $\mu_j$ of the cluster it belongs to. WCM Equation (12) present the minimization criteria in k-means. Further, the pseudo-code for k-means clustering is shown in Algorithm 1.
$$WCM = \sum_{\mathbf{a}_i \in \mathcal{A}} \sum_{j=1}^{R} \|\mathbf{a}_i - \mathbf{\mu}_j\|^2 \quad (12)$$

<caption>**Algorithm 1: k-means clustering algorithm**</caption>

Input: $\mathcal{A}/\{a_1\}, R$
Output: $\mathcal{L} = \{L_1, \dots, L_R\}$
1 &nbsp; **for** $j = 1, \dots, R$ **do**
2 &nbsp;&nbsp;&nbsp;&nbsp; $\mu_j \leftarrow a_j$
3 &nbsp; **iterating** &leftarrow; True
4 &nbsp; **while** **iterating** **do**
5 &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{L}_{\text{prev}} \leftarrow \mathcal{L}$
6 &nbsp;&nbsp;&nbsp;&nbsp; **for** $i = 1, \dots, A - 1$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $L^{(i)} \leftarrow \arg\min_j \|a_i - \mu_j\|^2$
8 &nbsp;&nbsp;&nbsp;&nbsp; **for** $j = 1, \dots, R$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $L_j \leftarrow \{\}$
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $i = 1, \dots, A - 1$ **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $L^{(i)} = j$ **then**
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $L_j \leftarrow L_j \cup \{a_i\}$
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Update centroids: $\mu_j \leftarrow \frac{1}{|L_j|} \sum_{a_i \in L_j} a_i$
14 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\mathcal{L}_{\text{prev}} = \mathcal{L}$ **then**
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\text{iterating} \leftarrow \text{False}$

**2-Opt local search** will be applied after the sites have been partitioned into clusters. Within each cluster, the 2-Opt algorithm will calculate the optimal routing for each robot to complete the tasks, starting from a randomly determined order. The 2-Opt algorithm initiates its optimization process by generating an initial random order for task execution by the robots within the cluster. It then systematically evaluates and iteratively improves the order of tasks allocated to every one.

## Collision avoidance

Dividing the MRTA problem into clusters corresponds to partitioning the operational space into distinct regions, each designated for a specific robot. This spatial segmentation minimizes the complexity of the overall problem by creating smaller, more manageable subsets. As a result, the task allocation process becomes more structured and organized, with robots focusing on their assigned areas. Further, implementing the 2-Opt algorithm within these clusters allows each robot to optimize its routing locally, within its designated region. The 2-Opt algorithm, known for its effectiveness in optimizing routes by swapping segments to reduce the sequence cost, is efficient when applied to individual clusters. This optimization happens independently
within each cluster, enabling robots to fine-tune their mission without considering the
entire operational space, thus enhancing computational efficiency.

The crucial advantage of this approach lies in its collision avoidance mechanism. By confining robots to their respective clusters during task allocation, the probability of collisions significantly decreases. Since each robot operates within its defined region, the mission is planned and optimized in isolation from one another. This spatial isolation naturally reduces collision risks, as robots aren't likely to traverse overlapping or conflicting paths within their own clusters. Moreover, this method simplifies the task allocation process and robots can focus on executing their allocated tasks without the need for constant real-time collision detection and avoidance strategies. Instead, collision avoidance is naturally embedded in the initial task allocation phase through the strategic division of the operational space.

## Results and discussion

To present validate the proposed approach, a simulation scenario featuring four robots $\mathcal{R} = \{r_1, r_2, r_3, r_4\}$ was considered. Within this scenario, tasks are designated to these robots across fifty distinct sites denoted by $\mathcal{A} = \{a_1, \dots, a_{50}\}$, including the central depot $a_1$.

Clustering is employed to define specific operational zones for individual robots, relying on the Euclidean distances between various sites. Once robots are assigned to clusters, the 2-Opt algorithm is implemented separately for each robot, utilizing the clustering outputs and the calculated costs in Equation (8). The goal is to subsequently minimize the cost associated with the sequence followed by each robot within its designated cluster.

In Figure 6, the solution is visually depicted, revealing a scenario where allocation appears to be facing a free collision issue. This occurs due to the operation of robots within distinct clusters. The assumption underlying this analysis is the strategic placement of a central depot sufficiently distant from other points, which is believed to be advantageous. The mission path of each robot is represented by a dotted line, employing distinct colors for each robot, serving as a visual aid to track their individual trajectories and operational zones. The free collision issue arises primarily from the divergence of robot operations into separate clusters, potentially causing conflicts or overlaps in their paths or objectives. The strategic positioning of a central depot is crucial in mitigating these collisions, ensuring efficient and streamlined operations for each robot. This visual representation in Figure 6 allows for a clear identification of these operational zones and the potential areas of conflict, providing valuable insights into the allocation and movement strategies of the robots within the designated environment.

Figure 7 presents the evolution of the k-means algorithm during execution, illustrating how the algorithm minimizes the criterion in Equation (12) representing the overall distance between the points of each cluster and their associated centroid. It takes 8 iterations to converge to the best solution, which was relatively fast considering we deal with fifty sites. Although this number might be considered small for clustering, it's quite the opposite for our problem. This approach proves highly beneficial as it can efficiently handle a large number of tasks.
<figure><img src="image_7.png" /><figcaption>**Figure 6.** The generated allocation for each robot: Illustrating individual robots paths with dotted lines and unique colors</figcaption></figure>

Once the clustering solution is determined, each robot's cluster undergoes the 2-Opt algorithm. Figure 8 illustrates the cost function's evolution during this algorithm's execution in the simulation scenario. As the algorithm progresses, it continually alters intersections with each permutation, ultimately taking more than 160 steps to resolve all conflicting situations and arrive at the final solution. Notably, despite the overall reduction in the cost function, certain permutations temporarily increase the sequence's cost due to creating new intersection scenarios that are later resolved. In our study, permutations are executed sequentially, addressing the first one each time it appears. However, alternative strategies, such as random permutation selection or employing ascending/descending order based on swap quality, can be explored. Random selection proves effective when various permutations offer equal chances of improving the cost function, but it risks getting stuck in local minima if it doesn't explore the search space adequately. Conversely, using a hierarchy-based approach might be more efficient if some swaps consistently outperform others, yet it also carries the risk of trapping the algorithm in local optima. While these alternative strategies might impact algorithm performance and increase computational demands, the 2-Opt algorithm itself lacks a guarantee of reaching the best solution, often succumbing to local minima. Nevertheless, empirical evidence suggests that despite this limitation, 2-Opt generally outperforms constructive TSP methods, providing near-optimal solutions. Hence, it remains a promising approach for addressing multi-robot issues across various problem domains in this field.

In summary, the combination of clustering and subsequent localized optimization through 2-Opt contributes to a computationally efficient solution. The problem decomposition into clusters followed by localized routing significantly reduces the computational complexity, making this approach well-suited for real-time applications where quick decision-making and efficient resource utilization are paramount.
Table 2 presents the execution times for two optimization approaches: Genetic Algorithm (GA) with 2-Opt and k-means with 2-Opt. Various scenarios involving
<figure><img src="image_8.png" /><figcaption>**Figure 7.** The progression of the clustering optimization</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Figure 8.** The progression of the objective function during the 2-Opt procedure</figcaption></figure>

different numbers of robots and tasks were considered (see the two first columns of Table 2). Then, Column 3 details the execution time when using GA combined with 2-Opt on the whole position data set, without preliminary clustering of that set. Column 4 gives the execution time (obtained with the same PC unit) when using a priory a *k*-means clustering approach combined with the use of 2-Opt in each cluster. The results demonstrate that using a priory clustering outperforms a direct use of optimization
approach in terms of numerical complexity and paves the way for the combination of clustering and metaheuristic approaches for addressing complex MRTA problems.

<table><caption>**Table 2.** Performance analysis of task allocation strategies: GA and K-means with 2-Opt Algorithm</caption><thead><tr><td>Number of robots</td><td>Number of tasks</td><td>GA + 2-Opt execution time (s)</td><td>K-means + 2-Opt execution time (s)</td></tr></thead><tbody><tr><td>2</td><td>20</td><td>2.518</td><td>0.268</td></tr><tr><td>2</td><td>50</td><td>3.736</td><td>0.375</td></tr><tr><td>2</td><td>100</td><td>7.235</td><td>0.395</td></tr><tr><td>3</td><td>20</td><td>2.732</td><td>0.306</td></tr><tr><td>3</td><td>50</td><td>4.467</td><td>0.356</td></tr><tr><td>3</td><td>100</td><td>7.818</td><td>0.465</td></tr><tr><td>4</td><td>20</td><td>3.035</td><td>0.312</td></tr><tr><td>4</td><td>50</td><td>4.747</td><td>0.381</td></tr><tr><td>4</td><td>100</td><td>7.751</td><td>0.527</td></tr></tbody></table>

## Conclusion

This paper presents a multi-robot mission designed for inspecting industrial areas. Its primary objective is the efficient allocation of precise measurement tasks among a fleet of mobile sensing robots based on their abilities. We discussed methodologies addressing this challenge and incorporate a real-time collision avoidance system. Additionally, we explored a specific scenario involving multiple identical tasks, proposing a clustering-based strategy to manage allocation and collision avoidance by partitioning the workspace into clusters.

Multiple significant facets need addressing in terms of new directions and future challenges. Firstly, the online reconfiguration presents difficulties due to its reliance on unreliable resources and real-time components. Specifically, transitioning from standard inspection patrols to exceptional intervention ones demands attention, particularly regarding the necessity for prompt responses during events and the acquisition of new data (such as additional tasks). Moreover, it's crucial to consider temporal constraints in tasks, especially those of critical nature. Addressing issues related to distributed settings and consensus approaches is vital for enhancing complexity, particularly in scenarios involving large-scale problems. A distributed setting involves individual agents making local decisions and having partial knowledge of the environment and tasks to fulfill. Each agent must autonomously determine its optimal strategy without adversely affecting the strategies of other robots. Furthermore, energy management must be addressed both in terms of constraints and cost functions. Robots operate with finite energy reserves and must actively seek out energy stations to recharge their batteries when their charge level reaches zero.
## References

Bektas, Tolga. The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures. Omega, vol. 34, n 3, 2006, p. 209-19.

Berkhin, P. A Survey of Clustering Data Mining Techniques. Grouping Multidimensional Data: Recent Advances in Clustering, edited by Jacob Kogan et al., Springer, 2006, p. 25-71.

Beynier, Aurélie, et Abdel-Illah Mouaddib. Decentralized Markov Decision Processes for Handling Temporal and Resource Constraints in a Multiple Robot System. Distributed Autonomous Robotic Systems 6, edited by Rachid Alami et al., Springer Japan, 2007, p. 191-200.

Bhattacharjee, Preetha, et al. Multi-robot path-planning using artificial bee colony optimization algorithm. 2011 Third World Congress on Nature and Biologically Inspired Computing, 2011, p. 219-24.

Chakraa, Hamza, et al. Optimization Techniques for Multi-Robot Task Allocation Problems: Review on the State-of-the-Art. Robotics and Autonomous Systems, vol. 168, 2023a, p. 104492.

Chakraa, Hamza, et al. A Multi-Robot Mission Planner by Means of Beam Search Approach and 2-Opt Local Search. 2023 9th International Conference on Control, Decision and Information Technologies (CoDIT), IEEE, 2023b, p. 1-6.

Chakraa, Hamza, et al. A Centralized Task Allocation Algorithm for a Multi-Robot Inspection Mission With Sensing Specifications. IEEE Access, vol. 11, 2023c, p. 99935-49.

Chen, Jianping, et al. A Multi-Robot Task Allocation Method Based on Multi-Objective Optimization. 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), IEEE, 2018, p. 1868-73.

Choi, Han-Lim, et al. Consensus-Based Decentralized Auctions for Robust Task Allocation. IEEE Transactions on Robotics, vol. 25, n 4, 2009, p. 912-26.

Croes, G. A. A Method for Solving Traveling-Salesman Problems. Operations Research, vol. 6, n 6, 1958, p. 791-812.

Dang, Anh Duc, et al. Formation Control for Autonomous Robots with Collision and Obstacle Avoidance Using a Rotational and Repulsive Force-Based Approach. International Journal of Advanced Robotic Systems, vol. 16, n 3, 2019, p. 950-962.

Das, Gautham P., et al. A Distributed Task Allocation Algorithm for a Multi-Robot System in Healthcare Facilities. Journal of Intelligent Robotic Systems, vol. 80, n 1, 2015, p. 33-58.

David, Jennifer, et Thorsteinn Rögnvaldsson. Multi-Robot Routing Problem with Min-Max Objective. Robotics, vol. 10, n 4, novembre 2021, p. 122.

Dijkstra, E. W. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, vol. 1, n 1, 1959, p. 269-71.

Gam, Marwa, et al. Hybrid Filtered Beam Search Algorithm for the Optimization of Monitoring Patrols. Journal of Intelligent Robotic Systems, vol. 107, n 2, 2023, p. 26.

Gerkey, Brian P., et Maja J. Matarić. A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems. The International Journal of Robotics Research, vol. 23, n 9, 2004, p. 939-54.

Hartigan, J. A., et M. A. Wong. Algorithm AS 136: A K-Means Clustering Algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 28, n 1, 1979, p. 100-08.
Ismail, Sarah, et Liang Sun. Decentralized hungarian-based approach for fast and scalable task allocation. 2017 International Conference on Unmanned Aircraft Systems (ICUAS), IEEE, 2017, p. 23-28.

Janati, Farzam, et al. Multi-Robot Task Allocation Using Clustering Method. Robot Intelligence Technology and Applications 4, edited by Jong-Hwan Kim et al., Springer, 2017, p. 233-47.

Korsah, G. Ayorkor, et al. A Comprehensive Taxonomy for Multi-Robot Task Allocation. The International Journal of Robotics Research, vol. 32, n 12, 2013, p. 1495-512.

Li, Haodong, et al. Prioritized Planning Algorithm for Multi-Robot Collision Avoidance Based on Artificial Untr Vertex. Applied Intelligence, vol. 52, n 1, 2022, p. 429-51.

Liu, Xiao-Fang, et al. An Efficient Ant Colony System for Multi-Robot Task Allocation with Large-scale Cooperative Tasks and Precedence Constraints. 2021 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, 2021, p. 1-8.

Madridano, Ángel, et al. Trajectory Planning for Multi-Robot Systems: Methods and Applications. Expert Systems with Applications, vol. 173, 2021, p. 114660.

Miloradovic, Branko, et al. GMP: A Genetic Mission Planner for Heterogeneous Multirobot System Applications. IEEE Transactions on Cybernetics, vol. 52, n 10, 2022, p. 10627-38.

Mishra, Balmukund, et al. Drone-surveillance for search and rescue in natural disaster. Computer Communications, vol. 156, avril 2020, p. 1-10.

Nekovar, Frantisek, et al. Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection. IEEE Robotics and Automation Letters, vol. 6, n 4, 2021, p. 6196-203.

Nunes, Ernesto, et al. A Taxonomy for Task Allocation Problems with Temporal and Ordering Constraints. Robotics and Autonomous Systems, vol. 90, 2017, p. 55-70.

Parker, L. E. ALLIANCE: an architecture for fault tolerant multirobot cooperation. IEEE Transactions on Robotics and Automation, vol. 14, n 2, 1998, p. 220-40.

Petitprez, Etienne, et al. Decentralized Coordination of a Multi-UAV System for Spatial Planar Shape Formations. Sensors, vol. 23, n 23, 2023, p. 9553.

Portugal, David, et Rui P. Rocha. Multi-Robot Patrolling Algorithms: Examining Performance and Scalability. Advanced Robotics, vol. 27, n 5, 2013, p. 325-36.

Rabiner, L. Combinatorial optimization:Algorithms and complexity. IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 32, n 6, 1984, p. 1258-59.

Robusto, C. C. The Cosine-Haversine Formula. The American Mathematical Monthly, vol. 64, n 1, 1957, p. 38.

Schneider, Eric, et al. Mechanism Selection for Multi-Robot Task Allocation. Towards Autonomous Robotic Systems, edited by Yang Gao et al., Springer, 2017, p. 421-35.

Spensieri, Domenico, et al. An Iterative Approach for Collision Free Routing and Scheduling in Multirobot Stations. IEEE Transactions on Automation Science and Engineering, vol. 13, n 2, 2016, p. 950-62.

Verma, Janardan Kumar, et Virender Ranga. Multi-Robot Coordination Analysis, Taxonomy, Challenges and Future Scope. Journal of Intelligent Robotic Systems, vol. 102, n 1, 2021, p. 10.

Werger, Barry Brian, et Maja J. Mataric. Broadcast of Local Eligibility: Behavior-Based Control for Strongly Cooperative Robot Teams. Proceedings of the Fourth International Conference on Autonomous Agents, ACM, 2000, p. 21-22.
Wurman, Peter R., et al. Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses. AI Magazine, vol. 29, n 1, 2008, p. 9-9.

Ye, Fang, et al. Decentralized Task Allocation for Heterogeneous Multi-UAV System with Task Coupling Constraints. The Journal of Supercomputing, vol. 77, n 1, 2021, p. 111-32.

Zhou, Xing, et al. Balanced Connected Task Allocations for Multi-Robot Systems: An Exact Flow-Based Integer Program and an Approximate Tree-Based Genetic Algorithm. Expert Systems with Applications, vol. 116, 2019, p. 10-20.

Zitouni, Farouq, et al. A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System. IEEE Access, vol. 8, 2020, p. 27479-94.