Traffic Management Strategies for Multi-Robotic Rigid Payload Transport Systems
Yahnit Sirineni Pulkit Verma Kamalakar Karlapalem

Suppressing the Kibble-Zurek mechanism by a symmetry-violating bias
    V.B. Eltsov
    December 30, 2023
===================================================================

empty
empty



In this work, we address traffic management of multiple payload transport systems comprising of non-holonomic robots. We consider loosely coupled rigid robot formations carrying a payload from one place to another. Each payload transport system (PTS) moves in various kinds of environments with obstacles. We ensure each PTS completes its given task by avoiding collisions with other payload systems and obstacles as well. Each PTS has one leader and multiple followers and the followers maintain a desired distance and angle with respect to the leader using a decentralized leader-follower control architecture while moving in the traffic.  We showcase, through simulations the time taken by each PTS to traverse its respective trajectory with and without other PTS and obstacles. We show that our strategies help manage the traffic for a large number of PTS moving from one place to another.





§ INTRODUCTION

Multi-robot systems are a well studied problem in robotics where applications like payload transportation <cit.><cit.><cit.>, traffic management <cit.><cit.>, and area exploration <cit.><cit.> are most commonly used. A system with multiple robots/agents offers several advantages like low power consumption, increased redundancy, and makes the system modular <cit.><cit.><cit.>. Handling more number of robots poses different challenges on the functionality of the system. Collision avoidance of a system with other neighbourhood transport systems and other obstacles in the environment is an important challenge. The basic idea of collision avoidance is that a system derives the control inputs based on its surroundings such that it does not collide with any other system or obstacles while performing its task. Work has been carried out on avoiding the obstacles for a single or multiple robots <cit.>, further research is needed on obstacle avoidance for multiple robots moving in a formation(s) of different shapes.
For payload carrying tasks in industries, assembly lines, warehouses, etc., where payloads need to be transported from one place to another without affecting the functionality of other systems, is a challenging problem. Such applications require smooth and collision free movement of these systems such that 
    
  * A PTS does not collide with the other payload systems in the surroundings.
    
  * Avoids collisions with static obstacles.
    
  * Reaches the destination by following the desired trajectory.

In our work, we simulate multiple PTS carrying payloads of different shapes (like triangular, square, circle, etc.) from one point to another. Each system comprises of a group of non-holonomic robots moving in a formation using a decentralized leader-follower approach in <cit.>. One leader and multiple followers are present in each system. The leader uses the trajectory information provided by our control architecture which is derived from source to destination. The followers generate their velocities using the leader information which makes the formation intact all the time. We show, through simulations, the time taken by a PTS to move from one point to another in an environment with [label=(a),font=]
    
  * Only one payload transport system.  
 
[label=(b),font=]
    
  * Multiple PTS with a possibility of having a collision 
 
[label=(c),font=]
    
  * Multiple PTS and static obstacles in the environment.

We propose a modified version of Optimal Reciprocal Collision Avoidance for non-holonomic robots (nh-ORCA) <cit.> algorithm to identify if a PTS is prone to collide with other formations and obstacles in the environment. Our method provides the command velocities to the robots in the formation such that no collision happens while the transport system is approaching its goal and also ensures least deviation possible to the existing path of the formation. We present the simulation results for different formation shapes with and without obstacles. We discuss the related work done in this domain in Section <ref>. Our contribution in this paper is discussed in Section <ref>. The modeling and control of non-holonomic robots is carried out in Section <ref>. Traffic Management strategies for multiple PTS are discussed in Section <ref>.  To make our solution more concrete, we display simulation results in Section <ref>. Conclusion is discussed in Section <ref>





§ RELATED WORK


Over the years, various methods have been developed for formation control and navigation of formations for payload transportation. <cit.>, <cit.> propose methods for path planning of a single formation without laying much emphasis on the presence of obstacles.  <cit.>,  <cit.>, <cit.>,    <cit.> shows navigation of single formation in environments which consists of static obstacles.Path planning for 3D formations is proposed in <cit.> and <cit.>.  Method for navigating a single formation using the leader-follower approach is shown in <cit.> and <cit.>. <cit.>,<cit.> shows some promising results in aerial vehicle formation control. A slung payload transportation method is demonstrated in <cit.> where as <cit.> devised wheeled locomotion for payload carrying with modular robot. <cit.> proposes path planning of a single formation in environment with dynamic obstacles but is a computationally expensive centralized method. 

