Explaining the Space of SSP Policies via Policy-Property Dependencies: Complexity, Algorithms, and Relation to Multi-Objective Planning.

Stochastic shortest path (SSP) problems are a common frame-work for planning under uncertainty. However, the reactivestructure of their solution policies is typically not easily com-prehensible by an end-user, nor do planners justify the rea-sons behind their choice of a particular policy over others.To strengthen confidence in the planner’s decision-making,recent work in classical planning has introduced a frame-work for explaining to the user the possible solution spacein terms of necessary trade-offs between user-provided planproperties. Here, we extend this framework to SSPs. We in-troduce a notion of policy properties taking into accountaction-outcome uncertainty. We analyze formally the com-putational problem of identifying the exclusion relationshipsbetween policy properties, showing that this problem is in factharder than SSP planning in a complexity theoretical sense.We show that all the relationships can be identified througha series of heuristic searches, which, if ordered in a cleverway, yields an anytime algorithm. Further, we introduce analternative method, which leverages a connection to multi-objective probabilistic planning to move all the computationalburden to a preprocessing step. Finally, we explore empiri-cally the feasibility of the proposed explanation methodologyon a range of adapted IPPC benchmarks