About
The purpose of multi-agent coverage control is to direct agents (robots) to cover a space as best they can. This can be a 2D area or 3D region in space, one main application is surveillance of an area of interest via mobile robots with sensors. The advantages of performing multi-agent coverage control in a distributed way include robustness to agents being added to or leaving the system, less information must be shared with each other agent, and there is no central point of failure. For these reasons, we have implemented Fortune's algorithm as our method to deploy robots.
Algorithms
Fortune's Algorithm and Voronoi Diagrams
A Voronoi Diagram is the initial step in constructing an evenly spaced out region throughout which multiple agents can be distributed. A Voronoi Diagram is defined as shown on the wiki page Voronoi diagram. That is, a Voronoi diagram is simply a domain broken up into cells. Each cell is defined around an agent. By using the eculidian distance the cells have the following property: that any point within an agent's cell has a distance to the agent that is less than or equal to any other agent in the domain. By using this definition, an example voronoi with six agents (denoted by the black dots) may look as shown in the following figure.
Image of a Voronoi Diagram with 6 sites (agents).
A famous algorithm for computing a Voronoi Diagram is Fortune's Algorithm named after Steven Fortune which was publish in his paper in 1986. This algorithm uses a sweepline approach. The algorithm uses a set of points in a plane using O(n log n) time and O(n) space. To read more see the wiki page Fortune's Algorthim. An animation of this algorithm is shown below.
Animation of Fortune's Algorithm computing a Voronoi Diagram, taken from Wikipedia.
Weighted Centroid Algorithm
In order to distribute the agents "evenly" over a given area, the Voronoi Diagram partition of regions or cells is not enough. A necesary component is moving the agents to the centroid or center of mass of their respective cells. This is especially important when prescribing an area of importance.
The way the centroids are computed are cell by cell. Once Fortune's algorithm is run, a Voronoi Diagram is returned. Which specifies the location of the agents within their cells. At this point the Weighted Centroids Algorithm computes the weighted centroid of each cell by further partitioning each cell up triangles formed with the vertices of the agent's cell and the position of the agent itself. This allows for the computation of the weighted centroid of each triangle and ultimately the cell itself.
Flow chart depicting how Fortune's Algorithm and Weighted Centroid Algorithm work together.
The computation over the triangles is done using a finite element scheme and the areas of importance of defined using gaussian distributions. Once the weighted centroids are found for all cells, the agents are moved towards their respective centroids. After moving, Fortune's algorithm is called to recalculate the Voronoi Diagram. This process is iterated until either it converges or the importance function is moved in which case it will continue to run iteratively.
This video shows, starting with a Voronoi Diagram computed with Fortune's Algorithm, how the triangles are formed using cell vertices and agent positions. The black lines denote the Vornoi Diagram, the blue circles denote the position of the agents, the green lines denote the traingles of each cell, red x's denote weighted centroids of the triangles, the black dots denote the finial weighted centroid. The density function used is uniform throughout the domain.
Applications
Android App Use of Voronoi Weighted Centroid Algorithm
With the android app we are able to show the use of the the Weighted Centroid Algorithm using a Gaussian distribution as the importance. The following is a video demonstrating a simulation of the agents finding their cetnroids using a guassian distribution.
This video shows a simulation of 5 agents being distributed over a domain using a gaussian function on the android app.
In addition we have implemented a static agent as a strategy to enable the agents to move around obstacles by setting the location of the obstacles as the location of another agent that is nonmoving (hence the static agent). By using this strategy a cell is created for the obstacle itself and the other agents by definition do not interfere with the cell of the obstacle and thereby move around the obstacle. A video showing this implemenation is shown below.
This video shows a number of agent moving around the obstacle while simulatenously moving towards their resepctive centroids.
We are currently still in developmental phase in implementing these algorithms on the turtelBots for coverage control. The following video demonstates some of the current progress that is taking place.
This video shows the coverage control algorithms being tested on 3 turtleBots using the adroid app to control the gaussian distribution and the location of the mean.
We are currenlty preparing for a demo at UCSD. The following is a video displaying a few updates we have made with the coverage control algorithm.
This video shows an updated version of the converage control algorithm deployment on four turtlebots using obstacles and path following.
In this next video you will see an older version of the multi-agent coverage control implementation. This implementation had no human user interaction and used only a uniform distribution.
Older converage control algorithm implementation. Uses a simple uniform distribution.