Potential Game Based Distributed Control for Voronoi Coverage Problems with Obstacle Avoidance

Toshimitsu USHIO

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A    No.7    pp.1156-1163
Publication Date: 2012/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.1156
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Concurrent Systems
Voronoi coverage,  obstacle avoidance,  barycentric coordinate,  potential game,  replicator dynamics,  

Full Text: PDF(1.5MB)>>
Buy this Article

It is known that the optimal sensor coverage of a mission space is performed by a Voronoi partition, which is called a Voronoi coverage problem. We consider the case that the mission space has several obstacles where mobile sensors cannot be deployed and search an optimal deployment to maximize the sensing performance. Inspired by the potential field method, we introduce a repulsive potential for obstacle avoidance and define the objective function by a combination of two functions: one for evaluation of the sensing performance and the other for obstacle avoidance. We introduce a space where a sensor can move, called its moving space. In general, a moving space may not coincide with the mission space. We assume that the respective moving spaces of each sensor may differ from each other. By introducing a barycentric coordinate over the moving space, we show that the Voronoi coverage problem to maximize the objective function is transformed into a potential game. In potential games, local maximizers of a potential function are stable equilibrium points of the corresponding replicator dynamics. We propose a distributed sensor coverage control method based on the replicator dynamics to search a local maximizer of the objective function and a path to it. Using simulations, we also compare the proposed method with the Lloyd and TangentBug algorithm proposed by Breitenmoser et al.