Complexity of planning with partial observability
Jussi Rintanen · 2004
We show that for conditional planning with partial observability the existence problem of plans with success probability 1 is 2-EXP-complete. This result completes the complexity picture for non-probabilistic propositional planning. We also give new more direct...