王 凡，范文斌，張雪艷，郭玉堂，劉樂群

（合肥師范學(xué)院 計算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230601）

提高回答集編程在家庭機(jī)器人仿真上求解效率初探

王 凡，范文斌，張雪艷，郭玉堂，劉樂群

（合肥師范學(xué)院 計算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230601）

家庭機(jī)器人仿真比賽是由中科大發(fā)起的一項(xiàng)基于簡單機(jī)器人模型在一定范圍內(nèi)實(shí)現(xiàn)任務(wù)規(guī)劃的比賽.Answer Set Programm ing（回答集編程）是一種非單調(diào)邏輯編程技術(shù)，是在融合邏輯編程理論基礎(chǔ)上發(fā)展而來的.獨(dú)創(chuàng)性的提出合并關(guān)聯(lián)原子動作來提高回答集編程的求解效率，并在家庭機(jī)器人仿真比賽中實(shí)現(xiàn)較高效率的自動規(guī)劃.

回答集編程；家庭機(jī)器人；行動規(guī)劃；邏輯推理

家庭機(jī)器人是在家庭環(huán)境下為為人類服務(wù)的一種機(jī)器人，能夠代替人類完成家庭中的各種繁重且重復(fù)的工作[1,2].家庭機(jī)器人仿真比賽是一項(xiàng)關(guān)于家庭機(jī)器人如何對給定的一系列任務(wù)進(jìn)行合理的規(guī)劃的問題的比賽，服務(wù)器會給出一組場景信息和任務(wù)信息，通過程序在規(guī)定的時間內(nèi)能算出一套最佳的動作序列，服務(wù)器對給出的動作序列進(jìn)行鑒定模擬，計算成績[3].

回答集編程（Answer Set Programming）技術(shù)是近年來比較流行的解決人工智能問題的一種非單調(diào)推理編程技術(shù)，已成為很多的研究者用于非單調(diào)推理的知識表示和推理的工具，經(jīng)過研究者們多年的工作積累，回答集編程理論方面己相對成熟，但是，其常例化窮舉的本質(zhì)使得其求解器的效率不是很高，影響其廣泛應(yīng)用[4].

本文就回答集編程效率不高的現(xiàn)狀，提出了利用合并關(guān)聯(lián)原子動作的方法來提高回答集編程的求解效率，并用編寫相應(yīng)代碼實(shí)現(xiàn)，最后設(shè)置一組對照實(shí)驗(yàn)證明其正確性與實(shí)用性.

1 簡介

1.1 Answer Set Programming

1.1.1 ASP基礎(chǔ)

在經(jīng)典邏輯中，我們經(jīng)?？紤]這樣一個推理：從前提“所有的人都是有死的”和“蘇格拉底是人”推出結(jié)論“蘇格拉底是有死的”.這樣的推理我們稱為演繹推理，然而在人們?nèi)粘５耐评碇?，給出的信息往往是不完全的，所以推理出的結(jié)論往往是可錯的，比如我們通常認(rèn)為“鳥會飛”，知道“twweety是一直鳥”的話就會推出結(jié)論“tweety會飛”.可是一旦我們增加前提“tweety是一只鴕鳥”，我們知道通?！傍r鳥是不會飛的”，則之前的結(jié)論“tweety會飛”就不合理了，即增加了前提使原先推出的結(jié)論推不出，也就是說，這樣的推理不具有單調(diào)性，我們稱這種性質(zhì)為非單調(diào)性，稱這樣的推理為非單調(diào)推理[5].

回答集編程（ASP）是語法上類似傳統(tǒng)邏輯編程而語義上密切于非單調(diào)邏輯的一種聲明式編程[5].邏輯程序和非單調(diào)推理兩個領(lǐng)域的交叉融合促使了回答集編程研究的產(chǎn)生.

1.1.2 ASP求解

ASP求解問題，只需要將問題本身描述出來，不需要關(guān)心使用何種算法，即先構(gòu)造問題的可能解，在刻畫約束解的條件，對問題表達(dá)為通用的問題描述部分和問題實(shí)例，這樣同一段問題描述的代碼可以處理不同的問題實(shí)例[4].ASP的求解過程分兩個步驟：

常例化（Grounding）：原始程序中可能含有變量或其他語法縮寫，將其常例化為僅含常規(guī)則的程序，并且解釋翻譯相應(yīng)的語法縮寫.

模型搜索（計算回答集）：計算常例化以后程序的回答集，一般采用搜索方式.

1.2 家庭機(jī)器人仿真比賽

