Recently, a number of research groups have developed rational techniques, by which I mean ones based on decision theoretic principles, that answer one or both of these questions. These researchers have argued convincingly that their rational approaches improve on the non-decision-theoretic techniques previously used for partial state-space search.
In this paper, I will survey work in this area by researchers such Hansson & Mayer, Russell & Wefald, and Baum & Smith, with an emphasis on the latter, since it subsumes much of the earlier work. I will conclude with some speculations on how to apply the principles learned from rational state-space search to do abstract reasoning that transcends the state-space paradigm.
@UNPUBLISHED{Frank-93a,
AUTHOR = {Michael P. Frank},
TITLE = {Rational partial state-graph search},
NOTE = {draft report},
MONTH = may,
YEAR = {1993},
url = {http://www.ai.mit.edu/~mpf/ftp/term-paper.ps}
annote = {Term paper for Rationality and Intelligence, Jon Doyle}
}