A game-theoretic approach to non-cooperative target assignment

Shemin Kalam, Mahbub Gani, Lakmal Seneviratne

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

In this paper, we have adopted a game-theoretic approach to consider the optimal assignment of targets to vehicles. We have taken optimality to mean the minimum sum of costs which are proportional to the Euclidean distance 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 itself to a target located within the Voronoi region associated with the vehicle. Standard schemes require communication between vehicles 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. Vehicles that do not have any targets within their Voronoi region select their nearest unassigned target. We also present a communication model illustrating how the model can be implemented in a practical scenario.

Original languageBritish English
Pages (from-to)955-962
Number of pages8
JournalRobotics and Autonomous Systems
Volume58
Issue number8
DOIs
StatePublished - Aug 2010

Keywords

  • Game theory
  • Non-cooperative
  • Vehicle-target assignment

Fingerprint

Dive into the research topics of 'A game-theoretic approach to non-cooperative target assignment'. Together they form a unique fingerprint.

Cite this