Utilizing Landmarks in Euclidean Heuristics for Optimal Planning

An important problem in AI is to construct high-quality heuristics for optimal search. Recently, the Euclidean heuristic (EH) has been proposed, which embeds a state space graph into a Euclidean space and uses Euclidean distances as approximations for the graph distances. The embedding process leverages recent research results from manifold learning, a subfield in machine learning, and guarantees that the heuristic is provably admissible and consistent. EH has shown good performance and memory efficiency in comparison to other existing heuristics. Our recent works have further improved the scalability and quality of EH. In this short paper, we present our latest progress on applying EH to problems in planning formalisms, which provide richer semantics than the simple state-space graph model. In particular, we improve EH by exploiting the landmark structure derived from the SAS+ planning formalism.