介紹
本文提出了MAPF問題的一個新變種及其解決方案。變種的名字正如題目，簡寫為MAPF-PC，這個問題中每個agent都有一個goal序列铝阐，需要按這個序列依次訪問每個goal，然后不同agent的不同goal之間有先后關(guān)系要求铐拐。
本文繼續(xù)在CBS和PBS上進(jìn)行魔改以解決這個變種徘键，同時提出了一些優(yōu)化方案。
CBS-PC
基本思路
在CBS上的魔改遍蟋，核心思路是把“先后關(guān)系”也定義為一種CBS內(nèi)的constraint吹害。當(dāng)搜索到某個節(jié)點出現(xiàn)這種違背先后關(guān)系的conflict時，假設(shè)當(dāng)前路徑下本應(yīng)先到的agent在時刻到虚青，對左右子節(jié)點分別施加“本應(yīng)晚來的agent必須在t時刻之后到”和“本應(yīng)晚來的agent必須在
或之前到以及本應(yīng)先來的agent必須在
或之前到”它呀。左子節(jié)點顯然很可能會解決掉這個conflict，而右子節(jié)點把conflict發(fā)生的時間至少推前了一個時刻棒厘。
其他細(xì)節(jié)
如果搜索到多個conflict纵穿，優(yōu)先解決先后關(guān)系的conflict，而在其間優(yōu)先解決會導(dǎo)致路徑長度增加最多的奢人。
對于每次路徑的尋找政恍，使用些微修改過的Multi-Label A*算法即可解決。
一些優(yōu)化
- 用先后關(guān)系預(yù)處理好到每個goal的時刻上下限（很顯然的優(yōu)化）
- disjoint splitting（CBS常規(guī)優(yōu)化）
- target reasoning（CBS常規(guī)優(yōu)化）
PBS-PC
也是在PBS基礎(chǔ)上添加了先后順序的constraint达传，但既然已經(jīng)有了規(guī)劃路徑的先后順序，底層沒有使用MLA*而只是貪心地尋找最短路徑迫筑。和PBS一樣不optimal不complete宪赶，但是快且效果不差。
