Journal article
Double Oracle Algorithm for Game-Theoretic Robot Allocation on Graphs
IEEE transactions on robotics, v 41, pp 3244-3259
06 May 2025
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
In this article, we study the problem of game-theoretic robot allocation where two players strategically allocate robots to compete for multiple sites of interest. Robots possess offensive or defensive capabilities to interfere and weaken their opponents to take over a competing site. This problem belongs to the conventional an acronym colonel blotto game (CBG). Considering the robots' heterogeneous capabilities and environmental factors, we generalize the conventional Blotto game by incorporating heterogeneous robot types and graph constraints that capture the robot transitions between sites. Then, we employ the double oracle algorithm (DOA) to solve for the Nash equilibrium of the generalized Blotto game. Particularly, for cyclic-dominance-heterogeneous (CDH) robots that inhibit each other, we define a new transformation rule between any two robot types. Building on the transformation, we design a novel utility function to measure the game's outcome quantitatively. Moreover, we rigorously prove the correctness of the designed utility function. Finally, we conduct extensive simulations to demonstrate the effectiveness of DOA on computing Nash equilibrium for homogeneous, linear heterogeneous, and CDH robot allocation on graphs.
Metrics
5 Record Views
Details
- Title
- Double Oracle Algorithm for Game-Theoretic Robot Allocation on Graphs
- Creators
- Zijian An - Drexel UniversityLifeng Zhou - Drexel University, Electrical and Computer Engineering
- Publication Details
- IEEE transactions on robotics, v 41, pp 3244-3259
- Publisher
- IEEE
- Number of pages
- 16
- Grant note
- Drexel Seaman Endowed Fellowship
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:001497954000006
- Scopus ID
- 2-s2.0-105004753053
- Other Identifier
- 991022051420004721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Robotics