# COMP7404 Computational Intelligence and Machine Learning

## Topic 2 Beyond Classical Search

**Planning vs Identification**

- Planing: sequence of actions
- The path to the goal is the important thing
- Paths have various costs, depths
- Heuristics to guide, frontier to keep backups

- Identification: assignments to variables
- The goal itself is important, not the path

*Local Search can find solutions faster for specific types of identification problems*

**Local Search**

- Evaluate and modify one current state rather than systematically explore paths from an initial state
- Suitable for problems were all that matters in the solution state and not the path cost to reach it
- Although local search algorithms are not systematic they have two advantages
- Require very little memory
- Often find reasonable solutions in large spaces

**Local Search Algorithm**

```
Randomly initialize currentState
If cost of currentState == 0 return currentState
If min(cost(getNeighbors(currentState))) > cost(currentState)
goto step 1 (we have reached a local minimum)
Select cheapest neighbor as currentState and goto step2
```

**Example: 8-Queens**

- States
- Each state has 8 queens on board, one per column

- Successors
- All possible states generated by moving single queen to another square in the same column

- Cost function
- Number of pairs of queens that are attacking each other, either directly and indirectly

**Constraint Satisfaction Problems**

CSPs use a factored representation for states

- A set of variables, each of which has a value

**Defining CSPs**

- A CSP consists of three components
- A set of variables, X = {X1,…,Xn}
- A set of domains, D = {D1,…,Dn}, where Di = {V1,…,Vk} for each variable Xi
- A set of constraints C which specify allowable combinations of values

- To solve a CSP we need to define a state space
- Each state is defined by an assignment of values to some or all variables {Xi = Vi, Xj = Vj,…}

**Solving CSPs**

- States are defined by the values assigned so far
- Initial state
- Empty assignment {}

- Successor function
- Assign a value to an unassigned variable

- Goal test
- Current assignment is complete and consistent

**Solutiona to CSPs**

- Consistent - No constraints are violated
- Complete - Every variable is assigned

**Backtracking Search (The basic algorithm for solving CSPs)**

Idea

- Only consider assignments to a single variable at each point
- Only allow legal assignemnts to each point

DFS with these two ideas is called backtracking search

**Improving Backchecking**

Idea

- Forward checking (FC)
- Constraint propagation (AC-3)

**Filtering: Forward Checking**

- Filtering
- Keep track of domains for unassigned variables and cross off bad options

- Forward checking
- Cross off values that violate a constraint when added to the existing assignment

**Improving Backtracking Further**

- Variable Ordering
- Minimum remaining values (MRV)
- Choose the variable with the fewest legal left values in its domain
- Most constraint variable
- Fail-first heuristic

- Tie-breaker among MRV variables
- Degree Heuristic (Deg)
- Choose the variable with the most constraints on remaining variables

- Degree Heuristic (Deg)

- Choose the variable with the fewest legal left values in its domain

- Minimum remaining values (MRV)
- Value Ordering
- Least constraining value (LCV)
- Choose the value that rules out the fewest values in the remaining variables

- Least constraining value (LCV)