2D - Reasoning and Agents

Based on Informatics 2D: Reasoning and Agents in The University of Edinburgh lecture slides from 2018-2019.

Table of Contents

15 January 2019

Intelligent Agents

An agent

Examples:

Simple Reflex Agents

function Simple-Reflex-Agent(percept) returns action:
    persistent: rules - set of condition-action rules

    # Pay attention to the fact that state is constructed
    # purely out of the current percept.
    state  := Interpret-Input(percept)
    rule   := Rule-Match(state, rules)
    action := rule.ACTION

    return action

Model-Based Reflex Agents

function Reflex-Agent-With-State(percept) returns action:
    persistent: state  - description of current world state
                model  - description of how the next state depends
                         on current state and does affected by our
                         actions
                rules  - a set of condition-action rules
                action - the most recent action, initially none

    state  := Update-State(state, action, percept, model)
    rule   := Rule-Match(state, rules)
    action := rule.ACTION

    return action

Goal-Based Agents

Utility-Based Agents

Types of Environment

17 January 2019

Simple Problem Solving Agent

function Simple-Problem-Solving-Agent(percept) returns an action:
    persistent: seq     - an action sequence, initially empty
                state   - some description of the current world state
                goal    - a goal, initially null
                problem - a problem formulation

    state := Update-State(state, percept)
    if seq is empty then
        goal    := Formulate-Goal(state)
        problem := Formulate-Problem(state, goal)
        seq     := Search(problem)
        if seq = failure then
            return null action

    action := First(seq)
    seq    := Rest(seq)

    return action

Agent has a "Formulate, Search, Execute" design.

Problem Types

Search Trees

1548160539501

Tree-Search function

function Tree-Search(problem) returns a solution or a failure:
    initialise `frontier` using the initial state of `problem`

    loop:
        if frontier is empty:
            return failure

        leaf := frontier.Pop()
        if leaf is goal:
            return a solution

        frontier.Add-All(leaf.expand())

TODO

Summary

18 January 2019

Search Strategy

Implementation:

Properties:

Implementation:

Properties:

Properties:

Summary

1548716427150

22 January 2019

Games

Game Trees

1549840840750

Minimax

Properties of Minimax

$\alpha-\beta$ Pruning

Example

Properties

In Practice

24 January 2019

Properties:

Properties:

Heuristic Functions

Admissibility:

Consistency:

Dominance:

Common Heuristics:

Relaxed Problems

25 January 2019

Knowledge-Based Agents

Pseudocode:

function KB-Agent(percept) returns an action:
    persistent: KB -  knowledge base
                t  - a counter, initially 0, indicating time (monotonic clock)

    # We tell our KB about the most recent state of the world
    # as we perceive.
    Tell(KB, Make-Percept-Sentence(percept, t))

    # "What should I do now (t)?" we ask our knowledge base.
    action := Ask(KB, Make-Action-Query(t))

    # We tell our KB about the action we are about to take.
    Tell(KB, Make-Action-Sentence(action, t))

    # Increase our monotonic clock
    t := t + 1

    return action

The agent must be able to:

PEAS

Example: Wumpus World

1549977445526

Logics

Entailment

Semantic Entailment (or just entailment), Syntactic Entailment (or inference), and Material Implication (or just implication):

Models

1549980063350

Equivalence

Inference by Enumeration

Validity and Satisfiability

Proof Methods

29 January 2019

(Effective) Propositional Inference

Conjunctive Normal Form (CNF)

DPLL Algorithm

Early Termination

Unit Clause Heuristic

Pure Symbol Heuristic

Tautology Deletion

WalkSAT Algorithm

Hard Satisfiability Problems

Expressiveness Limitation of Propositional Logic

31 January 2019

Constraint Satisfaction Problems (CSPs)

Example

1550669892711

Constraint Graph

Varieties of CSPs

Varieties of Constraints

Real-World CSPs

Improving Backtracking Search Efficiency

Most Constrained Variable

1550672451779

Most Constraining Variables

1550672510412

