CISPA
Browse

Stackelberg Planning: Towards Effective Leader-Follower State Space Search

Download (854.63 kB)
conference contribution
posted on 2023-11-29, 18:08 authored by Patrick Speicher, Marcel Steinmetz, Michael BackesMichael Backes, Jörg Hoffmann, Robert KünnemannRobert Künnemann
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 (eg with a leader sabotaging road network connections in transportation-type domains). To identify all equilibria–exhibiting the leader's own-cost-vs.-follower-cost tradeoff–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.

History

Preferred Citation

Patrick Speicher, Marcel Steinmetz, Michael Backes, Jörg Hoffmann and Robert Künnemann. Stackelberg Planning: Towards Effective Leader-Follower State Space Search. In: National Conference of the American Association for Artificial Intelligence (AAAI). 2018.

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

National Conference of the American Association for Artificial Intelligence (AAAI)

Legacy Posted Date

2018-02-14

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_1426, title = "Stackelberg Planning: Towards Effective Leader-Follower State Space Search", author = "Speicher, Patrick and Steinmetz, Marcel and Backes, Michael and Hoffmann, Jörg and Künnemann, Robert", booktitle="{National Conference of the American Association for Artificial Intelligence (AAAI)}", year="2018", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC