A Decentralized Method Using Artificial Moments for Multi-Robot Path-Planning

Abstract

For the local path-planning of multi-robots, a decentralized method is presented where each robot plans its own path in the following steps for each iteration. Firstly, an optimal way representative point (OWRpoint) is obtained for guiding the robot to move along a shorter path. Then, the robot moves a step under the control of its own motion controller, which is designed based on artificial moments. In the motion controller, attractive and repulsive moments are used to move robots closer to their OWRpoints and away from obstacles, while coordinated moments are used to resolve the conflicts between robots. Two simulations are given to test the method and the results indicate that the method is valuable as it meets the requirements of the real-time property while optimizing the performance measure of each robot: namely, the path travelled to reach the robot's target.

Keywords

Multiple Mobile Robots Path-Planning Motion Control Collision Artificial Moments

1. Introduction

As remarked upon in [1], there has been a growing interest in multi-robot systems in recent years and motion planning is of primary importance in the design of multi-robot systems. This paper focuses on a version of the problem that concerns the path-planning of multiple autonomous mobile robots. The environment is populated with various obstacles. No robot has a priori knowledge about the environment or other robots. The objective is to simultaneously bring each robot from an initial position to an independent target. In addition to ensuring collision avoidance, each robot has a performance measure - the path travelled to reach its target - to be optimized.

As no robot has a priori knowledge, the problem is a form of local or online path-planning for multi-robots [2]. As individual performance measures are not combined into a single scalar criterion, the problem differs from that discussed in [3], [4], where the criterion is to minimize the time taken by the last robot to reach its target. As remarked upon in [5], when individual performance measures are combined, certain information about potential solutions and alternatives are lost. For example, the degree of sacrifice that each robot makes in order to avoid other robots is not usually taken into account.

Many approaches have been developed for multi-robot path-planning, which are often categorized as centralized or decentralized [5], [6], [7]. With centralized methods, a central planner designs the motion plan for all of the robots based on full knowledge about the environment. Decentralized approaches require that each robot plans its own path based only on the locally available information - e.g., the positions of neighbouring robots - so that it requires less computational resources and also ensures the scalability of the system.

Obviously, only decentralized approaches can be used for the local path-planning of multi-robots as no robot has full knowledge about the environment or other robots.

In [2], [8], [9], a decentralized method based on evolutionary algorithms (EAs) or differential evolution algorithms is discussed, where n EAs are used for n robots and the i-th EA determines the next position for the i-th robot during each iteration, satisfying the necessary constraints associated with that robot and certain cooperation objectives related with the others. In [10], [11], prioritized planning is discussed, which works as follows. First, priorities are assigned to the robots. Then, in order of decreasing priority, the robots are picked. For each picked robot, a path is planned, avoiding collisions with obstacles as well as with the previously picked robots. The drawback of the two methods is the requirement of a considerable amount of communication.

In recent years, the artificial potential field (APF) method is extended to multi-robot path-planning [12], [13]. Here, a repulsive potential field to force a robot away from obstacles or other robots and an attractive field to drive the robot close to a target are employed to generate a force. The force equals the negative gradient of the total potentials and makes the robot move from a position with higher potentials to one with lower potentials. This method requires only a simple calculation and no pre-processing of the environment, but powerful results and elegance of output are generated in a short time [12], [14]. However, this method suffers from many problems [12], [13], [14], [15], such as the “local minimum” problem. When it is used for multi-robot path-planning, coordination between robots is difficult to obtain through the pure APF method as robots cannot be regarded as simply obstacles, and as such some other techniques, such as priorities, have to be used [12], [13].

The configuration space method [12], [16], [17] and the free space method [16], [18], [19] are the methods directly used not only for multi-robot path-planning but also as the basis of other methods, such as the probabilistic roadmap method [20]. In the configuration space, the original problem of planning the motion of a robot through a space of obstacles is transformed into an equivalent - but simpler - problem of planning the motion of a point through a space of enlarged configuration space obstacles or pseudo-obstacles. The free space method is to search the free space directly without first transforming the problem into a configuration space. A representation of a free space can be obtained using generalized Voronoi diagrams [16], a tangent graph [18] or a visibility graph [19]. The drawback of the two techniques is that in local path-planning the configuration space or the free space is frequently required to be recomputed, considering the safe distance and the sizes of the robots. Again, a great deal of computation is needed.

In fact, and to the best of our knowledge, although many algorithms have been developed for the local path-planning of multi-robots, very few can not only meet the requirements of a real-time property but also optimize each robot's performance measure well. Activated by the limitation noted above, a decentralized method is proposed for multi-robot path-planning, which is an extension of the artificial moment method for multi-robot formation control [21], [22].

In the proposed method, each robot which has not reached its target or which is required to cooperate with other robots uses a path planner, which works as follows. At each sampling time, an optimal way representative point (OWRpoint), which can guide the robot in moving along a shorter path, is obtained firstly, ignoring the presence of other robots. Then, a motion controller based on artificial moments causes the robot to move a step to the next position. The above process is repeated until the task is fulfilled. The proposed method is valuable as it not only meets the requirements of a real-time property, but it also optimizes the independent performance measure of each robot well.

The rest of this paper is organized as follows. In section 2, the problem under discussion is formulated and some concepts are defined. In section 3, the techniques and algorithms for computing OWRpoints are presented. In section 4, a motion controller based on artificial moments is designed. In section 5, the algorithm for the path-planning is given. Several simulations are given and analysed in section 6 and certain conclusions are drawn in section 7.

2. Problem formulation and basic definitions

2.1 Problem Formulation

This paper focuses on the path-planning of multi-robots in a bounded planar environment which is populated with static polygonal obstacles.

A robot model is a square, as shown in Fig. 1, which has a principal motion direction line (PMDline) such as that in [21], [22] and two coordinated segments. The PMDline of a robot is a ray starting from the robot's position (the centre) and can indicate the robot's posture or motion direction.

Figure 1.

Associated model

A target model is a static point with a PMDline, as shown in Fig. 1. The PMDline of a target indicates the target's posture.

We rotate a directed line (ray, directed segment) around its start-point until its direction is the same as that of the X-axis of the global coordinate system. As such, the angle formed by the rotation is the direction angle of the line if the angle's absolute value is not larger than π. Assume that β_i and β_i are the direction angles of directed lines l_i and l_j and that n is an integer and function:

