1 Introduction

Multi-Robot Systems (MRSs) have advantages over single-robot systems in terms of spatial distribution [1], robustness [2], scalability [3], and flexibility [4]. During the last decade, MRS has evolved from an isolated anecdotal laboratory system to robust deployment in many fields [5], especially when a given task requires the cooperation of robot teams, such as cleaning [6], service [7], space-exploring [8, 9], warehousing [10], coverage [11], search-and-rescue [12], and military [13]. To date, many research efforts have focused on different research topics related to MRS, including communication techniques [14], vision systems [15], and navigation [16, 17]. Mobile navigation is typically realized through perception, planning, and control [18]. The objective of perception is to obtain environmental information around the robot for path planning, and the objective of control is to make the mobile robot follow the planned path. Therefore, path planning is a fundamental problem of MRS, and its objective is to move all robots working in a shared environment to their respective goal positions while meeting performance constraints (e.g., travel time) and safety constraints (e.g., collision avoidance) [19]. This paper focuses on a decentralized MRPP approach whose objective is to avoid potential collisions and deadlocks [20] with other robots in real-time while minimizing the deviation from the preplanned optimal path.

The collision between robots is a crucial problem in the path planning and motion control of MRSs and has not received sufficient attention. Obstacle and interrobot collision avoidance directly impact system safety, so it should be the highest priority among all objectives [21]. A simple method of avoiding collisions is to treat other moving robots as obstacles, namely, untraversable vertices [22] in the grid map. However, as shown in Fig. 1, the method cannot prevent robot 2 (R2) from planning D3 as the next vertex, which is likely to cause another collision with robot 1 (R1).

Fig. 1
figure 1

A problematic situation of collision avoidance by treating other robots as obstacles. The green and the red vertices denote the robot positions and goal positions, and the arrow denotes the direction of the robot

Full size image

The deadlock between robots is another vital issue in MRPP since it can degrade system performance or even crash the system [23]. As shown in Fig. 2, the deadlock between mobile robots typically occurs when robots block each other in a way so that none of them can follow its predefined path without causing a collision.

Fig. 2
figure 2

Illustration of the deadlock between robots [24]. a The initial state of robots. b and c The deadlock condition is encountered and repeated in-between (b) and (c) infinitely

Full size image

Moreover, the prioritized planning algorithm typically plans each robot’s path individually and then combines other methods or strategies to resolve the conflicts between robots. The established paths are typically optimal in the grid environment, so minimizing the deviation between the modified path and the initial path helps maintain the path optimality. As shown in Fig. 3, R1 collides with R2 as it follows the preplanned path and vice versa. A decentralized approach may make the optimal decision locally to move R1 to vertex C3 and then head south to reach the target, but it causes unnecessary deviations if R3 can move diagonally.

Fig. 3
figure 3

A problematic situation of decentralized methods where the shortest path is the objective [24]

Full size image

The motivation of this research is to solve the challenges mentioned above in implementing the prioritized MRPP approach, that is, (1) what is the effect when a robot lies in the path of another robot, namely, interrobot collision avoidance, (2) how to move robots when they block each other, namely, deadlock avoidance, and (3) how to ensure that the actions taken to avoid collisions and deadlocks with other robots do not exceed the minimum effort required, that is, to minimize the deviation between the modified path and preplanned path. This paper proposes a Multi-Robot D* Lite (MR-D* Lite) algorithm to solve these problems. The main idea of MR-D* Lite is to employ the D* Lite algorithm to calculate the initial path of each robot individually, and then combine the AUV to modify the path of the robot with a potential collision or deadlock risk. The main contributions of this paper can be summarized as follows:

  • Many researchers focus on collision avoidance between robots, but deadlock avoidance and path deviation are typically not considered simultaneously. This paper defines five types of potential conflicts between mobile robots and proposes three types of AUVs to resolve the conflicts. The AUV considers both the position and direction of robots, thereby solving the conflicts between robots with a minor or minimum deviation from the predetermined optimal path.

  • The dynamic characteristics of D* Lite are used to address the conflicts between robots while minimizing the time to replan a new collision-free and deadlock-free path for each robot.

The remainder of this paper is organized as follows: Section 2 introduces the related works, problem definition, and underlying algorithm. Section 3 provides the proposed method. The results and the conclusion are presented in Sections 4 and 5, respectively.

