Planning in Stochastic Environments with Goal Uncertainty
This work addresses planning under goal uncertainty for robotics and AI applications, but it is incremental as it extends existing stochastic shortest path models.
The authors tackled the problem of path planning in stochastic environments where the exact goal is unknown beforehand, by introducing the Goal Uncertain Stochastic Shortest Path (GUSSP) framework, which reduces planning time using an admissible heuristic and determinization approach, achieving empirical results in simulation and on a mobile robot.
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.