基于Petri網(wǎng)的多線程技術(shù)在機器人編隊中的應(yīng)用

劉曉程　王武

摘 要：傳統(tǒng)的單機器人難以適應(yīng)復雜的任務(wù)以及靈活多變的環(huán)境，因此多機器人的研究受到越來越多的關(guān)注。結(jié)合多線程技術(shù)為機器人編隊建立Petri網(wǎng)模型，運用Petri網(wǎng)模型對系統(tǒng)各線程對共享區(qū)資源的獨占性存取，線程之間同步協(xié)作進行模擬分析，提出機器人編隊的多線程軟件解決方案。

關(guān)鍵詞：機器人編隊 多線程技術(shù) Petri網(wǎng) 解決方案

中圖分類號：TP242 文獻標識碼：A 文章編號：1007-3973（2013）006-047-02

1 引言

多機器人編隊以其能夠更加有效、準確的獲取環(huán)境信息，提高工作效率，增加系統(tǒng)魯棒性等優(yōu)點成為機器人研究領(lǐng)域中的一個熱點。編隊成員之間通過加速度計、里程計、電子羅盤等傳感器收集自身位姿信息實現(xiàn)自身定位，結(jié)合超聲波、視覺等感知型傳感器獲得周圍環(huán)境信息，采用無線組網(wǎng)的方式將個體的位置與環(huán)境信息在群體內(nèi)共享并計算機器人之間的相對位置實現(xiàn)機器人編隊。

編隊移動過程中對系統(tǒng)實時性要求較高，常需要多個任務(wù)并行運行，常規(guī)的軟件設(shè)計方案難以滿足要求，本文結(jié)合多線程技術(shù)為機器人編隊的軟件設(shè)計方案提供參考。引入多線程技術(shù)之后，由線程并發(fā)運行所造成的非確定性使得系統(tǒng)變得更加復雜，協(xié)調(diào)線程以配合完成系統(tǒng)控制任務(wù)、對共享區(qū)數(shù)據(jù)的訪問進行限制等問題使常規(guī)的系統(tǒng)設(shè)計方法難以滿足要求。Petri網(wǎng)理論是一種直接易用的系統(tǒng)建模工具，具有嚴格的數(shù)學定義，對具有并發(fā)行為的系統(tǒng)能夠合理描述，對系統(tǒng)的運行過程能夠直觀的模擬。結(jié)合多線程技術(shù)為機器人編隊建立Petri網(wǎng)模型，利用模型對機器人編隊中的多線程的運行做模擬分析，提出機器人編隊的多線程軟件解決方案。

2 多線程技術(shù)在機器人編隊中的設(shè)計與實現(xiàn)

多線程技術(shù)可以通過時分輪轉(zhuǎn)調(diào)度算法在單片機中實現(xiàn)。每個活動的線程輪流使用CPU，每個線程占用CPU的一個時間片，CPU在多個線程間快速切換，宏觀上表現(xiàn)為多個線程同時執(zhí)行。本文將機器人編隊劃分為多個進程：主進程，獲取任務(wù)命令進程，機器人間的通訊進程，進程中包含多個線程。本文所選的主控芯片為Freescale Kinetis系列，采用ARM Cortex-M4內(nèi)核，處理速度快，外設(shè)接口豐富，能夠較好的滿足本設(shè)計的要求。

主進程利用周期中斷定時器產(chǎn)生時間片用于線程切換。時間片的長短根據(jù)各個線程的執(zhí)行時間和各任務(wù)的響應(yīng)要求來綜合考慮。主進程中包含的線程有：獲取機器人自身姿態(tài)線程、實現(xiàn)自身定位線程、實現(xiàn)機器人移動線程等。

獲取任務(wù)命令進程根據(jù)任務(wù)要求創(chuàng)建。機器人進行通信獲取任務(wù)，根據(jù)目標任務(wù)的要求激活相應(yīng)的子線程。若沒有接到任務(wù)命令，則不執(zhí)行本進程。

機器人之間的通訊進程采用外部中斷服務(wù)函數(shù)實現(xiàn)。當收到外部通信中斷請求，或者本機對外通訊的中斷請求時創(chuàng)建激活本進程。若沒有接到通信中斷請求，則不執(zhí)行本進程。

3 機器人編隊的多線程Petri網(wǎng)模型

本文主要研究的是帶禁止弧的時間Petri網(wǎng)，該Petri網(wǎng)的定義請參考文獻[2]，本文不做過多的描述。

用位置表示進程、線程和與此有關(guān)的工作狀態(tài)，用變遷表示進程、線程的執(zhí)行以及與此有關(guān)的工作過程，結(jié)合多線程技術(shù)為機器人編隊建立Petri網(wǎng)模型，如圖1所示。圖中各標號相同的位置表示同一位置。表1是各主要位置和變遷實施的具體含義。

