家庭仿真求解最優路徑問題算法研究

劉巖愷 薛毅 （天津師范大學計算機與信息工程學院 天津 300387）

0 引言

家庭仿真項目最早為中國科技大學為測試藍鷹“可佳”機器人智能問題求解性能設計的一個開放性測試平臺。[1]立足于服務機器人高層功能的探索，側重對服務機器人自動規劃、自然語言解析、自動判斷及推理能力的認知能力考查。“可佳”機器人的框架包括4個主要部件：人機對話，語言理解，任務規劃和行為規劃。機器人通過人機對話獲得用戶的服務請求，對話語言為詞匯受限的自然語言。語言理解部件將對話中有用信息進行提取、分類和轉換，再傳遞給任務規劃。任務規劃根據機器人知識庫，計算出完成任務的規劃結果，再將其發送給行為規劃部件。[2]

該仿真項目是得到最優的任務規劃，本文以其實現算法為重點。比賽主要分為指令語言,自然語言兩個階段。比賽的評分公式如下：問題得分=10×完成的目標數目+5×維護的約束數目×完成的目標數目-3×行動個數-其他行動個數。[1]

1 關于最優化問題

在遵守指定約束的前提下，自動規劃任務問題得分與move原子動作的發生頻率相關，用盡可能少的move動作完成盡可能多的目標任務，這就是最優化問題的關鍵。

2 求解最優路徑問題

針對上述求解最優路徑問題的分析提出兩種解決策略：一種是最優策略算法，在準確分析確定目標任務以及指定場景后，根據比賽的規則和實際情況對目標任務進行合并以及排序；另一種是目前比較主流而且相對比較穩定的回答集編程。

2.1 最優策略算法

2.1.1 建立世界模型 建立世界模型需要對現實場景及目標任務進行抽象，并在程序每次執行過程中通過相關函數完成對特定場景及目標任務進行描述和刻畫。建立世界模型的成功與否，將直接影響到自動規劃中機器人對當前場景認知的把握程度。

2.1.2 搜索優化 目標任務的初始化是建立在以搜索目標物體在世界模型中的具體信息的基礎上的。下面舉例分析搜索函數在程序設計中存在的難點。

①假設場景文件中有如下描述：

bottle（25）.green（25）.bottle（26）.red（26）.

任務文件中有如下要求：

puton（green bottle,worktable）.give（human,bottle）.

若搜索函數每次只順序搜索到類型為bottle的物體即刻中止搜索，最終結果為give（human,green bottle），兩個任務將都不能執行完成。此種問題解決方案為：設定目標物體標識位，凡是已定目標物體對于二次搜索為透明的。

②承接a中場景的描述假如任務文件有如下描述：

give（human,bottle）.puton（green bottle,worktable）.

結合①的解決方案，會發現此時將無法找到green bottle，因此針對①提出的解決方案，我們需要在①中完善的是：當目標物體第一次無法找到的時候，將在已確定為目標物體的集合中二次搜索，找到green bottle之后，give任務中的目標物體bottle再從未確定為目標物體的集合中搜索。

③假如場景中有如下描述：

bottle（26）.green（26）.bottle（27）.bottle（25）.red（25）.

在任務文件中有如下要求：

give（human,bottle）.puton（bottle,worktable）.puton（green,bottle,worktable）.

在此情況下，會發現在搜索過程中，沒有顏色約束的物體最好搜索到最佳匹配的，即無顏色描述的物體，只有在沒有找到最佳匹配物體之后，再去搜索有顏色約束的物體。

由以上3種情況分析，搜索函數優化：首先，確定為目標的物體設定標志位。其次，在順序搜索的前提下，首次搜索必須是搜索最佳匹配目標物體。最后，只有在搜索完未被確定目標集合后，才會對已確定目標集合進行二次搜索，并再次在未確定目標集合中尋找已確定目標物體的替代物體。

2.1.3 任務動作的排序與合并 在任務目標中，假定機器人不在任務目標的位置上，那么 give（human，obj1），puton（obj1，obj2），putin（obj1，obj2）需要兩次 move（A）原子動作，設定為 A類任務動作；而 putdown（obj1）|pickup（obj1）|opendoor（obj2）要一次 move（A），設定為 B類任務動作；而 goto（obj1）需要 1次move（A），設定為C類動作。在A類任務動作中，除了give（human，obj1），obj1為 big外，其他動作的 obj1均為 small。B類任務動作中，是機器人應該在完成所有任務之后保持的狀態。C類任務動作很明顯應該為機器人的終結動作。

