參考文獻(xiàn):

• Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

這篇綜述詳細(xì)介紹了多機(jī)器人路徑規(guī)劃問題(Multi-Agent Path Finding, MAPF)統(tǒng)一的描述形式和研究 MAPF 問題需要參考的術(shù)語定義，并介紹了評估 MAPF 算法的標(biāo)準(zhǔn)數(shù)據(jù)集.

文中介紹了一個關(guān)于 MAPF 非常重要的網(wǎng)站 : http://mapf.info, 里面實(shí)時更新 MAPF 問題研究的最新進(jìn)展，包括最新的論文和全球研究 MAPF 問題的組織機(jī)構(gòu).

以下是對這篇綜述比較有價值的部分進(jìn)行總結(jié)：

Introduction

看論文首先要知道論文干了啥，這樣后續(xù)看論文就會有重點(diǎn)，一般先看看摘要和 introduction 的后半部分，然后看看 conclusion．這篇綜述是一篇 2019 年的論文，論文開頭說關(guān)于 MAPF 的研究近年來涌現(xiàn)，但關(guān)于 MAPF 問題的描述形式和變量細(xì)節(jié)的定義卻眾說紛紜，對初學(xué)者很不友好．回想看過的 MAPF 算法論文，確實(shí)一語中的，比起經(jīng)典算法，這種對一個研究方向的全局概述才更算是大部分初學(xué)者的引路人．

文章的主要貢獻(xiàn)：

• 介紹 MAPF 問題的統(tǒng)一描述形式和術(shù)語定義
• 建立基準(zhǔn)數(shù)據(jù)集(benchmarks) 和算法評估標(biāo)準(zhǔn)

MAPF 的定義:

原文:

• MAPF is an important type of multi-agent planning problem in which the task is to plan paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other.

總結(jié):

• MAPF(Multi-Agent Path Finding) 問題要干什么，其實(shí)從名字來說已經(jīng)說的很清楚了: 就是多機(jī)器人路徑規(guī)劃，再關(guān)鍵一點(diǎn)，就是無碰撞(no collision)的路徑規(guī)劃

主要應(yīng)用場景:

• 倉儲物流
• 自動駕駛
• 機(jī)器人集群相關(guān)：比如無人機(jī)編隊(duì)

經(jīng)典 MAPF 算法(Classical MAPF)

定義

理解一個算法首先先把算法玩起來，玩起來的前提是知道算法的輸入輸出，這就夠了．從輸入輸出就能從總體上了解這個算法能干什么，之后再深入算法細(xì)節(jié)，就不至于在冗雜的參數(shù)和復(fù)雜的算法細(xì)節(jié)中迷失，從而事半功倍．

注：MAPF 算法，有時也叫求解器(solver)，從編程視角來說，叫求解器可能更貼切一些．

Classical MAPF 算法的數(shù)學(xué)描述：

• $Input:<G,s,t>$, 其中：
  • 無向圖 $G=(V,E)$，$V$ 為圖 $G$ 的頂點(diǎn)， $E$ 為圖 $G$ 的邊
  • 映射 $s:[1,...,k]$ -> $V$ 將一個機(jī)器人映射到一個頂點(diǎn)，描述每個機(jī)器人(agent)的起始(source)節(jié)點(diǎn)
  • 映射 $t:[1,...,k]$ -> $V$ 一個機(jī)器人映射到一個頂點(diǎn)，描述每個機(jī)器人(agent)的目標(biāo)(target)節(jié)點(diǎn)
• 在經(jīng)典 MAPF 算法中，連續(xù)時間被離散化為時間步(這也是很多 MAPF 算法中 time step 的起源)，在每一個時間步(time step )，機(jī)器人可以做一個動作(Action)
• $Action:a:V$ -> $V$，即 $a(v)=v^{\prime }$, 表示機(jī)器人執(zhí)行動作 $a$ 后，從頂點(diǎn) $v$ 移動到頂點(diǎn) $v^{\prime }$. 在經(jīng)典 MAPF 算法中，每個機(jī)器人有兩種 actions:
  • $wait$: 待在原地，$wait(v)=v$
  • $move$: 移動到下一個相鄰頂點(diǎn)，$move(v)=v^{\prime }，(v,v^{\prime })\in E$
