Planning in Stochastic Environments with Goal Uncertainty
  We present the Goal Uncertain Stochastic Shortest Path (GUSSP) problem -- a
general framework to model path planning and decision making in stochastic
environments with goal uncertainty. The framework extends the stochastic
shortest path (SSP) model to dynamic environments in which it is impossible to
determine the exact goal states ahead of plan execution. GUSSPs introduce
flexibility in goal specification by allowing a belief over possible goal
configurations. The unique observations at potential goals helps the agent
identify the true goal during plan execution. The partial observability is
restricted to goals, facilitating the reduction to an SSP with a modified state
space. We formally define a GUSSP and discuss its theoretical properties. We
then propose an admissible heuristic that reduces the planning time using
FLARES -- a start-of-the-art probabilistic planner. We also propose a
determinization approach for solving this class of problems. Finally, we
present empirical results on a search and rescue mobile robot and three other
problem domains in simulation.
