李月光，尹 東，張 榮

?

一種導(dǎo)覽機器人的任務(wù)規(guī)劃方法研究

李月光，尹 東，張 榮

(中國科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院，合肥 230027)

為導(dǎo)覽機器人實現(xiàn)服務(wù)目標(biāo)的引導(dǎo)規(guī)劃，提出一種以機器人操作系統(tǒng)為實驗平臺，結(jié)合馬爾科夫決策過程和微重啟技術(shù)的任務(wù)規(guī)劃方法。該方法在全面考慮服務(wù)對象身份需求信息及服務(wù)過程的總代價后，利用馬爾科夫決策模型確立最優(yōu)執(zhí)行方案。采用基于機器人分布式操作系統(tǒng)建立的微重啟自我修復(fù)機制解決功能失效問題。仿真結(jié)果驗證了該規(guī)劃方案在執(zhí)行導(dǎo)覽任務(wù)中的有效性，同時表明微重啟技術(shù)在處理功能失效問題時相對于傳統(tǒng)處理方法具有優(yōu)越性，其在隨機附加障礙的情況下可獲得91.03%的規(guī)劃成功率。

導(dǎo)覽機器人；操作系統(tǒng)；馬爾科夫決策過程；任務(wù)規(guī)劃；微重啟；馬爾科夫決策模型

1 概述

近年來包括導(dǎo)覽機器人、家庭服務(wù)機器人、醫(yī)療型機器人等在內(nèi)的多種服務(wù)機器人得到了迅速的發(fā)展，很多博物館、科技館已經(jīng)可以見到導(dǎo)覽機器人的身影。在實際應(yīng)用中導(dǎo)覽機器人面臨如下問題：(1)能否實現(xiàn)導(dǎo)覽任務(wù)，即功能設(shè)計的合理性；(2)能否對異常情況進行處理，即安全穩(wěn)定性；(3)執(zhí)行速度能否達到要求，即高效實用性。這些都是任務(wù)規(guī)劃所要解決的問題，因此，研究導(dǎo)覽機器人的任務(wù)規(guī)劃具有重大的意義。

作為機器人功能實現(xiàn)的重要環(huán)節(jié)，很多學(xué)者從不同角度研究了機器人任務(wù)規(guī)劃的方法。常用的注重人機互動的任務(wù)規(guī)劃方法有：將機器人與人分享同一套描述環(huán)境的符號集模型，如文獻[1-2]提出了多層次交互式任務(wù)規(guī)劃，解決了使用符號集進行人機交互效率較低的問題。文獻[3]提出了一種模仿人類意識的規(guī)劃框架，使得人機交互更加安全合理。實現(xiàn)實時處理隨機問題的規(guī)劃方法有馬爾科夫決策理論，文獻[4-5]研究了馬爾科夫決策模型在機器人規(guī)劃上的應(yīng)用。改變描述空間環(huán)境的方式也是任務(wù)規(guī)劃的研究重點。傳統(tǒng)的描述方法有度量地圖[6]及拓撲地圖[7]，文獻[8]結(jié)合兩者優(yōu)點提出了混合地圖，文獻[9]介紹了語義地圖描述方法，文獻[10]將語義地圖用在任務(wù)規(guī)劃中取得了很好的效果。針對規(guī)劃速度的問題，文獻[11]提出了一種用超圖的鄰接矩陣求解狀態(tài)之間可達關(guān)系的方法，簡化了規(guī)劃過程，提高了求解效率。

本文主要研究導(dǎo)覽機器人在中國科學(xué)技術(shù)大學(xué)校史館實現(xiàn)引導(dǎo)講解服務(wù)的任務(wù)規(guī)劃設(shè)計。規(guī)劃決策的關(guān)注點是高層規(guī)劃，提出一種具有一定普適性的解決方案。該方案在其他的導(dǎo)覽場景，如醫(yī)院、銀行、博物館都可以使用，它囊括從機器人服務(wù)對象的選取到任務(wù)序列的生成，再到異常情況的處理，整個服務(wù)過程的設(shè)計方法。

2 導(dǎo)覽任務(wù)功能結(jié)構(gòu)設(shè)計

