人工智能

• 制定决策   (2022-06-07)
• 贝叶斯网络与概率推理   (2022-05-30)
• 自动规划   (2022-05-24)
• 自动推理   (2022-05-22)
• 逻辑Agent   (2022-05-21)
• 约束满足问题   (2022-05-20)
• 对抗搜索算法   (2022-05-18)
• 局部搜索算法   (2022-05-18)
• 经典搜索算法   (2022-05-13)
• Agent智能体   (2022-05-03)

以下显示部分文章预览。

制定决策

偏好(Preferences)
假设Agent将在一组行为之间进行选择，每个行为可以视为一次抽奖。
假设一个行为的可能结果为\(S_1,\cdots,S_n,\) 其对应的发生概率为\(p_1,\cdots,p_n\)，则该行为可以记作\[L=[p_1,S_1;\cdots;p_n,S_n]\]其中每个输出是一个原子状态或另一次抽奖（行为）。

首先约定以下记号：
\(A\succ B\)表示Agent偏好A高于B；
\(A\sim B\)表示A和B之间偏好相同；
\(A\succsim B\)表示偏好A高于B，或者偏好相同。

偏好应当遵循以下几个公理：
(1) 有序性（operability）：\[(A\succ B)\lor (A\sim B)\lor (B\succ A)\]
(2) 传递性（Transitivity）：\[(A\succ B)\land (B\succ C)\Rightarrow (A\succ C)\]
(3) 连续性（Continuity）：\[A\succ B \succ C\Rightarrow \exists p,\ B\sim [p,A;1-p,C]\]
(4) 可替换性（Substitutability）：\[A\sim B \Rightarrow [p,A;1-p,C]\sim [p,B;1-p,C]\](对\(\succ\)也成立；)
(5) 单调性（Monotonicity）：\[A\succ B\Rightarrow p\ge q\Leftrightarrow [p,A;1-p, B]\succ [q,A;1-q,B]\]
(6) 可分解性（decomposability）：\[[p,A;1-p,[q,B;1-q,C]]\sim[p,A;(1-p)q,B;(1-p)(1-q), C]\]
效用(Utilities)
偏好可以用效用函数(utility function)来描述。用实数\(U(s)\)来表达对某个状态\(s\)的喜好程度。
在给定证据\(e\)的情况下，某个动作\(a\)的期望效用\(EU(a|e)\)等于输出结果的依概率加权平均效用值：\[EU(a|e)=\sum\limits_{s'} P(Result(a)=s'|a,e)U(s')\]
定理：如果一些偏好满足偏好公理，则存在实值效用函数\(U\)使得\[U(A)\ge U(B)\Leftrightarrow A\succsim B;\\U([p_1,S_1;\cdots;p_n,S_n])=\sum_i p_iU(S_i).\]
最大期望效用原理：Agent根据期望效用最大的原则来选择动作，\[a^*=\arg\max_a EU(a|e).\]
效用函数
首先约定最好和最坏的可能结果分别为\(u_\top,u_\bot\). 归一化效用是指满足\(u_top=1,u_\bot=0\)的效用。
对于一次抽奖\(L\), 其期待货币价值(expected monetary value)称为\(EMV(L)\)。一般来讲为了规避风险，人们会选择\(U(L) < U(EMV(L))\).

多属性效用函数(Multiattribute utility)\(U(x_1,\cdots,x_n)\)：根据多个变量进行决策。
严格优势(Strict dominance): 选择B相对于A是有严格优势的，如果\(\forall i, X_i(B)\ge X_i(A)\).
然而在多数情况下，严格优势并不总成立。
随机优势(Stochastic dominance): 设行动\(A_1,A_2\)在属性\(X\)上有概率分布\(p_1,p_2\)。称分布\(p_1\)比\(p_2\)在属性\(X\)上具有随机优势，如果满足\[\forall t, \int_{-\infty}^t p_1(x)dx \le \int_{-\infty}^t p_2(x)dx\]如果效用函数\(U(x)\)关于\(x\)单调不减，则\(A_1\)的效用期望不低于\(A_2\)。

偏好独立性(Perferentially independent, PI): 称属性\(X_1,X_2\)偏好独立于\(X_3\)，如果在\(\langle x_1,x_2,x_3\rangle\)和\(\langle x_1',x_2',x_3\rangle\)之间的偏好与\(x_3\)的值无关。
相互偏好独立性(Mutual Perferentially Independent, MPI)：如果每对属性都是偏好独立的。此时每个属性子集都独立偏好于其补集。

定理：如果一组属性\(X_1,\cdots,X_n\)是相互偏好独立的，则存在一个加法值函数\[V(S)=\sum_{i=1}^n V_i(X_i(S)).\]
从效用的角度来看，如果属性集X中抽奖的偏好与属性集Y无关，称X是效用独立(utility independent, UI)于Y的。
如果属性集的每个子集都独立于其余的属性，则称此属性集为相互效用独立的(MUI)。此时Agent的行为可以用乘法效用函数来描述，如\[U=\sum_i k_iU_i + \sum_{i,j}k_ik_jU_iU_j + k_1k_2k_3U_1U_2U_3.\]

    发表于2022-06-07

贝叶斯网络与概率推理

贝叶斯网络(Bayesian networks)
贝叶斯网络是一个有向图，每个结点对应一个随机变量，一组有向边连接结点。如果结点X指向结点Y，称X是Y的父结点。每个结点\(X_i\)有一个条件概率分布\[\mathbb P(X_i|Parents(X_i))\]用于刻画其父结点对其对影响。

贝叶斯网络的构建：
1. 选定一列（有序的）随机变量\(X_1,\cdots, X_n\);
2. 对\(i=1...n\), 将\(X_i\)添加到网络中，并选择其父结点满足：\[\mathbb P(X_i|Parents(X_i))=\mathbb P(X_i|X_1,\cdots, X_{i-1}).\]

联合分布：\[P(x_1,\cdots, x_n) = \prod_{i=1}^n P(x_i|parents(X_i))\]
概率推理
1. 通过枚举进行推理
根据公式\[\mathbb P(X|e)=\alpha\ \mathbb P(X,e) = \alpha\sum_y \mathbb P(X,e,y)\]对所有变量的可能取值进行枚举后求和。当有n个布尔变量时，算法复杂度为\(O(n\cdot 2^n)\).

2. 变量消元算法
采用动态规划。按照从右到左的顺序\((X_n,X_{n-1},\cdots, X_1)\)计算表达式，并存储中间结果。

    发表于2022-05-30

自动规划

规划(Planning)问题
规划是指设计一个动作规划以达到目标。规划选择要素化表示(factored representation)，用一组变量表示世界的一个状态。

经典规划
PDDL语言：
状态是流(fluent)的合取，这些流是基元的(无变量的)、无函数的原子。
动作：由一些动作模式(action schema)组成的集合.
每个动作模式包含变量列表、前提(precondition)和效果(effect). 前提和效果是由可以包含状态的文字(literal)的合取。

在状态s执行一个动作a的结果是一个状态s':
首先\(Del(a)\)，删去a的效果中的负文字；然后\(Add(a)\)， 加入a的效果中的正文字。可以写为\(Result(s,a) = (s-Del(a))\cup Add(a)\).

一组动作模式可以定义为规划域(domain). 域中的一个特定问题用一个初始状态和一个目标来定义：
初始状态是基元原子的合取，这里使用封闭世界假设（即没有提到的原子都是假的）。目标是可以含有变量的文字的合取。

经典规划问题可以视为搜索问题，通过前向/后向搜索求解，也可以定义启发式搜索。

分层规划(Hierarchical Planning)
层次任务网络(Hierarchical task network(HTN)):
包含基元动作(primitive actions)（具有标准的前提-效果模式）和高层动作(high-level action, HLA)，包含至少一个细化(refinement)的动作序列，序列中每个动作可以是一个HLA或一个基元动作。一个只包含基元动作的HLA细化称为HLA的实现（implementation）。

一般用单个称为Act的顶层动作来表示HTN规划，目的是找到达到目标的Act的实现。经典规划问题可以定义为对每个基元动作\(a_i\)，Act有一个细化\([a_i,Act]\), 这意味着递归定义了Act使得可以任意地向里面添加动作。另一方面，通过为Act提供另一个细化，使得步骤列表为空，前提为达到问题目标，来最终消去Act。可以通过搜索算法（如BFS，DFS）搜索找到基元实现。

情景演算(situation calculus)
将一阶逻辑加入到规划问题中。
初始状态\(S_0\)称为一个情景. 如果s是情景，a是动作，则\(Result(s,a)\)（或\(do(s,a)\)）也是情景。情景对应动作的一个序列或历史。

能够从一个情景变化到下一个情景的一个函数或关系称为流(fluent). 一般地，情景s作为流的最后一个参数。如关系(谓词)流\(Hold(r,x,s)\)表明机器人r在情景s下握住x。类似有函数流。

每个动作的前提条件(preconditions), 如\[Poss(pickup(r,x),s)\Leftrightarrow \forall z.\lnot Holding(r,z,s)\land NextTo(r,x,s)\]
每个动作也有效果(effect)：根据动作的结果得到的流。称为效果公理。如\[Fragile(x)\Rightarrow Broken(x, do(drop(r,x),s))\]
效果公理的规范形式：
(1) \(P_F(x,a,s) \Rightarrow F(x, do(a,s))\)
(2) \(N_F(x,a,s) \Rightarrow\lnot F(x, do(a,s))\)
如上面的效果可以改写为\[\exists r.\{a = drop(r,x)\}\Rightarrow Broken(x, do(a,s))\]
解释闭包公理(Explanation closure axiom)
(3) \(\lnot F(x,s)\land F(x, do(a,s))\Rightarrow P_F(x,a,s)\), 如果流F原本是False，但经过动作a之后变成True，则\(P_F\)必须变成True。
(4) \(F(x,s)\land \lnot F(x,do(a,s))\Rightarrow N_F(x,a,s)\), 如果流F原本是True但经过动作a之后变成False，则\(N_F\)必须变成True。

后继状态公理(successor state axioms)
F在后继状态中为True 当且仅当以下至少之一成立：
(a) 某动作使F成立
(b) F原本是True，且没有动作使F变成False
例：\[Holding(r, g, do(a,s))\Leftrightarrow\\ a=Grab(g)\lor[ Holding(r, g, s)\land a\ne Release(g)]\]

    发表于2022-05-24

自动推理

自动定理证明
假言推理(Modus Ponens, MP): \[\frac{a,\quad a\Rightarrow b}{b}\]
And-Introduction, AI: \[\frac{a,\quad b}{a\land b}\]
全称量词实例化(Universal instantiation, UI)\[\frac{\forall v\quad a}{Subst(\{v/g\},a)}\]其中v为变元(variable)，g为基项（没有变量的项, ground term）。此实例化可说明所有的变元v替换成基项g后，a仍成立。

存在量词实例化(Existential instantiation, EI)\[\frac{\exists v\quad a}{Subset(\{v/k\},a)}\]其中k应当是一个从未在知识库中出现过的常量符号k，称为Skolen常数。

前向链接(Forward Chaining)与反向链接(Backward Chaining)
合取范式(Conjunctive Normal Form, CNF): 由文字(literals)的析取子句进行合取得到的语句，如\((A\lor\lnot B)\land(B\lor C\lor \lnot D)\).
限定子句(Definite clause): 恰好只含一个正文字的析取式。如\(A\lor B\lor \lnot C\)不是，但\(\lnot A \lor\lnot B\lor C\)是限定子句。限定子句可以改写成蕴含式的形式，如上例为\(A\land B\Rightarrow C\).
Horn子句：至多含一个正文字的析取式。
目标子句(Goal clause): 不含正文字的析取式。

前向链接：判定单个命题词是否被限定子句的知识库所蕴含。
枚举所有现有知识库中命题符号可以推出的命题，如果不在KB中，就将新结论加入，直到要查询的命题词(query)被证明。通过维护每个命题符号的蕴含前提的命题符号个数进行推断。

反向链接与前向链接类似，从查询的命题符号开始推理。为了证明q，检查q是否已知或者证明q的所有前提。
前向链接和反向链接对Horn KB是可靠且完备的，但对一阶逻辑FOL不是完备的。

归结(Resolution)
归结是一个反证过程：为证明\(KB\vDash a\), 归结为\(KB\land\lnot a\)是不可满足的。归结需要用合取范式CNF的形式，将两个子句\(C_1,C_2\)归结为\(C\), 称为归结式子句(resolvent). 当归结式子句为空时得证（相当于推出矛盾）。
对于两个CNF \(C_1,C_2\)中分别包括的互补文字\(A,\lnot A\)，归结后可消去；相同文字可合并成一个。

命题逻辑中，语句到CNF的转化：
1. 用两个\(\rightarrow\)的合取消去\(\Leftrightarrow\);
2. 用\(A\lor\lnot B\)消去\(B\Rightarrow A\);
3. 使用摩根律将\(\lnot\)移到文字前；
4. 使用分配律调整\(\land,\lor\)为CNF。
归结证明算法：首先将clauses初始化为\(KB\land\lnot a\)的CNF表示。
用new\(=\{\}\)维护新产生的子句。
1. 对每一对clauses中的\(C_i,C_j\)，归结为新的子句resolvents.
| a. 如果resolvents为空语句，则命题得证。
| b. 否则，将resolvents 加入new中。
2. 判断是否有news\(\subseteq\) clauses.
| a. 如果成立，则无新子句产生，证明失败。
| b. 否则，将clauses \(\cup\) new赋给 clauses; 并回到1.

合一(Unification)
合一置换是指使不同的逻辑表示变得相同的置换。
合一算法Unify以两条语句为输入，如果存在合一置换，则返回之：\(Unify(p,q)=\theta\), 其中\(Subst(\theta,p)=Subst(\theta,q)\).
如果两个语句使用了相同的变量x，则不能进行合一置换，但可以通过新的命名解决这一问题。

对每一对可以合一的表达式，存在唯一的最一般合一置换(Most General Unifiers, MGU).

    发表于2022-05-22

逻辑Agent

基于知识的Agent
知识库（Knowledge Base, KB): 是一个语句集合，用逻辑语言描述。
推理器（Inference Engine, IE): 使用逻辑推理的算法。
Agent维护一个数据库KB，通过告诉(Tell)和询问(Ask)来更新数据库内容以及选择采取的行动。

