程序代写代做代考 AI algorithm !

!
CMP2020M   ARTIFICIAL INTELLIGENCE
Dr. Marc Hanheide
Lincoln School of Computer Science University of Lincoln
go to already: http://lncn.eu/cmp2020m

!
AI QUIZ
‣ Which predicates are true, after “(pickup B)” has been applied, i.e. what is the successor state?
A. (CLEAR A)
B. (CLEAR B)
C. (ONTABLE A) D. (ONTABLE B) E. (HANDEMPTY) F. (HOLDINGA) G. (HOLDING B)
(:action pick-up
:parameters (?x)
:precondition (and (clear ?x
(ontable ?x)
(handempty))
:effect
(and (not (ontable ?x))
(not (clear ?x))
(not (handempty))
(holding ?x)))
Successor State:
(?) (?) …
Initial State:
(CLEAR A)
(CLEAR B)
(ONTABLE A)
(ONTABLE B)
(HANDEMPTY)
)
(pickup B)

dynamic world, search graphs  static world 
specific (path) planning generic knowledge representation
dynamic world  universal planning  using logic

REPRESENTING STATES
One state
(CLEAR A)
(CLEAR B)
(CLEAR C)
(ONTABLE A)
(ONTABLE B)
(ONTABLE C)
(HANDEMPTY)
‣ represent the state of the world as predicate logic literals that are true
‣ actions modify the set of literals
!

!
APPLYING EFFECTS
(CLEAR A)
(CLEAR B)
(CLEAR C) (ONTABLE A) (ONTABLE B) (ONTABLE C) (HANDEMPTY)
(pick-up B)
(:action pick-up
:parameters (?x)
:precondition (and (clear ?x)
(ontable ?x)
(handempty))
:effect
(and (not (ontable ?x))
(not (clear ?x))
(not (handempty))
(holding ?x)))
(CLEAR A)
(CLEAR C)
(ONTABLE A)
(ONTABLE C)
(HOLDING B)

