Temporal Logic Path Planning under Localization Uncertainty

Abstract

We present a method to find the optimal control strategy for a robot using prior information of localization that maximizes the probability of satisfaction of a temporal logic specification while considering the uncertainty in both motion and sensing, two major causes for localization uncertainty. The specifications are given in the probabilistic computation tree logic (PCTL) formulae over a set of propositions, which capture the presence of the robot in some key locations in the environment. A computation model that can deal with the uncertainty in both motion and sensing is the Partially Observable Markov Decision Process (POMDP), which is computationally expensive. We approximate the underlying POMDP using Augmented Markov Decision Process (AMDP) and present a control synthesis algorithm for AMDP. We carry out numerous experiments on workspaces with sizes up to 100 × 100 and three different PCTL specifications to evaluate the efficacy of our technique. Experimental results show that our technique for computing robot control policy using localization prior can deal with localization uncertainty effectively and scale to large environments.