命题逻辑
语法：
命题符号\(P_1,P_2,\cdots\)为语句（称为原子语句）。
如果\(S_1,S_2\)为语句，则以下也为语句：
1. \(\lnot S_1\) (negation). 一个文字(literal)是指一个命题符号或者其否定式。
2. \(S_1\land S_2\) (conjunction)
3. \(S_1\lor S_2\) (disjunction)
4. \(S_1\Rightarrow S_2\) (implication)
5. \(S_1\Leftrightarrow S_2\) (biconditional)

命题逻辑的语义与\(\lnot, \land,\lor,\Leftrightarrow, \Rightarrow\)的常识语义相同。

蕴含(Entailment)
数据库KB蕴含语句\(\alpha\)指在所有KB成立的情况下，\(\alpha\)总是成立。记作\(KB\vDash\alpha\).
对于语句\(\alpha\), 如果m蕴含\(\alpha\)，即\(\alpha\)在取值m下成立，记作\(m\vDash \alpha\), 称m为\(\alpha\)的一个模型(model).
用\(M(\alpha)\)表示\(\alpha\)的全体模型组成的集合。因此，\(KB\vDash\alpha\)当且仅当\(M(KB)\subseteq M(\alpha)\).

推理(Inference)
如果推理算法\(i\)能够根据KB得到\(\alpha\), 记为\(KB\vdash _i\alpha\), 称为\(\alpha\)通过i从KB导出。

