一種導覽機器人的任務規劃方法研究

李月光，尹 東，張 榮

?

一種導覽機器人的任務規劃方法研究

李月光，尹 東，張 榮

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

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

導覽機器人；操作系統；馬爾科夫決策過程；任務規劃；微重啟；馬爾科夫決策模型

1 概述

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

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

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

2 導覽任務功能結構設計

任務規劃是一種重要的問題求解技術，它從某個特定的問題狀態出發，尋求一系列行為動作，并建立一個操作序列，直到求得狀態為止[12]。因此，對任何機器人的規劃都不能脫離機器人的功能本身，就本文來說設計一個能夠實現導覽任務的總體結構，并確定該結構中各個功能模塊間的聯系是任務規劃的第一步。

2.1 基于機器人操作系統的功能結構設計

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

圖1 功能結構

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

2.2 基于微重啟技術的自愈結構設計

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

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

(5)若和共享數據或狀態，則。

根據本文的功能結構，微重啟自愈結構設計如圖2所示。

圖2 自愈結構設計

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

3 導覽任務規劃模型設計

3.1 馬爾科夫決策過程

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

圖3 狀態轉移過程

最終得到的最優策略即為最佳的行動序列。

3.2 基于MDP的規劃模型

表1 狀態集合

表2 動作集合

4 仿真結果及分析

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

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

圖5 包含任務信息的平面圖

表3 最優實際執行序列

實際行動序列為：

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

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

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

5 結束語

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

[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]. 合肥: 中國科學技術大學, 2008.

[5] 范長杰. 基于馬爾可夫決策理論的規劃問題的研究[D]. 合肥: 中國科學技術大學, 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]. 南京: 南京理工大學, 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] 文中華, 黃 巍, 劉任任, 等. 模型檢測規劃中的狀態之間的可達關系研究[J]. 計算機學報, 2012, 35(8): 1635-1643.

[12] 蔡自興. 機器人學[M]. 2版. 北京: 清華大學出版社, 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

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

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

2012-12-19

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

10.3969/j.issn.1000-3428.2014.03.041