欧美久久免费福利视频_国产尤物网站尤物在线看_久久黄色大片99精品网站亚洲综合社区_欧美日韩一区二区三区伦理_免费?ⅴ片在线观看蜜芽Tⅴ_国产欧美日韩视频在线不卡_囯产片婬乱一级毛片91xXX_影音先锋男人资源av站

        多代理路徑尋找(Multi-agent path finding/MAPF)已在人工智能、機(jī)器人、理論計(jì)算機(jī)科學(xué)和實(shí)際操作研究中得到大量的研究。本文討論了在將MAPF方法推廣到實(shí)際場景時(shí)出現(xiàn)的問題與解決這些問題的四個(gè)研究方向。我們強(qiáng)調(diào)的是解決這些問題的重要性，而不是為MAPF問題的標(biāo)準(zhǔn)模型開發(fā)更快的方法。

1 引言

       多代理路徑尋找(MAPF，也叫多代理尋徑)在人工智能、機(jī)器人、理論計(jì)算機(jī)科學(xué)和實(shí)際操作研究中得到大量的研究。(標(biāo)準(zhǔn))MAPF的任務(wù)是為多個(gè)代理(agent)找到在給定圖(graph)中從其當(dāng)前頂點(diǎn)(vertices)到其目標(biāo)而不與其它代理發(fā)生碰撞的路徑，同時(shí)優(yōu)化成本函數(shù)(cost function)�，F(xiàn)有的 MAPF 使用的方法包括：從可滿足性減少問題(reductions to problems from satisfiability)、整數(shù)線性規(guī)劃(integer linear programming)、回答集編程(answer set programming)[Yu and LaValle， 2013b; Erdem et al.， 2013; Surynek， 2015]、最優(yōu)/有限次優(yōu)(optimal，bounded-suboptimal)或次優(yōu)搜索方法(suboptimal search method)[Silver， 2005; Sturtevant and Buro， 2006; Ryan， 2008; Wang and Botea， 2008; Standley， 2010; Standley and Korf， 2011; Wang and Botea， 2011; Luna and Bekris， 2011; Sharon et al.， 2013; de Wilde et al.， 2013; Barer et al.， 2014; Goldenberg et al.， 2014; Wagner and Choset， 2015; Boyarski et al.， 2015; Sharon et al.， 2015]。

       我們最近研究了將 MAPF 推廣到實(shí)際場景時(shí)出現(xiàn)的各種問題，包括 Kiva(Amazon Robotics)倉庫系統(tǒng)[Wurman et al.， 2008](圖1)和自動飛行器牽引車[Morris et al.， 2016]。這些問題可以分為兩個(gè)一般問題：

       1、為 MAPF 問題的標(biāo)準(zhǔn)模型開發(fā)更快的方法是不夠的，因?yàn)樵谠S多實(shí)際情況下，可以利用新的結(jié)構(gòu)或需要新的問題模型。

       2、僅將 MAPF 或其新的模型作為組合優(yōu)化問題進(jìn)行研究是不夠的，因?yàn)樗�產(chǎn)生的 MAPF 解決方案也需要執(zhí)行。

