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)
       

•  

  

   

  Reflexive Agents
  
  
•  

  

  Agents with an Internal World Model
  
  

   

  Agents with an Internal World Model
  
  
•  

  

   

  Agents with explicit goals
  
•  

  

  Utility-based Agents
  
  

   

  Utility-based Agents
  
  
  
  
•  

  

   

  Learning 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. 1. 1.Generate complete game tree 

   2. 2.Apply utility function to each terminal state 

   3. 3.Starting from the terminal states, calculate the values for the parent node 

      1. 1.If the parent node is at a MIN level, assign the minimum of the child values 

      2. 2.If the parent node is at a Max level, assign the maximum of the child values 

      3. 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

     

    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 $$\mathrm{\alpha },\mathrm{\beta }$$ and variable $$x,\neg \mathrm{\alpha },(\mathrm{\alpha }\wedge \mathrm{\beta }),(\mathrm{\alpha }\vee \mathrm{\beta }),\exists x\mathrm{\alpha }\forall x\mathrm{\alpha }$$ are wffs 

  • Notation 

    • Abbreviations 

      • $$(\mathrm{\alpha }\supset \mathrm{\beta })$$ 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. 1. 1. 1.Start with  
      2. 2.If all are identical, then success: is the MGU
         Otherwise look for the disagreement set  
      3. 3.Find a varibale and a term which does not contain
         Otherwise abort: not unifiable 
      4. 4. 

      5. 5.Goto 2 

• • • Exponential time 

      • there are faster linear MGU-algorithms 

• Strategies for Resolution 

1. 1. 1.Eliminating clauses 

• • Pure clauses 

  • Tautologies 

  • Subsumed clauses 

1. 1. 2.Ordering strategies 

   2. 3.Set of support 

   3. 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:
    

     

    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

     

    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 

•