Least Constraining Value

1550672531565

Inference: Forward Checking

Idea:

Example:

1550673153836

Constraint Propagation

Arc Consistency

5 February 2019

Propositional Logic (PL)

First-Order Logic (FOL)

Syntax of First-Order Logic

Atomic Formulas

Complex Formulas

Semantics of First-Order Logic

Quantifiers

Universal Quantifier ("for all")
Existential Quantifier ("(there) exists")
Duality

Equality

Substitution

Knowledge Bases & FOL

7 February 2019

Universal Instantiation (UI)

Existential Instantiation (EI)

Reduction to PL by Propositionalisation

Theorems Regarding Propositionalisation

Herbrand (1930)
Turing (1936), Church (1936)

Unification

Standardising Variables Apart

Most General Unifier

Computing the MGU

Generalised Modus Ponens (GMP)

$$\begin{align*} \dfrac{p'_1, p'_2, \ldots, p'_n\ (p_1 \land p_2 \land \ldots \land p_n \implies q)}{q\theta}\quad \text{when for all $i$, }\ p'_i\theta \equiv p_i\theta \end{align*}​$$

Example

$$\begin{align*} p'_1&: \text{King}(\text{John})\\ p'_2&: \text{Greedy}(y)\\ p_1&: \text{King}(x)\\ p_2&: \text{Greedy}(x)\\ q&: \text{Evil}(x)\\ \end{align*}​$$

then it follows that

$$\begin{align*} \theta&: {x/\text{John},\ y/\text{John}}\\ q\theta&: \text{Evil}(\text{John}) \end{align*}$$

Alternatively:

$$\dfrac{\text{King}(\text{John}), \text{Greedy}(y),\ (\text{King}(x), \text{Greedy}(x) \implies \text{Evil}(x))}{\text{Evil}(x){x/\text{John},\ y/\text{John}}}​$$

8 February 2019

Chaining

Forward Chaining

Properties
Efficiency

Backward Chaining

Properties

Chaining and Constraint Satisfaction Problems

Resolution

Ground Binary Resolution

$$\begin{align}\frac{C \lor P \quad D \lor \lnot P}{C \lor D}\end{align}​$$

Non-Ground Binary Resolution

$$\begin{align}\frac{C \lor P \quad D \lor \lnot P'}{(C \lor D)\theta}\end{align}$$

where $\theta$ is the MGU (most general unifier) of $P$ and $P'$.

Factoring

Okay this one is hairy...

Example 1

$$\begin{align} S&:\quad P(x) \lor \lnot Q(f(x), b) \lor P(g(y))\\ S\theta&:\quad P(g(y)) \lor \lnot Q(f(g(y)), b) \end{align}$$

for $\theta = {x/g(y)}$.

Now for resolution purposes:

Full Resolution

$$\begin{align}\frac{C \lor P_1 \lor \cdots \lor P_m \qquad D \lor \lnot P'_1 \lor \cdots \lor \lnot P'_n }{(C \lor D)\theta}\end{align}​$$

where $\theta$ is MGU of all $P_i$ and $P'_j$.

Conversion to CNF

  1. Eliminate all biconditionals (if-and-only-if's) and implications.
  2. Push $\lnot$ inwards all the way.
  3. Standardise variables apart; each quantifier should use a different one.
  4. Skolemise: a more general form of existential instantiation
  5. Drop universal quantifiers.
  6. Distribute $\lor$ over $\land$.

12 February 2019

Limitations of Generalised Modus Ponens

Due to restriction to definite clauses, in order to (be able to) apply GMP:

Resolution & Modus Ponens

Binary Resolution & Modus Ponens

Consider

$$\dfrac{C \lor P \quad D \lor \lnot P}{C\lor D}$$

and suppose $C$ is False

$\dfrac{P \quad D \lor \lnot P}{D}$

i.e. $P$ and $P \implies D$ entails $D$.

Resolution in Implication Form

Consider

$\dfrac{C \lor P \quad D \lor \lnot P}{C\lor D}$

and set $C \equiv \lnot A$

$\dfrac{A \implies P \quad P \implies D}{A \implies D}$

where the conclusion is equivalent to $\lnot A \lor D \equiv C \lor D$ .

Full Resolution and Generalised Modus Ponens

TODO: I don't get this!

1554220356463

Factors, Resolvents, and the Lifting Lemma

Factors

Described again to refresh the memory.

Example 1

$$\begin{align} S&:\quad P(x) \lor \lnot Q(f(x), b) \lor P(g(y))\\ S\theta&:\quad P(g(y)) \lor \lnot Q(f(g(y)), b) \end{align}$$

for $\theta = {x/g(y)}​$.

Resolvents

Example 2

$$\begin{align} C_1&:\quad P(x) \lor P(f(y)) \lor R(g(y))\\ C_2&:\quad \lnot P(f(g(a))) \lor Q(b)\\ \end{align}$$

now let us calculate a factor of $C_1​$ where $\theta = {x/f(y)}​$

$$C'_1: P(f(y)) \lor R(g(y))​$$

now let us calculate a resolvent $C$ of $C'_1$ and $C_2$ where $\theta = {y/g(a)}$

$C = R(g(g(a))) \lor Q(b)​$

The Lifting Lemma

1554227017275

Efficient Algorithms for Resolutions

14 February 2019

Using Logic to Plan

Situation

Actions

Axiomatising Actions

Situation Calculus

1554285476613

The Frame Problem

Refutation Theorem Proving

Not getting into the details since it seems very much unnecessary.

  1. Negate the goal.
  2. Skolemise.
  3. Apply resolution on $\text{KB} \land \text{Skolemise}(\lnot\text{Goal})$.
  4. Empty clause indicates that there is a solution.
  5. The last/latest situation, being a chain of actions starting from the initial situation $S_0$ is your plan.

26 February 2019

Alex Lascarides' part of the course starts here.

Planning

Logic & Deductive Inference

Planning Domain Definition Language (PDDL)

Representing States & Goals

Actions in PDDL

1554292368652

Last Remarks:

28 February 2019

Heuristics

Divide and Conquer
Relaxations

1554296635766

POP as a Search Problem

1554304439932

POP as a search problem consists of:

The POP Algorithm

Ensuring Consistency:

Unbound Variable:

Example

1 March 2019

Non-Deterministic Domains

Methods for Handling Indeterminacy

Sensing with Percepts

Belief States

There are three approaches:

  1. A belief state is a set of state representations that the agent thinks might be the case.

    1554365037393

  2. Logical sentences can capture a belief state.

  3. Knowledge propositions e.g. $K(\text{AtR}) \land K(\text{CleanR})$ (i.e. closed-world assumption).

We'll use the second method in this course, but clearly there is some loss of expressiveness.

Sensorless Planning

Rules:

Extending Action Representations

Conditional Effects

1554366203459

Others

Contingent Planning

Acyclic vs Cyclic Solutions
Non-determinism and Partially Observable Environments

5 March 2019

Online Planning

Execution Monitoring and Replanning

Hierarchical Decomposition in Planning

Searching for Primitive Solutions

Breadth First Search
Problems
Adding Preconditions and Effects to HLAs
Formalisms
Defining REACH
Approximate Descriptions of REACH

Optimistic Description $\text{REACH}^+(s, h)$

Pessimistic Description $\text{REACH}^-(s, h)$

$$\text{REACH}^-(s, h) \subseteq \text{REACH}(s, h) \subseteq \text{REACH}^+(s, h)$$

A Better Algorithm

We know that

  1. If $\exists s' \in \text{REACH}^-(s, h)$ such that $s' \vDash g$, we know that $h$ can succeed.
  2. If $\lnot\exists s' \in \text{REACH}^+(s, h)$ such that $s' \vDash g$, we know that $h$ will fail.

Thus the algorithm is:

7 March 2019

This lecture is a soft introduction.

Handling Uncertainty

Using Classical Logic to Handle Uncertainty

Degrees of Belief and Probabilities

Rational Decisions

Decision Theory

Introduction to Probability

The Axioms of Probability

1554380493244

12 March 2019

Inference with Joint Probability Distributions

Marginalisation, Conditioning & Normalisation

1554384555599

A General Inference Procedure

Independence

Bayes' Rule

Bayes' rule is derived by writing the product rule in two forms and equating them:

$$\begin{align*} \Pr(a \land b) &= \Pr(a \mid b)\Pr(b)\\ \Pr(a \land b) &= \Pr(b \mid a)\Pr(a)\\ \therefore \Pr(b \mid a) &= \frac{\Pr(a \mid b)\Pr(b)}{\Pr(a)} \end{align*}​$$

General case for multivaried variables using background evidence $e$:

$$\Pr(Y \mid X, e) = \dfrac{\Pr(X \mid Y, e) \Pr(Y \mid e)}{\Pr(X \mid e)}$$

It is useful because often we have good estimates for three terms on the right and are interested in the fourth.

Applying Bayes' Rule

Combining Evidence

Conditional Independence

14 March 2019

Bayesian Networks

An Example

1554573308955

Note that:

Semantics of Bayesian Networks

Topological Semantics of Conditional Independence

1554575139021

  1. A node is conditionally independent of its non-descendants, given its parents.

  2. A node is conditionally independent of all other nodes, given its Markov Blanket, i.e.

    1. its parents
    2. its children
    3. its children's parents

(Even More) Efficient Representation of CPD

Noisy-OR relationships

Example

BNs with Continuous Variables

15 March 2019

Exact Inference in Bayesian Networks

Exact Inference by Enumeration

Example

1554573308955

The Variable Elimination Algorithm

Pointwise Product

Example:

1554626799089

Tips:

An Example

1554573308955

1554627268137

19 March 2019

Approximate Inference in Bayesian Networks

Direct Sampling Methods

Example

1554629666461

Direct Sampling Continued

Rejection Sampling

Likelihood Weighting

Example

1554629666461

1554631206112

Why It Works?

1554632224019

Problems

The Markov Chain Monte Carlo (MCMC) Algorithm

Example

1554629666461

1554633012953

Simply:

Why It Works?

Basic idea of proof that MCMC is consistent is as follows:

The sampling process settles into a "dynamic equilibrium" in which the long-term fraction of time spent in each state is exactly proportional to its posterior probability.

21 & 22 March 2019

Time and Dynamic Environments

States and Observations

Stationary Processes and The Markov Assumption

Inference Tasks in Temporal Models

Filtering/Monitoring

Prediction

Likelihood of Evidence Sequence

Smoothing/Hindsight

1554712017030

Example

1554638275988

1554713827657

1554713851549

Most Likely Explanation/Sequence

Hidden Markov Models (HMM)

26 March 2019

Personal Notice

I think this section is quite sloppy, at least the concepts themselves. It seems to rely a lot on gut feelings of their inventors than actual theories so don't sweat over it too much. Read it casually and try having a conceptual understanding instead.

Dynamic Bayesian Networks (DBN)

Constructing Dynamic Bayesian Networks

Modelling Failure

Transient Failure

Persistent Failure

1554721445915

1554721881906

Exact Inference in DBNs

BNs, HMMs, and DBNs

1554723143576

28 March 2019

Beliefs and Desires

"So I say, walk by the Spirit, and you will not gratify the desires of the flesh but of robots."

--- Galatians 5:16

Utility Theory & Utility Functions

Constraints on Rational Preferences

Lotteries

Axioms on Preference

Axioms of Utility

Utility Scales

Decision Networks (DN) (Influence Diagrams)

Action-Utility Tables & Graphs

Evaluating Decision Networks

29 March 2019

Sequential Decision Problems

Markov Decision Process (MDP)

Optimality in Sequential Decision Problems

Value Iteration

Explanation

Utilities of States

Decision-Theoretic Agents


https://allthingsd.com/files/2013/03/Thats_All_Folks.jpg