Path Planning for the Rapid Reconfiguration of a Multi-Robot Formation Using an Integrated Algorithm

Abstract

Path planning is crucial in the scheduling and motion planning of multiple robots. However, solving multi-robot path-planning problems efficiently and quickly is challenging due to their high complexity and long computational time, especially when dealing with many robots. This paper presents a unified mathematical model and algorithm for the path planning of multiple robots moving from one formation to another in an area with obstacles. The problem was initially simplified by constructing a cost matrix, and then the route planning was achieved by integrating an elite enhanced multi-population genetic algorithm and an ant colony algorithm. The performance of the proposed planning method was verified through numerical simulations in various scenarios. The findings indicate that this method exhibits high computational efficiency and yields a minimal overall path distance when addressing the path-planning problem of a multi-robot formation reconstruction. As a result, it holds promising potential for the path-planning problem of a multi-robot formation reconstruction.

1. Introduction

An effective formation transformation path-planning strategy for multi-robots in two-dimensional plane conditions can minimize the energy consumption of a single robot, which has limited energy, during motion [1,2,3]. This strategy also aims to maximize the energy reserved for other functional tasks. The problem of positioning accuracy in robots has been effectively addressed using satellite or base-station positioning technology. In the context of a mobile robot formation reconstruction with a large range and many groups, it is crucial to minimize the individual path length for each robot during the reconstruction process. Additionally, reducing the overall path-planning time for the entire group is of utmost importance.

This problem is classified as a multi-objective path-planning problem, which is a significant research topic in the field of mobile robots and currently a popular area of study [4,5,6]. It involves the mobile individual search for an optimal or suboptimal collision-free path in an environment with obstacles, based on evaluation functions such as the shortest path or the best time [7,8].

The research methods for multi-objective path planning can be categorized into precise algorithms and heuristic algorithms. However, due to the limitations of precise algorithms, they are slightly inadequate when it comes to solving large-scale complex multi-objective path-planning problems. As a result, heuristic optimization algorithms, particularly metaheuristic algorithms, have gained significant attention and are widely applied in the field of multi-objective path planning [9,10].

Based on the idea of heuristic algorithms, this article proposes the idea of integrating two metaheuristic algorithms to solve the problem and verifies the significant effectiveness of the proposed method through numerical simulation experiments under different scenarios. Compared with traditional multi-objective path planning, our main contributions in this article are as follows:

• We propose simplifying the problem by constructing a cost matrix, which changes path planning into an obstacle-free process.
• The multi-population genetic algorithm and ant colony optimization algorithm are improved through the incorporation of the elite reinforcement concept, resulting in an increased algorithm convergence rate.
• The paper presents a strategy that integrates algorithms to solve the computationally complex problem of multi-objective path planning in a simple and feasible manner, and the feasibility and effectiveness of this strategy are validated through numerical simulation experiments.

The article is structured as follows: Section 2 introduces the research related to the topic and highlights the innovation and contributions of this article. Section 3 provides a comprehensive analysis of the problem, proposes solutions, and introduces the necessary basic concepts for the method. Section 4 delves into the specific implementation steps and details of the problem-solving method. Section 5 provides an overview of the methods, techniques, and basic parameter settings used for the numerical simulation. Section 6 analyzes and discusses the results obtained from the numerical simulation. Finally, Section 7 draws conclusions and outlines future research directions.

2. Related Work

In this section, we will conduct a thorough analysis of the most recent research and work in the field of multi-robot path planning. The research proposal will be further elaborated from a technical standpoint, with a specific focus on its relevance to multi-robot path planning. Through an exploration of the existing knowledge base and a review of the pertinent research, this section aims to establish a strong groundwork for the proposed research and to foster a deeper comprehension of the topic and its implications in the realm of robot path planning.

The development of robotics technology is continually advancing, with ongoing research and development in single-robot path planning [11]. Simultaneously, research on path planning for multiple robots is also continuously evolving [12]. Currently, research methods for multi-objective path planning can be broadly classified into two categories: precise algorithms and heuristic algorithms. Precise algorithms, such as dynamic programming [13] and integer programming [14,15], face challenges in solving large-scale, complex multi-objective path-planning problems. On the other hand, heuristic optimization algorithms, particularly metaheuristic algorithms, have gained more attention and research applications [6,16,17].

Metaheuristic algorithms, such as the genetic algorithm [18,19,20], annealing algorithm [21], tabu search algorithm [22], particle swarm optimization algorithm [23], and ant colony algorithm [24,25,26], have gained popularity in recent years for solving complex problems that cannot be solved by traditional methods [27,28,29]. Consequently, many researchers have utilized these metaheuristic global optimization algorithms to address multi-objective path planning. For various environments of mobile robots and autonomous systems, researchers often utilize ant colony optimization algorithms, genetic algorithms, or a combination of both [30,31,32]. These algorithms are commonly integrated with other algorithms to optimize global path planning for a single objective.

Additionally, several researchers have explored the field of multi-objective path-planning optimization [33,34,35,36,37,38,39]. However, they have not yet provided a definitive solution to the challenge of the lengthy solving time for multi-objective path planning when dealing with many groups.

Multi-objective combined path planning is a highly intricate problem in combinatorial optimization [34,40]. As the number of individuals increases, the complexity of solving the problem escalates rapidly, making it challenging for general metaheuristic algorithms to find a solution.

This article constructs a cost matrix through the establishment of a mathematical model to transform the multi-objective-path overall planning problem into a single-objective shortest-path class-solving problem. The method includes establishing a mathematical model and constructing a cost matrix. The problem is then solved using an elite enhanced multi-population genetic algorithm and ant colony optimization algorithms [41,42,43]. This integration allows for the quick convergence and solvability of the problem. The feasibility and effectiveness of this method are verified through numerical simulation experiments.

3. Our Methods

This section provides a detailed description of the specific problems studied in this article. It then proposes corresponding solutions by analyzing the difficulties of the problem. Finally, it delves into all the concepts of the algorithms that will be used in the research.

3.1. Problem Statement

3.1.1. Conditional Assumptions

