Using Reinforcement Learning to Herd a Robotic Swarm to a Target Distribution

We present two Temporal-Difference learning algorithms [1] for generating a control policy that guides a mobile agent, referred to as a leader, to herd a swarm of autonomous follower agents to a target distribution among a small set of states. This leader-follower control approach can be used to redistribute a swarm of low-cost robots with limited capabilities and information using a single robot with sophisticated sensing, localization, computation, and planning capabilities, in scenarios where the leader lacks a model of the swarm dynamics. Such a control strategy is useful for many applications in swarm robotics, including exploration, environmental monitoring, inspection tasks, disaster response, and targeted drug delivery at the micro-nanoscale.

There has been a considerable amount of work on leader-follower multi-agent control schemes in which the leader has an attractive effect on the followers [2, 3]. Several recent works have presented models for herding robotic swarms using leaders that have a repulsive effect on the swarm [4, 5, 6]. Using such models, analytical controllers for herding a swarm have been constructed for the case when there is a single leader [5, 6] and multiple leaders [4]. The controllers designed in these works are not necessarily optimal for a given performance metric. To design optimal control policies for a herding model, the authors in [7] consider a reinforcement learning (RL) approach. While existing herding models are suitable for the objective of confining a swarm to a small region in space, many applications require a swarm to cover an area according to some target probability density. If the robots do not have spatial localization capabilities, then the controllers developed in [2, 3, 4, 5, 6, 7] cannot be applied for such coverage problems. Moreover, these models are not suitable for herding large swarms using RL-based control approaches, since such approaches would not scale well with the number of robots. This loss of scalability is due to the fact that the models describe individual agents, which may not be necessary since robot identities are not important for many swarm applications.

In this paper, we consider a mean-field or macroscopic model that describes the swarm of follower agents as a probability distribution over a graph, which represents the configuration space of each agent. Previous work has utilized similar mean-field models to design a set of control policies that is implemented on each robot in a swarm in order to drive the entire swarm to a target distribution, e.g. for problems in spatial coverage and task allocation [8]. In this prior work, all the robots must be reprogrammed with a new set of control policies if the target distribution is changed. In contrast, our approach can achieve new target swarm distributions via redesign of the control policy of a single leader agent, while the control policies of the swarm agents remain fixed. The follower agents switch stochastically out of their current location on the graph whenever the leader is at their location; in this way, the leader has a “repulsive” effect on the followers. The transition rates out of each location are common to all the followers, and are therefore independent of the agents’ identities. Using the mean-field model, herding objectives for the swarm are framed in terms of the distribution of the followers over the graph. The objective is to compute leader control policies that are functions of the agent distribution, rather than the individual agents’ states, which makes the control policies scalable with the number of agents.

We apply RL-based approaches to the mean-field model to construct leader control policies that minimize the time required for the swarm of follower agents to converge to a user-defined target distribution. The RL-based control policies are not hindered by curse-of-dimensionality issues that arise in classical optimal control approaches. Additionally, RL-based approaches can more easily accommodate the stochastic nature of the follower agent transitions on the graph. There is prior work on RL-based control approaches for mean-field models of swarms in which each agent can localize itself in space and a state-dependent control policy can be assigned to each agent directly [9, 10, 11]. However, to our knowledge, there is no existing work on RL-based approaches applied to mean-field models for herding a swarm using a leader agent. Our approach provides an RL-based framework for designing scalable strategies to control swarms of resource-constrained robots using a single leader robot, and it can be extended to other types of swarm control objectives.

An OpenAI Gym environment [12] was created in order to design, simulate, and visualize our leader-based herding control policies [13]. This open source virtual environment can be easily modified to simulate swarm controllers for different numbers of agents and graph vertices, making it a suitable environment for training leader control policies using our model-free approaches. The simulated controllers can then be implemented in physical robot experiments. Figure 1 shows the simulated environment for a scenario with $100$ follower agents, represented by the blue $\times$ symbols, that are herded by a leader, shown as a red circle, over a $2\times 2$ grid. The OpenAI environment does not store the individual positions of each follower agent within a grid cell; instead, each cell is associated with an agent count. The renderer disperses agents randomly within a cell based on the cell’s current agent count. The agent count for a grid cell is updated whenever an agent enters or leaves the cell according to the DTMC (1), and the environment is re-rendered. Recording the agent counts in each cell rather than their individual positions significantly reduces memory allocation and computational time when training the leader control policy on scenarios with large numbers of agents.

