[SOLVED] A.I. PLANNING

A.I. PLANNING

Planning as Forward Search

Copyright By Assignmentchef assignmentchef

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

Dont 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: assignmentchef QQ: 1823890830 Email: [email protected]