### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Search Heuristics Course

No description
by

## Oleksii Molchanovskyi

on 1 April 2014

Report abuse

#### Transcript of Search Heuristics Course

def
Random-Hill-Climbing(problem):
current_point = make_node( initial_state( problem ))

while

True
:
neighborhood = current_point.get_neighbors( )
good_neighbors = neighborhood.take_all_nodes_with_value_greater( current_point.value )

if
good_neighbors is not empty:
current_point = good_neighbors.get_random_item( )

else
:

return
current_point
def
Hill-Climbing-With-Sidesteps(problem, sidesteps_limit):
sidesteps_counter = 0
current_point = make_node( initial_state( problem ))

while

True
:
neighborhood = current_point.get_neighbors( )
best_neighbor = neighborhood.find_the_best_neighbor( )

if
best_neighbor.value > current_point.value:
current_point = best_neighbor
sidesteps_counter = 0

elif
best_neighbor.value == current_point.value:
sidesteps_counter += 1

if
sidesteps_counter > sidesteps_limit:

return
current_point

else
:

return
current_point
Completeness ?
Optimality ?
Memory usage ?
Working time ?
Search Heuristics Course
Informed search
How do we define a problem?
Problem domain (what are we talking about?)
Input (what do we have?)
Output (what do we want?)
Example: shortest path
Input: starting and finishing points
Output: shortest route from start to finish
From Skopje, Macedonia to Kyiv, Ukraine
searching
State
searching
Space
searching
Strategy
State is a "one-time snapshot" of all valuable data from the problem domain (e.g. in which city are we now?)
Searching space is a set of all possible states for the current problem domain (e.g. all possible cities on the Earth)
Strategy describes how do we travel from one city to another
History analogies
Who are the most ancient "searchers", or search agents?
Wandering for 40 years in the desert with his people
Moses
quite enough time for an algorithm to get a solution
Searching for a shortest path from Troy to Ithaca for 10 years
Odysseus
Course plan
Uninformed strategies (Day 1)
BFS, DFS, LDFS, ...
Informed strategies (Day 2)
Greedy, A*, ...
Local search and metaheuristics (Day 3)
Hill climbing, Beam, Tabu, ...
Planning in AI, competitive games
Types of problems
1. It's essential to know the whole path from an initial state to a goal state
2. We don't care about path. The only valuable thing is a goal state as it is.
Examples: shortest path, planning in AI, puzzles
Examples: traveling salesman problems, scheduling, competitive games
Uninformed
search

Main idea
The uninformed algorithms are simply walking through the whole search space
They are the basis for more complicated methods
You may be familiar with them already:
Depth First Search
Recall search space and states
Problem domain (graph)
Search space (tree)
states
neighborhood
Depth First Search (DFS)
function Tree-Search(problem, strategy)
initialize current node with initial state of problem
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state then return the corresponding solution
else expand the node and add the resulting nodes to search tree
state
node
parent node
action
Each node has a "path-cost", i.e. cost of the path (length) from an initial node to the cureent one
Strategy properties
Completeness
Strategy is complete if it guarantees to find a solution
Optimality
Strategy is optimal if it guarantees to find an optimal solution
Memory usage
Number of nodes stored in memory during work
Working time
BFS properties
Completeness ?
Optimality ?
Memory usage ?
Working time ?
DFS properties
Yes
Yes
Exponential
Exponential
Completeness ?
Optimality ?
Memory usage ?
Working time ?
No
No
Linear
Exponential
BFS: Implementations details
Data structure: queue (First In First Out)
DFS: Implementations details
Data structure: stack (List In First Out)
DFS modifications
How to avoid this infinity loop?
Limited depth first search
Includes a limit - maximum depth of a searching tree
No
No
Linear
Exponential
LDFS properties
Completeness ?
Optimality ?
Memory usage ?
Working time ?
Iterative depth first search
Sequentially calls a limited DFS method while incremenating a limit iteratively
Yes
Yes
Linear
Exponential
IDFS properties
So which algorithm is better to use?..
BFS
DFS
LDFS
IDFS
Recall our shortest path problem
Goal: find the path
from Kyiv to Remsfeld
Information is significant!
What have we learned so far?
Main idea
Enable more intelligent wandering through a search space.
Our algorithms need somehow to guess a preferred direction where a goal state may lie.
Heuristics
experience-based techniques for problem solving, learning, and discovery that gives a solution which is not guaranteed to be optimal
a mental shortcut that allows people to solve problems and make judgments quickly and efficiently
strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines
Heuristic functions
Short path problem
How to define which city is closer to our goal?
Lviv, 1050 km to Remsfeld
Odessa, 1630 km to Remsfeld
Search Heuristics
VIII Summer School
Achievements and Applications of Contemporary Informatics, Mathematics and Physics

