Stackelberg planning is a recently introduced single-turn two-player adversarial planning model, where two players are acting in a joint classical planning task, the objective of the first player being hampering the second player from achieving its goal. This places the Stackelberg planning problem somewhere between classical planning and general combinatorial two-player games. But, where exactly? All investigations of Stackelberg planning so far focused on practical aspects. We close this gap by conducting the first theoretical complexity analysis of Stackelberg planning. We show that in general Stackelberg planning is actually no harder than classical planning. Under a polynomial plan-length restriction, however, Stackelberg planning is a level higher up in the polynomial complexity hierarchy, suggesting that compilations into classical planning come with a worst-case exponential plan-length increase. In attempts to identify tractable fragments, we further study its complexity under various planning task restrictions, showing that Stackelberg planning remains intractable where classical planning is not. We finally inspect the complexity of meta-operator verification, a problem that has been recently connected to Stackelberg planning.

Stackelberg计划是一个最近引入的单回合两个玩家对抗性规划模型，目标是第一个玩家阻碍第二个玩家实现目标。这个问题位于古典规划和组合式两个玩家游戏之间。通过对Stackelberg计划的第一个理论复杂性分析，我们发现通常情况下Stackelberg计划实际上并不比古典规划更难。然而，在多项式规划长度限制下，Stackelberg计划与多项式复杂性等级稍高，暗示着编译成古典规划可能导致最坏情况下指数级的规划长度增加。为了寻找可处理的片段，我们进一步研究了在各种规划任务限制下的复杂性，发现Stackelberg计划仍然难以处理，而古典规划则不是。最后，我们检查了最近与Stackelberg计划相关的元操作验证的复杂性。

关于Stackelberg规划和元操作验证的计算复杂性研究：技术报告