# Mobile Robots Path Planning Using the Overall Conflict Resolution and Time Baseline Coordination

Authors: Yong Ma; Hongwei Wang; Langxiong Gan; Min Guo; Liwen Huang; Jing Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper aims at resolving the path planning problem in a time-varying environment based on the idea of overall conflict resolution and the algorithm of time baseline coordination. The basic task of the introduced path planning algorithms is to fulfill the automatic generation of the shortest paths from the defined start poses to their end poses with consideration of generous constraints for multiple mobile robots. Building on this, by using the overall conflict resolution, within the polynomial based paths, we take into account all the constraints including smoothness, motion boundary, kinematics constraints, obstacle avoidance, and safety constraints among robots together. And time baseline coordination algorithm is proposed to process the above formulated problem. The foremost strong point is that much time can be saved with our approach. Numerical simulations verify the effectiveness of our approach.


---

## Body

## 1. Introduction

Since the 1990s, industrial robots have played an important role in the robotics research [1]. One foremost research topic of industrial robots is mobile robots’ path planning [2, 3], wherein the paths connecting the start and end poses of robots are planned to assist completing their task. In industrial application, to suit the actual situation, there is no denial that the nonholonomic constraint [4, 5] which means the mobile robots subjecting to the requirements of rolling without slipping should be taken into consideration. Further, in the traverse process of mobile robots, owing to the mutual influence of robots and obstacles moving and stationary in a time-varying environment, the conflicts would be induced inevitably. Thus, our concerned path planning problems become much more difficult since the planned paths must take above geometric and nonholonomic constraints and conflict-avoidance constraints into account. Then, how to plan the shortest paths for multiple mobile robots while explicitly considering smoothness, kinematics constraints, motion boundary, obstacle avoidance, and safety constraints among mobile robots becomes our mainly focused problem.During the past decades, various path planning methodologies for mobile robots have been developed [2, 6–12]. We have presented the detailed introduction in [2] with a sense of hierarchy. In [6, 13], differential evolution and honey bee mating optimization algorithms are used to resolve the cooperative multirobot path planning problem, respectively. However, too many broken lines exist in the planned paths, which cannot be directly used in the real scenario. With those ill-smooth paths as depictured in [14], the roller slip would be triggered in the motion process of mobile robots. Then, the slip would endanger the safety of mobile robots and furthermore lead to the meaninglessness of those paths.As pointed in [15] the planned path should be smooth to accord with the practical applications. With the smooth paths, we can account for the continuity [16] and the kinematics constraints sufficiently. Contrarily, if with the ill-smooth paths, the jerks would be triggered during the motion process. Given that polynomials are the set of highly smooth functions, there is no doubt that polynomial based paths are quite smooth [15]. Hence, we adopt the polynomial based paths to represent their motion in our research.Generally in many works like [2, 9, 10], they focus on two-phase approach for path planning problems. Firstly, the path for each mobile robot is reached with some certain algorithm. Following that, by using the predefined principles, the conflicts among the planned paths are resolved in the second phase. However, approaches of this category cannot be illustrated analytically and do not work sometimes. Consequently, the sound approach is disposing of all the conflicts as a whole not using the two-phase approach.To avoid the two-phase methods, the studies like [2, 7–11] adopted quartic Bezier curves to represent the paths of mobile robots. However, approaches in [7, 8] strictly restrict the paths to the fourth-order Bezier curves and require the initial and final velocities of each mobile robot, which would be impractical for the realistic application. Comparatively, as a natural continuation of our previous work in [2], to avoid the deadlock of the two-phase conflict dissolution approach, in our objective function, we eliminate the overall conflicts of the focused problem. When it comes to the objective function, we set the summation of the shortest paths of all mobile robots as the goal function and take generous constraints into account. Eventually, we formulate the problem as one time-varying nonlinear programming problem (TNLPP). To solve the TNLPP, we devise the time baseline coordination method. Within this method, we choose the least motion time of all mobile robots as the time baseline; by using this parameter we can fulfill their motion coordination. The detailed illustration is presented in Section 4.This paper is organized into seven sections. In Section2, the shortest polynomial based paths for multiple mobile robots are defined. In Section 3, modeling for path planning problems with overall confliction is introduced explicitly. In Section 4, time baseline coordination algorithm is detailed to resolve the path planning problems. In Section 5, simulation results are presented to demonstrate the effectiveness of our approaches. Section 6 discusses results of cases in Section 5. Section 7 concludes this paper.


## 2. Problem Formulation

Suppose that one mobile robotAi (i=1,2,…,J) is represented by a ri-radius circle with center xi(t)=(x1i(t),x2i(t)) and orientation θi(t),  t∈[0,tfi], where m is the number of mobile robots, xi is one parameterized polynomial with unknown index and used to denote the path of Ai, and tfi is a given real number as final moving time of Ai. The poses of mobile robots at time t are illustrated as Pi(t)=(xi(t),θi(t)). Then, we should plan the shortest and conflict-free paths for all mobile robots Ai (i=1,2,…,J) from the start pose Pi0 to the end pose Pif, where Pi0=Pi(0) and Pif=Pi(tf).As sensors or cameras are used to detect the positions of obstacles [17], the paths of obstacles can be duly reached. Meanwhile, suppose the obstacle Ok(k=1,2,…,q) is a rk-radius circle with center αk(t)=(α1k(t),α2k(t)),  t∈[0,tk], where q is the number of the obstacles, αk(·) is the path of Ok and expressed with known parameterized polynomial, and tk is a given real number as final motion time of Ok.


### 2.1. Polynomial Based Paths

To detailxi which is the path of Ai and equals (x1i(t),x2i(t)), we set x1i(t)=x1i,  x2i(t)=x2i, and the unknown indices of x1i and x2i are M and N, respectively. The unknown coefficients of x1i and x2i are represented by [a0ia1i⋯ami⋯aMi] and [b0ib1i⋯bni⋯bNi]  (1≤m≤M,1≤n≤N), respectively. Then, the path of Ai is given in the following form, where t∈[0,tfi]:
(1)x1i=a0i+a1it+⋯+amitm+⋯+aMitM,x2i=b0i+b1it+⋯+bnitn+⋯+bNitN.Suppose thatAi=[a0ia1i⋯ami⋯aMi], Bi=[b0ib1i⋯bni⋯bNi], TAi=[t0t⋯tm⋯tM], and TBi=[t0t⋯tn⋯tN], t∈[0,tfi]. Then, the path xi can be
(2)[x1ix2i]=[Ai00Bi][TAiTTBiT].Within pathxi, the velocities in the direction of x1i and x2i are x˙1i(t) and x˙2i(t), respectively. The accelerations in the direction of x1i and x2i are x¨1i(t) and x¨2i(t), respectively. Consequently, the path length of Ai can be
(3)si=∫0tfi‍x˙1i2(t)+x˙2i2(t)dt=∫0tfi‍∥x˙i(t)∥2dt.Analogously, for the path ofOk featured by αk, we set α1k(t)=α1k,α2k(t)=α2k, and the known indices of α1k and α2k are L and U, respectively. The known coefficients of α1k and α2k are represented by [a0Oka1Ok⋯alOk⋯aLOk] and [b0Okb1Ok⋯buOk⋯aUOk] (1≤l≤L,1≤u≤U), respectively. Then the path of Ok is given in the following form, where t∈[0,tfi]:
(4)α1k=a0Ok+a1Okt+⋯+alOktl+⋯+aLOktL,α2k=b0Ok+b1Okt+⋯+buOktu+⋯+bUOktU.Suppose thatAOk=[a0Oka1Ok⋯alOk⋯aLOk], BOk=[b0Okb1Ok⋯buOk⋯aUOk], TAk=[t0t⋯tl⋯tL], and TBk=[t0t⋯tu⋯tU], t∈[0,tk]. Then, the path αk can be
(5)[α1kα2k]=[AOk00BOk][TAkTTBkT].


