Service de Mathématiques - Nonuniform coverage and cartograms

by F. Lekien and N.E. Leonard
SIAM J. Control Optim. 48(1), pp. 351—372, 2009.

Abstract

In this paper, we investigate nonuniform coverage of a planar region by a network of autonomous, mobile agents. We derive centralized nonuniform coverage control laws from uniform coverage algorithms using cartograms, transformations that map nonuniform metrics to a near Euclidean metric. We also investigate time-varying coverage metrics and the design of control algorithms to cover regions with slowly varying, nonuniform metrics. Our results are applicable to the design of mobile sensor networks, notably when the coverage metric varies as data is collected such as in the case of an information metric. The results apply also to the study of animal groups foraging for food that is nonuniformly distributed and possibly changing.

Download paper

PDF Full text (1.6Mb)
PDF with high resolution figures (30Mb)

Animations

	Animated cartogram Animated GIF 512x408 AVI 512x408 Cartogram with deformation grid Animated GIF 512x408 AVI 512x408
	Convergence to uniform coverage Animated GIF 512x511 AVI 512x511 AVI 1024x1022
	Animated cartogram Animated GIF 512x511 AVI 512x511 Vehicles in motion Animated GIF 512x511 AVI 512x511
	Animated cartogram Animated GIF 512x511 AVI 512x511 AVI 1024x1022 Vehicles in motion Animated GIF 512x511 AVI 512x511 AVI 1024x1022
	Animated cartogram Animated GIF 512x511 AVI 512x511 Vehicles in motion Animated GIF 512x511 AVI 512x511

Figures

			Convergence to static uniform coverage. Thick dots: Position of the 4 agents. Shaded polygons: Voronoi cell for each agent. Large circles: Circumcircle of each Voronoi cell. Diamonds: Circumcenters. Arrows: Velocity of the vehicles (oriented along the segment joining the agents to the circumcenter of their Voronoi cell)
			Linguistic distribution and population density in Belgium. Left panel: Equal-area (Belgian Lambert) projection. Blue represents Flemish provinces, red stands for French-speaking provinces and green indicates the Brussels-Capital area. Center panel: Density of population binned on 5km x 5km cells (source: Columbia University's Center for International Earth Science Information Network). Right panel: Cartogram of the country based on population density. Areas in this projection are proportional to population and accurately represent the linguistic distribution.
	Proposed approach: when computing a cartogram for a domain $\mathcal{D}$ that has an arbitrary shape or for which the normal derivative of the density function $\rho$ does not vanish at the boundary, a large rectangle $\mathcal{D}_0\!\supset\!\mathcal{D}$ is selected. The density $\rho$ is extended outside $\mathcal{D}$ by enforcing Neumann boundary conditions at the boundary of the large square, requiring continuity of $\hat{\rho}$ at the edge with $\mathcal{D}$ , and setting the Laplacian of $\hat{\rho}$ to a constant value outside $\mathcal{D}$ . This defines a unique extension $\hat{\rho}$ which is continuous and has continuous derivatives almost everywhere.
		Continuous extension of the Belgian population density to a large rectangle with homogeneous Neumann boundary conditions. The extended density in the large rectangle is diffused to obtain the cartogram above.
Cartogram of the unit square in preparation for non-uniform sampling. Left panel: Physical domain with level sets of the Gaussian density function Right panel: Cartogram and image of a Cartesian mesh.
			Convergence to static non-uniform coverage. Thick dots: Position of the 4 vehicles. Shaded polygons: Voronoi cell for each vehicle (computed in the cartogram space). Large circles: Circumcircle for each Voronoi cell of the cartogram. Diamonds: Centers of each circumcircle (i.e., circumcenters). Arrows: Instantaneous velocity of the vehicles (oriented along the segment joining the vehicle to the circumcenter of its Voronoi cell). The first row depicts the computation in the cartogram space. The second row gives the resulting positions of the vehicles in the physical space.
		Level sets of the distortion factor for the cartograms constructed in this paper
			Convergence to non-uniform coverage with time-varying density. Thick dots: Position of the 4 vehicles. Shaded polygons: Voronoi cell for each vehicle (computed in the cartogram space). Large circles: Circumcircles for each Voronoi cell of the cartogram. Diamonds: Centers of each circumcircle (i.e., circumcenters). Arrows: Instantaneous velocity of the vehicles (oriented along the segment joining the vehicle to the circumcenter of its Voronoi cell). The first row depicts the computation in the cartogram space. The second row gives the resulting positions of the vehicles in the physical space. From left to right, the snapshots are taken when the peak of density is in the upper right corner, at $y=\frac{1}{2}$ , and in the lower right corner.
			Array of 10 agents covering the square with non-uniform, time-varying density. On the left, the peak of density is in the upper right quadrant; on the right, the peak is in the lower right quadrant. The middle panel is an intermediate snapshot.