The graph $\mathcal{G}$ that models the environment in Figure 1, with each vertex of $\mathcal{G}$ corresponding to a grid cell, was defined as the $2\times 2$ graph in Figure 2. In the graph, agents transition along edges in either a horizontal or vertical direction, or they can stay at the current vertex. The action set is thus defined as:

Using the graph in Figure 2, we trained and tested a leader control policy for follower agent populations of $N=10$–$100$ at $10$-agent increments. Both the SARSA and Q-Learning paradigms were applied and trained on $5000$ episodes with $5000$ iterations each. In every episode, the initial distribution $\hat{S}_{initial}$ and target distribution $\hat{S}_{target}$ of the follower agents were defined as:

The initial leader location, $\ell_{1}$, was randomized to allow many possible permutations of states $S_{env}$ for training. During training, an episode completes once the distribution of $N$ follower agents reaches a specified terminal state. Instead of defining the terminal state as the exact target distribution $\hat{S}_{target}$, which becomes more difficult to reach as $N$ increases due to the stochastic nature of the followers’ transitions, we define this state as a distribution that is sufficiently close to $\hat{S}_{target}$. The learning rate and discount factor were set to $\alpha=0.3$ and $\gamma=0.9$, respectively. The follower agent transition rate $\beta_{e}$ was defined as the same value $\beta$ for all edges $e$ in the graph and was set to $\beta=0.025$, $0.05$, or $0.1$. We use the mean squared error (MSE) to measure the difference between the current follower distribution and $\hat{S}_{target}$. The terminal state is reached when the MSE decreases below a threshold value $\mu$. We trained our algorithms on threshold values of $\mu=0.0005$, $0.001$, $0.0025$, and $0.005$.

After training the leader control policies on each follower agent population size $N$, the policies were tested on scenarios with the same environment and value of $N$. The policy for each scenario was run $1000$ times to evaluate its performance. The policies were compared for terminal states that corresponded to the four different MSE threshold values $\mu$, and were given $1000$ iterations to converge within the prescribed MSE threshold of the target distribution (15) from the initial distribution (14).

Figure 3 compares the performance of leader control policies that were designed using each TD algorithm as a function of the tested values of $\mu$. The leader control policies were trained on $N=100$ follower agents, using the parameters $\beta=0.05$ and $D=10$ or $20$, and tested in simulations with $N=100$. The plots show that for both policies, the mean number of iterations required to converge to $\hat{S}_{target}$ decreases as the threshold $\mu$ increases for constant $D$, and at low values of $\mu$, the mean number of iterations decreases when $D$ is increased. In addition, as $\mu$ increases, the variance in the number of iterations decreases (note the log scale of the $y$-axis in the plots) or remains approximately constant, except for the $D=20$ case of SARSA.

Figure 4 compares the performance of leader control policies that were designed using each algorithm as a function of $N$, where the leader policies were tested in simulations with the same value of $N$ that they were trained on. The other parameters used for training were $\mu=0.0025$, $D=20$, and $\beta=0.025,$ $0.05$, or $0.1$. The figures show that raising $\beta$ from $0.05$ to $0.1$ does not significantly affect the mean number of iterations until convergence, while decreasing $\beta$ from $0.05$ to $0.025$ results in a higher mean number of iterations. This effect is evident for both Q-Learning and SARSA trained leader control policies for $N>50$. Both leader control policies result in similar numbers of iterations for convergence at each agent population size. Therefore, both the Q-Learning and SARSA training algorithms yield comparable performance for these scenarios.

The results in Figure 4 show that as $N$ increases above $50$ agents, the mean number of iterations until convergence decreases slightly or remains approximately constant for all $\beta$ values and for $\mu=0.0025$. Moreover, from Figure 3, we see that MSE threshold values $\mu<0.0025$ for $N=100$ result in a higher number of iterations than the $N=100$ case in Figure 4. This trend may be due to differences in the magnitude of the smallest possible change in MSE over an iteration $k$ relative to the MSE threshold $\mu$ for different values of $N$. For example, for $N=10$, a similarity in iteration counts for all four MSE thresholds $\mu$ can be attributed to the fact that the change in the MSE due to a transition of one agent, corresponding to a change in population fraction of $1/N=1/10$, is much higher than the four MSE thresholds (i.e., $(1/10)^{2}>0.005$, $0.0025$, $0.001$, and $0.0005$). Compare this to the iteration count for $N=50$, which would have a corresponding change in MSE of $(1/50)^{2}$; this quantity is much smaller than $0.005$ and $0.0025$, but not much smaller than $0.001$ and $0.0005$. The iteration counts for $N=100$ are much lower, since $(1/100)^{2}$ is much smaller than all four MSE thresholds.

