Path: utzoo!utgpu!attcan!uunet!lll-winken!ames!haven!aplcen!jhunix!apl_aimh
From: apl_aimh@jhunix.HCF.JHU.EDU (Marty Hall)
Newsgroups: comp.ai
Subject: Re: Searching for graph searching
Message-ID: <598@jhunix.HCF.JHU.EDU>
Date: 27 Jan 89 13:29:57 GMT
References: <2070025@otter.hpl.hp.com>
Reply-To: apl_aimh@jhunix.UUCP (Marty Hall)
Organization: AAI Corp AI Lab, JHU P/T CS Faculty
Lines: 30

In <2070025@otter.hpl.hp.com> ijd@otter.hpl.hp.com (Ian Dickinson) writes:
>
>Does anyone know of an overview, anthology or bibliography of _current_ 
>[heuristically guided] graph searching techniques or algorithms?  Ie, I 
>am more interested in the results of recent research than techniques like
>A*, though modifications to that algorithm might be interesting.  Of
>particular interest would be algorithms for locating solutions comprising
>a set of nodes, rather than a single node.

My favorite overview of search is "Search: A Survey of Recent Results" by
Richard Korf of UCLA.  It appears in Shrobe, Howard, ed, _Exploring Artificial
Intelligence_, Morgan Kaufmann, 1988, pp 197-238.  It is basically
the survey talk Dr. Korf gave at last summer's AAAI meeting.  Several
extensions to A* are discussed, especially an Iterative-Deepening
version, IDA* (which is not all that new) and Real-Time A* (RTA*), which
as far as I recall, was first presented at the Seattle AAAI.

If you can't find this book, a very similar paper by Korf is Chapter 7, 
"Optimal Path Finding Algorithms" in Kanal & Kumar, eds, _Search in
Artificial Intelligence_, Springer-Verlag, 1988.  This book has
the advantage of several other good chapters on recent results in
search, although the Shrobe book has several other terrific survey
talks from AAAI, just not on search.  Enjoy!

				- Marty Hall

apl_aimh@jhunix.hcf.jhu.edu   Artificial Intelligence Laboratory, MS 100/601
...uunet!jhunix!apl_aimh      AAI Corporation
apl_aimh@jhunix.bitnet        PO Box 126
(301) 683-6455                Hunt Valley, MD  21030