Artificial intelligence (AI) with It's Applications

Drawback of DFS: DFS can make a wrong choice and get stuck going down a very long (even infinite) path when a different choice would lead to a solution near the root of the search tree.

Depth-Limited Search (DLS)

The procedure: If we can limit the depth of search tree to a certain level then searching will be more efficient. This removes the problem of unbounded trees. Such a kind of depth first search where in the depth is limited at a certain level is called as depth limited search. It solves infinite path problem.

The implementation: Same as DFS but limited to depth level 𝑙. DLS will terminate with two kinds of failure. The standard failure value indicates no solution and the cut-off value indicates no solution with in the depth limit.

The performance evaluation

1. Completeness: DLS suffers from completeness because if we choose 𝑙 (levels to be searched) < d (actual levels), when shallowest goal is beyond the depth limit 𝑙. It generally happens when ' 𝑑 ' is unknown.

2. Optimality: DLS is non-optimal if we choose 𝑙 (levels to be searched) > d (actual levels) because shallowest goal state may be ignored while reaching to depth level 𝑙.

3. Time and space complexity: Its time complexity is 𝑂(𝐛^𝑙) and space complexity is O(b𝑙). If we have knowledge of the problem, then we can decide depth limits. If we can find better depth limit then we can achieve more efficiency. This better depth limit is termed as diameter of state space. If problem is too complex then we are unable to find diameter of state space.

Algorithm for Depth Limited Search

DLS (node, goal, depth)

{

if(depth > = 0)

{

if(node == goal)

return node

for each child expand(node)

DLS (child, goal, depth-1)

}

}

General steps for DLS

1. Determine the node where the search should start and assign the maximum search depth.
2. Check if the current node is the goal state. v IF not: Do nothing v IF yes: Return
3. Check if the current node is within the maximum search depth. v IF not: Do nothing v IF yes: a) Expand the vertex and save all of its successors in stack. b) Call DLS recursively for all nodes of the stack and go back to step 2.

DLS [Depth-Limited Search]

Fig. 1.7 Depth-Limited Search.

If depth limit = 2 then nodes on level 2 are not expanded. D found (A-B-D)

(D, E, F, G are generated but not expanded). J though better goal than D could not reached because of algorithm technique.

Note: The numeric value beside each node indicates the order in which nodes are visited

(reached).

Iterative-Deepening Depth-First Search (IDDFS)

The procedure: In iterative deepening depth-first search, dfs is applied along with the best depth limit. In each step gradually it increases the depth limit until the goal is found. It increases depth limit from level 0, then level 1, then level 2 till the shallowest goal is found at certain depth 'd'.

The implementation: Iterative deepening depth first search can be implemented similar to BFS (where queue is used for storing fringe) because it explores a complete layer of new nodes at each iteration before going on to the next layer.

If we want to avoid memory requirements which are incurred in BFS then IDDFS can be implemented like uniform-cost search.

The key point is to use increasing path-cost limits instead of increasing depth limits, is if we have such a implementations it is termed as iterative lengthing search.

The performance evaluation

1. Completeness: It guarantees completeness as the search does not stop until goal node is found.

2. Optimality: As iterative deepening depth first search stops when the first goal node is reached, it is not necessary that it is the optimal. (That is, the shallowest goal reached is the final. Iterative deepening depth first search will not further search for optimal solution).

3. Time and space complexity: Iterative deepening depth first search has very moderate space complex which is 𝐎 (bd). Its time complexity depends on branching factor (b) and the bottom most level that is depth

(d). It is 𝑂(𝑏^𝑑).

Algorithm for Iterative-Deepening Depth First Search

//In IDDFS algorithm we are using DLS algorithm from earlier section IDDFS (root, goal)

{

depth = 0

while (no solution)

{

solution = DLS(root, goal, depth)

depth = depth +1

}

return solution

}

Example-IDDFS (Iterative Deepening Depth-First Search]

Fig. 1.8 Iterative Deepening Depth-First Search.

Shallowest Goal Node D Found:

Note: The numeric value beside each node indicates the order in which nodes are visited

(reached).

Bidirectional Search

The procedure: As the name suggests bi-directional that is two directional searches are made in this searching technique. One is the forward search which starts from initial state and the other is the backward search which starts from goal state. The two searches stop when both the searches meet in the middle. [As shown in below diagram].

Fig. 1.9 Schematic view of bidirectional search.

The implementation: Bidirectional search is implemented by having one or both of the searches check, each node before it is expanded, is examined to see if it is in the fringe of the other search tree. If so solution is found. Fringe can be maintained in queue data structure, like BFS.

The performance evaluation