Kyiv, Ukraine
2013

by Oleksii Molchanovskyi
Local search
Metaheuristics
Khrakiv, 1900 km to Remsfeld
For instance, you may use geographical coordinates to calculate the distances.
Which way is better to go from Kyiv to Remsfeld?
15-Puzzle
Is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing.
The object is to place the tiles in order by making sliding moves that use the empty space.
Amount of tiles that are not
on the proper places.
Total Manhattan distance:
sum of coordinate differences
between tile current position and
its goal position.
Possible heuristics
Eight Queens
Place 8 chess queens on an 8×8 chessboard so that no two queens attack each other
Possible heuristic
Amount of pairs of queens that attack each other
Best first search approach
A cost function F(x) is used to make an estimation of each node in the search tree (or search graph in general)
Generally heuristic function H(x) is a part of a cost function F(x)
H(x) estimates how close a particular state is to a goal state
General search algorithm
def

Best-First-Search
( problem, cost-function ):
queue = PriorityQueue( )
start_point = make_node( initial_state( problem ))
queue.insert( start_point )

while
True:

if
queue is empty:

return
Fail
node = queue.pop( )

if
node.state( ) is a goal state:

return
node
neighborhood = node.state( ).get_neighbors( )

for each
neighbor_node in neighborhood:
neighbor_estmate_cost = cost_function( neighbor_node )
queue.insert( [neighbor_node, neighbor_estmate_cost] )
Place where heuristics is used
Greedy search
Uses only heuristic function: F(x) = H(x)
Greedy algorithm expands a node that seems to be closest to a goal
Greedy method properties
Completeness ?
Optimality ?
Memory usage ?
Working time ?
No
Exponential
Exponential, but good
heuristics significantly
improve the result
Imagine yourself on a horse...
...a very fast one...
...and a little bit crazy.
So how to prevent such cases?
Use breaks!.. Even a simple rope works!
A* (A-star) method
Main idea: avoid the paths that are too costly
Cost function: F(x) = H(x) + G(x)
H(x) - a heuristic estimate of how close is a goal
G(x) - a cost of already passed path, i.e. from initial state to a current state x
G(x) is a rope for a crazy "greedy" horse.
So simple but so powerful!
Properties of A*
Completeness ? Yes
Optimality ? Yes
Moreover A* is optimally efficient for any given heuristic function!
That is, no other optimal algorithm is guaranteed to expand fewer nodes than A*.
Memory usage ? Exponential
Running time ? Exponentially depends on a solution length
Unfortunately A* is not a "silver bullet".
Recall the Best-First-Search function
def

Greedy-Search
(problem):

return
Best-First-Search( problem, H )
def
Astar
-Search
(problem):