任務(wù)規(guī)劃是一種重要的問題求解技術(shù)，它從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得狀態(tài)為止[12]。因此，對任何機器人的規(guī)劃都不能脫離機器人的功能本身，就本文來說設(shè)計一個能夠?qū)崿F(xiàn)導(dǎo)覽任務(wù)的總體結(jié)構(gòu)，并確定該結(jié)構(gòu)中各個功能模塊間的聯(lián)系是任務(wù)規(guī)劃的第一步。

2.1 基于機器人操作系統(tǒng)的功能結(jié)構(gòu)設(shè)計

本文的導(dǎo)覽機器人采用的是機器人操作系統(tǒng)(ROS)分布式通信系統(tǒng)。這里的分布式通信系統(tǒng)是指系統(tǒng)中各個模塊的運行方式是以節(jié)點形式相對獨立的運行，當(dāng)每個節(jié)點運行完成后其結(jié)果由通信機制整合到一起。這種工作方式可以分解簡化問題，提高效率。ROS系統(tǒng)中節(jié)點與核心或者節(jié)點之間的通信是通過話題與服務(wù)實現(xiàn)的，該實現(xiàn)過程由通信核心(即內(nèi)核)通過啟動節(jié)點rosout收集其運行的調(diào)試信息，進行全程的監(jiān)督管理。根據(jù)ROS系統(tǒng)結(jié)構(gòu)，將導(dǎo)覽任務(wù)細分，設(shè)計的功能結(jié)構(gòu)如圖1所示。

圖1 功能結(jié)構(gòu)

導(dǎo)覽任務(wù)分為3個部分：人機信息交互模塊，導(dǎo)航模塊，運動控制模塊。這3個功能模塊構(gòu)成系統(tǒng)的二級節(jié)點，其中每個模塊又有各自的任務(wù)子節(jié)點。他們之間的通信方式是這樣設(shè)計的：節(jié)點4和節(jié)點5在運行結(jié)束時會以話題的形式向核心發(fā)布運行結(jié)果，同時節(jié)點1向核心訂閱這個話題(任何節(jié)點都可以訂閱)信息，該信息的傳遞由節(jié)點rostopic控制，并參與到節(jié)點1的功能實現(xiàn)。節(jié)點2和節(jié)點3在運行時向核心提出服務(wù)要求，此時滿足條件的節(jié)點5、節(jié)點7及節(jié)點8、節(jié)點9將會分別啟動應(yīng)答。最終當(dāng)所有節(jié)點的功能都實現(xiàn)完畢，則整體任務(wù)完成。

2.2 基于微重啟技術(shù)的自愈結(jié)構(gòu)設(shè)計

微重啟技術(shù)本質(zhì)是一種自下至上的遞歸重啟策略[13]。首先重啟功能失效的節(jié)點及其直接下游節(jié)點，如果依然無法解決該失效問題，則把此節(jié)點所在的直接上游進行重啟。若問題依然存在，則繼續(xù)遞歸直至功能實現(xiàn)。涉及到的重啟規(guī)則定義如下[14]：

(1)若的執(zhí)行依賴，即A是的上游節(jié)點，則。

(5)若和共享數(shù)據(jù)或狀態(tài)，則。

根據(jù)本文的功能結(jié)構(gòu)，微重啟自愈結(jié)構(gòu)設(shè)計如圖2所示。

圖2 自愈結(jié)構(gòu)設(shè)計

本文關(guān)注的是高層規(guī)劃，因此，將整個系統(tǒng)結(jié)構(gòu)分為 3層，但為了便于底層實現(xiàn)及后續(xù)功能的擴展，將任務(wù)層做了進一步的細分。以圖2所示的結(jié)構(gòu)為例，假設(shè)要恢復(fù)系統(tǒng)中一個已發(fā)生故障的節(jié)點，如動作控制，實際上是恢復(fù)其本身及可能引起該故障的所有下游節(jié)點，即面部動作及軀干動作。若無法解決問題，那么系統(tǒng)將推斷節(jié)點功能的失效可能是由其上游節(jié)點發(fā)生故障而傳播過來的，這時將以遞歸的方式恢復(fù)上游節(jié)點運動控制，如此進行循環(huán)重啟直至問題解決。對于數(shù)據(jù)或狀態(tài)相互依賴的情況，如全局路徑規(guī)劃和局部路徑規(guī)劃，系統(tǒng)將在重啟過程中監(jiān)聽該數(shù)據(jù)或狀態(tài)來判定共享項是否需要被重啟。

