Chapter 3

PROBLEM SOLVING AND SEARCH

            There is a 4l container and 3l container ; neither has any measuring markers on it. There is a pump that can be used to fill the containers with water.Problem to solve is to get exactly two liters of water in the 4l container.

        From initial state to goal state through appropriate sequence of moves or actions    such
        as filling and emptying the containers.

Content of the two containers at any given time is a problem state

        Then (x,y) - problem state represented by an ordered pair.
        The set of all ordered pairs is the space of problem states or the state-space of the
         problem .
 
        State-space :  { (x,y) | x = 0,1,2,3,4  y=0,1,2,3 }
 
        Data structure to represent the state-space can be

• vectors
• sets
• arrays
• lists
• etc

                  initial state (0,0)
                  goal state   (2,y) where y = any possible number.

     Moves transform from one state into another state.
     Operators determine the moves.
 
     Operators for the problem state-space :

1.   Fill the 4l container
2.   Fill the 3l container
3.   Empty the 3l container
4.   Empty the 3l container
5.   Pour water from 3l container into 4l conatiner until 4l container is full
6.   Pour water from 4l container into the 3l container until the 3l container is    full
7.   Pour all the water from 3l container into the 4l container
8.   Pour all the water from 4l container into the 3l container

     R1 IF (x,y| x?4) THEN (4,y)
     R2 IF (x,y| y?3) THEN (x,3)
     R3 IF (x,y| x>0) THEN (0,y)
     R4 IF (x,y| y>0) THEN (x,0)
     R5 IF (x,y| x+y>=4 ? y>0 ? x?4) THEN (4,y-(4-x))
     R6 IF (x,y| x+y>=3 ? x>0 ? y?3) THEN (x-(3-y),3)
     R7 IF (x,y| x+y?=4 ? y>0) THEN (x+y,0)
     R8 IF (x,y| x+y?=3 ? x>0) THEN (0,x+y)

In certain states, more than one rule can be applied.
 
  e.g:
      (4,0) satisfies the preconditions of R2,R3 ? R6

3.1.1 Control or Search Strategy :
     Selecting rules; keeping track of those sequences of rules that have already been tried   and the states produced by them.

      Goal state provides a basis for the termination of the problem solving task.

1- PATTERN MATCHING STAGE
     Execution of a rule requires a match.
 
  preconditions               match              content of
  of a rule                    <=====>         the working memory.
 

 when match is found  => rule is applicable
 several rules may be applicable

2- CONFLICT RESOLUTION (SELECTION STRATEGY ) STAGE
     Selecting one rule to execute;

3- ACTION STAGE
  Applying the action part of the rule => changing the content of the workspace
 
  =>new patterns,new matches => new set of rules eligible for execution

  Recognize -act control cycle

3.1.2 Production System

    1. Content of workspace => candidate rules for execution (search strategy )
    2. Each rule surveys the entire workspace
    3. A rule activates itself when its condition matches the content of the workspace

Adv : Adding, deleting, revising rules without disturbing the rest of the system.

Water Container Problem

 PRODUCTION RULES                                                                    FACTS IN WORKING MEMORY
 IF (x<4) THEN FILL x                                                                                         (4,y)
 IF (y<3) THEN FILL y                                                                                         (x,3)
 IF (x>0) THEN EMPTY x                                                                                   (0,y)
 IF (y>0) THEN EMPTY y                                                                                    (x,0)
 IF (x+y>=4  AND  y>0)  THEN FILL x FROM y                                            (4,y-(4-x))
 IF (x+y>=3  AND  x>0)  THEN FILL y FROM x                                            (x-(3-y),3)
 IF (x+y<=4  AND  y>0)  THEN FILL x FROM y                                            (x+y,0)
 IF (x+y<=3  AND  x>0)  THEN FILL y FROM x                                            (0,x+y)
 
 
PRODUCTION SYSTEM

 no information is available to judge that one rule is better than the rest of the applicable rules

=>systematic search of the state-space is necessary for finding a solution.
=>no information which action is better than the others
=>no information on the progress towards solutio
   blind search (exhaustive search) is being done.

when number of states is high it is not an efficient method.

 3.1.3 Standard Terminology 
 
State j is an immediate successor of state i.
State i is a successor of state k.
All states that can be reached from initila state are search space.
Each intermediate state generates an exhaustive set of successors.

Exhaustive search leading to combinational explosion .To prevent combinational explosion, information at each intermediate state to identify which immediate successor is most promising.

Blind search,exhaustive search,uninformed search mean the same thing.
 

 All immediate successor states are sorted using heuristic information.The sort function is called the (heuristic) evoluation function.
 
 Tree             : a directed graph
 root              : a node with no pedecessor
 leaves          :  nodes with no successors
 branches      : links between nodes
 
• no node has ,as its successor, a node which is also its predessor.
• each node has a level (called depth)
• root has the depth of 0
Search tree shows the paths that have currently been explored in a state space.

open node : node that has not yet been examined for possible expansion
closed node : node that has already been examined and expanded.

search technique =>the order in which the open nodes are to be expanded. 
 
Partial Search Graph for Water Container Problem
 

 3.3.1 Depth First Search:

   Search proceeding in the parent-to children direction untill forced to backtrack.(stopping search in one direction, going back to the previous node and expand in a new direction. )
 
   Open nodes are ordered in descending order of their depth in a search tree(deepest node at the front of the list ).
 
   Such structure is stack data structure(LIFO).
  
 

•  nodes already on the closed list is not added to the open list to avoid recycling.
 
  3.3.2 Breadth First Search:
 
   Nodes are examined level by level. Open nodes are ordered in ascending orderof their depth (nodes at the lowest level of the depth are at the front of the queue) FIFO structure. 

  3.3.3 Heuristic Search:
   Uninformed search eventually finds a solution to the problem but, with large problem spaces these methods are not feasible due to the problem of combinational explosion.
 
    A search which uses information about the current situation to traverse a search tree is called heuristic search.

   Organization of the heuristic search :
 
  1) Ordering of successors ( most promising successors are expanded first )  A* algorithm .
      Evaulation function, h , is used which measures the cost of going from the node to the goal node.Approximation of h* is used.

      g*(i)=g(i)+h*(i)  for any node i.
      g*(j)=g(i)+c(i,j)+h*(j) for all successors, j , of i.