[發(fā)明專(zhuān)利]基于密集存儲(chǔ)區(qū)域的多移動(dòng)機(jī)器人路徑?jīng)_突解決方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210377706.0
• 申請(qǐng)日: 2012-10-08
• 公開(kāi)（公告）號(hào): CN102865877A
• 公開(kāi)（公告）日: 2013-01-09
• 發(fā)明（設(shè)計(jì)）人: 楊宇;景國(guó)輝
• 申請(qǐng)（專(zhuān)利權(quán)）人: 無(wú)錫普智聯(lián)科高新技術(shù)有限公司
• 主分類(lèi)號(hào): G01C21/34
• 分類(lèi)號(hào): G01C21/34
• 代理公司: 天津盛理知識(shí)產(chǎn)權(quán)代理有限公司 12209
• 代理人: 王利文

技術(shù)領(lǐng)域

本發(fā)明屬于移動(dòng)機(jī)器人領(lǐng)域，尤其是一種基于密集存儲(chǔ)區(qū)域的多移動(dòng)機(jī)器人路徑?jīng)_突解決方法。

背景技術(shù)

密集存儲(chǔ)區(qū)域多機(jī)器人避碰規(guī)劃的條件是：(1)機(jī)器人的運(yùn)動(dòng)限制在二維空間，屬于平面運(yùn)動(dòng)；(2)密集存儲(chǔ)區(qū)域巷道不僅狹窄并且還具有相干性，所謂狹窄，就是有的地方其寬度只允許一個(gè)機(jī)器人平躺著通過(guò)；所謂相干性就是某幾個(gè)路點(diǎn)區(qū)域組合的區(qū)域是由不同姿態(tài)的區(qū)域交錯(cuò)疊加而成：機(jī)器人可以以不同姿態(tài)通過(guò)這個(gè)區(qū)域；(3)機(jī)器人的碰撞指由于在同一條巷道上相向而行和交錯(cuò)而行引起的任務(wù)死鎖，不考慮同向而行的情況；(4)運(yùn)動(dòng)的機(jī)器人組成了其它機(jī)器人成員的動(dòng)態(tài)障礙；(5)機(jī)器人和服務(wù)器之間通過(guò)無(wú)限網(wǎng)絡(luò)進(jìn)行通訊。

在多機(jī)器人運(yùn)動(dòng)系統(tǒng)中，可能會(huì)出現(xiàn)死鎖的運(yùn)動(dòng)沖突情況。所謂死鎖是指兩個(gè)以顯示方式通訊的機(jī)器人相向而行，當(dāng)它們距離足夠近時(shí)，各自停了下來(lái)，相互無(wú)休止地循環(huán)等待，最后導(dǎo)致機(jī)器人的運(yùn)動(dòng)完全停止，此種情況稱(chēng)之為任務(wù)死鎖。多機(jī)器人路徑?jīng)_突解決策略就是要解決當(dāng)多機(jī)器人在同一條路徑上相向而行和交錯(cuò)而行時(shí)，在保證互不發(fā)生死鎖的情況下，安全順暢地執(zhí)行任務(wù)，從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)的問(wèn)題。

