人工智能-搜索問題

1、人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou1搜索問題搜索問題(對可能的選擇進(jìn)行探索，也是一種推理的過程) R&N: Chap. 3, Sect. 3.12 + 3.6人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou2 描述性的知識(shí)創(chuàng)造了多種可能的選擇： 那么應(yīng)該使用哪條的知識(shí)呢？ 如何使用呢？ 搜索就是對可能的選擇的探索. 是探索知識(shí)的一種主要方法Search搜索Knowledgerep.知識(shí)表示Planning規(guī)劃Reasoning推理Learning學(xué)習(xí)Agent智能體Robotics機(jī)器人Perception感知Naturallanguage自然語言

2、.ExpertSystems專家系統(tǒng)Constraintsatisfaction 約束滿足 人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou3Example: 8-Puzzle1234567812345678Initial stateGoal state狀態(tài)：33棋盤上8個(gè)數(shù)碼牌和空位的任意一種布局人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou48-Puzzle: 后繼函數(shù)后繼函數(shù)12345678123456781234567812345678搜索是對可能的選擇的探索后繼函數(shù)是有關(guān)8數(shù)碼問題的知識(shí)，但它不是告訴我們應(yīng)該選擇哪一個(gè)結(jié)果，也不是告訴我們應(yīng)該應(yīng)用棋局的哪一種

3、狀態(tài)的知識(shí)。人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou5縱觀歷史，數(shù)碼問題和博弈（如棋類）需要在眾多的可能選項(xiàng)中進(jìn)行選擇，被認(rèn)為是對人類智能的巨大挑戰(zhàn)： 象棋大約4000年前起源于波斯和印度 跳棋大約于3600年出現(xiàn)在埃及 圍棋源于3000多年前的中國因此， AI 針對博弈游戲來設(shè)計(jì)及測試算法并不讓人覺得意外人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou6人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou715-Puzzle據(jù)說在1878年，自稱為“美立堅(jiān)最偉大數(shù)碼問題專家”的Sam Loyd，發(fā)出懸賞15數(shù)碼問題人工智能原理2009年春季 廣西大學(xué)

4、計(jì)算機(jī)學(xué)院 Dr.Ou815-PuzzleSam Loyd 自掏腰包懸賞，第一個(gè)解決下面15數(shù)碼問題的人將得到$1,000的賞金:121411151013956784321121511141013956784321?人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou9But no one ever won the prize !人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou10把問題描述為搜索問題把問題描述為搜索問題State space S （狀態(tài)空間） Successor function（后繼函數(shù)） :x S SUCCESSORS(x) 2SInitial sta

5、te s0 （初始狀態(tài)） Goal test（目標(biāo)測試）: xS GOAL?(x) =T or F Arc cost（弧的耗散）S132人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou11State Graph 狀態(tài)圖狀態(tài)圖 每一個(gè)狀態(tài)被描述為一個(gè)不同的節(jié)點(diǎn) 每一段弧（或邊）連接節(jié)點(diǎn)s和節(jié)點(diǎn)s ，若 s SUCCESSORS(s) 狀態(tài)圖可以包含多個(gè)連通圖人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou12搜索問題的解搜索問題的解Solution to the Search Problem 問題的一個(gè)解即為連接初始節(jié)點(diǎn)與（任一）目標(biāo)節(jié)點(diǎn)的路徑IG人工智能原理2009年春

6、季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou13Solution to the Search Problem 問題的一個(gè)解即為連接初始節(jié)點(diǎn)與（任一）目標(biāo)節(jié)點(diǎn)的路徑 一條路徑的耗散即為該路徑上所有弧的耗散的和 最優(yōu)解即為有著最小耗散的解路徑 可能無解！IG人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou14(n2-1)數(shù)碼問題的狀態(tài)空間數(shù)碼問題的狀態(tài)空間到底有多大？到底有多大？ 8-puzzle ? states人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou15(n2-1)數(shù)碼問題的狀態(tài)空間數(shù)碼問題的狀態(tài)空間到底有多大？到底有多大？ 8-puzzle 9! = 362,880

