AAAI Publications, Thirty-Second AAAI Conference on Artificial Intelligence

Font Size: 
Stackelberg Planning: Towards Effective Leader-Follower State Space Search
Patrick Speicher, Marcel Steinmetz, Michael Backes, Jörg Hoffmann, Robert Künnemann

Last modified: 2018-04-26

Abstract


Inspired by work on Stackelberg security games, we introduce Stackelberg planning, where a leader player in a classical planning task chooses a minimum-cost action sequence aimed at maximizing the plan cost of a follower player in the same task. Such Stackelberg planning can provide useful analyses not only in planning-based security applications like network penetration testing, but also to measure robustness against perturbances in more traditional planning applications (e. g. with a leader sabotaging road network connections in transportation-type domains). To identify all equilibria---exhibiting the leader’s own-cost-vs.-follower-cost trade-off---we design leader-follower search, a state space search at the leader level which calls in each state an optimal planner at the follower level. We devise simple heuristic guidance, branch-and-bound style pruning, and partial-order reduction techniques for this setting. We run experiments on Stackelberg variants of IPC and pentesting benchmarks. In several domains, Stackelberg planning is quite feasible in practice.

Keywords


Planning; Stackelberg; Security; Pentesting; Partial Order Reduction; IPC

Full Text: PDF