高级人工智能-搜索

1、搜索中国科学院自动化研究所吴高巍2016-9-13内容搜索问题无信息搜索 Uninformed Search启发式搜索 Informed Search局部搜索 Local Search搜索问题搜索问题搜索问题 构成:状态空间 A state space后继函数 A successor function(with actions, costs)初始状态和目标测试 A start state and a goal test解 是一个行动序列，将初始状态转换成目标状态 “N”, 1.0“E”, 1.0搜索问题是对原问题的建模例子: 罗马尼亚旅行 状态空间: Cities 后继函数: Roads: G

2、o to adjacent city with cost = distance 初始状态: Arad 目标测试: Is state = Bucharest? 解?状态空间包含什么? Problem: Pathing States: (x,y) location Actions: NSEW Successor: update location only Goal test: is (x,y)=END Problem: Eat-All-Dots States: (x,y), dot booleans Actions: NSEW Successor: update location and poss

3、ibly a dot boolean Goal test: dots all false状态空间 包含了环境中的每一个细节搜索状态 只保留行动需要的细节状态空间中状态数量? 世界状态: Agent positions: 120 Food count: 30 Ghost positions: 12 Agent facing: NSEW 数量 世界状态?120 x(230)x(122)x4 路线规划状态?120 “吃光豆子”状态?120 x(230)Quiz: 安全通行 Problem: eat all dots while keeping the ghosts perma-scared What

4、 does the state space have to specify? (agent position, dot booleans, power pellet booleans, remaining scared time)状态空间图 State Space Graphs搜索树 Search Trees状态空间图 状态空间图: 搜索问题的数学表示 Nodes are (abstracted) world configurations Arcs represent successors (action results) The goal test is a set of goal node

5、s (maybe only one) 状态空间图中，每个状态只出现一次！ 几乎不在内存中构建完整的状态空间图（太大了），但它是非常有用的状态空间图SGdbpqcehafrTiny search graph for a tiny search problem 状态空间图: 搜索问题的数学表示 Nodes are (abstracted) world configurations Arcs represent successors (action results) The goal test is a set of goal nodes (maybe only one) 状态空间图中，每个状态只出

6、现一次！ 几乎不在内存中构建完整的状态空间图（太大了），但它是非常有用的搜索树 搜索树: 根节点对应了初始状态 子节点对应了父节点的后继 节点显示状态，但对应的是到达这些状态的行动行动 对大多数问题，实际上不会构建整个树“E”, 1.0“N”, 1.0This is now / startPossible futures状态空间图 vs. 搜索树SabdpacephfrqqcGaqephfrqqcGaSGdbpqcehafrWe construct both on demand and we construct as little as possible.Each NODE in the se

7、arch tree is an entire PATH in the state space graph.Search TreeState Space GraphQuiz: 状态空间图 vs. 搜索树SGbaConsider this 4-state graph: Important: Lots of repeated structure in the search tree!How big is its search tree (from S)?树搜索例子: 罗马尼亚旅行基于搜索树的搜索 搜索: 扩展出潜在的行动 (tree nodes) 维护所考虑行动的边缘(fringe)节点 试图扩展尽

8、可能少的树节点一般的树搜索 Important ideas: Fringe Expansion Exploration strategy Main question: which fringe nodes to explore?搜索算法特性搜索算法特性 完备性: 当问题有解时，保证能找到一个解? 最优性: 保证能找到最优解（最小耗散路径）? 时间复杂度? 空间复杂度? 例子: b 分支因子 m 最大深度 d 最浅目标节点的深度 整个树的节点数目? 1 + b + b2 + . bm = O(bm)b1 nodeb nodesb2 nodesbm nodesm tiers例子: 树搜索SGdbp

9、qcehafr深度优先搜索(Depth-First Search)深度优先搜索SabdpacephfrqqcGaqephfrqqcGaSGdbpqcehafrqphfdbacerStrategy: expand a deepest node firstImplementation: Fringe is a LIFO stack深度优先搜索 (DFS) 特性b1 nodeb nodesb2 nodesbm nodesm tiers DFS扩展哪些节点? Some left prefix of the tree. Could process the whole tree! If m is fini

10、te, takes time O(bm) 内存需求? Only has siblings on path to root, so O(bm) 完备性? m could be infinite, so only if we prevent cycles (more later) 最优性? No, it finds the “leftmost” solution, regardless of depth or cost广度优先搜索(Breadth-First Search)广度优先搜索SabdpacephfrqqcGaqephfrqqcGaSGdbpqcehafrSearchTiersStrate

11、gy: expand a shallowest node firstImplementation: Fringe is a FIFO queue广度优先搜索(BFS) 特性 BFS扩展哪些节点? Processes all nodes above shallowest solution Let depth of shallowest solution be s Search takes time O(bs) 内存需求? Has roughly the last tier, so O(bs) 完备性? s must be finite if a solution exists, so yes!

12、最优性? Only if costs are all 1 (more on costs later)b1 nodeb nodesb2 nodesbm nodess tiersbs nodesQuiz: DFS vs BFSQuiz: DFS vs BFS 什么情况下BFS优于DFS? 什么情况下DFS优于BFS?迭代深入搜索(Iterative Deepening)b Idea: 结合DFS的空间优势与BFS的时间优势 Run a DFS with depth limit 1. If no solution Run a DFS with depth limit 2. If no solutio

13、n Run a DFS with depth limit 3. . 浪费冗余? 通常绝大多数的节点都在底层，所以上层的节点生成多次影响不是很大。代价敏感搜索(Cost-Sensitive Search)BFS finds the shortest path in terms of number of actions.It does not find the least-cost path. We will now covera similar algorithm which does find the least-cost path. STARTGOALdbpqcehafr2928182324

14、4151322代价一致搜索(Uniform Cost Search)代价一致搜索SabdpacephfrqqcGaqephfrqqcGaStrategy: expand a cheapest node first:Fringe is a priority queue (priority: cumulative cost)SGdbpqcehafr39116411571381011171106391128821512Cost contours2代价一致搜索 (UCS) 特性 UCS扩展哪些节点? Processes all nodes with cost less than cheapest so

15、lution! If that solution costs C* and arcs cost at least , then the “effective depth” is roughly C*/ Takes time O(bC*/) (exponential in effective depth) 内存需求? Has roughly the last tier, so O(bC*/) 完备性? Assuming best solution has a finite cost and minimum arc cost is positive, yes! 最优性? Yes! bC*/ “ti

16、ers”c 3c 2c 1代价一致搜索 UCS 探索了递增的轮廓线 优点: 完备性、最优性! 缺点: 在每一个“方向”上进行探索 没有关于目标信息StartGoalc 3c 2c 1搜索算法 所有的搜索算法都是相同的，除了对边缘的处理策略 从概念上说，所有的边缘是优先队列 (即附加优先级的节点集合) 对于DFS, BFS，可以通过使用栈或队列代替优先队列，从而减少log(n) 的开支搜索算法38搜索和模型 搜索是在问题世界的模型上操作 实际上并不在真实世界上试验所有的规划 规划全部是在“模拟中” 你的搜索只能和你的模型一样好启发式搜索(Informed Search)搜索的启发策略 启发策略:

17、估计估计一个状态到目标距离的函数问题给予算法的额外信息，为特定搜索问题而设计例: Manhattan distance, Euclidean distance for pathing10511.2例子: 启发函数h(x)贪婪搜索(Greedy Search)例子: 罗马尼亚旅行h(x)贪婪搜索 扩展离目标最近的节点贪婪搜索 策略: 扩展你认为最接近目标状态的节点 启发式: 对每个状态估计到最近目标的距离 只使用启发函数 f(n)=h(n) 来评价节点 通常情况: 最佳优先使你直接（或很快）到达目标 最坏情况: 类似DFSbbA* 搜索A* 搜索UCSGreedyA*结合 UCS 和 Greed

18、y Uniform-cost orders by path cost, or backward cost g(n) Greedy orders by goal proximity, or forward cost h(n) A* Search orders by the sum: f(n) = g(n) + h(n)SadbGh=5h=6h=218112h=6h=0ch=73eh=11SabceddGGg = 0 h=6g = 1 h=5g = 2 h=6g = 3 h=7g = 4 h=2g = 6 h=0g = 9 h=1g = 10 h=2g = 12 h=0A* 结束条件? 当目标入列

19、时，应该停止吗? 不: 只有目标出列时才停止！SBAG2322h = 1h = 2h = 0h = 3A* 最优性? 哪错了? 实际(差)目标耗散 (好)目标耗散的估计 需要估计要小于实际耗散!AGS13h = 6h = 05h = 7可采纳启发可采纳启发 启发函数 h 是 可采纳的，那么:其中 是到最近目标的真实耗散 例: 想出可采纳的启发函数是A*算法实际使用中的重点15A* 树搜索的最优性A* 树搜索的最优性假定: A 最优目标节点 B 次优目标节点 h 可采纳的结论: A在B之前离开边缘集合A* 树搜索的最优性证明: 假设 B 在边缘集合上 A的某个祖先节点n也在边缘集合上 (mayb

20、e A!) 那么 n 将在B之前被扩展1. f(n) = f(A)Definition of f-costAdmissibility of hh = 0 at a goalA* 树搜索的最优性证明: 假设 B 在边缘集合上 A的某个祖先节点n也在边缘集合上 (maybe A!) 那么 n 将在B之前被扩展1. f(n) = f(A)2. f(A) f(B)B is suboptimalh = 0 at a goalA* 树搜索的最优性证明: 假设 B 在边缘集合上 A的某个祖先节点n也在边缘集合上 (maybe A!) 那么 n 将在B之前被扩展1. f(n) is less or equal

