Abstract
We present the Goal Uncertain Stochastic Shortest Path (GUSSP) problem --- ageneral framework to model stochastic environments with goal uncertainty. Themodel is an extension of the stochastic shortest path (SSP) framework todynamic environments in which it is impossible to determine the exact goalstates ahead of plan execution. GUSSPs introduce flexibility in goalspecification by allowing a belief over possible goal configurations. Thepartial observability is restricted to goals, facilitating the reduction to anSSP. We formally define a GUSSP and discuss its theoretical properties. We thenpropose an admissible heuristic that reduces the planning time of FLARES --- astart-of-the-art probabilistic planner. We also propose a determinizationapproach for solving this class of problems. Finally, we present empiricalresults using a mobile robot and three other problem domains.