MIDTERM 1 AI
Foundations of Artificial Intelligence
A rational
agent selects
agents that maximizes
expected utility :
a*
=
argmaxE[r(outcome]]
Key Distinctions :
Reflex agents fixed computations
·
:
Planning agents reasoning optimization
· :
Modeling
>
-
Inference >
-
Learning
·
Modeling represent problems mathematically
:
Inference compute using algorithms
:
answers
·
from
Learning estimate model parameters data
· :
Search
Definition :
A search problem consists of :
·
State spaces
Start state
·
·
Actions
·
successor function Succ(s a) ,
·
Goal test
·
Path cost function
A of actions from start
↑
solution is a
sequence to
goal
, Search Tree vs . Graph Search
Tree Search :
·
states
may repeat
computation'
·
more
Graph Search :
·
maintains closed set
·
never expands a state twice
Evaluation Criteria
Completeness
·
·
Optimality
Time
Complexity
·
Space Complexity
↑
·
Parameters :
b=
branching factor d solution depth m max depth
= =
, ,
Uniformed Search
Breadth-first Search /BFS) :
Expands shallowest node first :
Time =
O(bd) , Space =
0 (ba]
Complete Yes :
Optimal Yes (equal costs]
:
, Bapth-First Search
(DFS) :
node first
Expands deepest
:
Space
=
OLbm) Time ,
=
&(bM)
complete : Not complete on
graphs with
cycles
Yes for finite graphs
No
optimal :
Uniform Cost Search/vcs] :
Expands node win smallest path cost g(n >
*
C /E)
space and time : O (b
+
>
C >
- cost ofthe optimal solution
& >
- min positive step cost
complete : yes
optimal yes
:
All differ their priority rule
search
algorithms decide which
Snow frey
node to expand next]
Informed Search
Heuristics :
h(n) =cost from n to goal
designed for specific problems
better heuristic fewer node expansions
+
-
a risks
more expensive
inadmissibility
Foundations of Artificial Intelligence
A rational
agent selects
agents that maximizes
expected utility :
a*
=
argmaxE[r(outcome]]
Key Distinctions :
Reflex agents fixed computations
·
:
Planning agents reasoning optimization
· :
Modeling
>
-
Inference >
-
Learning
·
Modeling represent problems mathematically
:
Inference compute using algorithms
:
answers
·
from
Learning estimate model parameters data
· :
Search
Definition :
A search problem consists of :
·
State spaces
Start state
·
·
Actions
·
successor function Succ(s a) ,
·
Goal test
·
Path cost function
A of actions from start
↑
solution is a
sequence to
goal
, Search Tree vs . Graph Search
Tree Search :
·
states
may repeat
computation'
·
more
Graph Search :
·
maintains closed set
·
never expands a state twice
Evaluation Criteria
Completeness
·
·
Optimality
Time
Complexity
·
Space Complexity
↑
·
Parameters :
b=
branching factor d solution depth m max depth
= =
, ,
Uniformed Search
Breadth-first Search /BFS) :
Expands shallowest node first :
Time =
O(bd) , Space =
0 (ba]
Complete Yes :
Optimal Yes (equal costs]
:
, Bapth-First Search
(DFS) :
node first
Expands deepest
:
Space
=
OLbm) Time ,
=
&(bM)
complete : Not complete on
graphs with
cycles
Yes for finite graphs
No
optimal :
Uniform Cost Search/vcs] :
Expands node win smallest path cost g(n >
*
C /E)
space and time : O (b
+
>
C >
- cost ofthe optimal solution
& >
- min positive step cost
complete : yes
optimal yes
:
All differ their priority rule
search
algorithms decide which
Snow frey
node to expand next]
Informed Search
Heuristics :
h(n) =cost from n to goal
designed for specific problems
better heuristic fewer node expansions
+
-
a risks
more expensive
inadmissibility