### 2.2. Generous Constraints

To plan the effective and reasonable paths for multiple mobile robots, when achieving our objective function, generous constraints including kinematics, motion boundaries, and obstacle avoidance should be satisfied. For this end, to probe into the essence of each constraint, we detail each constraint sequentially.


#### 2.2.1. Kinematics Constraints

Kinematics constraints indicate that the velocity and acceleration along with the path should be bound to their maximum allowed intervals to prevent robots from slipping. Then, the kinematics constraints can be(6)vi(t)≤vmax⁡i,ai(t)≤amax⁡i,t∈[0,tfi],i∈[1,J].In the kinematics constraints,vi(t) and ai(t) are denoted by x˙i(t) and x¨i(t), respectively.


#### 2.2.2. Motion Boundary

X is used to represent the two-dimensional environment boundary. The constraints imposed by the motion boundary should be satisfied as below:
(7)Pi(0)=(x0i,θ0i),Pi(tfi)=(xfi,θfi),X0i,Xfi∈X,i∈[1,J].


#### 2.2.3. Obstacle Avoidance Constraints

Obstacle avoidance constraints guarantee the least safe distance between the current moving robot and all the obstacles. Suppose thatdoik and dobs_ik are the real distance and the preset safe distance between Ai and Ok, respectively. doik is represented as below. For 1≤i≤J,  1≤k≤q,
(8)doik(t)=∥xi(t)-αk(t)∥2-(ri+rk).Then, the obstacle avoidance constraints forAi and Ok (1≤i≤J,1≤k≤q) in X should be
(9)dobs_ik-doik(t)≤0,t∈[0,max⁡(tfi,tk)].


#### 2.2.4. Safety Constraints among Mobile Robots

Within the safety constraints among mobile robots, all the robots can be kept away from each other with distances larger than the predefined safety value. Thus, the collisions between mobile robots can be averted triumphantly with ease.Supposedij and ds_ij are the real distance and the preset safe distance between Ai and Aj, respectively. For 1≤i≤J,  i≠j, dij can be
(10)dij(t)=∥xi(t)-xj(t)∥2-(ri+rj).Then, the safety constraints amongAi in X should be satisfied as below (1≤i≤J):
(11)ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)].


### 2.3. Goal Function

Our goal function is to minimize the summation of all the paths length, which can be(12)min⁡∑i=1J‍si.Similar to our work in [2], we equally divide the time interval [0,tfi] into F parts, where h denotes the value of each part, h=tfi/F, 0≤f≤F; set Ei(t)=∥x˙i(t)∥2. Consequently, after the transformation, the goal function can be
(13)min⁡∑i=1J‍h(2∑f=1F‍Ei(fh)-E(0)-Ei(tfi))2.


## 2.1. Polynomial Based Paths

To detailxi which is the path of Ai and equals (x1i(t),x2i(t)), we set x1i(t)=x1i,  x2i(t)=x2i, and the unknown indices of x1i and x2i are M and N, respectively. The unknown coefficients of x1i and x2i are represented by [a0ia1i⋯ami⋯aMi] and [b0ib1i⋯bni⋯bNi]  (1≤m≤M,1≤n≤N), respectively. Then, the path of Ai is given in the following form, where t∈[0,tfi]:
(1)x1i=a0i+a1it+⋯+amitm+⋯+aMitM,x2i=b0i+b1it+⋯+bnitn+⋯+bNitN.Suppose thatAi=[a0ia1i⋯ami⋯aMi], Bi=[b0ib1i⋯bni⋯bNi], TAi=[t0t⋯tm⋯tM], and TBi=[t0t⋯tn⋯tN], t∈[0,tfi]. Then, the path xi can be
(2)[x1ix2i]=[Ai00Bi][TAiTTBiT].Within pathxi, the velocities in the direction of x1i and x2i are x˙1i(t) and x˙2i(t), respectively. The accelerations in the direction of x1i and x2i are x¨1i(t) and x¨2i(t), respectively. Consequently, the path length of Ai can be
(3)si=∫0tfi‍x˙1i2(t)+x˙2i2(t)dt=∫0tfi‍∥x˙i(t)∥2dt.Analogously, for the path ofOk featured by αk, we set α1k(t)=α1k,α2k(t)=α2k, and the known indices of α1k and α2k are L and U, respectively. The known coefficients of α1k and α2k are represented by [a0Oka1Ok⋯alOk⋯aLOk] and [b0Okb1Ok⋯buOk⋯aUOk] (1≤l≤L,1≤u≤U), respectively. Then the path of Ok is given in the following form, where t∈[0,tfi]:
(4)α1k=a0Ok+a1Okt+⋯+alOktl+⋯+aLOktL,α2k=b0Ok+b1Okt+⋯+buOktu+⋯+bUOktU.Suppose thatAOk=[a0Oka1Ok⋯alOk⋯aLOk], BOk=[b0Okb1Ok⋯buOk⋯aUOk], TAk=[t0t⋯tl⋯tL], and TBk=[t0t⋯tu⋯tU], t∈[0,tk]. Then, the path αk can be
(5)[α1kα2k]=[AOk00BOk][TAkTTBkT].


## 2.2. Generous Constraints

To plan the effective and reasonable paths for multiple mobile robots, when achieving our objective function, generous constraints including kinematics, motion boundaries, and obstacle avoidance should be satisfied. For this end, to probe into the essence of each constraint, we detail each constraint sequentially.


### 2.2.1. Kinematics Constraints

Kinematics constraints indicate that the velocity and acceleration along with the path should be bound to their maximum allowed intervals to prevent robots from slipping. Then, the kinematics constraints can be(6)vi(t)≤vmax⁡i,ai(t)≤amax⁡i,t∈[0,tfi],i∈[1,J].In the kinematics constraints,vi(t) and ai(t) are denoted by x˙i(t) and x¨i(t), respectively.


### 2.2.2. Motion Boundary

X is used to represent the two-dimensional environment boundary. The constraints imposed by the motion boundary should be satisfied as below:
(7)Pi(0)=(x0i,θ0i),Pi(tfi)=(xfi,θfi),X0i,Xfi∈X,i∈[1,J].


### 2.2.3. Obstacle Avoidance Constraints

Obstacle avoidance constraints guarantee the least safe distance between the current moving robot and all the obstacles. Suppose thatdoik and dobs_ik are the real distance and the preset safe distance between Ai and Ok, respectively. doik is represented as below. For 1≤i≤J,  1≤k≤q,
(8)doik(t)=∥xi(t)-αk(t)∥2-(ri+rk).Then, the obstacle avoidance constraints forAi and Ok (1≤i≤J,1≤k≤q) in X should be
(9)dobs_ik-doik(t)≤0,t∈[0,max⁡(tfi,tk)].


### 2.2.4. Safety Constraints among Mobile Robots

Within the safety constraints among mobile robots, all the robots can be kept away from each other with distances larger than the predefined safety value. Thus, the collisions between mobile robots can be averted triumphantly with ease.Supposedij and ds_ij are the real distance and the preset safe distance between Ai and Aj, respectively. For 1≤i≤J,  i≠j, dij can be
(10)dij(t)=∥xi(t)-xj(t)∥2-(ri+rj).Then, the safety constraints amongAi in X should be satisfied as below (1≤i≤J):
(11)ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)].


## 2.2.1. Kinematics Constraints

Kinematics constraints indicate that the velocity and acceleration along with the path should be bound to their maximum allowed intervals to prevent robots from slipping. Then, the kinematics constraints can be(6)vi(t)≤vmax⁡i,ai(t)≤amax⁡i,t∈[0,tfi],i∈[1,J].In the kinematics constraints,vi(t) and ai(t) are denoted by x˙i(t) and x¨i(t), respectively.