如果\(KB\vdash_i\alpha\)蕴含\(KB\vDash\alpha\)，称算法\(i\)是可靠的(soundness).
如果\(KB\vDash\alpha\)蕴含\(KB\vdash_i\alpha\)，称算法\(i\)是完备的(completness).

通过枚举所有可能取值进行推断：使用深度优先枚举所有命题符号的取值(True/False)进行推断，是可靠且完备的。算法是\(O(2^n)\)且co-NP完全的。

两个语句是逻辑等价的，如果\(\alpha\vDash\beta,\beta\vDash\alpha\). 此时记作\(\alpha\equiv \beta\).

有效性(Validity)与可满足性(Satisfiability)
一个语句a称为有效的，如果在所有模型中均为真，此时a被称为重言式。
演绎定理(Deduction Theorem): \(KB\vDash\alpha\)成立当且仅当语句\((KB\Rightarrow\alpha)\)是有效的（重言式）。

可满足性：
语句a称为可满足的，如果存在一个模型使其成立。
反证法（归谬法, reductio, absurdum): \(KB\vDash\alpha\)成立当且仅当\((KB\land\lnot\alpha)\)是不可满足的。

一阶逻辑(First-Order Logic, FOL)
一阶逻辑的词汇表包括常量(Constants)、谓词(Predicates)、函数(Functions)、变量(Variables)、连接词(Connectives: \(\land, \lor, \lnot, \Rightarrow, \Leftrightarrow\))、等号(Equality, =)、量词(Quantifiers: \(\forall,\exists\))。

