On Combining Multi-robot Coverage and Reciprocal Collision Avoidance

Abstract

Although robotic coverage and collision avoidance are active areas of robotics research, the avoidance of collision situations between robots has often been neglected in the context of multi-robot coverage tasks. In fact, for robots of physical size, collisions are likely to happen during deployment and coverage in densely packed multi-robot configurations. For this reason, we aim to motivate by this paper the combined use of multi-robot coverage and reciprocal collision avoidance. We present a taxonomy of collision scenarios in multi-robot coverage problems. In particular, coverage tasks with built-in heterogeneity such as multiple antagonistic objectives or robot constraints are shown to benefit from the combination. Based on our taxonomy, we evaluate four representative robotic use cases in simulation by combining the specific methods of Voronoi coverage and reciprocal velocity obstacles.

1 Introduction

The primary objective of multi-robot coverage involves the deployment and/or sweeping motion of a group of mobile robots within a region or along boundaries in order to provide a service, such as monitoring or maintenance. Whenever the coverage tasks require the robots to come close, higher-priority objectives of cooperation are imposed, including the avoidance of robot-to-robot collisions. Collision situations arise first of all due to the other robots that are involved in the same task of covering the mission space. Second, collisions with other independent robots present in the mission space must be avoided. These robots—either static or dynamic—are pursuing their own objectives in a collaborative or non-collaborative fashion.

A survey of robotic coverage is given in [1]. Deployment and sweeping motion for robotic coverage of areas and boundaries (e.g., barriers) have previously also been referred to as blanket, barrier and sweep coverage [2]. A particular type of blanket coverage is Voronoi coverage [3], which arranges the robots in a final configuration that forms a so-called Centroidal Voronoi Tessellation (CVT) [4].

In the context of Voronoi coverage, robot-to-robot collision avoidance for robots of physical size (i.e., finite size instead of zero-sized point robots) has previously been considered by [5, 6]. The method in [5] restricts the robots’ positions to the collision-free subareas in the interiors of their Voronoi cells; the Voronoi coverage controller in [6] adds a collision avoidance component based on repulsive terms to the coverage control law. Both methods, however, focus on one collision scenario only, which addresses the collision avoidance among robots that all share one single objective and execute the same Voronoi coverage control law cooperatively.

The contributions of this paper are threefold. First, we describe the possible types of robot-to-robot collision scenarios in multi-robot coverage problems and propose a taxonomy (Sect. 2). Second, we present a concrete solution for integrating a reciprocal collision avoidance algorithm into a multi-robot coverage algorithm; in particular, the CVT-based Voronoi coverage controller is combined with Reciprocal Velocity Obstacles (RVO), using the Optimal Reciprocal Collision Avoidance (ORCA) formulation (Sect. 3). Besides collision-free coverage, this allows for collision avoidance between heterogeneous robots (e.g., robots with different kinematic models). Third, we evaluate four use cases for combining multi-robot coverage and reciprocal collision avoidance, which show some characteristics that are inherent to such a combination (Sect. 4). Final conclusions are provided in Sect. 5.

2 A Taxonomy of Collision Scenarios in Multi-robot Coverage

In this paper, we deal with instances of multi-robot coverage problems, i.e., problems which ask for covering a mission space with multiple robots. Each robot has its own primary objective, which may be an individual or a shared common goal with other robots. The robots that share common goals are in the following considered members of the same group or team. The primary objective of at least a subset of the robots will be the coverage of the common mission space.

In such a setting, there are many possibilities for conflicting situations, so-called collision scenarios, which need to be resolved. Some scenarios are encountered during initial robot deployment and others in a later stage of the coverage process. Some scenarios occur among robots of the same team, i.e., intragroup, and others between robots that belong to different teams, i.e., intergroup. In some collision scenarios, the robots must avoid each other while they collaborate, yet in others, the robots may compete and collisions with adversary robots must be avoided.

2.1 Categorization of Collision Scenarios

We base our categorization of collision scenarios in multi-robot coverage on the categorization of coverage behaviors by [2] and the categorization of interactions among agents by [7], where interactions are classified along the axes of “individual or shared goals”, “actions advance goals of others”, and “awareness of others”. For the multi-robot coverage tasks of our interest, we assume that the robots are aware of each other. Consequently, our taxonomy has three dimensions:

• Coverage phases during deployment and sweeping: We distinguish between the two coverage types of deployment and sweeping motion, each of which is subdivided into two coverage phases. Deployment refers to blanket and barrier coverage: a robot team deploys in the first phase and assumes a static coverage configuration. In the second phase after the initial deployment, the robots observe the mission space from their configuration. Sweeping motion refers to sweep coverage (and coverage by a moving barrier): each robot covers the mission space by a sweeping motion in the first phase. If a second phase exists, the robots move over already covered space and relocate, inspect a covered location closer, or resume the sweeping motion to achieve persistent or redundant coverage of the mission space.

• Intragroup and intergroup collision avoidance: According to [7], robots may share common goals or have individual differing goals. Robots with shared common goals form a team or group. Single robots or robots of different teams are said to be external to each other. During the completion of a task, such as coverage, the robots must avoid collisions and resolve collision situations inside their own team (intragroup) as well as between external robots and teams (intergroup). The robot teams may be homogeneous or as well consist of heterogeneous robots with different sizes, sensing and mobility capabilities (e.g., different kinematics).

• Cooperative and non-cooperative behavior: For coverage and reciprocal collision avoidance, the degree of cooperation is another important factor. Similar to [7], we measure cooperativeness by whether the actions of one robot influences the goals of other robots (both individual or shared goals) in a positive or negative way. Positive influence represents cooperative behaviors, neutral or negative influence represents non-cooperative, including competing or adversary, behaviors. Non-cooperative robots appear to each other as static or dynamic obstacles.

2.2 The Collision Scenarios in Voronoi Coverage

The multi-robot Voronoi coverage control approach serves us as a demonstration example to show the different categories suggested by our taxonomy. The basic CVT-based Voronoi coverage controller¹ is an example of the deployment coverage type. In addition, we will also consider a hybrid variant, where the second coverage phase involves, instead of observing, sweeping motions in the Voronoi cells.

Fig. 1

Coverage without (left) and with (right) reciprocal collision avoidance. Left A robot team (black robots) performs Voronoi coverage and covers a mission space $\varOmega$ by creating a CVT. The Voronoi graph is formed by the boundaries of the Voronoi cells (full black lines) and the dual Delaunay graph is visualized by the black dashed lines. The Voronoi neighborhood of one of the robots (yellow Voronoi cell) is indicated by the yellow outer circle. Right The robot team now avoids collisions among each other and with external robots (white robots); the numbers (1)–(3) and (4)–(6) refer to the different collision scenarios that occur during (i.e., first coverage phase) and after (i.e., second coverage phase) the initial deployment (see Sect. 2)

The collision scenario (1) in Fig. 1 on the right depicts the trajectory of a robot that shows intragroup collision avoidance and cooperative behavior when avoiding another team member (black robot) during the first phase of deployment. A similar situation is illustrated by collision scenario (2) in Fig. 1 but for intergroup collision avoidance between a team member that performs Voronoi coverage (black robot) and an external robot with differing goal (white robot).

Some collision scenarios include components from both intragroup and intergroup collision avoidance. Instead of single robots, a team of several robots—considered as a single entity—can as a subgroup itself be part of a larger team and thus be subject to coverage and collision avoidance. During the initial phase of deployment, the robots in the subgroup must avoid reciprocal collisions among each other locally and with other members of the team (intragroup collision avoidance, cooperative behavior), as well as with potential external robots (intergroup collision avoidance, cooperative or non-cooperative). The collision scenario (3) in Fig. 1 shows such an abstraction for a team of three robots, which forms a subgroup of the overall covering team (black robots).

In the second coverage phase of the deployment, certain operations, such as recharging, servicing, escape or evasion maneuvers, require robots of a team to occasionally leave their positions in the static coverage configuration for a short time. During these operations, the robots must avoid reciprocal collisions with team members (intragroup or intergroup collision avoidance) as well as with approaching external robots (intergroup collision avoidance). The robots which undergo such escape and return maneuvers become in some cases instances of “on-off” team members, i.e., they are recognized as external robots by some or all of the team members for a limited time period. In other words, these robots temporally convert into external robots, and apply intergroup collision avoidance, but eventually rejoin the robot team. The collision scenario (4) in Fig. 1 gives an example of a robot that leaves its Voronoi cell and comes back after having moved to the mission space boundary. On its way, it may get involved into collisions, e.g., with a former team member or an external dynamic obstacle (white robot).