## 2.2.2. Motion Boundary

X is used to represent the two-dimensional environment boundary. The constraints imposed by the motion boundary should be satisfied as below:
(7)Pi(0)=(x0i,θ0i),Pi(tfi)=(xfi,θfi),X0i,Xfi∈X,i∈[1,J].


## 2.2.3. Obstacle Avoidance Constraints

Obstacle avoidance constraints guarantee the least safe distance between the current moving robot and all the obstacles. Suppose thatdoik and dobs_ik are the real distance and the preset safe distance between Ai and Ok, respectively. doik is represented as below. For 1≤i≤J,  1≤k≤q,
(8)doik(t)=∥xi(t)-αk(t)∥2-(ri+rk).Then, the obstacle avoidance constraints forAi and Ok (1≤i≤J,1≤k≤q) in X should be
(9)dobs_ik-doik(t)≤0,t∈[0,max⁡(tfi,tk)].


## 2.2.4. Safety Constraints among Mobile Robots

Within the safety constraints among mobile robots, all the robots can be kept away from each other with distances larger than the predefined safety value. Thus, the collisions between mobile robots can be averted triumphantly with ease.Supposedij and ds_ij are the real distance and the preset safe distance between Ai and Aj, respectively. For 1≤i≤J,  i≠j, dij can be
(10)dij(t)=∥xi(t)-xj(t)∥2-(ri+rj).Then, the safety constraints amongAi in X should be satisfied as below (1≤i≤J):
(11)ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)].


## 2.3. Goal Function

Our goal function is to minimize the summation of all the paths length, which can be(12)min⁡∑i=1J‍si.Similar to our work in [2], we equally divide the time interval [0,tfi] into F parts, where h denotes the value of each part, h=tfi/F, 0≤f≤F; set Ei(t)=∥x˙i(t)∥2. Consequently, after the transformation, the goal function can be
(13)min⁡∑i=1J‍h(2∑f=1F‍Ei(fh)-E(0)-Ei(tfi))2.


## 3. Problem Modeling with the Overall Conflict Resolution

### 3.1.  The Meaning of the Overall Conflict Resolution

Generally in the path planning problems, the conflicts including the collisions among mobile robots owing to the crossover of their planned paths and the crashes between mobile robots and obstacles occurred within the motion boundary. To fulfill the conflict-free path planning, the strategies or methods adopted to remove and avoid the collisions can be named conflict resolution strategies. Therein, we propose the overall conflict resolution.In our overall conflict resolution, we consider all the constraints demonstrated above in the process of modeling. By using the overall conflict resolution, the phase of how to bring forward some ideal conflict resolution strategies in the multiphase approaches is deleted. However, compared with the path planning model of the multiphase methods, the founded model based on overall conflict resolution is much more difficult and harder to actualize.


### 3.2. Problem Modeling

As none of the above constraints can be violated, with overall conflict resolution, for1≤i,  j≤J,  i≠j,  1≤k≤q, we consider all the constraints as a whole in our objective function as below:
(14)min⁡∑i=1J‍h(2∑f=1F‍Ei(fh)-E(0)-Ei(tfi))2s.t.vi(t)≤vmax⁡it∈[0,tfi]s.t.ai(t)≤amax⁡ii∈[1,J]s.t.Pi(0)=(x0i,θ0i)s.t.Pi(tfi)=(xfi,θfi)s.t.X0i,Xfi∈Xi∈[1,J]s.t.ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)]s.t.dobs_ik-doik(t)≤0,t∈[0,max⁡(tfi,tk)].Based on the overall conflict resolution strategy, our focused path planning problem is transformed to one objective function while subjects to all above constraints. Substantially, the concerned problem is one time-varying nonlinear programming problem with multiple nonlinear constraints. In (14), conflicts among all the mobile robots and obstacles moving and static are considered explicitly, which evades the general multilevel conflicts. Thus, compared with the multiphrase approaches, since path planning for all mobile robots just needs to be calculated only once, it is evident that much time can be saved by using our approach. Logically, with this model, the path planning efficiency is improved evidently. However, all above advantages are gained at the cost of the upgrading of the resolve difficulty of our model. To entirely dissolute those conflicts, in the following section we propose the time baseline coordination approach.


## 3.1.  The Meaning of the Overall Conflict Resolution

Generally in the path planning problems, the conflicts including the collisions among mobile robots owing to the crossover of their planned paths and the crashes between mobile robots and obstacles occurred within the motion boundary. To fulfill the conflict-free path planning, the strategies or methods adopted to remove and avoid the collisions can be named conflict resolution strategies. Therein, we propose the overall conflict resolution.In our overall conflict resolution, we consider all the constraints demonstrated above in the process of modeling. By using the overall conflict resolution, the phase of how to bring forward some ideal conflict resolution strategies in the multiphase approaches is deleted. However, compared with the path planning model of the multiphase methods, the founded model based on overall conflict resolution is much more difficult and harder to actualize.


## 3.2. Problem Modeling

As none of the above constraints can be violated, with overall conflict resolution, for1≤i,  j≤J,  i≠j,  1≤k≤q, we consider all the constraints as a whole in our objective function as below:
(14)min⁡∑i=1J‍h(2∑f=1F‍Ei(fh)-E(0)-Ei(tfi))2s.t.vi(t)≤vmax⁡it∈[0,tfi]s.t.ai(t)≤amax⁡ii∈[1,J]s.t.Pi(0)=(x0i,θ0i)s.t.Pi(tfi)=(xfi,θfi)s.t.X0i,Xfi∈Xi∈[1,J]s.t.ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)]s.t.dobs_ik-doik(t)≤0,t∈[0,max⁡(tfi,tk)].Based on the overall conflict resolution strategy, our focused path planning problem is transformed to one objective function while subjects to all above constraints. Substantially, the concerned problem is one time-varying nonlinear programming problem with multiple nonlinear constraints. In (14), conflicts among all the mobile robots and obstacles moving and static are considered explicitly, which evades the general multilevel conflicts. Thus, compared with the multiphrase approaches, since path planning for all mobile robots just needs to be calculated only once, it is evident that much time can be saved by using our approach. Logically, with this model, the path planning efficiency is improved evidently. However, all above advantages are gained at the cost of the upgrading of the resolve difficulty of our model. To entirely dissolute those conflicts, in the following section we propose the time baseline coordination approach.


## 4. Optimal Solution to Path Planning Using the Time Baseline Coordination

In the path planning problems, suppose that all the mobile robots commence moving at the same time. In this section, we illustrate the time baseline coordination at first, following that analyze the equivalence of this approach, and finally put forward the implementation of our subtle approach.


### 4.1. Brief Introduction of the Time Baseline Coordination

As depicted in Section2, the final motion time of Ai and Ok is tfi and tk, respectively. Suppose that the baseline time is Tmin⁡. The essence of our time baseline coordination is selecting the least motion time of Ai denoted as Tmin⁡ to coordinate the motion of all the mobile robots.In the time baseline coordination, we demonstrate the general operating procedures concisely.Firstly, withTmin⁡, we can transform all the velocities, the accelerations, and so forth into [0,tfi/Tmin⁡].Following that, we renew the corresponding constraints in our goal function.Thirdly, using the algorithm of our former work in [2], we solve then the transformed problems.And then, with multiple1/Tmin⁡, we map the resolution into [0,tfi] corresponding to the first step.Finally, we can reach the final solution eventually.


### 4.2. Time Baseline Coordination Algorithm TimeCoor

