9.1 Introduction?

? 大概所有游戲行業(yè)的從業(yè)人員都知道行為樹，除非你從不關心技術(Isla 2005, Champandard and Dunstan 2012). 行為樹是一種基于任務層次圖來控制npc行為的體系結構，其中每個任務要么是一個原子，一個智能體可以直接執(zhí)行的簡單行為，要么是一個由任意復雜度的低級行為樹執(zhí)行的行為的組合。由于行為樹提供了比層次有限狀態(tài)機（HFSM）等替代方案更簡潔清晰的行為分解，并且有大量成功使用的經驗報告，行為樹的使用讓大團隊能處理更復雜的智能體行為，不僅在游戲行業(yè)中，在機器人領域也是如此。但是在實現(xiàn)中有一些關鍵的技術難點，這些關鍵點要嘛讓架構更困難，要嘛讓實現(xiàn)更靈活、易于擴展和易于重用。

? 我好不容易才發(fā)現(xiàn)這些關鍵點。在命運的驅使下，我已經實現(xiàn)了五次行為樹，包括Lisp中的三個與行為樹架構相似的系統(tǒng)，這這三個系統(tǒng)后來用于Halo2的AI系統(tǒng)中。并且最近為谷歌的機器人項目提供了兩個基于C++的行為樹方案實現(xiàn)。

? 在這個過程中，我學到了一些在創(chuàng)建行為樹時不應該做的事情，包括不必要地倍增核心原語（core primitives），發(fā)明了一個完整的控制編程語言，并在將所有通信通過“適當?shù)摹鼻溃ㄈ绾诎澹┻M行路由時，我提出了一些具體的建議，如何創(chuàng)建一個避免這些陷阱的系統(tǒng)，尤其是在許可或互操作性問題阻礙了您在現(xiàn)有商業(yè)或開源解決方案的基礎上構建時。

?9.2 What Makes Behavior Trees Work

? 像行為樹這樣的想法早在Halo出現(xiàn)之前就已經存在了。將行為分解分層為任務最先是由RAPs (Firby? 1987)開創(chuàng)的：高級RAPs被分解成低級RAPs，最終在最底層的葉子節(jié)點中用來直接控制真實或模擬的機器人?(Bonasso et al. 1997).?

行為到任務的分層分解是由反應性動作包（rap）開創(chuàng)的（Firby 1987）：高級rap被分解成低級rap，最終在葉技能中達到最低點，這些技能用于直接控制真實和模擬機器人（Bonasso et al。1997年）。我的TaskStorm架構更接近現(xiàn)代行為樹，將層次化的任務裝飾位置（hierarchical task decomposition）直接集成到封裝智能體狀態(tài)的黑板系統(tǒng)中，使得認知操作能夠在行為過程中相互分割?(Francis 2000)。

? 盡管這些系統(tǒng)在功能上類似于行為樹，但Damian Isla補充的關鍵點側重軟件設計方面，重點在于簡化生成行為樹所需的代碼(Isla 2005).

? Isla認為，有四個關鍵特性使Halo2的AI及其后續(xù)產品得以大規(guī)模開發(fā)：可定制性、明確性、可編輯性和可變性。

• 可定制性，行為被分解成更小的組件，這些組件可以單獨更改或參數(shù)化；

• 明確性，智能體所做的事情可以表示為不同的行為節(jié)點，整個行為可以表示為一個圖；

• 可編輯性，行為的徹底分解使得用現(xiàn)版本替換節(jié)點（舊版本）變得容易；

• 可變性，控制算法本身被表示為節(jié)點；

? 根據我的經驗，在實現(xiàn)過程中很容易失去方向，導致偏離最初的功能設計，并在這個過程中忽略這個關鍵點。一個在功能上將行為分解為由復合行為樹組成的原子行為的系統(tǒng)，其行為可能類似于行為樹，但如果行為過于緊密，它將不可定制或可編輯，如果節(jié)點太過臃腫，它也不會是明確的或可變的。更糟糕的是，實施這些特性的設計模式可能成為比疾病更糟糕的治療方法，使整個系統(tǒng)更難維護。盡管其中一些問題是不可避免的，但如果我們對如何設計行為樹非常小心，其他陷阱也很容易避免。

9.3 Pitfalls in Behavior Tree Design

