Centralization vs. decentralization in multi-robot coverage: Ground robots under UAV supervision

Multi-robot coverage targets the systematic, uniform observation of an environment. It is part of environment monitoring, and any other application in which more uniform observation would improve performance. For instance, in adaptive sensor networks, more efficient coverage in the exploration phase could improve the positions chosen by mobile sensors (Luo and Sycara, 2018; Siligardi et al., 2019; Santos et al., 2019). In robot swarms and multi-robot systems, more efficient observation of the environment could improve performance during, e.g., task allocation (Jamshidpey and Afsharchi, 2015), collective decision making (Valentini et al., 2015; Strobel et al., 2018), collective perception (Schmickl et al., 2006), search and rescue (Baxter et al., 2007), or foraging (Lima and Oliveira, 2017). In short, developing better solutions to coverage could improve performance in many other tasks.

We compare the following four types of coverage control, from most decentralized to most centralized (see Fig. 3).

1. 1.

   Decentralized. There are no UAV supervisors. The ground robots are fully independent; there is no explicit communication and each robot controls itself. The robots can locally detect objects in their environment. The motion control strategy is basic diffusion with obstacle avoidance.

2. 2.

   Hybrid formation control using mergeable nervous systems. UAVs are limited to local onboard sensing, through which they can observe the positions and orientations of ground robots and of environment boundaries, within a certain range. UAVs have a limited communication range and send motion control instructions to ground robots using a self-organized ad-hoc communication network (for details, see the mergeable nervous systems (MNS) approach described below). Motion control is based on a formation shape designed for sweeping.

3. 3.

   Centralized formation control. The single UAV has unlimited access to all ground robots’ positions and orientations and can sense the environment boundaries. The UAV has an unlimited communication range and directly sends motion control instructions to all ground robots over a predetermined star-graph communication network. Motion control is based on the same formation shape as in the hybrid formation approach.

4. 4.

   Predetermined control based on a priori knowledge. The UAV calculates instructions for the ground robots before the task begins, based on full a priori knowledge of the environment and the robots. The UAV has the same unlimited communication range and predetermined network topology as in the centralized formation approach. For motion control, the UAV decomposes the environment into zones and calculates motion trajectories offline, and then gives each ground robot its predetermined motion trajectory to sweep its predetermined zone.

In all approaches, the ground robots execute reactive obstacle avoidance using onboard sensing. The details of ground robot and UAV control for the four approaches are given below.

The experiments are conducted in the ARGoS simulator (Pinciroli et al., 2012), with robot models implemented using a plugin for prototyping new robots (Allwright et al., 2018a, b). All four approaches complete the coverage task with nine ground robots. In addition, the predetermined control and centralized formation control approaches each have one UAV supervisor, whereas the MNS hybrid formation control approach has three UAV supervisors, one of which is the MNS ‘brain’ (see Fig. 3). The simulated ground robot is based on the e-puck ground robot. It uses differential wheeled drive, with an average speed of $6.8$ cm/sec, and is equipped with a ring of 12 short-range proximity sensors. The ground robots can detect obstacles, other ground robots, and the boundaries of the environment at a distance of 5 cm. The simulated UAV is a quadrotor restricted to a maximum speed of $7.4$ cm/sec (such that the ground robots are able to follow the UAVs at their avergae speed), and is equipped with a downward-facing camera. Obstacles cannot be detected by the UAVs, only by the ground robots. Both simulated ground robots and UAVs are represented by simple $2.5$ cm radius cylinders.

Fiducial markers encoding unique IDs sit atop the ground robots. The UAVs detect these markers, tracking the relative positions and orientations of the ground robots in order to give them motion instructions. UAVs can establish a communication link with ground robots that lie within their field of view. In centralized formation control and predetermined control, the UAV can view the full arena and communicate with all ground robots. In MNS hybrid formation control, the UAVs fly at a constant altitude and each UAV can view ground robots in an approx. $1.5\times 1.75$ m² rectangular ground area (for details, see Zhu et al., 2020). Three UAVs are required in order to keep all ground robots in their collective view when in a line formation. In the MNS, two UAVs can establish a communication link when they can see the same ground robot (for details, see Zhu et al., 2020).