agl (x) = {\begin{matrix} \begin{matrix} x - 2 (n - 1) π sign (x) & 2 (n - 1) π \leq | x | \leq 2 n π - π & ​ \end{matrix} \\ \begin{matrix} x - 2 n π sign (x) & 2 n π - π < | x | < 2 n π & ​ \end{matrix} \end{matrix}

(1)

Then, the angle β=agl(β_i-β_j) is the angle from l_i to l_j.

For convenience, certain notations which will be used throughout this paper are listed as follows.

D_R, S_R: the side length and longest step length of a robot;

D_V: the valid radius of a robot's sensor;

D_S: a constant which is larger than 2S_R+D_R and is associated with the robots' safeties;

D_M: a positive constant less than D_S;

δ_θ²: a constant which is less than π/2 but not π/4;

δ_θ¹: a positive constant far less than δ_θ²;

λ₁, λ₂ two constants satisfying 0 <λ₁<λ₂<1;

λ_π: a constant whose value is π/DS;

R_i, T_i: the i-th robot and the target of the i-th robot;

β_Ri, β_Ti: the PMDline direction angles of R_i and T_i;

P_Ri: the position (the centre) of R_i;

(x_Ri, y_Ri)^T: the position coordinates of R;

P_Mi: a point on R_i's PMDline with a distance D_M from P_Ri;

(x_Ti, y_Ti)^T: the position coordinates of T_i;

A₁ A₂: the line segment with end points A₁ and A₂;

D_S(A₁, A₂): the directed line segment from A₁ to A₂;

β(A₁, A₂): the direction angle of DS(A₁, A₂);

RL(A₁, A₂): a ray starting from A1 and passing through A2;

| W|: the length of a continuous curve W;

∂(W,-A₁,…,-A_n): points on W except for points A₁, …, A_n;

∂(RL(A₁, A₂), -A₁ A₂): points on RL(A₁, A₂) except for those

on A₁A₂; A₁A₂… A_n: a polyline with vertices A₁, A₂, …, A_n. For an arbitrary variable V, V(k) denotes its value at time tk and V denotes it at the present.

A robot's coordinated segments are two directed segments whose lengths are DS+DR, the start-points are the robot's position while angles to the PMDline are ±π, as shown in the model of Ri in Figure 1. The coordinated segments are important in resolving the conflicts between robots.

The robot sensors are omni-directional. For a point F, only when P_RiF does not pass through any obstacle (including robots) and | P_RiF | ≤ DV, can F be detected by Ri. For two robots, only when the segment between their positions does not pass through any obstacle and is shorter than DV can they be detected and their positions and PMDlines be known by each other.

For example, in Figure 1 only R and its PMDline, as well as the points within the region with a grey colour or on the boundaries of the region, can be detected by R at present. The point A1 can be detected by R at Ri 's initial position but cannot be detected at Ri 's current position.

As it is important to reduce the communication required between robots to the absolute minimum (otherwise realtime dynamic planning will not be possible) there is no explicit communication between robots in this paper. That is to say, a robot has no knowledge about other robots until it detects them and, then, it knows - and only knows - their positions and PMDlines at the present. A robot also has no a priori knowledge about its workspace.

Assumption 1. At each sampling time, each robot knows the position and the PMDline's direction angle of its target through communication or through other means.

Assumption 2. For each robot, there is at least one feasible way between its target and its initial position which is not narrower than 2DS (ignoring other robots). Once the models, assumptions, sensing capabilities and communication protocols highlighted above have been detailed, the problem reduces to finding out a motion control algorithm that will enable each robot to avoid potential collisions with the remaining robots and any other obstacles present, reaching its target in a finite time. When a robot R reaches T_i, R_i is required to achieve the same posture as that of T_i as much as possible while its travelling path is also required to be as short as possible.

Remark 1. When R_i reaches T_i, the requirement for R_i to achieve the same posture as that of T_i is the requirement for |β_Ri-β_Ti| to be as small as possible, which is beneficial for certain applications, such as formation control [21], [22].

2.2 Basic Definitions

Definition 1. Assume Σ is a polyline on the boundary of an obstacle. If all of the points on Σ have been detected by Ri at the current time or at previous times, and Σ* has at least one point which has never been detected by R_i when Σ* is a continous curve on the same obstacle as Σ and Σ*⊃Σ, then Σ is a knowledge obstacle wall of R_i.

For example, in Figure 1, A₁A₂A₃A₄ is a knowledge obstacle wall of Ri and A₁, A₂, A₃, A₄ are its vertices; A₁A₂ A₃A₄A₅ is not so because some points on it, such as A5, have never been detected by R_i.

Each robot will memorize and update all of its knowledge obstacle walls.

Definition 2. Assume that two points F₁ and F₂ are the ends of a continuous curve W and that S is a set such that its members are all continuous curves with ends F₁ and F₂, and that all points on its members are on or very close to W. Σ is a knowledge obstacle wall of Ri. 1) If for any curve W* in S, ∂(W*, -F₁, -F₂) shares at least one point with Σ, then W is blocked by Σ. 2) If Σ blocks P_RiT_i, then Σ is a block wall of R_i. 3) If a continuous curve from R_i to T_i cannot be blocked by R_i 's block walls, it is a free block-wall way of R_i.

For example, in Figure 1, A₁A₂A₃A₄ is a block wall of R; PRiA 4 Ti and P_RiA₂A₁A₃T_i are free block-wall ways of Ri, but P_RiA₂A₃T_i is not because it is blocked by A₁A₂A₃A₄.

The shortest free block-wall way is important as a shorter, feasible way can be easily obtained through it. Furthermore, compared with the shortest feasible way obtained by such methods as the tangent graph method and the configuration space method, the shortest free block-wall way is easier to obtain as there is no requirement to consider the safe distance of robots and no requirement to pre-process the environment.

As obstacles are all polygons, the shortest free block-wall way of R must be a polyline. Assume it is P_RiA₁A₂,…,A_nT_i; then, the first vertex A₁ but not the full way is needed to be obtained for guiding R_i to move. The reasons for this are that, as the shortest free block-wall way of R_i at present is often significantly different from that at the next in local path-planning, it is effective only at the present.

