Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!sri-spam!ames!ucbcad!ucbvax!C.CS.CMU.EDU!THOMASON
From: THOMASON@C.CS.CMU.EDU (Rich Thomason)
Newsgroups: mod.ai
Subject: Seminar - Search Algorithms (CMU)
Message-ID: <8703160619.AA13019@ucbvax.Berkeley.EDU>
Date: Thu, 12-Mar-87 07:17:00 EST
Article-I.D.: ucbvax.8703160619.AA13019
Posted: Thu Mar 12 07:17:00 1987
Date-Received: Mon, 16-Mar-87 06:41:34 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: world
Organization: The ARPA Internet
Lines: 41
Approved: ailist@sri-stripe.arpa


		COMPUTER SCIENCE COLLOQUIUM   PITT/CMU

SPEAKER:    David Mutchler (Naval Research Laboratory)

TITLE:	    What Search Algorithm Gives Optimal Average-Case Performance
	    When Search Resources Are Highly Limited?

DATE:       March 13, 1987
TIME:       1:00 - 2:00 P.M.
PLACE:      228 Alumni Hall, University of Pittsburgh

      Searching the state-space for an acceptable solution is a
fundamental activity for many AI programs.  Complete search of the
state-space is typically infeasible.  Instead, one relies on whatever
heuristic information is available.  Here is one interesting question
that then arises:  Given n search resources, how can one dynamically
utilize those resources to achieve (on average) as good a solution as
possible?

In this talk, I will:

	(1)  present a probabilistic model in which to study this
	     question; 

	(2)  state two theorems that together answer the above
	     question in the context of that model;

	(3)  explain how branching processes and branching random
	     walks are used to prove the theorems.

      Here is a brief description of the model I will be using.  A
least-cost root-to-leaf path is sought in a random tree.  The tree is
known to be binary and complete to depth N.  Arc costs are
independently set either to 1 (with probability p) or to 0 (with
probability 1-p).  The cost of a leaf is the sum of the arc costs on
the path from the root to that leaf.  The searcher (scout) can learn
n arc values; after having done so, a leaf must be selected.  It is
easy to see how the leaf should be chosen.  The interesting question
is that:  how should the scout dynamically allocated the n search
resources to minimize the average cost of the leaf selected?