Search Control

Search control determines what transformations are made from what states.
- Assume a deterministic recoverable problem, in an accessible static environment.
- Take simple approach, expanding all ways from a chosen state (recall production systems discussion)
- These control strategies are applicable, to various degrees, to more complex environment and problem characteristics.
- Definitions
  - Search space layers numbered from 0
  - D = depth of goal
  - maxD = depth of search space
- Performance criteria for strategies
  - Time complexity - how long will it take
  - Space complexity - how much memory is used
  - Completeness - the search will find an answer if one exists.
  - Optimality - quality of solution, where cost is the number of transformations, or sum of transformation costs.
  These are computed below for the worst case.
- Information
  - Uninformed strategies have no heuristic measuring the quality of a state in terms of its closeness to a goal.
  - Informed strategies have a function h(S) that estimates the distance from state S to a goal state.
  - When searching for a best solution it is necessary to have a function g(S) that gives the cost of the sequence of transformations to state S (often the sum of transformation costs).
Uninformed, any solution.
- The game
  - No quality for states
  - No cost for transformations
  - Optimality is number of transformations.
  - Example
```
       ------  1  -----
      /        |        \
    2          3         4
  /  |  \     / \       / \
 5   6   7   8   9    10   11  
     |
     12 - goal  
               
```
- BFS
  - Will find a solution if a finite one exists.
  - Will find the shortest path to a solution.
  - Requires a lot of storage
  - Requires a lot of work following wrong paths
  - Example: 1,2,3,4,5,6,7,8,9,10,11,12
  - T-S-C-O = B^D-B^D-Yes-Yes
- DFS
  - Example: 1,2,5,6,12 (7,3,8,9,4,10,11)
  - T-S-C-O = B^maxD-B*maxD-No-No