The robot discussed in this article is capable of determining its relative coordinate position using established positioning techniques in a two-dimensional plane. It can maintain communication and positioning updates with other machines and move to the specified next coordinate position based on a specific motion mode. Additionally, it can recognize other robots it encounters during its journey.

• During robots’ deployment along a path, they can implement collision avoidance measures based on their self-generated number level. This means that the robots with smaller numbers will pass first, while those with larger numbers will step back by one body position and wait for the lower-numbered robots to pass before moving. However, the overall path planning does not take into account the issue of robot collisions caused by path intersections.
• The first step is to grid the map and to expand the obstacles according to the grid. In the figure, there are two types of areas: obstacle areas and non-obstacle areas. The robot is allowed to move freely in the non-obstacle areas, but it is not allowed to enter or cross the obstacle areas in a straight line.
• In order to establish a Cartesian coordinate system for the map area, we assign the length of the map as the x-axis and the width as the y-axis. The lower left corner serves as the coordinate origin. We are aware of the initial position of the robot in this coordinate system as well as the coordinates of the deployment position for the formation transformation.

3.1.2. Problem Requirements

As depicted in Figure 1, there are obstacles in a two-dimensional plane area measuring 400 m in length and 100 m in width. The existing multi-robots are currently scattered randomly across the area, following a two-dimensional normal distribution pattern. Now, it is required to transform the formation of these multi-robots into a uniform distribution. The coordinates of the deployment point for the formation transformation are already known. The objective is to find a path-planning scheme that is both reasonable and fast, allowing the multi-robots to achieve path planning with minimal overall energy consumption and in a timely manner. It is important to note that the number of robots is equal to or greater than the number of deployment points for the formation transformation, meaning there is redundancy in the number of robots available.

3.1.3. Problem Analysis and Model Establishment

Analysis

From the perspective of computer computing time and complexity, there are three challenges in addressing the problem, based on the existing research foundation [11,34].

First, in obstacle-based group path planning, the path planning between each point and another point must take into account the presence of obstacles in the same scenario. Finding the optimal path for a single target is a computationally complex problem [4]. Therefore, it is necessary to use a suitable algorithm that can guarantee convergence, even though it may require a long calculation time. Additionally, when dealing with $N$ groups, $N^2$ secondary path-planning calculations are needed, further increasing the complexity of problem solving.

Second, when the path distance between points is known, the planned route combination for group path planning with $N$ individuals is $N!$. The complexity of computation becomes higher [34].

Finally, ordinary greedy optimization lacks a strategy calculation, making the solution of the problem highly complex. When considering the optimization algorithm, it is feasible to plan the path between two single points [25,44]. However, when it comes to multi-point path planning, calculating the path between all robots and all deployment points first before optimizing the combination of robots and deployment points significantly reduces efficiency.

Method

In response to the difficulties identified in the analysis, we have developed a systematic approach to problem solving. Our steps for problem-solving methods are as follows:

Step 1: Solving in the absence of obstacles, the group path planning can be simplified to straight lines. Only the linear distance between two points needs to be considered. To begin, we can calculate the linear distance matrix between the robot point and the deployment point. Then, we can solve the mathematical model of the problem using a meta-heuristic optimization algorithm.

Step 2: We grid the map and establish a loss function to determine if two points can reach the straight line. We will calculate the loss coefficient and transform the obstacle problem into an obstacle-free problem. We will then solve this problem using the method described in Step 1. By simplifying the calculations, we can save computational time and make problem solving simpler and more feasible.

Step 3: In this step, obstacle avoidance paths should be planned between robot points and deployment points that cannot be reached in a straight line, considering a loss coefficient that is not equal to one, as mentioned in Step 2. To reduce the amount of calculations, it is recommended to first reduce the map grid resolution and to grid the map. Subsequently, ant colony optimization algorithms can be used to perform path planning for obstacle avoidance on the grid map.

Step 4: By following Steps 1–3, a comprehensive path-planning solution can be obtained. This approach significantly reduces computational time and enhances the efficiency of path planning. The accuracy of the path-planning process is influenced by the resolution of the grid map and the parameter values chosen for calculating the loss coefficient.

3.2. Model Building

In response to the problem requirements, the path-planning results minimize the energy consumption of the robot on the path; that is, the total distance of the overall path planning is the shortest. Therefore, a mathematical model is established as follows:

$$\begin{gathered} \mathit{min}f=\sum _{i=1}^{nz}{\gamma }_{ij} \left(i\in \left\{1\dots nz\right\},j\in \left\{1\dots nd\right\}\right) \\ s.t. for {\gamma }_{nm}and {\gamma }_{pq} , m\ne q while n\ne p . \\ \left(n,p\in \left\{1\dots nz\right\}, m,q\in \left\{1\dots nd\right\}\right) \end{gathered}$$

(1)

$${\gamma }_{ij}=d_{ij}\ast {\delta }_{ij} \left(i\in \left\{1\dots nz\right\},j\in \left\{1\dots nd\right\}\right)$$

(2)

$$d_{ij}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2} \left(i\in \left\{1\dots nz\right\},j\in \left\{1\dots nd\right\}\right)$$

(3)

$$s.t. nz\le nd$$

(4)

In Equation (1), $f$ represents the minimum cost of the overall path planning, $i$ represents the $i$-th deployment point,$j$ represents the $j$-th robot, and ${\gamma }_{ij}$ represents the cost from the $i$-th deployment coordinate point to the $j$-th robot. In Equation (1), for ${\gamma }_{nm}$ and ${\gamma }_{pq}$, if $n$ and $q$ in their subscripts are not equal, then $m$ and $q$ are also not equal. Equation (1) means that each robot corresponds to only one coordinate position, and the robot positions corresponding to different robots are also different. The equation seeks the minimum value of the sum of the costs of these robots and their corresponding positions.

In algorithm research, this problem is known as minimum matching in weighted bipartite graphs, and there exists an algorithm that solves it in $n^3$ steps in the worst case, where n denotes the number of locations; see [45]. However, this algorithm is quite involved. Therefore, in this paper, we shall present a heuristic solution based on a genetic algorithm. This type of approach has been successfully employed, even on NP-hard problems like the traveling salesperson problem [46].