7、states 15-puzzle 16! 2.09 x 1013 states 24-puzzle 25! 1025 states但其中只有一半的狀態(tài)才是可以到達(dá)的（但事先無法知道具體是哪一些狀態(tài)） 人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 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年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou23 建立一個(gè)完全的狀態(tài)圖一般來說是不切可行的（或者代價(jià)太高） 問題求解方法必須只探索狀態(tài)圖的一小部分就能夠得到問題的解狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the State Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou24Search tree狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the State Space人工智能原理2009年春季 廣西大學(xué)

9、 計(jì)算機(jī)學(xué)院 Dr.Ou25Search tree狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the State Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou26Search tree狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the State Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou27Search tree狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the State Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou28Search tree狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the S

10、tate Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou29Search tree狀態(tài)空間的搜索狀態(tài)空間的搜索Searching the State Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou30簡單的問題求解智能體的算法簡單的問題求解智能體的算法Problem-Solving-Agent Algorithm1.I sense/read initial stateI 感知/讀入初始狀態(tài)2.GOAL? select/read goal testGOAL? 選擇/讀入目標(biāo)測試3.Succ select/read successor functio

11、nSucc 選擇/讀入后繼函數(shù)4.solution search(I, GOAL?, Succ) 5.perform(solution)執(zhí)行（答案）人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou31狀態(tài)空間狀態(tài)空間 每一個(gè)狀態(tài)都是問題世界里所有可能的一個(gè)抽象表示，有著相同的關(guān)鍵特性，只描述那些區(qū)分彼此不同的細(xì)節(jié)例如: 在裝配規(guī)劃應(yīng)用中，一個(gè)狀態(tài)的描述并非是去定義實(shí)際裝配部件精確的絕對坐標(biāo) 狀態(tài)空間是離散的，可能是有限的，也可能是無限的人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou32后繼函數(shù)后繼函數(shù)Successor Function 后繼函數(shù)隱含表示了每一種狀態(tài)下

12、可行的所有動(dòng)作人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou33 后繼函數(shù)隱含的表示了每一種狀態(tài)下可行的所有動(dòng)作 后繼函數(shù)只返回兩個(gè)內(nèi)容，動(dòng)作產(chǎn)生的結(jié)果（即后繼狀態(tài)）及該過程的耗散 后繼函數(shù)是一個(gè)“黑匣子”：其中的內(nèi)容是不知道的例如，在裝配規(guī)劃問題中，其后繼函數(shù)可能是非常復(fù)雜的（碰撞檢測，穩(wěn)定性保證，零部件的夾持，）后繼函數(shù)后繼函數(shù)Successor Function人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou34路徑耗散路徑耗散Path Cost 弧的耗散是執(zhí)行該段弧所對應(yīng)動(dòng)作所付出 “代價(jià)”的一個(gè)度量，它是一個(gè)正數(shù)，例如： 8數(shù)碼問題中每一條弧的耗散為1（意味

13、著移動(dòng)1步）1 in the 8-puzzle example 裝配兩個(gè)子部件的動(dòng)作完成的時(shí)間 我們假設(shè)任意一個(gè)給定的問題，其每一條弧的耗散總是在某個(gè)范圍內(nèi)變化，滿足下式: c 0,其中是一個(gè)常數(shù)人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou35路徑耗散路徑耗散Path Cost 弧的耗散是執(zhí)行該段弧所對應(yīng)動(dòng)作所付出 “代價(jià)”的一個(gè)度量，它是一個(gè)正數(shù)， 我們假設(shè)任意一個(gè)給定的問題，其每一條弧的耗散總是在某個(gè)范圍內(nèi)變化，滿足下式: c 0,其中是一個(gè)常數(shù)Why is this needed?此處的條件保證了當(dāng)路徑不斷增長時(shí)，其耗散也隨之不斷增大人工智能原理2009年春季 廣西大學(xué)

14、計(jì)算機(jī)學(xué)院 Dr.Ou36 目標(biāo)可以是確切的描述: 或是部分描述: 根據(jù)條件來定義，例如，每行，每列，對角線之和為30目標(biāo)測試目標(biāo)測試Goal State12345678111451363841097122115158aaaaaa(“a” 表示“任意”其他1, 5, 和8之外的數(shù)碼牌)人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou37其他的一些例子其他的一些例子Other examples人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou388皇后問題皇后問題8-Queens Problem將8個(gè)皇后放在國際象棋棋盤中，要求相同的行，列，對角線不能有兩個(gè)皇后A solu

