Non-cooperative Target Assignment using Regret Matching

Shemin Kalam; Mahbub Gani

Non-cooperative Target Assignment using Regret Matching

King's College London

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

Abstract

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.

Original language	English
Title of host publication	Unknown
Place of Publication	NEW YORK
Publisher	IEEE
Pages	787 - 792
Number of pages	6
ISBN (Print)	978-1-4244-7813-2
Publication status	Published - 2010
Event	11th International Conference on Control, Automation, Robotics and Vision (ICARCV 2010) - Singapore, Singapore Duration: 7 Dec 2010 → 10 Dec 2010

Publication series

Name	11TH INTERNATIONAL CONFERENCE ON CONTROL, AUTOMATION, ROBOTICS AND VISION (ICARCV 2010)

Conference

Conference	11th International Conference on Control, Automation, Robotics and Vision (ICARCV 2010)
Country/Territory	Singapore
City	Singapore
Period	7/12/2010 → 10/12/2010

Cite this

@inbook{71913decb7094e4bb56d923cf5b53d52,

title = "Non-cooperative Target Assignment using Regret Matching",

abstract = "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.",

author = "Shemin Kalam and Mahbub Gani",

year = "2010",

language = "English",

isbn = "978-1-4244-7813-2",

series = "11TH INTERNATIONAL CONFERENCE ON CONTROL, AUTOMATION, ROBOTICS AND VISION (ICARCV 2010)",

publisher = "IEEE",

pages = "787 -- 792",

booktitle = "Unknown",

note = "11th International Conference on Control, Automation, Robotics and Vision (ICARCV 2010) ; Conference date: 07-12-2010 Through 10-12-2010",

}

TY - CHAP

T1 - Non-cooperative Target Assignment using Regret Matching

AU - Kalam, Shemin

AU - Gani, Mahbub

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79952376346&partnerID=8YFLogxK

M3 - Conference paper

SN - 978-1-4244-7813-2

T3 - 11TH INTERNATIONAL CONFERENCE ON CONTROL, AUTOMATION, ROBOTICS AND VISION (ICARCV 2010)

SP - 787

EP - 792

BT - Unknown

PB - IEEE

CY - NEW YORK

T2 - 11th International Conference on Control, Automation, Robotics and Vision (ICARCV 2010)

Y2 - 7 December 2010 through 10 December 2010

ER -

Non-cooperative Target Assignment using Regret Matching

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this