A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search

摘要: In the past few years, new very successful bidirectional heuristic search algorithms have been proposed. Their key novelty is a lower bound on cost of solution that includes information from g values in both directions. Kaindl and Kainz (1997) proposed measuring how inaccurate while expanding nodes opposite direction, using this to raise f value evaluated nodes. However, comes with set disadvantages remains yet be exploited its full potential. Additionally, Sadhukhan (2013) presented BAE∗, best-first algorithm based accumulated inaccuracy along path. no complete comparison regards other has done, neither theoretical nor empirical. paper we define individual bounds within lower-bound framework show Kainz's Sadhukhan's methods can generalized thus creating bounds. This overcomes previous shortcomings allows newer benefit these techniques as well. Experimental results substantial improvement, up an order magnitude number necessarily-expanded compared state-of-the-art near-optimal common benchmarks.