1. Completeness: Bidirectional search is complete if branching factor 𝐛 is finite and both directions searches use BFS.
2. Optimality: It is optimal as the goal is being searched from both directions. So guaranteed to find optimal (best) goal state.
3. Time and space complexity: Bidirectional search has time complexity as O(b^d/2), where ' b ' is branching factor. It is the important noticable point in case of backward a search because, we need to get predecessors of the node. The easiest case is when all the actions in the state space are reversible. When one goal state is there, the backward search is very much like the forward search (like in 8 puzzle problem). If there are several explicitly listed goal states (like in part picking robot) then it needs to construct a new dummy goal state whose immediate predecessors are all then actual goal states. The worst case in bidirectional search is when the goal test gives only implicit description of some possibly large set of goal states.

For example, in the game of chess 'checkmate' is the goal state which will have many possible description.

The memory requirement for bidirectional search is also moderate which is O(b^d/2) where 𝑏 = Branching factor, 𝑑 = Depth, where at least one of the search tree is maintained in memory.

Bidirectional search

Space complexity-O ( 𝑏^𝑑/2)

Time complexity-O ( 𝑏^d/2)

1.5 Strategy for Control

Control strategy is a strategy by which one come to know which rule is to be applied next during the process of reaching for a solution to problem.

Control strategies help to overcome the abnormal situations, when there are more than one rules or fewer than one rule will have its left side match the current state.

A good control strategy must have the following requirements (characteristics).

It should cause motion: A control strategy should always cause motion as only such control strategy can lead to solution. If there is no motion that means there is no change of state and if state is not changed, then one will never proceed from the initial state. So reaching to a goal state will become a dream or impossible.

For example, in water jug problem if one chooses first rule every time i.e., fill the 4-gallon jug full then one would never solve the problem. One would continue indefinitely filling the 4 -gallon jug with water. So a control strategy should always cause motion.

It should be systematic: A control strategy that causes motion but is not systematic is also not good. As in this type of strategy one can reach to a solution but it may pass from one state many times or many explore a particular sequence of operators several times unnecessarily and may use many more steps than are necessary.

1.6 Heuristic Search

Generate and Test

Generate-and-Test is a search algorithm which uses depth first search technique. It assures to find solution in systematic way. It generates complete solution and then the testing is done. A heuristic is needed so that the search is improved.

Following is the algorithm for Generate-and-Test

1. Generate a possible solution which can either be a point in the problem space or a path from the initial state.

2. Test to see if this possible solution is a real (actual) solution by comparing the state reached with the set of goal states.

3. If it is real solution then return the solution otherwise repeat from state 1. Following diagram illustrates the algorithm steps

Fig. 1.10 Generate-and-Test.

Generate-and-Test is acceptable for simple problems whereas it is inefficient for problems with large spaces.

Introduction to Informed Search

Informed search strategy is the search strategy that uses problem-specific knowledge beyond the definition of the problem itself.

The general, method followed in informed search is best first search. Best first search is similar to graph search or tree search algorithm where in node expansion is done based on certain criteria.

Best First Search Technique (BFS)

Search will start at root node. v The node to be expanded next is selected on the basis of an evaluation function, f(n). v The node having lowest value for 𝑓(𝑛) is selected first. This lowest value of 𝑓(𝑛) indicates that goal is nearest from this node (that is 𝑓(𝑛) indicates distance from current node to goal node).

Implementation: BFS can be implemented using priority queue where fringe will be stored. The nodes in fringe will be stored in priority queue with increasing value of 𝑓(𝑛) i.e. ascending order of 𝑓(𝑛). The high priority will be given to node which has low 𝑓(𝑛) value.

As name says "best first" then, we would always expect to have optimal solution. But in general BFS indicates that choose the node that appears to be best according to the evaluation function. Hence the optimality based on 'best-ness' of evaluation function.

Algorithm for best first search

Use two ordered lists OPEN and CLOSED. v Start with the initial node ' n₁' and put it on the ordered list OPEN. v Create a list CLOSED. This is initially an empty list. v If OPEN is empty then exit with failure. v Select first node on OPEN. Remove it from OPEN and put it on CLOSED. Call this node n. v If ' 𝑛 ' is the goal node exit. The solution is obtained by tracing a path backward along the arcs in the tree from ' n ' to ' n₁'. v Expand node ' 𝑛 '. This will generate successors. Let the set of successors generated, be S. Create arcs from ' 𝑛 ' to each member of 𝑆. v Reorder the list OPEN, according to the heuristic and go back to step 4. Consider the following 8-puzzle problem

Here the heuristic used could be "number of tiles not in correct position" (i.e. number of tiles misplaced). In this solution the convention used is, that smaller value of the heuristic function ' f ' leads earlier to the goal state.

Step 1

𝑓(𝑛) = 4

This is the initial state where four tiles (1,2,6,8) are misplaced so value of heuristic function at this node is 4.

Step 2

This will be the next step of the tree.

𝑓(𝑛) = 3

𝑓(𝑛) = 5

𝑓(𝑛) = 5