!
APPLYING EFFECTS
(CLEAR A)
(CLEAR C)
(ONTABLE A)
(ONTABLE C)
(HOLDING B)
(stack B C)
(:action stack
:parameters (?x ?y)
:precondition (and (holding ?x
(clear ?y))
:effect
(and (not (holding ?x))
(not (clear ?y))
(clear ?x)
(handempty)
(on ?x ?y)))
(CLEAR A)
(CLEAR B)
(ONTABLE A) (ON B C) (ONTABLE C) (HANDEMPTY)

A SEARCH TREE
(CLEAR A)
(CLEAR B)
(CLEAR C) (ONTABLE A) (ONTABLE B) (ONTABLE C) (HANDEMPTY)
(pickup B)
state 1_1
(stack B C)
(CLEAR A)
(CLEAR C)
(ONTABLE A)
(ONTABLE C)
(HOLDING B)
state 0
(pickup A)
state 1_2
(CLEAR B)
(CLEAR C)
(ONTABLE B)
(ONTABLE C)
(HOLDING A)
(pickup C)
state 1_3
(CLEAR A)
(CLEAR B)
(ONTABLE A)
(ONTABLE B)
(HOLDING C)
state 2_1
(CLEAR A)
(CLEAR B)
(ONTABLE A)
(ON B C)
(ONTABLE C)
(HANDEMPTY)
state 2_2 state 2_3
state 2_2 state 2_3
s
state 2_4
state 2_7
t s

PROBLEM REPRESENTATION FOR SEARCH
• States: S={si}
• Initial state: s0⊂S c
• Goal state: g⊂S
• Actions (successor func.): a(si)=sj
• Cost: c(a,si,sj)
• Path cost: total cost of executed actions • Directed Graph representation
S0
a(s0)
g

!
● ●
●
●
●
●
●
EXAMPLE: CLEANING TWO ROOMS
Two rooms A and B. One vacuum cleaner can move between the rooms. Set of States: Position of vacuum + state rooms, e.g. {vacuum(A), dirty(A),
dir ty(B)}
Goal: AandBareclean:{clean(A),clean(B)}
Initial state: {vacuum(A), dirty(A), dirty(B)}
Vacuum Actions : move: left, right; suck
Cost: 1 for each movement
Solution: sequence of movements and sucks, e.g. suck-right-suck

!
IN PDDL

!
STATE SPACE

!
SOLUTION
cost=1+1+1

!
EXAMPLE: GOING TO A CITY
On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest.
●
●
●
●
●
●
●
Bucharest
How to represent the state in predicate logic for simple path planning?
at(Arad)  connected(Arad,Sibiu)
Set of States: cities in Romania
Goal: be in Bucharest
Initial state: be in Arad
Action: drive from one city to another
Cost: distances between two cities
Solution: sequence of cities leading to Bucharest, e.g., Arad, Sibiu, Fagaras,

!
STATE SPACE

!
SOLUTION
cost = 140+99+211

●
We restrict to the particular case of tree representations (no cycles)
S0
STATE SPACE:TREE
a1
S2
a2
a2
S3
a1
g S4
!

● ●
Graphs that contains cycles result in non-ending trees There are powerful graph algorithms finding loops
FROM GRAPH TO TREES
S0
S0 a1
a2 S3
a2 S2 a S a12
a1
S23 S2g
a1 a2
a1 a2
g S2 a1
g a2
!
…
g

!
TREE SEARCH EXAMPLE
●
Going from Arad to Bucharest

TREE SEARCH EXAMPLE
●
Going from Arad to Bucharest
!

TREE SEARCH EXAMPLE
!
●
Going from Arad to Bucharest

!
● ●
−
−
−
−
SEARCH STRATEGIES
A strategy is defined by the order of node expansion Strategies are evaluated along the following dimensions:
completeness—does it always find a solution if one exists? time complexity—number of nodes generated/expanded space complexity—maximum number of nodes in memory optimality—does it always find a least-cost solution?

●
−
− −
a1
S0
S3 a2
g
SEARCH STRATEGIES
Time and space complexity are measured in terms of:
b: maximum branching factor of the search tree
d: depth of the least-cost solution
m: maximum depth of the state space (may be ∞, i.e, cycles)
a2
S2 a1
S2 a1
…
!

!
BREADTH-FIRST SEARCH

!
BREADTH-FIRST SEARCH Expand shallowest unexpanded node

!
●
Complete?
PROPERTIES OF BREADTH- FIRST SEARCH

!
● ● ● ●
Complete? Yes(ifbisfinite)
Time?1+b+b2 +b3 +…+bd +b(bd −1),i.e.,exp.ind Space? Same a s time (keeps every node in memory) Optimal? Yes (if cost = 1 per step); not optimal in general
PROPERTIES OF BREADTH- FIRST SEARCH

!
DEPTH-FIRST SEARCH Expand deepest unexpanded node

!
●
Expand deepest unexpanded node
DEPTH-FIRST SEARCH Expand deepest unexpanded node

!
DEPTH-FIRST SEARCH Expand deepest unexpanded node

!
●
Expand deepest unexpanded node
DEPTH-FIRST SEARCH Expand deepest unexpanded node

!
DEPTH-FIRST SEARCH Expand deepest unexpanded node

!
●
●
●
Time? O(bm): terrible if m is much larger than d Space? O(bm), i.e., linear space!
Optimal? No
PROPERTIES OF DEPTH-FIRST SEARCH
Complete? No: fails in infinite-depth spaces, spaces with loops
Modify to avoid repeated states along path complete in finite spaces
●
− −

!
●
Depth first search with limited depth l, i.e., nodes at depth l have no successors
DEPTH-LIMITED SEARCH
l=2

!
ITERATIVE DEEPENING SEARCH
for depth ← 0 to max-depth do
result ← Depth-Limited-Search( depth)
if found(goal, result) then return result end

!
ITERATIVE DEEPENING SEARCH

!
● ● ● ●
Complete? Yes
Time?(d+1)b0 +db1 +(d−1)b2 +…+bd =O(bd) Space? O(bd)
Optimal? Yes, if step cost = 1
ITERATIVE DEEPENING SEARCH

!
●
− − −
SUMMARY OF SEARCH ALGORITHMS
Time and space complexity are measured in terms of:
b: maximum branching factor of the search tree
d: depth of the least-cost solution
m: maximum depth of the state space (may be ∞, i.e, cycles)
Criterion Complete? Time Space Optimal?
Breadth-first Depth-first Depth-limited Iterative-deeping
Yes* No Yes if l<=d Yes d+1 m l d b b b b d+1 b bm bl bd Yes* No No Yes ! MAIN PROBLEM WITH CYCLES ● Failure to detect repeated states can turn a linear problem into an exponential one! ! ● ● ● ● Search is planning but with many restrictions and simplifications. How to formulate a search problem? Different algorithms for search. Cycles are bad for search. YOU SHOULD KNOW ! RECOMMENDED READING ‣ Artificial Intelligence:   A Modern Approach   mainly chapter 3   (excerpt on blackboard)

Related Posts