Optimal Mixed Strategies for Cost-Adversarial Planning Games

Authors

  • Rostislav Horčík Czech Technical University in Prague
  • Álvaro Torralba Aalborg University
  • Pavel Rytíř Czech Technical University in Prague
  • Lukáš Chrpa Czech Technical University in Prague
  • Stefan Edelkamp Czech Technical University in Prague

Keywords:

Cost-optimal Planning, Nash Equilibrium, Almost Zero-sum Game, Double Oracle

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.

Downloads

Published

2022-06-13

How to Cite

Horčík, R., Torralba, Álvaro, Rytíř, P., Chrpa, L., & Edelkamp, S. (2022). Optimal Mixed Strategies for Cost-Adversarial Planning Games. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 160-168. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19797