【正文】 sing算法 ? Tracking算法還可以做的更為真實一點，就像紅外導(dǎo)彈一樣： ? 在每一幀中，智能體仍然首先計算其到目標的前進方向 ? 這時，智能體的速度允許發(fā)生變化，并根據(jù)更新后的速度，計算下一幀的位置 ? 速度有一個上限，超過這個上限，智能體的速度將減慢，直到重新加速為止 浙江大學(xué) CADCG 國家重點實驗室 Evading算法 ? 與前面的 chasing算法基本相同，唯一區(qū)別是智能體沿著遠離物體的方向移動 浙江大學(xué) CADCG 國家重點實驗室 追逐行為的模擬示例 ? 你追我趕 Game AI/chasing and avoiding demo 基于行為模式的 AI ? 在任一時間點，每一個智能體都按照預(yù)先設(shè)定的某種模式運動 ? 決策系統(tǒng)根據(jù)系統(tǒng)當(dāng)前的狀態(tài)，為每一個智能體從模式集合中選擇適當(dāng)?shù)哪Ｊ? ? 模式描述了智能體將在下面幾幀中所采取的一系列動作 ? 特例： scripted AI，當(dāng)系統(tǒng)到達某一特定狀態(tài)（例如，每個回合的結(jié)束），系統(tǒng)運行的一段程序（用腳本寫），決定系統(tǒng)下一步的動作 典型的行為模式 ? 基本模式 ? 用一段指令定義模式 ? 寫一個解釋器解釋這段指令，并用于控制智能體的行為 ? 條件邏輯模式 ? 更為靈活的控制 ? 可以通過條件邏輯選擇模式 ? 也可以選擇本身帶有條件邏輯轉(zhuǎn)移的模式 編程技巧 ? 非常直觀 ? Pattern是一列數(shù)組 ? 數(shù)組的每一項定義智能體在該幀的速度（方向＋大?。? ? 在模擬過程中，智能體就按照預(yù)先設(shè)定的參數(shù)在每一幀之間運動 ? 當(dāng)移動到數(shù)組末尾時，重新選擇一個新的模式 行為型的 AI技術(shù)示例 ? Chasing behavior AI demo 策略性 AI與通用問題求解 ? AI的研究人員試圖尋找一個通用的計算模型和方法，解決所有的問題 ? 感知輸入系統(tǒng) ? 有一個記憶模擬存儲系統(tǒng) ? 推理機 ? 行為輸出系統(tǒng) ? 博弈問題 ? 有限狀態(tài)機（ FSM） ? 規(guī)劃和搜索 有限狀態(tài)機 ? 狀態(tài)（要采取的行為） ? 追擊 ? 隨機走動 ? 巡邏 ? 吃 ? 轉(zhuǎn)移（發(fā)生轉(zhuǎn)移的原因） ? 時間片結(jié)束 ? 發(fā)生某個時間 ? 完成某個行為 伐木 將木頭運往最近的倉庫 足夠多木材 放下木頭 : 返回林場 到倉庫 到林場 有限狀態(tài)機 ? 機器 ? 所有部件的總稱 ? 狀態(tài) ? 對于層次有限狀態(tài)機而言，狀態(tài)包括各種子狀態(tài) ? 轉(zhuǎn)移 ? 系統(tǒng)從當(dāng)前活動狀態(tài)出發(fā)，判斷下一個活動狀態(tài)，改變系統(tǒng)當(dāng)前的格局，并執(zhí)行相應(yīng)的操作 浙江大學(xué) CADCG 國家重點實驗室 有限狀態(tài)機 ? 條件 ? 定義發(fā)生轉(zhuǎn)移的先決條件 ? 輸入和事件 ? 允許狀態(tài)機對環(huán)境變化作出反應(yīng) ? 動作 ? 作為狀態(tài)的一部分，或者伴隨轉(zhuǎn)移出現(xiàn) 浙江大學(xué) CADCG 國家重點實驗室 狀態(tài)空間圖 ? 有向圖 ? 每個結(jié)點表示系統(tǒng)狀態(tài)模型，每條弧表示狀態(tài)轉(zhuǎn)移所伴隨的動作行為 ? 結(jié)點可以是無窮多個 ? 有些結(jié)點之間可能沒有弧相連接 特定狀態(tài)的查找 ? 結(jié)點 － 包含查找目標 ? 終點 － 搜索路徑的結(jié)束 ? 查找空間 － 所有結(jié)點的集合 ? 目標 － 所要到達的結(jié)點 ? 經(jīng)驗 － 在一定程度上提示下一步搜索的方向 ? 解答路徑 － 從起始結(jié)點開始，到目標的一條有向路徑 模糊的有限狀態(tài)機 ? 將模糊邏輯和有限狀態(tài)機結(jié)合 ? 狀態(tài)之間的遷移不再是確定的 ? 同時有多個狀態(tài) 有限狀態(tài)機和模糊的有限狀態(tài)機示例 ? FSM/FuFSM ? 代碼示例 ? 隸屬度 ? 演示 規(guī)劃 Part of intelligence is the ability to plan Move to a goal State ? 將系統(tǒng)表示成一系列狀態(tài)的集合 ? 通過操作（ Operator）改變狀態(tài) 浙江大學(xué) CADCG 國家重點實驗室 路徑規(guī)劃 ? 狀態(tài) ? 智能體在空間的位置 ? 其他離散空間 ? 體素 ? 室內(nèi)位置 ? 局部區(qū)塊（ tile） ? 操作 ? 從一個位置移動到其他位置 浙江大學(xué) CADCG 國家重點實驗室 路徑規(guī)劃算法 ? 必須對狀態(tài)空間進行搜索，才能轉(zhuǎn)移至目標狀態(tài) ? 完全性 ? 如果目標狀態(tài)存在，算法是否能夠?qū)⑵湔业剑? ? 時間復(fù)雜度 ? 空間復(fù)雜度 ? 能夠找到最優(yōu)解 浙江大學(xué) CADCG 國家重點實驗室 搜索策略 ? 如何評價搜索算法 ? 時間：多長時間能夠找到解 ? 找到的解是最優(yōu)、次優(yōu)還是其他 ? 盲目搜索 ? 沒有先驗知識 ? 僅僅知道目標狀態(tài)是什么 ? 經(jīng)驗搜索 ? 用經(jīng)驗公式表示擁有的先驗知識 ? “ 經(jīng)驗 ” 只能作相對簡單、低級的決策 浙江大學(xué) CADCG 國家重點實驗室 廣度優(yōu)先搜索 ? 根結(jié)點 兒子結(jié)點 孫子結(jié)點 ? 缺點：內(nèi)存消耗大 浙江大學(xué) CADCG 國家重點實驗室 Root Root Child1 Child2 Root Child1 Child2 GChild1 GChild2 GChild3 GChild4 (1) (2) (3) 深度優(yōu)先搜索 ? 先兒子結(jié)點，后兄弟 浙江大學(xué) CADCG 國家重點實驗室 Root Child1 GChild1 GChild2 Root Child1 Root Child1 GChild1 (1) (2) (3) 雙向搜索 ? 同時產(chǎn)生兩棵搜索樹 ? 一棵從起點出發(fā) ? 一棵從目標出發(fā) 浙江大學(xué) CADCG 國家重點實驗室 啟發(fā)式搜索 ? 定義目標函數(shù)，反映擁有的先驗知識 ? 估計離目標的距離 ? 估計到達目標的花費 ? 用上述估計指導(dǎo)路徑的搜索，加快搜索過程 浙江大學(xué) CADCG 國家重點實驗室 貪婪搜索法 ? 永遠沿著具有最小目標函數(shù)值的路徑進行搜索 ? 不一定能夠找到目標 ? 可能得到局部最優(yōu)解，而不是全局最優(yōu) 浙江大學(xué) CADCG 國家重點實驗室 A*啟發(fā)搜索 ? 考慮到貪婪搜索法不能保證找到最優(yōu)解 ? 改進 － 目標函數(shù)由兩個部分組成 ? 從當(dāng)前狀態(tài)到目標狀態(tài)的 “ 花費