To illustrate the proposed approach definitely, we devise the following time baseline coordination algorithm calledTimeCoor (see Algorithm 1).Algorithm 1:
Tim
e
Coor(Pi0,Pif,xi(t),tfi,αk(t),tk,F,Tmin⁡).
Input: Start and end poses Pi0 and Pif, respectively. Unknown path xi(t), a known path αk(t), motion time tfi and tk, and
number of divided time intervalF, temporary time variable Tmin⁡.
Output: Parameters Ai, Bi, TAi and TBi which are used to represent the path of Ai.
Begin
Tmin⁡ = 0;
foreach  tfi of Ai  do
Tmin⁡=min⁡tfi;
end foreach
foreach  Ai in the set of multiple mobile robots
Map motion time interval[0,tfi] of Ai into [0,tfi/Tmin⁡] with the multiples of 1/Tmin⁡.
Map constraints of kinematics and obstacle-avoidance ofAi into corresponding forms with respect to [0, tfi/Tmin⁡].
end foreach
Modify the objective function with all the adjustments, then reach the newly TNLPPs namedTNLPPs_new.
CallTrap_TNLPPs(TNLPPs_new)
foreach  Ai  do
MultiplesAi′, Bi′, TAi′ and TBi′ with Tmin⁡.
end foreach
return  Ai, Bi, TAi and TBi.
EndThe algorithmTrap_TNLPPs is our previous work in [2], which is proposed to solve the time-varying nonlinear programming problem. Brief flow of algorithm Trap_TNLPPs is presented in the Appendix, and a comprehensive procession can be found in [2].


### 4.3. Equivalence of the Time Baseline Coordination Algorithm

To proof the equivalence of our approach, several equivalent descriptions (which are abbreviated as Equ) are presented as below.Equ-1. The motion boundary has not varied after mapping.Proof.
X is the given motion boundary, which has little relation with the time.Equ-2. The ration of the transformed velocities to the former is Tmin⁡.Proof.
As shown in Equ-1, there is no change in the trajectory ofAi, while the motion time is mapped into [0,tfi/Tmin⁡]. Thus, with theorem of integral, the division between the current velocities and the former is Tmin⁡.Equ-3. The ration of the transformed accelerations to the former is Tmin⁡2.Proof.
Based on Equ-1 and Equ-2, according to the relationship between velocities and accelerations, with theorem of integral, the division between the current accelerations and the former is(Tmin⁡)2.Equ-4. The ration of the velocities in the final solution to the velocities in the mapped solution is 1/Tmin⁡.Proof.
Based on Equ-1 and Equ-2, there is no change in the trajectory ofAi, while the motion time is transformed from [0,tfi/Tmin⁡] to [0,tfi]. With theorem of integral, the division between the velocities in the final solution and the velocities in the mapped solution is 1/Tmin⁡.Equ-5. The ration of the accelerations in the final solution to the accelerations in the mapped solution is 1/(Tmin⁡)2.Proof.
Based on Equ-1 and Equ-2, according to the relationship between velocities and accelerations, with theorem of integral, the division between the accelerations in the final solution and the accelerations in the mapped solution is(Tmin⁡)2.With the overall conflict resolution, when all constraints are considered, paths for all mobile robots are promptly achieved based on algorithmTimeCoor.


## 4.1. Brief Introduction of the Time Baseline Coordination

As depicted in Section2, the final motion time of Ai and Ok is tfi and tk, respectively. Suppose that the baseline time is Tmin⁡. The essence of our time baseline coordination is selecting the least motion time of Ai denoted as Tmin⁡ to coordinate the motion of all the mobile robots.In the time baseline coordination, we demonstrate the general operating procedures concisely.Firstly, withTmin⁡, we can transform all the velocities, the accelerations, and so forth into [0,tfi/Tmin⁡].Following that, we renew the corresponding constraints in our goal function.Thirdly, using the algorithm of our former work in [2], we solve then the transformed problems.And then, with multiple1/Tmin⁡, we map the resolution into [0,tfi] corresponding to the first step.Finally, we can reach the final solution eventually.


## 4.2. Time Baseline Coordination Algorithm TimeCoor

To illustrate the proposed approach definitely, we devise the following time baseline coordination algorithm calledTimeCoor (see Algorithm 1).Algorithm 1:
Tim
e
Coor(Pi0,Pif,xi(t),tfi,αk(t),tk,F,Tmin⁡).
Input: Start and end poses Pi0 and Pif, respectively. Unknown path xi(t), a known path αk(t), motion time tfi and tk, and
number of divided time intervalF, temporary time variable Tmin⁡.
Output: Parameters Ai, Bi, TAi and TBi which are used to represent the path of Ai.
Begin
Tmin⁡ = 0;
foreach  tfi of Ai  do
Tmin⁡=min⁡tfi;
end foreach
foreach  Ai in the set of multiple mobile robots
Map motion time interval[0,tfi] of Ai into [0,tfi/Tmin⁡] with the multiples of 1/Tmin⁡.
Map constraints of kinematics and obstacle-avoidance ofAi into corresponding forms with respect to [0, tfi/Tmin⁡].
end foreach
Modify the objective function with all the adjustments, then reach the newly TNLPPs namedTNLPPs_new.
CallTrap_TNLPPs(TNLPPs_new)
foreach  Ai  do
MultiplesAi′, Bi′, TAi′ and TBi′ with Tmin⁡.
end foreach
return  Ai, Bi, TAi and TBi.
EndThe algorithmTrap_TNLPPs is our previous work in [2], which is proposed to solve the time-varying nonlinear programming problem. Brief flow of algorithm Trap_TNLPPs is presented in the Appendix, and a comprehensive procession can be found in [2].


## 4.3. Equivalence of the Time Baseline Coordination Algorithm

To proof the equivalence of our approach, several equivalent descriptions (which are abbreviated as Equ) are presented as below.Equ-1. The motion boundary has not varied after mapping.Proof.
X is the given motion boundary, which has little relation with the time.Equ-2. The ration of the transformed velocities to the former is Tmin⁡.Proof.
As shown in Equ-1, there is no change in the trajectory ofAi, while the motion time is mapped into [0,tfi/Tmin⁡]. Thus, with theorem of integral, the division between the current velocities and the former is Tmin⁡.Equ-3. The ration of the transformed accelerations to the former is Tmin⁡2.Proof.
Based on Equ-1 and Equ-2, according to the relationship between velocities and accelerations, with theorem of integral, the division between the current accelerations and the former is(Tmin⁡)2.Equ-4. The ration of the velocities in the final solution to the velocities in the mapped solution is 1/Tmin⁡.Proof.
Based on Equ-1 and Equ-2, there is no change in the trajectory ofAi, while the motion time is transformed from [0,tfi/Tmin⁡] to [0,tfi]. With theorem of integral, the division between the velocities in the final solution and the velocities in the mapped solution is 1/Tmin⁡.Equ-5. The ration of the accelerations in the final solution to the accelerations in the mapped solution is 1/(Tmin⁡)2.Proof.
Based on Equ-1 and Equ-2, according to the relationship between velocities and accelerations, with theorem of integral, the division between the accelerations in the final solution and the accelerations in the mapped solution is(Tmin⁡)2.With the overall conflict resolution, when all constraints are considered, paths for all mobile robots are promptly achieved based on algorithmTimeCoor.


## 5. Simulation

Simulations are carried out to show the effectiveness of our approach. Four curves have been used increasingly as metrics to evaluate the performance of the proposed approach [2, 7, 8, 18]. They are the curve of velocities relative to time, the curve of acceleration relative to time, the curve of the safety distances relative to time, and the curve of planned paths relative to their motion time. Experiments are conducted under several different time-varying scenarios.In the simulation, we first consider the case without obstacles and then the latter with static and moving obstacles. In the following figures of Section5, the scales are same and all quantities conform to one certain unit system, for instance, meters and meters per second.


### 5.1. Path Planning for Multiple Mobile Robots without Obstacles

