Abstract:
Heuristic search provides a principled way to guide exploration in large state spaces, enabling efficient solution finding. As a result, it is widely used across domains such as robotics, games, and planning. However, its performance is often limited by memory consumption and computational overhead, which have motivated extensive research on improving both. This thesis introduces a sparse representation called attractors and explores two of its applications in heuristic search. First, we present Attractor-based Closed List Search (ACLS), a framework that uses attractors to sparsely represent the Closed list. ACLS intelligently identifies attractor states in a way that enables efficient solution reconstruction while preserving theoretical guarantees on the quality of the solution. We demonstrate that ACLS significantly reduces memory usage, while achieving comparable planning times and outperforming state-of-the-art approaches. Second, we introduce front-to-attractors (F2A) heuristics, a family of heuristics that leverage attractors in bidirectional heuristic search (Bi-HS). We demonstrate that F2A heuristics substantially reduce the number of heuristic evaluations compared to front-to-front (F2F) heuristics, while maintaining strong informativeness and reducing expansions relative to front-to-end (F2E) heuristics, resulting in improved runtime performance. Together, these projects demonstrate the broad potential of attractors in heuristic search.

Committee:
Maxim Likhachev (chair)
Jiaoyang Li
Yorai Shaoul