Optimization for Heuristic Search
Saved in:
| Title: | Optimization for Heuristic Search |
|---|---|
| Authors: | Rayner, David Christopher Ferguson |
| Advisors: | Sturtevant, Nathan (Computer Science at University of Denver), Bowling, Michael (Computing Science) |
| Summary: | Abstract: Heuristic search is a central problem in artificial intelligence. Among its defining properties is the use of a heuristic, a scalar function mapping pairs of states to an estimate of the actual distance between them. Accurate heuristics are generally correlated with faster query resolution and higher-quality solutions in a variety of settings, including GPS road navigation and video game pathfinding. Effective methods for defining heuristics remain at the forefront of heuristic search research. This research puts the task of constructing good heuristics under the lens of optimization: minimizing a loss between the true distances and the heuristic estimates, subject to admissibility and consistency constraints. Starting with first principles and well-motivated loss functions, we show several instances where performing this optimization is both feasible and tractable. This novel approach reveals previously unobserved connections to other computing subfields (e.g., graph embedding), gives new insights into previous approaches to heuristic construction (e.g., differential heuristics), and proves empirically competitive in a number of domains. |
| URL: | https://era.library.ualberta.ca/items/57ecc087-1494-41b0-aa98-8f3bedcaa25f/view/dc00ad0c-3400-495a-b2c1-94f4abf1dcc7/Rayner_David_CF_201412_PhD.pdf |
| Database: | OpenDissertations |
| Abstract: | Abstract: Heuristic search is a central problem in artificial intelligence. Among its defining properties is the use of a heuristic, a scalar function mapping pairs of states to an estimate of the actual distance between them. Accurate heuristics are generally correlated with faster query resolution and higher-quality solutions in a variety of settings, including GPS road navigation and video game pathfinding. Effective methods for defining heuristics remain at the forefront of heuristic search research. This research puts the task of constructing good heuristics under the lens of optimization: minimizing a loss between the true distances and the heuristic estimates, subject to admissibility and consistency constraints. Starting with first principles and well-motivated loss functions, we show several instances where performing this optimization is both feasible and tractable. This novel approach reveals previously unobserved connections to other computing subfields (e.g., graph embedding), gives new insights into previous approaches to heuristic construction (e.g., differential heuristics), and proves empirically competitive in a number of domains. |
|---|