• 設(shè) $\pi =(a_1,...,a_n)$ 為一串動作序列．對于一個機(jī)器人 $i$，設(shè) ${\pi }_i[x]$ 為機(jī)器人 $i$ 從起點(diǎn) $s(i)$ 出發(fā)， 執(zhí)行 $\pi =(a_1,...,a_n)$ 中的前 $x$ 個動作(action)后到達(dá)的位置，即 ${\pi }_i[x]=a_x(a_{x?1}(???a_1(s(i)))$. 如果機(jī)器人 $i$ 從起點(diǎn) $s(i)$ 出發(fā)， 完整的執(zhí)行完 $\pi$ 后，到達(dá)目標(biāo)點(diǎn) $t(i)$，即 ${\pi }_i[|\pi |]=t(i)$，稱 $\pi$ 為機(jī)器人 $i$ 的單機(jī)規(guī)劃路徑($single$-$agent$ $plan$, 在 CBS 中定義為 $path$)
• $Output:solution$
  • $solution$: k 個機(jī)器人的單機(jī)規(guī)劃路徑集合(a set of $k$ single-agent plans)

總結(jié):
對于經(jīng)典 MAPF 問題:

• 輸入: 地圖+機(jī)器人起始位置+機(jī)器人目標(biāo)位置)
• 輸出: 全局路徑(多個帶時間步的單機(jī)規(guī)劃路徑)

沖突類型

為什么要定義沖突？
既然涉及到多機(jī)，每條單機(jī)規(guī)劃路徑之間的交叉或重合是很難避免的，這樣就必然導(dǎo)致機(jī)器人產(chǎn)生碰撞，為了在算法層面解決這個問題，就將路徑之間產(chǎn)生的交集定義為沖突．如果 $solution$ 中的所有 $single$-$agent$ $plan$ 都沒有沖突，那么這個 $solution$ 是 $vaild$．

設(shè) ${\pi }_i$ 和 ${\pi }_j$ 為兩條 $single$-$agent$ $plan$.

• 頂點(diǎn)沖突(Vertex conflict)
  • 在同一時間步 $x$，機(jī)器人 $i$ 和 $j$ 同時占據(jù)了頂點(diǎn) $v$, 即 ${\pi }_i[x]={\pi }_j[x]$ , 如圖(b)， 綠機(jī)器人和藍(lán)機(jī)器人將在下一時間步同時占據(jù)頂點(diǎn) $C$
• 邊沖突(Edge conflict)
  • 在同一時間步 $x$，機(jī)器人 $i$ 和 $j$ 同時穿越邊 $(v,v^{\prime })$, 即 ${\pi }_i[x]={\pi }_j[x]$ $and$ ${\pi }_i[x+1]={\pi }_j[x+1]$ , 如圖(a)， 綠機(jī)器人和藍(lán)機(jī)器人將在下一時間步同時穿越邊 $(A,B)$
• 跟隨沖突(Following conflict)
  • ${\pi }_i[x+1]={\pi }_j[x]$
  • 一臺機(jī)器人在下一時間步要占據(jù)的節(jié)點(diǎn)是另一臺機(jī)器人當(dāng)前占據(jù)的節(jié)點(diǎn)，如圖?
  • 形象一點(diǎn)解釋，跟隨沖突意味著跟車太近，沒有保持車距，如果有意外情況容易撞上
• 輪換沖突(Cycle conflict)
  • 一圖勝千言，如圖(d), 一圈機(jī)器人產(chǎn)生了一圈的跟隨沖突，當(dāng)禁止跟隨沖突的情況下這種情況會造成死鎖
  • 描述：${\pi }_i[x+1]={\pi }_{i+1}[x],{\pi }_{i+1}[x+1]={\pi }_{i+2}[x],???,{\pi }_{j?1}[x+1]={\pi }_j[x],{\pi }_j[x+1]={\pi }_i[x]$
• 交換沖突(Swapping conflict)
  • 非常經(jīng)典的沖突， ${\pi }_i[x+1]={\pi }_j[x],{\pi }_j[x+1]={\pi }_i[x]$
  • 如圖(e), 兩個機(jī)器人互換位置．
  • 在經(jīng)典 MAPF 算法中，交換沖突有時被分進(jìn)邊沖突類型，因?yàn)轱@然兩個機(jī)器人在同一時間步同時占據(jù)了一條邊

機(jī)器人在終點(diǎn)的狀態(tài)

由于每個機(jī)器人到達(dá)自己目標(biāo)點(diǎn)的時間步不一致，所以需要定義機(jī)器人到目標(biāo)點(diǎn)的狀態(tài)．這個性質(zhì)主要影響怎么去編程，跟算法沒有多大關(guān)系．

• 在終點(diǎn)消失(disappear at target)
  • 此狀態(tài)下，一旦該機(jī)器人到達(dá)目標(biāo)點(diǎn)，該目標(biāo)點(diǎn)在算法中會設(shè)置為空白(clear)狀態(tài)，之后，其他機(jī)器人的路徑可以經(jīng)過這個點(diǎn)
