01. Introduction
What is AI
Systems that act like humans
Systems that think like humans (not part of the lecture)
Systems that think rationally
Systems that act rationally
e.g. reflexes for self-protection
main topic of this course
02. Agent Architectures
Agent perceives the environment
Agent acts according to a performance criteria
domain dependent
Ideal Rational Agent
Acting rationally depends on
performance measure (goals)
percept sequence
wolrd knowledge
possible actions
The agent chooses an action which maximizes its performance for a given percept sequence and knowledge about the world
Table-Lookup Agents is a bad idea in general
too inflexible
too complex (chess: about 35100 entries)
-
-
Agents with an Internal World Model
-
-
Utility-based Agents
-
Performance Element => Agent in the old sense
Critic => Tells the system how good or bad it is performing
Learning Element => Improves the system
Problem Generator => Suggests actions to test performance
Properties of Environments
accessible vs. nonaccessible
all relevant aspects of the world accessible to the sensors?
Deterministic vs. nondeterministic/stochastic
Depends the next state completely on the current state and the action chosen?
Episodic vs. nonepisodic
The choise of action depends comletely on the current state (not the past)
Static vs. dynamic
Can the (relevant) world change while deciding on the next action?
Discrete vs. continuous
Is the world discrete (chess) or not (mobile robots)?
03. Search
Trough goal-oriented agents
Given initial world state
Agent wants to reach a goal
Using actions
An action transform one state into another
Definition goal:
Set of world states
Agent wants to reach one of them
Definition Search:
Finding an action sequence which transforms an initial state into a goal state
Problem classification
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 world knowledge
needs to gather information at run-time
Exploration problem
World states unknown
effect of actions unknown
Definitions:
State space Set of all possible states
Operator Description of which state is reached by an action from a given state (possible functions)
Successor function S S(x) returns the set of states reachable by any action from state x
Search in General
starting from initial state expand one state
create all successor states
next state to expand depends on strategie
Evaluating Search Strategies
Completeness
Does is always find a solution if one exists?
Time Complexity
Space Complexity
Optimality
Does it always find the best solution?
Uninformed (blind) search
no information about length and cost of a solution
Main-Methods:
BFS
completeness
optimal solution (if all actions have identical non-negative cost)
High cost (in time and space)
uniform cost search
BFS but expands node with least path cost
completeness
optimal solution (always)
high cost (in time and space)
DFS
no completeness
no optimal solution
space low
time high
depth-limited search
DFS but only up to a pre-specified depth
iterative deepening
combines BFS and DFS
completeness
optimal solution
time high
space lower as BFS
Preffered method if search depth unknown
bidirectional search
not always possible (not all operators are reverseable)
which kind of search method should be used for each direction
Comparsion
04. Informed Search
Uses information about the cost from a given node to a goal in the form of an evaluation function f, assigning each node a real number
Best-first Search
Always expand the node with the “best” f-value
Greedy Search
h(n) = estimated cost from state at node n to a goal state
Expand node n where h(n) is minimal
Use f = h
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 (heuristic)
f(n) = g(n) + h(n)
estimated cost of the cheapest path which passes through n
required to be admissible
h(n) <= h*(n)
h*(n) is the actual cost of the optimal path from n to the nearest goal
How to find a heuristic
Simplify the problem
compute the exact solution for the simplified problem
use the solution cost as heuristic
05. Games
Special variant of search problems
usually accessible
actions are the possible moves of a player
more than one actor
opponents actions (reactions) are usually not foreseeable
uncertain outcomes
Good algorithms have the following features
Early pruning of useless sub-trees
good evaluation function of states without doing a complete search
Player
MAX
begins game
wants to win (with help of AI)
MIN
Evaluation functions
should be easy to compute
accurately reflect the chance of winning
Minmax-Algorithm
-
1.Generate complete game tree
2.Apply utility function to each terminal state
3.Starting from the terminal states, calculate the values for the parent node
1.If the parent node is at a MIN level, assign the minimum of the child values
2.If the parent node is at a Max level, assign the maximum of the child values
3.At the root MAX chooses the action which leads to the child with maximum utility
-
Minmax assumes that MIN plays perfectly rationally
If Search Tree is large, stop at certain level (cut off)
Replace utility function by evaluation function
Alpha-Beta Search Algorithm
Like Minmax
-
But only calculates while option can be better
A22, A23 are not calculated, because A2 is always worse than A1 (after A21 is calculated)
Games with an Element of Chance
Third “player”, the probability
Action of third “player” depends on the probability
Values are multiplied with the probability
06. Knowledge Representation
Knowledge Base (KB)
contains sentences in a language with a truth theory (Logic) which we can interpret as propositions about the world
The sentences (through their form alone) have a casual effect on the agent’s behavior in correlation with the contents of the sentences
Syntax
ASK(KB,a) = YES iff a follows form KB
TELL(KB,a) = KB’ so that a follows from KB’
Levels
Knowledge Level
most abstract level
addresses what is known by the KB
e.g.: knows that Vaalser St connects Aachen and Vaals
Symbolic Level
Encoding of the KB as sentences in a formal language
e.g.: Connects(Vaalser_St, Aachen, Vaals)
Implementation Level
The internal representation of sentences
e.g.: a bit in a 3-D-matrix representing connections between places
Declarative Language
declarative
System believes P iff P is thought to be true
precise (needs to know)
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
First-order logic
Declarative Language
Symbols
Logical symbols
Delimiter
Operators
Variables
fixed meaning and use (like keywords in a programming language)
Nonlogical symbols
Predicate symbols (e.g. Friend)
Function symbols (e.g. bestFriendOf(x))
Meaning is application dependent
Grammar
Terms
single variable
If t1, t2, …, tn are terms and f is an n-ary function symbol, then f(t1, t2, …, tn) is a term
Atomic well formed formulas (wffs)
If t1, t2, …, tn are terms and P is an n-ary predicate symbol, then P(t1, t2, …, tn) is an atomic formula
If t1 and t2 are terms, then t1 = t2 is an atomic formula
Formulas (wff)
Every atomic wff is a wff
-
For wffs and variable are wffs
Notation
Abbreviations
-
instead of
-
instead of
-
Lexical binding
-
free bound first x can be differ from second x
-
Sentences
wffs without free variables
Substitution
-
means with all free occurences of replaced by
-
Interpretations
-
is an interpretation where
-
is the universe of discourse or domain
can be any non-empty set
-
is an interpretation function
-
where is an n-ary predicate symbol,
-
an n-ary relation over
-
-
where is an n-ary function symbol
-
an n-ary function over
-
-
-
-
Denotation
-
the denotation of a term is the element of assigned by
-
reads “I of t”
-
-
Satisfaction
The truth value of a wff depends also on the assignment to the variables
-
stands for is satisfied by and
-
Logical Consequence
-
implies or is a logical consequence of
-
iff for all , if then
-
-
07. Resolution
Clausal Form
Formulas
Use [ and ]
conjunction (AND) of clauses
[ ] represents FALSE
Clauses
use { and }
disjunction (OR) of literals
{ } represents TRUE
Literals
Clausal Form represents wff in CNF
every propositional wff can be converted to conjunctive normal form
Resolvent
-
From and infer
-
is called the resolvent of the input clauses relative to p
Implications of the input clauses
-
Most general unifier (MGU)
-
is a MGU of the literals and iff
-
unifies and
-
for every unifier there is a substitution such that
-
Resolution is complete when restricted to MGUs
Computing the MGU
-
-
-
-
1.Start with
-
2.If all are identical, then success: is the MGU
Otherwise look for the disagreement set -
3.Find a varibale and a term which does not contain
Otherwise abort: not unifiable -
4.
5.Goto 2
-
-
-
-
Exponential time
there are faster linear MGU-algorithms
-
Strategies for Resolution
-
1.Eliminating clauses
-
Pure clauses
Tautologies
Subsumed clauses
-
2.Ordering strategies
3.Set of support
4.Operators with a sense of direction
Komplex… noch einmal Foliensatz anschauen!
Ende weggelassen
08. Planning
Given
a description of the initial state
a description of the goal state
a description of actions
Problem
find a plan involving these actions that takes you from the initial state to the goal state
Difference to search
states need not to be completely specified
Search treats states as black boxes
search generates all successor states
planning only some
often too many actions to choose from, “impossible” to generate all successor states
search wants to find a sequence of actions leading to a goal
planning looks for description of a plan
e.g. actions may only be partially ordered
Stanford Research Institute Problem Solver (STRIPS)
Actions have the following attributes
Action name Function name with parameters
Preconditions only positive literals
Effects positive and negative literals
Initial State
Set of ground literals, no function symbols other than constants
Goal State
Set of literals
A plan consists of
a set of partially ordered plan steps
-
a set of variable assignments
a set of causal relations
-
( satisfies the precondition for )
-
Complete Plan
-
Every precondition of every plan step is satisfied, that is
with with and -
and for every linearization of the plan we have
with
-
Consistent Plan
-
If then
-
If then for distinct and
-
A complete and consistent plan is called a solution
-
Example:
Threat
-
threatens a link
often resolvable through promotion or demotion
-
Promotion
-
Add to orderings
-
Demotion
-
Add to orderings
-
09. Uncertainty
Probability Distributions
P(A) is the probability that proposition A holds
-
A is a boolean combination () of atomic propositions
-
Decision Theory = Probability Theory + Utility Theory
-
-
for distinct and
-
Conditional Probabilities
-
Probability for A under condition that B is given
B is called the evidence
-
Joint Distributions
-
with random variables
assigns probability to all atomic events
atomic events exclude one another
sum of all atomic events = 1
can be represented through a belief network
-
and
-
-
Bayesian Update
efficient solution is possible when certain conditional independence assumptions can be made
-
-
d-Separation
-
Set of nodes d-separate the sets of nodes and iff every path from a node in to a node in is blocked. Blocking means
-
and at minimum one Edge points from to or
-
Neither or any of its successors are in and no edge points from to or
-
-
IF d-separates from , then is independent of given
-
10. Learning
Goal: optimize future behavior on the basis of the history of percepts, actions and knowledge about the world
-