On the Properties of All-Pair Heuristics

Abstract

While most work in heuristic search concentrates on goal-specific heuristics, which estimate the shortest path cost from any state to the goal, we explore all-pair heuristics that estimate distances between all pairs of states. We examine the relationship between these heuristic functions and the shortest distance function they estimate, revealing that all-pair consistent heuristics may violate the triangle inequality. Thus, we introduce a new property for heuristics called Δ-consistency, requiring adherence to the triangle inequality. Additionally, we present a method for transforming standard consistent heuristics to be Δ-consistent, showcasing its benefits through a synthetic example. We then show that common heuristic families inherently exhibit Δ-consistency. This positive finding encourages the use of all-pair consistent heuristics, and prompts further investigation into the optimality of A*, when given an all-pair heuristic instead of a goal-specific heuristic.