Conflict-free and energy-efficient path planning for multi-robots based on priority free ant colony optimization

1.   Introduction

In recent years, with the wide application of intelligent robots in intelligent warehouse management and traffic control, multi-agent path finding (MAPF) as a critical technology in multi-intelligence collaboration has received extensive attention from scholars ^[1,2]. MAPF technique is to plan conflict-free paths for multiple robots with different tasks under obstacles and multiple constraints, and satisfies some production targets ^[3,4].

The algorithms for single robot path planning can be classified into three according to their characteristics: search-based, sampling-based and intelligent optimization-based. The typical method based on the search is the A* algorithm, but it is difficult to guarantee the optimality of paths in large-scale complex environments ^[5]. Lu et al. ^[6] address the large memory consumption and long running time of traditional A* by improving the heuristic function to reduce search efficiency. A typical method based on sampling is the Rapidly-exploring Random Trees (RRT), but there is a large amount of redundant computation during the traversal process ^[7]. Therefore, Xu et al. ^[8] and Ruan et al. ^[9] proposed a regional sampling RRT based on simplified maps. Zhang et al. ^[10] proposed an improved RRT based on target constraint sampling and target bias expansion. They ^[8,9,10] all address the low execution efficiency of the traditional RRT algorithm. Intelligent optimization algorithms include the ant colony algorithm ^[11], genetic algorithm ^[12], sparrow algorithm ^[13], and so on. In recent years, related scholars have made promising achievements in solving common problems such as slow convergence speed and easy falling into local optimality, which are widely faced in intelligent optimization algorithms. Yang et al. ^[14] introduced optimal and worst solutions in ant colony pheromone updating to expand the influence of high-quality ants and weaken the pheromones on the path of worst ants, which accelerated the convergence of ACO. Xu et al. ^[15] proposed a two-level ant colony algorithm with mutual collaboration, using external ant colonies for global search and internal ant colonies for local search, improving the algorithm's solution accuracy. Li et al. ^[16] proposed an improved forward search optimization planning path. This method can shorten the global path length by jumping the node search way and combined with an improved artificial potential field to smooth that path. Experimental results show that this method keeps the path at a safe and comfortable distance from obstacles compared to the traditional strategy, which is more suitable for single robot motion.

MAPF contains the research mentioned earlier on single-robot obstacle avoidance and path-optimal metrics (path length, smoothness, safety, energy consumption, etc.), more importantly, considers more complex motion conflict situations between robots. It has received much attention from scholars as a classical NP-Hard problem ^[17]. Lin et al. ^[18] reviewed the relevant research of MAPF over the years and have made a more systematic summary and generalization, classifying the planning algorithms into classical, heuristic, bio-inspired, and artificial intelligence methods and classifying the decision-making methods into centralized and decentralized. Cheng et al. ^[19] proposed an enhanced heuristic A* algorithm for solving the path-planning problem of large parking lots. Ren et al. ^[20] proposed an MS* exact algorithm, which can solve the optimal conflict-free path for 20 robots performing 50 tasks. Wen et al. ^[21] proposed a MAPF-POST algorithm based on the characteristics of robot motion in the actual scene. It reduces the conflict between robot paths and improves search efficiency. Xin et al. ^[22] proposed a solution to the problems of high computational complexity and difficulty in local planning for collision-free path planning of AGVs based on a Time-space network model. The global planning problem is decomposed into more minor local planning problems to improve computational efficiency, newly defined decision variables and constraints are introduced to improve the planning capability, and extensive case studies verify the feasibility. Murakami ^[23] considered scheduling and conflict-free paths for capacity-constrained AGV systems (robot capacity constraint and buffer capacity constraint) in a spatiotemporal network model. The proposed method enables optimal solutions in a wide range of cases.

In order to improve the solution efficiency and planning success rate of MAPF problems, many scholars have applied the priority-based planning method, conflict-based search and traffic rule method in recent years. Cap et al. ^[24] proposed a class of MAPF algorithms based on Prioritized Planning (PP) and designed several rules for determining the priority. Greshler et al. ^[25] introduced the cooperative conflict-based search (Co-CBS) to solve task assignments of multiple robots and their path planning. Wang et al. ^[26] proposed a method combining priority to obtain the path with optimal cost and execution time. Li et al. ^[27] combined D* Lite and PP algorithms to achieve high search efficiency and optimization of path quality. In order to efficiently achieve conflict-free path planning for swarm robots in more complex environments, Wu et al. ^[28] embedded priority rules into the improved heuristic algorithm to eliminate robot trajectories with potential conflicts, which has a high success rate and achieves a good balance between maximum completion time and working time objectives. Dewanga et al. ^[29] proposed a distance-priority-based approach, enabling low-priority robots to avoid collisions by bypassing high-priority robots.

There are promising results regarding the success rate of path solving and efficiency of algorithm execution for MAPF. However, the uncertain natural environmental factors may affect the cost of actual robot motion ^[30]. Accordingly, an investigation considering energy consumption ^[31] emerged. Zhang et al. ^[32] proposed a low energy consumption optimal path planning method based on the improved AD* (Anytime dynamic A*) algorithm, which incorporates distance and energy consumption cost into the evaluation function of the search nodes to search for the energy consumption optimal path. Mei et al. ^[33] divide the energy-optimal path planning process into two layers. First, a series of paths are generated by traditional path planning methods, such as the heuristic search ^[34] and RRT algorithms ^[35]. Then calculating these paths' consumption according to the energy consumption model in the path optimization process, an energy-efficient path can obtain.