return
Best-First-Search( problem, H + G )
VS
Recursive Best First Search
It is a standard BFS algorithm but which uses only linear memory.
On each iteration it stores in memory only one branch of a search tree
To avoid duplicate expanding of non-useful tree nodes it checks a best second state every time
When a current node will became unpromising it switches to the stored alternative and deletes whole current branch
Properties of RBFS
Completeness ? Yes
Optimality ? Yes
Memory usage ? Linear
Working time ? Exponential in general case
RBFS theoretically is as good as A*.
But it can spend too much time for "jumping" between alternative nodes in a search tree.
To minimize this side-effect and to optimize memory usage the memory-bounded A* modifications are used: MA* and SMA*.
SMA*: Simplified Memory-Bounded A*
Works similar to A* untill all memory is used.
When there is no enough memory it deletes the worst node from a search tree.
But stores deleted node cost in its parent node.
Methods comparison
Compare uninformed (BFS, LDFS, IDFS) and informed (Greedy, A*, RBFS) algorithms for various sizes of the N-queens problem
Overall amount of generated nodes and maximum amount of nodes in memory
- Unsolved instances of problem
Recall heuristic functions
Which heuristic function is a good one?
A heuristic function H(x) is called an admissible if it never overestimates the cost to reach the goal.
Admissible heuristics are by nature optimistic, because they think the cost of solving the problem is less than it actually is.
But too much optimism is not good either.
Heuristic function H1(x) dominates another function H2(x) if H1(x) > H2(x) for all x
H3(x) > H2(x)
Heuristics comparison
Compare two heuristics for N-queens problem using RBFS method
How to create a good heuristics?
On a basis of the relaxed problems.
A problem with less restrictions on the operators is called a relaxed problem.
Formal rule: a tile can move from square A to square B if A is adjacent to B and B is blank
Three relaxed problems:
(a) A tile can move from square A to square B if A is adjacent to B
(b) A tile can move from square A to square B if B is blank
(c) A tile can move from square A to square B
Wrong place tiles
Manhattan distance
Initial state
Goal state
How to get a best heuristics?
Get several admissible heuristics: H1(x), H2(x), ..., Hn(x)
Calculate a best one: H(x) = max( H1(x), H2(x), ..., Hn(x) )
Conclusions
Heuristics is a great and valuable idea!
Search strategy =
method + neighborhood + heuristics
Real life
For real life problems (NP-hard problems like TSP, knapsack, scheduling) even A* and its modifications will work too long.
So we need something else...

P.S. But don't forget about heuristics!
H2. Amount of pairs of queens that attack each other with the cases when two queens do not see each other
excluded
H1. Amount of pairs of queens that attack each other with the cases when two queens do not see each other
included
H1. Pairs of queens that do not see each other are
included
H2. Pairs of queens that do not see each other are
excluded
Running time limit: 60 sec
Heuristics is a great and valuable idea!
Search strategy =
method + neighborhood + heuristics

For real life problems (NP-hard problems like TSP, knapsack, scheduling) even A* and its modifications will work too long.
So we need something else...
Type of problems for today's section
We don't care about path. The only valuable thing is a goal state as it is.
Examples: traveling salesman problems, scheduling, competitive games
Main idea
Just use a current state and look for a best neighbor state hoping that it will lead you closer to your goal
Hill climbing
The simplest local search algorithm.
Select a best neighbor state in whole neighborhood to proceed with.
Optimization problems
Moreover we will talk about optimization problems, i.e. when we need to find an optimal solution (state).
For instance, take a TSP problem. Any state is admissible but only a few are optimal (compare with N-Queens problem).
Later we will clarify that it's OK to find a non-optimal but rather good solution.
The algorithm may not find a solution
Why "Hill climbing" ?
def
Hill-Climbing(problem):
current_point = make_node( initial_state( problem ))

while

True
:
neighborhood = current_point.get_neighbors( )
best_neighbor = neighborhood.find_the_best_neighbor( )

if
best_neighbor.value > current_point.value:
current_point = best_neighbor

else
:

return
current_point
It's for maximization problems
Who is the winner?
For minimization problem go to the southern hemisphere
Imagine you're a blindfolded alpinist (mountain climber) having serious troubles with remembering where you were at past. And you try to get on a highest Ukrainian mountain, Hoverla.
With such restrictions you'll probably find yourself in a nearest local hill (somewhere nearby our campus)
searching landscape
Solution cost
How can we avoid getting stuck in a local optimum?
There are several modification of Hill Climbing.
About more sophisticated approaches - after break.
Sidesteps
Allow the possibility to walk on "a plateau" making sidesteps hoping there will be another uphill.
Random walks
Do not select the best neighbor in the neighborhood but just good one - simply better than a current state
def
Hill-Climbing-With-Restarts(problem, number_of_restarts):
restart_number = 0
best_ever_found_node = current_point

while

True
:
current_point = make_node( problem.generate_state() )

while

True
:
neighborhood = current_point.get_neighbors( )
best_neighbor = neighborhood.find_the_best_neighbor( )

if
best_neighbor.value > current_point.value:
current_point = best_neighbor

else
:
break

if
current_point.value > best_ever_found_node.value:
best_ever_found_node = current_point

if
restart_number < number_of_restarts:
restart_number += 1

else
:

return
best_ever_found_node
Restarts
If we stuck in a local optimum try to restart the search from another initial solution. You need to memorize the best ever found optimum.
Hybrid local search
You can create any combination of these approaches:
Sidesteps
Random neighbor
Restarts
...
Beam search
Multiprocessing Hill Climbing.
Instead of enjoying one "blindfolded alpinist" use many of them!
def
Beam-Search(problem, number_of_beams):

for
i
from
1
to
number_of_beams:
current_point_list[i] = make_node( problem.generate_state( ) )

while

True
:
neighborhood = []

for
current_point in current_point_list:
neighborhood += current_point.get_neighbors( )
new_best_neighbors = neighborhood.select_best_nodes( number_of_nodes = number_of_beams )

if
new_best_neighbors is not empty:
current_point_list = new_best_neighbors

else
:
best_ever_found_node = new_best_neighbors.find_the_best_node( )

return
best_ever_found_node
Local search conclusions
Very fast
Almost doesn't use memory
Far from optimality
We cannot use a "magic rope" like with A*, right?
Motivation
Most of real life problems are very complicated (NP-hard or NP-complete):
Scheduling, Traveling Salesman, Knapsack...
So there are no algorithms for them that solve these problems efficiently (in polynomial time).
But for most of these problems it's OK to find a not optimal solution but a quite good one.
Why exponential time (memory) is so bad?
Take Traveling Salesman Problem
Optimal methods (branch-and-bound, branch-and-cut etc.) are working in exponential time
In worst case for TSP that are solved in acceptable amount of time the largest size is about 100-200 cities
To solve the problem with one more city you need to wait for a doubled amount of time
We call it a combinatorial explosion
Moore's law
The number of transistors on integrated circuits doubles approximately every two years. So does processing power.
If you are not developing new algorithms then you should wait for two years to add one more city to your problem.
What is a metaheuristic?
Compared to simpler heuristics, metaheuristics are more abstract procedures that use low-level heuristics or search algorithms.
They are the rules of how to “jump” from one solution to another in a searching space; how to accept the worse solutions in some way.
Metaheuristics' boom
1963 – Random Search
1965 – Evolutionary Strategy
1975 – Genetic Algorithms
1983 – Simulated Annealing
1986 – Tabu Search
1989 – Mimetic Algorithms
1992 – Ant Colony Optimization
2004 – Bee Colony Optimization
2007 – Intelligent Water Drops
2009 – Cuckoo Search
2011 – Galaxies Optimization
Tabu search
Main idea: memorize a number of previously visited states to deny immediate coming backs.
Denied states are stored in one tabu list or several lists (short-term, middle-term, long-term).
Tabued states
def
Tabu-Search( problem, tabu_list_limit ):
current_point = make_node( initial_state( problem ))
tabu_list = [ current_point ]

