Classical Planning and Cost-Adversarial Planning Games

Classical planning is an area of AI striving to build efficient solvers searching a (shortest) path in a succinctly represented digraph from a source node to any of target nodes. Due to the succinct representation, the problem is computationally challenging. The problem instances are specified in a standardized formal language to make the particular solvers domain-independent and easily comparable. The first part of the talk will present a brief introduction to classical planning.

The second part will focus on applying classical planning to security games. I will introduce Cost-Adversarial Planning Games (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. Nash equilibria of CAPGs can be found using a cost-optimal planner and the Double Oracle algorithm. To demonstrate the expressivity of CAPGs, I will present several examples of what kind of problems can be modeled as CAPGs.