In summary, most research on MAPF has focused on path planning success rate, algorithm execution efficiency, and so on as optimization objectives. Therefore, Considering the performance advantages of ACO in multi-objective planning paths have been verified and demonstrated by many scholars ^[36,37,38]. With the background of limited stored energy and the rough motion environment of the robot, we conducted a conflict-free and energy-efficient MAPF study based on an improved multi-objective ACO. The main contributions are as follows:

●   A dual-resolution raster map that considers obstacle and ground friction factors is designed to model the unstructured warehouse environment.

●   The energy-constrained ant colony optimization (ECACO) for a single mobile robot is proposed based on the excellent robustness and iterative evolution capability of the ant colony algorithm in path planning, which contains the heuristic function by energy-constrained improvement and the pheromone update strategy by energy model optimization. The improved heuristic function considers the path length, path smoothness, road friction coefficient, and path energy consumption. The enhanced pheromone update strategy considers the transformed kinetic energy of robot motion, the energy consumption to overcome the loss of traction resistance, and the energy consumption of robot hardware.

●   The priority conflict-free strategy (PCS) and route conflict-free strategy (RCS) are incorporated in ECACO. We named it priority-free ant colony optimization (PFACO) and applied it to the multi-warehouse robot systems. The PCS mainly solves the deadlock conflicts of multiple robots by switching the priority between conflicting robots and re-route planning to achieve the purpose of conflict resolution. The RCS mainly solves node conflict, counterpoint conflict, occupancy conflict, and blockage conflict among multiple robots based on waiting in place or re-route planning.

The rest of this paper is organized as follows: Section 2 classifies MAPF conflicts and proposes a 2.5D environment modeling method; Section 3 presents ECACO for single-robot energy-efficient path planning; Section 4 presents the multi-robot energy-efficient planning PFACO. Section 5 shows the simulation experiments and analysis; Section 6 provides a summary and the future work plan.

2.   Problem description

2.1.   Multi-agent path finding (MAPF)

The MAPF problem is defined as robots starting from their positions, planning paths to reach their separate target points, and eliminating spatiotemporal conflicts in the robot paths as much as possible. Based on conflict-free, optimizing the robot group path's energy consumption is the optimization goal in this paper.

where, the white grid indicates the free passable area, the black grid indicates the obstacle area, and the yellow grid indicates the free area always occupied by other high-priority robots.

Considering the PCS and map scenarios adopted in this paper, the conflict types are divided into two categories: typical MAPF conflicts (node conflict and counterpoint conflict) and priority MAPF conflicts (occupancy conflict and blockage conflict), which are defined as follows:

1) Node conflict: Two robots will occupy the same node position in the next moment. As shown in Figure 1, AGV1 and AGV2 will collide at moment Step 3 on map (2.5, 2.5).

2) Counterpoint conflict: Two robots traveling in opposite directions and exchanging positions with each other at the next moment. As shown in Figure 2, at the moment of Step 3, AGV1 will move from the map (1.5, 2.5) to map (2.5, 2.5), AGV2 will move from the map (2.5, 2.5) to map (1.5, 2.5), and AGV1 and AGV2 will collide in the exchange of positions.

3) Occupancy conflict: It means that in the priority MAPF (the principle is that the low-priority robot avoids the high-priority robot during its motion), as shown in Figure 3, the low-priority AGV2 stops more advance than the high-priority AGV1. The target point of AGV2 is located precisely on the node that AGV1 has not yet passed, and it cannot effectively avoid AGV1 later because the task is over.

4) Blockage conflict: We define it as a highly coupled local dynamic scenario that allows only one robot to pass. As shown in Figure 4 (yellow obstacles indicate positions always occupied by other high-priority robots), the congruent and phased movements between AGVs can significantly exacerbate the environment's coupling and limit the performance of conventional algorithms.

2.2.   Dual-resolution grid map modeling scheme

Considering the differentiated energy consumption of robot movement on the road surface with different roughness, this paper proposes a dual-resolution 2.5D map-building scheme, a composite map composed of two layers of grid maps. As shown in Figure 5, Maps A and B store the information on the friction coefficient of non-flat ground and obstacle information in the environment, respectively. Where the friction coefficient value of each node in Map A represents the average value of the friction coefficient in a grid range, the nodes in Map B represent white grids that robots can pass freely or black obstacle grids that are forbidden to pass.

In dual-resolution 2.5D, each grid information can be read arbitrarily by any robot. For example, we can use the function 'get. Map (1.5, 1.5)' to get the ground friction coefficient and obstacle information corresponding to Maps A and B at (1.5, 1.5), respectively. To reduce the computation of the algorithm, we mark the grid order from left to right and from top to bottom, and the relationship between the grid number $i$ and the coordinates $(x, y)$ is as follows:

where, $mod$ is the remainder operation; $ceil$ is the upward rounding operation; $MM$ is the maximum value of the horizontal axis of the grid map.

3.   Ant colony optimization theory

3.1.   Traditional ant colony optimization (ACO)

The ant colony algorithm simulates the foraging behavior of a natural ant population, where pheromones and heuristic information determine the probability ${p}_{i, j}^{k}$ of how ants choose their next travel direction in grid environments.

where, $k$ is the ant number; $i$ and $j$ denote the current position grid and the next transferred grid of ant $k$, respectively; $t$ denotes the current iterations; $\alpha$ and $\beta$ denote the expected values of the pheromone concentration ${\tau }_{i, j}\left(t\right)$ and heuristic function ${\eta }_{i, j}\left(t\right)$, respectively; $allowe{d}_{i}$ denotes the set of selectable lattices of ant $k$ at the grid $i$. ${\eta }_{i, j}\left(t\right)$ can be expressed as Eq (3).

