Autonomous Vehicle-Target Assignment: A Game-Theoretical Formulation

TLDR

The paper addresses the autonomous vehicle‑target assignment problem, aiming for optimal self‑assignment among multiple vehicles to a set of targets. The study proposes a game‑theoretical framework treating vehicles as self‑interested agents to achieve optimal target assignments. The authors design vehicle utility functions that are localized yet aligned with a global objective and equip vehicles with negotiation mechanisms that enable individually rational decisions toward the global utility. Two novel negotiation mechanisms—generalized regret monitoring with fading memory and inertia, and selective spatial adaptive play—are introduced, proven to converge, and simulations show they lead to near‑optimal assignments when utilities are properly designed.

Abstract

We consider an autonomous vehicle-target assignment problem where a group of vehicles are expected to optimally assign themselves to a set of targets. We introduce a game-theoretical formulation of the problem in which the vehicles are viewed as self-interested decision makers. Thus, we seek the optimization of a global utility function through autonomous vehicles that are capable of making individually rational decisions to optimize their own utility functions. The first important aspect of the problem is to choose the utility functions of the vehicles in such a way that the objectives of the vehicles are localized to each vehicle yet aligned with a global utility function. The second important aspect of the problem is to equip the vehicles with an appropriate negotiation mechanism by which each vehicle pursues the optimization of its own utility function. We present several design procedures and accompanying caveats for vehicle utility design. We present two new negotiation mechanisms, namely, “generalized regret monitoring with fading memory and inertia” and “selective spatial adaptive play,” and provide accompanying proofs of their convergence. Finally, we present simulations that illustrate how vehicle negotiations can consistently lead to near-optimal assignments provided that the utilities of the vehicles are designed appropriately.