我們從不同的角度討論了解決這兩個(gè)問題的四個(gè)研究方向：

       1.在許多實(shí)際的多代理系統(tǒng)中，在為所有代理找到最佳路徑之前，代理先被劃分成組(team)，然后給每個(gè)組分配特定的目標(biāo)，每個(gè)代理需要從所在的組中被指定一個(gè)目標(biāo)。我們已經(jīng)為不同組的代理制定了組合目標(biāo)分配和路徑查找(TAPF/target assignment and path finding)問題來解決這個(gè)困難。我們還開發(fā)了一個(gè)最佳 TAPF 方法，它可以擴(kuò)展到幾十個(gè)組和數(shù)百個(gè)代理[Ma and Koenig， 2016]。

       2.在許多實(shí)際的多代理系統(tǒng)中，代理是匿名的(可交換的)，但是它們的有效載荷是非匿名的(不可交換的)，并且需要被傳遞給給定的目標(biāo)。代理通�？梢栽谶@樣的系統(tǒng)中交換其有效載荷。作為第一次嘗試，我們設(shè)計(jì)了包裹交換機(jī)器人路由(package-exchange robot routing/PERR)問題，以解決更多一般化的(允許有效載荷轉(zhuǎn)移的)運(yùn)輸問題[Ma et al.， 2016]。在這篇文章中，我們還證明了近似最優(yōu) MAPF 解的困難性(復(fù)雜度)。

       3.在許多實(shí)際的多代理系統(tǒng)中，代理運(yùn)動(agent motions)的一致性和代理運(yùn)動的結(jié)果可預(yù)測性是重要的(特別是在由人和代理共享的工作空間中)，但是現(xiàn)有的 MAPF 方法沒有考慮這一點(diǎn)。我們已經(jīng)分兩個(gè)階段探索了給定 MAPF 例子的問題結(jié)構(gòu)：在第一階段，我們開發(fā)了一種為代理尋找路徑的方案，其中包含了由用戶提供的許多帶邊緣的高速公路(highways)，這個(gè)方案達(dá)到了代理運(yùn)動的一致性和可預(yù)測性[Cohen et al.， 2015];在第二階段，我們開發(fā)了自動生成高速公路的方法[Cohen et al.， 2016]。

       4.MAPF 的靈感主要來源于多機(jī)器人系統(tǒng)的導(dǎo)航或運(yùn)動規(guī)劃模塊。然而，MAPF 解決方案的最優(yōu)性或有限次優(yōu)性不一定意味著它們的魯棒性，特別是考慮到現(xiàn)實(shí)中機(jī)器人不完美的規(guī)劃執(zhí)行(plan-execution)能力。我們開發(fā)了一個(gè)框架，它能有效地后期處理(postprocesses)MAPF 方法的輸出，用于創(chuàng)建一個(gè)可以由實(shí)際的多機(jī)器人系統(tǒng)執(zhí)行的規(guī)劃執(zhí)行安排。

       圖 1 ：(左圖)自動駕駛單元和可以被駕駛單元移動的存儲產(chǎn)品的存儲艙(storage pod);(右圖)典型 Kiva 倉庫系統(tǒng)的布局(Wurman et al.， 2008)

       為了將 MAPF 方法推廣到實(shí)際的場景，我們現(xiàn)在展示這些研究方向的實(shí)用性，以證明解決這兩個(gè)問題與開發(fā)更快的 MAPF 問題的標(biāo)準(zhǔn)模型方法一樣重要(甚至更重要)。

2 代理組的目標(biāo)分配和路徑查找(TAPF)的組合

       一般來說，是按照代理所在的每個(gè)組分配目標(biāo)。代理先被劃分到組中，然后每個(gè)代理需要從所在的組中被指定一個(gè)目標(biāo)，以便得到代理從當(dāng)前頂點(diǎn)到其目標(biāo)的路徑來優(yōu)化成本函數(shù)。例如，在 Kiva 倉庫系統(tǒng)中，將存儲艙從倉庫搬運(yùn)到新存儲位置的駕駛單元(drive unit)會形成一個(gè)組，因?yàn)樗鼈冎械拿恳粋�(gè)需要被分配一個(gè)可用的存儲位置。以前的 MAPF 方法假設(shè)存在目標(biāo)分配程序，使得每個(gè)代理預(yù)先被分配一個(gè)目標(biāo)，但是為了實(shí)現(xiàn)最優(yōu)性，我們建立了 TAPF 模型，它整合了目標(biāo)分配和路徑尋找問題并且為它們定義了一個(gè)共同的目標(biāo)。在 TAPF 中，代理被分到各組中，每個(gè)組的目標(biāo)數(shù)量與該組中的代理數(shù)量相同。TAPF 的任務(wù)是將目標(biāo)分配給代理，并規(guī)劃代理從當(dāng)前頂點(diǎn)到其目標(biāo)的不會發(fā)生碰撞的路徑，使得每個(gè)代理恰好移動到其所在組的一個(gè)目標(biāo)，從而組中的所有目標(biāo)被訪問，且最大完成時(shí)間(當(dāng)所有代理已經(jīng)到達(dá)其目標(biāo)并停止移動時(shí)的最早時(shí)間步長)被最小化。組中的每個(gè)代理都可以被分配到所在組的目標(biāo)，并且同一組中的代理因此是可交換的。然而，不同組中的代理不可交換。TAPF 可以被視為(標(biāo)準(zhǔn))MAPF 和 MAPF 的匿名變體的一般化：