where, $d$ is the Euclidean distance from grid $i$ to grid $j$.

As the iteration proceeds, ${\tau }_{i, j}\left(t\right)$ pheromones will accumulate and volatilize, and the pheromone update model is shown as follows:

where, $\rho$ is the pheromone volatility residual; $Q$ is the pheromone constant; ${L}_{k}$ is the total length traveled by ant $k$ in this cycle; $M$ is the total number of ants; $visite{d}_{i}$ is the collection of grids already visited by ant $k$.

3.2.   Energy constrained ant colony optimization (ECACO)

There are three main methods ^[39,40,41] to improve the energy utilization of robots: The first is to use high-efficiency drive motors, the second is to improve the electrical energy conversion efficiency of motor drive circuits, and the third is to reduce energy consumption through motion planning. However, available hardware and electrical conditions limit the first two methods. Therefore, we propose the energy-constrained ant colony optimization (ECACO) to explore an energy-efficient path planning of mobile robots based on the advantages of the iterative evolution of the ACO.

3.2.1.   Heuristic function of energy consumption constraint

Based on the unstructured rough environment modeled in 2.5D, the distance of the path, the degree of the path curvature, and the energy consumption caused by the ground roughness factor on the robot motion are the best indicators to evaluate the path. However, the initial undifferentiated distribution of pheromones in ACO is prone to the chaotic nature of ant colony motion. To make the heuristic function with better guidance, we explore a heuristic function combined with an energy consumption constraint to reduce the energy consumption of ants in the search process.

where, ${L}_{i, j}\left(t\right)$ is the road evaluation function; ${T}_{i, j}\left(t\right)$ is the smoothing evaluation function; ${\varLambda }_{i, j}\left(t\right)$ is the friction factor evaluation function; ${E}_{i, j}\left(t\right)$ is the energy consumption evaluation function; $w, x, y, z$ are the weight of each function; $Backcost$ is the fallback suppression factor.

Considering the large-scale multi-robot scenario, ants will be given a large number of node conflict constraints. Moreover, there is a high possibility of blockage conflict, as shown in Figure 6, under the obstacle environment constraint. To relieve such situations, we introduce a fallback strategy ^[42] based on the traditional ACO. The effect of this strategy is illustrated in Figure 7, where ants return to the original path when a zero suitable node is available to follow. For the purpose of preventing unnecessary backtracking of ants resulting in extra energy consumption, we use the suppression factor $Backcost$ to reward and penalize the heuristic function.

1) Road evaluation function

The conventional ACO uses the distance factor of Eq (3) to evaluate the Euclidean distance from the ant's currently available grid that can be selected to the target grid. Since the difference in this distance is not apparent, we modified the distance evaluation function with the following equation to reflect the attractiveness of the target grid.

where, ${D}_{max}$ and ${D}_{min}$ denote the maximum and minimum Euclidean distance from the neighboring grid to the endpoint $E$, respectively; $d(j, E)$ is the Euclidean distance from the neighboring grid $j$ to the endpoint $E$.

2) Smoothing evaluation function

Considering the smoothness of the path, the fewer the number of turns, the better the energy consumption is. The smooth evaluation function of the two-dimensional path is introduced as follow:

where, $Lgrid$ is the length of cell grid; ${dr}_{g, i}$ and $d{r}_{i, j}$ are the movement direction of ant at the previous and current moments, respectively. If the two transfer directions are the same, the ant has a higher probability of transferring in the direction of the previous movement.

3) Friction factor evaluation function

The friction factor in a rough road environment is the main factor affecting the energy-efficient path planning of robots: the larger the friction factor, the greater the energy consumption generated by the work of robots to overcome traction resistance ^[43]. In order to make the ants tend to choose the grid blocks with smaller friction coefficients during the movement, we design the friction factor evaluation function as follows.

where, ${\mu }_{max}$ and ${\mu }_{min}$ denote the maximum and minimum values of the friction coefficients of the current grid $i$ and the neighboring grid $j$, respectively; ${\mu }_{i}$ and ${\mu }_{j}$ denote the friction coefficients of the ant's current position and the neighboring position, respectively.

4) Energy consumption evaluation function

Considering the physical characteristics of the mobile robot to overcome friction, we introduced an energy-related criterion to quantify the accumulated path energy consumption of the ant and the energy consumption to be generated. We used this criterion as an energy consumption evaluation function, expressed as follows:

where, ${\mu }_{x}$ is the friction coefficient of ants passing through the grid path $visite{d}_{i}$; $\theta$ is the slope of the ground (this paper only considers the two-dimensional plane, so we set ${\mathrm{\theta }}$ to 0); $m$ is the robot weight; $g$ is the acceleration of gravity; ${s}_{x}$ is the path length of the ant's single-step transfer.

3.2.2.   Pheromone update considering robot energy consumption model

1) Energy consumption model

The robot's load size, mode of operation, road conditions, distance traveled, sensor composition, and electronics all affect the system's energy consumption. This is especially true for warehouse robots that continuously transport materials in large-scale and rough ground environments, requiring higher energy reserves. In this paper, the energy consumption is based on the work done by robots to overcome ground friction, and the influence of the travel distance and ground environment factors is discussed. The following assumptions are made in advance:

Assumption 1: The robot has absolute power and can follow the planned path strictly without any failure.

Assumption 2: To ensure the safety and controllability of the multi-warehouse robot system, the robot's acceleration and deceleration motion control is achieved within half a grid area and works at rated power.

