Non-cooperative target assignment using regret matching

In this paper, we have adopted a game theoretic approach to consider optimal assignment of targets to vehicles. We have taken optimality to mean that the cost of vehicle-target assignment is minimized where the cost is the sum of the Euclidean distances between a vehicle and its assigned target. This occurs when the set of targets is assigned to their nearest vehicles. In other words, each vehicle should assign themselves to a target located within the Voronoi region associated with the vehicle. Standard schemes require vehicle-vehicle communication at least to rank the targets according to the nearest neighbour rule. In our proposed model, there is no need for communication among the vehicles and only limited communication between the targets and the vehicles is required. Specifically, we have introduced an appropriate utility function which depends on the distance between the vehicles and targets and the number of vehicles engaging a particular target. The vehicles negotiate their choice of targets via regret matching. We present simulations which demonstrate that vehicles select targets that fall within their Voronoi region. For vehicles that do not have any targets within their Voronoi region, they select their nearest unassigned target. We also present analysis of how the designed utility function causes convergence of the vehicle-target assignment using regret matching.