• 來自 TAPF的(標(biāo)準(zhǔn))MAPF 結(jié)果，如果每個(gè)組僅由一個(gè)代理組成，則組的數(shù)量等于代理的數(shù)量。目標(biāo)到代理的分配是預(yù)先確定的，因此代理是非匿名的(不可交換的)。

• 如果只有一個(gè)組(包含所有代理)，則 MAPF 的匿名變量(也稱為目標(biāo)不變的 MAPF)來自 TAPF。代理可以被分配任何目標(biāo)，因此是可交換的。它可以在多項(xiàng)式時(shí)間內(nèi)用基于流的 MAPF 方法(flow-based MAPF method)得到最優(yōu)解[Yu and LaValle， 2013a; Turpin et al.， 2014].

       當(dāng)前最先進(jìn)的最優(yōu) TAPF 方法——稱為基于碰撞的最小成本流(Conflict-Based Min-Cost Flow)[Ma and Koenig， 2016]——結(jié)合了搜索和基于流的 MAPF 方法。它可以推廣到幾十個(gè)組和數(shù)百個(gè)代理。

3 MAPF 的包裹交換機(jī)器人路由(PERR)和新的復(fù)雜度計(jì)算結(jié)果

       代理通常是匿名的，但攜帶被分配目標(biāo)的有效載荷(包裹)，因此是非匿名的。例如，在 Kiva 倉庫系統(tǒng)中，駕駛單元是匿名的，但是它們攜帶的存儲艙被分配了存儲位置，因此是非匿名的。如果每個(gè)代理都攜帶一個(gè)包裹，則該問題相當(dāng)于(標(biāo)準(zhǔn))MAPF。實(shí)際上，包裹通�？梢栽诖�理之間傳遞，這導(dǎo)致更一般的運(yùn)輸問題，例如，帶有換乘的乘客共享乘車[Coltin and Veloso， 2014]和在辦公室中使用機(jī)器人的包裹遞送[Veloso et al.， 2015]。我們已經(jīng)將 PERR 作為理解這些問題的第一步[Ma et al.， 2016]。在 PERR 中，每個(gè)代理運(yùn)載一個(gè)包裹，相鄰頂點(diǎn)中的任何兩個(gè)代理可以交換其包裹，并且每個(gè)包需裹要被遞送到給定目標(biāo)。PERR 因此可以被視為(標(biāo)準(zhǔn))MAPF 的改進(jìn)版：

• PERR 中的包裹可以被視為在(標(biāo)準(zhǔn))MAPF 中的自己移動的代理。

  
  

• 允許在相鄰頂點(diǎn)中的兩個(gè)包裹在 PERR 中交換它們的頂點(diǎn)，但是在相鄰頂點(diǎn)中的兩個(gè)代理不允許在(標(biāo)準(zhǔn))MAPF 中交換它們的頂點(diǎn)。

  
  

       K-PERR 是 PERR 的一般化，其中包裹被分成 K 個(gè)類型，并且相同類型的包裹是可交換的。因?yàn)樵?TAPF 中，代理被分到組中，并且同一團(tuán)隊(duì)中的代理是可交換的，所以 K-PERR 可以被視為對 K 個(gè)組的 TAPF 的改版，同樣的原理，PERR 可以被視為(標(biāo)準(zhǔn))MAPF 的改版。我們已經(jīng)證明了近似最佳 PERR 和 K-PERR 解的困難性(對于K≥2)。我們的研究的一個(gè)推論是：在任何因子小于4/3內(nèi)的最大完工時(shí)間最小化，近似 MAPF 和 TAPF 是 NP-hard 的，即使是只有兩個(gè)團(tuán)隊(duì)的 TAPF。我們還證明了向 MAPF 添加交換操作不會在理論上減少其復(fù)雜度，但使得 PERR 比 MAPF 更容易解決。由此產(chǎn)生的在不同的實(shí)際場景中的連續(xù)問題：「一個(gè)有很多包裹的代理」產(chǎn)生經(jīng)典的農(nóng)村郵遞員問題(rural postman problem);「代理與包裹一樣多」產(chǎn)生 MAPF、TAPF 或 PERR。了解這兩個(gè)極端問題有助于我們解決一般問題，正如其它許多真實(shí)世界任務(wù)的要求一樣。

