Unifying single-agent and two-player search

The seminal works of Nilsson and Pearl in the 1970s and early 1980s provide a formal basis for splitting the field of heuristic search into two subfie lds: single-agent and two-agent search. The subfields are studied in relati ve isolation from each other; each having its own distinct character. Despi te the separation, a close inspection of the research shows that the two ar eas have actually been converging. This paper argues that the single/two-ag ent distinction is no longer of central importance for heuristic search any more. The state space is characterized by a number of key properties that a re defined by the application; single-agent versus two-agent is just one of many. Both subfields have developed many search enhancements: they are sho wn to be surprisingly similar and general. Given their importance for creat ing high-performance search applications, it is these enhancements that for m the essence of our field. Focusing on their generality emphasizes the opp ortunity for reuse of the enhancements, allows the field of heuristic searc h to be redefined as a single unified field, and points the way towards a m odern theory of search based on the taxonomy proposed here. (C) 2001 Elsevi er Science Inc. All rights reserved.