while

True
:
neighborhood = current_point.get_neighbors( )
best_node = EmptyState( )

for
neighbor
in
neighborhood:

if
neighbor.value < best_node.value
and
neighbor
is not in
tabu_list:
best_node = neighbor

if
best_node
is
EmptyState( ):
break

current_point = best_node
tabu_list.append( current_point )

if
tabu_list.length( ) == tabu_list_limit:
tabu_list.remove_oldest_node_from_list( )

return
current_point
Simulated annealing
The name and inspiration come from annealing in metallurgy - heating and controlled cooling of a material to increase the size of its crystals and reduce their defects.
This notion of slow cooling is implemented in the method as a slow decrease in the probability of accepting worse solutions as it explores the solution space.
It's like a shaking pinball table while hoping that ball will jump to a better place
Or like a quaking of a searching landscape hoping to accelerate our blindfolded alpinist.
Metaheuristics could be very efficient
Overall amount of generated nodes and maximum amount of nodes in memory
- Unsolved instances of problem
Running time limit: 60 sec
Running time of Tabu search for N-queens problem
Other methods gave up at size < 20
50-queens by Tabu search
But their tuning is a true science
Metaheuristic's parameters
Neighborhood strategy
Take a TSP tour. What are the possible neighborhood rules?
Tabu list length limit for Tabu Search
Probability function that depends on temperature for Simulated Annealing
One-Point rule
Take a city and change its position in a tour
5 - 1 - 3 - 4 - 2 - 5
5 - 3 - 4 - 1 - 2 - 5
Two-Point rule
Take two cities and swap their positions in a tour
5 - 1 - 3 - 4 - 2 - 5
5 - 2 - 3 - 4 - 1 - 5
Two-Opt rule
Take two edges and replace them with two new edges in a tour
5 - 2 - 3 - 4 - 1 - 5
1 - 2 - 3 - 4 - 5 - 1
And you can use them in different combinations
Many different metaheuristics are copying nature:
Ant colony optimization
Bee colony optimization
Genetic algorithms
Natural Water Drops algorithm
etc.
So go to talk to people from Neuro Science stream
Conclusions
Creating and using the metaheuristics is true science and art.
They are one of the several mechanisms that can help us with really hard problems
But beware!
"Enormously many metaheuristic methods have been published with claims of novelty and practical efficacy. Unfortunately, many of the publications have been of poor quality; flaws include vagueness, lack of conceptual elaboration, poor experiments, and ignorance of previous literature."
en.wikipedia.org/wiki/Metaheuristic
def
Simulated-Annealing(problem, temperature_function, probability_function):
current_point = make_node( initial_state( problem ))

for
time = 1
to
infinity:
temperature = temperature_function( time )
neighborhood = shuffle( current_point.get_neighbors( ) )
new_node = EmptyState( )

for
neighbor
in
neighborhood:
delta = neighbor.value - current_point.value

if
delta < 0:
current_point = neighbor
continue to new temperature
probability = probability_function(delta, temperature)

if
probability > random_probability( ):
current_point = neighbor
continue to new temperature

if
no new_node was found:

return

current_point