圖 2：在一個(gè)模擬的 Kiva 倉庫系統(tǒng)中用戶提供的高速路(highway)

4 探索問題的結(jié)構(gòu)和運(yùn)動的可預(yù)測性

       代理與人共享工作空間，它們運(yùn)動的一致性和其運(yùn)動結(jié)果的可預(yù)測性對于人類的安全是重要的，因此不考慮現(xiàn)有的 MAPF 方法。這促使我們探索給定的 MAPF 例子的問題結(jié)構(gòu)，并設(shè)計(jì)一個(gè)激勵代理沿著用戶提供的邊緣(edge)集合(稱為高速公路)移動的方案[Cohen et al.， 2015]。我們在簡單的膨脹方案(inflation scheme)的背景下使用基于經(jīng)驗(yàn)圖(experience graph)的高速公路[Phillips et al.， 2012]的想法，以導(dǎo)出新的啟發(fā)值(heuristic values)，這個(gè)值用來激勵 MAPF 方法返回包括高速公路邊緣的路徑，這種方法能夠避免代理之間的迎面碰撞(head-to-head collisions)，并實(shí)現(xiàn)其運(yùn)動的一致性和可預(yù)測性。例如，在 Kiva 倉庫系統(tǒng)中，我們可以沿著存儲位置之間的狹窄通道設(shè)計(jì)高速公路，如圖2中的箭頭所示。我們已經(jīng)在模擬的 Kiva 倉庫系統(tǒng)中證明，這樣的高速公路能夠顯著加速 MAPF 方法，同時(shí)保持期望的 MAPF 解決方案成本的有限次優(yōu)性。 TAPF 和 PERR 例子的問題結(jié)構(gòu)也可以利用相同的方法。在可行性研究中，我們還開發(fā)了與用戶提供公路相媲美的自動生成公路的方法。

5 解決不完美的規(guī)劃執(zhí)行能力

最先進(jìn)的 MAPF 或 TAPF 方法可以在合理的計(jì)算時(shí)間內(nèi)為數(shù)百個(gè)代理找到最佳的或者在用戶提供的次優(yōu)性保證下的不會發(fā)生碰撞的路徑。它們甚至在雜亂而緊湊的環(huán)境中也能正常工作，如Kiva 倉庫系統(tǒng)。然而，代理通常具有不完美的規(guī)劃執(zhí)行能力，并且不能完美地同步它們的運(yùn)動，這可以導(dǎo)致頻繁的重新規(guī)劃并浪費(fèi)時(shí)間。因此，我們提出了一個(gè)框架，使用一個(gè)簡單的時(shí)間網(wǎng)絡(luò)來有效地后期處理 MAPF 解決方案并創(chuàng)建一個(gè)規(guī)劃執(zhí)行安排，這適用于非完整機(jī)器人(non-holonomic robot)，考慮到它們的最大的平移和旋轉(zhuǎn)速度，提供了一個(gè)機(jī)器人之間安全距離和松弛邊界(定義為最新和最早進(jìn)入時(shí)間的地點(diǎn)的差異)的保證，以緩解不完美的規(guī)劃執(zhí)行并避免在許多情況下的時(shí)間密集的重新規(guī)劃[Honig ¨ et al.， 2016]。這個(gè)框架已經(jīng)在仿真和真實(shí)機(jī)器人中得到評估。TAPF 和 PERR 方法也可以在同一框架中應(yīng)用。未來工作中要解決的問題包括增加用戶提供的安全距離、額外的運(yùn)動約束、不確定性規(guī)劃和重新規(guī)劃。

6 結(jié)論

我們討論了四個(gè)研究方向，以解決當(dāng)將 MAPF 方法推廣到實(shí)際場景中和探索問題結(jié)構(gòu)或現(xiàn)有 MAPF 方法時(shí)出現(xiàn)的問題。我們的目標(biāo)是為在 MAPF 領(lǐng)域工作的研究人員指出有趣的研究方向。