The initial deployment of a robot team often goes along with a decomposition or tessellation of the mission space. This provides an additional representation of the environment and robot configuration that can be shared among the robots. With respect to Voronoi coverage, the constructed CVT includes Voronoi and Delaunay graphs, which can be used as roadmaps for robot navigation in the mission space. Single robots or groups of multiple robots may, for example, patrol the Delaunay graph or pass threats with a maximum clearance or safety distance by transitioning the Voronoi graph. On both roadmaps, there can potentially be oncoming traffic of cooperative or non-cooperative robots, which asks for reciprocal intragroup or intergroup collision avoidance. The collision scenarios (5) in Fig. 1 show a robot (black) that moves along a path (red) on the Delaunay graph to a next Voronoi cell and an external dynamic obstacle (white robot) that moves along a path (green) on the Voronoi graph amidst the deployed robots. The first robot must actively avoid collisions on its path whereas the second robot needs to be avoided by other robots.

The two coverage types can also be combined; such hybrid coverage methods involve the hierarchical coupling of deployment and sweeping motion [8]. In case of Voronoi coverage, after the robots have deployed and a CVT spans the mission space, each robot in the team covers its Voronoi cell by sweeping motions (e.g., spiraling or back-and-forth sweeping patterns) during the second coverage phase. Here, collision situations occur during sweeping. The collision scenarios (6) in Fig. 1 illustrate that the robots must either avoid reciprocal collisions at the boundaries of their Voronoi cells (intragroup collision avoidance)² or within the cells, in case several robots—possibly of different teams (this would mean intergroup collision avoidance)—sweep the same Voronoi cell for purposes of redundant coverage.

Intragroup and intergroup collision avoidance during the second coverage phase can involve cooperative or non-cooperative behavior. Whereas two robot team members would typically cooperate when facing a collision situation while driving along a sweeping path or path in a roadmap, the cooperativeness of a robot that temporally leaves its team, for example for recharging, may strongly depend on its current state, e.g., its urge due to a low remaining battery level. Moreover, external dynamic obstacles pursue their own goals by strictly acting in a non-cooperative way.

3 Combining Voronoi Coverage and RVO

We are now going to present the implementation of a concrete solution for reciprocal collision avoidance in a multi-robot coverage problem. We build on the aforementioned example of CVT-based Voronoi coverage and combine it with reciprocal collision avoidance in velocity space, using the RVO and ORCA³ methods [9–12].

Voronoi coverage, as presented in Sect. 3.1, is based on a gradient-descent control law. In a collision situation, each involved robot faces one or multiple other robots in the mission space. Independent of their cooperativeness, each robot represents a dynamic (or static for stationary robots) obstacle that needs to be avoided completely, or up to a certain degree. This introduces (dynamically changing) constraints on the robot controllers and leads to constrained (or projected) gradient descent, which makes the problem considerably more challenging. We approach this constrained optimization problem with the reciprocal collision avoidance method using RVO and ORCA in Sect. 3.2.

3.1 CVT-based Voronoi Coverage

We restate the most important formulations from Voronoi coverage control after [3]. Given n robots at positions $P= \left\{ \mathbf {p}_1, \,\ldots \, , \, \mathbf {p}_n \right\}$, which are tasked with covering the mission space $\varOmega \subset \mathbb {R}^N$, let the coverage objective function be $\mathcal {H}_{\mathcal {V}}$ and the corresponding coverage cost

$$\begin{aligned} \mathcal {H}_{\mathcal {V}}(P) = \sum _{i=1}^n h(\mathbf {p}_i, \, V_i) = \sum _{i = 1}^{n} \int _{V_i} f(d(\mathbf {q}, \, \mathbf {p}_i)) \, \rho (\mathbf {q}) \, dF(\mathbf {q})\, . \end{aligned}$$

(1)

The Voronoi tessellation over $\varOmega$ is given by the set of Voronoi cells $\mathcal {V}(P) = \left\{ V_{1}, \,\ldots \, , \, V_{n} \right\}$, where

$$\begin{aligned} V_i= \left\{ \mathbf {q}\in \varOmega \, | \, d(\mathbf {q}, \, \mathbf {p}_i) \le d(\mathbf {q}, \, \mathbf {p}_j), \, j \ne i \right\} \, , \end{aligned}$$

