Planning with Uncertainty in Position: an Optimal and Efficient Planner

Abstract — We introduce a resolution-optimal path planner that considers uncertainty while optimizing any monotonic objective function such as mobility cost, risk, or energy expended. The resulting path minimizes the expected cost of the objective function, while ensuring that the uncertainty in the position of the robot does not compromise the safety of the robot or the reachability of the goal. Although the problem domain is stochastic in nature, our algorithm takes advantage of deterministic path-planning techniques to achieve significant performance improvements. Index Terms- path planning, uncertainty, optimal planner, error propagation, mobile robot. I