The Generalizability of FOND Solutions in Uncertain Environments


Logical regression has proven to be a powerful mechanism for computing compact solutions to non-deterministic planning problems. However, the impact on the generality of the generated solutions has thus far been largely unstudied. We analyze the compact solutions produced by a leading FOND planner, PRP, and develop a logical encoding that represents all possible states that the policy can handle. Through the use of a #-SAT solver, we count the number of models that satisfy the logical encoding (corresponding precisely to the states the policy is able to handle). We analyze the solution representation on seven standard FOND benchmarks and compare the generality of these policies to the reachable state space of the policy applied to the problem’s initial state. Our work can be seen as a generalization of similar studies for deterministic planning domains and clearly demonstrates the broad generalizability of these compact representations.

Workshop on Integrated Acting, Planning and Execution