游戲中的人工智能技術(shù)-展示頁
2025-01-24 18:09本頁面
【正文】 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ā) ? 一棵從目標(biāo)出發(fā) 浙江大學(xué) CADCG 國家重點實驗室 啟發(fā)式搜索 ? 定義目標(biāo)函數(shù)，反映擁有的先驗知識 ? 估計離目標(biāo)的距離 ? 估計到達(dá)目標(biāo)的花費 ? 用上述估計指導(dǎo)路徑的搜索，加快搜索過程 浙江大學(xué) CADCG 國家重點實驗室 貪婪搜索法 ? 永遠(yuǎn)沿著具有最小目標(biāo)函數(shù)值的路徑進(jìn)行搜索 ? 不一定能夠找到目標(biāo) ? 可能得到局部最優(yōu)解，而不是全局最優(yōu) 浙江大學(xué) CADCG 國家重點實驗室 A*啟發(fā)搜索 ? 考慮到貪婪搜索法不能保證找到最優(yōu)解 ? 改進(jìn) － 目標(biāo)函數(shù)由兩個部分組成 ? 從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的 “ 花費 ” （估計） ? 從初始狀態(tài)到當(dāng)前狀態(tài)的 “ 花費 ” 浙江大學(xué) CADCG 國家重點實驗室 基本想法 ? 貪婪搜索法 ? 對可能的后繼狀態(tài) n’，計算其到目標(biāo)狀態(tài)的“ 花費 ” h(n’)，并置于一個優(yōu)先隊列中 ? A* ? 對可能的后繼狀態(tài) n’，計算其目標(biāo)函數(shù)f(n’)，并置于優(yōu)先隊列中 ? f(n’) = g(n’) + h(n’)，其中 g(n’)是從初始狀態(tài)到 n’的 “ 花費 ” 浙江大學(xué) CADCG 國家重點實驗室 基本想法 ? 選擇下一步狀態(tài) n，使得 f(n)是隊列中最小的 ? 如果 h(n)估計準(zhǔn)確的話，方法是可行的 浙江大學(xué) CADCG 國家重點實驗室 結(jié)束條件 ? A*算法結(jié)束條件是：當(dāng)且僅當(dāng)目標(biāo)狀態(tài)被從優(yōu)先隊列中挑選出來 浙江大學(xué) CADCG 國家重點實驗室 A*算法 ? 優(yōu)先隊列 PQ － 初始為空 ? V（一系列三元組 (狀態(tài)， f，回溯指針 )集合，表示訪問過的結(jié)點） － 初始為空 ? 將初始結(jié)點 S置于 PQ中， V中放入 (S, f(s), NULL) ? 算法： ? 如果 V為空，退出程序，沒有解 ? 否則，從 PQ中取出第一項，記為 n ? 如果 n就是目標(biāo)結(jié)點，則搜索結(jié)束 ? 否則，產(chǎn)生 n的后繼結(jié)點 浙江大學(xué) CADCG 國家重點實驗室 A*算法 ? 對 n的每一個后繼結(jié)點 n’ ? 計算 f’=g(n’)+h(n’)=g(n)+cost(n,n’)+h(n’) ? 如果 n’未被訪問過，或者 n’曾經(jīng)被訪問過，但是記錄的 f(n’)f’，或者 n’已經(jīng)在 PQ隊列中，但是記錄的 f(n’)f’ ? 放置 /更新 n’于優(yōu)先隊列中，使其對應(yīng)的目標(biāo)函數(shù)值為 f’ ? 添加 (n’, f’, n)至 V當(dāng)中 ? 否則忽略 n’ 浙江大學(xué) CADCG 國家重點實驗室 A*算法能否找到最優(yōu)路徑 ? 否 浙江大學(xué) CADCG 國家重點實驗室 A*算法 性質(zhì) ? 令 h*(n)=從目標(biāo)到 n最小花費真實值 . ? 經(jīng)驗 h稱為可行的當(dāng)且僅當(dāng)對所有的狀態(tài) n, h(n) ＜ =h*(n). ? 可行經(jīng)驗確保永不過估計結(jié)點到目標(biāo)的花費 ? 具有可行經(jīng)驗的 A*算法一定收斂到最優(yōu)解 ? 比較費內(nèi)存 ? 當(dāng)不存在解時，算法失敗 ? 避免對全空間進(jìn)行搜索 ? 作雙向搜索 路徑的規(guī)劃和尋找演示 ? A star demo ? 最短路經(jīng) ? 戰(zhàn)術(shù)最短路經(jīng) ? 暴露時間 ? 有效火力 ? 視野 群體行為的模擬（ 1） ? 物群的行為 ? 物群聚集在一起飛行，遇到另一物群時，他們將避開和分散，必要時分成多群 ? 分開后，將尋找伙伴，形成新的物群，并最終恢復(fù)原來的物群 ? 物群能夠?qū)Ω锻话l(fā)行為，能否對不斷變化的環(huán)境做出實時的反應(yīng)，并作為一個整體行動 ? 。 群體行為的模擬（ 2） ? 物群模擬的簡單規(guī)則 ? 分離（ separation）：同物群中的其他成員若即若離。傳統(tǒng)邏輯即隸屬程度只能從 0和 1之間選擇的情況 ? 對于“性格穩(wěn)重”這個模糊概念，我們能夠用“一點而也不穩(wěn)重”、“不太穩(wěn)重”、“不好說”、“有點穩(wěn)重”、“挺穩(wěn)重”、“很穩(wěn)重”等沒有明確界限的詞語形容 模糊邏輯的應(yīng)用 ? 將重心轉(zhuǎn)移至物體屬于某個集合的隸屬程度上 ? 在 AI領(lǐng)域的主要應(yīng)用為 ? 決策 ? 行為選擇 ? 輸入、輸出過濾 浙江大學(xué) CADCG 國家重點實驗室 符合邏輯操作 ? 設(shè) A,B,C均為 U中的模糊集 ? 模糊并 ? 若對 8x2U，均有 ?c=max(?A(x),?B(x))，則稱 C為A與 B的模糊并 ? 模糊交 ? 若對 8x2U，均有 ?c=min(?A(x),?B(x))，則稱 C為A與 B的模糊交 浙江大學(xué) CADCG 國家重點實驗室 例子 浙江大學(xué) CADCG 國家重點實驗室 1 5 f eet 6 f eet 7 f eet 1 5 f eet 6 f eet 7 f eet 大約 6英尺 長的高的人 與 浙江大學(xué) CADCG 國家重點實驗室 或 浙江大學(xué) CADCG 國家重點實驗室 非 浙江大學(xué) CADCG 國家重點實驗室 模糊控制 ? 舉例：車輛駕駛 ? 前提：兩輛車之間不能相撞 ? 在模糊邏輯中的實現(xiàn)： ? 用兩個變量描述每一輛車 ? 當(dāng)前時刻，車與前面一輛車之間的距離 d ? 當(dāng)前時刻與前一時刻距離的差 ?d 浙江大學(xué) CADCG 國家重點實驗室 模糊控制 ? If ?d=0且 d=兩個車位長，保持現(xiàn)有速度 ? If ?d0且 d兩個車位長，減慢速度 ? If ?d0且 d兩個車位長，加快速度 浙江大學(xué) CADCG 國家重點實驗室 小結(jié) ? 模糊邏輯和模糊控制被廣泛用于游戲當(dāng)中 ? 當(dāng)你想模擬人的思維模式時 ? 模糊邏輯同樣能夠用于表示無生命時間 ? 給定風(fēng)速和方向，問云如何移動 浙江大學(xué) CADCG 國家重點實驗室
語文相關(guān)推薦
鄂ICP備17016276號-1