When it comes to the case of multiple mobile robots moving synchronously in the environment without obstacles, for1≤i, j≤J, i≠j, the essential objective function can be
(15)min⁡∑i=1J‍h(2∑f=1F‍Ei(fh)-E(0)-Ei(tfi))2s.t.vi(t)≤vmax⁡it∈[0,tfi]s.t.ai(t)≤amax⁡it∈[0,tfi]s.t.Pi(0)=(x0i,θ0i)s.t.Pi(tfi)=(xfi,θfi)s.t.X0i,Xfi∈Xi∈[1,J]s.t.ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)].


#### 5.1.1. Path Planning for Three Mobile Robots without Obstacles

In the first case, to test the validity of our approach, we choose the data listed in Table1 from recently published work [8] to examine the effectiveness of our algorithm. Approach in [8] was based on fourth-order Bezier curve.Table 1
Initial information of mobile robotsAi (i=1,2,3) in Section 5.1.1.
A
i
P
i
0
P
i
f
v
0
v
f
v
max
⁡
A
1
[
0.2,1.4
,
-
π
/
4
]
T
[
1.4,0.2
,
-
π
/
4
]
T
0.4
0.4
0.8
A
2
[
1.4,0.2,3
π
/
4
]
T
[
0.2,1.4,3
π
/
4
]
T
0.4
0.5
0.8
A
3
[
0.2,0.2
,
π
/
4
]
T
[
1.4,1.4
,
π
/
4
]
T
0.4
0.4
0.8In [8], the safety distances, the maximum motion time, and the maximum accelerations are given as ds_ij=0.35, Tmax⁡i=5, and amax⁡i=0.5 (i,j=1,2,3, i≠j), respectively.Within our approach, in order to fulfill the coordination, the minimized motion time of all the mobile robotsAi (i=1,2,3) is chosen as the time baseline which is used for coordination. Subsequently, applying the coordination algorithm TimeCoor, for t∈[0,5], paths of Ai (i=1,2,3) are obtained as below:A1=[0.20.2828-0.1660.097-0.0210.001];B1=[1.4-0.28280.198-0.0730.007];A2=[1.4-0.28280.518-0.0520.017-0.002];B2=[0.20.283-0.1270.041-0.004];A3=[0.20.28280.216-0.1160.019-0.001];B3=[1.40.28280.145-0.0650.007];TAi=[1titi2ti3ti4ti5];TBi=[1titi2ti3ti4ti5].Corresponding to Figures1(a), 1(b), and 1(c), our planned paths evolve from the perspective of three different time intervals [0, 2.3], [2.3, 5], and [0, 5]. In Figures 1(a), 1(b), and 1(c), it is shown that each mobile robot smoothly moves from its initial pose to final pose without any collision. The paths of [8] in the time interval [0,5] are shown in Figure 1(d). Thus, our approach based on TimeCoor can manipulate the multiple mobile robots path planning problems successfully.Planned paths evolvement ofAi and paths of [8], i=1,2,3. (a) In [0, 2.3], (b) in [2.3, 5], (c) in [0, 5], and (d) in [0, 5].
(a)
(b)
(c)
(d)The variation curves of velocities and accelerations along the time are shown in Figures2(a) and 2(b), respectively. Curves in Figure 2 are sufficient to the constraints in Table 1 and all other requirements in [8] fully. Then the planned paths meet the constraints of kinematics.(a)v-t, (b) a-t in Section 5.1.1.
(a)
(b)Figure3 illustrates that the variation of safety distances d12, d13, and d23 is satisfied with the predefined requirements in this case.Figure 3
Variation curve of safety distanced-t in Section 5.1.1.In our approach, the polynomials are general that are more flexible than the polynomials of [8] which are limited to four. Meanwhile, with approach in [8], prior to path planning, the initial and final velocities of each mobile robot should be specified in detail. Generally, in practice, the velocities belong to some certain intervals, not the constant predefined value. Contrastively, our approach is much more suitable for the general multiple mobile robots path planning problems.Compared to our prior work in [2], the paths of Ai (i=1,2,3) should be calculated for three times in the path planning phase. In our approach, it only takes a third of the time in the first phase of [2] to reach the conflict-free solution. Furthermore, the planned paths of A1 and A2 in [2] are almost overlapped, and the conflicts would exist in the planned paths of Ai (i=1,2,3); the phase of conflict coordination should be applied which can be ineluctable. Synthetically, from the perspective of calculational time, the proposed approach excels the approach of [2] remarkably.


#### 5.1.2. Path Planning for Four Mobile Robots without Obstacles

To validate the effectiveness and feasibility of our algorithm under much more complex time-varying environment, the simulation scenario is presented with four mobile robots moving synchronously bound to the limited area. For this case, the essential objective function can be (15), wherein the maximum number of the robots equals 4 and the test data is listed in Table 2.Table 2
Initial information of mobile robotsAi (i=1,2,3,4) in Section 5.1.2.
A
i
P
i
0
P
i
f
T
max
⁡
v
max
⁡
a
max
⁡
A
1
[
0.8,0.8
,
π
/
4
]
T
[
0.2,0.2
,
-
3
π
/
4
]
T
5
0.8
0.5
A
2
[
1.4,0.2,3
π
/
4
]
T
[
0.2,1.4
,
π
/
2
]
T
5
0.8
0.5
A
3
[
0.2,1.4
,
-
π
/
4
]
T
[
1.4,0.2,0
]
T
5
0.8
0.5
A
4
[
0.2,0.2
,
π
/
4
]
T
[
1.4,1.4
,
π
/
4
]
T
5
0.8
0.5The preset safety distances areds_ij=0.25 (i=1,j=2,3), ds_ij=0.25 (i=2,j=3,4), ds_14=0.035, and ds_34=0.25.In the time baseline coordination method, we select the minimized motion time ofAi (i=1,2,3,4) as the coordinate factor in the function (15). Then, after applying the coordination algorithm TimeCoor, the paths of Ai (i=1,2,3,4) are reached as below:
(16)x11(t)=0.8-0.2819t+0.0407t2-0.00167t3,x21(t)=0.8-0.2689t+0.03t2+0.00141t3x21(t)=-0.000257t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x12(t)=1.4-0.291t-0.00735t2+0.0035t3,x22(t)=0.2+0.472t-0.04731t2-0.00136t3x22(t)=+0.000311t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x13(t)=0.2+0.149t+0.0044t2+0.00276t3,x23(t)=1.4-0.3353t+0.0513t2-0.00812t3x23(t)=+0.00036t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x14(t)=0.2+0.326t-0.02121t2+0.00079t3,x24(t)=0.2+0.3003t-0.048t2+0.01446t3x24(t)=-0.001453t4,ccccccccccccccccccccccccccccccccccccct∈[0,5].Figure4 demonstrates the paths evolvement from the perspective of five different time intervals [0, 1.15], [1.15, 2.4], [2.4, 3.4], [3.4, 5], and [0, 5]. In Figure 4, the subfigures from (a) to (e) show that each mobile robot smoothly moves from its start pose to end pose without any collision.Planned paths evolvement ofAi (i=1,2,3,4) in Section 5.1.2. (a) In [0, 1.15], (b) in [1.15, 2.4], (c) in [2.4, 3.4], (d) in [3.4, 5], and (e) in [0, 5].
(a)
(b)
(c)
(d)
(e)The variation curves of velocities and acceleration along with time are shown in Figures5(a) and 5(b), respectively. Curves in Figure 5 are sufficient to the requirements of the constraints in Table 2 fully. Thus, the planned paths are consistent with the constraints of kinematics.(a)v-t, (b) a-t in Section 5.1.2.
(a)
(b)Furthermore, Figure6 illustrates that the variation of safety distances d12,d13,d14,d23,d24, and d34 lives up to the predefined requirements quite well.Figure 6
Variation curve of safety distanced-t in Section 5.1.2.In a word, with above verification, it is substantiated that our approach is effective for path planning problems with even much more time-varying environment.


### 5.2. Path Planning for Mobile Robots with Static and Moving Obstacles