$\forall \, i, \, j \in \left\{ 1, \,\ldots \, , \, n \right\}$. Two robots i and j are said to be Voronoi neighbors if their Voronoi regions $V_i$ and $V_j$ are adjacent. The density function $\rho :\, \varOmega \rightarrow \mathbb {R}_{\ge 0}$ directs the robots to areas of special interest. The function to measure distance between locations $\mathbf {q}\in V_i$ and robot positions $\mathbf {p}_i$ is defined as $d:\, \varOmega ^2 \rightarrow \mathbb {R}_{\ge 0}$. The performance function $f:\, \mathbb {R}_{\ge 0}\rightarrow \mathbb {R}$, which must be strictly increasing over the image of d, measures the degradation of the coverage performance with increasing distance.

As further shown in [3–5], the objective function is minimized by solving

$$\begin{aligned} \nabla _{\mathbf {p}_i}\mathcal {H}_{\mathcal {V}}(P) = \nabla _{\mathbf {p}_i}h(\mathbf {p}_i, \, V_i)&\nonumber \\ = \int _{V_i} \nabla _{\mathbf {p}_i} f(d(\mathbf {q}, \, \mathbf {p}_i)) \; \rho (\mathbf {q}) \; dF(\mathbf {q})&= \mathbf {0} \, . \end{aligned}$$

The partial derivatives and linear proportional control laws can then be obtained for each robot,

$$\begin{aligned} \nabla _{\mathbf {p}_i}h(\mathbf {p}_i, \, V_i)&= -2 \; M_{V_i} \; (\mathbf {c}_{V_i} - \mathbf {p}_i) \, , \nonumber \\ \mathbf {v}^{\text {pref}}_{i}&= -k \; \nabla _{\mathbf {p}_i}h(\mathbf {p}_i, \, V_i) \, , \end{aligned}$$

(2)

with $M_{V_i}$ and k set to positive values. The centroids $\mathbf {c}_{V_i}$ are critical points of the objective function $\mathcal {H}_{\mathcal {V}}$. The preferred velocities $\mathbf {v}^{\text {pref}}_{i}$, which are tracked by the robots, point toward the centroids and make the robots iteratively approach the centroids; the resulting CVT at convergence leads to a local minimum of the objective function. Figure 1 on the left shows a CVT, the Voronoi graph and its dual, the Delaunay graph, as well as an example of a robot’s Voronoi neighborhood.

We will additionally make the following assumptions with respect to the Voronoi coverage control in this paper.

Assumption 1

The Voronoi tessellation is defined after [3] by a coverage objective function that consists of the Euclidean distance $d(\mathbf {q}, \, \mathbf {p}_i) = \Vert \mathbf {q}- \mathbf {p}_i\Vert _2$ and the performance function $f(d(\cdot )) = d(\cdot )^2$. Under these settings, $M_{V_i}$ is the mass of the Voronoi cell $V_i$ for a given area density function $\rho$; we assume constant density $\rho (\cdot ) = 1 \,$.

Assumption 2

We assume the mission space $\varOmega$ to be two-dimensional, i.e., $N = 2$, and convex. In particular, the mission space does not contain any static obstacles as fixed components of the environment. However, there are mobile robots in the mission space, which represent—depending on whether they are moving or stopped—dynamic and static obstacles of circular shape to one another (see Fig. 1).

Assumption 3

The robots sense noisy positions; the noise in a robot’s position is uniformly distributed over a circle centered at the noise-free actual position and its radius is bounded by a maximum noise amplitude. We assume one noisy position per robot, i.e., each robot’s own position estimate and the estimates of its position by the other robots are equivalent. Due to this assumption, the Voronoi tessellations are correct partitions of $\varOmega$, composed of fully covering, disjoint sets of Voronoi cells.

3.2 Reciprocal Collision Avoidance Using RVO and ORCA

Assumptions 2 and 3 likewise hold for the reciprocal collision avoidance. In the case of holonomic robots with velocities $\mathbf {v}_H$, any robot j with radius $r_j$ positioned at $\mathbf {p}_j$, within a given neighborhood⁴ of a robot i with radius $r_i$ positioned at $\mathbf {p}_i$ and $j \ne i$, induces a velocity obstacle

$$\begin{aligned} VO^\tau _{i | j} = \left\{ \bar{\mathbf {v}} \, | \, \exists t \in \left[ 0 \, , \, \tau \right] , \; t \cdot \bar{\mathbf {v}} \in D(\mathbf {p}_j - \mathbf {p}_i \, , \, r_i + r_j)\right\} \, . \end{aligned}$$

(3)

Fig. 2

