Adaptation to Team Composition Changes for Heterogeneous
Multi-Robot Sensor Coverage

We address the problem of a heterogeneous multi-robot team tasked with covering an environment where multiple event types occur. We define $N$ robot team members, each located at a position denoted as $\mathbf{p}_{i}$ for the $i$-th robot. Each robot has a set of sensing capabilities denoted by a vector $\mathbf{c}_{i}\in\mathbb{R}^{E}$, where $E$ is the number of possible event types and $c_{ij}=1$ if the $i$-th robot has the $j$-th sensing capability, and $0$ otherwise. We additionally define events occurring in the environment, modelling each event with one or more density functions centered on one or more positions (e.g., in a disaster scenario, smoke may be spreading from a single fire or from several). Events can be any of $E$ different types, corresponding to the set of available sensing capabilities.

Each robot estimates the density functions corresponding to the events based on its own observations of them, where $\phi_{i,j}(\cdot)$ denotes the $i$-th robot’s estimation of the $j$-th event type and returns a scalar value for a given position. At each time step, each robot incorporates sensor observations at its position based on its heterogeneous capabilities and updates the corresponding $\phi(\cdot)$ functions. As a robot moves towards a source of an event, the value returned by the associated $\phi(\cdot)$ rises; similarly, if a robot were to move away from a source of an event the value would fall. If a robot does not possess the necessary sensing capability (i.e., $c_{ij}=0$) then $\phi_{i,j}=0$ for all positions.

To quantify the value of each of a robot’s heterogeneous sensing capabilities, we define the utility associated with moving towards an event type, and thus increasing the sensing quality with respect to it. We introduce $\mathbf{S}=[s_{ij}]\in\mathbb{R}^{N\times E}$ as the utility associated with sensing quality, where $s_{ij}$ describes the value of the $i$-th team member moving in the direction of the $j$-th event type, given its current estimate of that event. This utility is calculated using the gradient of $\phi_{i,j}$ with respect to the robot’s current position $\mathbf{p}_{i}$. We denote the movement implied by this gradient as $\mathbf{p}_{i\to j}$, which is a movement in the direction of the $j$-th event, based on the $i$-th robot’s estimate of that event. Formally, the utility is based on the value returned by $\phi_{i,j}$ if this movement is taken:

We note that just as the utility $s_{ij}=0$ if the $i$-th robot cannot sense the $j$-th event type, the movement $\mathbf{p}_{i\to j}$ is also equal to the zero vector.

Given the described utility $\mathbf{S}$, the objective of our problem formulation is to maximize the overall sensing utility based on each robot’s current estimation of the events occurring in the environment. Each robot, given the utility of its various capabilities, must find an optimal balance among them. We apply this balance to the possible actions for each robot, generating movements that allow them to maximize their individual sensing quality based on their available capabilities.

We introduce an optimization-based formulation to identify an optimal balance of the competing utilities of the various sensing capabilities. First, we introduce the base objective function, where we maximize the overall utility provided by $\mathbf{S}$:

where $\odot$ denotes element-wise matrix multiplication and $\|\cdot\|_{1}$ denotes the element-wise $\ell_{1}$-norm of a matrix. We introduce $\mathbf{W}\in\mathbb{R}^{N\times E}$, which weights the sensing utilities, with $w_{ij}$ specifically representing the weight that the $i$-th robot assigns to sensing the $j$-th event type.

To control the formation of this weight matrix, we introduce the following constraints:

where $\mathbf{1}_{N}$ is a vector of $1$s of length $N$. We introduce these constraints to ensure that all weights are positive and so that the weights assigned to each individual robot in $\mathbf{W}$ sum to $1$ (i.e., no weight for a sensing capability can grow unreasonably large).

Next, we introduce a regularization term to encourage the assignment of at least one robot to each event type in the environment. To do this, we introduce the $\ell_{2}$-norm on each column of $\mathbf{W}$ and define the event norm:

Because of the constraints introduced above, the values in $\mathbf{W}$ are bounded to be between 0 and 1, and each row sums to 1. Maximizing this norm encourages values to form in each column of $\mathbf{W}$, meaning that each event receives weights from a robot. Otherwise, multiple robots could assign the maximum weight of 1 to a single event, leaving others unattended.

We also introduce a regularization term to enforce temporal consistency in the weight matrix. We note that if a robot is moving in the direction of an event in order to improve its sensing quality, abruptly switching directions at the next time step to move towards an alternative event is not ideal; changes should be gradual so as to not lose progress made towards improved sensing quality. To enforce this, we introduce specifying $\mathbf{W}$ as $\mathbf{W}_{t}$, indicating the weight matrix at time step $t$, and add a penalty term based on the difference between the value of $\mathbf{W}_{t}$ with the value at the previous time step, $\mathbf{W}_{t-1}$:

where $\|\cdot\|_{F}^{2}$ denotes the squared Frobenius norm. We initialize $\mathbf{W}_{0}$ to give equal weights to all available sensing modalities, i.e. if the $i$-th robot is capable of sensing $x$ of the $E$ possible sensing modalities, then each entry $w_{ij}=\frac{1}{x}$.

Our final objective function combines these introduced terms into a unified regularized optimization problem that identifies an optimal balance between the competing utilities of the available sensing capabilities:

where $\gamma_{1}$ and $\gamma_{2}$ are hyperparameters controlling the importance of the two introduced regularization terms.

Earlier, we introduced $\mathbf{p}_{i\to j}$, or the movement of the $i$-th robot in the direction of the $j$-th event. The overall movement $\dot{\mathbf{p}}_{i}$ for the $i$-th robot is based on a combination of these movements, weighted by the weight matrix $\mathbf{W}_{t}=[w_{ij}]$ computed for time step $t$ in the objective function:

This overall movement update $\dot{\mathbf{p}}_{i}$ is scaled to unit length and added to the previous position $\mathbf{p}_{i}$ to arrive at the new position:

Because of the non-smooth terms and equality constraints, Eq. (6) is hard to solve. We propose an iterative solution based on the Augmented Lagrangian Multiplier (ALM) method, similar to [42], in which we can transform constraints into penalty terms in the objective formulation.

We consider problems of the form

Constrained optimization problems in this form can be solved by the general ALM method described in Algorithm 1. The equality constraint of $h(\mathbf{X})=0$ is transformed into the penalty term added to $f(\mathbf{X})$ in Line 3. This line and the updates to $\mu$ and $\Lambda$ are repeated until the value of $\mathbf{X}$ converges.

Following this general form, we can rewrite our final objective function in Eq. (6) and move the constraint of $\mathbf{W}_{t}\mathbf{1}_{E}=\mathbf{1}_{N}$ into the objective function as a penalty term. At the same time, we rewrite our objective as a minimization problem as opposed to maximization:

where $\mu$ and $\lambda$ are introduced as multiplier variables.

We also note that $\|\mathbf{W}_{t}\odot\mathbf{S}\|_{1}$, the element-wise $\ell_{1}$-norm of the Hadamard product, or element-wise matrix multiplication, can be rewritten as the Frobenius inner product, which is equal to the trace of the matrix product. For the first term in our objective function, this means that

This makes our actual objective function

To solve this rewritten objective function, we take the derivative with respect to $\mathbf{W}_{t}$ and set it equal to 0:

Here, $\mathbf{D}$ is a diagonal matrix such that

After rearranging Eq. (13), we see that the update to $\mathbf{W}_{t}$ at each step is:

Finally, to ensure the $\mathbf{W}_{t}\geq 0$ constraint is incorporated, we threshold the values in $\mathbf{W}_{t}$:

After updating $\mathbf{W}_{t}$, we also update $\mu$ and $\lambda$:

where $\rho$ is a value chosen such that $1<\rho<2$. These steps are repeated until the value of $\mathbf{W}_{t}$ converges. This process is formally defined in Algorithm 2.

Computational Complexity. In Algorithm 2, Lines 3, 5, 6, and 7 are trivial and can be computed in linear time. The computational complexity of our proposed solution is determined solely by Line 4, which computes both a matrix inverse and a matrix multiplication. Respectively, these have complexities of $\mathcal{O}(E^{3})$ and $\mathcal{O}(NE^{2})$. Typically, $N$ will be much larger than $E$ (i.e., a scenario where the number of possible event types exceeds the number of available robots is not one that will be able to be comprehensively sensed, and so the number of robots will need to increase). When this is the case, the overall complexity of each iteration of our proposed solution algorithm is $\mathcal{O}(NE^{2})$.

Convergence. Under the condition that $0<\mu^{k}<\mu^{k+1}$, the general ALM approach described in Algorithm 1 is proven to converge to an optimal value of $\mathbf{X}$ [43]. As we initialize $\mu^{0}>0$, then $0<\mu^{k}$ holds at $k=1$. We also initialize the parameter $\rho$ such that $1<\rho<2$, and this parameter controls the only update to $\mu$ in Line 6. Thus, $\mu^{k+1}$ cannot be less than $\mu^{k}$, as this would require that $\rho<1$, and so $\mu^{k}<\mu^{k+1}$ holds at every step.

In order to comprehensively evaluate our adaptive multi-robot sensor coverage approach, we performed both extensive simulations in a high-fidelity simulator to integrate real-world control considerations. This simulator also required our approach to integrate with the Robot Operating System (ROS), as would be necessary on physical robots.

