are  used  to  improve  the  eﬃciency  by  exploiting  structure  in  the  instance.  In  some  cases,  the  state  spaces  are  so  large 
that disk-based search is necessary [69]. From a complexity point of view, planning is known to be PSPACE-complete both 
for variables with binary domains [17] and for variables with arbitrary ﬁnite domain [11]. Length-optimal planning is also 
known to be W[2]-complete under parameterised analysis, using plan length as parameter [8].
A-framework-for-analysing-state-abstraction-metho_2022_Artificial-Intelligen