Week 1: Agents and Environments
PEAS: Performance measure, Environment, Actions, Sensors
Classifying Environment Type (vs)
Agents:
Simple Reflex (Reactive) Model-Based (Reflex) Planning
No past, no future Past, no future Past, future
Goal-Based (Teleological) Utility-Based (Happiness) Game Playing Learning
May involve search/plan Uses utility function World and opponent model
Week 2: Uninformed Search
A state space problem consists of: a state space, start state, set of actions, action function,
goal state, and path cost.
Uninformed Search methods:
, Week 3: Informed Search and Constraint Satisfaction Problems
Informed Search methods: All implemented using a priority queue.
A* Search = g(n) + h(n) = Uniform-cost search + Greedy search
Even after a goal node has been generated, A* will keep searching so long as there is a possibility of finding a
short solution. Once a goal node is selected for expansion, we know it must be optimal.
If h is not consistent but still admissible then A* admissibility is not guaranteed.
An admissible heuristic never overestimates the cost to reach the goal.
A heuristic is consistent if h(n) ≤ c(n, n’) + h(n’) where n’ is the successor of n.
A heuristic h1 is better than h2 if it means less nodes expanded (and therefore less time/memory) which happens
if h1(n) ≥ h2(n) for all n.
Constraint Satisfaction Problem methods:
Backtracking search: assign variables one by one, whenever a constraint is violated, go
abc to the most recently assigned variable and assign it a new value.
Improve backtracking search with:
1. Minimum remaining values (MRV): choose the variable with the fewest legal values
2. Degree heuristic: tie-breaker among MRV variables. Choose the variable with the
most constraints on remaining values
3. Least constraining value: choose the value that rules out the least values in the
remaining variables
4. Forwarding checking: keep track of remaining legal values for unassigned variables,
terminate search when any variable has no legal values, and backtrack.
5. Arc consistency: make each arc consistent i.e. for every x of X there is some allowed
y of Y for a function X → Y.
Variable elimination: combine tables where X appears to remove X and simply the
problem.
PEAS: Performance measure, Environment, Actions, Sensors
Classifying Environment Type (vs)
Agents:
Simple Reflex (Reactive) Model-Based (Reflex) Planning
No past, no future Past, no future Past, future
Goal-Based (Teleological) Utility-Based (Happiness) Game Playing Learning
May involve search/plan Uses utility function World and opponent model
Week 2: Uninformed Search
A state space problem consists of: a state space, start state, set of actions, action function,
goal state, and path cost.
Uninformed Search methods:
, Week 3: Informed Search and Constraint Satisfaction Problems
Informed Search methods: All implemented using a priority queue.
A* Search = g(n) + h(n) = Uniform-cost search + Greedy search
Even after a goal node has been generated, A* will keep searching so long as there is a possibility of finding a
short solution. Once a goal node is selected for expansion, we know it must be optimal.
If h is not consistent but still admissible then A* admissibility is not guaranteed.
An admissible heuristic never overestimates the cost to reach the goal.
A heuristic is consistent if h(n) ≤ c(n, n’) + h(n’) where n’ is the successor of n.
A heuristic h1 is better than h2 if it means less nodes expanded (and therefore less time/memory) which happens
if h1(n) ≥ h2(n) for all n.
Constraint Satisfaction Problem methods:
Backtracking search: assign variables one by one, whenever a constraint is violated, go
abc to the most recently assigned variable and assign it a new value.
Improve backtracking search with:
1. Minimum remaining values (MRV): choose the variable with the fewest legal values
2. Degree heuristic: tie-breaker among MRV variables. Choose the variable with the
most constraints on remaining values
3. Least constraining value: choose the value that rules out the least values in the
remaining variables
4. Forwarding checking: keep track of remaining legal values for unassigned variables,
terminate search when any variable has no legal values, and backtrack.
5. Arc consistency: make each arc consistent i.e. for every x of X there is some allowed
y of Y for a function X → Y.
Variable elimination: combine tables where X appears to remove X and simply the
problem.