3 導(dǎo)覽任務(wù)規(guī)劃模型設(shè)計

3.1 馬爾科夫決策過程

馬爾科夫過程由俄羅斯數(shù)學(xué)家馬爾科夫于1907年提出，它是一種無后效性的過程，即下一時刻的結(jié)果僅依賴于當(dāng)前時刻，而與以前的結(jié)果無關(guān)。這種忽略歷史的影響，無需不斷地保存歷史信息的特性已被廣泛應(yīng)用于多個領(lǐng)域。馬爾科夫決策過程是馬爾科夫過程在機器人上的一種應(yīng)用。

圖3 狀態(tài)轉(zhuǎn)移過程

最終得到的最優(yōu)策略即為最佳的行動序列。

3.2 基于MDP的規(guī)劃模型

表1 狀態(tài)集合

表2 動作集合

4 仿真結(jié)果及分析

實驗前期準(zhǔn)備共邀請了20位志愿者，其中18人包括臉譜信息在內(nèi)的多個信息將被錄入數(shù)據(jù)庫，2位作為首次訪問者參與本實驗。實驗開始時隨機數(shù)量的人將出現(xiàn)在機器人面前等待服務(wù)，機器人將根據(jù)識別的結(jié)果結(jié)合決策模型找到一個最優(yōu)的執(zhí)行序列，同時微重啟結(jié)構(gòu)將監(jiān)督動作的執(zhí)行，最終完成導(dǎo)覽目標(biāo)。下面將選取一個例子展示本文工作。

圖4 視覺模塊獲取信息實例

圖5 包含任務(wù)信息的平面圖

表3 最優(yōu)實際執(zhí)行序列

實際行動序列為：

為了驗證微重啟技術(shù)在本次規(guī)劃中的恢復(fù)性能，在每個規(guī)劃的過程中隨機添加了引起任務(wù)失敗的障礙。由于不同模塊重啟耗時不同，因此采用重啟的節(jié)點個數(shù)來描述恢復(fù)過程的執(zhí)行復(fù)雜度。針對移動失效和識別失效這2類問題，實驗包括微重啟和宏重啟(即重啟整個錯誤模塊)在內(nèi)各進行了4組，每組50次。實驗結(jié)果如圖6所示。

從圖6中可以看出，由于障礙是隨機添加的，不同性質(zhì)的障礙恢復(fù)復(fù)雜度不同，因此曲線有所波動。移動功能的失效因為其設(shè)計的復(fù)雜度要高于識別功能，所以總體恢復(fù)代價高。對于相同的問題，微重啟在執(zhí)行效率上要明顯高于宏重啟，且隨著處理次數(shù)的增多差距逐漸加大。

最后，整個規(guī)劃實驗包括多人及單人的情況，共進行了145組，規(guī)劃達到預(yù)期目標(biāo)的成功率為91.03%(132/145)，錯誤主要集中在視覺模塊性能的局限性，導(dǎo)致服務(wù)信息不準(zhǔn)確，以及障礙過多，使得系統(tǒng)長時間停留在系統(tǒng)層重啟。

5 結(jié)束語

本文探討了整個規(guī)劃系統(tǒng)的構(gòu)建方法，提出了基于馬爾科夫決策模型和微重啟技術(shù)的決策方案。該方案通過計算折算累積回報找到最優(yōu)策略，同時監(jiān)督單元監(jiān)聽該策略的執(zhí)行情況，并結(jié)合微重啟技術(shù)確保每次的狀態(tài)轉(zhuǎn)移都是預(yù)期的。通過實驗可以看出，雖然該方案降低了馬爾科夫決策處理不確定問題的能力，但依然不失為一種有效的規(guī)劃方法。本文的研究重點在高層規(guī)劃，但是底層實現(xiàn)的精度對規(guī)劃結(jié)果有很大的影響，根據(jù)機器人實際運行情況后續(xù)還有大量調(diào)試工作。在實際應(yīng)用中為觀測到全部信息的代價很大，因此，采用部分可觀察的馬爾科夫決策模型是一個較好的改進方向。