• 在終點(diǎn)保持(stay at target)
  • 此狀態(tài)下，一旦該機(jī)器人到達(dá)目標(biāo)點(diǎn)，該目標(biāo)點(diǎn)在算法中會設(shè)置為障礙物(obstacle)狀態(tài)，變成障礙物，之后，其他機(jī)器人的路徑不能經(jīng)過這個點(diǎn)

目標(biāo)函數(shù)

目標(biāo)函數(shù)用于評估 MAPF 問題的解($solution$), 一般有以下兩個標(biāo)準(zhǔn)：

• $Makespan$: $solution$ 中最長的 $path$ 長度，也就是最長時間步 $ma{x}_{1?i?k}|{\pi }_i|$. 類比一下，相當(dāng)于選取一個木桶最長的那塊板．
• $Sumofcosts$: 時間步總數(shù): ${\sum }_{1?i?k}|{\pi }_i|$. 類比一下，相當(dāng)于選取一個木桶所有木板的長度之和．

當(dāng)然這只是一般的標(biāo)準(zhǔn)，根據(jù)具體情況還可以設(shè)計(jì)別的評估函數(shù)，例如機(jī)器人總的等待時間($wait$動作)，這就見仁見智了．

MAPF 問題的延伸

上一部分介紹的是經(jīng)典 MAPF 問題，經(jīng)典 MAPF 問題基于以下假設(shè)：

• 時間離散化為時間步
• 一個時間步機(jī)器人執(zhí)行一個動作
• 一個時間步內(nèi)，機(jī)器人占據(jù)一個頂點(diǎn)

松弛以上假設(shè)，可以得到各種各樣的 MAPF 問題變形．

帶權(quán)圖

這部分其實(shí)就是把經(jīng)典 MAPF 的描述形式擴(kuò)展了一下，把圖的抽象擴(kuò)展成帶權(quán)圖，例如在機(jī)器人規(guī)劃領(lǐng)域廣泛使用的歐式空間(柵格地圖，矩陣等等)，$move$ 操作演變成上下左右或者更大的步數(shù)跳躍，例如數(shù)據(jù)結(jié)構(gòu)題里面模仿象棋馬走日的廣度優(yōu)先搜索．　　　　

可行性判斷

在經(jīng)典 MAPF 問題中，可行性的判斷標(biāo)準(zhǔn)唯一：沒有沖突($noconflicts$),　變形的可行性判斷規(guī)則有：

• 魯棒性判斷
  • $k?robust$ MAPF 保證每個機(jī)器人在每個時間步有 $k$ 個時間步的延遲裕量，這相比于經(jīng)典 MAPF 的條件是加強(qiáng)的．有點(diǎn)類似于高中數(shù)學(xué)幾何型線性規(guī)劃的思想.
• 隊(duì)形規(guī)則
  • 這個與多機(jī)隊(duì)形有關(guān)，例如無人機(jī)編隊(duì)，詳細(xì)可以閱讀原文獻(xiàn)中的參考文獻(xiàn)

路徑規(guī)劃和運(yùn)動規(guī)劃

經(jīng)典 MAPF 問題考慮的僅僅是理想情況的路徑規(guī)劃，但在實(shí)際問題中，機(jī)器人大小、機(jī)器人運(yùn)動學(xué)約束都是非常重要的影響因子，經(jīng)典算法需要進(jìn)行特定的優(yōu)化．

任務(wù)規(guī)劃

• 匿名 MAPF(Anonymous MAPF): 類似于滴滴打車，多個機(jī)器人需要到多個終點(diǎn)，但不規(guī)定哪臺機(jī)器人必須到哪個終點(diǎn)
• 分組 MAPF(Colored MAPF): 匿名 MAPF的變種，類似于外賣的區(qū)域性派單
• 動態(tài) MAPF(Online MAPF): 也叫 “Liftlong MAPF”, 南加州大名鼎鼎的 Jiaoyang Li 組就是研究這個的

Benchmark

這是這篇文章的第二個重點(diǎn)，介紹了評估 MAPF 算法的數(shù)據(jù)集和算法評估方法. 這里不涉及算法理論方面的東西，細(xì)節(jié)比較多，這里就不多介紹了，大家感興趣可以看看原文章．文章來源地址http://www.zghlxwxcb.cn/news/detail-462207.html

到了這里，關(guān)于多機(jī)器人路徑規(guī)劃(MAPF)綜述的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！