面向目標的計劃合并技術

劉宏義

(西安陸軍學院信息化研究試驗室，陜西西安 710108)

使用面向目標的行為計劃系統創建和管理自動化代理的行為是一種強大的技術，并且迅速地在游戲開發者中得到認同。在游戲開發中，計劃系統相對來說是新技術，但是學術界使用計劃來解決問題己經有多年。所以，找到一個可供游戲開發者用于改進計劃系統的研究基礎并不困難。計劃者可以使用計劃合并技術改進當前的計劃系統，使自動化代理的行為范圍變得更寬，甚至讓它們同時嘗試追求多個目標。這種技術使用方式有多種，但尚未應用到游戲中。本文描述了在實時游戲的背景下，實現計劃合并系統的方法以及使用這個系統的含義。

1 面向目標的計劃系統

面向目標的行為計劃系統是一種決策算法，它能讓程序員擺脫對特定代理行為的選擇，將這些選擇置入代理自身的感覺－思考－行為的循壞中。使用這個系統的最大好處是減少設計人工代理個人行為的復雜度，同時在代理的總行為中保持很高水準的真實感［1］。

面向目標計劃讓特定的代理通過追求特定的目標來決定自身的行為。一個代理的目標可能包括破壞一個目標或獲得一個物品。在使用代理來記錄世界狀態的系統中，目標被表現為期望的世界狀態。在傳統的計劃系統中，代理被限制，只能在給定的地點及時機挑選一個最重要的目標。一旦這個目標被選中，一個代理可以將原子行為串聯成一個序列來創建一個計劃，有時也被叫做運算符。

使用效果和前提作為指導，任何啟發式的搜索都可以通過列出一個代理可用來達到期望目標的行為序列來創造計劃。文獻［2～3］中描述了如何為計劃目的而使用A*算法。完成后的計劃就是代理用來實現目標的一系列行為。

圖1展示了制作三明治的部分有序計劃和完全有序計劃的例子。在部分有序計劃的版本中，注意獨立的行為相互之間沒有順序關系。但是行為可以有相對的順序:所有的組成部分必須在制作三明治前獲得。通常來說，給予行為的惟一順序是行為的前提條件所要求的。另外，完全有序計劃加強了所有行為的特定順序，而不管單獨的行為是否滿足其他行為的前提條件。雖然可以為三明治以任何順序獲得肉、奶酪和面包，但是一個完全有序計劃指定了執行這些行為的順序。顯而易見，任何部分有序計劃都可以被表現為一個完全有序計劃［4］。

雖然絕大多數基于學術的計劃算法產生部分有序計劃，但是這種類型的計劃者還沒有在游戲中找到廣泛應用。有一些原因解釋了為什么完全有序計劃能更直接地應用到 NPC 上［5－6］。

圖1 部分和完全有序計劃

首先，給予一個部分有序的計劃，為了執行計劃的行為，一個代理在某時不得不明確地或含糊地定義一個完全有序計劃。也就是說，代理仍然需要在任何數量的未排序的行為中選擇一個行為來第一個執行。在這個基礎上，有些原因解釋了為什么在其他行為前執行一個行為可能是有利的，但是代理選擇第一個行為的原因可以很容易地被抽象到計劃者自身。

游戲傳統地處理完全有序計劃的第二個主要原因是用A*來創造計劃的方便性。因為A*是一個眾所周知并且多用途的算法，對于面向目標的計劃系統是一個好的選擇，而且A*本質上產生完全有序計劃。文獻［2～4］覆蓋了許多用于游戲中實現A*計劃系統的實踐細節。

2 用于面向目標計劃的計劃合并

計劃合并適用于采取一些獨立生成的計劃并從中生成一個單獨計劃的過程，通常伴隨著減少計劃的總體開銷的目的。減少了開銷的計劃往往也有著產生更合理行為的益處。

利用一個計劃系統，可以有很多方式完成這個行為。假設收集道具并返回家的目標叫做道具返回目標?？梢詫懸粋€收集道具行為來完成這個目標。一個執行收集道具行為的代理會尋找最近的道具，盡可能多地收集，然后帶著它們返回家。雖然這是一種解決方案，但很明顯，收集道具行為會非常復雜。它需要包括尋路和在道具間移動，拾起道具，尋路回家，以及到達之后放下道具的代碼。為了使在一個行為中增加的功能起作用，會挫敗擁有一個靈活的計劃系統的目的。

普遍會選取兩個有重疊行為的計劃，把它們合并為一個比單獨執行每個原本計劃開銷要低的單一計劃。在這個例子中，代理可以計劃獨自收集每個道具，產生兩個不相關但十分相似的計劃，如圖2(a)所示。合并這樣的兩個計劃的可能結果是盡可能合并更多的行為，產生單獨的計劃，如圖2(b)所示。當代理執行這個計劃時，它會在回家前收集兩個道具。

圖2 兩個完全有序計劃和它們可能合并的結果

2.1 實現一個計劃合并算法

計劃合并的主要目的是優化計劃。文獻［1］指出了優化一個計劃的兩個主要組成部分，一是找到可以被合并的行為;二是如果存在多于一種合并操作的方法，則算出最優的方法來合并行為。分開處理這些問題會更容易，所以我們在本文中采用這種方法。

尋找可合并行為的第一個挑戰在于準確地發現什么類型的行為可以被合并。但是簡單來說，如果有另一個行為可以用下面的結果來代替被合并的行為，任何行為都可以被合并。

(1)如果行為有相同的有用的效果。

(2)如果用來代替的行為的開銷小于被合并行為的開銷總和。