Probability = F( Temperature )
What is planning?
Planning is the process of thinking about and organizing the activities required to achieve a desired goal.
We can describe a planning task in terms of searching problems. How?
Missionaries and cannibals problem
Three missionaries and three cannibals must cross a river using a boat which can carry at most two people.
For both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals.
If they were, the cannibals would eat the missionaries.
The boat cannot cross the river by itself with no people on board.
The Dock-Worker Robots
There is a seaport with different sites (locations), ships, pallets, containers, cranes, trucks. The object is to find a plan of loading/unloading cargo containers from ships to pallets, and from pallets to trucks.
Planning in robotics
In the field of robotics planning
is a critical issue.
Shakey the robot
Shakey the robot was the first general-purpose mobile robot to be able to reason about its own actions.
Created during 1966-1972
Planning everywhere
State is some snapshot of the problem domain.
Neighbors are obtained with different possible actions (moving, turning, etc.)
Then a plan is a path in this space from an initial state to a goal state.
State is some plan that includes a sequence of actions that change behavior of the problem domain.
In this case you need to find an overall plan (some goal state in searching space) without storing the path through states.
Neighbors are obtained by actions on a partial plans.
Recover two types of searching problems
You can use any proper searching method we've studied (BFS, DFS, A*, Greedy, ...)
But special algorithms are existed for this purposes. Especially when working with partially created plans (GraphPlan, Partial-Order Planning etc.)
Competitive games
You can imagine a game like a problem of finding a plan that will lead you to your victory.
Can you use any of the previously presented algorithms for games (uninformed, informed, local)?
No, because we do not control the whole process. There are opponents that can ruin our optimal path (plan).
We need to take into account their possible reactions.
Game as a search problem
State is a description of some situation on a board.
Neighbor is another situation that is obtained by some allowed move in a game.
To build a plan that will allow you to win you need to think instead of your opponent as well.
Tic-tac-toe
Min-Max (minimax) algorithm
Introducing two players: MAX (you) and MIN (opponent).
MAX wins if the game is over and overall score is greater than 0. MIN wins if the score is less than 0.
We need to find an optimal strategy. That is when our opponent doesn't do mistakes we still win.
Main idea
Everytime choose a move with best minimax value that is the score you gain while your opponent doesn't mistake.
MAX
MIN
3
12
8
2
4
6
14
5
2
3
2
2
3
def
Minimax-Value( node ):

if
terminal-test( node ):

return
utility( n )

elif
node
is
MAX-player:
successors = node.get_successors( node )

return

max
( Minimax-Value(s)
for
s
in
successors )

elif
node
is
MIN-player:
successors = node.get_successors( node )

return

min
( Minimax-Value(s)
for
s
in
successors )

def
Minimax-Decision( state ):
neighborhood = state.get_all_neighbors( )
best_value, best_neighbor = -float('inf'), None

for
neighbor
in
neighborhood:
neighbor_value = min_value( neighbor.get_state( ) )

if
best_value < neighbor_value :
best_value, best_neighbor = neighbor_value, neighbor

return
best_neighbor.action( )
Main function

def
Max-Value( state ):

if
Terminal-Test( state ):

return
Utility( state )
max_value = -float('inf')
neighborhood = state.get_all_neighbors( )

for
neighbor
in
neighborhood:
max_value =
max
( max_value, Min-Value( neighbor ) )

return
max_value
Function for MAX-player

def
Min-Value( state ):

if
Terminal-Test( state ):

return
Utility( state )
min_value = float('inf')
neighborhood = state.get_all_neighbors( )

for
neighbor
in
neighborhood:
min_value =
min
( min_value, Max-Value( neighbor ) )

return
min_value
Function for MIN-player
from kalah/methods/minmax.py
from kalah/methods/minmax.py
from kalah/methods/minmax.py
Problems with Minimax
Behaves like DFS-BFS, i.e. builds whole "decision" tree.
For real games (chess etc.) is not acceptable because of size of the tree.
We should use heuristics for...
...Terminal-Test function to decide whether to stop tree expanding or not
...Utility function to be able to calculate utility values for non-finished nodes
Heuristic attack
These are the most critical parts of all gaming algorithms
Alpha-Beta Pruning is used to cut-off some unpromising branches of the searching (decision) tree.

In theory it could speed up the whole method run in two times
Recommended books
by Stuart Russell & Peter Norvig

aima.cs.berkeley.edu
Artificial Intelligence
A Modern Approach
Essentials of
Metaheuristics
by Sean Luke
cs.gmu.edu/~sean/book/metaheuristics/