The path planning optimization function for multiple mobile robots with static and moving obstacles is the same as (14). To test the effectiveness of algorithm TimeCoor for multiple mobile robots path planning with stationary and moving obstacles, we use the data in Table 3 and the information of two stationary obstacles O1, O2 and one moving obstacle O3. For O1 and O2, α1=(0.5,0.6), α2=(0.8,0.9), dobs_1k=0.05, dobs_2k=0.03, robsk=0, and k=1,2. Trajectory of O3 is one curve from left to right, which is expressed as below and safety distance is set as dobs_i3=0.16, i=1,2:
(17)α31(t)=0.27+0.02t+0.0043t2,α32(t)=0.6+0.01t+0.001t2-0.00008t3,cccccccccccccccccccccccccccccccct∈[0,10].Table 3
Initial information of mobile robotsAi (i=1,2) in Section 5.2.
A
i
P
i
0
P
i
f
T
max
⁡
v
max
⁡
a
max
⁡
A
1
[
0.2,1
,
-
π
/
4
]
T
[
1,0.5
,
-
3
π
/
4
]
T
5
0.3
0.4
A
2
[
1,0.2
,
-
3
π
/
4
]
T
[
0.6,1
,
-
3
π
/
4
]
T
10
0.25
0.4With our approach, fort1∈[0,5] and t2∈[0,10], the expressions of the planned paths are given as below and corresponding curves with time intervals [0,2.1]  [2.1,4][4,10], and [0,10] are shown in Figure 7. It demonstrates that, with our planned paths, there is no collision among the motion process of the two mobile robots and the three obstacles static and moving:
(18)x11(t1)=0.2+0.0711t1+0.0095t12+0.0017t13,x21(t1)=1-0.08t1-0.04t12+0.01t14-0.0006t14,x12(t2)=1+0.0011t2-0.009t22+0.0005t23,x22(t2)=0.2+0.25t2-0.011t22-0.003t23+0.0002t24.Planned paths ofA1 and A2 with different time intervals in Section 5.2. (a) In [0, 2.1], (b) in [2.1, 4], (c) in [4, 10], and (d) in [0, 10].
(a)
(b)
(c)
(d)Thev-t and a-t curves are given in Figures 8(a) and 8(b), respectively. From Figure 8, it is verified that the velocity and acceleration constraints are satisfied, and then the kinematics constraints are met as well.(a)v-t, (b) a-t in Section 5.2.
(a)
(b)Distances variation curvesd12, dobs_11, dobs_12, dobs_13, dobs_21, dobs_22, and dobs_23 between mobile robots A1 and A2, Ai and Ok (i=1,2, k=1,2,3) are shown in Figure 9. In Figure 9, the safety distance constraints are satisfied as all the distances are in accordance with the corresponding requirements.Figure 9
Variation curves of safety distanced-t in Section 5.2.With this case, it is verified that our approach is effective for multiple mobile robots path planning under the time-varying environment with stationary and moving obstacles.


## 5.1. Path Planning for Multiple Mobile Robots without Obstacles

When it comes to the case of multiple mobile robots moving synchronously in the environment without obstacles, for1≤i, j≤J, i≠j, the essential objective function can be
(15)min⁡∑i=1J‍h(2∑f=1F‍Ei(fh)-E(0)-Ei(tfi))2s.t.vi(t)≤vmax⁡it∈[0,tfi]s.t.ai(t)≤amax⁡it∈[0,tfi]s.t.Pi(0)=(x0i,θ0i)s.t.Pi(tfi)=(xfi,θfi)s.t.X0i,Xfi∈Xi∈[1,J]s.t.ds_ij-dij(t)≤0,t∈[0,max⁡(tfi,tfj)].


### 5.1.1. Path Planning for Three Mobile Robots without Obstacles

In the first case, to test the validity of our approach, we choose the data listed in Table1 from recently published work [8] to examine the effectiveness of our algorithm. Approach in [8] was based on fourth-order Bezier curve.Table 1
Initial information of mobile robotsAi (i=1,2,3) in Section 5.1.1.
A
i
P
i
0
P
i
f
v
0
v
f
v
max
⁡
A
1
[
0.2,1.4
,
-
π
/
4
]
T
[
1.4,0.2
,
-
π
/
4
]
T
0.4
0.4
0.8
A
2
[
1.4,0.2,3
π
/
4
]
T
[
0.2,1.4,3
π
/
4
]
T
0.4
0.5
0.8
A
3
[
0.2,0.2
,
π
/
4
]
T
[
1.4,1.4
,
π
/
4
]
T
0.4
0.4
0.8In [8], the safety distances, the maximum motion time, and the maximum accelerations are given as ds_ij=0.35, Tmax⁡i=5, and amax⁡i=0.5 (i,j=1,2,3, i≠j), respectively.Within our approach, in order to fulfill the coordination, the minimized motion time of all the mobile robotsAi (i=1,2,3) is chosen as the time baseline which is used for coordination. Subsequently, applying the coordination algorithm TimeCoor, for t∈[0,5], paths of Ai (i=1,2,3) are obtained as below:A1=[0.20.2828-0.1660.097-0.0210.001];B1=[1.4-0.28280.198-0.0730.007];A2=[1.4-0.28280.518-0.0520.017-0.002];B2=[0.20.283-0.1270.041-0.004];A3=[0.20.28280.216-0.1160.019-0.001];B3=[1.40.28280.145-0.0650.007];TAi=[1titi2ti3ti4ti5];TBi=[1titi2ti3ti4ti5].Corresponding to Figures1(a), 1(b), and 1(c), our planned paths evolve from the perspective of three different time intervals [0, 2.3], [2.3, 5], and [0, 5]. In Figures 1(a), 1(b), and 1(c), it is shown that each mobile robot smoothly moves from its initial pose to final pose without any collision. The paths of [8] in the time interval [0,5] are shown in Figure 1(d). Thus, our approach based on TimeCoor can manipulate the multiple mobile robots path planning problems successfully.Planned paths evolvement ofAi and paths of [8], i=1,2,3. (a) In [0, 2.3], (b) in [2.3, 5], (c) in [0, 5], and (d) in [0, 5].
(a)
(b)
(c)
(d)The variation curves of velocities and accelerations along the time are shown in Figures2(a) and 2(b), respectively. Curves in Figure 2 are sufficient to the constraints in Table 1 and all other requirements in [8] fully. Then the planned paths meet the constraints of kinematics.(a)v-t, (b) a-t in Section 5.1.1.
(a)
(b)Figure3 illustrates that the variation of safety distances d12, d13, and d23 is satisfied with the predefined requirements in this case.Figure 3
Variation curve of safety distanced-t in Section 5.1.1.In our approach, the polynomials are general that are more flexible than the polynomials of [8] which are limited to four. Meanwhile, with approach in [8], prior to path planning, the initial and final velocities of each mobile robot should be specified in detail. Generally, in practice, the velocities belong to some certain intervals, not the constant predefined value. Contrastively, our approach is much more suitable for the general multiple mobile robots path planning problems.Compared to our prior work in [2], the paths of Ai (i=1,2,3) should be calculated for three times in the path planning phase. In our approach, it only takes a third of the time in the first phase of [2] to reach the conflict-free solution. Furthermore, the planned paths of A1 and A2 in [2] are almost overlapped, and the conflicts would exist in the planned paths of Ai (i=1,2,3); the phase of conflict coordination should be applied which can be ineluctable. Synthetically, from the perspective of calculational time, the proposed approach excels the approach of [2] remarkably.


### 5.1.2. Path Planning for Four Mobile Robots without Obstacles

