Fully non-cooperative optimal placement of mobile vehicles

In this paper, we consider optimal placement of autonomous mobile vehicles such that a cost function involving all the vehicles and possible locations of targets is minimized. This cost is proportional to the distance between the targets and vehicles. The optimal locations correspond to the vehicles being at the centroids of their own Voronoi cell which correspond to Centroidal Voronoi Tessellations (CVTs). We have adopted a game theoretical formulation to initially consider vehicle target assignment where a set of mobile vehicles choose their own targets. The movement of the vehicles towards the optimal locations is based on MacQueen's algorithm. But an important step of MacQueen's algorithm requires the knowledge of the nearest neighbour to be determined from a sample that is drawn from a fixed but unknown probability distribution. This calculation seems to be implicit in reported algorithms and brings in a hidden centralized process. We have used game theory as a framework to get around this problem and modelled the vehicles such that they are capable of making their own decisions and interested in optimizing their own utilities. Specifically, we have introduced an appropriate utility function and require the vehicles to negotiate their choice of targets via regret matching. We present simulations that illustrate that vehicles choose the targets optimally and converge to CVTs.