The primary energy consumption ^[44,4546] of the warehouse robots is: the energy converted into kinetic energy of the robot ${E}_{k}$, the energy to overcome traction resistance to do work ${E}_{f}$, and the loss from the conversion of the robot's hardware energy ${E}_{p}$, as shown in the following:

where, $m$ is the weight of the mobile robot itself and the supplies; $v\left(t\right)$ and $v(t-1)$ denote the robot's velocities at moments $t$ and $t-1$, respectively; $I$ is the rotational inertia; $\omega$ is the angular velocity of the robot during the turn; $R$ is the radius of the tire; $\mu$ is the ground friction coefficient; $g$ is the acceleration of gravity. η is the robot energy conversion efficiency; $P$ is the rated power of onboard sensors and electronics.

2) Pheromone update under energy consumption constraint

Several feasible paths will be obtained after the completion of the current iteration, which will be combined with the above energy consumption model to replace the traditional ant-period model.

We know from the above equation that the evaluated energy consumption value of a path always affects the update of the pheromone, which means that the lower the energy consumption of a path, the greater the accumulation of the pheromone. The probability ${p}_{i, j}^{k}\left(t\right)$ is consequently doubly influenced by the energy consumption heuristic function of Eq (6) and the pheromone of Eq (16), which makes the ant colony always tend to choose the path with a low energy consumption value in the subsequent search process. A path with the lowest energy consumption is eventually evolved by our ECACO algorithm.

Taking into account the possible local optimum problem caused by the search mechanism of the ant colony algorithm, we set the pheromone in the range as shown in Eq (18) by maximum ${\tau }_{max}$ and minimum ${\tau }_{min}$.

The pseudo code of ECACO above is shown in Algorithm 1.

4.   Priority free ant colony algorithm for multi robot

A straightforward approach to solve trajectory coordination problems is to see all robots in the system as one composite robot with many degrees of freedom and use some path planning algorithm to find a joint path for all the robots. However, the size of the joint configuration space that has to be searched during the planning is exponential in the number of robots. Thus, this approach quickly becomes impractical if one wants to plan for multi-robots. A pragmatic approach often useful for large multi-robot teams is prioritized planning. The idea of prioritized planning was first articulated by Erdman et al. ^[47].

Priority-free ant colony optimization (PFACO) is a heuristic algorithm that considers multi-robot path conflict and energy consumption cost, which is proposed for the first time in this paper. Based on our ECACO algorithm, the PFACO algorithm integrates the prioritization-free conflict strategy (PCS) and route-free conflict strategy (RCS). The execution process is as follows: First, the optimal energy consumption path of a single robot is planned by ECACO (the conflicts between robots are ignored), and the four-neighborhood search mechanism is adopted in this step. Then the robots are given the corresponding priority according to the energy consumption value. Then the low-priority robot searches for Spatio-temporal conflicts with the high-priority robot through the binary conflict-tree (CT). When a conflict is recognized, the path of the higher-priority robots holds while lower-priority robots follow wait or replan. We employ a dynamic priority adjustment method to improve conflict-free success, as the solution space of lower-priority robots is limited when there are too many robots.

PFACO consists of two crucial parts, a scheme for prioritizing robots in rough ground environments and a free strategy for resolving low-priority robot conflict. We will discuss how to fulfill them in this section.

4.1.   Prioritized conflict-free strategy

It was proposed by Erdmann et al. ^[47] in 1987 for the priority scheme. This works as follows: First, each robot is assigned a unique priority; Second, the trajectories of the individual robots are planned in decreasing order of priority; Third, one conflict-free trajectory is obtained for each robot.

4.1.1.   Prioritization order

One crucial question is how to assign different priorities to the robots. While there certainly can be some natural reasons, such as based on the task's importance or the robots' different times, this is not something we assume here. In addition, as there are ${\mathrm{N}}!$ priority plans if we have ${\mathrm{N}}$ robots, it would not be an appropriate solution to sacrifice valuable CPU time to try all plans to choose the best one ^[48].

We propose a simple method to assign priority to robots. In our ECACO algorithm, the optimal energy consumption path for each robot in a non-smoothed environment from the start point to the goal point is determined, so we define a robot's energy consumption query set as $Energy = \{{E}_{1}$, ${E}_{2}$, ...${E}_{m}$}. In our approach, the corresponding priority of a robot is its query position in the ascending energy consumption set ${{Energy}^{*} = \{{E}_{i}, {E}_{j}, ..., {E}_{z}\}}^{*}$. The rationale behind this heuristic can be illustrated in Figure 8: Robots with more significant query energy consumption traverse a larger number of regions and have a more extensive solution space than low-energy consumption robots. It should be able to complete the planning task relatively unhindered by giving it a lower priority, and this should be beneficial for reducing our energy consumption goal.

Since the path energy consumption of each robot is differentiated, it means that the priority of each robot can be specified. For example, this is done by the ECACO algorithm for the robots numbered {①$,$②$,$③$,$④$,$⑤}; Then we get ${\mathrm{E}}{\mathrm{n}}{\mathrm{e}}{\mathrm{r}}{\mathrm{g}}{\mathrm{y}} = \{200, {\mathrm{ }}345,514, {\mathrm{ }}490, {\mathrm{ }}145\}$, after ascending order as ${{\mathrm{E}}{\mathrm{n}}{\mathrm{e}}{\mathrm{r}}{\mathrm{g}}{\mathrm{y}}}^{{\mathrm{*}}} = \{145, {\mathrm{ }}200, {\mathrm{ }}345, {\mathrm{ }}490, {\mathrm{ }}514\}$, the robots correspond to priority {1, 2, 3, 4, 5}in order, and the robots numbered {⑤$,$①$,$②$,$④$,$③}. We know that the query energy consumption of robots ⑤ and ③ are 145 J and 514 J, respectively, and the corresponding priorities are 1 and 5, respectively, so robot ③ needs to execute PCS for robot {⑤$,$①$,$②$,$④} which has higher priority than it.