Finally, Figure 5 compares the performance of leader control policies that were designed using each algorithm as a function of $N$, where the leader policies were trained with $N=10$, $100$, or $1000$ follower agents and tested in simulations with $N=10$–$100$ (at $10$-agent increments) and $N=1000$ agents. This was done to evaluate the robustness of the policies trained on the three agents populations to changes in $N$. The other parameters used for training were $\mu=0.0025$, $D=20$, and $\beta=0.025,$ $0.05$, or $0.1$. As the plots in Figure 5 show, policies trained on the smallest population, $N=10$, yield an increased mean number of iterations until convergence when applied to populations $N>10$. The reverse effect is observed, in general, for policies that are trained on higher values of $N$ than they are tested on. An exception is the case where the policies are trained on $N=100$ and $1000$ and tested on $N=10$, which produce much higher numbers of iterations than the policies that are both trained and tested on $N=10$. This is likely a result of the large variance, and hence greater uncertainty, in the time evolution of such a small agent population. The lower amount of uncertainty in the time evolution of large swarms may make it easier for leader policies that are trained on large values of $N$ to control the distribution of a given follower agent population than policies that are trained on smaller values of $N$. We thus hypothesize that training a leader agent with the mean-field model (6) instead of the DTMC model would lead to improved performance in terms of a lower training time, since the policy would only need to be trained on one value of $N$, and fewer iterations until convergence to the target distribution.

We also conducted experiments to verify that our herding approach is effective in a real-world environment with physical constraints on robot dynamics and inter-robot spacing. Two of the leader control policies that were generated in the simulated environment were tested on a swarm of small differential-drive robots in the Robotarium [14], a remotely accessible swarm robotics testbed that provides an experimental platform for users to validate swarm algorithms and controllers. Experiments are set up in the Robotarium with MATLAB or Python scripts. The robots move to target locations on the testbed surface using a position controller and avoid collisions with one another through the use of barrier certificates [15], a modification to the robots’ controllers that satisfy particular safety constraints. To implement this collision-avoidance strategy, the robots’ positions and orientations in a global coordinate frame are measured from images taken from multiple VICON motion capture cameras.

A video recording of our experiments is shown in [16]. The environment was represented as a $2\times 2$ grid, as in the simulations, and $N=$ 10 robots were used as follower agents. The leader agent, shown as the blue circle, and the boundaries of the four grid cells were projected onto the surface of the testbed using an overhead projector. As in the simulations, at each iteration $k$, the leader moves from one grid cell to another depending on the action prescribed by its control policy. Both the SARSA and Q-Learning leader control policies trained with $N=100$ follower agents, $D=10$, $\mu=0.0025$, and a $\beta=0.1$ were implemented, and [16] shows the performance of both control policies. In the video, the leader is red if it is executing the Stay action and blue if it is executing any of the other actions in the set $A$ (i.e., a movement action). The current iteration $k$ and leader action are displayed at the top of the video frames. Actions that display $\epsilon$ next to them signify a random action as specified in (12). Each control policy was able to achieve the exact target distribution (15). The SARSA method took $59$ iterations to reach this distribution, while the Q-Learning method took $23$ iterations.

We have presented two Temporal-Difference learning approaches to designing a leader-follower control policy for herding a swarm of agents as quickly as possible to a target distribution over a graph. We demonstrated the effectiveness of the leader control policy in simulations and physical robot experiments for a range of swarm sizes $N$, illustrating the scalability of the control policy with $N$, and investigated the effect of $N$ on the convergence time to the target distribution. However, these approaches do not scale well with the graph size due to the computational limitations of tabular TD approaches and, in particular, our discretization of the system state into population fraction intervals. Our implementation requires a matrix with $D^{M}\times M\times|A|$ state-action values to train the leader control policy. For our $2\times 2$ grid graph with $|A|=5$ possible leader actions and $D=20$ intervals, this is about $20^{4}\times 4\times 5$ values.

To address this issue, our future work focuses on designing leader control policies using the mean-field model rather than the DTMC model for training, as suggested at the end of Section 3. In this approach, the leader policies would be trained on follower agent population fractions that are computed from solutions of the discrete-time mean-field model (6), rather than from discrete numbers of agents that transition between locations according to a DTMC. The leader control policies can also be modified to use function approximators such as neural networks for our training algorithm, allowing for utilization of modern deep reinforcement learning techniques. Neural network function approximators provide a more practical approach than tabular methods to improve the scalability of the leader control policy with graph size, in addition to swarm size. In addition, the control policies could be implemented on a swarm robotic testbed in a decentralized manner, in which each follower robot avoids collisions with other robots based on its local sensor information.