RVO and ORCA. Left Construction of the set of collision-free velocities $\textit{ORCA}^\tau _{i | j}$ from $VO^\tau _{i | j}$ for robot i. Right Computation of the optimal holonomic velocities $\mathbf {v}^*_{H_i}$ from the set $\textit{ORCA}^\tau _i$, given four other robots in robot i’s neighborhood as well as four different possible sets of allowed holonomic velocities $S_{\textit{AHV}_i}$. $S^1_{\textit{AHV}_i}$ represents the set for a holonomic robot, $S^2_{\textit{AHV}_i}$ corresponds to a differential-drive robot, and $S^3_{\textit{AHV}_i}$ and $S^4_{\textit{AHV}_i}$ describe two instances of the set for a bicycle robot

The vectors $\bar{\mathbf {v}} = \mathbf {v}_{H_i} - \mathbf {v}_{H_j}$ form the set of relative velocities between the robots, $\tau$ is the time horizon for a collision to occur and $D(\mathbf {p}\, , \, r) = \left\{ \mathbf {q}\, | \, \Vert \mathbf {q}- \mathbf {p}\Vert _2 < r\right\}$ is the open ball of radius r. The RVO and ORCA methods [9, 10] now assume that all the robots make similar attempts in order to avoid collisions. The set of collision-free velocities $\textit{ORCA}^\tau _{i | j}$ for a robot i with respect to any other robot j in its neighborhood results from $VO^\tau _{i | j}$ through an adjustment in velocity by

$$\begin{aligned} \mathbf {u}= \underset{\bar{\mathbf {v}} \in \partial VO^\tau _{i|j}}{{\text {argmin}}} (\Vert \bar{\mathbf {v}} - (\mathbf {v}^{\text {cur}}_{i} - \mathbf {v}^{\text {cur}}_{j})\Vert _2) - (\mathbf {v}^{\text {cur}}_{i} - \mathbf {v}^{\text {cur}}_{j}) \, . \end{aligned}$$

The vector $\mathbf {u}$ represents the smallest change the robot needs to add to the difference in the current velocities of the robots, $\mathbf {v}^{\text {cur}}_{i} - \mathbf {v}^{\text {cur}}_{j}$, in order to fully avoid a collision. The cooperativeness ratio $\alpha \in \left[ 0 \, , \, 1 \right]$ scales $\mathbf {u}$ and defines to which extent a single robot eventually participates in avoiding a reciprocal collision. The construction of the set $\textit{ORCA}^\tau _{i | j}$ is shown on the left of Fig. 2. $ORCA^\tau _{i | j}$ is given as

$$\begin{aligned} \textit{ORCA}^\tau _{i | j} = \{\mathbf {v}_{H_i} \, | \, (\mathbf {v}_{H_i} - (\mathbf {v}^{\text {cur}}_{i} + \alpha \cdot \mathbf {u})) \cdot \hat{\mathbf {n}} \ge 0 \} \, , \end{aligned}$$

(4)

where $\hat{\mathbf {n}}$ denotes the outward normal at $(\mathbf {v}^{\text {cur}}_{i} - \mathbf {v}^{\text {cur}}_{j}) + \mathbf {u}$ on $\partial VO^\tau _{i|j}$, i.e., the boundary of $VO^\tau _{i | j}$. Let $S_{{\textit{AHV}}_i}$ be the set of allowed holonomic velocities given the kinematic constraints of robot i. The final set of collision-free velocities is then computed as

$$\begin{aligned} \textit{ORCA}^\tau _i = S_{{\textit{AHV}}_i} \cap \bigcap _{j \ne i} \textit{ORCA}^\tau _{i | j} \, . \end{aligned}$$

(5)

The right side of Fig. 2 illustrates the set $\textit{ORCA}^\tau _i$ in a multi-robot scenario for different types of $S_{{\textit{AHV}}_i}$, including $S_{\textit{AHV}_i} = D(0 \, , \, v^{max}_{H_i})$ for holonomic robots with an upper bound on the velocity of $v^{max}_{H_i}$, as well as the $S_{\textit{AHV}_i}$ for differential-drive and bicycle (respectively car-like) robots, whose detailed derivations can be found in [11, 12]. The extension of the ORCA method to robots with non-holonomic kinematics is based on the idea that a robot i with given kinematic constraints can be enabled by a trajectory tracking controller to track a set of allowed holonomic velocities $S_{\textit{AHV}_i}$ within a certain maximum error bound. Because of the enlargement of the robots’ radii by this bound, $r'_i = r_i + \varepsilon _i$ and $r'_j = r_j + \varepsilon _j$, the robots can be treated as if holonomic. The velocity obstacles $VO^\tau _{i | j}$ in (3), the set $\textit{ORCA}^\tau _{i | j}$ in (4) and as a result the set $\textit{ORCA}^\tau _i$ in (5) are modified by the extended radii $r'_i$ and $r'_j$ in this case. This offers the flexibility of forming heterogeneous groups of multiple robots with different kinematic constraints and using them together in a common coverage task.