家庭機(jī)器人仿真比賽針對自主機(jī)器人在家庭環(huán)境中的基本應(yīng)用來設(shè)置一系列問題，每一個問題由一個場景描述和一個任務(wù)描述組成，其中場景描述確定家庭環(huán)境的初始狀態(tài)，代表機(jī)器人通過感知器獲得的家庭環(huán)境信息；任務(wù)描述包含了用戶下達(dá)任務(wù)的詳細(xì)信息，代表用戶通過人機(jī)對話向機(jī)器人傳遞的各種信息[6].

1.2.1 原子動作

機(jī)器人原子動作，體現(xiàn)機(jī)器人的基本行動能力，是仿真平臺對機(jī)器人底層功能的抽象，機(jī)器人為原子動作的主體[3].規(guī)定，機(jī)器人只能根據(jù)這些原子動作來改變場景.

1.2.2 場景描述

場景描述是家庭機(jī)器人仿真平臺虛擬的一套環(huán)境，規(guī)定了在一個房間內(nèi)，某個位置擁有某個物體，例如：table(4).location(4,108).表示物體table的編號為4號，其位置為108.場景描述就是機(jī)器人在規(guī)劃前房間的初始狀態(tài).

1.2.3 任務(wù)描述

任務(wù)描述包括三個方面，第一為機(jī)器人需要完成的任務(wù)集，例如：puton(book,desk).give(human,blue book).表示機(jī)器人需要將一本書放在桌子上并且還要給人一本藍(lán)色的書；第二為對場景的補(bǔ)充，例如：near(yellow book,red cup).表示黃色的書在紅色的杯子邊上；第三為約束信息，例如：not onplate(red cup).表示機(jī)器人無論如何都不能將紅色的杯子放在盤子里.

2 ASP在家庭機(jī)器人仿真上的應(yīng)用

使用ASP編程來實(shí)現(xiàn)家庭仿真機(jī)器人行動序列的自動規(guī)劃，首先應(yīng)該對平臺給出的場景信息進(jìn)行解析存儲，然后對平臺給出的任務(wù)描述進(jìn)行解析，任務(wù)部分分為三大塊，分別為：任務(wù)、補(bǔ)充信息和約束，接下來將場景信息和任務(wù)描述進(jìn)行ASP常例化，最后用ASP進(jìn)行求解，流程圖如圖1：

利用ASP編程來實(shí)現(xiàn)家庭機(jī)器人仿真行動序列的自動規(guī)劃其核心就是如何使用回答集編程規(guī)則對問題進(jìn)行描述、對行為進(jìn)行描述的問題.下面將從這兩個方面進(jìn)行闡述.

圖1 用ASP求解家庭仿真流程圖

2.1 問題描述

在家庭仿真中，需要描述各物體及機(jī)器人的初始狀態(tài)和目標(biāo)狀態(tài)，將其轉(zhuǎn)化為ASP編碼，下面是對場景進(jìn)行初始化的回答集編程：

obj(A):-location(A,X).

loc(X):-location(A,X).

mylocation(A,X,0):-location(A,X).

hasloc(A):-location(A,X).

myplate(A,0):-plate(A),loc(X),obj(A).

myhold(A,0):-hold(A),loc(X),obj(A).

2.2 行為描述

在行為描述階段也要定義相關(guān)謂詞來表示機(jī)器人的原子行為以及相應(yīng)的動作序列，下面是機(jī)器人執(zhí)行動作open（A）的回答集編程：

mydooropen(A,t):-occurs(open(A),t),bigobject (A).

:-occurs(open(A),t),not myhold(0,t-1), bigobject(A).

:-occurs(open(A),t),not mydoorclosed(A, t-1),bigobject(A).

3 利用合并關(guān)聯(lián)原子動作提高ASP求解效率

3.1 ASP求解算法

ASP求解的過程就是常例化窮舉的過程，圖2描述一個典型的ASP求解空間樹，圖中0表示初始狀態(tài)，1表示動作move（X），2表示動作pickup（A），3表示動作open（A），4表示動作putdon（A），則若使用ASP求解，則必須將所有葉節(jié)點(diǎn)進(jìn)行掃描，從而找出最優(yōu)序列，其時間復(fù)雜度為O（2n），很顯然，ASP的求解效率不是很高[8].

圖2 ASP求解空間樹

3.2 改進(jìn)的ASP求解算法

為了提高ASP求解效率，可以將機(jī)器人的原子動作中相關(guān)聯(lián)的某些原子動作進(jìn)行合并，以減少求解器的搜索樹空間.例如：家庭機(jī)器人仿真比賽的規(guī)則中指出，對于任務(wù)putin（A，B）規(guī)定，機(jī)器人必須將小物體A放入到帶有門的大物體B中，并且B的門必須是關(guān)著的[3]，由此可知，機(jī)器人要想將A物體放入到B物體中，就必須執(zhí)行putin（A，B），但又根據(jù)B物體的門必須是關(guān)著的，所以，機(jī)器人又必須執(zhí)行close（B），并且根據(jù)經(jīng)驗(yàn)得知，機(jī)器人執(zhí)行完putin（A，B）后往往都要執(zhí)行close（B），所以就將這兩個原子動作復(fù)合為一個動作piclo（A），相應(yīng)的ASP編程如下：

