第7部分逻辑Agent.ppt

第7章 逻辑Agent,中国科大 计算机学院,第部分 知识、推理与规划,本章内容,7.1 基于知识的Agent7.2 Wumpus世界7.3 逻辑7.4 命题逻辑：一种简单逻辑7.5 命题逻辑定理证明7.6 有效的命题逻辑模型检验7.7 基于命题逻辑的Agent,基于知识的Agent,基于知识的智能体的核心构件是其知识库，或称KB（Knowledge Base）。非形式化地表示，知识库是一个语句集合。在此语句作为一个技术术语使用。它与英语及其它自然语言中的语句相关，却不相同。这些语句在被称为知识表示语言的语言中表达，表示了关于世界的某些断言。有些语句是直接给定而不是推导得到的，这些语句称为公理。,基于知识的Agent,必须有将新语句添加到知识库以及查询目前所知内容的方法。这些任务的标准名称分别是TELL（告诉）和ASK（询问）。这两个任务都可能涉及推理：从旧有的语句中推导出新语句。推理必须遵循（follow）基本要求，即当ASK 知识库一个问题时，答案应该遵从事先告诉（或说已知）知识库的内容。可以理解为推理过程不应该虚构事实。后面将精确描述这个至关重要的词“遵循”。,基于知识的智能体,基于知识的智能体用感知信息作为输入，并返回一个行动。智能体维护一个知识库KB。该知识库在初始化时包括了一些背景知识。每次调用智能体程序，它做三件事情：首先，智能体TELL(告诉)知识库它感知的内容。其次，它ASK(询问)知识库应该执行什么行动。在回复该查询的过程中，可能要对关于世界的当前状态、可能行动序列的结果等等进行大量推理。再次，智能体用TELL告诉知识库它所选择的行动，并执行该行动。为了让知识库了解到该假定行动确实已经被执行，第二个TELL 必不可少。,通用的基于知识的Agent,function KB-AGENT(percept)returns an action persistent:KB,a knowledge base t,a counter,initially 0,indicating time TELL(KB,MAKE-PERCEPT-SENTENCE(percept,t)action ASK(KB,MAKE-ACTION-QUERY(t)TELL(KB,MAKE-ACTION-SENTENCE(action,t)t t+I return action表示语言的详细信息隐藏于三个函数中。,基于知识的智能体,通过TELL告诉Agent必须的知识，就可以构建一个基于知识的Agent。刚开始的时候，知识库是空的。Agent设计者通过TELL告知一条条语句，直到Agent知道如何在环境中工作。这种构建系统的方法称为陈述性方法。相反，过程性方法把需要的行为直接编码为程序代码，使得显式的表示和推理的作用最小化。上世纪70-80 年代，这两种方法的争论十分激烈。目前共识：一个成功的智能体在其设计中必须将陈述性和过程性的成分相结合，而且陈述性知识通常被编译成更高效的代码。,基于知识的智能体,除了TELL 智能体它需要知道的内容，我们还可以为基于知识的智能体提供某些机制，使得它可以自我学习。这些机制根据一系列感知信息创建关于环境的常识。这些知识可以并入智能体的知识库而且用于决策。这样，智能体可以完全自治。教材第十八章。所有的这些能力表示、推理和学习依赖于逻辑理论和技术的悠久发展。,本章内容,7.1 基于知识的Agent7.2 Wumpus世界7.3 逻辑7.4 命题逻辑：一种简单逻辑7.5 命题逻辑定理证明7.6 有效的命题逻辑模型检验7.7 基于命题逻辑的Agent,Wumpus世界,Wumpus世界是由多个房间组成，用通道连接起来的洞穴。在洞穴的某处隐藏着一只Wumpus（一种恶兽），它会吃掉进入它房间的任何人。智能体可以射杀Wumpus，但是智能体只有一枝箭。某些房间内有陷阱（无底洞），任何人漫游到这些房间，将被陷阱吞噬（Wumpus 除外，它由于太大而幸免）。生活在该环境下的唯一希望是存在发现一堆金子的可能性。,一个典型的Wumpus世界,注意：智能体位于左下角。,Wumpus世界,性能度量：拾到金子得+1000，掉入陷阱或者被Wumpus吞噬得-1000，每采用一个行动得-1，而用掉箭得-10。环境：4x4的房间网格。Agent每次都从标号为1,1 的方格出发，面向右方。金子和Wumpus的位置按均匀分布随机选择除了起始方格以外的方格。另外，除了起始方格以外的任一方格都可能是陷阱，概率为0.2。,Wumpus世界,执行器：Agent可以向前移动，左转90o或右转90o。如果它进入一个有陷阱或者活着的Wumpus的方格，它将悲惨地死去（进入一个有死Wumpus的方格是安全的，尽管很臭）。如果智能体前方有一堵墙，那么向前移动无效。行动Grab 可以用于捡起智能体所处方格内的一个物体。行动Shoot 可以用于向智能体所正对的方向射出一枝箭。在没有击中Wumpus（如果击中，Wumpus 将被杀死）或者击中墙之前，箭继续向前运动。Agent只有一枝箭，因此只有第一个Shoot 行动有效。行动Climb用于爬出洞口，只能从1,1中爬出。,Wumpus世界,传感器：Agent具有5 个传感器，每个都可以提供一些单一信息。在Wumpus 所在之处以及与之直接相邻（非对角的）的方格内，智能体可以感知到臭气。在与陷阱直接相邻的方格内，智能体感知到微风。在金子所处的方格内，智能体感知到闪闪金光。当智能体撞到墙时，它感知到撞击。当Wumpus 被杀死时，它发出洞穴内的任何地方都可感知到的悲惨嚎叫。以5个符号的列表形式将感知信息提供给智能体。例如，如果有臭气和微风，但是没有金光、撞击或者嚎叫，那么智能体接收到的感知信息为Stench,Breeze,None,None,None。,Wumpus世界,智能体的主要困难在于初始时它对环境配置一无所知：为了克服这一无知，看来需要逻辑推理。在Wumpus 世界的多数情况中，智能体可能可以安全地得到金子。偶尔，智能体必须在空手而归和冒着死亡危险寻找金子二者之间进行选择。大约21%的环境是不公平的，因为金子在陷阱中或者被陷阱包围。,一个典型的Wumpus世界,观察一个基于知识的Wumpus 智能体对下图 所示环境的探索过程。智能体的初始知识库包含了如前所列的环境规则。特别地，知道自己位于1,1，而且1,1是一个安全的方格。,下面将分析智能体的知识在获得新的感知信息并采取行动后如何演化。,Wumpus世界,感知是 None,None,None,None,None。,智能体的知识状态,Wumpus世界,感知是None,Breeze,None,None,None。,智能体的知识状态,Wumpus世界,感知是Stench,None,None,None,None。,智能体的知识状态,Wumpus世界,移动到2,3后，感知是为Stench,Breeze,Glitter,None,None。此时的知识状态是什么？,本章内容,7.1 基于知识的Agent7.2 Wumpus世界7.3 逻辑7.4 命题逻辑：一种简单逻辑7.5 命题逻辑定理证明7.6 有效的命题逻辑模型检验7.7 基于命题逻辑的Agent,逻辑,知识库是由语句构成的。根据表示语言的语法来表达这些语句，表示语言要对所有这些具有完整结构的语句进行具体说明。普通算术中的语法概念很明确：x+y=4 是一个结构完整的语句，而x2y+=则不是。逻辑语言的语法（以及算术语法，需要考虑的话）通常是为写文章和书而设计的。文献中存在许多不同的语法，有些采用很多希腊字母和奇特的数学符号，而有些采用具有很强视觉冲击效果，包含了箭头和气泡的图案。所有这些情况中，智能体知识库的语句都是智能体的（部分的）真实的实际结构。推理将涉及生成和操作这些结构。,逻辑,逻辑还必须走义语言的语义。不严格地说，语义必须和语句的含义有关。逻辑上，这个定义更为精确。语言的语义定义了每个语句关于每个可能世界的真值。例如，算术采用的通常语义表明语句x+y=4 在x 等于2，Y 也等于2 的世界中为真，而在x 等于1，y 等于1 的世界中为假1。标准逻辑学中，每个语句在每个可能的世界中必须非真即假不存在中间状态。,逻辑,当需要精确描述时，用术语模型取代“可能世界”，还用短语“m 是 的一个模型”表示语句 在模型m 中为真。不过，可能的世界可以被认为是智能体可能在也可能不在其中的（潜在的）真实环境。模型是数学抽象，每个模型只是简单地关注于每个相关语句的真或假。非形式化地，例如，我们可以把x 和y 视为坐在桌子旁玩桥牌的男士和女士的数量，当总共有四个人的时候，语句x+y=4为真。形式化地，可能的模型就是对变量x 和y 所有可能的赋值。每个这样的赋值决定了任何变量为x 租y 的算术语句的真值。,蕴涵,有了真值概念，就准备好讨论逻辑推理了。这涉及语句间的逻辑蕴涵（entailment）关系即一个语句逻辑上跟随另一个语句而出现。用数学符号表示为:I=意思是语句 蕴涵语句。蕴涵的形式化定义是:I=，当且仪当在 为真的每个模型中，也为真。另一种表述方法是，如果 为真，那么P 也必定为真。非形式地说，的真值包含于 的真值中。,蕴涵,蕴涌关系与算术类似：例如，语句x+y=4 蕴涵了语句4=x+y。显然，任何x+y=4 的模型比如x 等于2，Y 等于2 的模型也是4=x+y 的模型。可以认为知识库是语句，而且后面将经常谈论到知识库蕴涵某个语句。,Wumpus世界推理实例,考虑下图的情况：智能体检测出1,1什么也没有，而2,1有微风。这些感知信息，与wumpus 世界的智能体知识规则相结合，组成知识库。,Wumpus世界推理实例,智能体感兴趣的是一件事情是：相邻的方格1,2、2,2和3,1是否包含陷阱。3 个方格中每一个都可能包含或者不包含陷阱，因此存在23=8个可能的模型。,Wumpus世界推理实例,在与智能体所知道的内容相矛盾的模型中，KB 为假。例如，在任意1,2包含陷阱的模型中，KB 为假，因为1，1不存在微风。实际上只存在3 个使得KB 为真的模型，它们可被视为上图所示的模型的子集。下面分析两个可能的结论:1=“1,2 中无陷阱。”2=“2,2 中无陷阱。”,Wumpus世界推理实例,通过检验，可以得到以下结果:在KB 为真的每个模型中，1也为真。因而，KBI=1：“1,2 中无陷阱”。在KB 为真的某些模型中，2为假。因而，KBI2。智能体无法得出2,2无陷阱的结论（也无法得出2,2有陷阱的结论）。,Wumpus世界推理实例,这一示例不仅阐述了蕴含，而且说明了蕴含的定义如何用于推导出结论，即，实现逻辑推理。这样的推理算法称为模型检验，因为它枚举出所有可能的模型，用于检验在KB为真的所有模型中为真。,蕴含和推理,蕴含和推理：将KB的所有推论集合视为一个大干草堆，而把视为一根针。蕴含就像是干草堆里的一根针，推理就是寻找它的过程。如果推理算法i可以根据KB导出，则表示为KBI-i读为：通过i从KB导出，或i从KB导出。,蕴含和推理,只导出蕴含句的推理算法被称为可靠的或真值保持的推理。可靠性是一个非常必要的属性。本质上，不可靠的推理过程可能会虚构事实。模型检验在可行的情况下（模型空间是有限的）是一个可靠的过程。完备性属性也是非常必要的。推理算法是完备的，如果它可以生成任一蕴含句。真正的干草堆在一定程度上是个有限空间。显然，系统化的检查总可以判断出针是否在干草堆中。然后，对于多数知识库，干草堆的推论是无限的，完备性成为一个重要问。幸运的是，存在可用于逻辑学的完备的推理过程。,蕴含和推理,前面描述的推理过程，在前提为真的任何世界中，它的结论保证为真。特别地，如果KB在现实世界中为真，那么通过可靠推理过程从KB导出的任意语句在现实世界中也都为真。因此，当推理过程对“语法”内在的实际结果，注入寄存器的比特或大脑中的电子点模式进行操作时，该过程符合现实世界的关系，该关系表明现实世界的某些方面为真要依赖于现实世界的其它方面为真。,世界和表示之间的对应关系,语句是智能体的实际结构，推理是从旧的结构中构建新的实际结构的过程。逻辑推理应该确保新结构所代表的那部分世界的确是旧结构所代表的那部分的必然结论。,筑基,筑基：逻辑推理过程和智能体生存的真实环境之间的联系，如果存在的话。特别是，我们如何知道KB在现实世界中为真。毕竟，KB只是存在于智能体头脑中的“语法”。这是个哲学问题。一个简单回答是，智能体的传感器创建了这一联系。例如，Wumpus世界的智能体有一个嗅觉传感器。只要有气味，智能体程序就创建一个适合的语句来表示它。那么，只要该语句存在于知识库中，它在现实世界中就为真。,筑基,因此，感知语句的含义和真值是通过产生它们的感知和语句构造的过程来定义的。其余的智能体知识，诸如它对在相邻方格中的Wumpus 散发出气味的信念是怎么回事呢？这不是某个单一感知信息的直接表示问题，而是一条一般规则可能根据感知经验得到，但不等同于该经验的一个陈述。这类一般规则由被称为学习的语句构造过程产生。学习是教材第五部分的主题。学习容易出现错误。可能存在这样的情况，Wumpus 会发出臭味，但是除了闰年的2月29日那天Wumpus 去洗澡以外。因而，KB在现实世界中可能不为真，但是由于有很好的学习过程，存在乐观理由。,本章内容,7.1 基于知识的Agent7.2 Wumpus世界7.3 逻辑7.4 命题逻辑：一种简单逻辑7.5 命题逻辑定理证明7.6 有效的命题逻辑模型检验7.7 基于命题逻辑的Agent,命题逻辑,语法语义一个简单的知识库推理,语法,命题逻辑的语法定义允许出现的语句。包括原子语句和复合语句。原子语句不可分割的句法元素构成一个命题符号。每个这样的符号代表一个或为真或为假的命题。通常采用大写名称表示命题符号：P,Q,R，等等。名称可以采用任意字符，但是通常采用有助于读者记忆的名称。,语法,例如，我们可以用W1,3表示“Wumpus位于1,3”这一命题。注意，诸如W1,3这样的符号是一个原子。也就是说，W、1 和3 不是该符号有意义的部分。有两个具有固定意义的命题符号：True 是永真命题，False 为永假命题。,语法,复合句由更简单的语句用逻辑连接符构造而成。以下是常用的5 种连接符。：否定（非）：合取（与）：析取（或）：蕴涵（IFTHEN）：等价（当且仅当）,语法,：否定（非）例如，W1,3，称作W1,3的否定式：合取（与）例如，W1,3P3,1，称作合取式，它的各个部分称作合取子句。：析取（或）例如，(W1,3P3,1)W2,2是析取子句W1,3P3,1和W2,2的析取式。,语法,：蕴涵（IFTHEN）形式如(W1,3P3,1)W2,2的语句称为蕴含式（或条件式），它的前提或前项是W1,3P3,1，结论或后项是W2,2。蕴涵式也称为规则，或如果-那么语句(ifthen)。：等价（当且仅当）语句是W1,3 W2,2双向蕴含式。文字：要么是原子语句（正文字），要么是否定的原子语句（负文字）。,命题逻辑的形式语法,优先级（从高到低）：，。,命题逻辑,语法语义一个简单的知识库推理,语义,语义定义了用于判定关于特定模型的语句真值的规则。在命题逻辑中，模型简单地固定了每个命题符号的真值是true 还是false。例如，知识库中的语句采用命题符号P12、P22和P31，那么一个可能的模型为:m1=P12=false,P22=false,P31=true由于有3 个符号，因此有23=8个可能的模型。注意，因为己经对语法进行了约束，模型成为纯粹的数学对象，不必和wumpus 世界有关系。P12只是一个符号，它可以表示“1,2存在一个陷阱“，也可表示我今天和明天在巴黎。,语义,命题逻辑的语义必须给出在己知一个模型的情况下如何计算任一语句的真值。所有的语句都由原子语句和5 种连接符构成。如何计算原子语句的真值？如何计算由5 种连接符中的每一个形成的语句的真值？,语义,计算原子语句的真值：每个模型中True 代表真，False 代表假。其它的每个命题符号的真值必须在模型中直接指定。如，在早先给出的模型m1中，P12为假。计算复合句的真值：按如下真值表计算。,知识库与语句,知识库由语句集构成。逻辑知识库是知识库中语句的合取式。也就是说，如果从一个空的KB 开始，进行TELL(KB,S1),TELL(KB,Sn)，那么得到KB=S1.Sn,异或连接词,存在一个被称为“异或”(简称“xor”）的不同连接符。当两个析取子式皆为真时，其值为假。关于异或符号的使用没有统一标准，存在两个可选符号，和。本章不考虑。,蕴含式,蕴含的真值表可能让人感到很困惑，因为它可能不很符合人们对于“P蕴涵Q 或如果P，那么Q 的直觉理解。一方面，命题逻辑不要求P 和Q 之间存在任何相关性或因果关系。语句“5是奇数，蕴涵东京是日本的首都”是命题逻辑的真语句（常规解释下），即使它确实无疑是古怪的句子。另一方面，前提为假的任意蕴涵都为真。例如，“5 是偶数蕴涵Sam很聪明”为真，而跟Sam是否聪明无关。这看起来很怪异，但是如果把“PQ”看作“如果P为真，则我主张Q 为真，否则我不做任何声明”这样就有意义了。使得该语句为假的唯一条件是，如果P 为真而Q 为假。,双向蕴涵式,双向蕴涵式P Q：“P当且仅当Q 或“P iff Q。Wumpus 世界的规则最好用表示。例如，如果一个方格的某个相邻方格中有陷阱，则该方格有微风，而且当且仅当一个方格的某个相邻方格中有陷阱，该方格才有微风。因而需要如下的双向蕴涵:B11 P12 V P21注意，单向蕴涵B11P12 V P21在Wumpus 世界中为真，但不完备。,命题逻辑,语法语义一个简单的知识库推理,一个简单的知识库,知识库举例：为Wumpus 世界构造一个知识库。此处仅考虑一成不变的部分。对于每个位置x,y，需要如下命题词：如果x,y 中有陷阱，则Pxy 为真:如果x,y中有怪兽，则Wxy为真，不管是死是活。如果在x,y中感知到微风，则Bxy为真。如果在x,y中感知到臭气，则Sxy为真。如果在x,y中感知到闪闪金光，则Gxy为真。,一个简单的知识库,为了便于推导，用Ri对每个语句进行标注。1,1中没有无底洞（陷阱）：R1:P11一个方格里有微风，当且仅当在某个相邻方格中有无底洞（陷阱）。对于每个方格，都必须说明这种情况。目前，只考虑相关方格：R2:B11(P12 V P21)R3:B21(P11 V P22 V P31),一个简单的知识库,在所有的wumpus 世界中，前面的这些语句都为真。下面将智能体所处的特定世界中最初访问的两个方格的微风感知信息包括进来，导致如下图所示中的情景。R4:B11 R5:B21,于是，知识库有R1到R5这些语句组成。它也可以当做单一语句，即合取式R1R2R3R4R5因为它断言所有的单独语句都为真。,命题逻辑,语法语义一个简单的知识库推理,推理,推理的目标：判断对于某些语句，KBI=是否成立。第一个推理算法是对蕴涵的定义的直接实现：枚举出所有模型，验证 在KB为真的每个模型中为真。对于命题逻辑，模型对每个命题词赋值为true 或false。在Wumpus世界的示例，相关的命题词为B11、B21、P11、P12、P21、P22和P31。这7 个符号一共有128 种可能的模型：在其中的3 个模型中，KB 为真。,推理,真值表,推理,在这3 个模型中，P12 都为真，因此1,2 中没有陷阱。对于这3 个模型，两个模型中的P22 为真，而在另一个模型中的P22为假，所以还是无法判断2,2 中是否有陷阱。,判断命题逻辑的蕴涵的真值表枚举算法,function TT-ENTAILS?(KB,)returns true or false inputs:KB,the knowledge base,a sentence in propositional logic,the query,a sentence in propositional logic symbols a list of the propositional symbols in KB and return TT-CHECK-ALL(KB,symbols,)function TT-CHECK-ALL(KB,symbols,model)returns true or false if EMPTY?(symbols)then if PL-TRUE?(KB,model)then return PL-TRUE?(,model)else return true/when KB is false,always return true else do P-FIRST(symbols);rest-REST(symbols)return TT-CHECK-ALL(KB,rest,modelP=true)and TT-CHECK-ALL(KB,rest,modelP=false),判断命题逻辑的蕴涵的真值表枚举算法,该算法是可靠的，因为它直接实现了蕴涵的定义。该算法是完备的，因为它可以用于任意KB和。该算法总能够终止，因为只存在有限多个需要检验的模型。如果KB和总共包含n个符号，那么存在2n个模型，则该算法的时间复杂度为O(2n)。本章的后面将介绍更有效的算法。但不幸的是，命题蕴含是余NP完全（可能不会比NP完全容易）的。所以，每个已知的命题逻辑推理算法在最坏情况下的复杂度都是问题规模的指数级。,