Heuristic function gives the values as 3, 5 and 5 respectively. Step 3

3 nodes.

f(n) = 3

𝑓(𝑛) = 4

𝑓(𝑛) = 3

Step 4

Here there is tie for 𝑓(𝑛) value. We continue to expand node.

𝑓(𝑛) = 2

𝑓(𝑛) = 4

Step 5

𝑓(𝑛) = 1

Step 6

Goal state

𝑓(𝑛) = 2

In this algorithm a depth factor g is also added to h.

Heuristic Function

There are many different algorithms which employ the concept of best first search. The main difference between all the algorithms is that they have different evaluation function. The central component of these algorithms is heuristic function - ℎ(𝑛) which is defined as, h(n) = Estimate cost of the cheapest path from node ' n ' to a goal node.

Note

Heuristic function is key component of best first search. It is denoted by h( n ) and h(n) = The shortest and cheapest path from initial node to goal node. v One can give additional knowledge about the problem to the heuristic function. For example-In our problem of Pune-Chennai route we can give information about distances between cities to the heuristic function.

A heuristic function guide the search in an efficient way.

A heuristic function ℎ(𝑛) consider a node as input but it rely only on the state at that node.

ℎ(𝑛) = 0, if 𝑛 is goal state.

Greedy Best First Search (GBFS)

Greedy best first search expand the node that is closest to the goal, expecting to get solution quickly,

It evaluates node by using the heuristic function 𝑓(𝑛) = ℎ(𝑛).

It is termed as greedy (asking for more) because at each step it tries to get as close to the goal as it can.

GBFS resembles DFS in the way that it prefers to follow a single path all the way to the goal. It back tracks when it comes to dead end that is, to a node from which goal state cannot be reached.

Choosing minimum ℎ(𝑛) can lead to bad start as it may not yield always a solution. Also as this exploration is not leading to solution, therefore unwanted nodes are getting expanded.

In GBFS, if repeated states are not detected then the solution will never found.

Performance measurement

1. Completeness: It is incomplete as it can start down an infinite path and never return to try other possibilities which can give solution.
2. Optimal: It is not optimal as it can initially select low value ℎ(𝑛) node but it may happen that some greater value node in current fringe can lead to better solution. Greedy strategies, in general, suffers from this, "looking for current best they loose on future best and in turn finally the best solution" !
3. Time and space complexity: Worst case time and space complexity is O(𝐛^m) where ' m ' is the maximum depth of the search space.

The complexity can be reduced by devicing good heuristic function.

∗ Condition at which A becomes, i) BFS, ii) Best First Search and iii) No* Search is Required According to 𝐀^∗ algorithm

The heuristic function that estimates the merits of node we generate. This will enable the algorithm to search more promising path first. v Call this function 𝐟^′ (to indicate that it is an approximation to a function 𝐟 that gives the true evaluation of the node). v For many applications, it is convenient to define this function as the sum of two components that we call 𝑔 and 𝐡^′. v The function g is a measure of the cost of getting from the initial state to the current node. Note that g is not an estimate of anything it is known to be the exact sum of the cost of applying each of the rules that were applied along the best path to the node. v The function 𝐡^′ is an estimate of the additional cost of getting from the current node to a goal state. v This is the place where knowledge about the problem domain is exploited. v The combined function 𝐟^′, then represents an estimate of the cost of getting from the initial state to a goal state along the path that generated the current node. v There are conditions through which algorithm A^∗ will become -

i) Breadth-first search ii) Best-first search iii) No search is required. **i) Breadth-first search -**If the value of g is always 1, then the search will be known as breadth-first search. **ii) Best-first search -**If the value of ℎ^′ is 0, then the search will be controlled by g, then the search is known as best first. **iii)No search is required -**If 𝐡^′ is a perfect estimator of ℎ then 𝐴^∗ will converge immediately to the goal without searching. Hence, search is not required.

Memory Bounded Heuristic Search

If we use idea of Iterative deepening search then we can reduce memory requirements of A^∗. From this concept we device new algorithm.

Iterative deepening 𝐀^∗

Like IDDFS uses depth as cutoff value in IDA* f-cost (g + h) is used as cutoff rather than the depth.

It reduces memory requirements, incurred in A^∗, thereby putting bound on memory hence it is called as memory bounded algorithm. v IDA* suffers from real value costs of the problem. v We will discuss two memory bounded algorithm -

1. Recursive breadth first search.
2. MA* (Memory bounded A^∗).

Recursive Best First Search (RBFS)

It works like best first search but using only linear space. v Its structure is similar to recursive DFS but instead of continuing indefinitely down the current path it keeps track of the F value of the best alternative path available from any ancestor of the current node. v The recursion procedure is unwinded back to the alternative path if the current node crosses limit. v The important property of RBFS is that it remembers the f-value of the best leaf in the forgotten subtree (previously left unexpanded). That is, it is able to take decision regarding re-expanding the subtree. v It is reliable, cost effective than IDA but its critical problem is excessive node generation. Performance measure

