Problem-Solving Agent
Agent that can look ahead to find a sequence of actions that will (eventually) achieve its goal
Problem-Solving Process
(4 phases)
Goal Formulation
Goals organize behavior (limit objectives + limit actions to be considered)
Problem Formulation
Description of states & actions needed to reach goal (abstract model: relevant part of world)
Search
Simulation of action-sequences (until sequence is found that reaches goal)
Execution
Agent can execute actions in the solution (one at a time)
Provide
for the Route-Planning Search Problem
Route Planning
Goal Formulation:
Go from starting point A to B, possibly with (shortest, fastest, gas saving, …) path
Problem Formulation:
States: Locations, Time, …
Actions: Driving left, right, …
Possibly: Cost assigned to actions (time, distance, fuel, …)
Definition of a Search Problem:
4-tuple: <S, R, s0, G>
Search Problem 4-tuple: <S, R, s0, G>
S = Search/State Space
R = Successor/Transition Relation (R c S x S)
s0 = Initial State (s0 ∈ S)
G = Goal Predicate that terminates Search (G: S —> {true, false}
(Possibly: Transition Cost)
Definition of a Solution
A solution to a search problem is a sequence of states starting with initial state (s0) with adjacent states in the transition relation ( (si, si+1) ∈ R for i = 0, …, n-1) and ending at a goal state or G(sn) = true
Aim of a general Search “Algorithm”
Algorithm takes search problem as input and returns solutions (or failure indication).
This can be done by creating a search tree over the search-space graph, forming paths from initial states, trying to find path that reaches goal state.
State-Space Graph
State-Space Graph is represented as a graph in which:
nodes = states
directed edges = actions
directed graph and more abstract
(Search tree is an expansion to it)
Search Tree
each node corresponds to a state in the state space
edges = actions
root = initial state of the problem
strictly hierarchical, no backward-going
at each node, you know exactly what path you took
State-Space Graph vs Search-Tree
Sketch of a Search-Algorithm
Generate a search tree:
Start with s0 as root
Add successors to leaf-state si for all transitions (si, sj) ∈ R
A path from the root s0 to a node s in the tree with G(s) = true is a solution
Traverse search tree to collect the solutions
—> Different ways to traverse the Search Tree = Different Search Algorithms
Classical Search
Uninformed (Blind)
Uninformed Search (Blind Search)
Random Search
Systematic Search
Depth-First Search (DFS)
Breadth-First Search (BFS)
Variations
Uniform-Cost Search
Depth-Limited Search
Features:
No information about path cost from current- to goal state
Informed (Heuristic)
Informed Search (Blind Search)
Greedy Best-First Search
A*-Search
Heuristic information (estimate) about path cost from current- to goal state
(there’s an estimate at each state |on what I base my actions on)
From Classical to Local Search
find (optimal) sequence of actions
Sequence might be irrelevant
that leads from initial state
Might not exist
to a goal state
Might be hard to test
Local Search
find “nearly” feasible / optimal state
(more state-based rather than globally-based)
When is Local Search applied?
Local Search is applied if search spaces are too big for exhaustive search.
Problem Types for Local Search:
Typical problem types are:
CSPs
(Discrete) Optimization Problems
Production Planning (maximize profit)
Scheduling (minimize conflicts)
Machine Learning (minimize classification error)
Local Search:
States and Neighborhoods
States correspond to Variable Assignments
Neighborhood: which assignments can be reached from given one
Local Search main Ideas
Idea:
Start from initial assignment …
… select “promising” neighbor of the current assignment
—> continue selecting neighbors until we cannot improve anymore (goal/solution)
How to solve Local Search Problems?
Solving Local Search Problems
Define State Space
Define Neighborhood
Define Objective Function (tells how good state is depending on preferred goal)
—> minimize f(x) by maximizing -f(x)
Apply Local Search Algorithm
Applying Local Search to n-Queens Problem
State-Space
Neighborhood
Objective Function
n-Queens Problem
State-Space:
board configuration with 1 queen per column
Neighborhood:
configurations that can be obtained by moving a single queen to another field in the same column
Objective Function:
number of pairs of queens that can attack each other directly or indirectly (maximize negative objective function)
When is local search better suited than classical search?
If we’re only interested in a solution and not in its path —> Local Search can be better suited than Classical Search
—> used for optimization and CSPs
What is the simplest form of Local Search?
Gradient Ascent
we want to maximize real function f(x) = objective function
we start from random point and follow ascent direction (gradient ascent algorithm)
Hill-Climbing
Hill- Climbing
regarded as discrete state-space version of gradient ascent
in each step: select neighbor with highest value
Discrete State Spaces
instead of continuous curve —> seperate points
we often consider finite state spaces
Problem: state space is usually exponentially large (large to explore)
Continuous Space vs Discrete Spaces
Continuous Space (e-neighborhood)
infinite number of neighbors
gradient gives direction of steepest ascent
Discrete Space (discrete neighborhood)
often finite number of neighbors
best neighbor can be difficult to find (enumeration)
Hill-Climbing Algorithm
Hill Climbing
Termination Conditions
Termination Conditions (Hill Climbing)
can be bound to the maximum number of steps / search time
algorithm may end up in non-global local maximum / plateau
Steps of solving Local Search Problems
- Hill Climbing -
Solving Local Search Problems with Hill-Climbing
Define State-Space
Define Neighborhood (or actions that lead to it, e.g. transition function)
Define Objective Function (minimize f(x) by maximizing -f(x))
Apply Hill Climbing Algorithm
Steps of solving the 8-Queens Problem
State-Space: board configurations with one queen per column
Neighborhood: configurations that can be obtained by moving a single queen to another field in the same column (transition function)
Objective Function: number of pairs of queens that can attach each other (in)directly (—> maximize negative objective function)
If we reach only locally optimal state —> change neighborhood size (minimize it)
Tradeoff:
Small Neighborhood versus Large Neighborhood
Small Neighborhood
faster exploration of neighborhood (less objective functions have to be calculated)
greater risk of getting stuck in local optimum
Large Neighborhood
slower exploration of neighborhood
smaller risk of getting stuck in local optimum
Downsides of Hill Climbing + Variants
Variants of Hill Climbing
Hill Climbing is a greedy local search algorithm
Hill Climbing can perform poorly because high risk of ending up in non-global local maxima
Variants can alleviate the problem
Stochastic Hill Climbing
First Choice Hill Climbing
Random Restart / Parallel Hill Climbing
Hill Climbing never makes downhill moves (why it’s called greedy), but sometimes they can be necessary to find global optimum
instead of selecting neighbor with maximum value, we select random neighbor that improves value
Probability of selection can increase with value
compromise between Random Search and Hill Climbing
in neighbor selection step, pick first neighbor that improves objective function
(also useful if neighborhood is too large to enumerate all neighbors)
perform n independent hill-climbing searches starting from randomly generated initial states
(as n goes to infinity, probability of finding global optimum goes to 1 —> almost covers state space as initial value)
Simulated Annealing
chooses states that are not always better than the current
Initially: large probability for downhill moves (Exploration)
Search Progresses: probability decreases (Intensification)
Process is modelled by a Temperature Variable that decreases
—> Simulated Annealing is similar to Random Exploration for high temperatures and similar to First-Choice Hill Climbing later
(when T is high, I don’t care about value of the state)
Simulated Annealing Algorithm
Cooling Schedule
Cooling Schedule Simulated Annealing
schedule(t) controls temperature decrease
Scheduling Schemes:
Stepwise Linear: start with arbitrary T and decrease T by a constant c in each step
Delayed Stepwise Linear: start with arbitrary T and decrease T by a constant c every k-th step
Slow Cooling Schedule increase probability of finding a high-quality solution but increases runtime + computational costs
= more exploration (the slower the temperature will be cooled down)
Neighbor Selection
Neighbor Selection (Simulated Annealing)
In each step, SA picks random neighbor
if neighbor improves objective, neighbor replaces current state
otherwise, it replaces current state only with probability exp(ΔE/T), where ΔE = value(next) - value(current)
—> ΔE and T both control exploration and intensification
Neighbor Selection: ΔE
ΔE is always non-positive in else-branch
—> 0 <= exp(ΔE/T) <= exp(0) = 1
Neighbor Selection: Temperature
as temperature T decreases, probability decreases faster (not much exploration)
Implementing Neighbor Selection
Implementing Neighbor Selection (SA)
Naive Implementation
Enumerate all neighbors and pick randomly
Runtime O(|Neighborhood|) —> size of whole neighborhood
Reasonable when selection probability depends on value of state
Wasteful for uniform selection (if I choose randomly, I don’t care about value —> so it would be waste of running time & computation)
Uniform Implementation
Create random neighbor
Runtime O(1)
Local Beam Search
instead of following a single line through the state space, LBS follows multiple lines (a beam)
in each step, we select the k best states from the set of all neighbors of all k current states
Downsides:
can concentrate on a small region of the search space too early
Algorithm
Local Beam Search versus Parallel Hill-Climbing
Parallel Hill-Climbing:
In each iteration, select best neighbor for each of the k states independently (no interaction between them)
Local Beam Search:
In each iteration, select the k best neighbors of all current states (done in parallel, but not independently —> at each step, all neighbors are grouped together and selection is based on this whole neighborhood)
Stochastic Beam Search
LBS can concentrate on a small region of the search space too early (k-best states could be in a small region)
—> therefore: Stochastic Beam Search alleviates this problem by using randomized selection similar to Stochastic Hill-Climbing
Random Selection Stochastic Beam Search
random selection is usually not completely random
probability of selecting a state should increase with its value
—> This balances Diversity (Exploration) and Intensification
Last changeda year ago