? 行為樹作為一個決策組件運行在一個更大的結構（游戲引擎、機器人操作系統(tǒng)或認知架構）中，它很容易設計出滿足父系統(tǒng)所有需求的東西。但是，當軟件各組件有明確定義的職責范圍和明確區(qū)分的關注點時，會工作得更好。與此同時，反常的是，你的行為樹做的越多效率反而更低。其中三個陷阱是：

1. 將過多不同功能的類添加進行為樹的決策體系中。

2. 在不需要時提前加入其它編程語言。

3. 強迫所有的通信都必須通過黑板系統(tǒng)（作為準則之一），而不是按需實現(xiàn)。

? 如果你在一個大項目中，并且對你需要的東西有一個明確的規(guī)范（或經驗），（2）和（3）可能不適用于你；但如果你在一個較小的項目中，更簡單的結構可能適合你。

9.3.1 Pitfall #1: Creating Too Many Organizing Classes

? Occam的Razor被簡化為“保持簡單，傻瓜化”，但最初的表述更像是“如無必要，勿增實體”——這更符合行為樹架構的一個陷阱：為系統(tǒng)需要做的每一種事情創(chuàng)建一個單獨的架構類別。這使得開發(fā)所需的特性變得更加困難。

? 例如，除了執(zhí)行動作的元行為和編排動作的復合行為外，角色可能需要一些低級“技能”來直接操縱動畫系統(tǒng)，或機器人控制器，或管理游戲引擎或機器人操作系統(tǒng)提供的資源的高級“模塊”。但是，為每一個模塊（即行為、組合、技能和模塊的根類）單獨構建體系結構類別可能是錯誤的。行為樹已經提供了低層和高層結構，并且隨著外部內存存儲的增加，它們的決策能力是圖靈完備的。那么，為什么不使用行為呢？

? 如前所述，許多類似行為樹的史前系統(tǒng)在技能、任務、任務網絡或模塊等概念之間進行了區(qū)分，并創(chuàng)建了實現(xiàn)這些概念的類或模塊。這種方法完成了任務，也許在Lisp hacking時期是一種好方法，但是這種通過增加實體來實現(xiàn)功能的方法，在以更少的類來實現(xiàn)快速迭代重構的現(xiàn)代C++開發(fā)中會引入更多的陷阱。

? 例如，我們?yōu)镚oogle一個內部機器人項目開發(fā)的行為樹有兩個模塊，一是通過上下文模塊與機器人操作系統(tǒng)交流，一是組成行為樹的任務模塊，它通過隱藏底層通信協(xié)議的稱為AgentHandles的thin wrappers直接與智能體通信。

? 但是隨著系統(tǒng)體系結構的發(fā)展，每一個簡單的重構都會影響到這兩個模塊，而會影響到其他系統(tǒng)的（如Blackboard）更復雜的新功能需要考慮到兩者不同的特性，為兼容做額外的開發(fā)。

? 我們只使用tasks來避免創(chuàng)建太多抽象類。可以將所有能在行為樹中完成的事都看成是在創(chuàng)建新的任務。執(zhí)行元行為？任務。將多個動作分組？另一種任務。訪問系統(tǒng)資源？任務。運行整個行為樹腳本？另一種任務。我們最終采納了一句口頭禪：“這是任務，一路向下?！?/p>

??當我們把這個行為樹移植到一個新的機器人平臺上時，一切都變成了一項任務。好吧，從技術上講，不是所有來自機器人操作系統(tǒng)的資源都是由ExecutionContext統(tǒng)一提供的，但是所有負責行為模塊的類，比如舊的AgentHandles和腳本都被實現(xiàn)為一個任務的子任務SchedulableTask，如表9.1所示；這個類為給定特定ExecutionContext的單個決策步驟提供接口。

? 將所有這些不同的類型強制到一個模型中并沒有傷害我們；相反，結果是我們的新行為樹變成了一個具有單一責任決策的系統(tǒng)，其API只有兩個外部聯(lián)系點：頂部提供ExecutionContext或底部葉任務中的自定義代碼。這種更簡單的設計使我們能夠在幾個星期內構建出功能，而舊系統(tǒng)已經花了我們幾個月的時間。

9.3.2 Pitfall #2: Implementing a Language Too Soon

??行為樹是一個決策系統(tǒng)，這意味著構成樹的行為節(jié)點需要兩個獨立的屬性：一個節(jié)點既需要運行行為的能力，也需要決定是否運行行為的能力。這就提出了行為樹系統(tǒng)本身是否應該實現(xiàn)條件語言的問題。