To the best of our knowledge, no work has been done on path planning and collision avoidance of multiple formations of robots in environments with obstacles. We cannot consider other formations as dynamic obstacles and use the approach presented in <cit.> because the formations have a specific goal of reaching the destination while dynamic obstacles do not have a proper goal and hence show random behaviour. This aspect makes our task even more challenging .




§ CONTRIBUTION



We propose a Leader-Follower-ORCA-RRT* framework which is a decentralized method for navigation of multiple formations of robots carrying payloads to the desired destination while avoiding collisions with other formations and obstacles. Given an environment in which multiple payloads are to be transported from one place to another through formation of robots, we first compute the path of the leader of the formation using RRT* <cit.> from respective source to destination considering the static obstacles and interpolate the path to get multiple way points. We modify nh-ORCA <cit.> to compute  collision-free linear and angular velocity for the leader of the formation. A leader-follower based decentralized control law is incorporated to compute the corresponding command velocities of the followers in the formation. Finally, We present simulation results of the implemented control architecture to validate our method. 






§ BACKGROUND




 §.§ Non-holonomic Robot Kinematics

Consider a non-holonomic mobile robot positioned at (x, y) and oriented at and angle θ. Assuming the pseudo-command velocities be v, ω, the robot kinematics is given as

    [ [  ẋ;  ẏ; θ̇;    ]] =
      [ [    cosθ -d sinθ;    sinθ  d cosθ;       0       1;         ]] [ [ v; ω;   ]]

where d is the distance of the robot's center to the center of mass of the robot.


 §.§ Leader-Follower Formation Control
 
