Dynamic Potential Search on Weighted Graphs

Authors

  • Daniel Gilon Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Roni Stern Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v8i1.18436

Abstract

Dynamic Potential Search (DPS) is a recently introduced search algorithm that returns a bounded-suboptimal cost solution. DPS orders nodes in the open-list based on their potential which is a combination of both the g- and h-values of a node. In this paper we study the behavior of DPS on weighted graphs. In particular, we develop a new variant of DPS, called DPSU which calculates the potential by counting one for each edge regardless of its costs. We develop an eager version and a restrained version of DPSU. We then compare all these algorithms on a number of weighted graphs and study the pros and cons of each of them.

Downloads

Published

2021-09-01