4.1.2.   Secondary-free mechanism

For example, as shown in Figure 9, PCS determines the numbering of AGVs as ①–④, with decreasing priority. There is a risk of collision between AGV4 and AGV3 at Step 3 when the robots start moving simultaneously, and the low-priority AGV4 cannot search for a valid path. To solve this invalid pre-planned path caused by the priority mechanism, we perform the reward and punishment operation shown in Eq (20) on the heuristic function of ECACO. It prevents the ants from selecting those nodes with spatio-temporal conflicts during the path search process as much as possible by quadratic solution. Eventually, it obtains the ideal path in Figure 10.

4.1.3.   Dynamic prioritization strategy

The hypothesis is that other factors still hinder the secondary planning path of the ECACO algorithm, which will face an awkward situation, as shown in Figure 11. Considering the sensitivity of the priority mechanism to the robot scheduling order ^[49], we propose a priority dynamic adjustment strategy to respond. The principle is to find the highest priority robot which has a conflict with AGV4 by CT, that is AGV2, and adjust the original priority AGV1 > AGV2 > AGV3 > AGV4 to AGV1 > AGV4 > AGV2 > AGV3 by the priority insertion mechanism, and replan the paths of subsequent robots from AGV4. The coordinated conflict-free path is shown in Figure 12, and only AGV3 increases the waiting time at Step 3 moment. The dynamic priority adjustment strategy can possibly reduce the collision risk and energy consumption compared to the replanning path.

In this subsection, we discuss the PCS for resolving the overall conflict, which contains how to determine the task priority of the robots, the secondary-free operation, and the priority dynamic adjustment mechanism. In the following subsection, we will discuss the path conflict-free strategy when two robots are situation in detail.

4.2.   Route conflict-free strategy (RCS)

4.2.1.   Four-neighborhood search mechanism

The diagonal directional transfer shown in Figure 13 may occur in a single robot's traditional eight-neighborhood search path. It is difficult to effectively judge the motion conflict between two robots, especially when there are large-scale robots. In this paper, we restrict the selection of the grid by ECACO to the four-neighborhood shown in Figure 14 through Eq (21), which makes the single-step jump distance of 1m for the ant. This is not only guaranteed robot not to collide with obstacles but also more conducive to achieving the synchronization of swarm robot movements.

where, $D(i, j)$ is the distance from the grid $i$ to grid $j$ in eight-neighbourhood range; $Direction\left(\right)$ is the direction which the ant move from grid $i$ to grid $j$.

4.2.2.   RCS for typical path conflicts

Node and counterpoint conflicts are the most typical conflict in MAPF, where two robots meet in motion. We determine the movement nodes of the low-priority robots according to the node expansion approach in Section 4.2.1 to stop-wait or detour. The stop-wait mechanism is shown in Figure 15, which means expanding the current node as the next state point and resuming the motion after the high-priority robot leaves. The detour mechanism applies when the stop-wait mechanism fails, and the low-priority robot can only choose a conflict-free path with the high-priority one. The RCS pseudo-code for the typical conflict is shown in Algorithm 2.

1) Cross-shaped node conflict: as shown in Figure 16, the priority of conflicting robots is judged by ascending energy consumption priority strategy. The low-priority robot AGV2 implements wait-in-place, i.e., the extended wait point is the next state point until the motion path of the high-priority robot AGV1 no longer affects its movement and then continues to travel along the original path.

2) Phase direction type node conflict: As shown in Figure 17, the high-priority robot AGV1 continues to move according to the planned path, and the low-priority robot AGV2 performs a local re-planning path movement to the target point.

3) Counterpoint conflict: As shown in Figure 18, a collision between robots must exist, and the low-priority wait-in-place strategy fails. At this time, the high-priority robot AGV1's path remains unchanged, and the low-priority robot AGV2 gets a new path.

4.2.3.   RCS for priority-derived conflicts

Node and counterpoint conflicts are typical motion conflicts, and fewer scholars have focused on the risk of occupancy conflict and large-scale robot blockage coordination problems derived from priority MAPF. We additionally concentrate on the green path planning problem, with the following RCS for resolving related conflicts.

1) Placeholder Conflict

Occupancy conflict define: the target point of the low-priority robot is located exactly on the path not passed by the high-priority robot.

RCS (The RCS pseudo code is shown in Algorithm 3):

● Strategy 1- As shown in Figure 19, it is predicted that there is an occupancy conflict between the low-priority AGV2 and the high-priority AGV1. We then allow AGV2 to activate the waiting mechanism at the nearest Step3 position (conflict-free node) from the target point and resume its movement after the conflict release.

● Strategy 2- As shown in Figure 20, the path is replanned if the conditions of AGV3 would not enable a waiting mechanism of strategy 1 to be triggered. In this process, the waiting mechanism will be triggered cyclically so that we can also save energy resources while taking into account the obstacle avoidance process as much as possible.

2) Blockage Conflict

Blockage conflict define: low-priority robot meets high-priority robot in a narrow environment.

RCS (The RCS pseudo-code is shown in Algorithm 4):