? 你可以只做一點工作就能完成大部分的事情；甚至非常簡單的決策結構都是圖靈完備的：實際上，您可以使用NANDs或NORs執(zhí)行任何計算。

? 因此，可以用很少的節(jié)點類型實現(xiàn)復雜的控制行為。測試可以通過簡單的成功或失敗的元操作來實現(xiàn)；if–thens可以由組合實現(xiàn)，比如執(zhí)行第一個非失敗操作的Selectors，代碼塊可以由執(zhí)行所有未失敗操作的Sequences或Parallel nodes來實現(xiàn)，Parallel nodes允許同時執(zhí)行多個操作（Champandard和Dunstan 2012）。

? ? 使用非常簡單的組件（Tinkertoy  style）實現(xiàn)復雜的行為會導致很多boilerplate，因此很容易添加更多的控件結構。封裝其他任務的Decorator task允許創(chuàng)建反轉失敗重要性的Not；序列的子類可以創(chuàng)建一個And task，該任務只有在其所有任務都成功的情況下才能成功，依此類推。很快，您會發(fā)現(xiàn)自己正在開發(fā)一種完整的編程語言，它使您能夠簡潔地表示字符邏輯。

? 對于一個“陷阱”部分，我并不建議您不要實現(xiàn)一個完整的編程語言（這對于一個雙重否定是怎樣的）；如果您的行為樹會大量應用，您可能確實想要實現(xiàn)一種語言。但是我用兩種不同的方式實現(xiàn)了這類語言：從上到下從語言關注點出發(fā)，從下到上，基于對問題域的理解從下往上驅動，后者是一種更有效的策略。

? 有大量可供選擇的語言結構----Not, And, Or, If-Then-Else, Cond, Loop, For, While, Repeat-Until, Progn, Parallel, Any, All, Try-Catch-Except----當你學習你最喜歡的編程語言（可能不是C++）時，你看你會對其中的一個或多個情有獨鐘。大多數(shù)這些構造的邏輯都非常清晰，因此很容易為任何可能的需要構建一個大型庫。

??問題是，這些邏輯中的大部分可以通過標準行為樹節(jié)點來更好的實現(xiàn)----Actions、Decorator、Sequence、Parallels和Selector。（你可以試著在Selector和Cond之間找一找區(qū)別）最好的情況是，最終得到一個具有非標準名稱的節(jié)點。更糟糕的情況是編寫不需要的功能。實際的最壞情況時，最終你在多個相似的節(jié)點之間實現(xiàn)了重復的邏輯，這些節(jié)點雖然是被需要的，但隨著API的擴展，變得非常難以維護。

? 一個更好的方法是從行為樹節(jié)點的標準集合開始----Actions, Decorators, Sequences, Parallels, and Selectors，并盡可能將它們應用到您的問題域中。如果你要自己實現(xiàn)它們，那每個行為樹對于任務執(zhí)行、失敗和成功以及邏輯測試的含義都會略有不同。一旦你理解了你的問題域需要什么樣的模式，你就可以通過特化現(xiàn)有的結構來擴展你的語言。這將減少無意義的重復，得到更易于維護的代碼，和一個由對游戲有用的內容驅動的構造庫。

? 對于object containment這樣的結構特性，這一點很容易看到；例如，如果Schedulable Task有GetChildren和AddChild來管理其子級（children），在沒有子級的原子葉子任務和有子級的組合任務中，應該用不同的方式來重寫這些子級。對于我們用例中的幾乎所有不同類型的容器，一個高級類，如清單9.2所示的ContainerTask足以處理所有這些實現(xiàn)細節(jié)。

? 這是一個簡單的類設計，所以我假設您在執(zhí)行這個類或它的對應的AtomicTask的實現(xiàn)時沒有任何困難。實際上，我們擁有的每一個組合任務都繼承自ContainerTask；我們與此模式的唯一不同之處是某些類型的隊列不是從向量繼承的。

??但我們在行為領域有更好的復用機會。我們不應該簡單地分別實現(xiàn)每個任務的Step成員函數(shù)，而是應該分解Step成員函數(shù)，并通過類的受保護接口將stepping API的內部公開給子類，如清單9.3所示。