在主進程中主要包含獲取機器人自身姿態(tài)線程、實現(xiàn)自身定位線程、實現(xiàn)機器人移動線程（T0→T15）。每個線程能夠執(zhí)行應(yīng)同時滿足：輪巡的時間片到達、線程是活動的。例如在圖1中實現(xiàn)機器人自定位線程的啟動除了要等待時間片輪巡到P8，即等待所有傳感器信息采集完畢，還需要系統(tǒng)對自定位線程的使能，使T5具有發(fā)生權(quán)，P7得到令牌。T11為獲取命令進程的變遷節(jié)，只有當系統(tǒng)處于任務(wù)等待狀態(tài)且收到任務(wù)命令時才創(chuàng)建并執(zhí)行。

機器人之間的通訊進程包含數(shù)據(jù)的接收線程與發(fā)送線程。每個線程在運行的過程中需要調(diào)用全局變量，如果一個線程訪問并修改全局變量時，另一個線程啟動并訪問該變量，此時該變量的值將變得不確定，給系統(tǒng)帶來安全隱患，因此需要對線程進行互鎖。將所有線程需要訪問的全局變量存放在一個共享區(qū)進行共享。圖1中P11位置表示對訪問共享區(qū)的線程進行互鎖，只允許T9，T33，T16變遷中有且僅有一個線程對共享區(qū)進行訪問，一個變遷節(jié)使能將使其他變遷節(jié)不能發(fā)生。圖1中T18→T27表示數(shù)據(jù)發(fā)送子線程將數(shù)據(jù)以隊列的形式進行傳送。P28→T25的權(quán)值為3，即需要數(shù)據(jù)隊列準備完畢才能開始建立連接。P28想要獲得令牌，取決于變遷T22，T23，T24的引發(fā)，而這三個變遷的引發(fā)是相互競爭沖突的。本文引入禁止弧P25→T23和P26→T24可以使這三個變遷獲得T22的優(yōu)先級高于T23，T23的優(yōu)先級高于T24的引發(fā)次序，從而確保數(shù)據(jù)隊列的正確建立。

圖1 機器人編隊的多線程時間Petri網(wǎng)模型

表1 圖1 Petri網(wǎng)中主要位置和變遷節(jié)的含義

4 機器人編隊的多線程軟件解決方案探討

機器人編隊中進程、線程之間的同步協(xié)作、對共享區(qū)資源的獨占性存取、線程的啟動與結(jié)束等方面的問題在上文中的Petri網(wǎng)模型均有體現(xiàn)。通過該模型的模擬運行，可以直觀的了解各進程、線程之間工作流程中執(zhí)行順序、并發(fā)、競爭沖突以及同步關(guān)系。以此為基礎(chǔ)，針對機器人編隊中多線程的實現(xiàn)提出軟件設(shè)計方案。

線程優(yōu)先級的設(shè)置以及調(diào)用通過函數(shù)ThreadScheduler實現(xiàn)。程序上通過switch-case與break結(jié)合，識別線程編號priority_num。優(yōu)先級的設(shè)置通過case語句的排列順序?qū)崿F(xiàn)，優(yōu)先級較高的排列靠前。線程的調(diào)用由線程編號決定，只有priority_num為某個線程的編號時，該線程才啟動，實現(xiàn)時間片在多個線程之間的輪巡。

主進程中線程的啟動在中斷定時器PIT0中實現(xiàn)，劃分時間片長度為20ms（根據(jù)經(jīng)驗）即PIT0定時周期為20ms。周期中斷一次，時間片TIME的數(shù)值加1，根據(jù)時間片TIME值的不同調(diào)用線程使能函數(shù)ThreadSet使能相應(yīng)的線程。

由于篇幅有限，本文僅提出機器人編隊的多線程軟件框架。詳細的線程之間的互鎖、同步、競爭等關(guān)系，編隊通訊隊列的建立等具體代碼的實現(xiàn)將在后續(xù)論文中給予體現(xiàn)。

5 結(jié)束語

在機器人編隊的軟件設(shè)計中使用了多線程技術(shù)，使編隊的多個任務(wù)能夠同時執(zhí)行，增強了編隊的實時性，切實提高了編隊效率。建立多線程的機器人編隊帶禁止弧的Petri網(wǎng)模型，可以直觀明了地掌握多線程在工作流程中的執(zhí)行順序、競爭沖突、并發(fā)以及同步關(guān)系。為后期代碼的實現(xiàn)提供參考，能夠有效的避免多個線程對共享資源存取不當、線程不同步等常見問題，從而提高了機器人編隊的穩(wěn)定性和安全性。

參考文獻：

[1] Arai T，Pagello E，Parker L E.Guest editorial advances in multirobot systems[J].IEEE Transaction on Robotics and Automation，2002，18（5）：655-611.

[2] 詹惠琴，袁亮，古天祥.基于多線程的智能儀器Petri網(wǎng)[J].儀器儀表學報，2005（9）：909-912.

[3] 陳寧，程磊，王永驥.基于多線程同步的多機器人協(xié)調(diào)技術(shù)和實現(xiàn)[A].中國人工智能學會第10屆全國學術(shù)年會[C].2003.

[4] 吳哲輝.Petri網(wǎng)導論[M].北京：機械工業(yè)出版社，2006.

[5] 盧海軍.最小的多線程框架[J].單片機與嵌入式系統(tǒng)應(yīng)用，2010（4）：70-71.