● Strategy 1- As shown in Figure 21, a failed path is searched by low-priority AGV3 at Step3 time under massive conflict. We allow AGV3 to retreat to the previous path node if nothing is disturbed by other robots at the next moment. If this conflict holds, it will stop the movement at the original safe position to save energy. The movement on the original path is continued as soon as the conflict is solved. Otherwise, the path of AGV3 is re-planned.

● Strategy 2- In the particular case shown in Figure 22, there is no wait command satisfied by the low-priority AGV2. It will trigger a multiple fallback method without affecting the movement of high-priority AGV1 until the conflict is entirely released before resuming the original motion.

Remember: We did introduce the secondary freedom mechanism in Section 4.1.2 and the dynamic priority policy in Section 4.1.3 for resolution in the planning process when RCS failed to resolve the above four conflicts effectively.

4.3.   Algorithm flow

The flow of our multi-robot energy-efficient planning algorithm is shown in Figure 23.

5.   Simulation experiments

This paper is a simulation experiment on Matlab 2020a with the computer performance of Lenovo R7000, i5-11400H@2.70GHz. The relevant parameters of the robot and the ant colony algorithm are shown in Table 1.

5.1.   Single-robot path planning comparison experiment

In order to verify the energy-saving effect of the ECACO algorithm proposed in this paper on robot motion, a dual-resolution map is used to simulate an unstructured scenario. The map model uses a 20 m × 20 m scale, the friction coefficient of the non-flat road surface is randomly generated between 0 and 0.45, and the robot's weight is 10 kg. To reflect the applicable scenarios of our algorithm, we consider three standard neighborhood search methods for path planning: traditional eight-neighborhood, secure eight-neighborhood ^[50], and optimized four-neighborhood ^[51]. In addition, we verify the effectiveness of ECACO in energy saving by ablation experiments under each type of approach. The compared algorithms include Improved heuristic function-ACO (IHF-ACO), Improved pheromone update (IPU-ACO), traditional ACO, traditional A* and IA*^[52].

5.1.1.   Traditional eight-neighborhood search method

We conducted comparative experiments in an environment filled with diagonal obstacles, and the results of the simulation experiments are shown in Table 2 and Figures 24 and 25. It can be noticed that the energy cost of the path planned by ECACO in this paper is 9973 J, which is optimized by 5.04, 5.62, 2.70, 16.09 and 17.08% compared to IHF-ACO, IPU-ACO, traditional ACO, A* and IA*, respectively. A* and IA* outperforms ECACO slightly in terms of path length and solution time. Regarding path length and the number of energy-stable iterations, our ECACO algorithm is significantly better than the other algorithms with both 6 iterations. In terms of path smoothing, IHF-ACO and IA* perform the worst, ECACO has the least number of turns. In general, the algorithms in this paper outperform the comparison methods in comprehensive indexes. However, the paths planned by all algorithms in the traditional eight-neighborhood search method pass through the diagonal obstacle at (15, 4) and collide with the obstacle's edge many times on the map. Sections 5.1.2 and 5.1.3 will explore the safe ground path planning problem under the two safe neighborhood search mechanisms. The IA* algorithm improves the traditional heuristic function of A*, so it has its advantages in node expansion as well as program efficiency but may have the awkward situation of non-optimal solutions.

5.1.2.   Security eight-neighborhood search method

We remained in the more complex diagonal obstacle environment and conducted safety eight-neighborhood experiments, as shown in Figures 26 and 27 and Table 3. The results show that the paths planned by all algorithms after improving the neighborhood search maintain a certain safety distance from the obstacles, which improves the safety of robot passage compared with Section 5.1.1. In terms of energy consumption solution, the path energy consumption of our ECACO and traditional A* are 11,089 J, which is optimized by 1.67, 2.11, 0.40 and 2.26% compared to IHF-ACO, IIU-ACO, traditional ACO and IA*, respectively. Regarding the path length, IPU-ACO plans the longest path, ACO is the second, and the shortest path length of the robot in this paper is 30.3848 m. The stable iterations of path length and energy consumption in our ECACO are 6, which is better than other algorithms. In the smoothness of the path, ECACO, IHF-ACO, A* and IA*are the same, and both are better than IPU-ACO and ACO. As for the solution time, IHF-ACO has the worst solution time, IA* has the best path solution time.

It can be seen from the comprehensive analyses that the IPU-ACO using energy consumption model optimization has poor algorithm-seeking ability due to the lack of a reasonable heuristic guide. While the IHF-ACO, considering the energy consumption model heuristic function, can achieve low-energy path planning, it also lacks a reasonable pheromone strategy to enhance the iterative evolution of the algorithm. In this paper, ECACO integrates the advantages of IPU-ACO and IHF-ACO under the security eight-neighborhood mechanism to achieve better energy-efficient path planning. Both IA* and A* are heuristic algorithms with path length as the goal of finding the optimal path. IA* improves program execution efficiency but presents the awkward situation of non-optimal paths, as described in Section 5.1.1. The distribution of obstacles is relatively simple in this case, resulting in the path with the shortest path length also being the lowest energy one. Thus, the A* achieves the same effect as ECACO in this paper under the safe eight-neighborhood search mechanism, but there is a significant difference under the four-domain search in Section 5.1.3.

5.1.3.   Optimizing the four-neighborhood search method

