Random review on AI 1

Question 1

What is an agent?

Answer 1

• Agent: is an entity that perceives and acts.
• perceiving its environment through sensors –> percept
• acting upon that environment through actuators. –> action

Question 2

What is an agent function?

Answer 2

an agent´s behavior is described by the agent function that maps any given percept sequence to an action.
fa: P–>A

Question 3

What is a rational agent?

Answer 3

For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

Question 4

What are the terms used to specify the task environment in rational agent design?

Answer 4

PEAS components:
Performance measure
Environment
Actuators
Sensors

Question 5

How do we classify the characteristics of task environments?

Answer 5

• Observable: fully, partial
• Deterministic, nondeterministic, stochatisc
• Episodic, sequential
• Dynamic, static, semi
• Discrete, continuous
• single-agent, multiagent

Question 6

What are the four basic types of agent architectures? list in order of increasing generality.

Answer 6

• simple reflex agents
• model based agents
• goal based agents
• utility based agents
• (learning agents)

Question 7

What is the difference between an uninformed and an informed search algorithm

Answer 7

Uninformed:
- no estimate regarding the given state and goal state
- only uses the information available in the problem definition.
Informed: have some domain-dependent knowledge in the form of heuristic function h, or if we precompute partial solutions involving patterns or landmarks
h - estimate how far a given state is from the goal state

Question 8

What are the terms for constructing the overview structure of search problems?

Answer 8

Search problem :=<S, A, T, I, G>
S - set of states
A - set of actions
T - transition model AxS–> P(S)
I - initial state
G - goal state

Question 9

What is a search strategy? what are the important properties of strategies?

Answer 9

A function that picks a node from the fringe of a search tree.
completeness
time complexity
space complexity
optimality

Question 10

What are the terms of the search tree used to measure time and space complexity?

Answer 10

b - maximum branching factor
d - minimal graph depth of a solution
m - maximum graph depth (maybe infinity)

Question 11

List some uninformed search strategies.

Answer 11

• breadth-first search bfs
• uniform-cost search ucs
• depth-first search dfs
• depth-limited search
• iterative deepening search

Question 12

Describe the main difference in strategy between bfs, dfs, ucs, ids

Answer 12

-bfs:
+successors go in at the end of fringe (right side), FIFO
+expand the shallowest unexpanded node
- dfs:
+successors go in at front of fringe (left side), LIFO
+expand deepest unexpanded node
- ucs
+fringe is ordered by increasing path cost
+expand least-cost unexpanded node
+ <=>bfs if step costs are equal
+ step cost=0 –> infinite branches –> dfs
- ids
+ dfs with a depth limit and with increasing depth limits

Question 13

Compare the completeness property of different search strategies bfs, dfs, ucs, ids

Answer 13

-bfs - Yes (if b is finite)
-dfs - Yes if state space finite / No if tree contains infinite paths or loops
-ucs - Yes (if step costs >=e>0) not too small
- ids - yes

Question 14

Compare the time complexity property of different search strategies bfs, dfs, ucs, ids

Answer 14

-bfs - 1 + b + b^2+b^3+…+b^d, O(b^d), i.e. exponential in d
-dfs - O(b^m)
-ucs - nr. nodes with path-cost less than that of optimal
- ids - (d+1)b^0+db^1+(d-1)*b^2+…+b^d \in O(b^(d+1))

Question 15

Compare the space complexity property of different search strategies bfs, dfs, ucs, ids

Answer 15

-bfs - O(b^d)
-dfs - O(bm) linear space
-ucs - nr. nodes with path-cost less than that of optimal
- ids - O(bd)

Question 16

Compare the optimality property of different search strategies bfs, dfs, ucs, ids

Answer 16

-bfs - yes (if cost =1 per step), not optimal in general
-dfs - no
-ucs - Yes
- ids - Yes (if step cost=1)

Question 17

What is a solution for a search problem?

Answer 17

a sequence of actions that change initial to a goal state

Question 18

What is a cost function?

Answer 18

associates a step cost c(a) to an action a \in A
the cost of a solution is the sum of the step costs of its actions.

Question 19

What is the evaluation function in informed search?

Answer 19

it assigns a desirability value to each node of the search tree
f(n)
e.g. in best first search, the fringe is a queue sorted in decreasing order of desirability.

Question 20

What is heuristic (function)?

Answer 20

is evaluation function h on states that estimate of cost from n to the nearest goal state.
h(s)=0 whenever s is a goal state
h return infinity–> dead ends
extreme cases:
h=0: no overhead for computing h,–> uninformative search
h=h:same as true cost–> perfect accurate, overhead
=> in practice, trade off accuracy against overhead
h(s): the cost of the cheapest path from s to a goal state, or infinity if no such path exists => goal distance function

Question 21

When is a heuristic h admissible?

Answer 21

if it is a lower bound on goal distance(cost of cheapest path from s to a goal state).
h(s)=<h*(s) for all s \in S.
- note: consistency is a sufficient condition for admissibility.

Question 22

when is a heuristic consistent?

Answer 22

if, when applying an action a, the heuristic value cannot decrease by more than the cost of a.
h(s)-h(s´)=<c(a) for all s \in S and a\in A

Question 23

What are the similarity and differences between greedy search and A* search?

Answer 23

Similarity: use an evaluation function
Differences:
- greedy search: using heuristic
- A* search: using heuristic + path cost

-greedy: expand the node that appears to be closest to the goal

Question 24

What is the constraint satisfaction problem?

Answer 24

A problem is solved when each variable has a value that satisfies all the constraints on the
variable. A problem described this way is called a constraint satisfaction problem, or CSP.
–> The main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints.

Question 25

What is the formal definition of CSP?

Answer 25

Constraint network - a triple <V,D,C>, where
V is a finite set of variables
D the set of their domains (domains of each variable)
C set of constraints - relation between domains of variables involved. e.g. binary constraint Cuv \belongto Du x Dv
Du x Dv: possible assignment to variables u and v
Unary constraint Cv by restricting domain of v
Dv:=Cv

Question 26

Can CSP be seen as a search problem? if yes, how?

Answer 26

yes.
if we take:
states <-> partial assignment
actions<->assignment extensions
goal stats<-> consistent assignment
(initial state <-> empty assignment)

Question 27

What is arc consistency in CSP?

Answer 27

An arc (u,v) is arc consistent if
for all u \in Du there exists values v \in Dv. It is also said u is arc consistent with v.