Computing Planning Width: How Hard Is It, Really?

Abstract

The width of a classical planning instance, among other metrics, indicates the computational difficulty of solving the instance. However, no result exists on the complexity of computing the width itself. In this paper, we address this open problem by considering two versions: non-parameterised and parameterised. In the non-parameterised version, a positive integer is given as an input along a classical planning instance, and it is PSPACE-complete to decide if this number is an upper bound of the instance's width. In the parameterised version, it is coNP-complete to decide if the width is no greater than the fixed parameter. These tight results resolve the long standing question of how hard it is to compute the width of planning instances, and call for further research on width approximations, generalisation of width computation over multiple instances and islands of tractability.