? 使用這些受保護的成員函數(shù)，Step成員函數(shù)在SchedulableTask中以一種看起來幾乎微不足道的方式實現(xiàn)。但是，通過在樹的頂部定義這個（和類似的成員函數(shù)），我們定義了任務的執(zhí)行模型，所以我們真正需要了解的是任務與規(guī)范的區(qū)別。我們已經展示的ContainerTask只包含任務；它沒有執(zhí)行語義。但是在樹的下一級出現(xiàn)了類似ParallelTask或SequenceTask之類的任務，它們確實覆蓋了這些受保護的方法，如清單9.4所示。

? 一個實際的SequenceTask的核心可以相當簡單，在它的PerformAction成員函數(shù)中進行編碼。但是我們做的不僅僅是實現(xiàn)這個成員函數(shù)；我們還在受保護的API中暴露了它的一些內部特性，包括HandleChildFailure和AdvanceToNextChild。

? 我們選擇通過查看我們的機器人應用程序的實際決策用例來做到這一點，我們希望在不使實際的SequenceTask非常復雜的情況下，對任務如何響應各種環(huán)境進行更細粒度的控制。例如，我們需要一個TryTask，它按序列測試子任務，但如果子任務失敗，它本身不會失敗。通過在受保護的API中公開AdvanceToNextChild和HandleChildFailure，我們能夠用（本質上）半頁代碼編寫一個TryTask，如清單9.5所示。

? 我們需要重寫的唯一成員函數(shù)是HandleChildFailure，重寫本身非常簡單。這使得開發(fā)和測試這個類變得很容易；我們可以依賴父類的控制和stepping邏輯，并將測試重點放在HandleChildFailure及其對子級失敗的影響上。

? 此設計基于具有可重寫成員函數(shù)的類層次結構分解行為樹。在C++中，這可能比手工編寫的代碼更為有效。Game AI Pro 第一卷中關于 Behavior Tree Starter Kit 的章節(jié)描述了一系列這樣的權衡和考慮，你可以參考并深入考慮（Champandard和Dunstan 2012）。

? 對于我們的用例，這種明確的行為分解適用于其頂層決策周期不超過30赫茲的機器人。這可能不一定適用于需要優(yōu)化每個周期的游戲，但我們能夠在一臺不太結實的計算機上運行一個行為樹步驟，以獲得6000萬赫茲的簡單基準。因此，您可能需要從一個簡潔的分支開始，這個分支易擴展，且后續(xù)易于優(yōu)化并將其當做基準、分析和游戲所需的一切。

9.3.3 Pitfall #3: Routing Everything through the Blackboard

? 以前，類似BT的系統(tǒng)被設計成將認知任務分解成一個個功能塊(Francis 2000)，因此，系統(tǒng)所做的思考可以與系統(tǒng)的內存檢索過程混合在一起；為了使內存檢索工作正常，系統(tǒng)操作的幾乎所有數(shù)據都需要暴露在系統(tǒng)的黑板上。

? 因此系統(tǒng)所做的思想可以與系統(tǒng)的記憶檢索過程交織在一起；為了使記憶檢索起作用，系統(tǒng)操縱的幾乎所有數(shù)據都需要暴露在系統(tǒng)的黑板上。一種機器人控制系統(tǒng)，其中多個獨立進程進行通信，如ROS(ROS.org 2016)，也有類似的約束，谷歌的機器人行為樹的第一個版本支持系統(tǒng)黑板和行為樹之間的緊密交互。雖然不是系統(tǒng)的必需部分，但這使我們能夠同時指定行為樹及其數(shù)據。

??類似的問題也存在于需要感官模型的游戲中，比如潛行游戲（以及許多其他現(xiàn)代射擊游戲），但是，將整個行為樹邏輯與黑板的邏輯聯(lián)系得太緊密可能是一個錯誤，在原型設計過程中，將簡單任務依賴于黑板進行通信，這可能是一個錯誤。

? 將所有任務通過黑板系統(tǒng)或感官管理器來實現(xiàn)，同時還要隨著系統(tǒng)變得復雜龐大的時候還能順暢的運行，這可能比使用編程語言自帶的特性來進行通信要復雜得多，而且往往不太可靠，除非你們精通c++模板并用它創(chuàng)建了一個類型安全的黑辦系統(tǒng)（如果是，這將更強大）。?