We finally obtain the optimal holonomic velocity of robot i by projection to $\textit{ORCA}^\tau _i$,

$$\begin{aligned} \mathbf {v}^*_{H_i} = \underset{\mathbf {v}_{H_i} \in \textit{ORCA}^\tau _i}{{\text {argmin}}} (\Vert \mathbf {v}_{H_i} - \mathbf {v}^{\text {pref}}_{i}\Vert _2) \, , \end{aligned}$$

(6)

which avoids reciprocal collisions among all the robots in the neighborhood for at least the time horizon $\tau$ but also lies as close as possible to the previously specified preferred velocity $\mathbf {v}^{\text {pref}}_{i}$ of (2), which represents the primary objective of coverage.

Concerning the RVO and ORCA computation, the following additional assumption applies for the rest of the paper.

Assumption 4

Even though various cooperativeness ratios are supported, we set a robot’s ratio to $\alpha = 0.5$ with respect to other cooperative robots, i.e., the robots avoid collisions in equal parts (cooperative behavior), and to $\alpha = 1$ with respect to other non-cooperative robots (non-cooperative behavior); these robots represent dynamic obstacles, which have to be fully avoided.

3.3 Properties of the Combined Method

When combining Voronoi coverage and RVO, we have two alternatives to compose distributed controllers. If we apply Voronoi coverage control in an outer loop at high level, the preferred velocities $\mathbf {v}^{\text {pref}}_{i}$ after (2) serve as inputs to the inner control loop given by the ORCA method in (6). This is the implementation we will use throughout Sect. 4. Alternatively, Voronoi coverage can be used as inner loop for formation control of a group similar to [3, 13]⁵ and the entire group can be guided as single entity similar to [14, 15] by RVO or ORCA in the outer control loop.

Regarding the combined method in light of the taxonomy, “awareness of others” is implied by the Voronoi tessellation and the velocity obstacles of RVO. The CVT-based controller realizes the shared goal of well-balanced coverage and the cooperation behavior is expressed by $\alpha$. The two coverage phases are given by the two periods before and after convergence of the Voronoi coverage controller.

The unconstrained Voronoi coverage controller is shown in [3] to converge for a team of cooperatively covering holonomic robots. In the constrained case (Voronoi coverage combined with RVO), a team of cooperatively covering holonomic robots with intragroup collision avoidance converges but stays off the centroids $\mathbf {c}_{V_i}$ by $(r'_i + r'_j)/2$ in the worst case. A team of cooperatively covering non-holonomic robots converges after [3, 6] whenever the robots move closer to the centroids in each control step (in particular, this requires bidirectional driveability of the robots). Intergroup collision avoidance among non-cooperative robots or teams, however, can introduce arbitrary perturbances, such that final convergence is not guaranteed.

4 Simulation of Robotic Use Cases

In this section, we finally apply the combined Voronoi coverage and reciprocal collision avoidance methods from Sect. 3 in simulation,⁶ and evaluate the collision scenarios from Sect. 2 for four representative robotic use cases.

4.1 Recharging Use Case

Our first use case of recharging relates to the collision scenarios (1), (2) and (4) in Fig. 1: four robots use the combined Voronoi coverage and reciprocal collision avoidance methods to cover a square mission space; during the process of coverage, the robots regularly run out of power and need to recharge their batteries. A Voronoi coverage-based method was applied to a similar application in [16], thereby focusing on energy-awareness regardless of collision situations.

The four robots are modeled after the Khepera III robots⁷ as differential-drive robots with identical parameters; only their initial battery levels differ from each other. The robots can recharge by driving to the lower borderline of the mission space, which is the charging area (blue region in Fig. 3a–d). The robots start in the bottom left corner and are deployed in the mission space of $1.2 \times 1.2 \,$m$^2$. Energy is consumed per distance traveled and per time a robot is sensing. Sensing happens whenever a robot applies the Voronoi coverage controller, i.e., the robot is not moving to, returning from or residing at the charging area.

