Cram1 Flashcards
The agent perceives ______ acts according to a ______
environment, performance criteria
Performance criteria are
domain dependent
Possible performance criteria:
m2 per hour
how clean is the room after vacuuming
power consumption
Ideal rational agent
The agent chooses an action which maximizes its performance for a given
percept sequence and knowledge about the world.
to avoid trivialization use ____
active sensing
Categorization of Agents
Percepts: Symptoms, findings, patient’s answers,
Actions: Questions, tests, treatments,
Goals (performance measures): Healthy patient, minimize costs,
Environment: Patient, hospital
The goal of learning
Optimize future behavior on the basis of the history of percepts, actions, and knowledge about the world.
accessible vs. nonaccessible
Are all relevant aspects of the world accessible to the sensors?
deterministic vs. nondeterministic/stochastic
Does the next state depend completely on the current state and the action chosen.
episodic vs. nonepisodic
Does the choice of an action depend only on the current state or also on the past?
static vs. dynamic
Can the world change while deciding on the next action?
discrete vs. continuous
Is the world discrete (as in chess) or not (mobile robots)?
Properties of Environments
accessible, deterministic, episodic, static, discrete
A goal is
a set of world states, which the agent finds desirable (wants to reach one of them).
Search
Finding an action sequence which transforms an initial state into a goal state.
Single-state problem
complete world knowledge,
complete knowledge about the actions
Multiple-state problem
incomplete world knowledge,
complete knowledge about the actions
Contingency problem
incomplete knowledge about actions,
needs to gather information at run-time
Exploration problem
World states and effect of actions are
both unkown. Very difficult!
Initial state
World state which the agent believes to be in initially
State space
Set of all possible states
Operator
Description of which state is reached by an action from a given state.
Successor function S
S(x) returns the set of states reachable by any action from state x
Goal test
Tests whether a state is a goal state.
Path
Sequence of actions
Path cost
Cost function over paths, usually the sum of the costs of the actions of the path, often denoted as g.
Solution
Path from the initial state to a state that satisfies the goal test
Search cost
Time and memory needed to find a solution
Total cost
Sum of the path cost (of the solution) and search cost
8-Puzzle
States: Describe the location of each tile including the blank.
Operators: Blank moves left, right, up, or down.
Goal test: Does the state match picture on the right?
Path cost: Each step costs 1 unit.
Search cost: Problem is NP-complete in the size of the puzzle.
Completeness
Does it always find a solution if one exists?
Time Complexity
How long does it take to find a solution in the worst case?
Space Complexity
How much memory is used in the worst case?
Optimality
Does it always find the best solution?
Uninformed (blind) search
No information available about the length or the cost of a solution.
breadth-first search, uniform cost search, depth-first search
Informed (heuristic) search
has information about the length or the cost of a solution
Greedy search, A* and some variants, hill-climbing
Cost of Breadth-First Search
O(b^(d+1))
Iterative Deepening
Combines depth- and breadth-first search
Time complexity: O(b^d)
Space complexity: O(b*d)
Problems with Bidirectional Search
Operators not always reversible
Incompletely described goal states (e.g. checkmate)
A*
combines uniform cost search with greedy search
g(n) = actual cost from the initial state to n.
h(n) = estimated cost from n to the nearest goal
f (n) := g(n) + h(n)
f (n) = is the estimated cost of the cheapest path which passes through n.
h is called admissible if
h(n) <= h*(n) for all n
Path-Max Equation
n parent of n’
f (n’) = max(f(n), g(n’) + h(n’))
Games are a special variant of
search problems
The states are usually
accessible
Games belong to the class of
contingency problems (uncertain knowledge of action effects).
When the search space is large, the game tree can only be generated up to a certain depth. Minimax works then as well. Simply replace
TERMINAL-TEST by CUT-OFF-TEST and the utility function UTILITY by the evaluation function EVAL.
Evaluation Functions should be
easy to compute and accurately reflect the chance of winning
Complexity of Alpha-Beta
random leaves: O((b/logb)^d)
best: O(b^(d/2))
usually: O(3d/4)
Knowledge Base (KB):
- contains sentences in a language with a truth theory (Logic) which we can interpret as propositions about the world
- causal effect on the agent’s behavior in correlation with the contents of the sentences
Knowledge Level
what is known by the KB. E.g.: automatic taxi driver knows that Vaalser St connects Aachen and Vaals
Symbolic Level
Encoding of the KB as sentences in a formal language: Connects(Vaalser _St, Aachen, Vaals)
Implementation Level
The internal representation of sentences.
Taxi-example:
- a string “Connects(Vaalser_St, Aachen,
Vaals)”
- a bit in in a 3-D-matrix representing connections
between places.
declarative language
System believes P iff P is thought to be true
precise language
- which strings are sentences;
- what it means for a sentence to be true (without having to explicitly specify for every sentence whether or not it is true).
explicit knowledge
KB
implicit knowledge
{a | KB |= a}
Deductive inference
Process to compute the logical consequences of a KB.
given a KB and a query a, computes whether KB|=a.
Herbrand universe
the set of all terms which can be formed from the functions and terms in S