元数(parity): 自变量的个数。0元谓词即命题符号，0元函数为常量。
项(Term) \(:=function(term_1,\cdots,term_n)\ |constant\ |variable\)
原子语句(Atomic sentences) \(:=predicate(term_1,\cdots,term_n)\ |term_1=term_2\)

复合语句(Complex sentences)由原子语句和连接词归纳定义。
1. 每个原子语句是一个复合语句。
2. 如果\(S_1,S_2\)是复合语句，\(x\)是一个变量，则以下皆为复合语句：
\(\lnot S_1, S_1\land S_2, S_1\lor S_2, S_1\Rightarrow S_2, S_1\Leftrightarrow S_2,\forall x.S_1(x), \exists x.S_1(x).\)

    发表于2022-05-21

约束满足问题

定义约束满足问题
约束满足问题(Constraint satisfaction problems, CSP)是一种简单的形式化表示语言。当一组变量的一种取值满足所有变量约束时，问题就得到了解决。

约束满足问题包含三个成分：\(X,D,C\).
X是变量集合\(X_1,\cdots,X_n\);
D是值域集合\(D_1,\cdots,D_n\);
C是描述变量取值的约束集合。每个约束\(C_i\)是有序对\(\langle scope, rel\rangle\), scope是约束中的变量组，rel定义了这些变量取值应满足的关系。

