Assessing heuristic searches-artificial intelligence, Computer Engineering

Assessing Heuristic Searches

Given a specific problem you want to create an agent to solve, there can be more than one way of specifying it as a search problem, more than one option for the search strategy and different possibilities for heuristic measures. To a large extent, it is hard to predict what the best option will be, and it will require some experimentation to find out them. In some kind of cases, - if we calculate the effective branching rate, as described below - we may tell for sure if one heuristic measure is always being out-performed by another.

The Effective Branching Rate

Assessing heuristic functions is an essential part of Artificial Intelligence research: a specific heuristic function can sound like a good idea, but in practice give no discernible increase in the quality of the search. Search quality may be determined experimentally  in  terms  of  the  output  from  the  search,  and  by  using  sevral measures likewise  the effective branching rate. Imagine  a specific  problem P has been solved by search strategy S by expanding N nodes, and the solution lay at depth D in the space. Then the effective branching value of S for P is calculated by comparing S to a uniform search U. An example of a uniform search is a breadth first search where many branches from any node are always the same (as in our baby naming example). We then suppose the (uniform) branching rate of U is like  that, on exhausting its search to depth D, it too would have expanded defiantly N nodes. This imagined branching rate, written b*, is the effective branching rate of S and is calculated thus:

N = 1 + b* + (b*)2 + ... + (b*)D.

Rearranging this equation will give a value for b*. For an example (taken from  Norvig and Russell )imagine S finds a solution at depth 5 having expanded 52 nodes. In this type of case:

 52 = 1 + b* + (b*)2 + ... + (b*)5.

and it turns out that b*=1.91. To calculate its value , we use the well known mathematical identity:

 

This make us enables to write a polynomial for which b* is a 0, and we may solve this using numerical techniques such as Newton's method.

581_Assessing Heuristic Searches.png 
It is typically the case that the effective branching rate of a search strategy is same  over all the problems it is used for, because of this it is suitable to average b* over a small set of problems to give a valid account. If a heuristic search has a branching rate near to 1, then it is a good sign.  We say that 1 heuristic function  h1 dominates another h2 if the search using h1 always has a lower effective branching rate than h2. Having a lower effective branching rate is obviously desirable because it means a quicker search.

Posted Date: 10/2/2012 3:01:37 AM | Location : United States







Related Discussions:- Assessing heuristic searches-artificial intelligence, Assignment Help, Ask Question on Assessing heuristic searches-artificial intelligence, Get Answer, Expert's Help, Assessing heuristic searches-artificial intelligence Discussions

Write discussion on Assessing heuristic searches-artificial intelligence
Your posts are moderated
Related Questions
What is Instruction Cycle A program residing in the memory unit of the computer having of a sequence of instructions.  The program is implemented in the computer by going throu

The following are just a few return types of a controller action process. In common an action process can return an instance of an any class that derives from Action Result class.

Obstacles to IS implementation While information systems are now becoming the norm in most organisations the journey to this point has been a difficult one. Even in the 21st c

What is MASK OPERATION The mask operation is similar to selective-clear operation except which the bits of Aare cleared only where there are corresponding 0's in register B. th

Syntax of recursion int fib(int num) /* Fibonacci value of a number */ {      switch(num) { case 0: return(0); break; case 1: return(1); break; default:  /* Incl

Windows Authentication This provider utilizes the authentication capabilities of IIS. After IIS completes its authentication, ASP.NET uses the authenticated identity's token to

What is Cursor? Cursor is a database object used by applications to manipulate data in a set on a row-by- row basis, instead of the typical SQL commands that operate on all the

Explain dynamic server creation briefly. Dynamic Server Creation: If only one server handles one request at a time, each client should wait while the server fulfils the on

Problem: (a) Cellular systems are based on two types of multiplexing, what are those two types of multiplexing? Describe how they are used to improve channel allocation in cel

How different are interface and abstract class in .Net? Abstract classes cannot be instantiated it can have or can't have abstract method basically known as must inherit as th