Each PTS comprises of a number of non-holonomic wheeled mobile robots which move on a trajectory while maintaining a rigid formation. A decentralized leader-follower approach control algorithm <cit.> is used which include a leader and multiple followers. The followers use the command velocities and odometery information of the leader to derive their velocities such that the followers maintain a specified distance and angle to remain in a formation. Fig. <ref> shows different shapes of the formation used in the paper. The formation control law is given by the following equations


    v_j   =    (k_1α_j + v_i cos θ_ij - ρ^d_ijω_i sin(ψ^d_ij - θ_ij) 
    ω_j   =   v_isinθ_ij + ρ^d_ijω_i cos(ψ^d_ij + θ_ij) + k_2β_j + k_3θ_je/d

where α_j and β_j is the error in longitudinal and vertical direction respectively. Constants k_1, k_2, k_3, k_4, k_5, k_6 > 0, ρ^d_ij and ψ^d_ij are the desired distance and orientation to maintain between the leader and follower robot, v_i and ω_i are command velocities of the leader, v_j and ω_j are the generated command velocities of the j^th follower, d is distance from the robot's center to the robot's center of mass. θ_ij is the orientation error and x_je, y_je, θ_je are the positional tracking errors between the leader and follower.



 §.§ Optimal Reciprocal Collision Avoidance for non-holonomic robots (nh-ORCA)

nh-ORCA <cit.> is a collision avoidance algorithm for non-holonomic robots which is an extension to ORCA<cit.> which deals with only holonomic robots.

Using the algorithm presented in <cit.>, each robot independently computes its velocity such that it is collision free for at least τ time assuming that the other robots also compute their velocity using the same method. There is no explicit communication amongst the robots to choose their velocities, hence making this is a robust decentralized system.  Each robot i constructs ORCA^τ_i|j ∀ j ≠ i  which in turn is computed using velocity obstacles presented in <cit.>.  

Let p_i, p_j be the positions of two robots i and j and r_i, r_j be the radius of the robots respectively,
VO^τ_i|j is the set of velocities of robot i w.r.t robot j such that:
 
 
    VO^τ_i|j = {v̅|∃ t ∈ [ 0, τ ], t ·v̅∈ D  ( p_j - p_i, r_i + rj ) }

where 

    D ( p, r  ) = { q |∥ q-p ∥ < r }

 







Then ORCA^τ_i|j is computed from Eq (<ref>):


    ORCA^τ_i|j = { v_H_i| ( v_H_i -  ( v_i^opt + 0.5*u  )  ).n≥ 0 }


where n denotes the outward normal of the boundary of VO_i|j at (v_i^opt-v_j^opt) + u, u is computed as shown in  <cit.>.

Now, the set of collision free velocities for robot i is given by Eq (<ref>).


    ORCA^τ_i = S_AHV_i∩⋂_j ≠ i ORCA^τ_i | j

with S_AHV_i being the set of allowed velocities.
The final optimal velocity of the robot is given by equation (<ref>).


    v_H_i^* = _v_H_i∈ ORCA_i^τ∥v_H_i - v_i^pref∥


We extend this approach to our problem for avoiding collisions among other formations and obstacles.



§ TRAFFIC MANAGEMENT


Given an environment in which multiple payloads are to be transported from one place to another with multi-robot payload transport systems, we propose an efficient traffic management strategies for path planning and collision avoidance of formations carrying payloads. A bio inspired neurodynamic based leader follower-ORCA-RRT* framework is discussed, which computes a path to the respective destination for all the leaders of PTS considering the static obstacles using RRT* <cit.>, then uses a modified version of nh-ORCA <cit.> for collision avoidance amongst other formations and finally incorporates a bio inspired neurodynamic based leader-follower formation control law for computing the command velocities for the followers in the formation. The architecture diagram has been shown in Fig.<ref>





Multiple PTS are considered in this work. Each PTS is a set of robots with a leader and its followers working together to perform a particular task. Follower j of each formation (f_i) maintains a certain angle and distance relative to its leader.  
Each formation f_i has a current position p_i, radius r_i,  current velocity v_i, number of followers followers_i, source src_i, destination dest_i, next immediate destination nextDest_i, preferred velocity v^pref_i i.e the velocity with which it would traverse had there been no obstacles in its path,  maximum velocity v^max_i, neighbours neighbours_i which indicates the formations in its vicinity, neighbourDist_i which refers to the formations that are at a distance less than this value.We use the RRT* to find the preferred path from src_i to dest_i for each formation f_i and interpolate the path returned by RRT* to get multiple way points in the path. The nextDest_i for each formation i is set to the first point of the interpolated path indicating that the formation's tentative target is to reach the nextDest_i and v^pref_i for each formation is set to (nextDest_i - p_i).For each timestep dt, new collision avoiding velocities are computed for each of the leaders of the formations through Algorithm <ref>. To compute the collision avoidance velocities for each formation f_i, consider all the neighbours j in neighbours_i for formation f_i and compute VO^τ_i|j and ORCA^τ_i|j from Eq.(<ref>) and Eq(<ref>) for all the neighbours j in neighbours_i and compute u from <cit.>. Now, compute ORCA^τ_i and v_H_i^* from Eq(<ref>) and Eq(<ref>) to get the holonomic velocity of the leader of the formation f_i. Now, map the holonomic velocity to non-holonomic velocities as illustrated in <cit.>. If the formation f_i at a distance less than δ from nextDest_i where δ is a parameter to be set based on the environment, then update the nextDest_i to the next point of the interpolated path and the preferred velocity of formation v^pref_i to (nextDest_i - p_i). This modified version of nh-ORCA is given in Algorithm <ref>.Once the leader velocities of the formations are computed using Eq.(<ref>), command velocities of all the followers are computed using Eq. (<ref>) which are then applied to all the robots. The complete algorithm is illustrated in Algorithm <ref>



§ RESULTS






We showcase the simulation results of the presented algorithm and discuss various aspects of the system. In the simulations,we consider a Baseline scenario in which a payload transport system is carrying a payload from one place to another while there are no other transport systems and  static obstacles in the surroundings. We compare the baseline results with [label=(a),font=]
    
  * Multiple PTS moving in the environment
  
[label=(b),font=]
    
  * Multiple PTS and static obstacles in the environment
. We compare the time taken, velocity variations and scalability aspect of this approach with the baseline result. 


 §.§ Multiple Payload Transport Systems

In this case, we consider four payload transport systems carrying a payload to their respective destinations. Each PTS has to avoid the traffic as posed by the other transport systems while heading towards the destination simultaneously. 

Different shapes (circle, square, triangle) are considered for different PTS to make the problem more challenging. Each formation has different number of robots ranging from 3-10. However, the number of formations in an environment and number of robot in a formation is not limited and will discussed in latter part of the section. Fig. <ref> shows the initial set of all the Payload transport systems present and their respective goal points (denoted by the same color). The simulation is symmetric and hence all formations travel almost the same distance.
We compare the time taken by the system in this environment with a system having no traffic in the environment. Fig. <ref> shows that the time taken by the system in presence of traffic is approximately equal to a system moving in no traffic environment. This time is nearly equal, as all the PTS create a symmetric trajectory and hence takes nearly equal time to reach their destination. 
It is important to note that all the payload transport systems maintain a minimum distance from each other ensuring no collision while in motion. Fig. <ref> shows the distance maintained by each PTS to its closest neighbourhood. The figure shows that all the PTS are maintaining a minimum threshold and hence it is clear that the payload systems are not colliding with each other. The change in the velocities of each PTS when coming close to each other is shown in Fig. <ref>. We can see that whenever the PTS are coming close to each other, the velocities of the followers in the formation experiences a changes such that the collision can be avoided. Points A, B, C, D are marked in Fig. <ref> and Fig. <ref> which can be used to relate the two graphs. We can observe that at point B, all the formation are close to each other (see Fig. <ref>(f)) and hence suffers a velocity change in the robots of all the PTS. Similarly, point A, C are the points where the PTS started changing the trajectory to successfully avoid the obstacles. 


While avoiding traffic in the surroundings, we ensure that each payload transport system maintains the robots formation using the leader-follower based approach. Fig. <ref> depicts that the followers in each formation nearly maintains the desired distance and orientation from the leader. For simulation, we have considered this distance constant for all the followers in all the PTS, which is equal to 0.35 m. The figure shows that the distance of each followers from the leader is approximately equal to 0.35, even when a system avoids any collision with its neighbourhood.


 §.§ Multiple Payload Transport Systems with Static Obstacles

To make our results more concrete, we consider an environment where there are multiple PTS are moving along with the static obstacles between the start point and the destination. 

We consider four payload transport systems carrying a payload. Five static obstacles are considered at random places in the arena. Each payload transport system receives the trajectory information using Algorithm <ref> such that there is no collision amongst the PTS and static obstacles. Fig. <ref> shows a initial set up of all formations and the obstacles present in the surroundings. We observe that all the systems successfully avoid collision with the obstacles.  
We compare the time taken by the PTS to reach to their respective destinations with and without obstacles. Fig. <ref> shows that the time taken by the PTS in presence of obstacles is comparable to the time taken by the PTS in no obstacles scenario. We conclude that an optimal collision avoiding path is provided by our control algorithm. 

In this case, we plot the minimum distance of a PTS which is to be maintained wrt. neighbourhood PTS (similar to the previous case with no static obstacle). This will make sure that the formations do not collide with each other. Fig. <ref> shows the minimum distance maintained by each PTS with its closest neighbourhood PTS. We present a change in the velocities of each PTS when coming close to each other Fig. <ref>. We observe, a PTS changes its velocities (as generated by the nh-ORCA) such that it avoids any collision with other obstacles. As discussed in the above case, we mark points in Fig. <ref> and Fig. <ref> to relate the change in velocities of the formation in the vicinity of the other formations or static obstacles. For example, formation 2 and formation 4 come close to each other at Point B and the velocity of both the formation also changes at the same to avoid any obstacle (see Fig. <ref>). 

It is even more challenging in this case to maintain the formation for each PTS as the static obstacles in the surroundings make it more difficult to maintain the desired distance and angles of the follower with the leader robot. Fig. <ref> highlights that the followers in each PTS is maintaining the specified parameters with the leader when avoiding the obstacles. For simulation of this scenario also, we have taken the distance of followers w.r.t to leader to be 0.35 m. 


 §.§ Scalability analysis of the system

Our system scales well with the increase in number of PTS, hence making it more efficient and robust. We showcase through simulations, that our system works well with 30 different payload transport systems with variable number of robots in each of them. But, in general, it can be extended to any number of PTS. Fig. <ref> shows that all the PTS reach their destination to complete a given task without colliding with any of the neighbourhood PTS. Thus our system is more robust and reliable to work with large number of PTS in an industrial/warehouse environment. We have added more detailed results and simulations of the scalability in the video uploaded.






§ CONCLUSION


We simulate the traffic management strategies for multiple loosely coupled payload transport system. Each PTS comprises of a number of non-holonomic mobile robots which are moving in a formation and carrying a payload from one place to another. The formation control is done using a decentralized leader-follower based algorithm. A modified version of decentralized collision avoidance algorithm nh-ORCA is used to compute the collision-free velocities for the leader of the formation. The followers follow the leader such that a rigid formation is maintained while simultaneously moving towards a goal. Various environments are considered for the simulation which includes [label=(a),font=]
    
  * Multiple PTS are running with no other obstacles
  
[label=(b),font=]
    
  * Multiple PTS are running with static obstacles
. A comparison is made with a baseline scenario where individual PTS are moving to reach a goal.

ieeetr


