劉巖愷 薛毅 （天津師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院 天津 300387）

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

③假如場(chǎng)景中有如下描述：

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

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

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

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

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

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

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

2.2 回答集編程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

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

[2]吉建民，陳小平，姜節(jié)匯，等.一種支持個(gè)性化協(xié)調(diào)的服務(wù)機(jī)器人體系結(jié)構(gòu)[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，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].