In Equation (2), $d_{ij}$ represents the linear distance from the $i$-th deployment coordinate point to the $j$-th robot without considering obstacles, and ${\delta }_{ij}$ represents the loss coefficient from the $i$-th deployment coordinate point to the $j$-th robot. In Equation (3), $x_i,y_i$ represents the deployment point coordinates, and $x_j, y_j$ represents the robot point coordinates. In Formulas (1)–(4), $nz$ represents the number of deployment points, and $nd$ represents the number of robots.

3.3. Algorithm Description

This section provides a detailed introduction to the basic concepts of the genetic algorithm and the ant-colony optimization algorithm used in this method.

3.3.1. Genetic Algorithm and Improvement Description

The genetic algorithm is a global optimization search algorithm that mimics the natural biological evolution mechanism of “natural selection, survival of the fittest”. It was first proposed by John H. Holland [42]. Unlike other optimization processes that rely on gradients, this algorithm exhibits strong robustness and global optimization ability [18]. The problem discussed in the article is transformed into a permutation combination based on a cost distance. Therefore, it is highly suitable to utilize this algorithm for finding the optimal value of such permutation combinations.

Single-Population Genetic Algorithm

The single-population genetic algorithm is the most fundamental genetic algorithm [18]. Figure 2 illustrates the basic execution process of the single-population genetic algorithm for the objective function described in Equation (1).

The specific steps of the algorithm are explained as follows:

Step 1: Objective function construction. The equation for the objective function is:

$$\min f\left(q\right)=\sum _i^n{\gamma }_{ij} \left(i=1\dots n,j=1\dots nd\right)$$

(5)

In Equation (5), $f\left(q\right)$ represents the objective function value of the $q$-th individual.

Step 2: To initialize the population, we set the cumulative number of evolution iterations, denoted as $t$, to zero. The maximum number of iterations was set to $T$. $P\left(t\right)$ represents the population at $t$ iterations, and $M$ denotes the population number. The expression for calculating $P\left(t\right)$ is as follows:

$$P\left(t\right)=\left\{q\left|q\left(k\right)=a_1{a}_2\cdots a_n,k=\mathrm{1,2},\cdots M\right.\right\}$$

(6)

In Equation (6), the individual $q\left(k\right)$ represents the $k$-th individual when the population $P$ evolves into the $t$-th generation population. The chromosome code of this individual is $a_1{a}_2\cdots a_n$, where $a$ is the real number code $a\in \left\{\mathrm{1,2},\cdots nd\right\}$. The real number code is a mapping from the position of each robot to the location of the deployment point.

Step 3: Individual fitness evaluation. The fitness value of each individual is calculated to assess their strengths and weaknesses. The individuals are then screened using the principle of “survival of the fittest”. The equation is:

$$fitness(q_k)=\frac{1}{f\left(q_k\right)}$$

(7)

Step 4: Select operation. The parent generation for the next generation genetic process is selected based on the fitness value of the individual. This selection is carried out using the roulette method, as illustrated in Figure 3. The parent generation undergoes crossover and mutation to generate the next generation population.

$$p\left(q_k\right)=\frac{fitness\left(q_k\right)}{{\sum }_{k=1}^{M}fitness\left(q_k\right)}$$

(8)

$$Q(q_k)=\sum _{k=1}^{M}p\left(q_k\right)$$

(9)

In Equation (8), $p\left(q_k\right)$ represents the probability of selecting an individual $q_k$, which is determined by the proportion of its fitness value in the population. Equation (9) defines $Q\left(q_k\right)$ as the cumulative probability of the individual $q_k$. The roulette selection method assigns a higher probability of selection to individuals with greater fitness values.

Step 5: Cross operation. The crossover operator simulates the crossover recombination of human chromosomes, inherits the excellent individual characteristics of the parent to the next generation, and eliminates the individual characteristics of poor quality so that the calculation of the algorithm converges with the genetic iteration.

Step 6: Mutation operation. The main source of maintaining individual diversity in the population is the mutation of some individual features, which expands the calculation results of the algorithm toward global optimization.

Step 7: The parent population $P\left(t\right)$ obtains the offspring population $P\left(t+1\right)$ through selection, crossover, and mutation operations.

Step 8: Termination condition judgment. If $t=T$, the operation terminates and outputs the chromosome encoding of the individual with the highest fitness value, which is then decoded as the optimal solution. Otherwise, a round of iteration cycles is entered.

Multi-Population Genetic Algorithm

With the practice and development of the genetic algorithm theory, the multi-population genetic algorithm was proposed and applied. This gradually replaced the traditional single-population genetic algorithm with its fast convergence and global optimization characteristics [19]. Compared with those of a single-population genetic algorithm, the steps of a multi-population genetic algorithm are as follows:

Step 1: Introduce multiple populations, set different control parameters for different populations, and perform optimization search at the same time to achieve individual diversification and to strengthen the global optimization characteristics of the algorithm.

Step 2: During the evolution of each population, some elite individuals with large fitness values are retained, and elite enhanced immigration operations are performed among multiple populations, realizing the collaborative optimization of different populations and accelerating the convergence of the algorithm.

Step 3: Through the selection operation, the optimal individual of each iteration in each group is retained. When the iteration condition is satisfied and the algorithm terminates, the overall optimal individual is obtained by selecting the best among the retained individuals. The basic flow of the implementation of the multi-population genetic algorithm is shown in Figure 4.

3.3.2. Grid-Based Ant Colony Algorithm

The ant colony algorithm imitates the path information of ants by leaving pheromones in the process of foraging. The ant colony selects the path by sensing the concentration of pheromones on the path. Under the update mechanism, a better path for foraging is finally found [24]. After practice and development, the grid-based ant colony path planning is applied in this paper, and the path planning for crossing obstacles can quickly converge and obtain a better solution.

Environment Establishment Based on the Grid Method

Using the grid method to build an environmental map can effectively imitate the local characteristics of the environment. This method has the following two rules:

