The last decade has witnessed substantial technological advances of multi-robot systems that enabled a vast range of applications including autonomous transportation systems, multi-robot exploration, rescue and security patrols. Multi-robot systems demonstrated notable advantages over single-robot systems such as enhanced efficiency in task execution, reconfigurability and fault tolerance. Particularly, the capability of multi-robot systems to self-organize via local interaction gives rise to various multi-robot collective behaviors (e.g., flocking, formation, area coverage) to achieve team-level objectives (Guo, 2017).
A plethora of control methods has contributed to the development of multi-robot autonomy that enables complex collective behaviors of multi-robot systems. One major control design paradigm focuses on decentralized feedback control methods (Cortés and Egerstedt, 2017;Panagou et al., 2015;Bechlioulis et al., 2019) which provide provable control and coordination protocols that can be executed efficiently at run time. Control protocols are designed to compute robot actions analytically using robot's kinematic/dynamic model and communication graph that specifies the interaction connectivity for local information exchange.
Such hand-engineered control and coordination protocols separate the problem into a set of sequentially executed stages including perception, state measurement/estimation, and control. However, this pipeline of stages could suffer from perception and state estimation errors which compound through the sequential individual stages (Loquercio et al., 2021;Zhang and Scaramuzza, 2018). Moreover, such pipeline introduces latency between perception and actuation as the time necessary to process perception data and compute control command accumulates (Falanga et al., 2019). Both compounding errors and latency are well-known issues that impact task performance and success in robotics. Learning-based methods, as another control design paradigm, has proven to be successful in learning control policies from data (Kahn et al., 2018;Li et al., 2020;Devo et al., 2020;Li et al., 2022). Particularly, owing to the feature representation capability of deep neural networks (DNNs), control policies can be modeled to synthesize a control command directly from a raw sensor observation. Such control policies are trained to model an end-to-end computation that encompasses the traditional pipeline of stages and their underlying interactions (Loquercio et al., 2021).
Multi-robot learning has long been an active research area (Stone and Veloso, 2000;Gronauer and Diepold, 2021). Nonetheless, it wasn't until recent years that challenges originating from real-world complexities can be handled with the advancement of deep reinforcement learning techniques. Breakthroughs on computational methods have been made to address long-standing challenges in multi-robot learning such as non-stationarity (Foerster et al., 2017;Lowe et al., 2017;Foerster et al., 2018), learning to communicate (Sukhbaatar et al., 2016;Foerster et al., 2016;Jiang and Lu, 2018), scalability (Gupta et al., 2017).
Various multi-robot control problems such as path planning (Blumenkamp et al., 2022;Wang et al., 2021), coordinated control (Tolstaya et al., 2020a;Yan et al., 2022;Agarwal et al., 2020;Zhou et al., 2019;Tolstaya et al., 2020b;Kabore and Güler, 2021;Jiang and Guo, 2020) have been tackled using learning-based methods. Despite the remarkable progress in multi-robot learning, the architecture design and learning of scalable computational models that accommodate emerging information structures is still an open question.
For example, it has yet to be understood what and how information should be dynamically gathered given the distributed information structure that only allows local inter-robot interaction. Recently, graph neural networks (GNNs) (Scarselli et al., 2008) were used to model the information-sharing structure between robots. A GNN can be trained to capture task-relevant information to be propagated and shared in the robot team via local inter-robot communication. GNNs have become an appealing framework for modeling distributed robot networks (Agarwal et al., 2020;Zhou et al., 2019;Tolstaya et al., 2020a,b;Wang and Gombolay, 2020;Blumenkamp et al., 2022) due to their scalability and permutation-invariance (Gama et al., 2020).
In this paper, we study a multi-robot formation problem using a learning-based method to find decentralized control policies that operate on robot sensor observations. The formation problem is defined for the multi-robot team to achieve triangulation formations that constitute a planar graph with prescribed equidistant edge lengths. We use a GNN to model the inter-robot communication for learning scalable control policies. The GNN is combined with a convolutional neural network (CNN) to process sensor-level robot observations. Utilizing a model-based decentralized controller for triangulation formation as an expert control, we train the deep neural network (DNN) with a data aggregation training scheme. We demonstrate in a robot simulator that the learned decentralized control policy is scalable to different sizes of multi-robot teams while trained with a fixed number of robots.
The main contributions of this paper is the GNN-based end-to-end decentralized control for multi-robot triangulation formation. Comparing to our prior work (Jiang et al., 2019) on learning-based end-to-end control of multi-robot formation, this paper achieves decentralized scalable control policy, while our prior work (Jiang et al., 2019) adopts centralized training mechanism and the trained policy is not scalable and applies to three-robot formation only. Comparing to the recent GNN-based flocking control method (Tolstaya et al., 2020a), the triangulation formation studied in this paper imposes additional geometric constraints for multi-robot coordinated motion in comparison with the flocking behavior in Tolstaya et al. (2020a). Furthermore, our decentralized control scheme is end-to-end and takes robot LIDAR sensor data as input directly, while the method in Tolstaya et al. (2020a) takes state values of robot positions as input.
As mentioned earlier, the end-to-end learning facilitates direct learning from sensor data, and can avoid potential compounding errors and latency issues commonly found in conventional design that separates perception and control in sequential stages of a pipeline.
The rest of the paper is organized as follows. Section 2 presents the model of differential-drive mobile robots, and formulates our multi-robot cooperative control problem. The GNN-based training and online control methods are described in Section 3. Robot simulation results are demonstrated in Section 4.
Section 5 discusses the main difference compared to existing learning-based methods. The paper is finally concluded in Section 6.
In this paper, we consider a multi-robot cooperative control problem with N differential-drive mobile robots. The kinematic model of each robot i ∈ {1, ..., N } is given by the discrete-time model:
where [x i , y i , θ i ] T ∈ R 3 is the robot state vector that consists of the position p i ≜ [x i , y i ] T and the orientation θ i ; u i ≜ [u iL , u iR ] T ∈ R 2 is the control vector with u iL and u iR being the left and right motor control, respectively. The matrix G(t) is defined as:
where ∆T is the sampling period and l is the distance between the robot's left and right wheels.
We assume that each robot is equipped with a LIDAR sensor to detect neighboring robots. The LIDAR measurements are transformed to an occupancy map, denoted by o i (t), serving as the robot's local observation. The proximity graph of the robot team is defined as a Gabriel graph (Mesbahi and Egerstedt, 2010), denoted as G = (V, E), where V = {v 1 , ..., v N } is the set of vertices corresponding to the robots located at p 1 , ..., p N ∈ R 2 and E is the set of edges. The "line" connecting the vertices v i , v j ∈ V , i ̸ = j, is said to be an edge if and only if the circle of diameter, ∥p i -p j ∥, containing both vertices v i and v j does not contain any vertex in its interior. An example of a valid and an invalid edge of a Gabriel graph can be seen in Fig. 1. Robots i and j associated with vertices v i and v j , respectively, are said to be neighbors and can communicate if {v i , v j } ∈ E. Note that the proximity graph G is time-varying as a robot's neighbors vary when they move around.
The objective of the cooperative control is to find a decentralized control protocol for each robot such that, starting from any initial positions that there's at least one robot within the neighborhood of each robot (i.e., the initial proximity graph G is connected), the group of robots achieves triangulation formations with a prescribed inter-robot distance, d * , for all pairs of robots {v
To address the formulated multi-robot coordination problem, we propose a learning-based method to find a decentralized and scalable control policy that can be deployed on each robot. A GNN in conjunction with a CNN will be used as the parameterized representation of the control policy. The neural network policy is decentralized in the sense that only local information obtained by each robot is used to compute a control action. We show in simulation experiments that, owing to the scalability of the GNN representation, the learned control policy is scalable in that once trained with a given number of robots, the policy is applicable to different sizes of robot team with the team size remaining unchanged during operation. In the next section, we introduce the architecture and training of the neural network control policy.
The overview of the proposed learning-based multi-robot cooperative control is shown in Fig.
To compute a control action u i , the policy (3) uses each robot's own observation o i and the local information aggregated from current neighboring robots determined by the proximity graph G that the GNN has access to. Θ is the tensor of parameter of the DNN which is tuned during policy training.
During online control, the DNN policy computes robot control end-to-end through a feed-forward pass in a More details of the computation of GNN are presented in Section 3.2.
We train the policy (3) via learning from demonstrations (LfD), and a model-based controller is used as an expert controller to provide demonstration data. The data set is composed of pairs of robot observation o i and expert control action u * i associated with that observation. The policy training then amounts to finding the optimal parameters Θ that minimize the following loss function (for a single data sample):
The loss function measures the difference between the neural network controller's output given by π(o i ; G, Θ) and the expert controller's output u * i computed in the same system state from which the observation o i is obtained. Minimizing the loss function encourages the policy to imitate the control strategies of the model-based decentralized controller.
The feature vector x i ∈ R F extracted by the CNN on each robot i will be communicated to its neighbors by one-hop communication via the GNN. The GNN architecture adopted in this paper is the aggregation GNN (Gama et al., 2018). Each layer of the GNN performs a graph convolution that aggregates information from neighboring robots. The information aggregation with k-hop communication in the robot network at time step t creates a signal:
where
is the collection of feature vectors of all robots and S(t) ∈ R N ×N is the Graph Shift Operator (GSO) (Gama et al., 2018). The GSO is defined as a local linear operation applied to graph signals (e.g., the feature vector x i (t)) (Gama et al., 2018). Specifically, the f -th element of the feature vector for robot i after applying the GSO with one-hop (i.e., k = 1) communication is given by:
The GSO is associated with the graph structure, and in our problem it is defined as the adjacency matrix, i.e., [S] ij = 1 if robot i and j are neighbors, otherwise [S] ij = 0. k+1) , is a local signal representing the information vector aggregated on the i-th robot. The local signal z i is then convolved with a bank of F G filters, denoted by h ∈ R F (k+1)×G , to produce an output feature vector:
point-wise nonlinear activation function. The elements of h represent the learnable filter weights which are shared by all robots. The local feature vector, y i , is fed into the MLP and FC layers of each robot's local policy to compute an robot control command. More details of the aggregation GNN used in this paper can be found in Gama et al. (2018). Note that we specifically use one-hop communication (i.e., k = 1)
and select the the number of GNN layers to be one (i.e., the graph convolution operation σ gnn (•) is only performed once per time step) to reduce the communication load at each time step.
It is worth mentioning that our proposed policy model inherits the scalability property of the GNN. The scalability of GNNs stems from their permutation equivariance property and stability to changes in the topology (Gama et al., 2020). These properties allow GNNs to generalize the signal processing protocol learned at local nodes to every other node with similar topological neighborhood.
The model-based controller (Mesbahi and Egerstedt, 2010) for multi-robot triangulation formation problem was employed as the expert controller to provide training data. The expert controller achieves triangulation formations by minimizing the potential function associated with robots i and j, i.e.,
The potential function takes on its minimum at the prescribed inter-robot distance, d * . Assuming singleintegrator dynamics of the robots, i.e., ṗi = v i , the control law is given by
where robot j belongs to the neighbors of robot i, N i , defined by the Gabriel graph and K c is the control gain. When the inter-robot distance is greater than d * , the controller exerts attractive force through the positive weight
When the inter-robot distance is smaller than d * , the controller repels the robots away from each other as the weight becomes negative. At convergence, the neighboring robots form triangulations with the distance d * .
The control input, v i , computed by the expert controller for the single-integrator model is converted to the motor control of the differential-drive robot model, u i , using coordinate transformation method (Chen et al., 2019). The transformation is given by
where l is defined in (2) and c = l/2. Then the differential-drive robot (1) can be controlled by the expert controller after transformation.
The DNN policy was trained via learning from demonstration, and a model-based controller was used to provide expert demonstration data. In order to obtain a model sufficiently generalizable to unseen states at test time, we used a Data Aggregation (DAgger) training framework (Ross et al., 2011). The idea behind this is that an empty data set is gradually "aggregated" by data samples with states visited by a learning policy and actions given by the expert. To this end, we picked the learning policy with a probability (1 -β)
to execute a control action at each time step of collecting data samples during training. The probability β was initialized to 1 and decayed by a factor of 0.9 after every 50 episodes. for n = 1 to K do Update policy parameters Θ by mini-batch gradient descent with loss (4) 18:
end for 19:
Update β ← 0.9β if mod(e, 50) = 0 20: end for 21: return learned policy π(o i ; G, Θ)
At test time i.e., online formation control, a local copy of the learned policy π(o i ; G, Θ) was deployed on each robot as a decentralized controller. At each time step, the local policy received an occupancy map and a control action was calculated in a feed-forward pass. One-hop communication was performed between neighboring robots i and j, for which {v i , v j } ∈ E, to aggregate information in a decentralized way. Note that the communication graph is defined in Section 2 as a Gabriel graph and shown in Fig. 1 end for 8:
Execute the control action u i , ∀i ∈ {1, ..., N } to advance the environment 9: end for
The robot control simulation was conducted in the robot simulator, CoppeliaSim (from the creators of V-REP). We choose a team of P3-DX mobile robots, each of which has a Velodyne VLP 16 LiDAR sensor used to obtain LiDAR data and then converted to occupancy maps. The LiDAR sensors were set to a sensing range of 10 meters. The size of the occupancy map created from the sensory reading was 100 pixels ×100 pixels, making the granularity of the occupancy maps 0.1 meters/pixel. The robot simulator was controlled via various Python scripts, as the simulator API can be accessed via local data communication to and from the client Python program.
The computer used to simulate the results has an Intel i7 12900K, 12 core CPU that ran at 3.6 GHz.
The GPU used for rendering and neural network training and testing was an NVIDIA Titan Xp GPU. The PyTorch framework handled the GNN implementation as well as computations for training and testing the neural network.
The implementation details of the neural network architecture shown in Fig. 2 are given in Table 1. The CNN layers were composed of multiple convolutional blocks. The input size of the first convolutional block was set to (1, 100, 100) to fit the size of the occupancy map. The extracted features from the input by the CNN were flattened into a vector of size (1, 18432), which was further compressed by the compression block into a feature vector whose size was (1, 128). That is, the dimension F of x i was set to 128. The compressed feature vector was fed to the GNN block and communicated to neighboring robots. The GNN consisted of 1 graph convolution layer that produced a new feature vector of the same size with the input.
That is, the dimension G of y i was set to 128. Muliple MLP blocks took as input the feature vector and output the robot control action whose dimension was (1, 2).
The desired triangulation formation was set as d * = 2 m. We set k = 1 in the k-hop communication.
The initial conditions of robot positions were randomly generated in a circle of radius 5m, and the initial orientation of each robot was randomly chosen from [0, 2π]. The distance l between the robot's left and right wheels is 0.331 m.
We trained the DNN on a team of five robots. To evaluate the performance of the trained model, we tested it on different numbers of robots ranging from N = 4 to N = 9. We define the formation error between neighboring robots i and j at time t as:
The group formation error at any time t is defined as:
During training with N = 5, the data collection period of each training episode (i.e., lines 6-14 in Algorithm 1) ran for at most 200 s, and a data point was collected every 0.05 s. We terminated the simulation if the temporal average of E g (t)/d * over the most recent 20 s was smaller than 5%. Note that when we chose the speed control gain K c in the expert control (7), there was a tradeoff between the converging speed and the steady-state error. A large K c makes the system converges to the triangulation formation faster, but may cause the system to oscillate around the equilibrium. We chose an adaptive control gain K c in (7) to be 1 initially, and then after E g (t)/d * < 0.05, K c is decreased to slow down the robots as they are close to each other.
During testing, we consider the multi-robot system converged if the group formation error (i.e., the temporal average of the group formation error E g (t)/d * over the most recent 20 s) is smaller than 5% or 10%. We define three performance metrics as follows:
1. Success rate: Rate = n success /n, is the proportion of successful cases over total number of tested cases n. A simulation run is considered successful if it converges before the end of the simulation. We present success rate with 5% and 10% tolerance in Table 2.
2. Converge time: T converge is the time when a simulation run converges. That is, the first time that the temporal average of the group formation error over the most recent 20 s reaches the 5% threshold and then keeps decreasing.
3. Group formation error defined in percentage: E g /d * , where E g is defined as the temporal average of E g (t) over the last 20 s prior to the end of the simulation.
We trained the DNN using a five-robot team by running Algorithm 1. The data collection period of each training episode (i.e., lines 6-14) ran for at most 200 s, where a data point was collected every 0.05 s. The probability value β for picking between the neural network controller and the expert controller at every time step started at β = 1 in episode e = 1, and was updated every episode with the formula for episode e
as β e = 0.9 ⌊ e 50 ⌋ where ⌊•⌋ represents the floor operator. Thereby, β decayed by a factor of 0.9 every 50 training episodes. The loss function used was a mean squared error loss between the expert control that was stored and the control that was returned by the learned model. During training, the RMSprop optimizer (Mustapha et al., 2020) was used. The learning rate was set to 0.0001 and the size of mini-batch, B, used to calculated gradient was set to 16. After training for 200 episodes, the weights were saved for testing.
After training the neural network model using a five-robot team, we tested our end-to-end decentralized formation control for robot teams of varying sizes by running Algorithm 2. Random initial conditions were used for robot start positions. We demonstrate the empirical and statistical results below. To evaluate scalability, we ran testing experiments with 100 different robot initial conditions for each of the robot-team sizes from 4 to 9. The success rate for different robot-team sizes are shown in Table 2.
We can see that the success rate achieves 100% for any team size with the 10% tolerance (i.e., the group formation error E g /d * is smaller than 10% as defined in Section 4.3). With the 5% tolerance threshold, the success rate decreases as the number of the robots increases. This is due to the fact that when robots get closer to the desired formation, small motion uncertainties cause oscillations of trajectories, and the oscillations persist more when the number of robots increases. This phenomenon can be mitigated by reducing the speed control gain K c further after the robots reach around the desired formation. However, tuning this control parameter is tedious and is by trial and error. The success rate reported in this table were obtained using one set of K c . Thus, we can see that our method possesses good scalability, that is, while trained with a 5-robot team, the DNN policy can be applied to different sizes of robot team. To further evaluate performance, we tested 100 initial conditions for each of the multi-robot teams with sizes from 4 to 9. We show in Fig. 5(a) the box plot of the group formation error E g as defined in Section 4.3. We can see that the median formation errors are between 2% to 6% for robot team sizes from 4 to 9. To further compare the performance between the expert control and our trained DNN models, we show the box plot of 100 initial conditions for the 5-robot case in Fig. 6. We can see that the expert control achieved 1.76% in median formation error and 12.9 s in median convergence time, while our DNN model achieved 3.12% and 18.2 s, respectively. We can see that the expert policy outperforms the end-to-end policy slightly. This is expected given that the expert policy, as defined in ( 7) and ( 8), uses the global position of the robots, which is assumed to be observable perfectly. The end-to-end policy, on the other hand, uses LiDAR observations as input which is noisy. It should be noted that the goal of the proposed method was not to outperform the expert controller given ideal state measurements. The main advantages of our method over the expert controller are that 1) the end-to-end computational model by our method mitigates accumulation of error and latency in traditional pipeline of computational modules used by the expert control method; 2) our method does not need a localization system to obtain global robot positions, reducing overall system complexity.
The triangulation formation control we designed can be extended to other formation shapes, such as line formation and circle formation. For such cases, we used additional landmarks (i.e., stationary robots positioned at pre-selected reference positions for other robots to achieve formation objectives) and modified the expert controller to achieve the desired formations.
Line formation: The objective of the line formation is for the robots to position themselves at an equal distance from one another in a line between two landmarks . We simulated a 7-robot team with 2 stationary robots serving as landmarks that were 14 meters apart at each end of the desired line. The other 5 robots were controlled by the same expert controller ( 7) and ( 8) that we used for the triangulation formation. We ran the same training algorithm (i.e., Algorithm 1) with the same hyperparameters as before. Fig. 7(a)
shows the testing result that the robots achieved the desired line formation.
Circle formation: The objective of the circle formation is for M robots to position themselves into an M -sided regular polygonal formation with a landmark at the center. We simulated using M = 6 robots with one additional robot stayed stationary at the desired center position. We modified the expert controller (7) to the following:
where d * = 2 is the radius of the circle, p l = (0, 0) is the position of the center robot, and the control gains were set to K l = 10, K c = 1. We ran the same training algorithm (i.e., Algorithm 1) with the modified expert control above with the same hyperparameters as before. Fig. 7(b) shows the testing result that 6 robots achieved the desired circle formation.
Comparison with other works: To empirically compare our method with other learning based method on formation control, we used the publicly available implementation of the work (Agarwal et al., 2020) to evaluate performances of both line formation and circle formation for 100 trials. In the case of line formation, the mean of the group formation error, E g /d * (as defined in Section 4.3), obtained in Agarwal et al. (2020) was 7.4% with a standard deviation (SD) 2.9%; and using our method, the mean was 1.8%
with SD 1.1%. In the case of circle formation, the formation error obtained in Agarwal et al. ( 2020) was 4.2% with SD 1.2%, and ours was 3.4% with SD 1.4%. Note that our simulation was implemented with realistic robot models in a robot simulator, while Agarwal et al. ( 2020) used a point mass robot model.
Thus our method achieves comparable or better formation error with more complicated robot models.
To further compare our proposed method with recent work on learning-based multi-robot control, we summarize in Table 3 the main differences. Existing methods can be categorized into reinforcement depending on the training paradigm. The RL method does not require an expert policy, but its trial-and-error nature could make the training intractable for multi-robot systems. The intractability issue exacerbates when a realistic environment is considered, where the dimensionalities of the robot state and observation spaces increase dramatically. As shown in the table, the RL-based methods (Li et al., 2022;Yan et al., 2022;Blumenkamp et al., 2022) were only validated for up to 5 robots when a realistic robot model was considered. It's noteworthy to mention that Li et al. (2022) incorporated LfD into RL to mitigate the training intractability issue. Agarwal et al. (2020) used up to 10 robots for validation, however, the robot model was simplified as point mass. In contrast, our method employs a LfD paradigm which exploits expert demonstrations to guide the control policy search, thus considerably reduces the policy search space. Our
Frontiers