To validate the effectiveness and feasibility of our algorithm under much more complex time-varying environment, the simulation scenario is presented with four mobile robots moving synchronously bound to the limited area. For this case, the essential objective function can be (15), wherein the maximum number of the robots equals 4 and the test data is listed in Table 2.Table 2
Initial information of mobile robotsAi (i=1,2,3,4) in Section 5.1.2.
A
i
P
i
0
P
i
f
T
max
⁡
v
max
⁡
a
max
⁡
A
1
[
0.8,0.8
,
π
/
4
]
T
[
0.2,0.2
,
-
3
π
/
4
]
T
5
0.8
0.5
A
2
[
1.4,0.2,3
π
/
4
]
T
[
0.2,1.4
,
π
/
2
]
T
5
0.8
0.5
A
3
[
0.2,1.4
,
-
π
/
4
]
T
[
1.4,0.2,0
]
T
5
0.8
0.5
A
4
[
0.2,0.2
,
π
/
4
]
T
[
1.4,1.4
,
π
/
4
]
T
5
0.8
0.5The preset safety distances areds_ij=0.25 (i=1,j=2,3), ds_ij=0.25 (i=2,j=3,4), ds_14=0.035, and ds_34=0.25.In the time baseline coordination method, we select the minimized motion time ofAi (i=1,2,3,4) as the coordinate factor in the function (15). Then, after applying the coordination algorithm TimeCoor, the paths of Ai (i=1,2,3,4) are reached as below:
(16)x11(t)=0.8-0.2819t+0.0407t2-0.00167t3,x21(t)=0.8-0.2689t+0.03t2+0.00141t3x21(t)=-0.000257t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x12(t)=1.4-0.291t-0.00735t2+0.0035t3,x22(t)=0.2+0.472t-0.04731t2-0.00136t3x22(t)=+0.000311t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x13(t)=0.2+0.149t+0.0044t2+0.00276t3,x23(t)=1.4-0.3353t+0.0513t2-0.00812t3x23(t)=+0.00036t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x14(t)=0.2+0.326t-0.02121t2+0.00079t3,x24(t)=0.2+0.3003t-0.048t2+0.01446t3x24(t)=-0.001453t4,ccccccccccccccccccccccccccccccccccccct∈[0,5].Figure4 demonstrates the paths evolvement from the perspective of five different time intervals [0, 1.15], [1.15, 2.4], [2.4, 3.4], [3.4, 5], and [0, 5]. In Figure 4, the subfigures from (a) to (e) show that each mobile robot smoothly moves from its start pose to end pose without any collision.Planned paths evolvement ofAi (i=1,2,3,4) in Section 5.1.2. (a) In [0, 1.15], (b) in [1.15, 2.4], (c) in [2.4, 3.4], (d) in [3.4, 5], and (e) in [0, 5].
(a)
(b)
(c)
(d)
(e)The variation curves of velocities and acceleration along with time are shown in Figures5(a) and 5(b), respectively. Curves in Figure 5 are sufficient to the requirements of the constraints in Table 2 fully. Thus, the planned paths are consistent with the constraints of kinematics.(a)v-t, (b) a-t in Section 5.1.2.
(a)
(b)Furthermore, Figure6 illustrates that the variation of safety distances d12,d13,d14,d23,d24, and d34 lives up to the predefined requirements quite well.Figure 6
Variation curve of safety distanced-t in Section 5.1.2.In a word, with above verification, it is substantiated that our approach is effective for path planning problems with even much more time-varying environment.


## 5.1.1. Path Planning for Three Mobile Robots without Obstacles

In the first case, to test the validity of our approach, we choose the data listed in Table1 from recently published work [8] to examine the effectiveness of our algorithm. Approach in [8] was based on fourth-order Bezier curve.Table 1
Initial information of mobile robotsAi (i=1,2,3) in Section 5.1.1.
A
i
P
i
0
P
i
f
v
0
v
f
v
max
⁡
A
1
[
0.2,1.4
,
-
π
/
4
]
T
[
1.4,0.2
,
-
π
/
4
]
T
0.4
0.4
0.8
A
2
[
1.4,0.2,3
π
/
4
]
T
[
0.2,1.4,3
π
/
4
]
T
0.4
0.5
0.8
A
3
[
0.2,0.2
,
π
/
4
]
T
[
1.4,1.4
,
π
/
4
]
T
0.4
0.4
0.8In [8], the safety distances, the maximum motion time, and the maximum accelerations are given as ds_ij=0.35, Tmax⁡i=5, and amax⁡i=0.5 (i,j=1,2,3, i≠j), respectively.Within our approach, in order to fulfill the coordination, the minimized motion time of all the mobile robotsAi (i=1,2,3) is chosen as the time baseline which is used for coordination. Subsequently, applying the coordination algorithm TimeCoor, for t∈[0,5], paths of Ai (i=1,2,3) are obtained as below:A1=[0.20.2828-0.1660.097-0.0210.001];B1=[1.4-0.28280.198-0.0730.007];A2=[1.4-0.28280.518-0.0520.017-0.002];B2=[0.20.283-0.1270.041-0.004];A3=[0.20.28280.216-0.1160.019-0.001];B3=[1.40.28280.145-0.0650.007];TAi=[1titi2ti3ti4ti5];TBi=[1titi2ti3ti4ti5].Corresponding to Figures1(a), 1(b), and 1(c), our planned paths evolve from the perspective of three different time intervals [0, 2.3], [2.3, 5], and [0, 5]. In Figures 1(a), 1(b), and 1(c), it is shown that each mobile robot smoothly moves from its initial pose to final pose without any collision. The paths of [8] in the time interval [0,5] are shown in Figure 1(d). Thus, our approach based on TimeCoor can manipulate the multiple mobile robots path planning problems successfully.Planned paths evolvement ofAi and paths of [8], i=1,2,3. (a) In [0, 2.3], (b) in [2.3, 5], (c) in [0, 5], and (d) in [0, 5].
(a)
(b)
(c)
(d)The variation curves of velocities and accelerations along the time are shown in Figures2(a) and 2(b), respectively. Curves in Figure 2 are sufficient to the constraints in Table 1 and all other requirements in [8] fully. Then the planned paths meet the constraints of kinematics.(a)v-t, (b) a-t in Section 5.1.1.
(a)
(b)Figure3 illustrates that the variation of safety distances d12, d13, and d23 is satisfied with the predefined requirements in this case.Figure 3
Variation curve of safety distanced-t in Section 5.1.1.In our approach, the polynomials are general that are more flexible than the polynomials of [8] which are limited to four. Meanwhile, with approach in [8], prior to path planning, the initial and final velocities of each mobile robot should be specified in detail. Generally, in practice, the velocities belong to some certain intervals, not the constant predefined value. Contrastively, our approach is much more suitable for the general multiple mobile robots path planning problems.Compared to our prior work in [2], the paths of Ai (i=1,2,3) should be calculated for three times in the path planning phase. In our approach, it only takes a third of the time in the first phase of [2] to reach the conflict-free solution. Furthermore, the planned paths of A1 and A2 in [2] are almost overlapped, and the conflicts would exist in the planned paths of Ai (i=1,2,3); the phase of conflict coordination should be applied which can be ineluctable. Synthetically, from the perspective of calculational time, the proposed approach excels the approach of [2] remarkably.


## 5.1.2. Path Planning for Four Mobile Robots without Obstacles

