Joint and LPA*: Combination of Approximation and Search

Daniel Ratner, Ira Pohl

This paper describes two new algorithms, Joint and LPA*, which can be used to solve difficult combinatorial problems heuristically. The algorithms find reasonably short solution paths and are very fast. The algorithms work in polynomial time in the length of the solution. The algorithms have been benchmarked on the 15-puzzle, whose generalization has recently been shown to be NP hard, and outperform other known methods within this context.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.