Abstract
This paper shows that domain-independent tools from classical planning can be used to model and solve a broad class of game-theoretic problems we call Cost-Adversarial Planning Games (CAPGs). We define CAPGs as 2-player normal-form games specified by a planning task and a finite collection of cost functions. The first player (a planning agent) strives to solve a planning task optimally but has limited knowledge about its action costs. The second player (an adversary agent) controls the actual action costs. Even though CAPGs need not be zero-sum, every CAPG has an associated zero-sum game whose Nash equilibrium provides the optimal randomized strategy for the planning agent in the original CAPG. We show how to find the Nash equilibrium of the associated zero-sum game using a cost-optimal planner via the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, we formalize a patrolling security game and several IPC domains as CAPGs.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the 32nd International Conference on Automated Planning and Scheduling, ICAPS 2022 |
Redaktører | Akshat Kumar, Sylvie Thiebaux, Pradeep Varakantham, William Yeoh |
Antal sider | 9 |
Vol/bind | 32 |
Forlag | AAAI Press |
Publikationsdato | 13 jun. 2022 |
Sider | 160-168 |
ISBN (Elektronisk) | 9781577358749 |
DOI | |
Status | Udgivet - 13 jun. 2022 |
Begivenhed | The 32nd International Conference on Automated Planning and Scheduling - Virtual, Singapore, Singapore Varighed: 13 jun. 2022 → 24 jun. 2022 |
Konference
Konference | The 32nd International Conference on Automated Planning and Scheduling |
---|---|
Lokation | Virtual |
Land/Område | Singapore |
By | Singapore |
Periode | 13/06/2022 → 24/06/2022 |