如果效果直接為計劃中的另一個行為建立了前提條件或者是目標本身的前提，那就是有用的。比如，假設一個代理計劃用開火和上膛行為來摧毀目標。上膛行為有很多效果，首先，它使武器有子彈，其次，它減少了代理的彈藥量。第一個效果是有用的，因為它完成了計劃中另一個行為的前提條件。第二個效果沒有用，因為它與計劃的執行無關。

如果沒有行為本身的信息，搜索可合并行為計劃的開銷會很大，所以最好尋找那些已知可以合并的行為。在一個已實現的系統中，這意味著要么尋找自己可合并的特定行為，要么尋找已知的可以合并的行為組合。在早些的資源收集例子中，知道代理會有多種計劃，每一個都有Returnltems行為。這就是一個要尋找的完美的候選行為，因為知道可以合并兩個Retumltems行為。在這個特定的例子中，甚至可以從計劃的末尾開始尋找，因為很可能是每一個計劃中的最后行為可以被合并。GoTo(Base)也可以與自身合并，因為它顯然可以完成同樣的效果。

最簡單的是，接下來合并計劃算法接受由通用A*計劃系統生成的兩個計劃。比如，代理可以把它最重要的兩個目標發給計劃者，然后把那兩個獨立的計劃發送給計劃合并者。對于第一個計劃的每一個行為，算法檢查它是否可以被第二個計劃的一個行為合并，如果可以執行合并，那兩個行為被放到一個單獨的計劃中。從兩個計劃中放置合并行為前的行為要小心，對于在合并行為后的行為也是一樣。如果需要對未合并行為的順序進行更精確的控制，可以加入評價來決定最好的順序，并且根據需要重新安排行為的順序。對于更廣范圍的可能合并來說，一個完整的計劃合并算法應該在每一個計劃中檢查每一個可能的行為組的綜合效果，尋找一連串的行為可以被一個單獨的、更廉價的行為所代替的情況。這樣一個算法對可合并計劃產生非?？捎^的改進，但是運行起來開銷同樣巨大。

2.2 超越單代理合并

雖然為一個單獨的代理合并兩個計劃確實可以改進行為，但計劃合并同樣在分組行為區域中可以提供益處。比如，一個利用計劃合并的代理可以合并一個單獨的目標和分組目標。在這些情況下，利用計劃合并可以允許一個代理在分組順序下維持它自己的目標和個性，甚至允許代理同時完成很多目標的情況。

2.3 提高行為搜索的戰略

搜索帶有相似效果的兩個或多個計劃行為是昂貴的，特別是如果考慮用不同的綜合效果代替行為組。如果游戲是快節奏的，代理的第一個和第二個目標會變換得更快，甚至可以為它的第二個目標設計計劃。確實，如果不能快速執行合并，計劃合并是沒有用的。

一個可能的減少搜索行為時間的戰略是只在計劃存在特定行為時才搜索可合并的行為，這可以在計劃決策過程中做出決定。對于非常長的計劃來說，計劃結構本身會帶有直接與可能合并的行為的聯系，不僅要指示算法立刻進入正確的位置，并且也會通知它是否值得搜索一個合并。在特定類型的代理中，在每一個計劃中只尋找特定行為來合并也是值得的。

相似地，也許只在計劃目標相容的情況下才嘗試合并。相反地，如果兩個計劃之內的目標不相容，也就沒有意義去費力地嘗試合并。確實，如果目標不相容，即使為第二個目標做計劃也一是浪費時間。這個決定可能最好由程序員做出。顯然，攻擊和撤退目標永遠不會產生可合并的計劃，但是算法會在報告沒有可合并行為存在之前搜索每個計劃的每一個行為。

3 結束語

計劃合并提供方法來改進代理在單獨或組行為時的可感知智能。雖然可能是一個開銷十分昂貴的過程，但應仔細地考慮，可以通過花費一小部分額外的時間檢查生成的計劃來完成它。文獻［5～6］介紹了不同的執行計劃合并的系統和方法，也許更適合于比這里描述的代理行為更長的代理。比如，在［6］中描述的計劃合并算法特別適合于策略游戲AI對手，可以用多種不同的方法來完成目標，并且可能延遲行為來利用明確的合并機會。

計劃是一個多功能的AI系統，有很多的機會來進行擴展和改進。即使在給定情況下計劃合并沒有用，但其提出的想法可以應用到其他AI系統中，或者甚至是其他的像分級任務網絡(HTNs)那樣的計劃系統中。這種技術提供的行為改進使得代理有更好的智能，同時使玩家有更好的游戲體驗。

［1］FOUSLER D，LI Ming，YANG Qiang.Theory and algorithms for plan merging ［J］.Artificial Intelligence，1992，57(2 －3):143－181.

［2］ORKIN J.Applying goal－ oriented action planning to games［M］.Charles River Media:AI Game Programming Wisdom 2，2004.

［3］ORKIN J.Symbolic representation of game world state:toward real－ time planning in games［R］.USA:AAAI Challenges in Game AI Workshop Technical Report，2004.

［4］ORKIN J.Three states and a plan:the AI of FEAR［C］.USA:Proceedings from Game Developers Conference，2006.

［5］THANGARAJAH J，WINIKOFF M，PADGHAM L，et al.A-voiding resource conflicts in intelligent agents［C］.Syato:Proceedings of the 15th European Conference on Artificial Intelligence，2002.

［6］THANGARAJAH J，PADGHAM L，WINIKOFF M.Detecting＆exploiting positive goal interaction in intelligent agents［C］.Fukong:AAMAS'03，2003.