The Importance of a Suitable Distance Function in Belief-Space Planning

TitleThe Importance of a Suitable Distance Function in Belief-Space Planning
Publication TypeConference Paper
Year of Publication2015
AuthorsLittlefield, Z, Klimenko, D, Kurniawati, H, Bekris, KE
Conference NameInternational Symposium on Robotic Research (ISRR)
Date Published09/2015
Conference LocationSestri Levante, Italy

Many methods for planning under uncertainty operate in the belief space, i.e., the set of distributions over states. Although the problem is computationally hard, recent advances have shown that belief-space planning is becoming practical for many medium size problems. Some of the most successful methods utilize sampling and often rely on distances between beliefs to partially guide the search process. This paper deals with the question of what is a suitable distance function for belief space planning, which despite its importance remains unanswered. This work indicates that the rarely used Wasserstein distance (also known as Earth Mover’s Distance (EMD)) is a more suitable metric than the commonly used L1 and Kullback-Leibler (KL) for belief-space planning. Simulation results on Non-Observable Markov Decision Problems, i.e., the simplest class of belief-space planning, indicate that as the problem becomes more complex, the differences on the ef- fectiveness of different distance functions become quite prominent. In fact, in state spaces with more than 4 dimensions, by just replacing L1 or KL distance with EMD, the problems become from virtually unsolvable to solvable within a reasonable time frame. Furthermore, preliminary results on Partially Observable Markov Decision Processes indicate that point-based solvers with EMD use a smaller number of samples to generate policies with similar qualities, compared to those with L1 and KL. This paper also shows that EMD caries the Lipschitz continuity of the cost of the states to Lipschitz continuity of the expected cost of the beliefs. Such a continuity property is often critical for convergence to optimal solutions.