#+title: AI I WS22/23 - Summary #+author: Florian Guthmann #+email: florian.guthmann@fau.de #+options: toc:nil num:nil \n:t html-style:nil html5-fancy:t #+html_doctype: xhtml5 #+html_head: * 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.[fn:1] 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][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. | \land-Introduction | \begin{prooftree} \AxiomC{A} \AxiomC{B} \BinaryInfC{$A \land B$} \end{prooftree} | | \land-Elimination-left | \begin{prooftree} \AxiomC{$A \land B$} \UnaryInfC{$A$} \end{prooftree} | | \land-Elimination-right | \begin{prooftree} \AxiomC{$A \land B$} \UnaryInfC{$B$} \end{prooftree} | | \Rightarrow-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 [fn:1] here $P^*$ refers to the [[https://en.wikipedia.org/wiki/Kleene_star][Kleene star]] of $P$