1. Completeness: It is complete.
2. Optimality: Recursive best-first search is optimal if ℎ(𝑛) is admissible.
3. Time and space complexity: Time complexity of RBFS depends on two factors - a) Accuracy of heuristic function. b) How often (frequently) the best path changes as nodes are expanded. RBFS suffers from problem of expanding repeated states, as the algorithm fails to detect them.

It’s space complexity is O(bd).

It’s suffers from problem of using too little (very less) memory. Between iterations, RBFS maintains more information in memory but it uses only 𝐎(𝐛𝐝) memory. If more memory is available then also RBFS cannot utilize it.

MA*

RBFS under utilizes memory. To overcome this problem MA* is deviced.

Its more simplified version called as simplied MA* proceeds as follows -

If expands the best leaf until memory is full. v At this point it cannot add new node to the search tree without dropping an old one. v It always drops the node with highest f-value. v If goal is not reached then it backtracks and go to the alternative path. In this way the ancestor of a forgotten subtree knows the quality of the best path in that subtree. v While selecting the node for expansion it may happen that two nodes are with same f-value. Some problem arises, when the node is discarded (multiple choices can be there as many leaves can have same f-value).

The SMA* generates new best node and new worst node for expansion and deletion respectively. Performance measurement

1. Completeness: SMA* is complete and guarantee solution.
2. Optimality: If solution is reachable through optimal path it gives optimal solution. Otherwise it returns best reachable solution.
3. Time and space complexity: There is memory limitations on SMA*. Therefore it has to switch back and forth continually between a set of candidate solution paths, only small subset of which can fit in memory. This problem is called as thrashing because of which algorithm takes more time. Extra time is required for repeated regeneration of the same nodes, means that the problem that would be practically solvable by A^∗ (with unlimited memory) became intractable for SMA*.

It means that memory restrictions can make a problem intractable from the point of view of computation time.

Problem Reduction with AO* Algorithm (AND-OR Graphs Algorithm)

When a problem can be divided in a set of sub problems, where each sub problem can be solved seperately and a combination of these will be a solution. AND-OR graphs or AND-OR trees are used for representing the solution.

AND-OR graphs

The decomposition of the problem or problem reduction generates AND arcs. v One AND arc may point to any number of successor nodes. v All these must be solved so that the arc will give rise to many arcs, indicating several possible solutions. Hence the graph is known as AND-OR instead of AND. v AO^∗ is a best-first algorithm for solving problems represented as a cyclic AND/OR

graphs problems. v An algorithm to find a solution in an AND-OR graph must handle AND area appropriately.

Fig. 1.11 AND-OR graph example.

The comparative study of 𝐀^∗ and 𝐀𝐎^∗

Unlike A^∗ algorithm which used two lists OPEN and CLOSED, the AO* algorithm uses a single structure G. v 𝐺 represents the part of the search graph generated so far. v Each node in G points down to its immediate successors and upto its immediate predecessors, and also has with it the value of ' ℎ ' cost of a path from itself to a set of solution nodes. v The cost of getting from the start nodes to the current node 'g' is not stored as in the A^∗ algorithm. This is because it is not possible to compute a single such value since there may be many paths to the same state. v AO^∗ algorithm serves as the estimate of goodness of a node. v A^∗ algorithm cannot search AND-OR graphs efficiently. v AO^∗ will always find minimum cost solution. The algorithm for performing a heuristic search of an AND-OR graph is given below.

AO* algorithm

Initialize the graph to start node. v Traverse the graph following the current path accumulating nodes that have not yet been expanded or solved. v Pick any of these nodes and expand it and if it has no successors call this value as, FUTILITY, otherwise calculate only ' f ' for each of the successors. v If ' 𝑓 ' is 0 then mark the node as SOLVED. v Change the value of ' 𝑓 ' for the newly created node to reflect its successors by back propagation.

Wherever possible use the most promising routes and if a node is marked as SOLVED then mark the parent node as SOLVED. v If starting node is SOLVED or value greater than FUTILITY, stop, else repeat from

How to Search Better?

We have seen many searching strategies till now, but as we can see no one is really the perfect. How can we make our AI agent to search better?

We can make use of a concept called as meta-level state space. Each state in a meta-level state space captures the internal (computational) state of a program that is searching in an object-level state space such as in Indian Traveller Problem.

Consider 𝐀^∗ algorithm

In A^∗ algorithm it maintains internal state which consists of the current search tree. v Each action in the metalevel state space is computation step that alters the internal state. For example-Each computation step in A^∗ expands a leaf node and adds its successors to the tree.

As the level increases the sequence of larger and larger search trees is generated.

