Cooperative Coverage of Spatial Urban Networks

Abstract

In this thesis, I investigate the properties of coverage of multiple agents within a bounded domain. In the first chapter, I provide a general definition of coverage for the discrete or continuous time on a discrete or continuous domain and review the past literature on various forms of the coverage problem.

For the first major contribution of this thesis, the detailed statistics of coverage on a discrete space is studied, specifically on complete graphs. Using a master equation method, we derive the exact probability density function and expectation of coverage time on a complete graph with multiple agents. Several useful identities involving Stirling numbers of the second kind are discovered.

The second contribution made in this thesis is the prediction of the stationary probability density of a randomly moving agent within a bounded domain. Given knowledge of its current location, we find that we can predict and even engineer the long-run probability of an agent?s position based on a decision probability of deciding which direction to move. The coverage of the whole domain is assured in the long-run and specific sites within the bounded domain can be made to be visited more frequently.

For the third contribution, I find the representation of a circular area using a square grid results in a discretization error which varies linearly with the discretization ratio of the simulation. An accurate result with zero discretization error can be obtained via extrapolation. A novel method is proposed for storage of the coverage information in the square grid by using the Coordinate pairs? method, decreasing the memory requirements of the simulation procedure.

For the fourth contribution in my thesis, I solve for the exact expected coverage of various random sets distributed uniformly within a bounded domain. This problem represents the initial coverage problem during the deployment of sensors into the domain. Analysis is conducted on the edge effects on the coverage capability of circular sensor footprints within a rectilinear domain. The theoretical formula derived in this chapter is compared to the simulation results and verifies the simulation results.

The final main contribution is a model that describes the coverage evolution of multiple agents within a two-dimensional bounded domain. Mobile agents are used in an experimental procedure and their movement is governed by a random billiard ball algorithm. The coverage is measured using a vision based system. We find that the evolution of coverage with time can be modeled by the cumulative distribution function of a Weibull distribution and show that the parameters of the model correspond to the sensor radius, velocity and the number of agents used. We then compare between the speed-up attained from the complete graph case and the speed-up attained from the actual robots and find that the speedup characteristics behave differently due to the physical constraints of a real coverage process.