人工智能搜索问题

1、人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou1搜索问题搜索问题(对可能的选择进行探索，也是一种推理的过程) R&N: Chap. 3, Sect. 3.12 + 3.6人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou2 描述性的知识创造了多种可能的选择： 那么应该使用哪条的知识呢？ 如何使用呢？ 搜索就是对可能的选择的探索. 是探索知识的一种主要方法Search搜索Knowledgerep.知识表示Planning规划Reasoning推理Learning学习Agent智能体Robotics机器人Perception感知Naturallanguage自然语言

2、.ExpertSystems专家系统Constraintsatisfaction 约束满足 人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou3Example: 8-Puzzle1234567812345678Initial stateGoal state状态：33棋盘上8个数码牌和空位的任意一种布局人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou48-Puzzle: 后继函数后继函数12345678123456781234567812345678搜索是对可能的选择的探索后继函数是有关8数码问题的知识，但它不是告诉我们应该选择哪一个结果，也不是告诉我们应该应用棋局的哪一种

3、状态的知识。人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou5纵观历史，数码问题和博弈（如棋类）需要在众多的可能选项中进行选择，被认为是对人类智能的巨大挑战： 象棋大约4000年前起源于波斯和印度 跳棋大约于3600年出现在埃及 围棋源于3000多年前的中国因此， AI 针对博弈游戏来设计及测试算法并不让人觉得意外人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou6人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou715-Puzzle据说在1878年，自称为“美立坚最伟大数码问题专家”的Sam Loyd，发出悬赏15数码问题人工智能原理2009年春季 广西大学

4、计算机学院 Dr.Ou815-PuzzleSam Loyd 自掏腰包悬赏，第一个解决下面15数码问题的人将得到$1,000的赏金:121411151013956784321121511141013956784321?人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou9But no one ever won the prize !人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou10把问题描述为搜索问题把问题描述为搜索问题State space S （状态空间） Successor function（后继函数） :x S SUCCESSORS(x) 2SInitial sta

5、te s0 （初始状态） Goal test（目标测试）: xS GOAL?(x) =T or F Arc cost（弧的耗散）S132人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou11State Graph 状态图状态图 每一个状态被描述为一个不同的节点 每一段弧（或边）连接节点s和节点s ，若 s SUCCESSORS(s) 状态图可以包含多个连通图人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou12搜索问题的解搜索问题的解Solution to the Search Problem 问题的一个解即为连接初始节点与（任一）目标节点的路径IG人工智能原理2009年春

6、季 广西大学 计算机学院 Dr.Ou13Solution to the Search Problem 问题的一个解即为连接初始节点与（任一）目标节点的路径 一条路径的耗散即为该路径上所有弧的耗散的和 最优解即为有着最小耗散的解路径 可能无解！IG人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou14(n2-1)数码问题的状态空间数码问题的状态空间到底有多大？到底有多大？ 8-puzzle ? states人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou15(n2-1)数码问题的状态空间数码问题的状态空间到底有多大？到底有多大？ 8-puzzle 9! = 362,880

7、states 15-puzzle 16! 2.09 x 1013 states 24-puzzle 25! 1025 states但其中只有一半的状态才是可以到达的（但事先无法知道具体是哪一些状态） 人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou16Wlg, let the goal be:A tile j appears after a tile i if, if either j appears on the same row as i to the right of i, or on another row below the row of i.For all i = 1,

8、 2, ., 15, let ni be the number of tiles j 109 years8-, 15-, 24-Puzzles人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou23 建立一个完全的状态图一般来说是不切可行的（或者代价太高） 问题求解方法必须只探索状态图的一小部分就能够得到问题的解状态空间的搜索状态空间的搜索Searching the State Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou24Search tree状态空间的搜索状态空间的搜索Searching the State Space人工智能原理2009年春季 广西大学

9、 计算机学院 Dr.Ou25Search tree状态空间的搜索状态空间的搜索Searching the State Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou26Search tree状态空间的搜索状态空间的搜索Searching the State Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou27Search tree状态空间的搜索状态空间的搜索Searching the State Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou28Search tree状态空间的搜索状态空间的搜索Searching the S

10、tate Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou29Search tree状态空间的搜索状态空间的搜索Searching the State Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou30简单的问题求解智能体的算法简单的问题求解智能体的算法Problem-Solving-Agent Algorithm1.I sense/read initial stateI 感知/读入初始状态2.GOAL? select/read goal testGOAL? 选择/读入目标测试wSucc select/read successor function

11、Succ 选择/读入后继函数wsolution search(I, GOAL?, Succ) wperform(solution)执行（答案）人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou31状态空间状态空间 每一个状态都是问题世界里所有可能的一个抽象表示，有着相同的关键特性，只描述那些区分彼此不同的细节例如: 在装配规划应用中，一个状态的描述并非是去定义实际装配部件精确的绝对坐标 状态空间是离散的，可能是有限的，也可能是无限的人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou32后继函数后继函数Successor Function 后继函数隐含表示了每一种状态下可行的

12、所有动作人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou33 后继函数隐含的表示了每一种状态下可行的所有动作 后继函数只返回两个内容，动作产生的结果（即后继状态）及该过程的耗散 后继函数是一个“黑匣子”：其中的内容是不知道的例如，在装配规划问题中，其后继函数可能是非常复杂的（碰撞检测，稳定性保证，零部件的夹持，）后继函数后继函数Successor Function人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou34路径耗散路径耗散Path Cost 弧的耗散是执行该段弧所对应动作所付出 “代价”的一个度量，它是一个正数，例如： 8数码问题中每一条弧的耗散为1（意味着移动

