[發明專利]基于拓撲地圖的多移動機器人調度方法及系統

有效

• 申請號: 202110756841.5
• 申請日: 2021-07-05
• 公開（公告）號: CN113342002B
• 公開（公告）日: 2022-05-20
• 發明（設計）人: 歐陽博;何代鈺;顏志;張開來
• 申請（專利權）人: 湖南大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 長沙永星專利商標事務所(普通合伙) 43001
• 代理人: 周詠;米中業

1.一種基于拓撲地圖的多移動機器人調度方法，其特征在于包括如下步驟：

S1. 獲取待調度區域的地圖，并建模得到拓撲地圖；

S2. 對步驟S1獲取的拓撲地圖進行處理得到壓縮宏環圖；具體為為每個葉子節點添加自環生成圖，然后分離自環生成圖中的所有橋邊，得到宏環集，其中為宏環且，為宏環的頂點集合，為宏環的連邊集合，為宏環的連邊的數量；最后，在自環生成圖中將所有宏環壓縮為節點，從而得到壓縮宏環圖CMG；

S3. 當待調度區域內的移動機器人接受到新指令或移動到當前連邊的設定位置時，為移動機器人規劃多條候選路徑；具體為當待調度區域內的移動機器人接受到新指令，或者當調度區域內的移動機器人在當前連邊上移動的距離超過了當前連邊的x%時，采用Dijkstra算法為移動機器人規劃多條候選路徑；x為(0,100)上的正數；

具體為采用如下步驟為移動機器人規劃多條候選路徑：

A. 在步驟S2得到的拓撲地圖G中，在每次進行候選路徑規劃時，均將移動機器人所在邊的前向首節點作為源點s；

B. 根據拓撲地圖G的鄰接矩陣，采用現有的Dijkstra算法為移動機器人規劃一條從源點s至目標點d的最短路徑p₁；

C. 根據步驟B得到的最短路徑p₁上的第一個分叉點，以第一個分叉點為第一源點繼續規劃若干條不同的從第一源點至目標點d的路徑，從而得到若干條從源點s至目標點d的路徑，構成可選路徑集合P；具體為采用如下步驟構成可選路徑集合P：

C1. 找到最短路徑p₁上的第一個分叉點v，此時源點s到第一分叉點v僅有一條前向路徑p₀；

C2. 將第一分叉點v作為第一源點；

C3. 在拓撲圖中刪除第一源點v后最短路徑p₁上的第一條邊，采用現有的Dijkstra算法為移動機器人規劃一條從第一源點v至目標點d的最短路徑p₂；

C4. 在拓撲圖中刪除步驟C3得到的最短路徑p₂的首個連邊，并將路徑p₀與p₂拼接后存入可選路徑集合P；

C5. 重復步驟C3~C4直至最短路徑p₂為空，從而得到最終的可選路徑集合P；

S4. 對步驟S3得到的多條候選路徑進行安全性判斷，從而給移動機器人下達下一步的控制指令；具體為采用如下步驟進行安全性判斷并給移動機器人下達下一步的控制指令：

a. 獲取待調度區域的所有移動機器人的數據信息；

b. 在自環生成圖中，將移動機器人所在的連邊轉化為對應其移動方向的有向邊，生成部分有向圖D用于表示當前狀態；

c. 根據宏環集M，將可選路徑集合P中的路徑p_i分離為p_ib、p_iu、p_ibub、u_i1和u_i2；其中p_ib為路徑p_i的第一個宏環前的路徑，p_iu為路徑p_i的第一個宏環內的路徑，p_ibub為路徑p_i的第一個宏環和第二個宏環之間的橋邊，u_i1為路徑p_i的第一個宏環，u_i2為路徑p_i的第二個宏環；

d. 采用如下步驟判斷路徑p_i的安全性：

d1. 若路徑p_i上的第一條邊沒有被任何移動機器人占領，則采用如下步驟繼續進行d2~d3的判定；否則，判定路徑p_i為不安全；

d2. 若路徑p_ib為空，則對路徑p_iu進行判定：

若路徑p_iu為空，則判定路徑p_i為安全；

若路徑p_iu不為空，則采用如下步驟繼續進行d2-1~ d2-4的判定：

d2-1. 在部分有向圖D內標記宏環u_i1內涉及到的所有的邊和節點，得到部分有向圖D的子圖：

d2-2. 將當前所有處于宏環u_i1內的移動機器人構成集合u_i1_controller；

d2-3. 遍歷宏環u_i1內路徑p_iu上的連邊：

若連邊已經被其他移動機器人占有，則判定路徑p_i為不安全；

若連邊未被其他移動機器人占有，則在子圖上將相應連邊轉換為相應方向的有向邊并得到第一子圖，再進行判斷：若集合u_i1_controller內所有移動機器人在第一子圖中均能夠按照路徑達到虛擬前進連邊且子圖為強連通圖，則判定路徑p_i為安全，同時將當前遍歷的連邊設置為移動機器人的虛擬前進邊；否則，重復步驟d2-3直至所有連邊均遍歷完成；

d2-4. 若宏環u_i2的容量大于0且p_ibub上不存在與當前移動機器人相反方向移動的機器人，則判定路徑p_i為安全，同時設p_ibub的首條邊為當前移動機器人的虛擬前進邊；否則，判定路徑p_i為不安全；

d3. 路徑p_ib不為空，則采用如下步驟繼續進行的判定：

d3-1. 若宏環u_i1的容量小于1，則判定路徑p_i為不安全；否則，采用后續的步驟d3-2~d3-3進行判斷：

d3-2. 針對所有當前處于橋邊的移動機器人，將移動機器人當前連邊前方首節點作為源點，以路徑上最近的宏環作為目標點，構成二元組集合b_controller；

d3-3. 基于壓縮宏環圖CMG，判斷二元組集合b_controller中所有的二元組能否按照任意順序完成配對關系，完成配對關系的定義為：每個二元組的源點能夠與其他二元組無交互地到達對應的目標點：若不能，則判定路徑p_i為不安全；否則，采用步驟d2中對于路徑p_iu的判定方法，對路徑p_iu進行判定；

e. 采用如下規則給移動機器人下達下一步的控制指令：

將第一個被判定為安全的路徑p_i直接分配給移動機器人，作為下一步的控制指令；

若所有路徑都被判定為不安全，則移動機器人暫停移動，直至收到下一步的控制指令；

S5. 重復步驟S3~S4，完成待調度區域內多移動機器人的調度。