根據(jù)機(jī)器人工作環(huán)境的不同，沖突消解可分為兩種:集中管理式?jīng)_突消解和分布式?jīng)_突消解。集中管理式方法通常可以尋找最優(yōu)解，但是需要預(yù)先知道環(huán)境的準(zhǔn)確信息，并且計(jì)算量很大，實(shí)時(shí)性差，其典型應(yīng)用是將機(jī)器人的運(yùn)動(dòng)路徑分段，然后按沖突消解要求對(duì)機(jī)器人通過(guò)各段的時(shí)間進(jìn)行約束，通過(guò)調(diào)整機(jī)器人各段的時(shí)間進(jìn)行沖突消解，從而將沖突消解問(wèn)題轉(zhuǎn)化為高維線性空間的優(yōu)化問(wèn)題，并進(jìn)一步轉(zhuǎn)化為線性方程的求解。分布式?jīng)_突消解方法側(cè)重于考慮機(jī)器人當(dāng)前的局部環(huán)境信息，讓機(jī)器人具有良好的沖突消解能力，和集中管理式方法向比較，分布式方法更具有實(shí)時(shí)性和實(shí)用性。分布式?jīng)_突消解方法通常有三種解決方法：交通規(guī)則法、速率調(diào)整法和優(yōu)先級(jí)法（見(jiàn)哈爾濱工程大學(xué)論文《多機(jī)器人協(xié)調(diào)避碰與任務(wù)協(xié)作研究》）。交通規(guī)則法就是給多機(jī)器人制定共同遵守的規(guī)則，保持群體的有序性，有了這些規(guī)則，就能使有自控意愿的個(gè)體保持有序，交通規(guī)則法雖然可以避免死鎖現(xiàn)象發(fā)生，但機(jī)器人行走通道必須保證右側(cè)通行，當(dāng)兩個(gè)相向而行的機(jī)器人在同一條通道上行走時(shí)，只有各占其道才能保證不發(fā)生死鎖，如果通道的寬度不能容納兩個(gè)機(jī)器人的寬度而只能讓一個(gè)機(jī)器人通過(guò)時(shí)，交通規(guī)則法此時(shí)顯然失效。速率調(diào)整法和優(yōu)先級(jí)法是結(jié)合一起使用的，其速率調(diào)整包括加速、減速、停止甚至是倒退，當(dāng)兩個(gè)相向而行的機(jī)器人發(fā)生死鎖時(shí)，優(yōu)先級(jí)別高的有權(quán)讓級(jí)別低的退讓到寬闊地帶，而使其自身優(yōu)先通過(guò)，此方法不足在于，僅僅依靠局部信息，會(huì)產(chǎn)生局部極點(diǎn)，無(wú)法保證機(jī)器人順利到達(dá)目的地，例如：機(jī)器人其中一個(gè)必須退回到開(kāi)闊地帶才可以解決問(wèn)題，但機(jī)器人作倒退運(yùn)動(dòng)的環(huán)境條件在當(dāng)前局部信息中無(wú)法獲得：在倒退過(guò)程中如何保證途中不再和其它機(jī)器人發(fā)生碰撞?機(jī)器人倒退到哪里最為經(jīng)濟(jì)合理？如何保證倒退目標(biāo)點(diǎn)是有效目標(biāo)點(diǎn)等一系列問(wèn)題，由于分布式?jīng)_突消解方法僅僅依靠局部信息無(wú)法真正實(shí)現(xiàn)任務(wù)，還增加了難度，在實(shí)際運(yùn)行中，此種方法很少被采納。

綜上所述，集中管理式方法最為精確，但運(yùn)算復(fù)雜且實(shí)時(shí)性差，而分布式方法雖然運(yùn)算簡(jiǎn)單、實(shí)時(shí)性和靈活性強(qiáng)，但由于會(huì)出現(xiàn)局部極點(diǎn)，往往無(wú)法完整地完成任務(wù)。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術(shù)的不足，提供一種精確程度高、運(yùn)算簡(jiǎn)潔、實(shí)時(shí)性強(qiáng)的的基于密集存儲(chǔ)區(qū)域的多移動(dòng)機(jī)器人路徑?jīng)_突解決方法。

本發(fā)明解決其技術(shù)問(wèn)題是采取以下技術(shù)方案實(shí)現(xiàn)的：

一種基于密集存儲(chǔ)區(qū)域的多移動(dòng)機(jī)器人路徑?jīng)_突解決方法，包括以下步驟：

步驟1：調(diào)度服務(wù)器建立一初始化網(wǎng)狀路徑圖；

步驟2：調(diào)度線程檢測(cè)到有存取貨物任務(wù)時(shí)，獲取起始點(diǎn)和目標(biāo)點(diǎn)信息并將任務(wù)劃分若干個(gè)子任務(wù)，每個(gè)子任務(wù)又設(shè)有各自的起始點(diǎn)和目標(biāo)點(diǎn)，每個(gè)子任務(wù)為空車(chē)尋貨子任務(wù)或負(fù)載運(yùn)貨子任務(wù)；

步驟3：調(diào)度線程根據(jù)子任務(wù)的起始點(diǎn)、目標(biāo)點(diǎn)及參數(shù)使用圖搜索法輸出當(dāng)前子任務(wù)的任務(wù)路徑；

步驟4：調(diào)度線程判斷該子任務(wù)目標(biāo)點(diǎn)是否被上一個(gè)的任務(wù)釋放掉，如果沒(méi)有被釋放，等待釋放，如果已經(jīng)被釋放，則進(jìn)入步驟5；

步驟5：調(diào)度線程使用攜帶方向和排序特征的任務(wù)編號(hào)標(biāo)記每個(gè)任務(wù)路經(jīng)，被標(biāo)記的點(diǎn)包括當(dāng)前任務(wù)路徑上的點(diǎn)以及它的相干點(diǎn)；

步驟6：調(diào)度線程標(biāo)記完所有任務(wù)路徑后，將標(biāo)記后的任務(wù)送入執(zhí)行隊(duì)列，返回步驟2；

步驟7：執(zhí)行線程執(zhí)行任務(wù)隊(duì)列的各任務(wù)搶占資源變量；

步驟8：執(zhí)行線程將所有一個(gè)路點(diǎn)上被標(biāo)記至少兩個(gè)任務(wù)編號(hào)、并且方向相反的路點(diǎn)組合的區(qū)域劃分為沖突區(qū)。