In harder problem there can be mis-steps taken by algorithm. That is algorithm can explore unpromising unuseful subtrees. Metalearning algorithm overcomes these problems.

The main goal of metalearning is to minimize the total cost of problem solving.

Heuristic Functions and Their Nature

Accuracy of Heuristic Function

More accurate the heuristic function more is the performance.

The quality of heuristic function can be measured by the effective branching factor 𝑏^∗.

Consider A^∗ that generates N nodes and ' d ' is depth of a solution, then b^∗ is the branching factor that a uniform tree of depth ' 𝑑 ' would have so as to contain ' 𝑛 + 1 ' nodes.

Thus, N + 1 = 1 + b^∗ + (b^∗)² + ⋯ + (b^∗)^d

If A^∗ finds a solution at depth 5 using 52 nodes, then the effective branching factor is 1.92.

A well designed heuristic function will have a value of 𝑏^∗ close to 1, allowing fairly large problems to be solved.

An Example of Designing Heuristic Function

Consider 8-puzzle problem

The objective of the puzzle is to slide the tiles horizontally or vertically into the empty space until the configuration matches the goal configuration.

Start state

Goal state

The average solution cost for a randomly generated 8 -puzzle instance is about 22 steps. v The branching factor is about 3 (when the empty tile is in the middle, there are four possible moves, when it is in a corner there are two, and when it is along an edge there are three. v An exhaustive search to depth 22 would look at about 3²² ≈ 3.1 × 10¹⁰ states. v If we keep track of repeated states, we could cut this down by a factor of about 1,70,000, because there are only 9!/2 = 1,81,440 distinct states that are reachable. v If we use 𝐴^∗, we need a heuristic function that never overestimates the number of steps to the goal. v We can use following heuristic function, Ø h₁ = The number of misplaced tiles. All of the eight tiles are out of position, so the start state would have h₁ = 8 ⋅ h₁, is an admissible heuristic, because it is clear that any tile that is out of place must be moved at least once. Ø h₂ = The sum of the distances of the tiles from their goal positions. Because tiles cannot move along diagonals, the distance we will count is the sum of the horizontal and vertical distances.

The Domination of Heuristic Function

If we could design multiple heuristic function for same problem then we can find that which one is better.

Consider two heuristic functions ℎ₁ and ℎ₂. From their definitions for some node 𝑛, if ℎ₂(n) ≥ ℎ₁(n) then we say that ℎ₂ dominates ℎ₁.

Domination directly points to accuracy. A^∗ using h₂ will never expand more nodes than 𝐴^∗ using ℎ₁ (except for some node having 𝑓(𝑛) = 𝑐^∗).

Admissible Heuristic Functions

A problem with fewer restrictions on actions is called a relaxed problem. v The cost of an admissible solution to a relaxed problem is an admissible heuristic for the original problem. The heuristic function is admissible because the optimal solution in the original problem is, also a solution in the relaxed problem, and therefore must be at least as expensive as the optimal solution in the relaxed problem. v As the derived heuristic is an exact cost for the relaxed problem, therefore it is consistant. v If problem definitions are written in formal languages then it is possible to construct relaxed problem automatically. v Admissible heuristic function can also be derived from the solution cost of a subproblem of the given problem. The cost of optimal solution of this subproblem would be the lower bound on the cost of the complete problem. v We can store the exact solution costs for every possible subproblem instance in a database. Such a database is called as pattern database. The pattern database is constructed by searching backwards from the goal state and recording the cost of each new pattern encountered.

The cost of the entire problem is always greater than sum of cost of two subproblems. Hence it is always better to derive disjoint solution and then sum up all solutions to minimize the cost.

Learning Heuristic from Experience

A heuristic function ℎ(𝑛) is supposed to estimate the cost of a solution begining from the state at node 𝑛. Therefore it is really difficult to design ℎ(𝑛). v One solution is to devise relaxed problems for which an optimal solution can be found. v Another solution is to make agent program that can learn from experience.

"Learn from experience" means solving similar problem again and again (i.e. practicing). Ø Each optimal solution will provide example from which ' ℎ(𝑛) design' can be learned. Ø One can get experience of which ℎ(𝑛) was better. Ø Each example consists of a state from the solution path and the actual cost of the solution from that point. Ø From such solved examples an inductive learning algorithm can be used to construct the function ℎ(𝑛) that can predict solution costs for another states that have arised during search. [A lucky agent program will get the prediction early.] Ø For developing inductive algorithms we can make use of techniques like neural nets, decision trees, etc. Ø If inductive learning methods have knowledge about features of a state that are relevant to evaluation of algorithms then inductive learning methods give best output.

1.7 Hill Climbing Search

This algorithm generally moves up in the direction of increasing value that is-uphill. It breaks its “moving up loop” when it reaches a “peak” where no neighbour has a higher value.

It does not maintain a search tree. It stores current node data structure. This node records the state and its objective function value. Algorithm only look out for immediate neighbours of current state.

It is similar to greedy local search in a sense that it considers a current good neighbour state without thinking ahead.

Greedy algorithm works very well as it is very easy to improve bad state in hill climbing.

Algorithm for Hill Climbing

The algorithm for hill climbing is as follows:

Evaluate the initial state. If it is goal state quit, otherwise make current state as initial state. v Select a new operator that could be applied to this state and generate a new state. v Evaluate the new state. If this new state is closer to the goal state than current state make the new state as the current state. If it is not better, ignore this state and proceed with the current state.

If the current state is goal state or no new operators are available, quit. Otherwise repeat from 2.

Problems with Hill Climbing

1. Local maxima-can't see higher peak. 2) Shoulder-can't see the way out. Fig. 1.12 Various stages in hill climbing search.

**Local maxima -**It is a state where we have climbed to the top of the hill, and missed on better solution.

It is the mountain-A state that is better than all of its neighbours, but not better than some other states further away. [Shown in Fig. 1.13]

Fig. 1.13 Local maxima.

Plateau: It is a state where everything around is about as good as where we are currently. In other words a flat area of the search space in which all neighbouring states have the same value. [Shown in Fig. 1.14]

Fig. 1.14 Plateau.

Ridges: In this state we are on a ridge leading up, but we can't directly apply an operator to improve the situation, so we have to apply more than one operator to get there. [Shown in

Fig. 1.15]

