Path Planning of Mobile Robots Considering Position Uncertainty and Cost of Observation

Abstract

This paper addresses movement and observation planning for mobile robots under position uncertainty. A sequence of actions that minimizes the total time needed for reaching a destination while guaranteeing that the collision probability is less than a prescribed threshold is planned. The problem is formulated as a path planning problem on a roadmap with additional constraints on covariance matrices expressing position uncertainty, for which a novel branch-and-bound based solution is presented. Moreover, a heuristic technique for creating a roadmap based on a new criterion that encapsulates both collision safety and localization ability is proposed. Simulation study is performed to evaluate computational complexity and relations between some characteristic parameters and obtained solutions.