问题的状态由对部分或全部变量的一个赋值来定义。一组不违反约束的赋值称为相容的(consistent), 每个变量都有值的赋值称为完全的(complete). CSP的解即为相容且完全的一组赋值。

约束条件的种类：一元(Unary) 、二元(Binary) 或多元(Higher-order).
使用对偶图可以将任意n元CSP转换成二元CSP。变量个数人意的约束称为全局约束，如AllDiff.

现实世界中还会有一些偏好约束(Preferences), 指出在不违反所有(绝对)约束的情况下，哪些解是更好的。这样的问题称为约束优化问题(constrained optimization)

CSP中的推理
推断(Inference)选择使用约束来减少某个变量的合法取值范围，从而进一步减少其他变量的合法取值范围。这一过程称为约束传播(constraint propagation). 其核心思想是局部相容性。

1. 弧相容(Arc consistency)
单个变量满足一元约束称为结点相容（容易解决，这里不讨论），两个变量满足二元约束称为弧相容。弧\(X\to Y\)是相容的，当且仅当对每个X的取值\(x\), 都有一个Y的取值\(y\)使得\((x,y)\)满足约束。如果每个变量X相对其他变量Y都是弧相容的，称网络是弧相容的（此处默认只有二元约束）。

如果利用弧相容\(X\to Y\)删去了X的一部分取值，则与X相容的变量\(Z\to X\)也需要被重新检查。弧相容可以视为求解CSP问题的预处理。可以采用AC-3算法来解决弧相容：维护一个弧相容队列，每弹出一组\((Xto Y)\), 如果X发生变化，则所有指向X的弧需要被重新加入队列中。