Fig. 1.15 Ridges.

Illustration of ridges: The grid of states (dark circles) is superimposed on a ridge rising from left to right, creating a sequences of local maxima that are not directly connected to each other. From each local maximum all the available actions point downhill.

Solving Problems Associated with Hill Climbing

All the above discussed problems could be solved using methods like backtracking, making big jumps (to handle plateaus or poor local maxima), applying multiple rules before testing (helps with ridges) etc. Hill climbing is best suited to problem where the heuristic gradually improves, the closer it gets to the solution; it works poorly where there are sharp drop-offs. It assumes that local improvement will lead to global improvement.

Example for Local Search

Consider the 8-queens problem

A complete-state formulation is used for local search algorithms. In 8-queens problem, each state has 8 -queens on the board one per column. There are two functions related with 8 - queens.

1. The successor function: It is function which returns all possible states which are generated by a single queen move to another cell in the same column. The total successor of the each state 8 × 7 = 56.
2. The heuristic cost function: It is a function ' ℎ ' which hold the number of attacking pair of queens to each other either directly or indirectly. The value is zero for the global minimum of the function which occurs only at perfect solutions.

Advantages of Hill Climbing

Hill climbing is an optimization technique for solving computationally hard problems. v It is best used in problems with the property that the "state description itself contains all the information needed for a solution". v The algorithm is memory efficient since it does not maintain a search tree. It looks only at the current state and immediate future states. v In contrast with other iterative improvement algorithms, hill-climbing always attempts to make changes that improve the current state. In other words, hill-climbing can only advance if there is a higher point in the adjacent landscape. v It is often useful when combined with other methods, getting it started right in the immediate general neighbourhood.

Variations of Hill Climbing

Many variants of hill-climbing have been invented as discussed below.

Stochastic hill climbing: Chooses at random from among the uphill moves; the probability of selections can vary with the steepness of the uphill move. v First choice hill climbing: Implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state. This is a good strategy when a state has many (e.g. thousands) of successors. v Random restart hill climbing: Adopts the well known saying "If at first you don't succeed, try, try again". It conducts a series of hill climbing searches from randomly generated initial states, stopping when a goal is found. The hill climbing algorithms described so far are incomplete because they often fail to find a goal when surely goal exist. This can happen because these algorithms can get stuck on local maxima. Random restart hill is complete with probability approaching to 1. This algorithm do not stop until it reaches to goal.

The success of hill climbing depends very much on the shape of the state-space landscape. If there are few local maxima and plateaux, random-restart hill climbing will find a good solution very quickly.

Steepest ascent hill climbing: This algorithm differs from the basic hill climbing algorithm by choosing the best successor rather than the first successor that is better. This indicates that it has elements of the breadth first algorithm.

Steepest ascent hill climbing algorithm

v Evaluate the initial state.

If it is goal state then quit otherwise make the current state this initial state and proceed.

Repeat set target to be the state that any successor of the current state can better; for each operator that can be applied to the current state apply the new operator and create a new state evaluate this state.

If this state is goal state then quit. Otherwise compare with target. If better set target to this value. If Target is better than current state set current state to target. Until a solution is found or current state does not change.

