TC2011 ARTIFICIAL INTELLIGENCE

SPACES AND SEARCH ALGORITHMS

A search space is a collection of all possible solutions to a given problem. We see it as a set of nodes or states that can appear on route to a goal or end state. Search algorithms are one of the most important features of an AI program. How to

examine the search space is a serious consideration in terms of efficiency since there are many ways to combine the data to reach a goal or solution.
The Water Jugs Problem

Imagine that you have two jugs called X and Y. Initially, both are empty. You are allowed to fill either jug X or jug Y from a tap but if you do, you have to fill it completely. You are also allowed to fill jug X from jug Y, or jug Y from jug X, and to empty either jug on the ground. Jug X can hold 4 pints and jug Y can hold 3 pints. The objective is to leave 2 pints in one of the jug.

Evaluation Criteria of Search Strategies

Completeness: Does the strategy guarantee to find a solution if it exists? Optimality: Does the strategy find the best solution among several solutions? Temporal Complexity: How long does it take to find the solution? Space Complexity: How much memory is needed to carry out the search?

Search Depth
In the case of node structures or large frames, it is desirable to limit the exertion used in the search for solutions or inherited values in frame systems. FLEX provides a means to impose a maximum depth of search, for this situation, using a default of 9 levels; this is independent from the search technique used.

NON-INFORMED SEARCH METHODS

1. BREADTH-FIRST
This algorithm will visit all nodes or frames of a tree which has up to a particular level of depth or until a solution is reached, expanding the root first, then the successors of the expanded nodes, and so on.

Example: 1 Animal 2 3Mammal 4 Feline 5 7 Tiger 6 8 Cat 3 X

My_other_ cat

Felix

Evaluation
It is a complete search - Excellent for operators of unit cost (the costs do not change or even better the costs never decrease). - Its time and space complexity is O(bd), where d is the depth of the solution and b is the arity of the tree. Its Space complexity makes it impractical for many cases.

2. UNIFORM SEARCH
It is a modified breadth-first search through the selection of the cheapest route. All routes are saved in a list or stack and the solution is not recognized until they are processed (extracted) from the list, all routes that have been traveled. Example: /--------- A ---------\ 1 10 / \ S ------5----- B ----5------ Meta \ / 15 5 \---------- C --------/

Evaluation
It is a complete search Optimal if the uniform cost is always increasing, ie. There are no negative cost values, operators dont require to be unitary (to have different costs.) Its time complexity is equal to the breadth-first search: O(bd), where d is the depth of the solution and b is the arity of the tree.

3. DEPTH-FIRST
This search algorithm applied to a network node or a hierarchy of frames, will expand an entire branch from the root to reach the leaves, before visiting ancestors. The searches are performed from left to right.

Example. 2 Mammal 3 Feline 4 Tiger

Animal 1

Cat

5 Evaluation
-

My_other_cata t

7 Felix

Its an incomplete search; it can get stuck when entering the wrong path. It is not optimal. This search always goes down without returning, even if there exists a solution from a node with a lesser depth. Its time complexity is O (bm) and space complexity of O (bm), where m is the maximum depth and b is the arity of the tree.

4. ITERATIVE DEEPENING SEARCH

To solve the problem of incompleteness of depth-first search algorithm the following strategy is used: an initial maximum depth is defined and it is increased iteratively to find the solution.

Criteria
This algorithm combines the benefits of breadth-first searches and depth-first searches: - It is complete and optimal, such as breadth-first search. - It has the memory requirements of depth-first search. The downside is that many states are expanded multiple times. > This is the preferred method when the search space is large and the depth of the solution is unknown.

BIDIRECTIONAL SEARCH
The idea of this method is to expand simultaneously from the source and from the target, until both searches meet in the middle. This method is only applicable when the arity b of the network is the same in both directions, and if so, the search can make a huge difference having a space complexity of O(bd/2). For example, for b = 10 and d = 6, breadth-first search generates 1'111, 111 nodes, while the bidirectional search generate only 2,222 nodes in each direction. The disadvantage is that its implementation is more complex.

COMPARISON OF SEARCH STRATEGIES Criteria

Time Space Optimal? Complete? BreadthFirst bs bs Yes Yes Uniform Cost bs bs Yes Yes bm bm No No Depth Limited Depth bl bl No Yes l >=s Iterative Depth bs bs Yes Yes Bidirectional bs/2 bs/2 Yes Yes

Where

b - branching factor s - depth of the solution m - maximum depth of the tree (from root to the leaf with the longest route) l - limit of the search depth (# of search levels )

---------------------------------------------------------------------------------------------HOMEWORK 2:
Implement a Prolog database to represent the knowledge of problem solving of photography expressed in the delivered photocopy (Bowen, Appendix E).

----------------------------------------------------------------------------------------------

INFORMED SEARCH STRATEGIES

Informed search methods use a heuristic function that provides an estimate of how close a state is from the goal, allowing you to choose the node that is closest to the target. The heuristic function calculation can be done at low cost, whilst at the same time the solution is being calculated. 1) HILL-CLIMBING Analogy camping This algorithm selects as the next step, a state that guarantees to be in the path of the target state and appear as close to it as possible. 2) MIN-COST Path of least resistance This algorithm selects as the next step the state with the lowest cost of transition from the current state. Examples for all searches: 1. Location of an object in a store Warehouse 2 Corridor Main Warehouse Receiving Products Warehouse 1 Office Studio

SPACE SOLUTIONS Home Receiving Products Corridor Office (Bomba) ..... Studio ... 2 0 1

Warehouse1 Warehouse2 Main Warehouse

2. Determination of flight routes.

a) Incorporating Heuristic of Hill- Climbing: link closest to the goal. b) Incorporating Heuristic of Min-Cost: Select the shortest connections.

Calgary

2500

Toronto 1800 500 Chicago 1000

Los Angeles

800

1000

New York

1900 Denver 1500 Houston

1500

New York
1000

Chicago
MC2

Toronto

800 MC1

1900 HC1
Denver
1000 HC2

1
Denver
1500 HC3

Los Angeles
Solucin Min-Cost

Calgary Chicago

Los Angeles
Solution Min-Cost

Los Angeles

Houston
1500 HC4

Los Angeles Solution Hill-Climbing

Multiple Solutions When a problem requires many different solutions to a problem it is possible to use generating methods of multiple solutions, such as: Path Removal: It consists of removing all the nodes that lead to the current solution from the database and then trying to find another solution, i.e. pruning tree branches Node Removal: Removes only the last node in the path of the current solution and then tries to find another solution. Optimal Solution The optimal solution to a search problem can only be performed through exhaustive search. The best way to do a search (non-exhaustive) is combining a method of multiple solutions with one of the heuristics above. These include the path removal, generating multiple solutions and the search for mincost to minimize the distance.