[1] Dillmann R, Zoellner R, Ehrenmann M. Interactive Natural Programming of Robots: Introductory Overview[C]//Proc. of IEEE-RAS Joint Workshop on Technical Challenge for Dependable Robots in Human Environments. Tolouse, France: [s. n.], 2002: 253-258.

[2] Galindo C, Madrigal F J A. Multihierarchical Interactive Task Planning: Application to Mobile Robotics[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2008, 38(3): 785-798.

[3] Sisbot E A. A Human-aware Manipulation Planner[J]. IEEE Transactions on Robotics, 2012, 28(5): 1045-1057.

[4] 石 軻. 基于馬爾可夫決策過程理論的Agent決策問題研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué), 2008.

[5] 范長杰. 基于馬爾可夫決策理論的規(guī)劃問題的研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué), 2010.

[6] Thrun S, Fox D, Burgard W. Probabilistic Mapping of an Environment by a Mobile Robot[C]//Proc. of IEEE Interna- tional Conference on Robotics and Automation. [S. l.]: IEEE Press, 1998: 1546-1551.

[7] Choset H, Nagatani K. Topological Simultaneous Localization and Mapping(SLAM): Toward Exact Localization Without Explicit Localization[J]. IEEE Transactions on Robotics and Automation, 2001, 17(2): 125-137.

[8] Buschka P, Saffiotti A. Some Notes on the Use of Hybrid Maps for Mobile Robots[C]//Proc. of the 8th International Conference on Intelligent Autonomous Systems. Amsterdam, the Netherlands: [s. n.], 2004: 547-556.

[9] 莊 磊. 智能移動機器人地圖描述和導(dǎo)航方法研究[D]. 南京: 南京理工大學(xué), 2011.

[10] Galindoa G, Madrigala J A F, Saffiotti A. Robot Task Planning Using Semantic Maps[J]. Robotics and Autonomous Systems, 2008, 56(11): 955-966.

[11] 文中華, 黃 巍, 劉任任, 等. 模型檢測規(guī)劃中的狀態(tài)之間的可達關(guān)系研究[J]. 計算機學(xué)報, 2012, 35(8): 1635-1643.

[12] 蔡自興. 機器人學(xué)[M]. 2版. 北京: 清華大學(xué)出版社, 2009.

[13] Shi Changting, Zhang Rubo, Zhao Jing. Software Self-recovery Method of AUV Based on Micro-reboot[C]//Proc. of the 9th World Congress on Intelligent Control and Automation. [S. l.]: IEEE Press, 2011: 91-96.

[14] Shi Changting. Layered Self-healing Software Architecture of AUV Based on Micro-reboot[C]//Proc. of International Workshop on Intelligent Systems and Applications. [S. l.]: IEEE Press, 2009: 1951-1954.

編輯 顧逸斐

Study on a Task Planning Method for Tour Guide Robot

LI Yue-guang, YIN Dong, ZHANG Rong

(School of Information Science and Technology, University of Science and Technology of China,Hefei 230027, China)

Towards the planning problem of robot for guiding service objects, Robot Operating System(ROS) as experimental platform, combined with Markov Decision Process(MDP) and micro-reboot technology, this paper presents a robot task planning scheme suitable for guide service. After considering comprehensive service object identity information and total cost of service process, the scheme establishes optimal execution plan using MDP model. And based on the ROS distributed system, the scheme uses micro-reboot self-repairing mechanism to solve the functional failure problem. The simulation results show that the proposal is effective in the implementation of navigation mission. Compared with the traditional processing method, it shows the advantages of micro-reboot technology in dealing with functional failures. The planning scheme gets 91.03% success rate in the case of additional barriers randomly.

tour guide robot;operating system; Markov Decision Process(MDP); task planning; micro-reboot; Markov decision model

1000-3428(2014)03-0196-05

A

TP18

中國科學(xué)技術(shù)大學(xué)重要方向培育基金資助項目“機器人智能交互、柔性機械與高性能樣機研制”。

李月光(1987－)，男，碩士，主研方向：機器人任務(wù)規(guī)劃，機器視覺；尹 東、張 榮，副教授。

2012-12-19

2013-04-02 E-mail：lyg@mail.ustc.edu.cn

10.3969/j.issn.1000-3428.2014.03.041