At the start of each experiment, the $4\times 4\times 2$ cm³ obstacles are distributed randomly throughout the $4$ m² arena, with a $15$ cm buffer to the outer boundary and a $15$ cm buffer between separated obstacles. The buffers ensure that it is always possible for the ground robots to sweep the environment without becoming stuck. Also at the start, the robots are randomly distributed in a $1.0\times 1.25$ m² rectangular area against the perimeter of the arena.

For the MNS hybrid formation, centralized formation, and predetermined control approaches, we define a round as one complete sweep of the environment. These experiments are terminated at the completion of the round. A round takes the same amount of time in the hybrid and centralized formation approaches, because the reactive controller that the UAVs use for perimeter following is deterministic. The decentralized approach does not perform a comparable sweep, therefore we define its round end to be at the same time step as the round ends of the hybrid and centralized approaches, to enable direct comparisons between the approaches. In the decentralized approach experiments, we continue to collect data after the round end, terminating the experiments at time step 11000.

In high-performing and efficient multi-robot coverage, robots cover a high percentage of the environment with a low rate of repeated coverage. We assess the performance of the four approaches in terms of coverage completeness (i.e., the percentage of grid cells visited) and coverage uniformity (i.e., the variability of time that robots collectively spend visiting each cell). We complete 50 runs for each control approach, in each of the three obstacle setups (100, 200, and 300 obstacles), for a total of 600 runs.

We assess the fault tolerance of coverage control in terms of the impact that robot failures have on coverage completeness. For the MNS hybrid formation control approach, we test this experimentally. For the other approaches, we conduct analysis to assess the impact of failures.

A common vulnerability in multi-robot systems is the presence of single points of failure. The fully decentralized approach is not susceptible to this problem, because it does not have a central coordinating entity. By contrast, a failure of the UAV in either the predetermined or centralized formation approaches results in a system-wide failure—neither approach can autonomously replace the failed UAV in order to recover. The MNS hybrid formation approach also has a central coordinating entity—however, if the robot fulfilling this role fails, then another robot can substitute it on the fly, because the role is defined dynamically through self-organization. Previous work has already shown the fault tolerance of MNS formation control in terms of replacing a failed robot (even the brain) and reconfiguring the formation accordingly (Zhu et al., 2020). In short, the predetermined control and centralized formation control approaches suffer from a single point of failure, while the fully decentralized and MNS hybrid formation control approaches do not.

Another key possibility is failure of robots that are responsible for the task and that cannot be replaced during runtime. Here, we test the impact on coverage completeness when failures of ground robots reduce the size of the system. In the MNS hybrid formation control approach, performance depends in part on maintaining the ad-hoc communication network. We therefore evaluate the impact of failures on both coverage completeness and connectivity. We run the fault tolerance experiments in the setup with 100 obstacles and allow the MNS hybrid formation control approach to complete one round. At time step 400, we impose failure on either one, three, five, seven, or eight out of the nine total ground robots. We complete 10 runs for each number of failing robots.

The MNS hybrid formation results show that the performance drop per robot failure is fairly consistent for 1, 3, or 5 failures—coverage completeness drops at a rate of approximately 5% per robot failure (see Fig. 8-c). When there are more than 5 failures, the performance drop per robot failure approximately doubles (see Fig. 8-c). This pattern of performance occurs because the brain UAV is capable of maintaining connectivity with its children UAVs whenever there are 5 or fewer failures (i.e., 56% or less of ground robots fail), but sometimes experiences disconnections when there are more failures (see Fig. 8-d). When there are 7 or 8 failures, the brain UAV might additionally lose contact with some of the remaining ground robots, causing the observed increase in performance drop.