Moreover, at the current time, A₁ has the same effect as the full way for optimizing R_i 's path but is easier to obtain and requires less memory.

Definition 3. The first vertex A₁ of the shortest free block-wall way of R_i is the optimal way representative point of R (OWRpoint_i) at present.

For example, when P_RiT_i is not blocked by any knowledge obstacle wall of R_i, T_i is the OWRpointi.

Definition 4. For two robots R and R, if R can be detected by R_i and |P_miP_mj|<D_s+2D_R, then R_j is a coordinated companion of R_i.

For example, in Figure 1, R_i and R_j are coordinated companions of each other.

Obviously, a dangerous wall representative point of R_i is the point that is the shortest distance from PRi in a local region of a dangerous knowledge obstacle wall. Accordingly, for R_i, several such points may exist on the same knowledge obstacle wall, which can prevent R_i from colliding with one side while avoiding another side of the wall.

Definition 6. Assume that F is a point on a free block-wall way of R and that A₁ is a point on a knowledge obstacle wall Σ of R. 1) If ∂(RL(F, A₁), -FA₁)∩Σ is null and RL(F, A₁) is not blocked by Σ, then RL(F, A₁) is a single-direction tangent of R from F to Σ and A₁ is the tangent point. 2) When Σ(RL(F, A₁), -FA₁)Σ is not null, assume that A₂ is the point that is the shortest distant from A1 in the set. If FA₂ is not blocked by Σ and if a closed curve by which T_i and F are separated can be formed by A₁A₂ and a part of Σ, then RL(F, A₁) is a close tangent of R from F to Σ and A₁ and A₂ are the tangent and close point respectively.

For example, in Figure 2, RL(P_Ri, A₄) is a single-direction tangent from P_Ri to Σ and A₄ is the tangent point. RL(P_Ri, A₁) is a close tangent from P_Ri to Σ₁ (Σ₂ and Σ₁ are merged into one wall by an artificial obstacle segment V₃V₄) and A₁ and F₁ are the tangent and the close point respectively. RL(A₁, A₂), RL(A₂, A₃) are close tangents of R.

Figure 2.

Single-direction and close tangents, artificial obstacle segments

3. Method for OWRpoints

In this section, a method is presented to determine a series of OWRpoints which guide each robot to move along a shorter path. The first step of this method is to set artificial obstacle segments according to the rules given as follows until no such segments can be set. Since such segments can block these ways onto which the OWRpoints are not suitably placed, the computation of the OWRpoints is decreased by setting such segments.

3.1 Rules for Setting Artificial Obstacle Segments

There are two types of artificial obstacle segments, namely narrow-types (N-type) and back-types (B-type).

The rule for N-type artificial obstacle segments is as follows. For two points A₁ and A₂ on knowledge obstacle walls of R_i, if |A₁A₂| is less than 2DS and a free block-wall way of R_i passes through A₁A₂ once and once only, then A₁A₂ can be set as an N-type artificial obstacle segment. For example, in Figure 2, V₃V₄ is an N-type artificial obstacle segment of Ri.

N-type artificial obstacle segments are used to prevent a robot from walking along ways narrower than 2DS, as if two robots encounter each other in a way that is narrower than 2DS, they may be blocked by each other such that their convergence is lost. As remarked upon in [6], the loss of convergence in this case is not a matter of a good or a bad algorithm - it is due to the decentralized control model.

The rules for B-type artificial obstacle segments are as follows. For R_i, assume Σ₁ and Σ₂ are two different knowledge obstacle walls and that Σ₁ blocks P_RiT_i. 1) If Σ₂ also blocks P_RiT_i, then A₁A₂ can be set as such a segment, where A₁ and A₂ are the intersections of P_RiT_i with Σ₁ and Σ₂ respectively. 2) Assume that A₁ is the tangent point of a close or single-direction tangent from P_Ri to Σ₁. If Σ₂ blocks P_RiA₁ and A₂ is an intersection of P_RiA₁ with Σ₂, then A₁A₂ can be set as such a segment.

For example, V₁V₂ in Figure 2 is a B-type artificial obstacle segment of R_i. Obviously, for R_i, if A₁A₂ can be set as a B-type artificial obstacle segment at present, then no point (except for A₁ and A₂) on A₁A₂ can be detected at present; however, A₁A₂ may have been detected at some previous time because A₁ and A₂ are all on knowledge obstacle walls. That is to say, R_i has moved from a position with a shorter distance from A₁A₂ to the current one with a longer distance. Thus, walking towards A₁A₂ will result in walking backwards, which is the reason for calling such segments B-type artificial obstacle segments.

Setting B-type artificial obstacle segments has two main benefits. One is to guarantee the global convergence to a certain extent by preventing a robot from walking backwards. The second is to decrease the total number of knowledge obstacle walls of a robot by merging two different walls into one wall.

Conclusion 1. If no artificial obstacle segment can be set by Ri at present, then: 1) P_RiT_i is blocked by at most one knowledge obstacle wall; 2) assume that Σ is a block wall of R_i and that A₁ is the tangent point of a close or single-direction tangent of R_i from P_Ri to Σ. Then, P_RiA₁ will not be blocked by any knowledge obstacle wall.

Artificial obstacle segments are dealt with as a part of knowledge obstacle walls in general. However, if a closed curve by which R_i and T_i are separated is formed by a knowledge obstacle wall of R_i, then all B-type artificial obstacle segments on the wall will be removed.

3.2 Algorithm to Determine OWRpoints

For R_i, after setting artificial obstacle segments, an OWRpoint will be obtained, which is based on the following conclusions.

Conclusion 2. If Σ is a block wall of R_i, no close tangent from P_Ri to Σ exists, and if A₁ is the tangent point of a single-direction tangent from P_Ri to Σ, then a polyline PR_iA₁A₂…A_nT_i represented with FBW_A1 can be obtained by algorithm 1.

Algorithm 1 Obtaining the vertices on FBW_A₁.

1: Let A₀ =PR_i, A_l = A₁ and, then, go to step 2.

2: If A_lT_i is not blocked by Σ, then stop. Otherwise, go to step 3.

3: If a close tangent from A_l to Σ exists, then the tangent point is A_l₊₁. Let A_l = A_l₊₁ and then return to step 2. Otherwise, go to step 4.