Fig. 3

Recharging use case. Four robots deploy from the bottom left corner of the mission space. During the coverage process, the robots leave the robot team, recharge at the lower borderline and rejoin the team after charging. The covering robots compensate for the recharging robots while concurrently avoiding collisions with them. No collision avoidance leads to faster convergence of the coverage cost but also to collisions. The envelopes show $95\,\%$ confidence intervals on the mean

The recharging robots are examples of “on-off” team members, during as well as after the first phase of deployment. During deployment and after convergence, as soon as a robot’s battery level decreases below a minimum critical value (red robots in Fig. 3b–c), the robot leaves the team of covering robots and becomes an external dynamic obstacle to them (transition from intragroup to intergroup collision avoidance). The recharging robot will moreover become non-cooperative and will not help to avoid collisions with the covering robots anymore. This can also be viewed as inherently increasing the priority of the recharging robot, i.e., the remaining covering robots now have to give way and fully avoid collisions with that robot. However, the covering robots as well as the recharging robots themselves remain cooperative and still avoid collisions among each other in equal parts. Once fully charged, the robots return to the last position at which they were located when the critical battery level was detected, and rejoin the covering robot team.

Figure 3a–d presents several snapshots from the simulation of the recharging scenario. The noise in the robots’ positions is bounded by a maximum value of $0.01 \,$m. We compare the combined Voronoi coverage and reciprocal collision avoidance methods with the case where no collision avoidance is performed. Each case is tested by 10 simulation runs, during which each robot recharges twice in average. Without collision avoidance, the coverage cost is minimized faster and reaches lower levels (Fig. 3f). The resulting configurations are more optimal in terms of the minimization of the coverage cost in (1) since the covering robots do not need to avoid the recharging robots. However, there occur an average total of 8 collisions during each simulation run and 80 collisions over all runs, whereas the use of the collision avoidance method prevents most of these collisions⁸ (Fig. 3e).

Fig. 4

Push-through (left) and sweeping (right) use cases. Left Two robots (gray) push through human agents (blue) in a $4 \times 6 \,$m$^2$ mission space. The red points mark the start positions, the gray lines the Voronoi cells and the trajectories are in green. Thin blue arrows represent velocities $\mathbf {v}^{\text {pref}}_{i}$ and red arrows indicate velocities $\mathbf {v}^*_{H_i}$. Right Two robots at a time form a group (red and blue, violet and yellow, orange and green) and deploy. Each of the three groups covers one of the three Voronoi cells redundantly; the first robot in the group (red, violet, orange) executes a spiraling sweeping pattern and the second robot moves back and forth (blue, yellow, green). In the process, the robots have to avoid reciprocal collisions at the boundaries of their Voronoi cells and with each other. Finally, the set of red, violet and orange trajectories and the set of blue, yellow and green trajectories each result in complete coverage of the mission space without collisions

4.2 Push-Through Use Case

In the second use case, we simulate a heterogeneous crowd of 12 human agents and two robots (see Fig. 4 on the left). We model the robots as the differential-drive Pioneer 3-DX⁹ and assume a holonomic kinematic model for the humans. The CVT is used as a simplified model of the human personal space. The human agents are distributed according to the Voronoi coverage controller. This is an example of collision scenario (5) in Fig. 1, after initial deployment, with intergroup collision avoidance and cooperative behavior. After convergence, the human agents stand at their positions slightly apart, similar to people waiting at a bus stop. The robots move across the mission space by pushing through the crowd; in order to reduce disturbances of the humans, the robots follow the Voronoi graph, which represents a maximum clearance roadmap. Thereby, both the human agents and the robots run the reciprocal collision avoidance method at the low level with $\alpha = 0.5$ for everyone.

4.3 Sweeping Use Case

The third use case relates to sweep coverage, e.g., for cleaning or inspection tasks, and includes collision scenarios that occur during and after the first phase of deployment, with intragroup collision avoidance and cooperative behavior. It showcases the concepts of abstractions for robot groups and hybrid coverage [8], illustrated as collision scenarios (3) and (6) in Fig. 1 above. Six differential-drive Khepera III robots form a covering team but further subdivide into groups of two. The groups deploy in the mission space of $1.2 \times 1.2 \,$m$^2$. At convergence, the final CVT is fixed and each of the three groups subsequently sweeps its Voronoi cell collaboratively by applying spiraling and back-and-forth sweeping patterns (see Fig. 4 on the right). All the robots run the reciprocal collision avoidance method with $\alpha = 0.5$. The resultant redundant coverage with two different coverage patterns in parallel presents a characteristic outcome of combining robotic coverage and reciprocal collision avoidance.