We compare the MNS hybrid formation results to the other approaches using analysis (see Table 5), based on the assumption that no approach is permitted to adapt its coverage strategy during runtime (e.g., the formation approaches cannot adapt their path planning and the predetermined control approach cannot adapt its environment decomposition). As in the MNS hybrid formation approach, the fully decentralized and centralized formation approaches both include some inter-robot redundancy and interference, so we calculate the impact of failures based on the results of the MNS approach, taking into account the respective differences in coverage uniformity.²²2For each failure rate, we scale the difference in performance recorded in the MNS hybrid formation experiments for fault tolerance, according to the difference between the MNS hybrid formation approach and the compared approach in terms of average absolute deviation, based on $p$. By contrast, robots are confined to their own lanes in the predetermined control approach, so any variability in uniformity is due to self-redundant coverage. We calculate the impact of failures by simply subtracting the coverage achieved by the failed robots after time step 400. The predetermined control approach experiences the largest drop in overall coverage completeness due to robot failures (see Table 5), because the remaining robots have no opportunity to cover the zones assigned to the failed robots. In the other approaches, overall performance drops more slowly with fewer failures and more quickly with more failures. This change appears in the decentralized approach because robots have a higher chance of redundancy in a larger group, and it appears in the formation approaches because the redundancy between two robots depends on their positions in the formation. The decentralized approach experiences smaller performance drops overall, because it has more inter-robot redundancy. However, the decentralized approach never outperforms the formation approaches at the end of a round (see Table 5), because in the decentralized approach a robot has more self-redundant coverage. The centralized formation approach maintains a slight advantage over the MNS hybrid formation, up to 5 failures. With more failures, the centralized formation approach more substantially outperforms the MNS hybrid formation approach (see Table 5), because at these failure rates the MNS formation may lose contact with the remaining ground robots.

We assess scalability in terms of the number of messages exchanged between the robots, the number of inter-robot collisions, and the performance speedup achieved by the addition of one robot. We test the MNS hybrid formation approach experimentally and conduct analysis to compare to the other approaches.

We assess the performance speedup associated with adding one ground robot, regardless of the number of UAV supervisors. For the MNS hybrid formation approach, we base our analysis on the data obtained in the fault tolerance experiments (i.e., in the 100 obstacle setup) after time step 400. Similar to the fault tolerance analysis, for the fully decentralized and centralized formation approaches we calculate the performance speedup based on the results of the MNS approach, taking into account the respective differences in coverage uniformity.³³3For each number of ground robots, we scale the difference in performance recorded after time step 400 in the MNS hybrid formation experiments for fault tolerance, according to the difference between the MNS hybrid formation approach and the compared approach in terms of average absolute deviation, based on $p$. We calculate performance speedup for the predetermined control approach based on the assumption that before runtime the supervisor UAV calculates the environment decomposition according to the number of ground robots. In the predetermined control approach, the speedup in coverage completeness per time step is the same for each additional robot (see Table 5). In the predetermined control approach, the overall coverage completeness does not increase as the system scales—rather, the time required to complete a round decreases. In the other approaches, the speedup provided by one additional robot gets smaller as the system grows in size (see Table 5). Overall, the speedups in the fully decentralized approach are the lowest, because its inter-robot redundancy is highest and because its overall coverage completeness at the end of a round is lowest.

To test the scalability of communication and inter-robot collisions in the MNS hybrid formation approach, we run experiments without obstacles in the environment, with the following three heterogeneous system sizes: 1) two UAVs and four ground robots, 2) four UAVs and eight ground robots, and 3) six UAVs and twelve ground robots. We complete 10 runs per system size. For each system size, we keep the same type of communication topology and formation shape (i.e., caterpillar tree communication network, and linear formation with a slight zigzag).

In the MNS hybrid formation approach, the total number of messages exchanged is expected to scale linearly, because the robots communicate only with those they are connected to in the network. The experimental results confirm this expectation (see Fig. 8-a): at time step 5 000, the total messages passed is approximately $5\times 10^{4}$ in the 6-robot system, $13.5\times 10^{4}$ in the 12-robot system, and $22\times 10^{4}$ in the 18-robot system. Based on the field of view, the maximum number of children for one UAV is 5. We can therefore conclude that, in the MNS hybrid formation approach, the maximum number of messages passed by one robot in one time step is 10, no matter the size of the system. Just as in the fully decentralized approach, no communication bottleneck will appear in larger systems in the MNS formation approach (see Table 5). By contrast, in the centralized formation and predetermined control approaches, the maximum number of messages passed by one robot in one time step is dependent on the number of ground robots (i.e., the supervisor UAV passes 2 messages per ground robot). Therefore, the scalability limit of these approaches depends on the maximum communication load of the UAV.

