0%

# Problem Solving and Search

## Environment Types

• Accessible
• Deterministic
• Episodic
• Static
• Discrete

## Problem Types

• single-state problem
• deterministic, accessible
• agent knows the exact state
• can calculate optimal action on sequence to reach goal state
• multiple state problem
• deterministic, inaccessible
• Agent does not know the exact state
• Assume states while working towards goal state.
• contingency problem
• nondeterministic, inaccessible
• must use sensors during execution (could be in any of the possible states)
• solution is a tree or policy
• often iterative search and execution
• exploration problem
• unknown state space

## Problem Formulation

a problem is defined by four items

• initial state
• operators
• goal test
• path cost

for more detailed implementation,

## Node and State

Know the difference between state in state-space and tree node in a search tree, they are Different! `p58 in 02-04`

A state is a representation of physical configuration.

A node is a data structure, which includes `parent`, `children`, `depth`, `path` and `cost(g)`, and expanded by some kind of `EXPAND` function.

Analyze

• Completeness
• Time complexity
• Space complexity
• b - max branching factor
• d - depth of the least-cost solution
• m - max depth of the search tree
• optimality

# Uninformed Search

Enqueue expanded (children) nodes to the back of the queue (FIFO order)

Analyze

• Completeness: yes, if b is finite
• Time: O(b^d)
• Space: O(b^d)
• Optimality: yes, assuming cost = 1 per step

## Uniform Cost Search (UCS)

The queuing function keeps the node list sorted by increasing path cost, and expand the first unexpanded node (hence with smallest path cost)

Analyze

• Completeness: Yes, if step cost > 0
• Time: # nodes with g <= cost of optimal solution, <= O(b^d)
• Space: # nodes with g <= cost of optimal solution, <= O(b^d)
• Optimality: Yes, as long as path cost never decrease ?

### Problem

Uniform-cost search not optimal if it is terminated when any node in the queue has goal state.

Here is the example

### Improved UCS

refine the queuing function for optimal search, queue-up node if

• Its state does not match the state of any parent
• path cost smaller than path cost of any unexpanded node with same state in the queue

here is the codes in `[...]`

## Depth-First Search (DFS)

Enqueue expanded (children) nodes to the front of the queue (LIFO order)

Analyze

• Completeness: no ? infinite state space / yes ? finite state space
• Time: O(b^m)
• Space: O(bm)
• Optimality: No

A depth-first search with depth limit `l`

Analyze

• Completeness: yes
• Optimality: No

Analyze

• Completeness: Yes,
• Time: O(b^d)
• Space: O(bd)
• Optimality: Yes, if step cost = 1

Iterative deepening is preferred to depth-first or breadth-first when search space large and depth of solution not known

## Comparing Uninformed Search Strategies

Type TimeO SpaceO Optimal Complete
BFS O(b^d) O(b^d) Yes Yes
UCS O(b^d) O(b^d) Yes Yes
DFS O(b^m) O(bm) No No
DIS O(b^l) O(bl) No Yes, if I >= d
IDS O(b^d) O(bd) Yes Yes

# Informed Search

Use heuristics to guide the search

• Idea: use an evaluation function for each node, estimate of “desirability”
• Queuing function: Insert successors in decreasing order of desirability
• Special cases:
• Greedy search
• A* search

Estimation function: h(n) = estimate of cost from n to goal (heuristic)

Analyze

• Complete: No, can get stuck in loops
• Complete in finite space with repeated-state checking.
• Time: O(b^m), but a good heuristic can give dramatic improvement
• Space: O(b^m), keeps all nodes in memory
• Optimal: No.

A* search uses an admissible heuristic

`f(n) = g(n) + h(n)`

• `f(n)` is the estimated total cost through n to the goal.
• `g(n)` is the cost so far to reach n
• `h(n)` is the estimated cost from n

Analyze

• Complete: Yes, unless infinitely many nodes with f <= f(G)
• Time: Exponential in `[(relative error in h) x (length of solution)]`
• Space: Keeps all nodes in memory
• Optimal: Yes – cannot expand fi+1 until fi is finished

### F(n) Increment

A* expands nodes in order of increasing f value.

so when traversing the node, `f'(n) = max (g(n')+h(n'), f(n))`

Iteratively maximize “value” of current state, by replacing it by successor state that has highest value, as long as possible.

here is the pseudo code

weakness: can only find the local minimum/maximum

## Simulated Annealing

Boltzmann distribution

P(A)/P(B) = exp((E(A)-E(B))/T) = exp(E(B)/T)/exp(E(A)/T)

Case ΔE ΔE/T exp(ΔE/T) accept bad move
T is large <0 <0, very small close to 1 high probability
T is small <0 <0, very large close to 0 low probability

# Game playing

## Basic Concepts

• Initial state
• Operators
• Terminal state
• Utility function: AKA payoff function

## The Minimax Algorithm

Minimize opponent’s chance and thus? maximize your chance

Pseudo code of minimax algorithm

Statistic

• Complete: Yes, for finite state-space
• Optimal: Yes
• Time Complexity: O(b^m)
• Space Complexity: O(bm)

## Resource Limitations

• Evaluation function: evaluates value of state using heuristics and cuts off search
• Using new minimax
• CUTOFF-TEST: cutoff test to replace the termination condition
• EVAL: evaluation function to replace utility function

Note: exact values do no matter, only the order matters.

## Alpha-beta Pruning

• prune portions of the search tree that cannot improve the utility value.
• pruning does not affect the final result.
• time complexity: O(b^(m/2)) if perfect

## Elements Of Chance

expectimax and expectimin, expected values over all possible outcomes. In this way, order-preserving transformation do not necessarily behave the same!

# Constraint Satisfaction

## Constraint Satisfaction Problems (CSP)

• Variables
• Domains
• Constraints
• Consistent
• Complete

### Varieties of CSPs

• Discrete variables
• finite domains
• infinite domains
• Continuous variables

• Unary
• Binary
• Higher-order

## Backtracking Search For CSPs

Depth-first search for CSPs with single-variable assignments is called
backtracking search

### Improved Backtracking

• choose the variable with the fewest legal values
• choose the variable with the most constraints on remaining variables

### Arc Consistency

• node-consistent: all the values in its domain satisfy the variable’s unary constraints
• arc-consistent: every value in its domain satisfies the binary constraints