Both the basic and this method of hill climbing may fail to find a solution by reaching a state from which no subsequent improvement can be made and this state is not the solution.Local maximum state is a state which is better than its neighbours but is not better than states faraway. These are often known as foothills. Plateau states are states which have approximately the same value and it is not clear in which direction to move in order to reach the solution. Ridge states are special types of local maximum states. The surrounding area is basically unfriendly and makes it difficult to escape from, in single steps, and so the path peters out when surrounded by ridges. Escape relies on: backtracking to a previous good state and proceed in a completely different direction involves keeping records of the current path from the outset; making a gigantic leap forward to a different part of the search space perhaps by applying a sensible small step repeatedly, good for plateau; applying more than one rule at a time before testing, good for ridges. None of these escape strategies can guarantee success.

1.8 Issues with Constraint Satisfaction

Constraint satisfaction problems are problems whose states and goal test conform to a standard, structured and very simple representation. Search algorithm can be defined that take advantage of the structure of states and can use general-purpose rather than problem-specific heuristics to enable the solution of large problems.

Constraint Satisfaction Problems-The Concept

Constraint satisfaction problem has various states and goal test, a traditional problem has been converted into standard structured and very simple "representation". v The general-purpose routines can be used to access a special representation which has more benefit than problem-specific heuristics. These routines combined with special structure can find solution of large problems. v The structure of the problem is represented in different form such as, standard representation of the goal test. v The revealed structured is very efficient in many ways such as,

Problem decomposition. Ø To understand structure of problem and the difficulty of solving it and their connection. v If the problem is treated as CSP we have many advantages, as discussed below. Ø As the representation of states have standard pattern [that is a set of variables with assigned values], we can design successor function and goal test in generic way that will apply to all CSPs. Ø We can develop effective generic heuristic that require no additional domain specific expertise. Ø The structure of the constraint graph can be used to simplify the solution process in some cases giving exponential reduction in complexity.

Formal Definition of Constraint Satisfaction Problems

A constraint satisfaction problem is defined by a set of variables 𝑋₁, 𝑋₂,…,𝑋_𝑛 and a set of constraints 𝐶₁, 𝐶₂,…,𝐶_𝑚. v Each variable 𝑋₁ has a nonempty domain 𝐷₁ of possible values. v Each constraint 𝐶₁ involves some subset of the variables and specifies the allowable combinations of values for that subset. v A state of the problem is defined by an assignment of values to some or all of the variables {𝑋_𝑖 = 𝑉_𝑖, 𝑋_𝑗 = 𝑉_𝑗, …}. v An assignment that does not violate any constraints is called a consistent or legal assignment. v A complete assignment is one in which every variable is maintained and a solution to a CSP is, a complete assignment that satisfies all the constraints.

4. Some CSPs also require a solution that maximizes an objective function. Consider following graph colouring problem. Constraints are -

5. We have three colours for colouring a vertex.

6. No two adjacent vertices have same colour. Given three colours-(Red, Green, Blue). Allowable combination for A, B vertices would be, {(𝑅, 𝐺), (𝑅, 𝐵), (𝐺, 𝑅), (𝐺, 𝐵), (𝐵, 𝑅), (𝐵, 𝐺)}

Examples of CSP

Map Colouring Problem

The problem is to colour the regions of a given map such that no 2 adjacent regions have the same colour. [Refer Fig. 1.17] v The regions in the map are the variables and the set of possible colours for the regions is the domain. v The constraint is that "no two adjacent regions should have the same colour." Formal Representation of Map Colouring Problem

1. Variables: {N, NW, NE, M, MW, ME, S, SE}
2. Domains: D={red, green, blue }
3. Constraints: Adjacent regions must have different colors. Example: N ≠ NW

Note:

Typically, such a problem has many solutions. v We sometimes represent map colouring as a graph coloring (constraint graph) problem. v The topology of a constraint graph can sometimes be used to identify solutions easily.

Other Examples of CSP

1. N-queens puzzle.

2. Job shop scheduling.

3. Scene labelling.

4. Circuit board layout.

5. Map colouring problem.

6. Sudoku

7. Boolean satisfiability.

Some real-world problems

1. Assignment problems.
2. Transporation scheduling.
3. Hardware configuration.
4. Spreadsheets.
5. Factory scheduling.
6. Floor planning. Fig. 1.17 Map colouring problem.

Incremental Formulation for CSP

It is fairly easy to see that a CSP can be given an incremental formulation as a standard search problem as follows,

i) Initial state

The empty assignment {}, in which all variables are unassigned.

ii) Successor functions

A value can be assigned to any unassigned variable, provided that it does not conflict with previously assigned variables.

iii) Goal test

The current assignment is complete.

iv) Path cost

A constant cost for every step.

Searching for Goal State in CSP

1. Every solution must be a complete assignment and therefore appears at depth n if there are n variables.
2. The search tree extends only to depth n.
3. Depth-first search algorithms are popular for CSPs.
4. The path by which a solution is reached is irrelevant.
5. We can also use a complete-state formulation, in which every state is a complete assignment that might or might not satisfy the constraints.
6. Local search methods work well for this formulation.