action(piclo(A),t):-action(putin(A,X),t),action (close(X),t+1).

同理也可以將move（X）和pickup（A）復(fù)合為動作mtop（A）等，部分復(fù)合動作的ASP編程如下：

action(mtop(A),t):-action(move(X),t),action (pickup(A),t+1).

action(mfrp(A),t):-action(move(X),t),action (fromplate(A),t+1).

通過將合并關(guān)聯(lián)原子動作，可以將ASP的搜索空間樹進(jìn)行大量剪枝，使其時間復(fù)雜度下降20-30個百分點(diǎn)，大大提高了ASP的求解效率.

4 實(shí)驗(yàn)分析

為了測試改進(jìn)后的ASP求解的效果，設(shè)置一組對照實(shí)驗(yàn)，實(shí)驗(yàn)選取2012年中國服務(wù)機(jī)器人大賽的家庭仿真組比賽平臺（Planner-1.30）和測試題目（從中選取2個環(huán)境場景，對每個場景隨機(jī)選取2組任務(wù)）進(jìn)行測試（平臺服務(wù)器會根據(jù)規(guī)劃器的動作序列綜合考慮為每組測試題計算出最后得分）[7].A組實(shí)驗(yàn)為基于簡單策略求解，B組實(shí)驗(yàn)為未經(jīng)處理的ASP求解，C組試驗(yàn)為合并原子動作后ASP求解.

實(shí)驗(yàn)結(jié)果如表1所示：

表1 對比實(shí)驗(yàn)結(jié)果表

通過表4，可以看到，基于簡單ASP的求解在時間上要高于基于簡單策略的求解，即簡單ASP的效率要比簡單策略低，但是基于ASP求解最后的得分要遠(yuǎn)遠(yuǎn)大于基于簡單策略的求解；同時也可以看到，C組在規(guī)定的時間內(nèi)能完成的任務(wù)要多于B組且C組的求解效率要遠(yuǎn)遠(yuǎn)高于B組的求解效率，這證明，采用合并關(guān)聯(lián)原子動作的方法確實(shí)能提高ASP的求解效率.

5 結(jié)束語

實(shí)驗(yàn)證明，ASP能規(guī)劃出家庭仿真機(jī)器人最優(yōu)的行動序列，同時也證明了我們提出的合并關(guān)聯(lián)原子動作的方法能有效提高ASP的求解效率.ASP方式靈活、方法可靠、程序可擴(kuò)展性好，當(dāng)場景中物品描述形式或機(jī)器人原子動作有所變化，只用相應(yīng)地修改ASP規(guī)則即可.雖然其常列化窮舉的本質(zhì)嚴(yán)重制約了其求解效率[6]，但是在合并了關(guān)聯(lián)原子動作后，ASP求解成功率在可接受的響應(yīng)時間內(nèi)提高13-17個百分點(diǎn).但是，目前還無法從本質(zhì)上解決其效率低的問題，所以，未來的主要方向是如何盡可能的提高ASP求解效率.

〔1〕田國會,李曉磊,趙守鵬,路飛.家庭服務(wù)機(jī)器人智能空間技術(shù)研究與進(jìn)展[J].山東大學(xué)學(xué)報(工學(xué)版),2007,37(5):53-59.

〔2〕田國會.家庭服務(wù)機(jī)器人研究前景廣闊[J].國際學(xué)術(shù)動態(tài),2007（1）:28-29.

〔3〕@HomeSimulation.USTC[EB/OL].http://www. w righteagle.org/homesimulation.[2012-4-23].

〔4〕Apt K,Bol R.Logic programm ing and negation: A survey[J].The Journal of Logic Programming, 1994,19/20:9-71.

〔5〕ZHENG X G J.Multi-agent based hybrid evolutionary algo-rithm [J].Natural Computation, 2011(2):1106-1110.

〔6〕吉建民,陳小平.一種支持個性化協(xié)調(diào)的服務(wù)機(jī)器人體系結(jié)構(gòu)[J].南京大學(xué)學(xué)報（自然科學(xué)版）, 2010,46(2):131-139.

〔7〕Pedro Cabalar,Paolo Ferraris.Propositional theories are strongly equivalent to logic programs[J]. Theory and Practice of Logic Programming, 2007,6:745-759.

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

TP181

A

1673-260X（2014）03-0019-03

安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目（KJ2013A217），合肥師范學(xué)院2013本科教學(xué)質(zhì)量提升計劃（2013zyzh01），國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目（201314098016）