4.4 Perturbation Use Case

The last use case looks at the perturbation that is introduced into a multi-robot system through external dynamic obstacles. The dynamic obstacles traverse a bounded mission space, which is covered by a robot team according to the Voronoi coverage control law. The covering robots need to fully avoid the dynamic obstacles as well as the enclosing borderlines of the mission space.

Fig. 5

Perturbation use case. Top left Start positions of the robots. The gray lines show how much the CVT is perturbed through noise for case (i) over a simulation run. Center left Massive perturbation of the covering robots by external dynamic obstacles (blue), moving from the bottom to the top, for case (vi). The robots avoid the collisions while covering the mission space. Bottom left Robots’ final configuration after a completed simulation run for case (vi). Top right Coverage cost per time for cases (i) and (ii). Center right Coverage cost per time for cases (iii) and (iv). Bottom right Coverage cost per time for cases (v) and (vi). The envelopes show $95\,\%$ confidence intervals on the mean. The black dash-dotted horizontal lines show the cost at start and the black dash-dotted vertical lines at $20\,\mathrm{s}$ mark the time when the injection of obstacles is stopped

This use case shows a scenario for the second phase after initial deployment, with intergroup collision avoidance and non-cooperative behavior, and is of general interest for applications with adversarial pursuers or intruders. However, in this paper, we are particularly interested in the aspect of how the inherent perturbation by dynamic obstacles influences the coverage cost and the optimality of the robot deployment. The configurations after convergence of the Voronoi coverage method correspond to local minima of the coverage cost. More optimal configurations can be reached through the perturbation of the robot team. This may also help to break off saddle points and symmetry configurations which sometimes result from CVTs [4].

12 holonomic robots, similar in size to e-puck robots,¹⁰ deploy initially from the bottom left corner. We simulate the cases with no perturbation through external dynamic obstacles but with a maximum noise in the robots’ positions of (i) $0.01 \,$m and (ii) $0.05 \,$m, as well as the cases with perturbation for the maximum noise in position of $0.01 \,$m and the following settings: (iii) small obstacles and low frequency of perturbation, (iv) small obstacles and high frequency of perturbation, (v) large obstacles and low frequency of perturbation, and (vi) large obstacles and high frequency of perturbation. The small obstacles have the same size as the robots, the large obstacles are double the size; the high frequency (1 s$^{-1}$) is twice the low frequency (0.5 s$^{-1}$). The injection of new obstacles is stopped in each case after half the simulation time ($20\,\mathrm{s}$) to allow the robots to settle down. For each setting, 15 simulation runs were computed. Figure 5 shows the simulation of the perturbation scenario and compares perturbations through noise only with perturbations through small or large dynamic obstacles at low or high frequency. At low noise levels of $0.01\,$m, the robot configurations are not changed substantially. However, at increased noise levels, such as $0.05\,$m, the noise influences the robots’ positions and changes the configuration, which leads to more optimal coverage cost. The same result can be achieved through the perturbation with external dynamic obstacles. The obstacles initiate high temporary perturbations which may stop at some point, whereas the noise level usually remains. Note that large obstacles and high frequencies introduce stronger perturbations, which take longer to settle down but increase chances for reaching more optimal configurations and lower coverage cost.

5 Conclusions and Future Work

This paper motivates the combined use of coverage and collision avoidance methods for multi-robot systems. We present a taxonomy of collision scenarios in multi-robot coverage problems and illustrate the performance of the combined methods in simulations. For our specific study, we review the Voronoi coverage control and reciprocal collision avoidance methods, such as RVO and ORCA, and combine and apply them to four representative robotic use cases, namely recharging during persistent coverage, pushing through a human crowd, sweeping for inspection and reacting to perturbations introduced by external dynamic obstacles.

As direct continuation of the presented work, the combined Voronoi coverage and reciprocal collision avoidance methods are to be tested for each use case on the real robot platforms. The study of Voronoi coverage control under the influence of actuator and sensor noise presents another related research direction. Foremost, it would be interesting to study further coverage and cooperation tasks in view of the proposed taxonomy of collision scenarios.