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

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

（合肥師范學院 計算機科學與技術系，安徽 合肥 230601）

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

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

（合肥師范學院 計算機科學與技術系，安徽 合肥 230601）

家庭機器人仿真比賽是由中科大發起的一項基于簡單機器人模型在一定范圍內實現任務規劃的比賽.Answer Set Programm ing（回答集編程）是一種非單調邏輯編程技術，是在融合邏輯編程理論基礎上發展而來的.獨創性的提出合并關聯原子動作來提高回答集編程的求解效率，并在家庭機器人仿真比賽中實現較高效率的自動規劃.

回答集編程；家庭機器人；行動規劃；邏輯推理

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

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

本文就回答集編程效率不高的現狀，提出了利用合并關聯原子動作的方法來提高回答集編程的求解效率，并用編寫相應代碼實現，最后設置一組對照實驗證明其正確性與實用性.

1 簡介

1.1 Answer Set Programming

1.1.1 ASP基礎

在經典邏輯中，我們經常考慮這樣一個推理：從前提“所有的人都是有死的”和“蘇格拉底是人”推出結論“蘇格拉底是有死的”.這樣的推理我們稱為演繹推理，然而在人們日常的推理中，給出的信息往往是不完全的，所以推理出的結論往往是可錯的，比如我們通常認為“鳥會飛”，知道“twweety是一直鳥”的話就會推出結論“tweety會飛”.可是一旦我們增加前提“tweety是一只鴕鳥”，我們知道通常“鴕鳥是不會飛的”，則之前的結論“tweety會飛”就不合理了，即增加了前提使原先推出的結論推不出，也就是說，這樣的推理不具有單調性，我們稱這種性質為非單調性，稱這樣的推理為非單調推理[5].

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

1.1.2 ASP求解

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

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

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

1.2 家庭機器人仿真比賽

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

1.2.1 原子動作

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

1.2.2 場景描述

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

1.2.3 任務描述

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

2 ASP在家庭機器人仿真上的應用

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

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

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

2.1 問題描述

在家庭仿真中，需要描述各物體及機器人的初始狀態和目標狀態，將其轉化為ASP編碼，下面是對場景進行初始化的回答集編程：

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 行為描述

在行為描述階段也要定義相關謂詞來表示機器人的原子行為以及相應的動作序列，下面是機器人執行動作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 利用合并關聯原子動作提高ASP求解效率

3.1 ASP求解算法

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

圖2 ASP求解空間樹

3.2 改進的ASP求解算法

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

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

同理也可以將move（X）和pickup（A）復合為動作mtop（A）等，部分復合動作的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).

通過將合并關聯原子動作，可以將ASP的搜索空間樹進行大量剪枝，使其時間復雜度下降20-30個百分點，大大提高了ASP的求解效率.

4 實驗分析

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

實驗結果如表1所示：

表1 對比實驗結果表

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

5 結束語

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

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

〔2〕田國會.家庭服務機器人研究前景廣闊[J].國際學術動態,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〕吉建民,陳小平.一種支持個性化協調的服務機器人體系結構[J].南京大學學報（自然科學版）, 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效率的若干途徑及服務機器人上應用[D].合肥:中國科學技術大學，2010.

TP181

A

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

安徽省高校自然科學研究重點項目（KJ2013A217），合肥師范學院2013本科教學質量提升計劃（2013zyzh01），國家級大學生創新創業訓練項目（201314098016）