Coverage control for wire-traversing robots

Examples of coverage control. The Voronoi cells and a density function on the environment are depicted as gray thick lines and a colored contour plot, respectively.

The problem of deploying a team of robots in a closed and convex environment for monitoring purposes has been widely studied, and an algorithm to solve it is known as coverage control. Starting from the definition of a locational cost $\mathcal H$, the following locational optimization problem can be defined:

$$\underset{p}{\mathrm{minimize~}} \mathcal H(p),$$

where $p$ is the vector of positions of robots. This can solved in a decentralized fashion considering the following gradient-flow control law that drives the robots to an optimal spatial distribution (i.e. a centroidal Voronoi tessellation):

$$\dot p = \dfrac{\partial \mathcal H(p)}{\partial p}.$$

In our work, we analyze the case in which the deployed robots are constrained to move on wires or curves (as in the case of the SlothBot) which can be formalized as the following constrained optimization problem:

$$\begin{aligned} \underset{p}{\mathrm{minimize~}} &\mathcal H(p)\\ \mathrm{subject~to~} &p \in \mathcal C, \end{aligned} $$

where $\mathcal C$ represents the curve on which the robots move. Unless $\mathcal C$ is a straight curve, the constraint $p \in \mathcal C$ is non-convex.

First, we consider robots that are constrained to move on a mesh of wires present in the environment they have to cover. The problem is far from being trivial, insofar as a naive approach consisting of projecting the motion of the robots onto the wires would suffer from the following two problems:

  • the robots may get stuck in a very bad spatial distribution, or
  • the resulting projected motion is not continuous.

We propose a continuous-onto-wires (COW) mapping which allows to overcome these issues, by providing a continuous mapping onto the wires using which the robots end up in an optimal constrained spatial distribution. The video below shows the developed algorithm implemented on real robots.

1-D Voronoi coverage
Projected gradient Voronoi coverage
Weighted 1-D Voronoi coverage

The second problem we consider consists in designing a control law that allows robots to optimally distribute themselves along a smooth curve on which they are constrained to move. Unlike the previous case, here the robots cannot switch between wires, but they can only move on a single smooth curve.
If for simple cases this problem can be cast as a convex optimization problem, in most realistic scenarios, it requires further analyses. The solution we propose builds up on the one-dimensional Voronoi coverage control algorithm to develop a new optimization problem and a convex relaxation that can be solved by the robots in a decentralized fashion. The video below shows the implementation of this algorithm on a team of mobile robots.

More details on this work can be found in the following two papers:

Additional resources

  • The basic formulation of the unconstrained coverage control can be found in this paper
  • The experiments shown above are programmed using the swarm simulator available here, and executed on the Robotarium