面向目標(biāo)的計(jì)劃合并技術(shù)

劉宏義

(西安陸軍學(xué)院信息化研究試驗(yàn)室，陜西西安 710108)

使用面向目標(biāo)的行為計(jì)劃系統(tǒng)創(chuàng)建和管理自動(dòng)化代理的行為是一種強(qiáng)大的技術(shù)，并且迅速地在游戲開發(fā)者中得到認(rèn)同。在游戲開發(fā)中，計(jì)劃系統(tǒng)相對來說是新技術(shù)，但是學(xué)術(shù)界使用計(jì)劃來解決問題己經(jīng)有多年。所以，找到一個(gè)可供游戲開發(fā)者用于改進(jìn)計(jì)劃系統(tǒng)的研究基礎(chǔ)并不困難。計(jì)劃者可以使用計(jì)劃合并技術(shù)改進(jìn)當(dāng)前的計(jì)劃系統(tǒng)，使自動(dòng)化代理的行為范圍變得更寬，甚至讓它們同時(shí)嘗試追求多個(gè)目標(biāo)。這種技術(shù)使用方式有多種，但尚未應(yīng)用到游戲中。本文描述了在實(shí)時(shí)游戲的背景下，實(shí)現(xiàn)計(jì)劃合并系統(tǒng)的方法以及使用這個(gè)系統(tǒng)的含義。

1 面向目標(biāo)的計(jì)劃系統(tǒng)

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

面向目標(biāo)計(jì)劃讓特定的代理通過追求特定的目標(biāo)來決定自身的行為。一個(gè)代理的目標(biāo)可能包括破壞一個(gè)目標(biāo)或獲得一個(gè)物品。在使用代理來記錄世界狀態(tài)的系統(tǒng)中，目標(biāo)被表現(xiàn)為期望的世界狀態(tài)。在傳統(tǒng)的計(jì)劃系統(tǒng)中，代理被限制，只能在給定的地點(diǎn)及時(shí)機(jī)挑選一個(gè)最重要的目標(biāo)。一旦這個(gè)目標(biāo)被選中，一個(gè)代理可以將原子行為串聯(lián)成一個(gè)序列來創(chuàng)建一個(gè)計(jì)劃，有時(shí)也被叫做運(yùn)算符。

使用效果和前提作為指導(dǎo)，任何啟發(fā)式的搜索都可以通過列出一個(gè)代理可用來達(dá)到期望目標(biāo)的行為序列來創(chuàng)造計(jì)劃。文獻(xiàn)［2～3］中描述了如何為計(jì)劃目的而使用A*算法。完成后的計(jì)劃就是代理用來實(shí)現(xiàn)目標(biāo)的一系列行為。

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

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

圖1 部分和完全有序計(jì)劃

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

游戲傳統(tǒng)地處理完全有序計(jì)劃的第二個(gè)主要原因是用A*來創(chuàng)造計(jì)劃的方便性。因?yàn)锳*是一個(gè)眾所周知并且多用途的算法，對于面向目標(biāo)的計(jì)劃系統(tǒng)是一個(gè)好的選擇，而且A*本質(zhì)上產(chǎn)生完全有序計(jì)劃。文獻(xiàn)［2～4］覆蓋了許多用于游戲中實(shí)現(xiàn)A*計(jì)劃系統(tǒng)的實(shí)踐細(xì)節(jié)。

2 用于面向目標(biāo)計(jì)劃的計(jì)劃合并

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

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

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

圖2 兩個(gè)完全有序計(jì)劃和它們可能合并的結(jié)果

2.1 實(shí)現(xiàn)一個(gè)計(jì)劃合并算法

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

尋找可合并行為的第一個(gè)挑戰(zhàn)在于準(zhǔn)確地發(fā)現(xiàn)什么類型的行為可以被合并。但是簡單來說，如果有另一個(gè)行為可以用下面的結(jié)果來代替被合并的行為，任何行為都可以被合并。

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

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

如果效果直接為計(jì)劃中的另一個(gè)行為建立了前提條件或者是目標(biāo)本身的前提，那就是有用的。比如，假設(shè)一個(gè)代理計(jì)劃用開火和上膛行為來摧毀目標(biāo)。上膛行為有很多效果，首先，它使武器有子彈，其次，它減少了代理的彈藥量。第一個(gè)效果是有用的，因?yàn)樗瓿闪擞?jì)劃中另一個(gè)行為的前提條件。第二個(gè)效果沒有用，因?yàn)樗c計(jì)劃的執(zhí)行無關(guān)。

如果沒有行為本身的信息，搜索可合并行為計(jì)劃的開銷會(huì)很大，所以最好尋找那些已知可以合并的行為。在一個(gè)已實(shí)現(xiàn)的系統(tǒng)中，這意味著要么尋找自己可合并的特定行為，要么尋找已知的可以合并的行為組合。在早些的資源收集例子中，知道代理會(huì)有多種計(jì)劃，每一個(gè)都有Returnltems行為。這就是一個(gè)要尋找的完美的候選行為，因?yàn)橹揽梢院喜蓚€(gè)Retumltems行為。在這個(gè)特定的例子中，甚至可以從計(jì)劃的末尾開始尋找，因?yàn)楹芸赡苁敲恳粋€(gè)計(jì)劃中的最后行為可以被合并。GoTo(Base)也可以與自身合并，因?yàn)樗@然可以完成同樣的效果。

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

2.2 超越單代理合并

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

2.3 提高行為搜索的戰(zhàn)略

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

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

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

3 結(jié)束語

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

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

［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.