Random review on AI 1 Flashcards
What is an agent?
- Agent: is an entity that perceives and acts.
- perceiving its environment through sensors –> percept
- acting upon that environment through actuators. –> action
What is an agent function?
an agent´s behavior is described by the agent function that maps any given percept sequence to an action.
fa: P–>A
What is a rational agent?
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.
What are the terms used to specify the task environment in rational agent design?
PEAS components:
Performance measure
Environment
Actuators
Sensors
How do we classify the characteristics of task environments?
- Observable: fully, partial
- Deterministic, nondeterministic, stochatisc
- Episodic, sequential
- Dynamic, static, semi
- Discrete, continuous
- single-agent, multiagent
What are the four basic types of agent architectures? list in order of increasing generality.
- simple reflex agents
- model based agents
- goal based agents
- utility based agents
- (learning agents)
What is the difference between an uninformed and an informed search algorithm
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
What are the terms for constructing the overview structure of search problems?
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
What is a search strategy? what are the important properties of strategies?
A function that picks a node from the fringe of a search tree.
completeness
time complexity
space complexity
optimality
What are the terms of the search tree used to measure time and space complexity?
b - maximum branching factor
d - minimal graph depth of a solution
m - maximum graph depth (maybe infinity)
List some uninformed search strategies.
- breadth-first search bfs
- uniform-cost search ucs
- depth-first search dfs
- depth-limited search
- iterative deepening search
Describe the main difference in strategy between bfs, dfs, ucs, ids
-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
Compare the completeness property of different search strategies bfs, dfs, ucs, ids
-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
Compare the time complexity property of different search strategies bfs, dfs, ucs, ids
-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))
Compare the space complexity property of different search strategies bfs, dfs, ucs, ids
-bfs - O(b^d)
-dfs - O(bm) linear space
-ucs - nr. nodes with path-cost less than that of optimal
- ids - O(bd)
Compare the optimality property of different search strategies bfs, dfs, ucs, ids
-bfs - yes (if cost =1 per step), not optimal in general
-dfs - no
-ucs - Yes
- ids - Yes (if step cost=1)
What is a solution for a search problem?
a sequence of actions that change initial to a goal state
What is a cost function?
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.
What is the evaluation function in informed search?
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.
What is heuristic (function)?
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
When is a heuristic h admissible?
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.
when is a heuristic consistent?
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
What are the similarity and differences between greedy search and A* search?
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
What is the constraint satisfaction problem?
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.
What is the formal definition of CSP?
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
Can CSP be seen as a search problem? if yes, how?
yes.
if we take:
states <-> partial assignment
actions<->assignment extensions
goal stats<-> consistent assignment
(initial state <-> empty assignment)
What is arc consistency in CSP?
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.
