[發(fā)明專(zhuān)利]一種基于拓?fù)涞貓D和沖突消除策略的多無(wú)人車(chē)尋路方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010041160.6
• 申請(qǐng)日: 2020-01-15
• 公開(kāi)（公告）號(hào): CN111238519B
• 公開(kāi)（公告）日: 2022-05-03
• 發(fā)明（設(shè)計(jì)）人: 蔡奕僑;張凱凱;鄒燁;傅順開(kāi);張惠臻;田暉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華僑大學(xué)
• 主分類(lèi)號(hào): G01C21/34
• 分類(lèi)號(hào): G01C21/34
• 代理公司: 廈門(mén)市首創(chuàng)君合專(zhuān)利事務(wù)所有限公司 35204
• 代理人: 張松亭

1.一種基于拓?fù)涞貓D和沖突消除策略的多無(wú)人車(chē)尋路方法，其特征在于，包括以下步驟：

1)根據(jù)真實(shí)的地形獲取相應(yīng)的拓?fù)涞貓D的數(shù)據(jù)，拓?fù)涞貓D的數(shù)據(jù)包含：node(x,y)，track(startNode,endNode,weight)，topoMap（tracks,nodes)；其中，node表示拓?fù)涞貓D中結(jié)點(diǎn)，track表示拓?fù)涞貓D的邊，其由開(kāi)始頂點(diǎn)startNode、結(jié)束頂點(diǎn)endNode和權(quán)重weight組成，topoMap表示整個(gè)拓?fù)涞貓D，由邊集tracks和頂點(diǎn)集nodes構(gòu)成；

2)將拓?fù)涞貓D轉(zhuǎn)化為加權(quán)有向圖，具體地：將拓?fù)涞貓D中邊集的每條邊，加上方向生成有向圖，再在其邊上等距離插入點(diǎn)，點(diǎn)的數(shù)目為邊的權(quán)重，從而生成加權(quán)有向圖；

3)輸入M，M≥3輛車(chē)在加權(quán)有向圖中的起點(diǎn)與終點(diǎn)，并設(shè)無(wú)人車(chē)的路徑集chrome為空,其中，chrome由無(wú)人車(chē)的動(dòng)作計(jì)劃S構(gòu)成，S表示M輛無(wú)人車(chē)在一段時(shí)間內(nèi)的動(dòng)作計(jì)劃；

4)調(diào)用CCBS算法生成無(wú)人車(chē)的動(dòng)作計(jì)劃S，具體地，CCBS算法以無(wú)人車(chē)的起點(diǎn)與終點(diǎn)為輸入，重復(fù)調(diào)用高級(jí)搜索來(lái)檢查、選擇和解決沖突，調(diào)用低級(jí)搜索來(lái)生成新的動(dòng)作計(jì)劃S，直到生成合理解或到達(dá)最大運(yùn)行時(shí)間，返回S；

5)判斷S中是否存在沖突，若不存在，進(jìn)入步驟11)；

6)若存在，獲取S中所有的沖突點(diǎn)，記錄下含有沖突最多的結(jié)點(diǎn)p及其沖突數(shù)n_t；

7)分析在p點(diǎn)存在沖突的無(wú)人車(chē)數(shù)量，即：n_t≥m-1,若是，進(jìn)入步驟8)；若否，進(jìn)入步驟9)；

8)調(diào)用“中間點(diǎn)沖突消除法”，選擇最大沖突點(diǎn)之前的位置作為無(wú)人車(chē)的目標(biāo)位置；

9)調(diào)用“相鄰點(diǎn)沖突消除法”，選擇當(dāng)前位置的相鄰位置作為無(wú)人車(chē)的目標(biāo)位置；

10)以選擇的每輛無(wú)人車(chē)的目標(biāo)位置作為其終點(diǎn)，進(jìn)入步驟4)；

11)將新生成的無(wú)人車(chē)的動(dòng)作計(jì)劃S加入到無(wú)人車(chē)的路徑集chrome中，并判斷無(wú)人車(chē)是否到達(dá)輸入的終點(diǎn)，若到達(dá)，進(jìn)入步驟12)；若沒(méi)有到達(dá)，以當(dāng)前位置為無(wú)人車(chē)的起點(diǎn)，輸入終點(diǎn)為無(wú)人車(chē)的終點(diǎn)，然后進(jìn)入步驟4)；

12)對(duì)多無(wú)人車(chē)的路徑集chrome進(jìn)行處理，即：將按時(shí)間段的路徑集chrome＝{S₀,S₁,…}轉(zhuǎn)化成面向無(wú)人車(chē)的聯(lián)合計(jì)劃π＝{π₁,π₂,…,π_M}，然后返回π；

所述中間點(diǎn)沖突消除法，具體包括：定義了動(dòng)作計(jì)劃中每個(gè)結(jié)點(diǎn)的選擇概率，如下所示：

其中，N_i表示無(wú)人車(chē)i動(dòng)作計(jì)劃中頂點(diǎn)的數(shù)目，表示無(wú)人車(chē)i經(jīng)過(guò)第j個(gè)頂點(diǎn)的沖突數(shù)目，t表示在無(wú)人車(chē)i的動(dòng)作計(jì)劃中結(jié)點(diǎn)的取最大值時(shí)j的值，表示無(wú)人車(chē)i到達(dá)第t個(gè)點(diǎn)時(shí)出現(xiàn)的沖突數(shù)之和，通過(guò)公式計(jì)算出無(wú)人車(chē)經(jīng)過(guò)頂點(diǎn)的選擇概率，選擇最大沖突點(diǎn)之前的頂點(diǎn)來(lái)消除沖突；

所述相鄰點(diǎn)沖突消除法，具體包括：

a)針對(duì)每輛沖突的無(wú)人車(chē)建立其所在結(jié)點(diǎn)的鄰接表，隨機(jī)地將其未使用的鄰居頂點(diǎn)加入到鄰接表中；

b)根據(jù)無(wú)人車(chē)的鄰接表長(zhǎng)度對(duì)無(wú)人車(chē)進(jìn)行升序排序，從而使鄰居少的無(wú)人車(chē)優(yōu)先被處理；

c)按順序?qū)γ總€(gè)沖突的無(wú)人車(chē)進(jìn)行分配相鄰頂點(diǎn)，并將分配過(guò)的頂點(diǎn)從整個(gè)鄰接表中刪除，若無(wú)人車(chē)沒(méi)有無(wú)沖突的相鄰頂點(diǎn)，則無(wú)人車(chē)的目標(biāo)為當(dāng)前位置；

d)重復(fù)c)，直到?jīng)_突的無(wú)人車(chē)被重新分配相鄰點(diǎn)完畢。