15、tionNot a solution人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou39問題形式化問題形式化 方法方法1 Formulation #1 狀態(tài)：狀態(tài)：所有0, 1, 2, ., 8皇后在棋盤上的布局 初始狀態(tài)初始狀態(tài): 0 個(gè)皇后在棋盤上 后繼函數(shù)后繼函數(shù): 每往棋盤上加入一個(gè)皇后即得到一個(gè)后繼 Arc cost: 無關(guān)緊要 Goal test: 8個(gè)皇后均在棋盤上，且相互之間不會(huì)攻擊到對方 64x63x.x57 3x1014 states人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou40問題形式化問題形式化 方法方法2 Formulation #2 S

16、tates: k = 0, 1, 2, ., 8 個(gè)皇后放置在棋盤最左側(cè)k列上，且沒有兩個(gè)皇后相互攻擊可能的所有布局 Initial state: 0 個(gè)皇后在棋盤上 Successor function: 把一個(gè)皇后添加在左側(cè)空列，且保證沒有兩個(gè)皇后能夠相互攻擊，就是一個(gè)后繼 Arc cost: 無關(guān)緊要 Goal test: 8個(gè)皇后都在棋盤上 2,057 states人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou41n-Queens Problem 一個(gè)就是一個(gè)目標(biāo)節(jié)點(diǎn)，而不是一條解的路徑（這是一個(gè)典型的設(shè)計(jì)問題） 狀態(tài)空間的狀態(tài)個(gè)數(shù)： 8-queens 2,057 100

17、-queens 1052 現(xiàn)在的技術(shù)方法已經(jīng)能高效的解決大數(shù)值n皇后問題發(fā)現(xiàn)存在許多的解分布在狀態(tài)空間里人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou42Assembly (Sequence) Planning人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou43Possible FormulationStates: All decompositions of the assembly into subassemblies (subsets of parts in their relative placements in the assembly)Initial sta

18、te: 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 me

19、rging人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou44A Portion of State Space人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou45But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou46But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou47But the formulation rules out “

20、non-monotonic” assemblies人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou48But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou49But the formulation rules out “non-monotonic” assemblies人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou50基本搜索中的假設(shè)基本搜索中的假設(shè)Assumptions in Basic Search The world is static 靜態(tài)

21、The world is discretizable 離散 The world is observable 可觀察 The actions are deterministic 確定性不過上述許多假設(shè)可以是不必要的，因此搜索仍然是一種重要的問題求解工具人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou51搜索與搜索與AISearch and AI 搜索方法在AI系統(tǒng)中幾乎是無處不在的，常常是系統(tǒng)內(nèi)核與外部模塊的骨架 一個(gè)自主機(jī)器人使用搜索: 決定該采取的動(dòng)作和執(zhí)行哪一個(gè)傳感操作 快速的預(yù)測可能發(fā)生的碰撞 軌道的規(guī)劃 將由大量傳感器得到的數(shù)字設(shè)計(jì)翻譯為符號(hào)的描述 診斷一些預(yù)期的事情為何沒

22、有發(fā)生 . . 許多搜索可能會(huì)同時(shí)發(fā)生并持續(xù)進(jìn)行人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou52應(yīng)用應(yīng)用Applications搜索在許多的應(yīng)用里擔(dān)任著關(guān)鍵的角色，例如: 路徑查找：旅行航線，網(wǎng)絡(luò) 包裹/郵件的分揀 管道路由，VLSI 路由 蛋白質(zhì)鍵的比較與分類 制藥業(yè)中的藥物設(shè)計(jì) 視頻游戲人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou53人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou54Data structures: Searching dataAI: Searching solutions人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.

23、Ou55Example: robot assembly States? Initial state? Actions? Goal test? Path cost?人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 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? Continu

24、ous motion of robot jointsGoal test? Complete assembly (without robot)Path cost? Time to execute人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 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、西大學(xué) 計(jì)算機(jī)學(xué)院 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年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou59CSP Example: Cryptharithmetic puzzle人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou60CSP Example: Cryptharithmetic puzzle人工智能原理2009年春季 廣西大學(xué) 計(jì)算機(jī)學(xué)院 Dr.Ou61A Water Jug Problem You have a 4-gallon and a