In all four approaches, inter-robot collisions can occur due to obstacles in the environment. Here, we only assess interference between robots in terms of collisions caused by the control approach. In the MNS formation, it is expected that inter-robot collisions will only occur during the formation establishment phase, which is confirmed by the experiment results (see Fig. 8-b). In the fully decentralized approach, inter-robot collisions are not considered to be interference, because changes in direction help the robots cover the environment. In both the centralized formation and predetermined control approaches, robots start the experiment by moving to their target positions before proceeding with coverage. However, in these approaches, it is possible for the supervisor UAV to calculate paths for all robots that prevent collision.

We analyze the coverage completeness achieved by each method under the constraint of energy exhaustion (i.e., limited operation). Although the experiment results for coverage completeness show that the predetermined control approach is the highest performing overall, the other methods outperform it in the initial 1 000 time steps (see Fig. 5). We analyze the robot, UAV, and environment constraints under which a system would be limited to those initial performance results.

To analyze the constraint of robot distance traveled, Fig. 9 gives the average coverage completeness according to the total meters traveled by all ground robots, in one square meter of the environment. Fig. 9 shows that the decentralized method is the top performer until 0.87 m traveled per sqm, then the centralized formation method is the top performer until 1.64 m traveled per sqm, after which the predetermined control approach is the top performer. Fig. 9 also shows that the decentralized method outperforms the MNS method until 2.61 m traveled per sqm.

The point at which a robot’s energy is exhausted during a coverage task will depend on the power and efficiency of the robots, and on the size of the environment. These conditions can vary greatly, so it is relevant to better characterize performance according to energy exhaustion. To assess the limit imposed by ground robot exhaustion, we calculate the average coverage completeness depending on the maximum distance a ground robot can travel in one charge. To assess the limit imposed by typical UAV exhaustion (i.e., 30 minutes in one charge), we also calculate the average coverage completeness depending on the maximum speed of the ground robot. Because the maximum speed of the UAV will always be higher, it is not a limitation. We consider environment sizes of up to 100 000 square meters per ground robot. Such an environment is large enough to assess the performance shifts for ground robots with a maximum travel distance from 1.5 km to 100 km per robot per charge and a maximum speed from 0.1 m/s to 50 m/s (under the condition of 30 minutes of UAV flight time). These ranges are representative of ground robots available off-the-shelf (and the flight time is representative of the average UAV), as listed in the Appendix.

In general, the analysis results indicate that more centralization performs better if maximum distances or maximum speeds are higher, while more decentralization performs better if operating areas are larger (see Fig. 10). For indoor environments, even in the most limited robots available off-the-shelf (see the Appendix), the environment size in which the decentralized approach would be the best performer is somewhat large (see Table 6). For example, for e-puck2 or Thymio II robots designed for indoor research, for a group of nine ground robots, the decentralized approach would only be the top performer in environments larger than $50\times 50$ m². However, for applications such as outdoor search and rescue, the environment could easily be large enough to make the decentralized approach the top performer (see Table 6). For example, for a group of nine Boston Dynamics Spot robots, the decentralized approach will be the top performer in any environment larger than $135\times 135$ m².

In some coverage applications, battery life could be increased or autonomous recharging could be implemented. The energy efficiency of ground robots might also be significantly different from the efficiency of UAVs. To characterize the impact of energy efficiency on performance, we analyze the coverage completeness achieved by each approach under an overall energy budget, regardless of battery life. Basing our analysis on the results obtained in Sec. 4.1.1, we assign the system a total energy consumption budget of either 200 or 300 kilojoules. The budget is shared among all ground robots and UAVs used in that method (i.e., nine ground robots for all methods, three UAVs for MNS hybrid formation, one UAV for both centralized formation and predetermined control, and no UAVs for decentralized). We consider ground robots with energy consumption rates from 3 joules/s to 70 j/s, and UAVs with energy consumption rates from 6 j/s to 60 j/s. These ranges represent robots available off-the-shelf (see the Appendix).

