A.I. PLANNING
Planning as Forward Search
Copyright By PowCoder代写 加微信 powcoder
Search spaces
(at mydvd amazon)
(at truck amazon)
(at driver home)
(at mydvd amazon)
(at truck amazon)
(at driver amazon)
(in mydvd truck)
(at truck amazon)
(at driver home)
(walk driver home amazon)
(load mydvd truck amazon)
New states are generated
Don’t go round in circles
Keep a closed list:
All states that have been seen before
When expanding a state, ignore successors on the closed list
Forward Search, Graphs & Trees
The search space is a Directed Graph
Lots of different paths, can undo all actions, go around in circles, …
Forwards search from the initial state, with a closed list, builds a tree
Only one path into each node is kept
No backwards edges
Forward search
What you have been doing so far
Closed list – states already dealt with
Also, Open list – states to deal with
Initially: closed = [], open = [I]
while open not empty:
S = remove the next state from open
If S is not in closed
expand S and
add S to closed;
add successors to open
load-truck…
walk driver…
walk driver…
board-truck…
load-truck…
drive-truck…
drive-truck…
unload-truck…
walk driver home amazon
board-truck driver truck amazon
load-truck mydvd truck amazon
drive-truck driver amazon london
drive-truck driver london myhouse
unload-truck mydvd myhouse
Planning as Forward Search
Open list options
What if open was a queue?
Can push states onto the back
Can pop states from the front
> Breadth-first search
What if open was a stack?
Can push/pop states from the front
> Depth-first search
(not generally used in planning)
Breadth-First Search
Generate all the children of the current node.
Expand nodes in the order that they were generated.
Open list options
What if open was a queue?
Can push states onto the back
Can pop states from the front
> Breadth-first search
What if open was a stack?
Can push/pop states from the front
> Depth-first search
(not generally used in planning)
Depth-First Search
Generate all children of the current node.
If it has children select and expand its first child.
If not, backtrack to the most recent node with unexpanded children.
Open list options
What if open was a queue?
Can push states onto the back
Can pop states from the front
> Breadth-first search
What if open was a stack?
Can push/pop states from the front
> Depth-first search
(not generally used in planning)
How long will this take?
20 actions to choose from,
Solution plan is 20 steps long.
Worst case: need to search through all 20^20 possibilities.
(> 1 with 26 zeros after, 1026).
4.35*1017 is the estimated age of the universe in seconds….
Planning is PSPACE hard.
Need to find a way to search through only the most promising looking plans.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com