? 在原型設計階段，以這種方式“正確”地做事情實際上會干擾到行為樹的設計空間的探索和完善它們的邏輯。在我們的第一個行為樹中，黑板和行為樹被設計在一起，相互補充。不幸的是，這意味著一個應用程序接口的改變會影響到另一個，特別是任務的層次結構如何引用黑板的層次結構，反之亦然。至少在兩個不同的情況下，較低級別的API更改會導致一個月或更長的時間來重新連接任務和黑板，以便所有數(shù)據都可以用于正確的任務。

? 另一種方法是將行為樹與黑板強解耦。相同的行為樹邏輯應該與復雜的層次黑板一起工作，具有豐富的知識表示或具有簡單的C++簡單的舊數(shù)據結構（POD），或者甚至沒有顯式黑板，并建立協(xié)作任務之間的臨時通信。使用ad-hoc communication可以使構建完整的數(shù)據驅動的行為樹變得更加困難，但是對于許多問題，這已經足夠了。例如，一個機器學習系統(tǒng)成功地學習了比人類行為樹更好的控制，而無人機則使用了一個只包含少量值的C++ POD作為黑板。

? 當我們?yōu)橐粋€新的機器人平臺重新實現(xiàn)我們的行為樹時，我們暫時放棄了黑板，取而代之的是ad-hoc communication，這有兩個好處。

1. 可以在更高層次上測試和完善黑板的邏輯；

2. 當我們決定放棄一個低級API時，只需要更改兩個葉子節(jié)點上的任務。

? 我們在新的行為樹中仍然有一個舊黑板的用例，但把關注點從舊黑板上清晰地分離出來意味著我們有一個可靠的、經過良好測試的行為樹，它可以與各種通信機制一起工作。

? 我不能用簡單的代碼就清楚地告訴你這兩種方法之間的區(qū)別（舊的黑板上代碼很龐雜，新的通信機制是它們的用例所特有的），但如果你的行為樹架構合理，你可以在以下兩個場景使用相同的核心決策邏輯：

• 玩具級Demo：其“黑板”是一個C++的POD，其決策是由C++ LAMBDAS完成的。

• 一個完整的系統(tǒng)：它有一個分布式黑板和一個完全由數(shù)據驅動的行為樹條件系統(tǒng)。
  

9.4 Conclusion

? 我設計過很多行為樹系統(tǒng)和類行為樹系統(tǒng)，實現(xiàn)過程中遇到過許多陷阱。但我在上面概述的模式很簡單：首先弄清楚你的需求是什么，在沒確定好需求前不要急著動手，精煉設計直到可以用最簡單的方式來表達足夠復雜的功能。這種方法可以應用于任何地方，當您這樣做時，它可以從根本上改善您的開發(fā)體驗。

? 測試驅動開發(fā)和持續(xù)集成以及重構工具會讓這一過程變得簡單（sed, awk, 和?shell腳本工具也會幫上大用處），但我想說的是行為樹可能會十分復雜，其結構卻非常規(guī)則，因此非常重要的一點是要重點關注可能導致重復性工作的地方，并通過類層次結構來解決這一問題。

? 我們第一次嘗試創(chuàng)建行為樹時產生了太多的概念、太多重復的代碼和太多的樣板文件。通過減少實體的數(shù)量，考慮相關領域的需求，并將復雜性關聯(lián)到精心選擇的超類和支持文件中，我們從根本上減少了必須維護的重復代碼的數(shù)量，乃至一頁就能放下。

? 當你做到了這一點，并且你可以對你的系統(tǒng)進行基準測試以證明它仍然是有效的，那么你就完成了構建行為樹的工作。

References

Bonasso, R. P., Firby, R. J., Gat, E., Kortenkamp, D., Miller, D. P., and Slack, M. G.?

1997. Experiences with an architecture for intelligent, reactive agents. Journal of?

Experimental & Theoretical Artificial Intelligence 9(2–3):237–256.

Champandard, A., and Dunstan, P. 2012. The behavior tree starter kit. In Game AI Pro, ed.?

S. Rabin. Boca Raton, FL: CRC Press, pp. 73–95.

Firby, R. J. 1987. An investigation into reactive planning in complex domains. AAAI

87:202–206.

文章來源：http://www.gameaipro.com/??? ?

如侵犯版權，請聯(lián)系譯者刪除。??? ?

讀者若需要轉載，請注明出處。? ???

若有錯誤，歡迎指正。