First, the expansion processing of obstacles involves treating any grid that is touched by an obstacle as an obstacle. This simplifies the determination of whether an object encounters an obstacle, as shown in Figure 5.

Second, the object can only move freely between the center line of the grid without obstacles, and the size of the grid is determined according to the size of the moving object and the actual application accuracy requirements.

Ant Colony Algorithm and Its Improvement

The specific steps of the algorithm are explained as follows:

Step 1: Ant movement rules. In the direction that the ants are seeking, select adjacent grids with no obstacles in each grid, including top, top right, right, bottom, bottom right, bottom left, right, and top right, in which to move, as shown in Figure 6.

Step 2: Tabu list establishment. A tabu list is created for each ant to record the obstacle information and the nodes that have been visited. This ensures that the ants avoid obstacles and do not repeat routes when selecting the direction to move in. Consequently, the algorithm ensures feasibility and convergence. Nodes that are not in the tabu list are free to be chosen.

Step 3: Selection operation. According to Equation (8), the next free node is selected for the current node, and the next direction of movement is determined using a roulette selection method based on the information concentration of the path and the transfer probability generated by the heuristic information. The generation of transition probability ensures that the algorithm is able to generate feasible solutions and converge. Moreover, the selection based on random generation probability introduces diversity in the algorithm solutions, thereby promoting global optimization.

Step 4: Pheromone update. When all ants finish moving, calculate the path length of each ant reaching the target point, and update the pheromone according to Equations (10) and (11).

Step 5: Elite enhancement operation. Among the ants that reach the target point, the three ants with the shortest path are selected. The shortest path in this round is saved, and the path pheromones of these ants are updated again. This process strengthens the optimal solution of each round of iteration and accelerates the convergence of the algorithm.

Step 6: When the iteration meets the conditions, execution terminates. Otherwise, repeat Steps 2 to 5 until the termination conditions are met.

Step 7: After each iteration, select the shortest path among the reserved paths. Output the coordinates of the starting point, the center point coordinates of the grid that the path passes through, and the target point coordinates.