2. 路径相容(Path consistency)
路径相容通过观察变量得到隐式约束并以此来加强二元约束。两个变量的集合\(\{X_i,X_j\}\)相对于第三个变量\(X_m\)是相容的，如果对\(X_i,X_j\)的每一组二元相容赋值\((a,b)\), \(X_m\)都有一个取值\(c\)使得\((a,c),(c,b)\)同时是相容的。

3. k-相容(k-consistency)
以上相容的概念可以推广到k个变量中：如果对任何\(k-1\)个变量的一组合法取值，都存在第k个变量的一个取值与之相容，称这个CSP是k相容的。弧相容、路径相容分别是\(k=2,k=3\)的特例。如果一个图是\(1,2,\cdots,k\)-相容的，称其为强k相容的。

CSP的回溯搜索
CSP的赋值具有可交换性，不必考虑赋值顺序。因此只需要考虑搜索树一个结点的单个变量。回溯搜索用于深度优先搜索中，每次为一个变量选择一个赋值，当没有变量合法取值时就回溯。

高效回溯搜索，需要考虑的问题：
1. 下一步选择哪个变量赋值？
采取最少剩余值(MRV, minimum remaining values)启发式，选择合法值域个数最少的变量。也可以采用度启发式(Degree heuristic)，选择与未赋值变量约束最多的变量。

2. 按什么顺序尝试当前变量的赋值？
采取最少约束值(LCV, least constraining value)启发式，优先选择给邻居提供更多选择的值。

3. 每步搜索通过什么样的推理约简搜索空间？
前向检验(FC, Forward Checking), 当X被赋值x时，对所有与X弧相容的Y值进行检验，删去其中与x不相容的值。
FC不能检验出所有不相容，因为它使当前变量弧相容，但并不向前看使其它变量弧相容。算法MAC(maintaining arc consistency)用于解决这一问题，在一个变量X被赋值之后，利用AC-3进行推断，从与X邻接的所有弧\(Y\to X\)出发进行约束传播。

CSP局部搜索
使用完整状态的形式化，初始状态是每个变量（随机）赋一个值。最简单的启发式是最小冲突启发式。这样可以采取一些局部搜索算法（如爬山法，模拟退火）。

    发表于2022-05-20

对抗搜索算法

博弈游戏
博弈游戏可以形式化为包含以下组成部分的搜索问题：
\(s_0\)初始状态；
\(Player(s)\) 定义此时该谁行动；
\(Actions(s)\) 定义此状态下的合法移动集合；
\(Result(s,a)\) 转移模型；
\(Terminal\_Test(s)\) 终止测试，若游戏结束返回真；
\(Utility(s, p)\) 效用函数，定义游戏者p在终止状态s下的数值。

Minimax算法
结点的极大极小值(Minimax)即为效用值。
\[Minimax(s) =\begin{cases} Utility(s), & Terminal(s)\\ \max\limits_{a\in Actions(s)} Minimax(Result(s,a)), &MAX\_Node(s)\\ \min\limits_{a\in Actions(s)}Minimax(Result(s,a)), &MIN\_Node(s)\end{cases}\]

\(\alpha-\beta\)剪枝
\(\alpha\)是到目前为止的路径上，发现的MAX的最佳选择；
\(\beta\)是到目前为止的路径上， 发现的MIN的最佳选择。
对于MAX，如果新分支v比\(\alpha\)还差，则剪掉这一分支。
对于MIN，如果新分支v比\(\beta\)更好，则剪掉这一分支。

不完美决策
确定性(deterministic)的游戏可能有不完全的信息。
使用截断测试\(Cutoff\_Test(s, d)\)代替终止测试。

    发表于2022-05-18

局部搜索算法

局部搜索算法
局部搜索算法不关注路径，而是从单个当前节点只移动到他的邻近状态。局部搜索算法也常用于解决最优化问题。

