Reading list for CMPUT 651 -- Single-Agent Search

Heuristic Search - general

R. Korf (2003), "Delayed Duplicate Detection: Extended abstract", International Joint Conference on Artificial Intelligence (IJCAI'03)", pp. 1539-1541.
R. Korf and W. Zhang (2000), "Divide-and-Conquer Frontier Search Applied to Optimal Sequence Alignment", National Conference on Artificial Intelligence (AAAI'00), pp. 910-916.
R. Korf (1999), "Divide-and-Conquer Bidirectional Search: First Results", International Joint Conference on Artificial Intelligence (IJCAI'99), pp. 1184-1189.
(this is where RBFS first appeared)
Linear-space best-first search. R. E. Korf, Artificial Intelligence, 62(1):41-78, 1993.
Depth-first iterative deepening: An optimal admissible tree search. R. E. Korf, Artificial Intelligence, 27:97-109, 1985.
Search algorithms under different kinds of heuristics -- a comparative study. A. Bagchi and A. Mahanti, Journal of the ACM, 30(1):1-21, January 1983
Time Complexity of Iterative Deepening A*, Richard E. Korf, Michael Reid, and Stefan Edelkamp, Artificial Intelligence 129 (June 2001) pp. 199-218.
Performance of linear-space search algorithms, Weixiong Zhang and Richard E. Korf, Artificial Intelligence, 79(2), 1995, pp.241-292.

Stuart Russell, ``Efficient Memory-Bounded Search Methods.'' In Proceedings of the Tenth European Conference on Artificial Intelligence, Vienna: Wiley, 1992. (SMA*)
A. Reinefeld and T.A. Marsland, Enhanced Iterative-Deepening Search, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), volume 16, number 7, July 1994, pp. 701-710.
H. Kaindl, G. Kainz, A. Leeb, and H. Smetana, How to use limited memory in heuristic search, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, Aug. 1995.

Multiple Pattern Databases Proc. ICAPS'04.
co-authors: Jack Newton, Ariel Felner, Ram Meshulam, David Furcy
Additive Pattern Database Heuristics Ariel Felner, Richard E. Korf, and Sarit Hanan, JAIR, Vol. 22, pp. 289-318, November 2004.
Pattern Databases Joseph C. Culberson and Jonathan Schaeffer, Computational Intelligence, Vol. 14, No. 4, pp. 318-334, 1998.
Steps Towards the Automatic Creation of Search Heuristics, Robert C. Holte and Istvan Hernadvolgyi, technical report TR04-02, Computing Science Department, University of Alberta, 2004 (original manuscript: November, 2001).
A Space-Time Tradeoff for Memory-Based Heuristics Proc. AAAI'99, pp.704-709.
co-author: Istvan T. Hernadvolgyi
Hierarchical A*: Searching Abstraction Hierarchies Efficiently , technical report tr-95-18. pre-publication version of: AAAI'96, pp.530-535.

Bidirectional Heuristic Search Reconsidered, H. Kaindl and G. Kainz, Journal of Artificial Intelligence Research (JAIR), Volume 7, pages 283-317, 1997.
G. Manzini, BIDA*: An improved perimeter search algorithm, Artificial Intelligence, Vol. 75, No. 2, June 1995, pp. 347-360.
A Fast Algorithm for Finding Better Routes by AI Search Techniques T. Ikeda, Min-Yao Hsu, H. Imai, S. Nishimura, H. Shimoura, T. Hashimoto, K. Tenmoku, and K. Mitoh. In Proc. Vehicle Navigation and Information Systems Conference. IEEE, 1994.
This paper is the first I know to show that A* is simply Dijkstra's algorithm with the heuristic values folded into the graph's edge weights. It is a rare example of bidirectional A* outperforming unidirectional A* (but by less than a factor of 2). It argues that the routes found by bidirectional A* are better.

Speeding Up Problem-Solving by Abstraction: A Graph-Oriented Approach pre-publication version of: Artificial Intelligence, vol.85, pp.321-361.
The Tradeoff Between Speed and Optimality in Hierarchical Search, technical report tr-95-19.
Searching for Macro-operators with Automatically Generated Heuristics I. Hernádvölgyi, Proceedings of the 14th Canadian Conference on Artificial Intelligence (AI 2001), pp. 194-203.