2 Preliminaries

2.1 Related works

MRPP can be characterized into two categories: centralized and decentralized approaches [25, 26]. The centralized approach treats the path planning issue as an optimization problem via a central server, which has comprehensive knowledge about all robots’ workspace (e.g., a 2D grid map) and intents (e.g., speed, start position, and goal position). The centralized approach mainly includes four categories [27]: protocol-based [28], conflict-based search [29], increasing cost tree search [30], and A* search expansion [31]. It plans collision-free paths for all robots simultaneously and can produce globally optimal plans. However, the time complexity is exponentially related to the composite configuration space dimensions and the number of robots. Thus, it is typically applicable to simple problems that involve two or three robots, and its performance can be low if tasks/goals are reassigned frequently. Moreover, the approach relies heavily on a reliable communication network between the central server and robots in practice. Thus, MRS will breakdown if the central server or communication network fails. Furthermore, the centralized approach is inapplicable when the environment is unknown and unstructured [32]. In recent years, nature-inspired optimization algorithms have been applied to various versions of centralized approaches to address the MRPP optimization problem [21], which include Particle Swarm Optimization (PSO) [33], Gravitational Search Algorithms (GSA) [34], firefly optimization [35], Charged System Search (CSS) [36], Ant Colony Optimization (ACO) [37], Artificial Bee Colony (ABC) [38], and Genetic Algorithm (GA) [39]. Most of these algorithms can find better paths as the number of iterations increases, but they are computationally expensive.

Compared with centralized approaches, some researchers have proposed decentralized conflict avoidance strategies, where each robot takes the observable states (e.g., velocities, shapes, and positions) of other robots as inputs to make autonomous decisions. In contrast to a centralized approach, a decentralized approach can better respond to unknown or dynamic environments and has better reliability, flexibility, adaptability, and fault tolerance [40]. It can be further categorized into two approaches: the path coordination approach and the prioritized planning approach. In a path coordination approach, the robot moves in a coordinated path. If a potential collision is detected, it changes robot velocity to predefined values or even stops robots to avoid collision [19]. However, stopping or slowing down increases the time for the robot to complete the task. In practice, a widely used decentralized approach for MRPPs that has proven effective is prioritized planning. The prioritized planning algorithm assigns a unique priority to each robot and proceeds sequentially from the robot with the highest priority to the one with the lowest priority [41]. The prioritized planning approaches plan the path for each robot individually and then combine other methods to avoid collisions between robots, which include Artificial Potential Field (APF) [42], A* [43], Revised Prioritized Planning (RPP) [44], Safe Interval Path Planning (SIPP) [45], and Hybrid Path Planning (HPP) [46]. Nonetheless, the work proposed above typically focuses on interrobot collision avoidance, but deadlock avoidance and path deviation are typically not considered simultaneously.

2.2 Problem definition

We model each robot as a point that can move freely in a two-dimensional space. It is assumed that each robot is equipped with several sensors by which a robot can build a global map of the working environment. The robot may find new obstacles or robots when moving, so it also builds a local map to save dynamic information on the surrounding environment. Due to the various local information surrounding the robots, each robot’s grid map may vary slightly. All the maps mentioned above are composed of finite vertices, and some of the vertices are occupied by obstacles. The configuration of obstacles in different vertices may vary in shape, position, and occupancy level. However, this paper assumes that a vertex is either unknown, free, or entirely occupied by obstacles. The occupied vertices of the global and local maps can represent the shape and location of obstacles. The given start position and desired goal position of each robot are located in the free vertex, and MRPP can be defined as finding a finite set of free vertices to navigate each robot between the start and goal points without interrobot collisions and deadlocks [47].

Let Nr be the total number of robots in an MRS, Np be the total number of vertices in a path, ℕr = {1, 2, ..., Nr}, and ℕp = {1, 2, ..., Np}. The path of robots can be denoted as

$$ P=\left\{{p}_j^i\right\},i\in {\mathrm{\mathbb{N}}}_r,j\in {\mathrm{\mathbb{N}}}_{p,} $$
(1)