Under a constrained energy budget, in general, more centralization tends to perform better if the ground robots are more efficient, and more decentralization tends to perform better if the ground robots are less efficient (see Fig. 11). In most of the analyzed energy consumption scenarios, the decentralized approach is the top performer if the UAV has its highest possible energy consumption rate (i.e., 60 j/s). All the approaches that have UAV supervisors perform better if the UAVs are more efficient, but the MNS hybrid formation approach benefits the most from efficient UAVs, because it has more of them. As the energy budget increases, the performance of all approaches improves (see Fig. 11). If the budget is unlimited, the performance rankings of the four approaches will always be those seen at the end of a round in Sec. 4.1.1, regardless of the energy consumption ratio between ground robots and UAVs.

It is evident that the predetermined control and centralized formation control approaches suffer from a single point of failure and a communication bottleneck when scaling. As would be expected, our analysis also suggests that the predetermined control approach suffers much more from robot failures than the other approaches (see Table 5). Perhaps less expected, our analysis suggests that the MNS hybrid and centralized formation control approaches do not suffer much more from robot failures than the decentralized approach. These analysis results should be investigated further, in experimental setups with a variety of failure types.

Many existing hybrid approaches use a dynamically elected leader to increase fault tolerance and flexibility in an otherwise centralized approach (e.g., Din et al., 2018), but these approaches still suffer from a bottleneck when scaling. It might be expected that the MNS hybrid formation control approach would suffer from a similar bottleneck. However, our experimental results indicate that communication in the MNS hybrid formation approach scales linearly (see Fig. 8), and that the communication load on the MNS brain does not increase when scaling.

In later time steps (e.g., after the first 1000 time steps in the main experiments, see Fig. 5), the relative performance rankings of the four methods remain consistent—in terms of coverage completeness, the ranking is: \nth1 predetermined, \nth2 centralized formation, \nth3 MNS hybrid formation, and \nth4 fully decentralized (see Fig. 5). However, these performance rankings are not representative of earlier time steps. Although the coverage completeness in these earlier steps is low (e.g., 10% or 40%), our experiments use a high-resolution analysis grid, where adjacent grid points are $25$ cm apart. This matches a real-world application in which, for instance, ground robots can sense a targeted condition within a $12.5$ cm radius. In scenarios where a ground robot’s sensing range is much higher, then a low coverage completeness in our experiments may be sufficient. For example, with a ground robot sensing range of $50$ cm radius, intuitively we would posit that a coverage completeness of 25% could be sufficient for a monitoring application. This should be further investigated experimentally, using different grid resolutions in a discrete environment or using different sensor ranges. Similarly, all the analysis results in Sec. 5 need to be further investigated to be confirmed as representative—for example, by running experiments in larger arenas, up to 100 000 m². Such experiments would involve implementing new behaviors in some of the approaches. For instance, in a larger environment, the formation approaches would need to use a different path planning strategy such as boustrophedon motion (Almadhoun et al., 2019; Avellar et al., 2015).

In general, our energy analysis results indicate that overall operation time is a highly relevant constraint. In large environments or with tight energy budgets, fully decentralized control may be the only feasible approach. In order to achieve high coverage completeness in real applications, our results indicate that the development of autonomous recharging is essential. Autonomous recharging will likely be easier to implement in hybrid or predetermined control approaches, because localization and positioning is more challenging in fully decentralized approaches. From among our tested approaches, the MNS hybrid formation control approach may be the most suitable for autonomous recharging, because it is already able to replace robots on the fly (Zhu et al., 2020).

Future work could also investigate the implications of monetary costs. If many robots are added, the area per robot can be kept smaller, even in larger environments. However, in outdoor environments, suitable robots are expensive and the monetary cost of adding ground robots can be very high (see the Appendix). The cost of adding UAV supervisors is low in comparison, so adding UAV supervisors may sometimes be a more effective way to increase coverage completeness, depending on task conditions.