We evaluate the effects on various combinations of multi-robot team sizes ($N=\{5,10\}$) and numbers of event types ($E=\{2,3,4\}$). Evaluation is conducted with each event type being randomly generated at two positions. Members of a multi-robot team are also initialized at randomly generated positions near a chosen start area in this environment, with only a subset of $E$ possible sensors available to each robot. We conduct each simulation until $t=75$. In order to demonstrate the adaptive abilities of our approach, we simulate various numbers of robot failures during the simulation.

In all evaluations, we considered the metric of sensing quality, or the improvement of sensing performance over the base deployment of the multi-robot system. This metric relates the sensing quality at a specific point to the initial sensing quality when robots are randomly positioned in an environment. That is, if a system begins with robots deployed within an environment and they each proceed intelligently based on their sensors, then the overall sensing quality would improve. Specifically, we look at the improvement of sensing quality at the end of the simulation.

As our approach is not only adaptive to the distribution of sensors but the availability of sensors as a dynamic system proceeds (i.e., in the real world, robots can fail or lose sensing capabilities due to environmental factors), we consider a number of alternate approaches in order to demonstrate the effectiveness of our approach. We compare to three alternate approaches in order to evaluate our proposed method for multi-robot sensor coverage:

1. 1.

   Baseline: This approach sets $\gamma_{1}=0$ and $\gamma_{2}=0$, and so continues to find a weight matrix $\mathbf{W}$ that maximizes the available utility but does not utilize regularization to influence the development of $\mathbf{W}$. This approach still attempts to adapt each robot’s weighting of its capabilities in order to provide a complete view of the environment.

2. 2.

   Equally Weighted: This approach defines an equally weighted $\mathbf{W}$, where each robot assigns identical values to each of its available sensing capabilities (i.e., if a robot has two sensing capabilities, it assigns a weight of $0.5$ to each of them). This approach does not adapt to the availability of sensors or the failure of robots during the sensor coverage task.

3. 3.

   Single Capability: This approach randomly selects an available sensing capability for each robot and only allows the robot to use that sensor (i.e., if a robot has an RGB camera and a depth camera, this approach limits the robot to only one and ignores the other). Similar to the Equally Weighted approach, this approach does not adapt to changes in the system as the robots operate.

We present extensive quantitative results in Table I. For each combination of $N=\{5,10\}$ and $E=\{2,3,4\}$, we conduct simulations with $0,1,2$, and $3$ robot failures. Each combination of parameters and failures is simulated 100 times. We report the improvement in sensing quality at the end of the simulation and at its highest point. This is reported as a multiple of the initial sensing quality, e.g. if the initial sensing quality is $0.50$ and the sensing quality at the end of the simulation is $5.00$, we report an improvement of $10.00$.

We observe that our full approach consistently provides the largest sensing quality improvement, across nearly every combination of $N$, $E$, and number of robot failures. This demonstrates the effectiveness of our approach to identify an optimal weighting of available sensing capabilities, assigning weights in the context of the capabilities available to the overall team. Additionally, we see that as the number of robot failures increases, our approach widens its performance gap over the compared approaches, indicating that its ability to adapt to changes in the multi-robot team best enables it to overcome robot failure and continue to provide effective sensing performance. In some cases, our approach provides multiple times as much sensing improvement as the compared approaches. For example, for $N=10$, $E=3$, and three robot failures, our approach is able to increase sensing quality 7.87 times the initial value, while the Equally Weighted approach only doubles it. This shows the main strength of our approach, in that it is able to adapt to changes in team composition (i.e., failure) and continue to optimally balance the remaining available sensing capabilities.

In a few combinations, our baseline approach with $\gamma_{1}=0$ and $\gamma_{2}=0$ slightly edges out our the full approach, and when it does not it still consistently performs the second best or very near to it. This shows that even without our introduced regularization terms that distribute weights among event types and maintain temporal consistency, our approach’s ability to identify an optimal balance between sensing capabilities is much more effective than relying on a either a single capability or an equal weighting of capabilities.

Figure 2 shows qualitative results from example simulation of multi-robot sensor coverage in an urban environment. The initial state is seen in Figure 2(a), with five Husky ground robots. Three events are simulated, located down each road entering the three-way intersection. Figure 2(b) shows the ground robots deploying towards the simulated events. Two robots are moving towards the left road, one moving up the road entering the top of the frame, and the remaining two towards the road on the right. Figure 2(c) shows the simulated failure, with the Husky robot marked with the large red arrow failing. As this was the only robot moving towards the event at the top of the frame, existing approaches that cannot adapt would lose observations of this event. In Figure 2(d) we see that our approach is able to adapt to this failure. One of the robots that had been moving left has shifted its weighting of its sensing capabilities and is now moving towards the top of the frame to provide observations of that event. Approaches that prioritize only a single sensing modality or that do not adjust the weighting of sensing modalities would not be able to adapt to this failure, leaving the event type completely unobserved.