當機器人在執行A類任務動作的時候，剛好有B類中obj1物體時，可以進行同源任務動作合并；當有B類中obj2時，可以進行同目標合并。同理也會有A類任務動作與A類任務動作中同源或同目標動作的合并。在理想情況下，針對每一種情況，程序中都會有相應的處理分支。但是，由于最優策略算法接近于手動實現窮舉法，因此針對部分特殊情況的規劃結果并不令人滿意。

2.2 回答集編程

2.2.1 回答集編程介紹 在人工智能研究方面，回答集編程作為具有非單調推理能力的知識表示和推理的一般工具，在將智能符號推理形式化刻畫的前提下，來實現機器人自主決策，人機交互等認知功能。下面以家庭仿真比賽項目為平臺進行介紹，具體包括：使用ASP刻畫設定環境的初始化情況，機器人的行動效果，初始化任務目標，將機器人中的推理任務（包括規劃和診斷），轉換為求解相應回答及編程程序的回答集。[3-4]

2.2.2 回答集編程求解 在自然語言比賽項目中，特定指令通過語言理解部件被轉換為內部邏輯公式，此過程中需要借助常例化工具Grounder，[5]任務規劃部件將這些公式作為事實直接添加到ASP程序中，形成必須滿足的目標狀態。回答集編程程序的求解實際上相當于通過經典規劃方式，得到最優化行動序列。接下來舉例說明使用回答集編程進行描述的3個基本步驟。[5]

第一步：生成所有潛在可能的解。

通過loc（X）、obj（A）和small（A）3個域謂詞來推出機器人所有可能的動作，這3個域謂詞的初始化是由規劃的環境描述文件完成的。

第二步：用約束消除不符合的解。

任務規劃程序中用not和constraints的方式來滿足目標。比如說在執行自動規劃過程中指定約束不能到B物體，在程序中描述如下：:-notgoal［goto（B），t］，goto（B），obj（B）.

第三步：定義在約束中出現的輔助謂詞。

若任務中有要求機器人catch（A），那么我們需要做出的判斷為機器人是否與其在同一處，若在，直接采用catch動作，若不在則先執行goto（X）動作，然后在再執行catch動作。要實現這些目標，使初始環境變換到目標環境需要機器人的對環境進行改變，不但需要定義機器人原子動作的執行條件，而且也需要定義執行效果，從而為機器人的下一步執行提供依據。

整個任務規劃問題可以歸為回答集編程程序求解問題。采用iclingo[5]求解器進行迭代求解，窮舉所有的行動序列組合從而得到最優行動序列。需要注意的是窮舉雖然能夠得到目標結果，但是當規劃任務過大時，由于規劃的步數太多從而出現超時，下面是在理論基礎上進行的求解效率優化方法。

第一種是從描述規劃問題角度優化。

靜態因果定律：動作的間接效果或一些受其他的謂詞影響的謂詞。

慣性定律：動作改變了其中一些謂詞，但是沒有被動作改變的那些謂詞，其值保持不變。

第二種是從常例化過程中采用增量求解方法，可以判斷當前第i步是否實現目標，若沒有，則會在此基礎上進行第i+1步規劃。

綜上所述，回答集編程具有很好的擴展性，而且在不限定時間的前提下，能夠窮舉得出最有行動序列，其效率仍需進一步改善。

3 總結

本文以家庭仿真比賽為背景，分別介紹了用于任務規劃的最優策略算法以及回答集編程，并對當前在提高回答集編程求解效率方面的方法進行了研究。

[1]吉建民.提高ASP效率的若干途徑及服務機器人上應用[D].中國科學技術大學,2010.

[2]吉建民，陳小平，姜節匯，等.一種支持個性化協調的服務機器人體系結構[J].南京大學學報：自然科學版，2010，46（2）：131-139.

[3]Gelfond,M.，Lifschitz,V.The Stable Model Semantics For Logic Programming[M].In Proceedings of the Fif th International Conference on Logic Programming（ICLP-88），1988：1070-1080.

[4]Gelfond,M.and Lifschitz,V.Classical Negation in Logic Programs and Disjunctive Databases[J].New Generation Computing，1991（9）:365-385.

[5]Martin Gebser,Roland Kaminski,Benjamin Kaufmann,etal.A User’s Guide to gringo,clasp,clingo and iclingo[Z].