家庭仿真求解最優(yōu)路徑問題算法研究

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

0 引言

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

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

1 關(guān)于最優(yōu)化問題

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

2 求解最優(yōu)路徑問題

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

2.1 最優(yōu)策略算法

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

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

①假設(shè)場景文件中有如下描述：

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

任務(wù)文件中有如下要求：

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

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

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

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

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

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

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

在任務(wù)文件中有如下要求：

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

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

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

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

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

2.2 回答集編程

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

2.2.2 回答集編程求解 在自然語言比賽項目中，特定指令通過語言理解部件被轉(zhuǎn)換為內(nèi)部邏輯公式，此過程中需要借助常例化工具Grounder，[5]任務(wù)規(guī)劃部件將這些公式作為事實直接添加到ASP程序中，形成必須滿足的目標狀態(tài)?；卮鸺幊坛绦虻那蠼鈱嶋H上相當于通過經(jīng)典規(guī)劃方式，得到最優(yōu)化行動序列。接下來舉例說明使用回答集編程進行描述的3個基本步驟。[5]

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

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

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

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

第三步：定義在約束中出現(xiàn)的輔助謂詞。

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

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

第一種是從描述規(guī)劃問題角度優(yōu)化。

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

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

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

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

3 總結(jié)

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

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

[2]吉建民，陳小平，姜節(jié)匯，等.一種支持個性化協(xié)調(diào)的服務(wù)機器人體系結(jié)構(gòu)[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].