AI I WS22/23 - Summary

Basics

Rational Agents

An agent is an entity that perceives (via sensors) and acts (via actuators).
An agent can perceive percepts from a set $P$ and perform actions from a set $A$.
An agent function $f_a : P^* \to A$ models an agent as a mapping from percept histories to actions.¹

A performance measure is a function that evaluates a sequence of environments.

An agent is rational, if it chooses the action that maximises the expected value of the performance measure given the percept history.

An agent is autonomous, if it does not rely on prior knowledge of its designer.

PEAS description

To design a rational agent, we specify the task environment as

P erformance measure
E nvironment
A ctuators
S ensors

Environments

An Environment $e$ of an agent $a$ can be

fully observable, if $a$'s sensor have access to the complete state of $e$ (else partially observable)
deterministic, if the next state of $e$ is completely determined by the current state and $a$'s action (else stochastic)
episodic, if it can be divided into atomic episodes where $a$ perceives an performs a single action (else sequential)
dynamic, if $e$ can change without $a$ performing an action (else static). semidynamic, if $e$ does not change but the performance measure does
discrete, if the set of $e$'s states and the set of $a$'s actions are countable (else continuous)
single agent, if only one agent acts on the enviroment (else multi agent)

Agent Types

Simple reflex agent

An agent that bases its actions on only the last percept.
The agent function reduces to $f_a : P \to A$

Model based agent

A reflex agent that maintains a world model to determine its action.
Its agent function depends on:

a set $\mathcal{S}$ of states
a sensor model $S$, that given a state $s$ and percepts $e$ determines the next state
an action function $f$ that maps states to actions

The agent function is then computed iteratively as $e \mapsto f(S(s,e))$

Goal based agent

A model based agent with a transition model $T$ that decides actions based on a world model and goals.

Utility based agent

An agent with a world model and a utility function that measures a state.
The agent chooses to maximise the expected utility.

States

A state representation is

atomic if it has no internal structure
factored if each state is characterised by attributes and their values
structured if the state includes objects and their relations

Search

A search problem consists of

a set $\mathcal{S}$ of states
a set $\mathcal{A}$ of actions
a transition model $\mathcal{T} : \mathcal{A} \times \mathcal{S} \to \mathcal{P}(\mathcal{S})$ that maps an action $a \in \mathcal{A}$ and a state $s \in \mathcal{S}$ to a set of successor states
a set $\mathcal{I} \subseteq \mathcal{S}$ of initial states
a set $\mathcal{G} \subseteq \mathcal{S}$ of goal states

Uninformed Search

BFS

DFS

Informed Search

Greedy

A*

Adversarial Search

MinMax

AlphaBeta

MonteCarlo

Constraint Satisfaction

A constraint satisfaction problem is a search problem given by

a finite set of variables $V := \{X_1, \dots X_n\}$
a family of domains $D : \{D_v \mid v \in V\}$
a set of constraints

A CSP is

binary if all constraints relate at most two variables
discrete if all variables have countable domains (else continuous)

Constraint Network

A constraint network is a CSP with a set of binary constraints
\[ C := \{C_{uv} = C_{vu} \subseteq D_u \times D_v \mid u,v \in V, u \neq v \} \]
Any CSP can be represented by a constraint network

Assignments

A partial assignment for a constraint network is a partial function

Constraint Propagation

Forward Checking

Arc Consistency

Cutset Conditioning

Logic

We write $\varphi \vDash A$ if $A$ is true for an assignment $\varphi$

If for every $\varphi$, $\varphi \vDash A$ implies $\varphi \vDash B$ then we write $A \vDash B$ ($A$ entails $B$) (note the polymorphism of $\vDash$)

A calculus $C$ for a logic is a set of inference rules. It is

sound if $A\vdash_C B \implies A \vDash B$
complete if $A \vDash B \implies A \vdash_C B$

Propositional Logic

SAT

First-Order Logic

Natural Deduction

A calculus for first order logic.

∧-intro	\NDANDI{A}{B}

∧-Introduction	\begin{prooftree} \AxiomC{A} \AxiomC{B} \BinaryInfC{$A \land B$} \end{prooftree}
∧-Elimination-left	\begin{prooftree} \AxiomC{$A \land B$} \UnaryInfC{$A$} \end{prooftree}
∧-Elimination-right	\begin{prooftree} \AxiomC{$A \land B$} \UnaryInfC{$B$} \end{prooftree}
⇒-Introduction	\begin{prooftree} \AxiomC{A} \UnaryInfC{B} \UnaryInfC{$A \implies B$} \end{prooftree}

\begin{prooftree} \AxiomC{$A \implies B$} \AxiomC{A} \RightLabel{$\implies\,E$} \BinaryInfC{B} \end{prooftree}\\ \begin{prooftree} \AxiomC{$[B/X](A)$} \RightLabel{$\exists I$} \UnaryInfC{$\exists X \ldotp A$} \end{prooftree}\\ \begin{prooftree} \AxiomC{$\exists X \ldotp A$} \AxiomC{$[c/X](A)$} \UnaryInfC{B} \RightLabel{$\exists E$} \BinaryInfC{$B$} \end{prooftree}\\ \begin{prooftree} \AxiomC{A} \RightLabel{$\forall I$} \UnaryInfC{$\forall X \ldotp A$} \end{prooftree}\\ \begin{prooftree} \AxiomC{$\forall X \ldotp A$} \RightLabel{$\forall E$} \UnaryInfC{$[B/X](A)$} \end{prooftree}\\ \begin{prooftree} \AxiomC{} \RightLabel{LEM} \UnaryInfC{$A \lor \neg A$} \end{prooftree}

Analytical Tableau

Resolution

Knowledge Representation

$\mathcal{ALC}$

Planning

STRIPS

A STRIPS task is a quadruple $\Pi = \langle P, A, I, G \rangle$ where

$P$ is a finite set of facts
$A$ is a finite set of actions where each action $a = \langle \mathrm{pre}, \mathrm{add}, \mathrm{del}$ consist of
- precondition
- add list
- delete list
$I \subseteq P$ is the initial state
$G \subseteq P$ is the goal

A STRIPS task is a search problem $\langle S, A, T, I, S^G \rangle$ where

$S = \mathcal{P}(P)$
$T$ is a transition model
if for an action $a$, $pre_a \subseteq s$, then $a$ is applicable in $s$
$S^G = \{s \in S \mid G \subseteq s\}$

Partial Order Planning

Let $\Pi = \langle P, A, I, G \rangle$ be a STRIPS task.
Then $\mathcal{P} = \langle V, E \rangle$ is a partially ordered plan as a DAG, where the nodes $V$ are actions from A or

a start step with effect $I$
a finish step with precondition $G$

Every edge $\langle S,T\rangle$ is labeled with either

A non-empty set $p \subseteq P$ of facts that are effects of $S$ and preconditions of $T$
$S \overset{s}{\to} T$
$S \prec T$ a temporal constraint

Clobbering

In a partially ordered plan, a step $C$ clobbers a causal link $L := S \overset{s}{\to} T$ iff it destroys the condition $p$ achieved by $L$.

If $C$ clobbers $S \overset{s}{\to} T$ in $\Pi$, then we can

demote: add a temporal constraint $C\prec S$ to $\Pi$
promote: add $T\prec C$ to $\Pi$

Delete Relaxation

h+ heuristic

Footnotes:

here $P^*$ refers to the Kleene star of $P$