Herself’s Artificial Intelligence

Searches are broken into two main categories; uninformed searches (brute-force, blind), and informed (heuristic, directed) searches. Uninformed searches are done when there is no information about a preferred search path. Informed searches have some information to help pick search paths, usually a rule of thumb is used to reduce the search area. A traveling salesman search going from Boston to Dallas is uninformed if it begins searching randomly, or methodically with no preference. An informed search knows Dallas is South West of Boston, so it begins and concentrates its search in that direction.

Directed graphs (state-space graphs) are used to keep track of possible steps and the state of the world from step-to-step. The edges are used to define steps and the nodes define states of the world. A state space graph has three basic components: A start node; functions that transform a state description representing one state into the representation after an action is taken; and a goal condition. Four main criteria for evaluating search strategies are:
completeness; likelihood of finding a solution if a solution exists
time complexity; (path cost) time to find a solution (Order O(n))
space complexity; amount of memory, ram, needed
optimality; does it find best solution, if several solutions exist?

There are three steps you must take to avoid loops in your search algorithm: Do not return to the state you just came from; Do not create paths with cycles in them; Do not regenerate prior states.

The Breadth First Search first checks all of the nodes directly connected to the start node, then it checks the nodes connected to each of the beginning nodes. In a tree graph it checks the top level, then the second level nodes, and 8 so on. If a solution exists, the Breadth First Search will find it (algorithmic search), and it will find the shallowest solution first.
Breadth First Search: Algorithm
top::
Is it the end of the queue?
true: quit, no solution
false:
Remove first node
Is it the solution node?
true: return node and quit
false: expand node and put children of this node at end of the queue
loop to top:

Depth First (Uniform Cost) Search is similar to the Breadth First Search except it searches minimum cost first rather than level. If the cost is equal on all the levels then it is the same as the Breadth First Search. It will probably find a solution faster than Breath First, if several solutions exist. It may get stuck on dead ends and not find a solution even if a solution exists, so it is not an algorithmic search. It may not find the shallowest or least cost solution, but is uses far less memory than the Breadth First Search. Usually a boundary is placed, a depth bound, so if a solution isn’t found at a certain depth it backs up and tries the next section.

Depth First Search: Algorithm:
top::
Is it the end of the queue?
true: quit, no solution
false:
Remove first node
Is it the solution node?
true: return node and quit
false: expand node and put children of this node at the front of the queue
loop to top:

{ Depth first search is also known as the right hand rule.  Should you ever find yourself kidnapped by aliens and dropped into a maze use the right hand rule.  Place your right hand on a wall.  Follow it where ever it leads you never letting your hand leave the wall.  Eventually you will have traversed the entire maze and therefore find an exit. }

Iterative Deepening only uses the memory of a Depth-First Search, but will find the lowest cost solution if any solution exists. It does a Depth-First Search with a depth-bound of one, then a Depth-First Search with a depth-bound of two, and continues until a solution is found. Constraint Satisfaction Search: Is a search algorithm in which a set of vari ables must meet a set of constraints or conditions rather than meet a goal. (scheduling, for example, and the eight queens problem are examples of this.) There are two main methods of solving constraint problems. One is ‘Constructive Methods’ and it works by constructing piece-by-piece a solution, a second is ‘Heuristic Repair’ and it works by trying a random solution and moving any piece that doesn’t fit into a space where it meets the constraints. The graph search algorithms are used to look for solutions state or constraint graphs.

Greedy Search: A best-first strategy, it arrives at a solution by making a sequence of choices, each of which looks the best at the moment. This is like making change in a store, first you deal out the largest coins, quarters, then when the difference is less than .25, you hand out dimes until it is less than .10, etc. Cost is estimated using a formula h(). h(n) then gives cost of cheapest path to goal state. Greedy is similar to Depth First Search.
Greedy Search: Algorithm
top::
have we got a solution?
true: quit, return answer
false: grab the largest/best selection we can
loop to top:

The following searches are heuristic. They combine one or another of the above searches with a rule of thumb or a weighting method to direct the search. Several evaluation functions exist which are used to construct an ordered search. The heuristic search theories have only been applied to searches in trees, so far.

A* (A star) This algorithm combines a best-first search with a uniform cost search, usually breadth first. h(n) is the best-first formula which is added to g(n), the known path cost. f (n) = g(n) + h(n). The lowest cost f(n) is followed first. Often the example given is of the 15 square puzzle where you slide the numbers to put them in order. A* works by examining the surrounding squares and beginning with the most promising of them, and repeating that until the puzzle is solved.
A*: Algorithm
Put first node on SearchList
loop::
Pop top node on SearchList and put on DoneList
if no nodes on SearchList, break, no solution
is this node the solution?
..yes
….break with answer
..no
….calculate f(n) for each node off of this node
….check DoneList, if node on DoneList discard
….add each node to SearchList in order of smallest f(n) (including previous nodes on SearchList)
….loop::

h(n), an ‘admissible heuristic’, must be chosen in a way that it never overes timates the path cost. If you are trying to find a route between two cities then h(n) is a straight line between the two cities. The better the h(n) function is the better the search will work. Some examples of h(n) are: For the sliding block children’s puzzle that has numbered blocks that you order by sliding about, h(n) might be the number of tiles in the correct location For a path from one location to another h(n) might determine distance from goal of the city node expanded. A* is optimally efficient for any given h(n) function. It will find and expand fewer nodes than any other algorithm. A* is a complete algorithm, and it is of Order, O(log h (n))h (n) is the true cost of reaching the goal. It will also find the lowest cost path from start to finish if there is a path.

idA* (iterative deepening A*), A* does a depth first search up to a cost limit i place of the breadth-first part.

SMA* (simplified memory bounded A*), A* to stay with in memory space, this algorithm fills available memory, then drops the highest cost node, to make room for the new node.

RBFS (recursive best-first search). This uses depth-first and best-first to gether. It calculates f(n) for all the nodes expanded off the current node, then backs up the tree and re-calculates f(n) for the previous nodes. Then it expands the smallest f(n) of those nodes. Planning out a set of steps to reach a goal may be done with STRIPS rules using different search techniques. Searching a group of plans begins with an incorrect or incomplete plan that is changed until it satisfies the situation. Sometimes a rule is learned if it will save time and have general applicability. Situational Calculus is a form of first-order predicate calculus with states, actions, and the effects of states after actions have taken place. A list of states 11 is kept. States are treated as things and actions are treated as functions. The effects of actions are mapped onto the states. The effects of actions on the states can not always be inferred and this is a major weakness of Situational Calculus.

STRIPS combines state-space and situational calculus in an effort to over come the problems of situational calculus. STRIPS has a set of precondition literals, a set of delete literals and a set of add literals. To obtain the after action state using a forward-search the before action conditions are deleted, and add all of the literals in the add list. Everything not in the delete list is carried over to the next state. A recursive STRIPS method adding to each achieved part of the state can also be used. This is the method used in the ‘General Problem Solver’. It uses a global data structure that is set to the initial state and changed until the goal state is reached. The Sussman anomaly occurs if a state closer to the goal must be undone to achieve the goal state, breadth first searches can sometimes work around this. A backward search with STRIPS works backward grabbing sub-goals as it goes. It is usually more efficient, but it is also more complicated and Sussman anomalies appear here as well. Following is the code to show the effects of various types of searches between US cities. It provides a GUI interface and graphical output.

GUI Search Source Code