Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/30683
Title: Cooperative Coverage of Spatial Urban Networks
Authors: MUHAMAD AZFAR BIN RAMLI
Keywords: probabilistic coverage, Weibull distribution, multi-agent systems, stationary density, bounded domains, circular discretization
Issue Date: 11-Aug-2011
Source: MUHAMAD AZFAR BIN RAMLI (2011-08-11). Cooperative Coverage of Spatial Urban Networks. ScholarBank@NUS Repository.
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.
URI: http://scholarbank.nus.edu.sg/handle/10635/30683
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Ramli MA.pdf2.07 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

211
checked on Dec 11, 2017

Download(s)

189
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.