where the superscript i denotes the robot number of the MRS, and the subscript j is the vertex number of the path. We assume that it takes the same time for the robot to move from one vertex to another. Therefore, an interrobot collision will occur if ∃ x, y ∈ ℕr, x ≠ y, j ∈ ℕp, such that px j = py j. Moreover, a deadlock will occur if ∃ i ∈ ℕr, such that ∃ pi j1 = pi j2 = ... = pi jn, where ∀ n > 1, n ∈ ℕp.

2.3 D* Lite

We use D* Lite as our method’s underlying algorithm. D* Lite is a well-known goal-directed path planning algorithm and widely utilized for autonomous mobile robot navigation [48]. It can reuse the previous path planning information to replan a path dynamically. This characteristic can be applied to our method for dynamic collision avoidance between robots. The following notation is utilized to describe D* Lite: S is the set of vertices of the graph. Succ(s) ⊆ S is the set of successors of vertex s ∈ S. Pred(s) ⊆ S is the set of predecessors of vertex s ∈ S. 0 < c(s’, s) < ∞ is the cost of moving from vertex s’ ∈ Pred(s) to vertex s. D* Lite maintains two kinds of estimates of each vertex’s goal distance: a g-value g(s) and an rhs-value rhs(s). The rhs-value always satisfies the following relationship:

$$ rhs(s)=\left\{\begin{array}{ll}0,& if\ s={s}_{goal}\\ {}{\min}_{s\hbox{'}\in Succ(s)}\left(g\left(s\hbox{'}\right)+c\left(s,s\hbox{'}\right)\right),& \mathrm{otherwise}\end{array},\right. $$
(2)

where a vertex is called locally consistent if g(s) = rhs(s); otherwise, it is called locally inconsistent.

3 Methodology

This section classifies the conflict scenarios into five types according to the vertex position where the path conflicts. Before moving to the next vertex, each robot judges whether it is in any five conflict types with other robots. Then we set the AUV for the robot in conflict and replan the path.

3.1 Conflict types

Some researchers have defined conflict types for pairs of robots [49], but some scenarios have not been discussed. In a discrete gridded environment, a robot can only move to its neighboring eight vertices, so the vertex where robots collide (i.e., conflict vertex) must be one of their current vertices and neighboring vertices. In the following, robot i (Ri) is the higher priority robot, and robot j (Rj) is the lower priority robot. According to the position of the conflict vertex, we classify the conflict scenarios into five types. Let pi c and pj c be the current positions of Ri and Rj, respectively. As shown in Fig. 4, if Ri and Rj move diagonally and pi c + 1 = pj c + 1, the robots are in the Type 1 Conflict Scenario (CST1).

Fig. 4
figure 4

CST1: Robots move diagonally and their next position is the conflict vertex (i.e., brown square)

Full size image

As shown in Fig. 5, if pi c + 1 = pj c and pi c ≠ pj c + 1, the robots are in the Type 2 Conflict Scenario (CST2).

Fig. 5
figure 5

CST2: The current position of Rj is the conflict vertex

Full size image

As shown in Figs. 6, 7, 8, 9, 10, 11, 12 and 13, if pi c = pj c + 1, the robots are in the Type 3 Conflict Scenario (CST3).

Fig. 6
figure 6

CST3 when Ri moves north

Full size image
Fig. 7
figure 7

CST3 when Ri moves northeast

Full size image
Fig. 8
figure 8

CST3 when Ri moves east

Full size image
Fig. 9
figure 9

CST3 when Ri moves southeast

Full size image
Fig. 10
figure 10

CST3 when Ri moves south

Full size image
Fig. 11
figure 11

CST3 when Ri moves southwest

Full size image
Fig. 12
figure 12

CST3 when Ri moves west

Full size image
Fig. 13
figure 13

CST3 when Ri moves northwest

Full size image

As shown in Figs. 14, 15, 16, 17, 18, 19, 20 and 21, if Ri and Rj are adjacent to each other and pi c + 1 = pj c + 1, the robots are in the Type 4 Conflict Scenario (CST4).

Fig. 14
figure 14

CST4 when Ri moves north

Full size image
Fig. 15
figure 15

CST4 when Ri moves northeast

Full size image
Fig. 16
figure 16

CST4 when Ri moves east

Full size image
Fig. 17
figure 17

CST4 when Ri moves southeast

Full size image
Fig. 18
figure 18

CST4 when Ri moves south

Full size image
Fig. 19
figure 19

CST4 when Ri moves southwest

Full size image
Fig. 20
figure 20

CST4 when Ri moves west

Full size image
Fig. 21
figure 21

CST4 when Ri moves northwest

Full size image

As shown in Figs. 22, 23, 24, 25, 26, 27, 28 and 29, if pi c + 1 = pj c + 1, Ri and Rj are not adjacent, and are not in CST1, then the robots are in the Type 5 Conflict Scenario (CST5).

Fig. 22
figure 22

CST5 when Ri moves north

Full size image
Fig. 23
figure 23

CST5 when Ri moves east

Full size image
Fig. 24
figure 24

CST5 when Ri moves south

Full size image
Fig. 25
figure 25

CST5 when Ri moves west

Full size image
Fig. 26
figure 26

CST5 when Ri moves northeast

Full size image
Fig. 27
figure 27

CST5 when Ri moves southeast

Full size image
Fig. 28
figure 28

CST5 when Ri moves southwest

Full size image
Fig. 29
figure 29

CST5 when Ri moves northwest

Full size image

3.2 Artificial untraversable vertex

The AUV is the basis for the underlying path planning algorithm to replan the path to avoid collisions and deadlocks. The number and position of the AUV can be adjusted according to needs (e.g., the number of vertices occupied by a robot). In this paper, we assume that each robot occupies a vertex. We summarized three types of AUVs during the experiment, as shown in Figs. 30, 31 and 32, which produced a minimum or slight path deviation and steering angle for collision and deadlock avoidance. In Figs. 30-32, according to the coordinate and direction of robot R, the AUV is set for the original robot (Ro), which conflicts with R. There are eight cases for each type of AUV corresponding to the eight moving directions of R. Figure 30 shows the cases for Type 1 AUV (AUVT1), which is applied to both higher priority and lower priority robots. The AUVT1 set for RO is shown in Fig. 30 (a) when R moves northward and Figs. 30 (b)-(h) correspond to the other seven moving directions.

Fig. 30
figure 30

Illustration of AUVT1. The vertex with the term R is the current position of R, and the arrow signifies its direction. The black vertex represents the AUV set for the robot Ro

Full size image
Fig. 31
figure 31

Illustration of AUVT2

Full size image
Fig. 32
figure 32

Illustration of AUVT3

Full size image

Figure 31 presents the eight cases for Type 2 AUV (AUVT2) applied to the lower priority robots. The AUVT2 set for RO is shown in Fig. 31 (h) when R moves northwest, and Fig. 31 (a)-(g) correspond to the other seven moving directions.

Figure 32 shows eight cases for Type 3 AUV (AUVT3), and it is applied to the lower priority robots. The AUV set for RO is shown in Fig. 32 (h) when R moves northwest, and Fig. 32 (a)-(g) corresponds to the other seven moving directions.

Figures 33, 34, 35, 36 and 37 list the solution for CST1–5. Robot Ri is the higher priority robot, and robot Rj is the lower priority robot. The graph is an eight-connected grid whose edge costs are initially one and change to infinity when the robot discovers that the vertices cannot be traversed [48]. We assume that the dynamic environment map range is the 48 vertices in the shadow around the robot. For CST1 in Fig. 4, we make the higher priority robot Ri continue to move along its established path, and the lower priority robot Rj bypasses the brown conflict vertex, that is, pi c + 1 is set as the AUV for robot Rj. Taking Fig. 4 (a) as an example, we set vertex G4 as the AUV for Rj as shown in Fig. 33, and Rj’s moving direction changes to the south.

Fig. 33
figure 33

Solution for CST1 (taking Fig. 4 (a) as an example). The vertex G4 is the AUV for Rj, the black square is the AUV for the robot Rj, the green and red squares are the robot and goal positions, and the blue and red arrows are the initial and modified directions

Full size image
Fig. 34
figure 34

Solution for CST2 (Taking Fig. 5 (a) as an example). a The AUV for Ri. b The AUV for Rj

Full size image
Fig. 35
figure 35

Solution for CST3 (Taking Fig. 6 (a) as an example). a The AUV for Ri. b The AUV for Rj

Full size image
Fig. 36
figure 36

Solution for CST4 (Taking Fig. 18 (a) as an example). a The AUV for Ri. b The AUV for Rj

Full size image
Fig. 37
figure 37

Solution for CST5 (Taking Fig. 22 (a) as an example). a The AUV for Rj. b The robots after moving one step

Full size image

For CST2 in Fig. 5, we make the lower priority robot Rj continue to move along its established path because its direction does not conflict with Ri. To make Ri’s modified path not conflict with Rj’s established path, we considered both Rj’s position and direction to set the AUV for Ri. Moreover, Rj is also likely to update its path due to other robots. Thus, we set the AUV for both Ri and Rj according to AUVT1. Taking Fig. 5 (a) as an example, the AUVs for Ri and Rj are set as shown in Fig. 34, and Ri’s direction changes to the northwest.

For CST3 in Figs. 6-13, pj c + 1 is occupied by Ri, so Rj should replan its path, and Ri needs to bypass Rj’s current vertex. In MR-D* Lite, we replan the path of robots from the higher priority to the lower priority. Therefore, we set Rj’s current vertex as the AUV for Ri and set the AUV for Rj according to AUVT1. Taking Fig. 6 (a) as an example, we set the AUV as shown in Fig. 35. After the replanning process, Ri’s direction changes to the northeast, and Rj’s direction changes to the southwest.

For CST4 in Figs. 14-21, we make the higher priority robot Ri continue to move along its established path. However, to prevent Ri’s modified path (Ri is likely to update the path due to other robots in MRS) from conflicting with Rj’s current vertex, we set Rj’s current vertex as the AUV for Ri. Then, we set the AUV for Rj according to AUVT1. That is, the solution for CST3 is the same as that for CST4. Taking Fig. 18 (a) as an example, the AUV is set as shown in Fig. 36, and Rj’s direction changes to the northwest.

For CST5 in Fig. 22-29, we make Ri continue to move along its established path and set the AUV for Rj according to AUVT2. Taking Fig. 22 (a) as an example, corresponding to Fig. 31 (a), the AUV for Rj is set as shown in Fig. 37 (a), and Rj’s direction changes to south. Note that all AUVs are cleared after the robot moves to the next vertex. Therefore, after the robots in Fig. 37 (a) move one step and reach the position in Fig. 37 (b), all the AUVs for Rj have disappeared. Then, the path is replanned again, and Rj’s direction changes to the original southeast.

The method mentioned above can solve conflicts between any two robots, but there is a problem of crowding between robots for the MRS with three or more robots. For example, if the robots in Fig. 38 (a) reach the position in Fig. 38 (b), then it is challenging to replan a collision-free path for each robot. AUVT3 is employed to address this problem, as shown in Fig. 39.

Fig. 38
figure 38

A problematic situation for the MRS of three or more robots. a Initial positions of robots. b Robots crowded together

Full size image
Fig. 39
figure 39

Solution for crowding between robots (with Fig. 38 (a) as an example). a The AUV for R2. b The AUV for R3. (c) The AUV for R4

Full size image

If the vertices pi c + 1 and pj c + 1 are adjacent to each other, we set the AUV for the lower priority robot according to AUVT3. With Fig. 38 (a) as an example, the AUV for the robots is set as shown in Fig. 39. In Fig. 38 (a), the lower priority robot R2 detects that p2 c + 1 is adjacent to p1 c + 1. Thus, corresponding to Fig. 32 (f), we set the AUV for R2 as shown in Fig. 39 (a), and its direction changes to the west after replanning the path. In Fig. 39 (a), the lower priority robot R3 detects that p3 c + 1 is adjacent to p1 c + 1. We set the AUV for R3 as shown in Fig. 39 (b), and its direction changes to the northeast. In Fig. 39 (b), the lower priority robot R4 detects that p4 c + 1 is adjacent to t p1 c + 1. We establish the AUV for R4 as shown in Fig. 39 (c), and its direction changes to the north.

In summary, the method of setting the AUV for robots is as follows:

  • For the CST1 in Fig. 4, we set the conflict vertex as the AUV for Rj.

  • For CST2 in Fig. 5, we set the AUV for Ri and Rj according to AUVT1.

  • For CST3 and CST4 in Figs. 6-21, we set pj c as the AUV for Ri and set the AUV for Rj according to AUVT1.

  • For CST5 in Figs. 22-29, we set the AUV for Rj according to AUVT2.

  • If pi c + 1 and pj c + 1 are adjacent to each other, we set the AUV for Rj according to AUVT3.

  • If pi c and pj c are adjacent to each other, we set pi c and pj c as the AUVs for each other.

3.3 Multi-robot D* lite

We now use D* Lite and AUV to develop our MR-D* Lite, whose pseudocode is shown in Fig. 40. The definitions of symbols used in the pseudocode are summarized in Table 1. Similar to the D * Lite algorithm, MR-D* Lite maintains two kinds of estimates of the goal distance of each vertex: a g-value g(i, s) and an rhs-value rhs(i, s), where i denotes the robot number of the MRS. The rhs-value always satisfies the following relationship:

Fig. 40
figure 40

The pseudocode for MR-D* Lite

Full size image
Table 1 Symbol definitions for MR-D* Lite
Full size table
$$ rhs\left(i,s\right)=\left\{\begin{array}{ll}0,& if\ s={s}_{goal}\\ {}{\min}_{s\in Succ(s)}\left(g\left(i,s\right)+c\left(i,s,s\ \right)\right),& \mathrm{otherwise}\end{array}\right., $$
(3)

where a vertex is called locally consistent for Ri if g(i, s) = rhs(i, s); otherwise, it is called locally inconsistent. The distance between vertex s and sstart(i) uses the Chebyshev distance:

$$ h\left({s}_{start(i)},s\right)=\max \left(\left|{x}_{s_{start(i)}}-{x}_s\right|,\left|{y}_{s_{start(i)}}-{y}_s\right|\right), $$
(4)

where xs and ys symbolize the x-coordinate and y-coordinate of vertex s, respectively.

The functions CalcKey(), Initialize(), UpdateVertex(), and ComputeShortestPath() in D* Lite remain unchanged to plan the initial paths and modify them when potential conflicts are detected and the environmental information changes. However, the function Main() needs to be extended, and the functions UpdatePath() and ScanGraph() are introduced to address the collisions and deadlocks between different robots. The main function Main() first calls Initialize(i) to initialize the search problem for each robot {58}. (Numbers in curly brackets refer to line numbers in the pseudocode.) Initialize(i) sets the initial g-values of all vertices of Ri to infinity and sets their rhs-values according to Eq. (3) {04–05}. Note that in an actual implementation, Initialize(i) only needs to initialize a vertex when Ri encounters it during the search [50]. MR-D* Lite then computes the shortest path from the current vertex of Ri to the goal vertex {59}. After robots have calculated their initial paths {56–59}, they move forward along their respective paths. As the robot moves to the target vertex, MR-D* Lite uses the function UpdatePath(i) to monitor potential conflicts and update the path to achieve collision and deadlock avoidance {63}. UpdatePath(i) clears the AUV set for Ri previously and updates Ri’s path by ScanGraph(i) {30–31}. It sets the AUV for Ri and updates the path according to the type of conflict {32–55}. A robot first monitors potential conflict with higher priority robots and executes the corresponding strategy {32–46}. Then, the robot monitors potential conflicts with lower priority robots and executes the corresponding strategy {47–55}. Finally, all robots have a collision-free and deadlock-free path, and each robot updates sstart(i) to reflect the current vertex of the robot and makes one transition along the path {64–67}.

In the pseudocode, we have included a comment on how the robot can detect there is no path {65} but do not prescribe what it should do in this case. For the goal-directed navigation problem in unknown static terrain, if there is no path because of obstacles, the robot should stop and announce there is no path [50]. However, if a robot cannot find the path due to the AUV (e.g., robots are in a narrow passage or corner), then it should stop moving temporarily and wait for the next iteration to update the path.

Figure 41 displays a general flowchart of a robot Ri in the MRS that is executed in the implementation. The robots first plan their initial paths without considering other robots. Then, the conflict avoidance strategy between robots is implemented when the robot moves along its original path. Before robot Ri moves to the next vertex, it checks whether there is a conflict with the other robots in order of priority from high to low. If there is a conflict, MR-D* Lite sets the AUV for Ri and then replans its path. After all other robots are checked, robot Ri moves one step and then repeats the procedure until it eventually reaches the goal coordinates.

Fig. 41
figure 41

Path planning of a robot (Ri) in MRS, where Rh indicates the robot with the highest priority among the unchecked robots

Full size image

3.4 Example

We now step through the example of Fig. 1 to show the operation of MR-D* Lite. Figure 42 (a) and (b) show the heuristics of R1’s and R2’s traversable cells, which approximate the distance from a cell to the start cell with the maximum absolute differences of the x and y coordinates of both cells. Figure 42 (c)-(l) shows the g-values and rhs-values of the traversable cells. The start cells of R1 and R2 are C1 and E2, and the goal cells are C5 and A2. The cell with a bold border is the current cell of the robot. Figure 42 (c) and (d) show the values after the first call Initialize(1) and Initialize(2). Figure 42 (e) and (f) show the values after the first call ComputeShortestPath(1) and ComputeShortestPath(2). The robot follows the path from the start to the goal cell by always moving from the current vertex s, starting at the start cell, to any successor that minimizes c(s, s’) + g(s’) (i.e., the rhs-value in Fig. 42) until the goal cell is reached. Thus, as shown in Fig. 42 (e) and (f), the original path of R1 is C1 – C2 – C3 – C4 – C5, and the original path of R2 is E2 – D2 – C2 – B2 – A2. Therefore, the robots are likely to collide at C2. After the first call UpdatePath(1) and UpdatePath(2), R1’s path remains unchanged, but R2’s path changes, as shown in Fig. 42 (h). Each robot then follows the path from its current cell to the goal cell. Therefore, R1 moves the first step to C2, and R2 moves the first step to D2. Before the robots move the second step, MR-D* Lite calls UpdatePath(1) and UpdatePath(2) again, and the previous AUVs are cleared. The path of the robot after the first replanning no longer conflicts. However, the vertices where the robots are located are set as each other’s AUV, as shown in Fig. 42 (i) and (j), because they are adjacent. The paths of robots remain unchanged, and R1 and R2 move to C3 and C1, respectively. Before the robots move the third step, MR-D* Lite calls UpdatePath(1) and UpdatePath(2) for the third time. The previous AUVs are cleared, and no new AUVs are set. Each robot follows its remaining path from the current cell to the goal cell without observing other conflicts or obstacles and thus without changing the g-values and rhs-values.

Fig. 42
figure 42figure 42

Operation of MR-D* Lite. (a) The heuristics of R1’s traversable cells. b The heuristics of R2’s traversable cells. c Initialization of R1. d Initialization of R2. e R1’s original path. f R2’s original path. g R1’s path after the first call UpdatePath(1). h R2’s path after the first call UpdatePath(2). i R1’s path after the second call UpdatePath(1). j R2’s path after the second call UpdatePath(2). k R1’s path after the third call UpdatePath(1). l R2’s path after the third call UpdatePath(2)

Full size image

4 Experimental results

We tested MR-D* Lite in experiments run on a Xeon E5 computer at 2.10 GHz with 16 Gb of RAM. The priority of the robots is R1 > R2 > R3 > R4 > R5. We assume that each robot occupies a vertex in the grid map, and it takes the same time for a robot to move from the current vertex to the next vertex. As shown in Fig. 43, the green and red squares are the start vertex and goal vertex of a robot, and the red and green lines are the trajectories of R1 and R2, respectively. The yellow square is the vertex where the trajectories overlap. The experimental results in Fig. 43 correspond to the four cases of CST1 in Fig. 4.

Fig. 43
figure 43

Experiment results of CST1

Full size image

The experimental results in Fig. 44 correspond to the eight cases of CST2 in Fig. 5. Note that in some cases, because MR-D* Lite gives robots the ability to deal with potential conflict scenarios in advance (taking Fig. 44 (a) as an example), the robot does not reach the position in Fig. 5 (a).

Fig. 44
figure 44

Experiment results of CST2

Full size image

For CST3, CST4, and CST5, many scenarios correspond to the eight moving directions of the higher priority robot. Due to symmetry, we only list the experimental results when the higher priority robot R1 moves north and northeast, where the simulation results in Figs. 45 and 46 correspond to CST3 in Figs. 6 and 7, the results in Figs. 47 and 48 correspond to CST4 in Figs. 14 and 15, and the results in Figs. 49 and 50 correspond to CST5 in Figs. 22 and 26. The simulation results in Figs. 43, 44, 45, 46, 47, 48, 49 and 50 show that MR-D* Lite can successfully resolve the conflict scenario mentioned in Section 3.

Fig. 45
figure 45

Experiment results of CST3 when R1 moves north

Full size image
Fig. 46
figure 46

Experiment results of CST3 when R1 moves northeast

Full size image
Fig. 47
figure 47

Experiment results of CST4 when R1 moves north

Full size image
Fig. 48
figure 48

Experiment results of CST4 when R1 moves northeast

Full size image
Fig. 49
figure 49

Experiment results of CST5 when R1 moves north

Full size image
Fig. 50
figure 50

Experiment results of CST5 when R1 moves northeast

Full size image

Experiments are conducted with more robots to validate the flexibility of the proposed algorithm. Figure 51 shows the conflict avoidance trajectories of the three robots, that is, R1 (red line), R2 (green line), and R3 (blue line).

Fig. 51
figure 51

Collision avoidance trajectories of three robots

Full size image

Figure 52 shows the conflict avoidance trajectories of four robots, that is, R1 (red line), R2 (green line), R3 (blue line), and R4 (white line), where Fig. 52 (a) is the experimental result of the scenario shown in Fig. 38 (a).

Fig. 52
figure 52

Collision avoidance trajectories of four robots

Full size image

Figure 53 shows the conflict avoidance trajectories of five robots: R1 (red line), R2 (green line), R3 (blue line), R4 (white line), and R5 (magenta line). The experimental results in Figs. 51-53 show that MR-D* Lite can successfully avoid collisions with obstacles and other robots. Figures 51 (a), 52 (a), and 53 (a) show that the algorithm can solve the problem of many robots being concentrated at a single choke vertex.

Fig. 53
figure 53

Collision avoidance trajectories of five robots

Full size image

We compare MR-D* Lite against three other MRPP algorithms: FIS, APF, and HPP [46]. As shown in Fig. 54, the experimental environment is a two-dimensional space of 100 × 100 rectangle, where the term Si denotes the start position of Ri and Gi denotes the target position. Table 2 lists the coordinates of the start position and goal position of robots.

Fig. 54
figure 54

Trajectories of five robots under different algorithms. a MR-D* Lite. b FIS. c APF. d HPP

Full size image
Table 2 Initial and target position of robots
Full size table

The performance of the experimental results is first analyzed in terms of trajectory distance, by which we can minimize energy and time consumption. The MR-D* Lite algorithm first plans a globally optimal path for each robot and modifies the established path when a potential conflict between the robots is detected. The robots using the other three algorithms plan their paths while moving according to the surrounding environment’s information. Therefore, the robots using MR-D* Lite can typically generate a shorter trajectory, which is reflected in Table 3.

Table 3 Trajectory distance under different algorithms
Full size table

One of the goals of MRPP is to ensure that any action taken to avoid a collision with another robot in real-time does not adversely affect the optimal planned route beyond the minimum extra effort required to avoid the collision [51]. Thus, the performance of the experimental results is analyzed in terms of the path deviation. Table 4 lists the robot’s path deviation under different algorithms, which is the trajectory distance minus the linear distance between the initial position and the target position. In MR-D* Lite, the method to resolve conflicts between robots is replanning the path based on the AUV. The other three algorithms mainly resolve conflicts by generating a repulsive force between robots. Therefore, as shown in Table 4, the other three methods may produce more unnecessary detours.

Table 4 Path deviation under different algorithms
Full size table

Table 5 lists the computational time of different algorithms to solve the conflicts between robots. MR-D* Lite avoids interrobot collisions and deadlocks by bypassing the AUV, and other algorithms need to make the robot escape the predefined danger zone to address the problem. The AUV contains up to 11 vertices, and the danger zone may contain a large number of vertices. Therefore, MR-D* Lite takes less time for robots to resolve conflicts.

Table 5 Time consumption of resolving conflicts, in seconds (s)
Full size table

5 Conclusions

This paper introduces a multi-robot version of a well-known single-robot path planning algorithm D* Lite. The proposed method resolves collisions and deadlocks between multiple robots while maintaining the robustness and real-time performance of the D* Lite algorithm. Thus, MR-D* Lite can tolerate inaccuracies in a map and fast replan a conflict-free path. The experimental results show that MR-D* Lite outperforms the remaining three algorithms in path deviation and replanning time. However, in this paper, the conflict is not detected until it almost happens, so sometimes the robot needs a large steering angle to avoid the collision. In the future, further efforts are needed to solve the problem.