Probability propagation for path planning in unknown environments

We propose a probability propagation framework for path planning on discrete grids where an agent can navigate in an unknown environment to discover new areas and goals. We introduce a technique in which the probabilistic backward flow provides guidance towards discovering multiple distributed goals and hidden regions. This is achieved using a maximum likelihood path estimation framework in which the hidden areas become constrained goals that “attract” the agent. Simulations on various grids are included in the paper. The results show how this idea, applied to a completely unknown environment and goal position, may provide a unifying and powerful method for distributed dynamic path planning. • It is shown how the probability flow can provide an effective and general technique to guide the agent’s progressive discovery of initially hidden areas and goals. • This feature, to our knowledge, has never been included in MDP path planning algorithms. • The backward flow is also surprisingly effective in autonomously detecting multiple distributed goals. • Moreover, this technique reveals intriguing common features to some of those proposed in the literature, suggesting that the probability propagation framework may provide a unifying and powerful method for distributed dynamic decision-making in uncertain environments.