Heuristic search through islands

Abstract

A heuristic search strategy via islands is suggested to significantly decrease the number of nodes expanded. Algorithm I, which searches through a set of island nodes ("island set"), is presented assuming that the island set contains at least one node on an optimal cost path. This algorithm is shown to be admissible and expands no more nodes than A*. For cases where the island set does not contain an optimal cost path (or any path). Algorithm I', a modification of Algorithm I, is suggested. This algorithm ensures a suboptimal cost path (which may be optimal) and in extreme cases falls back to A*.