13、1步）1 in the 8-puzzle example 装配两个子部件的动作完成的时间 我们假设任意一个给定的问题，其每一条弧的耗散总是在某个范围内变化，满足下式: c 0,其中是一个常数人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou35路径耗散路径耗散Path Cost 弧的耗散是执行该段弧所对应动作所付出 “代价”的一个度量，它是一个正数， 我们假设任意一个给定的问题，其每一条弧的耗散总是在某个范围内变化，满足下式: c 0,其中是一个常数Why is this needed?此处的条件保证了当路径不断增长时，其耗散也随之不断增大人工智能原理2009年春季 广西大学 计算机

14、学院 Dr.Ou36 目标可以是确切的描述: 或是部分描述: 根据条件来定义，例如，每行，每列，对角线之和为30目标测试目标测试Goal State12345678111451363841097122115158aaaaaa(“a” 表示“任意”其他1, 5, 和8之外的数码牌)人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou37其他的一些例子其他的一些例子Other examples人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou388皇后问题皇后问题8-Queens Problem将8个皇后放在国际象棋棋盘中，要求相同的行，列，对角线不能有两个皇后A solutio

15、nNot a solution人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou39问题形式化问题形式化 方法方法1 Formulation #1 状态：状态：所有0, 1, 2, ., 8皇后在棋盘上的布局 初始状态初始状态: 0 个皇后在棋盘上 后继函数后继函数: 每往棋盘上加入一个皇后即得到一个后继 Arc cost: 无关紧要 Goal test: 8个皇后均在棋盘上，且相互之间不会攻击到对方 64x63x.x57 3x1014 states人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou40问题形式化问题形式化 方法方法2 Formulation #2 Stat

16、es: k = 0, 1, 2, ., 8 个皇后放置在棋盘最左侧k列上，且没有两个皇后相互攻击可能的所有布局 Initial state: 0 个皇后在棋盘上 Successor function: 把一个皇后添加在左侧空列，且保证没有两个皇后能够相互攻击，就是一个后继 Arc cost: 无关紧要 Goal test: 8个皇后都在棋盘上 2,057 states人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou41n-Queens Problem 一个就是一个目标节点，而不是一条解的路径（这是一个典型的设计问题） 状态空间的状态个数： 8-queens 2,057 100-qu

17、eens 1052 现在的技术方法已经能高效的解决大数值n皇后问题发现存在许多的解分布在状态空间里人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou42Assembly (Sequence) Planning人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou43Possible FormulationStates: All decompositions of the assembly into subassemblies (subsets of parts in their relative placements in the assembly)Initial state:

18、 All subassemblies are made of a single partGoal state: Un-decomposed assemblySuccessor function: Each successor of a state is obtained by merging two subassemblies (the successor function must check if the merging is feasible: collision, stability, grasping, .)Arc cost: 1 or time to carry the mergi

19、ng人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou44A Portion of State Space人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou45But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou46But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou47But the formulation rules out “non

20、-monotonic” assemblies人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou48But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou49But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou50基本搜索中的假设基本搜索中的假设Assumptions in Basic Search The world is static 静态 The

21、 world is discretizable 离散 The world is observable 可观察 The actions are deterministic 确定性不过上述许多假设可以是不必要的，因此搜索仍然是一种重要的问题求解工具人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou51搜索与搜索与AISearch and AI 搜索方法在AI系统中几乎是无处不在的，常常是系统内核与外部模块的骨架 一个自主机器人使用搜索: 决定该采取的动作和执行哪一个传感操作 快速的预测可能发生的碰撞 轨道的规划 将由大量传感器得到的数字设计翻译为符号的描述 诊断一些预期的事情为何没有发生

22、 . . 许多搜索可能会同时发生并持续进行人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou52应用应用Applications搜索在许多的应用里担任着关键的角色，例如: 路径查找：旅行航线，网络 包裹/邮件的分拣 管道路由，VLSI 路由 蛋白质键的比较与分类 制药业中的药物设计 视频游戏人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou53人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou54Data structures: Searching dataAI: Searching solutions人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou5

23、5Example: robot assembly States? Initial state? Actions? Goal test? Path cost?人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou56Example: robot assemblyStates? Real-valued coordinates of robot joint angles; parts of the object to be assembled.Initial state? Any arm position and object configuration.Actions? Continuous

24、 motion of robot jointsGoal test? Complete assembly (without robot)Path cost? Time to execute人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou57CSP example: map coloring Variables: WA, NT, Q, NSW, V, SA, T Domains: Di=red,green,blue Constraints:adjacent regions must have different colors. E.g. WA NT 人工智能原理2009年春季 广西大学

25、 计算机学院 Dr.Ou58CSP example: map coloring Solutions are assignments satisfying all constraints, e.g. WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou59CSP Example: Cryptharithmetic puzzle人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou60CSP Example: Cryptharithmetic puzzle人工智能原理2009年春季 广西大学 计算机学院 Dr.Ou61A Water Jug Problem You have a 4-gallon and a 3