1. 爬山法(Hill-climbing)
贪心局部搜索，每次向值最优的邻接状态移动。当所有邻点的值都不超过当前结点时终止。

随即重启爬山法(random restart hill climbing): 每次随机生成一个初始状态开始爬山。
随机爬山法(random sideway moves): 随机选择下一步，被选中的概率依目标函数增益而定。

2. 模拟退火(Simulated annealing)
随机选择一个后继结点。
如果该移动对函数值有增益，则接受。否则，如果损失为\(\Delta E\), 以\(e^{\frac{\Delta E}{T}}\)的概率选择。T为超参数。

3. 局部束搜索(Local Beam Search)
局部束搜索是对束搜索(Beam Search)的改版，每次记录k个状态而不是1个。
每步搜索从当前k个结点的全部后继中选择最好的k个进行更新。
注意，这并不等同于k个相同的搜索算法并行，因为可能会有同一个结点的多个后继被纳入新的维护结点中，同时也可能有结点因为所有后继都不够好而被放弃。

    发表于2022-05-18

经典搜索算法

问题求解Agent的一般形式
一个问题(Problem)可以由5个组成部分形式化描述：
1. Agent的状态\(S\)和初始状态\(s_0\in S\)
2. Agent可能的行动Actions，给定状态s，Agent可以应用的行动包括\(a\in Actions(s)\)
3. 转移模型(transition model) \(Result(s, a):S\times A\to S\)
4. 目标测试(Goal test). 检查当前状态是否已达目标，可以是显示集合也可能是隐式表达式
5. 路径好散函数(cost) \(c:S\times A \times S\to R_{\ge 0}\), 描述某组状态和动作的代价\(c(s,a,s')\).
问题的解是从初始状态到目标状态到一组行动序列。

搜索求解
先约定一些记号：用F(frontier)存储当前搜索的结点集合（如栈，队列），R(reached)存储已经搜索过的结点。用b(branch)表示搜索树中所有结点的子结点个数最大值， d(depth)表示最优解的搜索深度，m表示搜索空间的最大深度(可能是\(\infty\)). 对于结点s，约定\(g(s)\)为当前到达s的路径的损失。当有启发式信息时，用\(h(s)\)表示当前结点到目标结点的最小代价路径的估计值。

搜索策略的性能主要由以下几方面评价：
1. 完备性(completness): 问题有解时，是否一定能得到解；
2. 最优性(optimality): 有解时，得到的解是否一定是最优（代价最小的）
3. 时间复杂度
4. 空间复杂度

无信息搜索
1. 广度优先搜索(Breadth-first search)
每次扩展当前F中深度最浅的点。
当F非空时，选择F第一个点s，根据s下所有可行的动作得到一组新的s', 检验其中是否有已经达到目标的结点；若否，将s'都加入F的末尾，并将s加入R中(下同)。

完备性：True, 最优性：每步代价为1时 True
时间：\(O(b^{d+1})\), 空间\(O(b^{d+1})\)

2. 一致代价搜索(uniform-cost search)
每次扩展路径消耗\(g(n)\)最小的结点。通过对边缘结点集F的路径损失值g进行排序，并选择其中代价最小的点进行扩展。

完备性：当每个行动有一致下界\(\epsilon\)时True,否则可能进入无行动循环。 最优性：完备性成立时True
时间：\(O(b^{[C^*/\epsilon]+1})\), 空间\(O(b^{[C^*/\epsilon]+1})\), \(C^*\)为最优解的代价。

3. 深度优先搜索(Depth-first search)
每次选择F中最深的点进行扩展。
完备性：无穷深度的搜索空间下为False，最优性：False
时间：\(O({b^m})\). 空间：\(O(bm)\)

4. 深度受限搜索\(Depth-limited search)
对深度优先搜索设置深度上限\(l\), 使得深度为\(l\)的结点没有后继。

5. 迭代加深搜索(Iterative deepening search)
对深度受限搜索中的深度上限进行\(0\to\infty\)迭代。

有信息（启发式）搜索
1. 贪婪最佳优先搜索(best-first search)
每次扩展启发式信息最小（距离目标估计最近）的结点。如罗马尼亚问题中，采用到目标的直线距离作为\(h(s)\).

完备性：结点有限且有访问集R检验时为True, 最优性：False
时间/空间：\(O(b^m)\)

2. \(A^*\)搜索
评估\(f(s) = g(s) + h(s)\)并选取最小的点进行扩展。
当启发式函数\(h(s)\)满足可采纳性时，树搜索\(A^*\)算法是最优的。
当启发式函数\(h(s)\)满足可采纳性、一致性时，图搜索\(A^*\)算法是最优的。

可采纳性(admissible): 不会过高估计到达目标的代价。若从结点n出发，到达目标的实际代价为\(h^*(n)\)，可采纳性要求\(h(n)\le h^*(n)\).

一致性(consistent/ monotonic):
\[h(n)\le c(n,a,n') + h(n'),\quad\forall a\]这个条件比可采纳性更强一些。

3. 递归最佳优先搜索(Recursive best-first search, RBFS)
最佳优先搜索，但是存储空间受限，只使用线性空间。
每扩展一个结点，用变量\(f_{limit}\)记录从当前结点的祖先可得到的最佳可选路径（初始化为同级结点中最佳）的f值。如果当前结点超过了这个限制，即当前的路径有更好的替代方案可以选择，递归将回到可选路径上。
如果递归回溯，对当前路径上每个结点，用其余子结点的最佳f值替换原来的f值。
因此，RBFS可以记住被遗忘的子树中，最佳叶结点的f值，用于决定以后是否值得重新扩展该子树。

    发表于2022-05-13

Agent智能体

Agent和环境
Agent函数：\(f:\mathcal P^*\to\mathcal A\) 将感知序列映射为行动。

理性Agent
理性(Rational)行为的度量：依赖于以下4个方面
定义成功标准的性能度量；Agent对环境的先验知识；Agent可以完成的行动；Agent截止到此时的感知序列。
理性Agent：对每一个可能的感知序列，根据已知的感知序列提供的证据和Agent具有的先验知识，Agent应该选择使得性能度量最大化的行动。
理性≠全知(omniscient,clairvoyant)，感知不一定会提供所有信息，行为的结果也可能是未知的，只能使期望最大化。

环境的性质
PEAS描述：性能(Performance)，环境(Environment)，执行器(Actuators)，传感器(Sensors)

环境的性质：
1. 完全可观察(Observable)与部分可观察的；
2. 单Agent(Single-agent)与多Agent；
3. 确定的(Deterministic)与随机的（注意这里是相对于环境而言，即环境的下一状态是否完全取决于当前环境与Agent的动作）；
4. 片段的(Episodic)与延续式的；
5. 静态的(Static)与动态的；
6. 离散的(Discrete)与连续的；

Agent的结构
Agent = 体系结构 + 程序
4中基本的Agent程序：
1. 简单反射Agent (simpel reflex agent)
基于当前的感知选择行动，不关注感知历史

2. 基于模型的反射Agent (model-based reflex agent)
Agent根据感知历史维护内部状态。具体而言，Agent将根据现有状态state，采取的行动action，sensors对世界的感知perception，和知识模型model这四个输入变量共同维护新的state。然后，再根据新状态state和规则rules选取一条rule并决定下一步行动action.

3. 基于目标的Agent (Goal-based agent)
在模型的基础上，检查哪些行为的结果可以/有利于实现目标，并基于此选择下一步的行为。

4. 基于效用的Agent (Utility-based agent)
Agent利用效用(utility)函数度量性能，并根据每个行为之后的可能结果的效用来选择下一步行动。

学习Agent
学习Agent可以被划分为4个概念上的组建，包括:
评判元件(Critic) 反馈评价Agent做得如何，观察世界并把信息传递给学习元件；
学习元件(Learning element) 负责改进提高，影响性能元件；
性能元件(Performance element) 负责选择外部行动，
问题产生器(Problem generator) 可以得到新的和有信息的经验的行动提议。

    发表于2022-05-03