In recent years, multi-robot systems (MRS) have garnered significant attention due to their superior efficiency and flexibility compared to single-robot systems. As a core component of MRS, task allocation and path planning are critical for applications in warehousing, rescue operations, and inspection monitoring. However, in complex environments, robots may face uncertainties such as hazardous zones that can lead to failures, challenging the system’s robustness. This paper addresses the dynamic task allocation and path planning problem for MRS under fault conditions, ensuring that tasks are completed even when robots malfunction. We propose a coupled approach that integrates task assignment and path planning, leveraging advanced robot technology to enhance system reliability and performance.
We begin by modeling the environment using a grid-based approach, where the workspace is divided into equally sized cells. Let $C = \{c_1, c_2, …, c_n\}$ represent the set of $n$ cells. Robots move horizontally between adjacent cells, with a distance of 1 unit between them. The Dijkstra algorithm is employed to precompute the shortest paths and distances between task cells, stored in matrices $L$ and $D$, respectively. This preprocessing step is essential for efficient path planning in robot technology applications.
The task requirements are specified using Boolean specifications, which describe complex tasks involving “and,” “or,” and “not” logic. Let $\Omega_t = \{\Pi_1, \Pi_2, …, \Pi_p\}$ be the set of waypoint task regions and $\Omega_f = \{\pi_1, \pi_2, …, \pi_q\}$ be the set of final task regions. Each region consists of one or more cells representing the same task. The Boolean formula $\phi$ is defined as $\phi = T \land U \land A$, where $T$ specifies the waypoint tasks, $U$ defines forbidden regions, and $A$ indicates the final tasks. For example, $T = \bigwedge_{i=1}^m t_i$ with $t_i \in P_t$, where $P_t$ is the set of atomic propositions for waypoint tasks. This formalism allows for precise task descriptions in robot technology systems.
To handle task allocation, we encode the tasks into a format that robots can execute. The encoding $Code = [C_t, C_f]$ consists of $C_t$, a vector storing waypoint task information, and $C_f$, a vector for final tasks. $C_t$ is a $(m + k)$-dimensional non-negative integer vector, where $m$ is the number of waypoint tasks and $k$ is the number of robots, with zeros indicating task boundaries. $C_f$ is a $k$-dimensional vector specifying the final task cells for each robot. Decoding this encoding yields a sequence of cells for each robot to visit, forming their trajectories. This encoding-decoding mechanism is a key aspect of robot technology for task management.
We propose an Improved Northern Goshawk Optimization (INGO) algorithm for task allocation, which enhances the original NGO algorithm with local adjustment strategies to avoid local optima. The algorithm initializes a population of $N$ individuals, each representing a task encoding. The objective function $F(X)$ minimizes the total travel distance for all robots, computed as:
$$F(X) = \sum_{i=1}^k \left( d(c_{s_i}, c_{t_{i,1}}) + \sum_{j=1}^{n_i-1} d(c_{t_{i,j}}, c_{t_{i,j+1}}) + d(c_{t_{i,n_i}}, c_{f_i}) \right)$$
where $d(c_a, c_b)$ is the precomputed distance between cells $c_a$ and $c_b$. The INGO algorithm involves two phases: identification and pursuit. In the identification phase, individuals update their positions based on the best solution:
$$x_{i,j}^{\text{new}} = x_{i,j} + r \times (b_{i,j} – I \times x_{i,j})$$
where $r$ is a random number in [0,1], $b_{i,j}$ is the value from the best individual, and $I$ is randomly 1 or 2. In the pursuit phase, a Cauchy mutation is introduced to enhance global search:
$$x_{i,j}^{\text{new}} = x_{i,j} + R \times (2r – 1) \times x_{i,j} \times \delta_i$$
where $R = 0.02 \times (1 – t/T)$ decreases over iterations, and $\delta_i$ is derived from the Cauchy distribution. Additionally, we incorporate a local adjustment strategy involving 2-opt operations and multi-point reinsertion to refine solutions. This optimization approach demonstrates the advancement in robot technology for solving complex allocation problems.
For dynamic task allocation under robot failures, we implement a fault-tolerant strategy. The central controller monitors robot states and updates the environment in real-time. If a robot enters a hazardous cell and fails, its uncompleted tasks are reassigned to other robots. Let $T_f$ be the set of failed robots, and $T_U$ be the set of unvisited task cells. The controller updates the robot set $T_s^{\text{new}} = T_s \setminus T_f$ and reassigns tasks using an auction-based method. In the auction, robots bid on tasks based on Euclidean distance, and tasks are allocated to minimize marginal cost. The marginal cost for inserting a new task $c_{\text{new}}$ into a robot’s sequence $T_i$ is computed as:
$$\Delta = \min \left\{ \cos_1 + \cos_2 – \cos_3 \right\}$$
where $\cos_1 = d(c_{t_{i,j}}, c_{\text{new}})$, $\cos_2 = d(c_{\text{new}}, c_{t_{i,j+1}})$, and $\cos_3 = d(c_{t_{i,j}}, c_{t_{i,j+1}})$. This ensures efficient reassignment with minimal impact on total travel distance. The integration of auction methods with robot technology enhances system robustness.
We validate our approach through simulations in various environments. For instance, in a fire rescue scenario with 100 cells, three robots are tasked with灭火, search and rescue, and valve closure operations. The Boolean specification is $\phi = \phi_1 \land \phi_2 \land \neg \phi_3$, where $\phi_1$ requires visiting waypoint regions for search and rescue, $\phi_2$ for灭火, and $\phi_3$ for valve closure, with a final task to reach a safe zone. The INGO-based allocation results in paths that satisfy the specification, and upon robot failure, tasks are reassigned seamlessly. The following table summarizes the performance compared to other methods:
| Method | Average Distance | CPU Time (s) | Best Case | Worst Case |
|---|---|---|---|---|
| Proposed INGO | 52.4 | 0.369 | 42 | 63 |
| NGO Algorithm | 61.0 | 0.627 | 57 | 69 |
| Auction Method | 65.2 | 0.074 | 54 | 73 |
| Genetic Algorithm | 64.2 | 0.591 | 61 | 71 |
In larger environments, such as a 900-cell map, our method maintains efficiency. The table below shows results for varying task numbers:
| Task Count | Proposed Distance | Proposed Time (s) | Auction Distance | Auction Time (s) |
|---|---|---|---|---|
| 3 | 61.1 | 0.239 | 90.0 | 0.023 |
| 6 | 119.6 | 0.334 | 157.2 | 0.063 |
| 9 | 126.0 | 0.477 | 170.3 | 0.177 |
| 15 | 182.7 | 0.691 | 236.5 | 0.223 |
| 20 | 233.2 | 0.907 | 301.0 | 0.355 |
These results demonstrate that our method balances travel distance and computation time effectively, outperforming existing approaches in scalability and robustness. The use of advanced robot technology, such as the INGO algorithm and auction-based reassignment, ensures reliable task completion even under faults.
In conclusion, we have developed a dynamic task allocation and path planning framework for MRS that incorporates fault tolerance. By combining Boolean specifications, optimized algorithms, and real-time monitoring, our approach enhances the robustness of robot technology in complex environments. Future work will address uncertainties in perception and environment dynamics to further improve applicability.