A new path planning algorithm with uncertainty information of robot´s initial position

The task of path planning has attracted considerable attentions over decades. Most path planning research was focused on the property of environment, which is either static or dynamic, and many accomplishments have been achieved. However, less attention has been paid to the uncertainty of robot location. Previous research works always assume the position of robot to be a certain point, which is a waste of information. Actually, many localization algorithms suggest that robots knowledge of its location is a probability distribution over many points. Partial Observable Markov Decision Process(POMDP) provides a framework to handle uncertainty in planing. In this paper we propose a new path planning algorithm, which is called M* to find an admissible and optimal path for moving robots with the initial position of the robot be uncertain. By using the Monte Carlo method and considering in high dimensionality, we transform this problem into a more neat form and make A* applicable.