The more popular current node search strategy for multi-robot systems is the four-neighborhood approach (described in Section 4.2.1). To facilitate the experimental verification of the multi-warehouse robots in subsequent Sections 5.3.1 and 5.3.2, the energy-efficient planning of ECACO is verified in a single-robot environment in advance. The simulation and experimental results are shown in Table 4 and Figures 28 and 29. In terms of energy consumption solution, the energy consumption of the ECACO in this paper is 11,219 J, which is 11.32, 8.39, 13.16, 19.91 and 26.30% optimized compared with IHF-ACO, IIU-ACO, traditional ACO, A* and IA*, respectively. As for the solution time, ECACO has the worst solution time, and IA* has the best path solution time. Since the optimized four-neighborhood approach is adopted, the path lengths of all six algorithms are the same. However, our ECACO significantly reduces the energy cost due to its clear superiority over other algorithms in path smoothing and node selection for rough pavement. In addition, ECACO outperforms the IHF-ACO, IIU-ACO and traditional ACO regarding path and energy consumption iteration stability. Taken together, it can be seen that the ECACO algorithm proposed in this paper is suitable for multi-robot environments and can reduce energy costs.

5.2.   Multi-robot priority scheduling sensitivity verification

The PFACO algorithm in this paper incorporates three strategies: single-robot ECACO, PCS for determining multi-robot priorities, and RCS for coordinating multi-robot conflicts. Section 5.1 verifies the energy-saving effectiveness of ECACO. This section will test the sensitivity of robot priority scheduling on MAPF problem through a 10 m × 10 m scale blank rough environment and a 10 m × 10 m scale obstacle rough environment energy consumption. Within the framework of ECACO-PCS-RCS in this paper, three types of PCS are selected for comparison: energy consumption ascending PCS (the smaller the energy consumption value, the higher the robot priority), energy consumption descending PCS (the more extensive the energy consumption value, the higher the robot priority), and regular PCS (the robot priority is not specially treated). We set up 10 robots in each of the environments for 10 labs, and the starting and endpoints of each robot were randomly generated. The algorithm performance was quantified by averaging the energy consumption, path length, the number of turns, mean squared difference of friction coefficients, and time spent on algorithm solving.

5.2.1.   Blank rough environment

The experimental results of the three PCS strategies in the blank rough environment are shown in Figures 30–32 and Table 5. What can be known is that the average energy consumption value of PCS in this paper is 73.858 KJ, which is 13.5 and 7.8% more optimized than descending PCS and conventional PCS, respectively. Regarding path length solving, the results of this paper and the descending PCS are optimal and worst, respectively. As for path smoothing, Our PCS and conventional PCS solving effects are close, and the descending PCS performs the worst. The three strategies are close in effect in terms of the average friction coefficient mean square deviation and algorithm-solving time. In addition, we can obviously discover from Figure 30 that the descending PCS performs the worst in each experiment, and the conventional PCS outperforms our PCS only in the seventh experiment. Overall, the strategy of this paper to query the energy consumption of robots in blank rough environments based on the ECACO algorithm and assign higher priority to robots with lower energy consumption values is feasible and effective.

5.2.2.   Obstacle rough environment

This section adds the obstacle environment to the above rough terrain experiments to further expand the test scenario of the algorithm, and the experimental results are shown in Figures 33–35 and Table 6. What can be known is that the energy consumption values of our PCS, descending PCS, and conventional PCS are 86.9405, 94.2088 and 94.4898KJ, respectively. Our PCS is optimized by 4 and 8% compared to the two strategies. Our strategy performs optimally regarding path length, path smoothing and algorithm time-solving. We compare three different PCS strategies in the framework of the ECACO-PCS-RCS algorithm through this example experiment and verify the feasibility of the ascending PCS to determine the robot priority in this paper. In the following subsection, we will expand the number of robots and the scale of the environments, then compare and analyze multiple performance metrics in both horizontal and vertical directions.

5.3.   Multi-robot path planning comparison experiment

In order to evaluate the practical advantages of the multi-robot energy-efficient path planning algorithm in this paper, two different scenarios are selected for comparison experiments, which are 20 m × 20 m scale blank rough and 40 m × 40 m scale rough warehouse environments. Based on the algorithmic framework of ECACO-PCS-RCS in this paper, our PFACO algorithm is compared with three methods, ACO-TPCS-RCS, ACO-PCS-RCS and ECACO-TPCS-RCS, in each scenario. Where ACO is the ant colony algorithm of the traditional ant perimeter model; ECACO is the ant colony algorithm of the energy consumption model in this paper; TPCS is the traditional priority strategy; PCS is the priority strategy in this paper; RCS is the free strategy for multi-robot path conflicts (to ensure that there is no collision conflict among robots) in this paper.

Regarding experimental design and comparison metrics: the number of robots increases from 10 until the total number is over 100, with 10 more each round. For each experiment, the starting and target points are randomly generated to match the number of robots, and they are guaranteed to be different from each other to avoid invalid conflict. In order to avoid the chance of single simulation experiment results, 20 non-repeated experiments are conducted for the same number of robots, and the average of these experiments reflects the algorithm's accuracy. The performance indexes of the algorithm mainly include path planning success rate (We only count those cases where the paths are free of any conflicts), average energy consumption, average path length, the average number of turns, average variance of ground friction coefficient, and average program running time value.

5.3.1.   Blank rough environment