21、 to f(A)2. f(A) is less than f(B)3. n expands before B A的所有祖先在B之前扩展 A在B之前扩展 A*是最优的A*算法特性bbUniform-CostA*UCS vs A* 代价一致搜索在所有“方向”上等可能的扩展 A*搜索主要朝着目标扩展，而且 能够保证最优性StartGoalStartGoal比较GreedyUniform CostA*A* 算法应用 Video games Pathing / routing problems Resource planning problems Robot motion planning Langua

22、ge analysis Machine translation Speech recognition 设定启发函数设定可采纳的启发函数 对于解决难的搜索问题，大部分工作就是想出可采纳的启发函数 通常，可采纳启发函数是松弛问题松弛问题的解的耗散15366例子: 八数码游戏 状态空间? 状态数量? 有哪些行动? 从初始状态有多少后继? 耗散?Start StateGoal StateActions 松弛问题棋子可以从方格A移到B棋子可以从方格A移到B，如果A和B相邻八数码游戏 I Heuristic: 不在位棋子数 可采纳? h(start) = 由松弛问题得到的启发函数8Average node

23、s expanded when the optimal path has4 steps 8 steps 12 stepsUCS1126,3003.6 x 106TILES1339227Start StateGoal StateStatistics from Andrew Moore八数码游戏 II 更简单的八数码游戏任何棋子可以在任何时间滑动，而不用考虑其他棋子 曼哈顿(Manhattan)距离 可采纳? h(start) = 3 + 1 + 2 + = 18Average nodes expanded when the optimal path has4 steps8 steps12 ste

24、psTILES1339227MANHATTAN122573Start StateGoal State八数码游戏 III 采用实际耗散作为启发函数? 可采纳? 节点扩展? 存在问题? A*算法: 估计质量与每个节点计算量间的折衷 启发函数越接近真实的耗散，将扩展越少的节点，但通常会在每个节点计算启发函数本身时有更多的计算启发函数 占优势: ha hc if 可采纳的启发函数集合: Trivial heuristics 底层是零启发式(what does this give us?) 顶层是精确的启发式图搜索避免重复的状态 如果算法不检测重复状态，线性问题变成了指数问题Search TreeSta

25、te Graph71图搜索 例如，BFS中，不应该为圈起来的节点而操心 (why?)SabdpacephfrqqcGaqephfrqqcGa图搜索 主要思想: 不要扩展一个状态两次 执行: 树搜索 + 扩展过的状态集 (“closed set”)按节点扩展搜索树，但扩展节点之前，检查确保它的状态在之前没有被扩展如果不是新的状态，忽略；如果是新的，加入closed表 重点: store the closed set as a set, not a list 图搜索会破坏完备性吗? Why/why not? 最优性?A* 图搜索?SABCG11123h=2h=1h=4h=1h=0S (0+2)A

26、(1+4)B (1+1)C (2+1)G (5+0)C (3+1)G (6+0)State space graphSearch tree启发式的一致性 主要思想: estimated heuristic costs actual costs 可采纳性: heuristic cost actual cost to goalh(A) actual cost from A to G 一致性: heuristic “arc” cost actual cost for each arch(A) h(C) cost(A to C) 一致性: 沿路径的节点估计耗散 f 值单调递增 h(A) cost(A to C) + h(C) A* 图搜索具备最优性3ACGh=4h=11h=2A*图搜索的最优性A*图搜索的最优性A*算法采用一致的启发函数 :Fact 1: A*算法扩展节点，f值单调增 (f-contours)Fact 2: 对每个状态s, 到达s 最优的节点先于次优的节点扩展Result: A*图搜索是最优的f 3f 2f 1A*图搜索的最优性证明:假定 到G*的路径上某个n不能进入队列中，因为某个具有相同状态且较差的n 先被扩展了 (disaster!)找到树中最高的这样的节点 n 设p 是n 的祖先，且在 n