Faster Stackelberg Planning via Symbolic Search and Information Sharing

Álvaro Torralba, Patrick Speicher, Robert Künnemann, Marcel Steinmetz, Jörg HoffmannAAAI 2021 · DOI

Introduction

Stackelberg planning is a powerful framework for modeling "leader-follower" scenarios, where a leader acts first and a follower responds optimally. This paradigm is essential for applications in cybersecurity, such as a network administrator (leader) deploying defenses to thwart an attacker (follower), and infrastructure robustness. However, solving these problems is computationally grueling because the leader must account for the follower's optimal response to every possible action sequence.

The Computational Bottleneck

The primary challenge in Stackelberg planning is the search space explosion. For every potential leader plan, a complete, cost-optimal planning problem must be solved for the follower. Previous state-of-the-art approaches, such as Iterative Deepening Search (IDS), treated each follower subtask as an independent problem. This leads to massive amounts of redundant computation, as many leader plans result in similar follower environments.

Symbolic Leader Search (SLS)

To address these inefficiencies, this research introduces Symbolic Leader Search (SLS). SLS shifts the paradigm from explicit state exploration to symbolic search, emphasizing the "recycling" of information across subtasks.

Key Methodological Components

  1. Symbolic Representation with BDDs: SLS uses Binary Decision Diagrams (BDDs) to represent sets of leader states. This allows the algorithm to process exponentially many states simultaneously in a compressed format.
  2. Information Sharing via Regression: When a follower plan is identified for one subtask, SLS employs regression to find all other leader states where that same plan remains valid. This enables the solver to prune large portions of the search space without invoking the follower sub-solver.
  3. Cost-Bounded Solvers: A critical insight is that an optimal follower solution is only necessary for leader plans that might end up on the Pareto front. For others, a "good enough" suboptimal plan—found using fast heuristics like FF—is sufficient to prove a leader action is non-optimal.
The SLS architecture integrates symbolic search with various heuristics to compute bounds and plans, facilitating information sharing across subtasks.

Evaluation and Datasets

The SLS approach was evaluated across three benchmark sets:

  • OLD: Standard benchmarks from previous literature.
  • NEW: A more challenging set with larger action spaces and complex maps designed to test scalability.
  • NET: A "net-benefit" version of the NEW set, where followers maximize utility minus action costs, modeling more realistic attacker behavior.

Key Results and Insights

The symbolic approach demonstrated significant performance gains over existing methods. In tasks with complex Pareto fronts (three or more entries), the version of SLS with upper-bound sharing (SLS-ub) often outperformed baselines by more than an order of magnitude in total runtime.

Comparison of optimal sub-solver calls between SLS-ub-II+-FF and the baseline IDS.

As shown in the figure above, SLS-ub-II+-FF drastically reduces the number of optimal sub-solver calls compared to the IDS baseline. This reduction is the primary driver of the observed speedups. Furthermore, SLS solved up to 786 instances on the "NEW" dataset, compared to only 601 by IDS, showcasing superior coverage and robustness.

Conclusion and Future Work

Symbolic Leader Search represents a major step forward in making Stackelberg planning practical for large-scale problems. By leveraging BDDs for state compression and regression for information sharing, SLS avoids the redundant work that plagued previous explicit search methods. Future research will focus on optimizing BDD variable ordering to prevent memory explosion and exploring more advanced symbolic heuristics for multi-agent planning scenarios.

Summary updated

BibTeX
@inproceedings{torralba2021faster,
  author = {Álvaro Torralba and Patrick Speicher and Robert Künnemann and Marcel Steinmetz and Jörg Hoffmann},
  title = {{Faster Stackelberg Planning via Symbolic Search and Information Sharing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17425},
}
Figure