In this thesis, we study theoretically and empirically the additive abstraction-based heuristics. First we present formal general definitions for abstractions that extend to general additive abstractions. We show that the general definition makes proofs of admissibility, consistency, and additivity easier, by proving that several previous methods for defining abstractions and additivity satisfy three imple
conditions. Then we investigate two general methods for defining additive abstractions and run experiments to determine the effectiveness of these methods for two benchmark state spaces: TopSpin and the Pancake puzzle. Third, we propose that the accuracy of the heuristics generated by abstraction can be improved by checking for infeasibility. The theory and experiments demonstrate the approach to detect infeasibility and the application of this technique to different domains. Finally, we explore the applications of additive abstraction-based heuristics in two state spaces with nonuniform edge costs: the Sequential Ordering Problem (SOP) and the weighted Pancake puzzle. We formalize a novel way of generating additive and non-additive heuristics for these state spaces. Furthermore,
we investigate the key concepts to generate good additive and non-additive abstractions. Experiments show that compared to some simple alternative heuristics, well chosen abstractions can enhance the quality of suboptimal solutions for large SOP instances and reduce search time for the weighted Pancake problems.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/1749 |
| Date | 06 1900 |
| Creators | Yang, Fan |
| Contributors | Culberson, Joseph (Computing Science), Holte, Robert (Computing Science), Schaeffer, Jonathan (Computing Science), Buro, Michael (Computing Science), Gannon, Terry (Mathematical Sciences), Hansen, Eric (Computer Science and Engineering, Mississippi State University) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1091204 bytes, application/pdf |
| Relation | Yang, Fan (2008) Journal of Artificial Intelligence (JAIR), volume 32, pp. 631-662. http://www.jair.org/papers/paper2486.html |
Page generated in 0.0016 seconds