4: If A_l =A₁, then A2 is the tangent point of the single-direction tangent from A1 to Σ such that A₀A₂* is blocked by Σ, where A₂* is a point on A1A2 and close to A₁. Otherwise, A_l ₊₁ is the tangent point of the single-direction tangent from A_l to Σ that shares no point with RL(A_l-2, A_{l -}₁). Let A_l = A_l ₊₁; then return to step 2.

Conclusion 3. Assume that no artificial obstacle segment can be set by R_i at present and that Σ is a block wall of R_i. For R_i, if a close tangent from P_Ri to Σ exists, then the tangent point is the OWRpointi; otherwise, A₁ or Q₁ is the OWRpointi as FBW_A₁ or FBWQ1 is the shortest free block-wall way, where A₁ and Q₁ are the tangent points of the two single-direction tangents from PRi to Σ.

Based on previous discussion, an algorithm for the OWRpointi at present is given as follows.

Algorithm 2 Obtaining the OWRpointi at present.

1: If Ri has no block wall, then T_i is the OWRpointi; otherwise, go to step 2.

2: Assume that Σ is a block wall of R_i. If a close tangent from PRi to Σ exists, then its tangent point is the OWRpointi; otherwise, go to step 3.

3: Obtain the tangent points A₁ and Q₁ of the two single-direction tangents from P_Ri to Σ.

4: Obtain FBWA1 and FBWQ1 respectively.

5: Substitute PRi in FBWA1 and FBW_Q1 with P_Mi, such that another two ways represented with FBW_A1* and

FBWQ1* are obtained.

6: If |FBW_A1*|<|FBW_Q1*|, then A₁ is the OWRpointi; otherwise Q₁ is.

For algorithm 2, the necessary computation in the worst case is to compute |FBW_A₁| and |FBW_Q₁| using algorithm 1. Assume that m is the vertex number of the knowledge obstacle wall of Ri with most vertices; then, the computational complexity of algorithm 2 is O(2m) as the number of vertices on FBWA1/FBWQ1 cannot be more than m.

4. Motion controller based on artificial moments

A motion controller based on artificial moments is designed in this section, which is an extension of the artificial moment method for multi-robot formation control [21], [22]. Its basic idea is that at each sampling time R_i may be influenced by three types of artificial moments - that is, the attractive moment by the OWRpointi, the repulsive moments by obstacles and the coordinated moments by other robots. The gradient of each artificial moment generates an expected vector for Ri to change position and the PMDline so that the moment can increase as quickly as possible. Additionally, Ri has a motion vector along its PMDline which is not in general determined by artificial moments. The total vector determines the next position and the PMDline direction of Ri and, afterwards, the above process is repeated until the task is fulfilled.

Obviously, the artificial moment method is similar to the APF method in some aspects. Therefore, they have shared advantages. However, there are certain important differences between them.

One of these is that in the artificial moment method each robot has a motion vector along its PMDline which is nearly uninfluenced by artificial moments. Let (S_xi(k+1), S_yi(k+1))^T represent the expected vector of R_i along its PMDline in (t_k, t_k₊₁]. If the OWRpointi at the current time tk is T_i and the distance from P_Ri to T_i is not larger than DS, then (S_xi (k+1), S_yi(k+1))^T=(0, 0)^T; otherwise:

{\begin{matrix} S_{x i} (k + 1) = S_{R} \cos (β_{R i} (k + 1)) \\ S_{y i} (k + 1) = S_{R} \sin (β_{R i} (k + 1)) \end{matrix}

(2)

where β_Ri (k+1) is R_i's PMDline's direction angle in (t_k, t_k₊₁].

The motion vector (S_xi (k+1), S_yi(k+1))^T causes R_i to have a high moving speed even if the total moment's gradient is zero and, as such, it is difficult for R_i to be trapped even in complicated environments.

A second difference is that a unique robot model is used in the artificial moment method, where each robot has a PMDline and two coordinated segments. According to the robot model, a coordinated moment - which can resolve the conflicts between robots (almost) optimally - is designed as follows.

4.1 Coordinated Moments

Each coordinated companion of R_i will - and only such robots can - impose a coordinated moment on R_i so that the conflict between them can be solved.

Assume that Rj is a coordinated companion of R_i and that CM(k) is the coordinated moment generated by R_j at the current time t_k. The function cmt(x) is defined as (3) and its derivative dcmt(x) as (4):

cmt (x) = {\begin{matrix} \begin{matrix} \cos (x) \begin{matrix} ​ & ​ & ​ \end{matrix} & | x | \leq π ∕ 2 \end{matrix} \\ π ∕ 2 - 1 - | x | + \cos (x - (π ∕ 2) sign (x)) \begin{matrix} ​ & | x | > π ∕ 2 \end{matrix} \end{matrix}

(3)

dcmt (x) = {\begin{matrix} \begin{matrix} - \sin (x) \begin{matrix} ​ & ​ & ​ \end{matrix} & | x | \leq π ∕ 2 \end{matrix} \\ - sign (x) - \sin (x - (π ∕ 2) sign (x)) \begin{matrix} ​ & | x | > π ∕ 2 \end{matrix} \end{matrix}

(4)

When |agl(β_Ri-β(P_Ri, P_Rj))|<δ_θ² and |agl(β_Ri-β(P_Rj, P_Ri))|<δ_θ² (the case where R_i and R have a marked trend to move towards each other), CM(k) is required to cause R_i to move to a side of R so that R_i can bypass R and so that no collision occurs between them. Furthermore, according to the PMDlines of R_i and R at present, it can be concluded that the two robots are moving towards PMi and P_Mj respectively. Accordingly, CM(k) is required to make R_i move towards a position that is away from P_Mj but close to P_Mi so that their influence upon the motion of each other can be minimized.

Let M represent the end-point of the directed segment whose start-point is P_Rj; the direction angle is the same as that of DS(P_Mj, P_Mi) and the length is DS+ DR (as shown in Figure 1); (xM, yM)^T represents the coordinates of M. As such, M is an ideal point towards which R_i moves as M satisfies all of the requirements mentioned above. Thus, CM(k) is designed as (5) in this case:

\begin{array}{l} C M_{​} (k) = λ_{r} λ_{1} cmt (agl (β_{Ri} - β (P_{R i}, C_{r j}))) + \\ + λ_{l} λ_{2} cmt (agl (β_{Ri} - β (P_{Ri} {, C}_{lj}))) + \\ + (cmt (λ_{π} (x_{R i} - x_{M})) +cmt (λ_{π} (y_{R i} - y_{M}))) ∕ {(λ_{π})}^{2} \end{array}

(5)

where C_lj and C_rj are the end-points of the left and right coordinated segment of R_j respectively; λ_r =D_S/(|P_RiC_rj|+ D_S) and λ_l= D_S/(|P_RiC_lj|+ D_S).

In (5), only when P_Ri is at M does CM (k) have the potential to be the greatest. Thus, CM (k) will cause R_i to move towards M. However, when P_MiP_Mj is parallel to P_RiP_Rj, Ri ‘s motion towards M and Rj 's similar motion will lead the two robots to move in parallel and, then, a deadlock arises. To avoid the deadlock situation, the first term, λ,λ₁cmt[agl(β_Ri(k)-β(P_Ri, C_rj))] and the second, λ₁,λ₂cmt[agl(β_Ri(k)- β(P_Ri, C_lj))] are designed. The first term is to make R_i 's PMDline point to C_rj, as the term will be the greatest when R_i 's PMDline points to C_rj; the second is to make R_i 's PMDline point to C_lj for the same reasons. As λ₁< λ₂, the influences of the two terms are not the same in general. As a result, P_MiP_Mj cannot be parallel to P_RiP_Rj at next time, even if P_MiP_Mj is parallel to P_RiP_Rj at present. Accordingly, the deadlock situation is avoided.

When |agl(β_Ri-β(P_Ri, P_Rj))|≥δ_θ2 or |agl(β_Rj-β(P_Rj, P_Ri))|≥δ_θ2 (the case where R_i and R_j have no marked trend to move towards each other), CM(k) is only required to ensure that R_i maintains a safe distance from R. Thus, CM (k) is designed as (6) in this case:

C M_{​} (k) = (cmt (λ_{π} (x_{R i} - x_{M})) + cmt (λ_{π} (y_{R i} - y_{M}))) ∕ {(λ_{π})}^{2}

(6)

Let (Δ₁β_Ri(k), Δ_1XRi(k), Δ_1yRi(k))^T denote the expected vector to increase CM(k); then, it is the gradient of CM(k). When |agl(β_Ri-β(P_Ri, P_Rj))|≥δ_θ2|agl(β_Rj-β(P_Rj, P_Ri))|≥δ_θ2:

{\begin{matrix} Δ_{1} β_{R i} (k) = λ_{r} λ_{1} dcmt (agl (β_{R i} - β (P_{R i}, C_{r j}))) \\ \begin{matrix} + λ_{l} λ_{2} dcmt (agl (β_{R i} - β (P_{R i}, C_{l j}))) \\ Δ_{1} x_{R i} (k) = dcmt (λ_{π} (x_{R i} - x_{M})) ∕ λ_{π} \begin{matrix} ​ & ​ & ​ \end{matrix} \end{matrix} \\ Δ_{1} y_{R i} (k) = dcmt (λ_{π} (y_{R i} - y_{M})) ∕ λ_{π} \begin{matrix} ​ & ​ & ​ \end{matrix} \end{matrix}

(7)

When |agl(β_Ri-β(P_Ri, P_Rj))|≥δ_θ2 or |agl(β_Rj-β(P_Rj, P_Ri))|≥δ_θ2:

{\begin{matrix} Δ_{1} β_{R i} (k) = 0 \\ Δ_{1} x_{R i} (k) = dcmt (λ_{π} (x_{R i} - x_{M}))/ λ_{π} \\ Δ_{1} y_{R i} (k) = dcmt (λ_{π} (y_{R i} (k) - y_{M}))/ λ_{π} \end{matrix}

(8)

(ΣΔ₁β_Ri(k), ΣΔ₁x_Ri(k), ΣΔ₁y_Ri(k))^T denote the sum of the gradients of all coordinatedmoments acting on R_i, where when R_i has no coordinated companion at the current time t_k, (ΣΔ₁β_Ri(k), ΣΔ₁x_Ri(k), ΣΔ₁y_Ri(k))^T =(0, 0, 0)^T.

4.2 Attractive Moments

A third difference between the artificial moment method and the APF method is the difference between artificial moment functions and artificial potential functions. Artificial potential functions are always designed in terms of the positions, velocities and accelerations of robots, targets and obstacles (or relative ones between them). Artificial moment functions, however, are always designed in terms of the angles from robots' PMDlines to OWRpoints and obstacles and, in most cases, artificial moments influence only robots' PMDlines but not their positions and velocities. As a result, many problems encountered in the APF - such as there being no passage between closely-spaced obstacles or goals being non-reachable with obstacles nearby - are solved by the proposed motion controller.

Assume the function amt(x) is (9); then, its derivative is (10):

amt (x) = {\begin{matrix} \cos (δ_{θ} ​_{1}) + (δ_{θ 1} ​^{2} - x^{2}) ∕ 2 \begin{matrix} \begin{matrix} ​ & ​ \end{matrix} & | x | \leq δ_{θ 1} \end{matrix} \\ \cos (x) \begin{matrix} \begin{matrix} \begin{matrix} ​ & ​ \end{matrix} & ​ \end{matrix} & δ_{θ 1} < | x | \leq π ∕ 2 \end{matrix} \\ π ∕ 2 - 1 - | x | + \cos (x - (π ∕ 2) s i g n (x)) \begin{matrix} ​ & | x | > π ∕ 2 \end{matrix} \end{matrix}

(9)

damt (x) = {\begin{matrix} - x \begin{matrix} \begin{matrix} ​ & \begin{matrix} ​ & ​ \end{matrix} \end{matrix} & | x | \leq δ_{θ 1} \end{matrix} \\ - \sin x \begin{matrix} \begin{matrix} ​ & ​ \end{matrix} & δ_{θ 1} < | x | \leq π ∕ 2 \end{matrix} \\ - sign (x) - \sin (x - (π ∕ 2) sign (x)) \begin{matrix} ​ & | x | > π ∕ 2 \end{matrix} \end{matrix}

(10)

Let AM(k) denote the attractive moment imposed by the OWRpointi at the current time tk; then, AM(k) is designed as follows.

If the OWRpointi is not T or else if its distance from P_Ri is larger than DS, then AM(k) is only required to make Ri's PMDline face the OWRpointi. As with when R_i's PMDline is facing the OWRpointi, the objective for R_i in moving closely to the OWRpointi can be fulfilled by the motion vector (S_xi(k+1),S_yi(k+1))^T. Thus, AM(k) is designed as (11) in this case:.

A M (k) = - (λ_{1} ∕ 2) {(agl (β_{R i} - β (P_{R i}, O W R p o i n t_{i})))}^{2}

(11)

If the OWRpointi is T and its distance from P_Ri is not larger than DS, AM(k) is required to influence both R_i's PMDline and position so that R_i can reach T_i exactly while having as similar a posture to T as is possible. Thus, AM(k) is designed as (12) in this case:

\begin{array}{c} A M (k) = amt (agl (β_{R i} - β_{T i})) + \\ + (amt (λ_{π} (x_{R i} - x_{T i})) + amt (λ_{π} (y_{R i} - y_{T i}))) ∕ {(λ_{π})}^{2} \end{array}

(12)

Let (Δ₂β_Ri(k), Δ_2xRi(k), Δ_2yRi(k))^T denote the expected vector to increase AM(k); then, it is the gradient of AM(k). When the OWRpointi is not T or its distance from PRi is larger than DS:

\begin{array}{c} {(Δ_{2} β_{R i} (k), Δ_{2} x_{R i} (k), Δ_{2} y_{R i} (k))}^{T} = \\ = {(- λ_{1} (agl (β_{R i} - β (P_{R i}, O W R p o i n t_{i}))), 0, 0)}^{T} \end{array}

(13)

When the OWRpointi is T_i and its distance from P_Ri is not larger than DS:

(\begin{matrix} Δ_{2} β_{R i} (k) \\ Δ_{2} x_{R i} (k) \\ Δ_{2} y_{R i} (k) \end{matrix}) = (\begin{matrix} damt (agl (β_{R i} - β_{T i})) \\ damt (λ_{π} (x_{R i} - x_{T i})) ∕ λ_{π} \\ damt (λ_{π} (y_{R i} - y_{T i})) ∕ λ_{π} \end{matrix})

(14)

4.3 Repulsive Moments and Motion Controller

Suppose that G is a dangerous wall representative point of Ri at the current time tk and that PM(k) is the repulsive moment generated by G at tk.

When R has no coordinated companion at present, PM(k) is only required to cause R_i's PMDline to move away from G. As with when R_i's PMDline is away from G, the objective for R in moving away from G can be fulfilled by the motion vector (S_xi(k+1), S_yi(k+1))^T. Thus, PM(k) is designed as (15) in this case:

P M (k) = - λ_{p} {(agl (β_{R i} - β (G, P_{R i})))}^{2}

(15)

When R has coordinated companions, PM(k) is required to influence R_i's position but not the PMDline so that the influence of the coordinated moments on R_i's position can be weakened and so that R will not move too closely to G. Accordingly, PM(k) is designed as (16) in this case:

P M (k) = (cmt (λ_{π} (x_{R i} - x_{D})) + cmt (λ_{π} (y_{R i} - y_{D}))) ∕ {(λ_{π})}^{2}

(16)

where (xD, yD)^T is the coordinates of the end-point of the directed segment with a start-point G, a direction angle β(G, P_Ri) and a length DS.

Let (Δ₃β_Ri(k), Δ₃x_Ri(k), Δ₃y_Ri(k))^T denote the expected vector to increase PM(k); then, it is the gradient of PM(k). When R_i has no coordinated companion:

\begin{array}{c} {(Δ_{3} β_{R i} (k), Δ_{3} x_{R i} (k), Δ_{3} y_{R i} (k))}^{T} = \\ = {(- λ_{p} (agl (β_{R i} - β (G, P_{R i}))), 0, 0)}^{T} \end{array}

(17)

When R_i has coordinated companions:

{\begin{matrix} Δ_{3} β_{R i} (k) = 0 \\ Δ_{3} x_{R i} (k) = dcmt (λ_{π} (x_{R i} - x_{D})) ∕ λ_{π} \\ Δ_{3} y_{R i} (k) = dcmt (λ_{π} (y_{R i} - y_{D}))) ∕ λ_{π} \end{matrix}

(18)

(ΣΔ₃β_Ri(k), ΣΔ₃x_Ri(k), ΣΔ₃y_Ri(k))^T denotes the sum of the gradients of all repulsivemoments acting on R_i, where when R_i has no dangerous wall representative point at t_k, (ΣΔ₃β_Ri(k), ΣΔ₃x_Ri(k), ΣΔ₃y_Ri(k))^T =(0, 0, 0)^T.

The motion controller of R_i using artificial moments for multi-robot path-planning is designed as (19), (21), (22):

β_{R i} (k + 1) = agl [β_{R i} (k) + Σ Δ_{1} β_{R i} (k) + Δ_{2} β_{R i} (k) + Σ Δ_{3} β_{R i} (k)]

(19)

Let:

{\begin{matrix} Δ x_{R i} = S_{x i} (k + 1) + Σ Δ_{1} x_{R i} (k) + Δ_{2} x_{R i} (k) + Σ Δ_{3} x_{R i} (k) \\ Δ y_{R i} = S_{y i} (k + 1) + Σ Δ_{1} y_{R i} (k) + Δ_{2} y_{R i} (k) + Σ Δ_{3} y_{R i} (k) \end{matrix}

(20)

If $\sqrt{{(Δ x_{R i})}^{2} + {(Δ y_{R i})}^{2}}$ is not larger than S_R, then:

{\begin{matrix} x_{R i} (k + 1) = x_{R i} (k) + Δ x_{R i} \\ y_{R i} (k + 1) = y_{R i} (k) + Δ y_{R i} \end{matrix}

(21)

Otherwise:

{\begin{matrix} x_{R i} (k + 1) = x_{R i} (k) + \frac{Δ x_{R i} S_{R}}{\sqrt{{(Δ x_{R i})}^{2} + {(Δ y_{R i})}^{2}}} \\ y_{R i} (k + 1) = y_{R i} (k) + \frac{Δ y_{R i} S_{R}}{\sqrt{{(Δ x_{R i})}^{2} + {(Δ y_{R i})}^{2}}} \end{matrix}

(22)

From (2)–(22), we can conclude that the proposed motion controller can make a robot enter and pass through narrow passages. Although the effects of attractive and repulsive moments may be cancelled out by each other when R is close to a narrow passage, R can still enter the passage through the motion vector (S_xi(k+1), S_yi(k+1))^T.

The controller can also make R_i reach a target with obstacles nearby. As with when R_i is close to T_i, (S_xi(k+1), S_yi(k+1))^T is zero, which means that repulsive moments cannot influence R_i's motion. As a result, R_i can reach T_i under the influence of the attractive moment generated by T_i.

When R_i has no coordinated companion, the controller will make R_i move under the guidance of its OWRpoints at its full speed for almost of the time. As such, no problem similar to the “local minimum” problem exists in the controller as it is impossible for R_i to stay at a “local minimum” point or in a small region.

5. Algorithm for multi-robot path-planning

Although the proposed motion controller has many advantages, it still has certain problems.

One is that where the OWRpoint_i is not T_i or else its distance from P_Ri is larger than DS, the controller may cause R_i to move away from the OWRpoint_i if R_i has a dangerous wall representative point G satisfying (23), as shown in Figure 3(a):

| agl (β (P_{R i}, O W R p o i n t_{i}) - β_{R i}) + agl (β_{R i} - β (G, P_{R i})) | \geq π

(23)

Figure 3.

(a) R_i moves away from the OWRpointi; (b) Ri cannot achieve the same posture as that of T_i as much as possible. (c) The conflict between R_i and R_j cannot be solved effectively.

The reasons for this are that if (23) is satisfied, Ri 's PMDline direction may not be changed by the controller since the sign of agl (β_Ri-β(P_Ri, OWRpoint_i)) will be opposite to that of agl (β_Ri-β(G,P_Ri)), as shown in Figure 3(a); as such, the effects of the attractive and repulsive moments may cancel each other out. Accordingly, R_i will move away from the OWRpointi if |agl(β_Ri-β(P_RiOWRpointi|≥π/2. In this situation, the method for avoiding the problem set out above is to let β_Ri(k) be agl(β(P_Ri, OWRpointi)+δ_θ1) if the OWRpointi is T or else after lettingβ_Ri(k)=agl(β(P_Ri, OWRpointi)+δ_θ1), R_i 's PMDline has no intersection with the knowledge obstacle wall on which the OWRpointi lies; otherwise, let β_Ri(k) be agl(β(P_Ri, OWRpointi)-δ_θ1).

A second problem is that in the case where the OWRpoint_i is T_i and its distance from P_Ri is not larger than DS, the controller may not cause R_i to achieve the same posture as that of T_i as much as possible, if R_i has a dangerous wall representative point G satisfying (24), as shown in Figure 3(b).

| agl (β_{T i} - β_{R i}) + agl (β_{R i} - β (G, P_{R i})) | \geq π

(24)

The reasons are similar to that of the first. In this case, the method for avoiding the problem is to let β_Ri (k) be β_Ti (k).

A third problem is that where the OWRpointi is T_i and the distance between P_Ri and T_i is not larger than DS, if R_j is a coordinated companion of R_i and |agl(β_Ti-β_Rj)| <δ_θ2, as shown in Figure 3(c), then the controller may not resolve the conflicts between R_i and R_j. The reasons for this are that as the direction of R_i 's PMDline may be the same as that of T_i's PMDline under the influence of the attractive moment generated by T_i, it is concluded that there is no marked trend for them to move towards each other. As a result, the coordinated moment generated by R_i will only allow R_j to maintain a certain safe distance from R_i but it will not guide R_j in bypassing R_i. In this situation, the method for avoiding the problem is to let β_Ti(k)=agl(β_Ti(k)+π).

After the above-mentioned pre-processes, the proposed controller performs well in various situations. The algorithm for the local path-planning of multi-robots is then given as follows:

Algorithm 3 Path-planning of multi-robots

1: Set the values of the parameters in the control system; initialize the shared environment and the sets of robots, targets and knowledge obstacle walls; let t_k =t₀.

2: For each robot that has not reached its target, remove or set artificial obstacle segments until no such work can be done.

3: For each robot R_i, if it has not reached T_i or else has coordinated companions, then go to step 4. Otherwise, its position and PMDline will not be changed.

4: Obtain the OWRpoint_i and all dangerous wall representative points of R_i.

5: In the case where the OWRpointi is T and its distance from PRi is not larger than DS, if R_i has a coordinated companion R_j and |agl(β_Ti-β_Rj)|<δ_θ2, then let β_Ti=agl(β_Ti +π); otherwise, if T_i's PMDline direction is not that at t0, then let β_Ti be that at t₀.

6: If the OWRpoint_i is not T_i or else its distance from P_Ri is larger than D_S, then if R_i has a dangerous wall representative pointG satisfying (23), let β_Ri(k)=agl(β(P_Ri, OWRpoint_i)±δ_θ1). Otherwise, if R_i has a dangerous wall representative point G satisfying (24), let β_Ri(k)= β_Ti(k).

7: Move a step to the next position under the control of the proposed motion controller. Update the current time as t_k ₊₁.

8: If all of the robots have reached their targets, then stop; otherwise, update their knowledge obstacle walls and let t_k = t_k ₊₁; then, return to step 2.

6. Simulations and analysis

In order to demonstrate the feasibility of the proposed method, extensive simulations have been carried out and two of them are given in what follows. In the simulations, no robot has a priori knowledge about the environment or other robots. The parameters are: DR=0.4, DV=3.5, DS=1, DM=SR=0.24, λ₁=0.5, λ₂=0.8, δ_θ1=π/90 and δ_θ2=π/3. A simulation will terminate automatically if the distance from the boundary of a robot to that of another one (or an obstacle) is less than 0.05.

The path-planning of two robots in a complicated environment is shown in Figure 4 where (including Figure 5) short segments on obstacles are N-type artificial obstacle segments. From Figure 4, we can see that the two robots encounter each other in a narrow passage whose width is only 2DS =2, but the conflict between them is solved quickly. The simulation verifies that the method is effective in solving the conflicts between robots in narrow passages and that robots will not be trapped in complicated environments.

Figure 4.

Path-planning of two robots with 130 steps

The path-planning of three robots in a complicated environment is shown in Figure 5, where T₃ is in the middle of a narrow passage whose width is also 2D_S=2, and R₃ is at T₃ at the initial time.

Figure 5 (a) and (b) present the situations in solving the conflicts between the robots at the entrance of a narrow passage and in the middle of the passage, respectively. The simulation verifies, again, that the method is effective for the path-planning of multi-robots in complicated environments.

Figure 5.

Path-planning of three robots with 149 steps

From Figures 4 and 5, we can see that although the path travelled by each robot may not be the optimal one, it is sure to be a sub-optimal one. As such, the method can optimize the path travelled by each robot.

7. Conclusions

From the discussion and simulations given in this paper, we can arrive at the following conclusions.

The proposed method meets the requirements of the real-time property for the following reasons. Firstly, all of the computations involved in the method are spatially distributed and their complexity is bounded regardless of the number of robots. Secondly, it needs almost no pre-processing of the environment, no consideration of the safe distance of robots and no explicit communication. Thirdly, the computational complexity of OWRpoints is low.

Compared with the traditional APF method, the proposed motion controller has certain advantages as follows. Firstly, under its control, a robot will not be trapped in a complicated environment, can enter and pass through narrow passages, can reach a target with obstacles nearby, and can achieve the same posture as that of its target as much as possible when it reaches its target. Secondly, it can resolve the conflicts between robots while no other techniques - such as priorities and negotiation - are needed and it can minimize other robots' influences on a given robot's motion.

The proposed method can optimize the path travelled by each robot as each robot's motion is under the guidance of its OWRpoints and other robots' influences are minimized by coordinated moments.

A disadvantage is that the proposed method may find it difficult to solve the conflicts between robots in passages narrower than 2DS or in a dynamical environment. In the future, we will try our best to overcome these disadvantages.

Footnotes

8. Acknowledgments

The research reported in this paper was supported by the NSF of China under Grant No. 60874017, the State Key Laboratory of Robotics and System (HIT) under Grant No. SKLRS-2011-MS-03 and the Special Research Foundation of Liaoning University of Science and Technology under Grant No. 2012RC01.

References

Rigatos

G. G.

(2008) Multi-robot motion planning using swarm intelligence. International Journal of Advanced Robotic Systems, Vol. 5, No. 2, pp. 139–144.

Chakraborty

Konar

Chakraborty

U. K.

Jain

L. C.

(2008) Distributed cooperative multi–Robot path planning using differential evolution. Proceedings of IEEE Congress on Evolutionary Computation, pp. 718–725.

Bien

Lee

(1992) A minimum-time trajectory planning method for two robots. IEEE Trans. Robot. Autom., Vol. 8, pp. 414–418.

Shin

K. G.

Zheng

(1992) Minimum-time collision-free trajectory planning for dual-robot systems. IEEE Trans. Robot. Autom., Vol. 8, pp. 641–644.

Lavalle

S. M.

Hutchinson

S. A.

(1998) Optimal motion planning for multiple robots having independent goals. IEEE Trans. Robot. Autom., Vol. 14, No. 6, pp. 912–925.

Lumelsky

V. J.

Harinarayan

K. R.

(1997) Decentralized motion planning for multiple mobile robots: The cocktail party model. Autonomous Robots, No. 4, pp. 121–135.

Pallottino

Scordio

V. G.

Bicchi

Frazzoli

(2007) Decentralized cooperative policy for conflict resolution in multivehicle systems. IEEE Trans. Robot., Vol. 23, No. 6, pp. 1170–1183.

Zheng

Sun

Ding

(2005) Evolutionary route planner for unmanned air vehicles. IEEE Trans. Robot., Vol. 21, No. 4, pp. 609–620.

Besada-Portas

Torre

Cruz

J. M.

Andrés-Toro

(2010) Evolutionary trajectory planner for multiple UAVs in realistic scenarios. IEEE Trans. Robot., Vol. 26, No. 4, pp. 619–634.

10.

Bennewitz

Burgard

Thrun

(2001) Optimizing schedules for prioritized path planning of multi-robot systems. IEEE International Conference on Robotics and Automation, pp. 271–276.

11.

Regele

Levi

(2006) Cooperative multi-robot path planning by heuristic priority adjustment. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5954–5959.

12.

Kim

S. H.

Lee

Hong

Kim

Y. J.

Kim

(2010) New potential functions for multi robot path planning: SWARM or SPREAD. The 2nd international conference on computer and automation engineering, pp. 557–561.

13.

Yan

Y. J.

Zhang

(2009) Collision avoidance planning in multi-robot based on improved artificial potential field and rules. Proceedings of the 2008 IEEE International Conference on Robotics and Biomimetics, pp. 1026–1031.

14.

Yin

Y. X.

Lin

C. J.

(2009) A New Potential Field Method for Mobile Robot Path Planning in the Dynamic Environments. Asian Journal of Control, Vol. 11, No. 2, pp. 214–225.

15.

S. S.

Cui

Y. J.

(2002) Dynamic motion planning for mobile robots using potential field method. Autonomous Robots, No. 13, pp. 207–222.

16.

Takahashi

Schilling

R. J.

(1989) Motion planning in a plane using generalized Voronoi diagrams. IEEE Trans. Robot. Autom., Vol. 5, No. 2, pp. 143–150.

17.

Lozano-Perez

(1983) Spatial planning: A configuration space approach. IEEE Trans. Comput., Vol. 32, pp. 108–120.

18.

Liu

Y. H.

Arimoto

(1991) Proposal of tangent graph and extended tangent graph for path planning of mobile robots. Proceedings of IEEE International Conference on Robotics and Automation, pp. 312–317.

19.

Huang

H. P.

Chung

S. Y.

(2004) Dynamic visibility graph for path planning. Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2813–2818.

20.

Svestka

Overmars

M. H.

(1995) Coordinated motion planning for multiple car-like robots using probabilistic roadmaps. Proceedings of IEEE International Conference on Robotics and Automation, pp. 1631–1636.

21.

W. B.

Chen

X. B.

(2008) Artificial moment method for swarm-robot formation control. Science in China Series F: Information Science, Vol. 51, No. 10, pp. 1521–1531.

22.

W. B.

Chen

X. B.

(2009) A dynamical formation control approach based on artificial moments. Control Theory & Applications (in Chinese), Vol. 26, No. 11, pp. 1232–1238.