Prize Collecting Multiagent Orienteering: Price of Anarchy Bounds and Solution Methods

Timothy Murray, Jugal Garg, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review

Abstract

We propose and address a new variation of the team orienteering problem (TOP) in which all members of the team are independent self-interested agents. The prize-collecting nature emanates from the fact that the prize available at a node of the traversal graph can be collected only by a single visiting agent. The problem is motivated by situations in which team members (agents) must accomplish tasks toward a common goal but are unable to communicate, such as a fleet of surveillance drones operating in a communication denied area or with remote pilots operating independently. We explore three policies for minimizing the amount of inefficiency these self-interested agents can bring into the situation. We analyze these policies in a game-theoretic framework and show upper bounds on the Price of Anarchy (PoA) ranging from $\approx 1.582$ to unbounded depending on the policy, network type, and the number of players $k$. This is done by extending well-known PoA bounds for valid utility systems to a leader-follower setting. The PoA also depends on the behavior of the agents, which could not have goodwill toward other agents. In many cases, we are able to provide examples that establish the tightness of the bounds. Finally, solution methods are provided for each of these policies. Numerical results computed by these solution methods are then presented and compared with the optimal centrally coordinated solutions. Note to Practitioners - Unmanned aerial vehicles (UAVs) are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and when centralized optimal routes for each UAV are too complex to compute. For managers of UAV systems, our work provides a theoretical bound on how bad decentralized routing could be in the context of a prize-collecting game. Under a game-theoretic framework, we prove that the fleet will collect at least 50% of the prizes collected by the optimal centralized solution. Empirically, we show that the performance of the fleet is much better, usually providing at least 90% of the optimal centralized solution. Our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.

Original languageEnglish (US)
Pages (from-to)531-544
Number of pages14
JournalIEEE Transactions on Automation Science and Engineering
Volume19
Issue number1
DOIs
StatePublished - Jan 1 2022

Keywords

  • Game theory
  • Price of Anarchy (PoA)
  • multiagent systems
  • prize collection

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Prize Collecting Multiagent Orienteering: Price of Anarchy Bounds and Solution Methods'. Together they form a unique fingerprint.

Cite this