To validate the effectiveness and feasibility of our algorithm under much more complex time-varying environment, the simulation scenario is presented with four mobile robots moving synchronously bound to the limited area. For this case, the essential objective function can be (15), wherein the maximum number of the robots equals 4 and the test data is listed in Table 2.Table 2
Initial information of mobile robotsAi (i=1,2,3,4) in Section 5.1.2.
A
i
P
i
0
P
i
f
T
max
⁡
v
max
⁡
a
max
⁡
A
1
[
0.8,0.8
,
π
/
4
]
T
[
0.2,0.2
,
-
3
π
/
4
]
T
5
0.8
0.5
A
2
[
1.4,0.2,3
π
/
4
]
T
[
0.2,1.4
,
π
/
2
]
T
5
0.8
0.5
A
3
[
0.2,1.4
,
-
π
/
4
]
T
[
1.4,0.2,0
]
T
5
0.8
0.5
A
4
[
0.2,0.2
,
π
/
4
]
T
[
1.4,1.4
,
π
/
4
]
T
5
0.8
0.5The preset safety distances areds_ij=0.25 (i=1,j=2,3), ds_ij=0.25 (i=2,j=3,4), ds_14=0.035, and ds_34=0.25.In the time baseline coordination method, we select the minimized motion time ofAi (i=1,2,3,4) as the coordinate factor in the function (15). Then, after applying the coordination algorithm TimeCoor, the paths of Ai (i=1,2,3,4) are reached as below:
(16)x11(t)=0.8-0.2819t+0.0407t2-0.00167t3,x21(t)=0.8-0.2689t+0.03t2+0.00141t3x21(t)=-0.000257t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x12(t)=1.4-0.291t-0.00735t2+0.0035t3,x22(t)=0.2+0.472t-0.04731t2-0.00136t3x22(t)=+0.000311t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x13(t)=0.2+0.149t+0.0044t2+0.00276t3,x23(t)=1.4-0.3353t+0.0513t2-0.00812t3x23(t)=+0.00036t4,ccccccccccccccccccccccccccccccccccccct∈[0,5],x14(t)=0.2+0.326t-0.02121t2+0.00079t3,x24(t)=0.2+0.3003t-0.048t2+0.01446t3x24(t)=-0.001453t4,ccccccccccccccccccccccccccccccccccccct∈[0,5].Figure4 demonstrates the paths evolvement from the perspective of five different time intervals [0, 1.15], [1.15, 2.4], [2.4, 3.4], [3.4, 5], and [0, 5]. In Figure 4, the subfigures from (a) to (e) show that each mobile robot smoothly moves from its start pose to end pose without any collision.Planned paths evolvement ofAi (i=1,2,3,4) in Section 5.1.2. (a) In [0, 1.15], (b) in [1.15, 2.4], (c) in [2.4, 3.4], (d) in [3.4, 5], and (e) in [0, 5].
(a)
(b)
(c)
(d)
(e)The variation curves of velocities and acceleration along with time are shown in Figures5(a) and 5(b), respectively. Curves in Figure 5 are sufficient to the requirements of the constraints in Table 2 fully. Thus, the planned paths are consistent with the constraints of kinematics.(a)v-t, (b) a-t in Section 5.1.2.
(a)
(b)Furthermore, Figure6 illustrates that the variation of safety distances d12,d13,d14,d23,d24, and d34 lives up to the predefined requirements quite well.Figure 6
Variation curve of safety distanced-t in Section 5.1.2.In a word, with above verification, it is substantiated that our approach is effective for path planning problems with even much more time-varying environment.


## 5.2. Path Planning for Mobile Robots with Static and Moving Obstacles

The path planning optimization function for multiple mobile robots with static and moving obstacles is the same as (14). To test the effectiveness of algorithm TimeCoor for multiple mobile robots path planning with stationary and moving obstacles, we use the data in Table 3 and the information of two stationary obstacles O1, O2 and one moving obstacle O3. For O1 and O2, α1=(0.5,0.6), α2=(0.8,0.9), dobs_1k=0.05, dobs_2k=0.03, robsk=0, and k=1,2. Trajectory of O3 is one curve from left to right, which is expressed as below and safety distance is set as dobs_i3=0.16, i=1,2:
(17)α31(t)=0.27+0.02t+0.0043t2,α32(t)=0.6+0.01t+0.001t2-0.00008t3,cccccccccccccccccccccccccccccccct∈[0,10].Table 3
Initial information of mobile robotsAi (i=1,2) in Section 5.2.
A
i
P
i
0
P
i
f
T
max
⁡
v
max
⁡
a
max
⁡
A
1
[
0.2,1
,
-
π
/
4
]
T
[
1,0.5
,
-
3
π
/
4
]
T
5
0.3
0.4
A
2
[
1,0.2
,
-
3
π
/
4
]
T
[
0.6,1
,
-
3
π
/
4
]
T
10
0.25
0.4With our approach, fort1∈[0,5] and t2∈[0,10], the expressions of the planned paths are given as below and corresponding curves with time intervals [0,2.1]  [2.1,4][4,10], and [0,10] are shown in Figure 7. It demonstrates that, with our planned paths, there is no collision among the motion process of the two mobile robots and the three obstacles static and moving:
(18)x11(t1)=0.2+0.0711t1+0.0095t12+0.0017t13,x21(t1)=1-0.08t1-0.04t12+0.01t14-0.0006t14,x12(t2)=1+0.0011t2-0.009t22+0.0005t23,x22(t2)=0.2+0.25t2-0.011t22-0.003t23+0.0002t24.Planned paths ofA1 and A2 with different time intervals in Section 5.2. (a) In [0, 2.1], (b) in [2.1, 4], (c) in [4, 10], and (d) in [0, 10].
(a)
(b)
(c)
(d)Thev-t and a-t curves are given in Figures 8(a) and 8(b), respectively. From Figure 8, it is verified that the velocity and acceleration constraints are satisfied, and then the kinematics constraints are met as well.(a)v-t, (b) a-t in Section 5.2.
(a)
(b)Distances variation curvesd12, dobs_11, dobs_12, dobs_13, dobs_21, dobs_22, and dobs_23 between mobile robots A1 and A2, Ai and Ok (i=1,2, k=1,2,3) are shown in Figure 9. In Figure 9, the safety distance constraints are satisfied as all the distances are in accordance with the corresponding requirements.Figure 9
Variation curves of safety distanced-t in Section 5.2.With this case, it is verified that our approach is effective for multiple mobile robots path planning under the time-varying environment with stationary and moving obstacles.


## 6. Discussion

In the case of Section5.1.1, from Figure 1, it is shown that the initial and final poses of A1 and A2 are interchanged with each other. Above situations are common in the path planning problems which belong to the classical deadlock problems. If using one multiphase approach, it is hard to present the concerted ideal solution. However, with our overall conflict resolution and time baseline coordination algorithm, we can dispose this problem perfectly. Meanwhile, in the case of Section 5.1.2, from Figures 4, 5, and 6, we can assert that our approach can handle the path planning problems under the complex time-varying environment. Consequently, those numerical case studies substantiate that our proposed approach would do great deeds for robotic industrial production.In the case of Section5.2, from Figure 7, although the trajectory of the moving obstacles almost traverses all the boundaries, no conflict among the planned paths exists. From this case, it is firmly verified that our approach can resolve the path planning problem under the congestive situations with static and moving obstacles which occupied the motion area.In all the numerical cases, we consider the poses constraints of mobile robots, which have not been achieved in most literatures such as [19]. Thus, our algorithm validates for the multiple mobile robots path planning problems with poses’ constraints.


## 7. Conclusions

The path planning problem for multiple mobile robots under the time-varying environment with stationary and moving obstacles has been studied. The considered objective of our formulated TNLPPs is to simultaneously minimize all the paths’ lengths of mobile robots while subjecting to generous constraints. The algorithm consists of the overall conflict resolution and time baseline coordination is suggested to solve this problem. With overall conflict resolution, all conflicts among the planned paths are removed in our objective function. By using the time baseline coordination method, we can attain the high-quality planned paths. With our approach, all the paths just need to be calculated only once; there is no need to calculate the path for each mobile robot one by one. Furthermore, the phase of conflict coordination is not required any more. Numerical examples under various scenarios are utilized to validate the efficiency of our approach. Moreover, since generous metaheuristics have been proposed and developed in recent years, we can integrate our algorithm with those heuristics methods to optimize the analytical solving process in the near future.



---

*Source: 902587-2014-06-22.xml*