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

Zakary Littlefield, Dimitri Klimenko, Hanna Kurniawati, Kostas E. Bekris

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Scopus citations


Many methods for planning under uncertainty operate in the belief space, i.e., the set of probability 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 is a more suitable metric than the commonly used and Kullback–Leibler 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 effectiveness of different distance functions become quite prominent. In fact, in state spaces with more than 4 dimensions, by just replacing distance with, 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 use a smaller number of samples to generate policies with similar qualities, compared to those with. This paper also shows that carries the Lipschitz continuity of the state’s cost function to Lipschitz continuity of the expected cost of the beliefs. Such a continuity property is often critical for convergence to optimal solutions.

Original languageEnglish (US)
Title of host publicationSpringer Proceedings in Advanced Robotics
PublisherSpringer Science and Business Media B.V.
Number of pages18
StatePublished - 2018
Externally publishedYes

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Mechanical Engineering
  • Engineering (miscellaneous)
  • Artificial Intelligence
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'The Importance of a Suitable Distance Function in Belief-Space Planning'. Together they form a unique fingerprint.

Cite this