- Interative deepening (level saturation)
  - This does a complete DFS in the graph down to a certain level. If no goal is found, the level is increased and the search restarted.
  - The maths shows that this is not too expensive
  - Example (increase = 1):
    1
    1,2,3,4
    1,2,5,6,7,3,8,9,4,10,11
    1,2,5,6,12 (7,3,8,9,4,10,11
  - T-S-C-O = B^D-B*D-Yes-Yes
Uninformed, best solution
- The game
  - Transformations have cost
  - The cost so far is g(S) for state S.
  - Example
```
       ------A------
    4/       |6      \5
    B        C        D
 2/   \1     |4     8/ \5
 E     F     G      H   I
1|      \4              |10
 J!      K!             L!
               
```
- British museum procedure.
  - Uses an exhaustive "find any path" search and retains the best throughout.
- Branch and bound
  - Expand the node with least g(S), until a goal G is found and all other g(S) exceed the least g(G).
  - Example:
    A(0)
    A-B(4),A-D(5),A-C(6)
    A-D(5),A-B-F(5),A-C(6),A-B-E(6)
    A-B-F(5),A-C(6),A-B-E(6),A-D-I(10),A-D-H(13)
    A-C(6),A-B-E(6),A-B-F-K(9!),A-D-I(10),A-D-H(13)
    A-B-E(6),A-B-F-K(9!),A-D-I(10),A-C-G(10),A-D-H(13)
    A-B-E-J(7)!,A-B-F-K(9!),A-D-I(10),A-C-G(10),A-D-H(13)
  - If all costs are equal this is a BFS.
  - T-S-C-O = B^D-B^D-Yes(if costs are +ve)-Yes
- Branch and Bound with dynamic programming (Dijkstra's algorithm)
  - If two diffent paths to any state are found, then only keep the cheapest.
  - A to Z example
Informed, any solution
- The game
  - States have quality = estimated cost to goal
  - The estimate is h(S) for state S. If h(S) is an underestimate, it is admissible.
  - Optimality is number of transforms
  - Transform from the frontier state that seems closest
  - Example: (node=h(S))
```
       ------ A=8 -----
      /        |        \
    B=7       C=4       D=9
  /  |  \     / \       / \
E=6 F=4 G=7 H=5 I=8   J=7  K=6
     |
    L=0
               
```
- Hill climb
  - Keep best new state, only if better or equal to parent state
  - Example: A,C, stop no solution
  - Problems
    - Local maxima
    - Plateaus
    - Ridges - none of the available transformations lead to a better state, but a combination will.
  - Solutions
    - Backtracking to almost as good previous nodes.
    - Big jumps in arbitary directions (recall this folks?)
    - Avoid the test for several steps
  - T-S-C-O = D(or maxD if failed)-D(or 1 if discarding path)-No-No
- Modified Hill Climbing
  - Keeps all equal or better states in order, i.e., assumes monotonicity of estimate.
  - Example:
    A(8)
    A-C(4),A-B(7)
    A-B(7)
    A-B-F(4),A-B-E(6),A-B-G(7)
    A-B-F-L(0),A-B-E(6),A-B-G(7)
  - T-S-C-O = B^maxD-B^maxD-No-No
- Beam
  - Keep N best nodes are retained at each level. All are expanded at each iteration.
  - Generalises hill climbing.
  - Example (N=2):
    A(8)
    A-C(4),A-B(7)
    A-B-F(4),A-C-H(5)
    A-B-F-L(0)
  - T-S-C-O = N^maxD-N*maxD(or N if discarding path)-No-No
  - Note lowered branching factor
- Best first search
  - This extends the hill climbing/beam search to keep all achieved states.
  - A continuously re-ordered agenda is a way to organise currently attained states.
  - Example:
    A(8)
    A-C(4),A-B(7),A-D(9)
    A-C-H(5),A-B(7),A-C-I(8),A-D(9)
    A-B(7),A-C-I(8),A-D(9)
    A-B-F(4),A-B-E(6),A-B-G(7),A-C-I(8),A-D(9)
    A-B-F-L(0),A-B-E(6),A-B-G(7),A-C-I(8),A-D(9)
  - A-Z example, with DP on path length
  - T-S-C-O = B^maxD-B^maxD-Yes(if h is admissible)-No (T & S are worst case)
Informed, best solution
- The game
  - Example:
```
       ---- A=4 ----
    4/       |6      \5
    B=3      C=9      D=1
 2/   \1     |4     8/ \5
 E=1   F=1   G=9    H=9 I=5
1|      \4              |10
 J!      K!             L!
               
```
- A*
  - Combines branch-and-bound with best-first search by adding the distance so far (g(S)) to an under-estimate of the distance to the goal (admissible h(S)). This improves efficiency but does not lose completeness.
  - First found may not be best, due to underestimates. Like branch and bound, search must continue.
  - Example. Underestimate by half:
    A(0+4)
    A-D(5+1),A-B(4+3),A-C(6+9)
    A-B(4+3),A-D-I(10+4),A-C(6+9),A-D-H(13+9)
    A-B-F(5+1),A-B-E(6+1),A-D-I(10+4),A-C(6+9),A-D-H(13+9)
    A-B-E(6+1),A-B-F-K(9+0)!,A-D-I(10+4),A-C(6+9),A-D-H(13+9)
    A-B-E-J(7+0)!,A-B-F-K(9+0)!,A-D-I(10+4),A-C(6+9),A-D-H(13+9)
  - T-S-C-O = B^maxD-B^maxD-Yes-Yes (T & S are worst case)
  - If the cost of transformations is 0 we want the quickest solution and get a find any path solution.
    - If the estimate of the cost to a goal is 0, the search is non-deterministic, but implementation could lead to DFS or BFS.
    - If the estimate of the cost to a goal is heuristic we get best first search, with dynamic programming.
  - If the estimate of the cost to a goal is always 0 we get a find the best path solution.
    - If the cost of transformations is 1 we get BFS.
    - If the cost of transformations measures the cost of getting here so far we get branch and bound.
- A* with dynamic programming
  - If two diffent paths to any state are found, then only keep the cheapest.
  - A to Z example

Classification of Search Control Categories

Search strategies may be categorised according to the tree below.

                      / \
heuristics and       yes no
tranformation costs /     \
                   / \      A
domain specific  yes  no
                 /     \
                / \     \
   perfect    yes  no    \
              /     \     \
             B     / \   / \
 admissible      yes no yes no
                  |  |   |  |
                  C  D   E  F

Class A - ignorant search
- Unintelligent 'syntactic', 'systematic' search strategies. These are easy to use and measure the effectiveness of.
- Examples are :
  - Depth First Search
  - Breadth First Search
  - Iterative deepening.
Classes B to F - heuristic search.
- A heuristic function evaluates the quality of a given state (closeness to a goal state ?+ distance so far), and the value is used by the control strategy to select the state to transform from.
- The measured closeness of a state to a goal may be dynamic and dependant on the search, e.g. how many times that state has been reached. Negative changes may also take place.
- The more accurate the heuristic function the more direct the search will be.
- Problems of:
  - Measuring a strategy, is it possible and how much work does it require? Is it of utility?
  - What is the effect of non-structured stategies?
Class B, C & D
- Heuristics specific to a domain, e.g. semantic checking. These method know what objects the symbols structures in the states designate.
Class E & F
- General purpose heuristics, e.g. unit preference strategy.
- Note that these non-domain specific strategies are hypothsised to never be perfect - this I cannot prove.
Class B - strong methods
- Very intelligent, if the problem is in fact exponentially hard.
- No search is required.
- Most algorithms used in computing science are strong methods, e.g. solution of linear equations.
Classes C to F - weak methods
- Methods that may reduce combinatorial explosion by guidance through the search space, not prevent it.
- Methods that prune the search space, without loss of completeness - very desirable. e.g. semantic deletion.
- Methods that prune the search space, but with loss of completeness - less desirable, possibly useless. e.g. complexity limits on data.
Class C & E
- Complete search methods that should exibit intelligence. If a solution exists, it will be found.
- Examples are :
  - Branch and bound
  - A*
Class D & F
- These methods may exibit intelligence, but may also fail to find a (best) solution when one exists by ignoring good paths which initially look bad.
- Examples are:
  - Hill climbing
  - Beam search
  - Best first

Exam Style Questions

What are the four criteria for measuring the performance of a search control strategy? What fifth criteria is typically assumed for production systems?
List the order in which the states are expanded in the following state space, using a <place search strategy name here> search control strategy.
```
PICTURE OF STATE SPACE GOES HERE - MAKE ONE UP YOURSELF 
```
Give the Time-Space-Completeness-Optimality measures for the <place search strategy name here> search strategy.
Explain how the A* strategy can be used to implement a best first search, BFS, and branch & bound search.
Differentiate between:
- informed and uninformed search
- weak and strong methods
- domain specific and non-domain specific heuristics