Variations in CSPs

The simplest kind of CSP involves variables that are discrete and have finite domains. Graph-coloring problems are of this kind. The 8 -queens problem described can also be viewed as finite-domain CSP, where the variables Q₁,…,Q₈ are the positions of each queen in colums 1, …,8 and each variable has the domain {1,2,3,4,5,6,7,8}. If the maximum domain size of any variable is a CSP in 𝑑, then the number of possible complete assignments are 𝑂(𝑑^𝑛) that is exponential in the number of variables. v Finite-domain CSPs include Boolean CSPs, whose variables can be either true or false. Boolean CSPs include, as special cases, some NP-complete problems, such as 3SAT. v In most practical applications, however, general-purpose CSP algorithms can solve problems of orders of magnitude larger than those solvable via the general-purpose search algorithms that we saw.

Discrete variables can also have infinite domains-for example, the set of integers or the set of strings. v Constraints satisfaction problems with continuous domains are very common in the real world and are widely studied in the field of operations research. For example, the scheduling of experiments on the Hubble Space Telescope requires very precise timing of observations; the start and finish of each observation and man ever are continuous-valued variables that must obey a variety of astronomical, precedence and power constraints. The best-known category of continuous-domain CSPs is that of linear programming problems where constraints must be linear inequalities.

Constraints in CSPs

Properties of Constraints

Constraints are used to guide reasoning of everyday common sense. The constraints have following properties.

Constraints may specify partial information; constraint need not uniquely specify the values of its variables. v Constraints are non-directional, typically a constraint on (say) two variables V₁, V₂ can be used to infer a constraint on V₁ given a constraint on V₂ and vice versa. v Constraints are declarative; they specify what relationship must hold without specifying a computational procedure to enforce that relationship. v Constraints are additive; the order of imposition of constraints does not matter, all that matters at the end is that the conjunction of constraints is in effect. v Constraints are really independent; typically constraints in the constraint store (i.e. collection of constraints) share variables.

Types of Constraints in CSPs

Unary constraint

Which restricts the value of a single variable. Every unary constraint can be eliminated simply by prepressing the domain of the corresponding variable to remove any value that violates the constraint.

For example-Constraint can be that, Vertex A can’t be coloured with blue colour.

Binary constraint

Relates two variables. A binary CSP is one with only binary constraints; it can be represented as a constraint graph. For example-In graph colouring problem two adjacent vertices can’t have same colour.

Higher-order constraints

Involves three or more variables. A familiar example is provided by crypto arithmetic puzzles. It insist that each letter in a crypto arithmetic puzzle represent a different digit. Higher-order constraints can be represented in a constraint hypergraph. Such as shown below,

**Example 1 -**The crypto arithmetic problem. (A CSP problem having high order constraints)

**Example 2 -**Explain the constraint satisfaction procedure to solve the crypto arithmetic problem.

Solution: (At each step minimum possible value is selected.)

General Algorithm for Finding Solution in CSP

Propagate available constraints Ø Open all objects that must be assigned values in a complete solution. Ø Repeat until inconsistency or all objects are assigned valid values: Select an object and strengthen as much as possible, the set of constraints that apply to object. If set of constraints are different from previous set, then open all objects that share any of these constraints. Remove selected object. v If union of constraints discovered above defines a solution then return solution. v If union of constraints discovered above defines a contradiction then return failure. v Make a guess in order to proceed. Repeat until a solution is found or all possible solutions exhausted; Ø Select an object with a no assigned value and try to strengthen its constraints. Ø Recursively invoke constraint satisfaction with the current set of constraints plus the selected strengthening constraint.

CSP Representation as a Constraint Graph

The CSP can be represented in terms of the constraint graph. A constrain graph has,

Nodes as variables (For example-In graph-colouring problem the vertex is variable which needs to be coloured. This vertex will be a node in constraint graph.) v Arcs as a constraints (For example-In graph-colouring problem the arc will denote that no two adjacent vertices will have same colour.) Advantages of Constraint Graph v The organization of constraint graph is very much useful for simplification of CSP's solutions. v It reduces complexity in exponential manner.

Backtracking Search

If we apply BFS to generic CSP problems then we can notice that the branching factor at the top level is 'nd', because any of ' 𝑑 ' values can be assigned to any of ' 𝑛 ' variables. At the next level, the branching factor is '( n − 1)d ' and so on for n levels. Therfore a tree with ' 𝑛!

• 𝑑^𝑛 leaves is generated even though there are only ' 𝑑^𝑛 ' possbile complete assignments.

Basic Steps in Backtracking Search

Depth-first search selects values for single variable at a given time. v Apply constraint to the variable when variable is selected. v Backtracking action-performed if a variable has no legal values left to assign. v Backtracking search is basic uninformed algorithm for CSPs.

Backtracking Search Algorithm