Real problems are too complex, to solve them we need to abstract them! Simplify them by removing unnecessary details.
Eg. If we need to find the path somewhere, we can ignore things such as weather, road conditions, scenary.
Actions need to be suitable specified eg not "turn the steering wheel left by 5 degrees".
The level of abstraction must be appropriate.
State = set of real states
Action = complex combination of real actions
Solution = set of real paths that are solutions in the real world
Incremental - stat with empty space, add 1 queen at a time
Complete-state - start with all 8 queens and move them around
States? Any arrangement of 0 to 8 queens
Initial state? No queens on the board
Operators? Add any queen to any square
State space? 1.8 10^14 states (= 64 63 ... 57)
States? Any arrangement of 0 to 8 queens, 1 in each column with no queen attacking each other
Initial state? No queens on the board
Operators? Place a queen in the left-most-empty column such that it is not attacked by any other queen
State space? 2057 states
1: 10^400 states
2: 10^52 states (hugh improvement but problem still not tractable)
Searching for solutions
Searching the state space
Generate a search tree starting from the initial state and applying the operators
We can generate a search graph - in a graph the same state can be reached rom multiple paths
Tree search algorithm - pseudo code
Basic idea: offline exploration of the state space by generating successors of the explored states (i.e. exapnding states)
We keep two lists:
Expanded - for nodes that have been expanded
Fringe - for nodes that bae been generated but not expanded yet
Nodes vs States
A node is different than a state.
represents a state
is a data structure used in the search tree
includes parent, children, and other relevant information e.g. depth and path cost g
A search strategy defines which node from the fringe is most promising and should be expanded next
We always keep the nodes in the fringe orded based on the search strategy and always expand the first one
is it guaranteed to find a solution if one exists?
is it guaranteed to find an optimal (least cost path) solution?
How long does it take to find the solution? (measured as no. of generated nodes)
what is the max number of nodes in memory?
Time and space complexity
Measured in terms of:
b: max branching factor of the search tree (we can assume that it is finite)
d: depth of the optimal (least cost) solution
m: maximum depth of the state space (can be finite or not finite)
There are two types of search methods:
Uninformed (Blind) Search Strategies
Generate children in a systematic way eg level by level, from left to right
Know if a child node is a goal or non-goal node
Do not know if one non-goal child is better (more promising) than another one. By contrast, informed (heuristic) search strategies know this
5 uninformed search strategies:
BFS - Breadth First Search
Is the first node in the fringe a goal node?
Yes => stop and return solution
No => expand it:
- Move it to the expanded list
- Generate its children and put them in the fringe in a order defined by the search strategy
Optimal? Not optimal in general; Yes, if step cost is the same, e.g. =1
Where are the improvements of IDS in comparison to DFS? - in completeness, optimality and time (shown with *)
Can be modified to explore uniform-cost tree
Informed vs Uninformed Search
A search strategy defines the order of node expansion
Uninformed search strategies do not use problem specific knowledge beyond the definition of the problem, i.e. they do not use heuristic knowledge. - expand nodes systematically - know if node is goal or non-goal - cannot compare two non-goal nodes (do not know if one goal node is better than another) - typically inefficient
Informed search strategies use problem-specific heuristic knowledge to select the order of node expansion. They: - can compare non-goal nodes – they know if one non-goal node is better than another one - are typically more efficient
Best First Search
How can informed strategies compare non-goal nodes?
By using domain specific knowledge to devise an evaluation function which estimates how good each node is
The evaluation function assigns a value to each node
At each step, the best node is expanded (the one with the best
This is called best-first search - Note that we don’t really know which is the best node as we use an estimate based on the evaluation function. So best-first search expands the node that appears to be the best.
Fringe: insert children in decreasing order of desirability
We will study 2 best-first search algorithms: greedy and A*
Greedy Search (GS)
Uses h value as an evaluation function (h - heuristic)
The h(n) for node n is the estimated cost from n to a goal node
Eg for the Romania example we can use h(n)=SLD(n, Bucharest) = straight-line distance from n to Bucharest
The h value of a goal node is 0, i.e. h(goal)=0
Complete? As DFS - Yes in finite spaces (if m is finite) - No - fails in infinite spaces (can get stuck in a loop)
Time? O(b^m) but good heauristic can give dramatic improvement