$$p_{ik}^m\left(t\right)=\left\{\begin{array}{cc}\frac{{\left[\tau \left(t\right)\right]}^{\alpha }{\left[{\eta }_k\left(t\right)\right]}^{\beta }}{{\sum }_{S\subset allowe{d}_m}{\left[{\tau }_{ik}\left(t\right)\right]}^{\alpha }{\left[{\eta }_k\left(t\right)\right]}^{\beta }},\hfill & \hfill k=allowe{d}_m;\\ 0,\hfill & \hfill otherwise.\end{array}\right.$$

(10)

In Equation (10), $P_{ik}^m\left(t\right)$ represents the transfer probability of ant $m$ from node $i$ to node $k$ at time $t$; $\tau \left(t\right)$ represents the amount of pheromone in the link from node $i$ to node $k$ at time $t$; ${\eta }_k\left(t\right)$ represents the heuristic information value of ant $m$ from node $i$ to node $k$; $\alpha$ represents the information heuristic factor; $\beta$ represents the heuristic factor; and $allowe{d}_{m }$ represents the set of nodes that ant $m$ is allowed to select in the next step.

$${\eta }_j(t)=\left\{\begin{array}{l}\frac{1}{\sqrt{(x_j-x_E{)}^2+(y_j-y_E{)}^2}}, j\ne E;\\ 100, j=E.\end{array}\right.$$

(11)

In Equation (11), ${\eta }_j\left(t\right)$ represents the heuristic information from node $j$ to target node $E$ when the ant is at node $i$ at time $t$. The heuristic information value provides guidance for the ant to choose a path towards the target point. $(x_j,y_j)$ is the coordinate of node $k$, and $\left(x_E,y_E\right)$ is the coordinate of node $E$, where if $j=E$, ${\eta }_j\left(t\right)$ is set to a constant of 100.

Step 8: Pheromone updating and elite strengthening for the shortest path.

$${\tau }_{ik}\left(t+1\right)=\left(1-\rho \right){\tau }_{ik}\left(t\right)+\Delta {\tau }_{ik}\left(t\right)$$

(12)

$$\Delta {\tau }_{ik}^m\left(t\right)=\left\{\begin{array}{c}\frac{Q}{L^t\left(m\right)},(m\in N)\\ 0.\end{array}\right.$$

(13)

$$\Delta {\tau }_{ik}\left(t\right)=\sum _{m=1}^M\Delta {\tau }_{ik}^m\left(t\right)$$

(14)

$$\Delta {\tau }_{ik}\left(t\right)=\sum _{rank=1}^3\Delta {\tau }_{ik}^{rank}\left(t\right)+\Delta {\tau }_{ik}\left(t\right)$$

(15)

In Equation (12), $\rho$ represents the volatilization coefficient of the pheromone, $\rho \in \left(0,1\right)$; $\mathsf{\Delta }{\tau }_{ik}\left(t\right)$ represents the amount of pheromone left by $m$ ants on the path from node $i$ to node $j$ after an iteration. In Equation (13), $\mathsf{\Delta }{\tau }_{ik}^m\left(t\right)$ represents the amount of pheromone left by ant $m$ on the path section from node $i$ to node $j$. $L^t\left(m\right)$ represents the total length of ant $m$’s path from starting point $S$ to ending point $G$, and $Q$ represents the pheromone constant. In Equation (15), $rank\in (\mathrm{1,2},3)$ represents the ants whose fitness value ranks in the top three in the current iteration and increases the pheromone value on the shortest path by elite reinforcement to accelerate the convergence of the algorithm.

The flowchart of the ant colony optimization algorithm is shown in Figure 7.

4. Solving the Problem

This section will elaborate on the specific implementation steps and details of the problem-solving method. The solution to the problem is divided into three steps: solving the coefficient matrix, improving and applying the multi-population genetic algorithm, and improving and applying the ant colony algorithm.

4.1. Calculate the Cost Coefficient Matrix

Problem solving is achieved through algorithm integration, where the coefficient matrix serves as a bridge between algorithms. First, the problem is transformed from path planning, considering the presence of obstacles to simplify the problem without considering obstacles. The specific steps for the coefficient matrix are as follows:

Step 1: Grid the map while also expanding obstacles, as shown in Figure 8.

Step 2: Based on the grid map, use Equation (3) to calculate the straight-line distance $d_{ij}$.

Step 3: As shown in Figure 9, the loss function is established by determining whether two points can reach the straight line, and the loss coefficient is calculated by using Equation (2) to transform the problems with obstacles into problems without obstacles.

The loss function equation is:

$${\delta }_{ij}=\frac{N_{ij}^{ob}}{N_{ij}^{gr}}+1$$

(16)

In Equation (16), $N_{ij}^{ob}$ represents the number of obstacle grids that a straight line passes through when connecting node $i$ to node $j$ at two points, and $N_{ij}^{gr}$ represents the total number of grids that a straight line passes through when connecting node $i$ to node $j$ at two points.

4.2. An Improved Genetic Algorithm Based on Elite Reinforcement and Its Application

Based on the cost coefficient matrix, the path-planning problem is transformed into a permutation and combination problem based on the distance matrix. Here, the improved genetic algorithm is used to establish the mapping from the problem to the solution space to solve the optimal arrangement and combination. The specific steps are as follows:

Step 1: Real-number genetic coding. The deployment coordinate points are numbered from one to $nz$, and the robot coordinates are numbered from one to $nd$. From the $nd$ numbers, $nz$ nonrepetitive numbers are selected and used for real-number genetic coding. The real number $j$ at the position of gene $i$ represents the $j$-th robot’s selection of the $i$-th deployment coordinate point.

Step 2: Establishment of a tabu list. For each real-numbered gene code, $nd$ robots are coded, the selected tabu list is marked as one, and the tabu list that is not selected is marked as zero.

Step 3: Initialization of the population. Set the initial population number as $M$, and the individual number of each population as $N$, where $N$ uses an even number for the convenience of the genetic operation. Each individual is a real-number genetic code. If it is not the first population, the last five individuals of this population will be replaced by the last five elite individuals retained last time, that is, the elite migration operation. The mutation probability $P_m$ is defined to balance the global search ability and the local search ability of the crossover and mutation algorithm.

$$P_m=0.05+(0.1-0.05)\ast rand(N,1)$$

(17)

The value range of $P_m$ is 0.05~0.1. According to Equation (17), each population randomly selects a value within this range.

Step 4: Calculation of the fitness value. Decode the individual, and use Equation (8) to calculate the fitness value of the individual. Sort the individuals based on the size of their fitness value and record the corresponding path.

Step 5: Individual selection. The sorted individuals are extracted according to the roulette method. Two individuals are selected for pairing each time, and a total of $0.5 \mathrm{*} N$ pairs are selected.

Step 6: Cross operation. As illustrated in Figure 10, the cross operation involves randomly selecting 20% of the points from one of the paired individuals and exchanging them with the genes at the corresponding points of the other individual. After the exchange, each individual will have duplicated gene points at the exchange points. The exchange points themselves are not listed, and the non-exchanged part is sequentially replaced with the original values of the replaced points.

Step 7: Mutation operation. As depicted in Figure 11, the randomly generated value is compared with the $P_m$ to determine if the point should be mutated. If it is determined that mutation should occur, two points are randomly selected as the mutated points. The individual’s tabu list is then updated, and two values are randomly chosen from the tabu list and added to the mutated points.

Step 8: Calculate the fitness value of the individual after operation, select the three individuals with the largest fitness value, update the elite individual record, record the genetic optimal individual this time, and update the global optimal individual.

Step 9: Repeat Steps 3–8 until the number of iterations reaches the maximum, and then enter the next population operation. If the population is exceeded, the operation is terminated, the globally optimal genetic individual is decoded, and the optimal combination mode is output. The pseudocode of the solution process is shown in Algorithm 1.

Algorithm 1. Improved Genetic Algorithm
Input: population number $M$, individual number of each population $N,$ iteration $T$ Output: optimal individual $GlobalBest$
1	while $m\in M$//Iteration
2		Initialize $P\left(0\right)$,$Tabu\left(0\right)$,$t$ = 0//Initialize variable
3		if $t$ = 0
4			for each $i\in (\mathrm{1,2},\mathrm{3,4},5)$
5				$P(t,N+2-i)=Elite\left(i\right)$//Elite immigration operation
6		while $t\in T$//Iteration
7			for each $i\in N$
8				Evaluate fitness to $P\left(t\right)$//Calculate fitness value
9			$P\left(t\right)$ = Sort ($P\left(t\right)$)//Sort by fitness value
10			for each $i\in N$
11				Select operation to $P\left(t\right)$//Individual selection
12			for each $i\in N$
13				Crossover operation to $P\left(t\right)$//Cross operation
14			for each $i\in N$
15				if rand < $P_m$
16					Mutation operation to $P\left(t\right)$//Mutation operation
17			for each $i\in N$
18				$P\left(t+1\right)=P\left(t\right)$
19				$S\mathrm{ave}Best\left(m\right)=P(t,1)$  //Update reserved values
20		for each $i\in N$
21			Evaluate fitness to $P\left(T\right)$//Calculate fitness value
22		$P\left(T\right)$ = Sort ($P\left(T\right)$)//Sort by fitness value
23		for each $i\in (\mathrm{1,2},3,4,5)$
24			$Elite\left(i\right)=P\left(T,i\right)$//Retain elite
25	Choose the smallest $GlobalBest$. from $SaveBest$

4.3. Improved Ant Colony Algorithm and Its Application

For the optimized permutation and combination based on the distance matrix that has been solved, for the path that cannot be reached by the actual straight line due to the existence of obstacles, the improved ant colony algorithm is used to solve the path planning. The specific steps are as follows:

Step 1. In order to reduce the amount of computation and reduce the resolution of the map, the grid map is re-established and expanded again for obstacles.

Step 2. Decode the optimal solution solved in Section 4.2 and screen out the two points that the robot cannot reach along a straight line from the deployment coordinate point.

Step 3. Use the ant colony algorithm to plan the path to avoid obstacles for the two points in Step 2 that cannot be reached by a straight line between the individual and the deployment coordinate point, that is, the two points with a loss coefficient of not 1.

Step 4. To initialize the algorithm, we define the start point $S$ as the grid where the $j$-th robot is located, and the end point $G$ as the grid where the $i$-th deployment point is located. Assuming that the number of ants in each iteration is $N$, the number of iterations is $ITE$. We convert the coordinate points into the corresponding grid numbers and establish a connectivity matrix between the grids. The connectivity matrix takes into account the eight directions of ant colony movement and whether there are obstacles in the grid. If it is not possible to reach a grid in one step or if it is not a valid option, the assignment value is set to 0. On the other hand, if a grid can be reached in one step, the assignment value is set as the distance between the center points of the two grids.

Step 5. Put $N$ ants on the starting point $S$, initialize the tabu list, calculate the heuristic information value ${\eta }_j$ of neighborhood nodes by Equation (11) according to the movement rules, and calculate the transition probability $P_{ik}$ of neighborhood nodes by Equation (10).

Step 6. Randomly generate $w$, determine the transition probability by roulette, select the grid the ant will reach next, and update the tabu list.

Step 7. When all ants complete the path search, that is, when the ants in an iteration move to the target point or when some ants cannot continue to move, select the shortest three paths as the elite path, save the shortest path information, and update the pheromone value according to Equations (10) and (11).

Step 8. Repeat Steps 4–7; when the number of iterations of the algorithm reaches the maximum $ITE$, the optimal path sequence is converted to the coordinate output.

Step 9. Repeat Steps 3–8 until all two points that cannot be reached in a straight line between the individual and the deployment coordinate point have calculated the obstacle avoidance path, at which point the algorithm ends. The pseudocode of the solution process is shown in Algorithm 2.

Algorithm 2 Improved Ant Colony Algorithm
Input: number of robots $nz$, number of deployment points $nd$, iteration $ITE$, start point $S$, end point $G$. Output: optimal path $Tbest$
1	for each $i\in nz,j\in nd$
2		Initialize ${\tau }_{ij}\left(0\right)={\tau }_0$, $H_{ij}\left(0\right)$, ${\eta }_j$//Initialize variable
3	for each $t\in ITE$
4		for each $k\in N$
5			$T^k(t,1)=S$;${\tau }_{ij}\left(k\right)={\tau }_{ij}\left(0\right)$//Initialize the pheromone concentration of the route
6			for each $j\in nd$
7				$Tabu(t,j)=1$;$H_{ij}\left(k\right)=H_{ij}\left(0\right)$//Initialize tabu list and connected matrix
8			while $T^k(t,end)\ne G$
9				$u=1$;$Set=\left[\right]$
10				for each $j\in nd$
11					if $Tabu(t,j)=1$ and $H_{uj}\left(k\right)=1$ $\left(u\in n\right)$
12					$Set=[Set,j]$
13				if $Set\ne \left[\right]$
14					Rand $w$ Choose $j(j\in Set)$ by $P_{uj}$//Select the next node
15					$T^k(t,u)=j$; $Tabu(t,j)=0$; $H_{uj}\left(k\right)=0$; $H_{ju}\left(k\right)=0$; $u=u+1$//Add node
16				else
17					break
18		for each $k\in N$
19			if $T^k\left(t,end\right)=G$
20				Calculate $L^t\left(k\right)(k\in N)$ by $T\left(t\right)$
21		Choose the shortest $Tellite\left(t\right)$ from $T\left(t\right)$//Select and record elite routes
22		for each $i\in nz,j\in nd$
23			Update ${\tau }_{ij}\left(t\right)$ by $L^t\left(k\right)(k\in N)$ and $T\left(t\right)$//Update pheromone on path
24		for each $i\in nz,j\in nd$
25			Update ${\tau }_{ij}\left(t\right)$ by $Tellite\left(t\right)$ and $T\left(t\right)$//Updaoute
26	Choose the shortest $Tbest$ from $Tellite\left(t\right)$

5. Numerical Simulation

In order to verify the effectiveness of the model and algorithm in this paper, the performance of the algorithm was analyzed through simulation experiments. The numerical simulation experiment was conducted on a Windows 10 (64-bit) operating environment with an Intel(R) Core (TM) i7-7700HQ processor running at 2.80 GHz and 8.00 GB of memory. The simulation platform used for the experiment was MATLAB R2022a.

5.1. Experimental Setup

To assess the efficiency of the algorithm proposed in this paper for solving multi-robot formation-reconstruction path planning, three scenario maps were created. These maps had the same dimensions (400 m in length and 100 m in width) but differed in terms of the obstacles present. The different obstacle configurations are illustrated in Figure 12.

At the same time, in order to verify the robustness of the algorithm in this paper, three groups with different numbers of robots and deployment points are set for each scenario, as shown in

Table 1. The number of robots and the number of deployment points in the three groups.

Type	$\mathbf{Number} \mathbf{of} \mathbf{Deployment} \mathbf{Points} \mathit{n}\mathit{z}$	$\mathbf{Number} \mathbf{of} \mathbf{Robots} \mathit{n}\mathit{d}$
1	26	29
2	36	39
3	46	50

. The position coordinates of each group of robots are randomly distributed, and the coordinates of the deployment points are uniformly distributed. The number of robots in each group $nd$ is greater than the number of deployed points $nz$, that is, the number of robots is redundant.

By combining the literature and experience [10,15], the parameter settings of the multi-population genetic algorithm and the ant colony algorithm are shown in

Table 2. Parameter setting of the multi-population genetic algorithm.

$\mathbf{Number} \mathbf{of} \mathbf{Populations} \mathit{M}$	Number of Individuals in Each Population $\mathit{N}$	$\mathbf{Number} \mathbf{of} \mathbf{Generations} \mathit{T}$
15	50	1000

and

Table 3. Parameter setting of the ant colony algorithm.

$\mathbf{Iteration} \mathit{I}\mathit{T}\mathit{E}$	$\mathbf{Number} \mathbf{of} \mathbf{Ants} \mathit{N}$	$\mathbf{Information} \mathbf{Heuristic} \mathbf{Factor} \mathit{\alpha }$	$\mathbf{Expected} \mathbf{Heuristic} \mathbf{Factor} \mathit{\beta }$	$\mathbf{Pheromone} \mathbf{Volatilization} \mathbf{Coefficient} \mathit{\rho }$	$\mathbf{Pheromone} \mathbf{Constant} \mathit{Q}$
30	100	1	7	0.3	1

, respectively.

The specific meaning of Table 2 is that, according to the improved multi-population genetic algorithm proposed in this paper, the parameters in the experiment process are set as follows: there are 15 populations with 50 individuals in each population, and the number of genetic iterations for each population is 1000.

The specific meaning of Table 3 is that according to the improved ant colony algorithm proposed in this paper, the parameters of the experimental process are set as follows: the number of iterations of the algorithm is 30, there are 100 individuals in each iteration, the information heuristic factor is constant at 1, the expected heuristic factor is constant at 7, the pheromone volatilization coefficient is 0.3, and the pheromone constant is 1.

5.2. Grouping and Recording

In order to reflect the efficiency of the algorithm in this paper, the numerical simulation set up a control group and an experimental group. The total calculation time and average distance of the two groups of simulation results were counted and calculated. The details are as follows:

Control group: Using the three scenarios and the three different data conditions set up in the experiment, the control group first uses the ant colony algorithm to solve the path planning of all robots to all deployment points and obtains the corresponding distance matrix. Then, according to the distance matrix, the multi-population genetic algorithm is used to solve the overall optimal path planning. The total calculation time $T_C$ (unit: s) and the average path distance $L_C$ (unit: m) are recorded for solving the path planning.

Experimental group: Under the same experimental conditions as the control group, using the algorithm idea in the paper, first calculate the cost matrix; then, use the multi-population genetic algorithm to solve the overall planning of all robots to all deployment points; finally, use the ant colony algorithm to solve the nonlinearly reachable path-planning solution between two points. In addition, record the total calculation time $T_E$ (unit: s) and the average path distance $L_E$ (unit: m) for solving the path planning.

For the above experiments, use Equations (18) and (19) to calculate the time reduction percentage ${\eta }_T$ and the average distance loss percentage ${\mu }_L$.

$${\eta }_T=\left(1-\frac{T_E}{T_C}\right)\ast 100$$

(18)

$${\mu }_L=\left(\frac{L_E}{L_C}-1\right)\ast 100$$

(19)

6. Results and Discussion

Experiments were conducted for the experimental setup. The path-planning results for the three scenarios and the three groups of different number of formation changes are shown in the following figures, and the calculated data results are shown in a table.

6.1. Image Results of Path Planning and Its Discussion

Figure 13, Figure 14 and Figure 15 display the number of three different robots and the number of deployment points under the map conditions of scenario 1. In Figure 13, $nz$ = 26, and $nd$ = 29; in Figure 14, $nz$ = 36, and $nd$ = 39; and in Figure 15, $nz$ = 46, and $nd$ = 50. Each graph consists of two subgraphs: “a” represents the experimental group path planning calculated using the algorithm proposed in this paper, and “b” represents the control group path planning calculated using the control group setting method. The green plus sign indicates the initial position of the robot people, the red circle represents the deployment position, the blue curve represents the planned curve path, and the magenta straight line represents the planned linear path.

As can be seen from Figure 13, Figure 14 and Figure 15, the number of straight lines is far greater than that of curves in both the control group and the experimental group. This phenomenon shows that when planning the path of multi-robot formation reorganization, first consider straight-line planning, which is conducive to saving calculation time and is consistent with the idea of the algorithm in this paper. In addition, it is worth noting that the number of blue curves in the control group is slightly more than that in the experimental group in each figure, which shows that the path-planning results of the control group are more complex and the calculation accuracy is higher, but with an increase in the number of robots and the number of deployment points, this advantage becomes smaller.

Figure 16, Figure 17, Figure 18, Figure 19, Figure 20 and Figure 21 display the three different numbers of robots and deployment points under the map conditions of scenario 1 and scenario 2. In Figure 16 and Figure 19, $nz$ = 26, and $nd$ = 29; in Figure 17 and Figure 20, $nz$ = 36, and $nd$ = 39; and in Figure 18 and Figure 21, $nz$ = 46, and $nd$ = 50. In the same way, each graph consists of two subgraphs: “a” represents the experimental group path planning calculated using the algorithm proposed in this paper, and “b” represents the control group path planning calculated using the control group setting method. The green plus sign indicates the initial position of the robot people, the red circle represents the deployment position, the blue curve represents the planned curve path, and the magenta straight line represents the planned linear path.

Figure 16, Figure 17, Figure 18, Figure 19, Figure 20 and Figure 21 are the results of calculation under the assumption of an obstacle environment in scenario 2 and scenario 3, where the area of a single obstacle in scenario 2 is increased relative to scenario 1, while the area of a single obstacle in scenario 3 is opposite to that in scenario 1; that is, the area of a single obstacle is reduced. As can be seen from Figure 16, Figure 17, Figure 18, Figure 19, Figure 20 and Figure 21, the number of straight lines is far greater than that of curves in both the control group and the experimental group. This phenomenon further confirmed that when reorganizing the path planning for multi-robot formation, the line planning should be considered first, which is conducive to saving calculation time and consistent with the idea of the algorithm in this paper.

In addition, it is worth noting that, apart from the number of blue curves in the control group in each figure being slightly more than that in the experimental group, the number of blue curves in the control group in Figure 20 is 15, which is significantly more than the 6 in the experimental group. This phenomenon shows that when the area of a single obstacle in the scene is smaller, the path-planning results of the control group are more complex. In this case, the computational efficiency of the experimental group has obvious advantages.

In Figure 13, Figure 14, Figure 15, Figure 16, Figure 17, Figure 18, Figure 19, Figure 20 and Figure 21, from the comparative analysis of the left and right subgraphs of each group of graphs, it can be seen that the two methods have achieved a better effect in overall path planning. For each group of path-planning results, the results of the two experimental methods are observed visually, and it is found that they are not much different.

6.2. Data Results of Path Planning and Its Discussion

To further compare and analyze the experimental results, the data summary results of the experimental results are shown in

Table 4. Numerical simulation results under different conditions.

Scenario	$\mathit{n}\mathit{d}$	$\mathit{n}\mathit{z}$	${\mathit{T}}_{\mathit{E}}$ (s)	${\mathit{T}}_{\mathit{C}}$ (s)	${\mathit{\eta }}_{\mathit{T}}$ (%)	${\mathit{L}}_{\mathit{E}}$ (m)	${\mathit{L}}_{\mathit{C}}$ (m)	${\mathit{\mu }}_{\mathit{L}}$ (%)
1	26	29	157.87	10,411.32	98.48	82.02	76.76	6.86
	36	39	146.22	18,084.22	99.19	53.99	48.46	11.41
	46	50	180.62	48,507.11	99.63	72.12	71.83	0.41
2	26	29	99.27	10,883.12	99.09	48.42	44.42	8.99
	36	39	89.16	17,526.31	99.49	38.17	32.93	15.91
	46	50	141.45	30,387.53	99.53	37.98	36.47	4.16
3	26	29	100.32	7728.4	98.70	43.12	39.64	8.79
	36	39	134.15	16,490.06	99.19	49.82	48.22	3.34
	46	50	146.56	24,878.76	99.41	51.6	50.76	1.66

. Columns 3 and 4 in Table 4 show the total time $T_E,T_C$ used for the calculations recorded in the experiment, and columns 6 and 7 show the average distance $L_E,L_C$ of the path-planning results recorded in the experiment. Columns 5 and 8 in Table 4 are the percentage of time reduction ${\eta }_T$ and the percentage of distance loss ${\mu }_L$, which are bold in both columns.

By analyzing Table 4, it can be clearly seen that, under nine different conditions, the total time $T_E$ calculated for the experimental group is far less than the total time $T_C$ calculated for the control group, and the time reduction percentage ${\eta }_T$ is maintained at more than 98.48%, with high robustness. From the perspective of the average distance loss ratio ${\mu }_L$, the control group is better than the experimental group, but the average distance loss percentage ${\mu }_L$ is generally controlled below 15.91%. When the number of $nz$ and $nd$ is large, the distance loss is significantly reduced compared with ${\mu }_L$ and remains within 5%.

In order to further verify the advantages of the algorithm in this paper in calculating the total time, the total calculation time in the experimental results is counted, and the time reduction percentage ${\eta }_T$ is calculated by using Equation (18), forming the line chart shown in Figure 22.

Figure 22 is a line chart of the time reduction percentage ${\eta }_T$. In the figure, the blue area on the left represents this percentage under the conditions of scenario 1, the yellow area in the middle represents this percentage under the conditions of scenario 2, and the gray area on the right represents this percentage under the conditions of scenario 3. The $nz \mathrm{a}\mathrm{n}\mathrm{d} nd$ values of each scene are 26 and 29, 36 and 39, and 46 and 50, respectively.

As can be seen from Figure 22, for a single scenario, the percentage of time reduction increases with the increase in the number of, with a minimum value of 98.48% and a maximum value of 99.63%. Through the analysis of the number, it can be seen that the computational efficiency of the algorithm proposed in this paper is much higher than that of the control group.

In order to further verify the effect of the algorithm in this paper on the average distance of multi-robot path planning, the average distance of path planning in the numerical simulation results is counted, and the average distance loss percentage ${\mu }_L$ is calculated using Equation (19), forming the histogram shown in Figure 23.

In Figure 23, the blue and orange columns show the comparison of the average distances $L_E$ and $L_C$ of path planning under nine different conditions. The yellow line chart shows the change trend of the average distance loss percentage ${ \mu }_L$ with the increase in the average distance of path planning.

In Figure 23, the height of the blue and orange histogram increases from left to right, and the yellow line chart decreases from left to right, with a maximum ${\mu }_L$ of 15.91% and a minimum ${\mu }_L$ of 0.41%. It can be concluded that the average distance of path planning obtained from the two experiments is similar, and that ${\mu }_L$ decreases with the increase in the average distance; that is, when the average distance of planning is large, the algorithm proposed in this paper can quickly calculate the results, and the calculation results are better.

Similarly, it must be noted that ${\mu }_L$ = 11.41% at the ninth group histogram in Figure 23. At this time, the ${\mu }_L$ value does not increase with the overall trend. Analysis reason: The corresponding path-planning result is shown in Figure 14. Comparing the left and right subgraphs of Figure 14, it is found that the fluctuation degree of the blue curve in the left subgraph “a” is greater than that in the right subgraph “b”, indicating that when using the ant colony algorithm for path planning between two points, due to the non-uniqueness of the calculation results, the results of each calculation only tend to be optimal, but not necessarily optimal. Therefore, the value of ${\mu }_L$ shows a decreasing trend as a whole, but it will fluctuate at local points. This also shows that the improved ant colony algorithm used in this paper has accelerated the convergence speed, but there is still much room for improvement in the optimization degree of path planning.

7. Conclusions

This paper proposes a method for efficiently calculating the path planning of a multi-robot formation transformation in the presence of obstacles in a two-dimensional plane. The method involves constructing a cost matrix and integrating the elite enhanced multi-population genetic algorithm with the ant colony algorithm to achieve route planning. The proposed method reduces the calculation time by more than 98% and exhibits high robustness, especially when the number of individuals in the formation-transformation path planning is relatively large. When considering the time reduction percentage ${\eta }_T$ and the average distance loss percentage ${\mu }_L$, the proposed method has a good application prospect for the path planning of multi-robot formation transformations with low overall energy consumption under the condition of allowing a certain increase in distance.

We will continue to carry out further research on 3D path planning in real space in the future and use real scenes to test the efficiency of the algorithm. In order to improve the algorithm’s convergence speed and path-planning results, we will further seek the optimal combination of parameters through experimental methods. In the case of curve partial path planning using an ant colony algorithm, we will attempt the use of a more efficient algorithm and verify its reliability via experiments.