As shown in Figure 36, when the number of robots is small (less than 20), the success rate of all two algorithms (PFACO, ACO-PCS-RCS) in planning paths is 100%. The success rate of solving ACO-TPCS-RCS and ECACO-TPCS-RCS starts to decrease obviously when the number of robots has more than 20, and the conflict among robots increases, so the robots with low priority under the TPCS strategy may not be able to find feasible paths. In contrast, based on our PCS strategy, PFACO and ACO-PCS-RCS success rates only start to decrease when the number of robots is 60 and 50, respectively. However, our PFACO maintains a high success rate, which is still 15% higher than ACO-PCS-RCS at a scale of 100 robots. As shown in Figures 37–40 for each comparison metric, the comparative analysis of PFACO and ACO-PCS-RCS is focused due to the premature death of the ACO-TPCS-RCS and ECACO-TPCS-RCS algorithms. When the number of robots is 10, the energy consumption solution result of our PFACO is 4.0 KJ better than ACO-PCS-RCS. When the number of robots is increased to 100, the difference achieves 30.4 KJ. The difference between the two algorithms increases as the number of robots increases, indicating that our PFACO algorithm framework is not only better at solving robot conflict but also more energy efficient. This is mainly reflected in the fact that PFACO significantly outperforms the other algorithms in terms of path length, the number of turns, and friction coefficient in Figures 38–40. Regarding the solution time shown in Figure 41, the difference in solution time between the four algorithms is small when the number of robots is small. As the number of robots increases and the congestion of robots becomes higher, the wait-in-place and detour behaviors performed by the RCS strategy rise, and the solution times of PFACO and ACO-PCS-RCS increase significantly. The maximum solution time of ACO-PCS-RCS is 13.4 s larger than our method at first, but the difference between the two is 255.3 s when the number of robots reaches 100. The path schematic of the maximum number of robots that the algorithm can achieve is shown in Figure 42. Our PFACO execution success rate is higher and the quality of the planned paths is better, as shown by comparing the various metrics of the four algorithms in the blank rough environment.

5.3.2.   Rough warehouse environment

To further verify the effectiveness and stability of the algorithm, the maximum load m = 500kg of the unmanned warehouse robot of Jingdong Company was used as the background. The relevant parameters of ECACO were modified as follows: the pheromone constant Q was 10,000, the number of ants M was 20, and the maximum number of iterations NC was 10. The size of the unstructured warehouse scene is 40 m × 40 m, and 48 shelves are placed. We conducted more comprehensive testing and analysis of the algorithms by the different levels of robots and random tasks, and the experimental results are shown in Figures 43–49.

The solution success rates of all algorithms are shown in Figure 43, where the success rates of ACO-TPCS-RCS and ECACO-TPCS-RCS still decrease to 0 prematurely, and the following analysis is focused on PFACO and ACO-PCS-RCS. Both PFACO and ACO-PCS-RCS success rates are at 100% when the number of robots is less than 60, and the success rate gradually decreases as the number increases. Although our ECACO outperforms ACO significantly for individual robots (verified in Section 5.1.3), this also means that more path intersections and more conflicts are generated when applied to multiple robots. These experiments add obstacle constraints compared to the obstacle-free environment in Section 5.3.1, making the success rate of our ECACO slightly worse than that of ACO-PCS-RCS when the number of robots is 90–120. However, it is clear from the energy consumption shown in Figure 44 that the energy consumption advantage of our PFACO algorithm is still apparent, especially when the number of robots is 120, the average energy consumption results of PFACO and ACO-PCS-RCS algorithms are 10207.1 KJ and 14675.2 KJ, respectively, and ours reduces 30% consumption compared with ACO-PCS-RCS. In Figures 45–48, with the number of robots at 120, our PFACO algorithm outperforms the ACO-PCS-RCS in terms of path length, the number of turns, friction coefficient, and algorithm running time by 24, 53, 3 and 51%, respectively.

Through the comparison experiments under two different environments in Section 5.3, we thoroughly verify the advantages of the PFACO algorithm in this paper regarding the success rate and cost of multi-robot path planning, and the innovative and industrial reference value of the theory is also reflected.

6.   Conclusions and prospect

Multi-robot coordination and cooperation in completing work will be the trend of robotics research. This paper proposes a multi-robot energy-efficient path planning algorithm based on the priority scheduling concept with limited energy storage and robots' energy consumption as the MAPF background. First, we design an unstructured storage environment modeling method that considers both obstacle and rough ground friction factors. Second, we propose an ECACO energy-efficient planning algorithm for a single mobile robot, which contains a heuristic function for energy consumption constraint improvement and a pheromone update strategy for energy consumption model optimization. The improved heuristic function considers the path length, path smoothness, road friction coefficient, and path energy consumption. The improved pheromone update considers the transformed kinetic energy of robot motion, energy loss from overcoming traction resistance, and robot hardware energy consumption. Then, we propose a PFACO energy-efficient planning algorithm for multi-warehouse robots, which incorporates Prioritized Conflict-free Strategies (PCS) and Route Conflict-free Strategies (RCS) based on ECACO. PCS mainly solves the deadlock conflicts of multiple robots by swapping the priority between conflicting robots and re-route planning to free conflict. RCS mainly resolves node conflict, counterpoint conflict, occupancy conflict and blockage conflict among multiple robots based on the methods of waiting in place or re-route planning. The results show that our ECACO algorithm and the extended PFACO algorithm have more significant improvements in energy savings and solution success rate than other methods in complex rough terrain, which are of reference value when applied to practical warehouse robots.

The performance of our PFACO algorithm was fully validated in this study, but further improvement of the algorithm success rate, path performance metrics, and program execution efficiency in the large-scale robot scenario will continue during future work. In addition, more complex factors such as MAPF multitask planning (TSP problem), intermittent communication, and dynamic obstacle problems will also be focused on in future research.

Data available

Detailed multi-robot experimental data can be obtained from the link: https://github.com/1354109872/PFACO.

Conflict of interest

The authors declare that there are no conflicts of interests.