您的位置:首頁 > 資訊 > 行業(yè)動態(tài) > 正文

AGV機(jī)器人多代理路徑尋的四大研究方向

2017-04-19 07:46 性質(zhì):轉(zhuǎn)載 作者:機(jī)器之心 來源:機(jī)器之心
免責(zé)聲明:中叉網(wǎng)(m.m21363.cn)尊重合法版權(quán),反對侵權(quán)盜版。(凡是我網(wǎng)所轉(zhuǎn)載之文章,文中所有文字內(nèi)容和圖片視頻之知識產(chǎn)權(quán)均系原作者和機(jī)構(gòu)所有。文章內(nèi)容觀點,與本網(wǎng)無關(guān)。如有需要刪除,敬請來電商榷?。?/div>

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

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

4 探索問題的結(jié)構(gòu)和運動的可預(yù)測性
  代理與人共享工作空間,它們運動的一致性和其運動結(jié)果的可預(yù)測性對于人類的安全是重要的,因此不考慮現(xiàn)有的 MAPF 方法。這促使我們探索給定的 MAPF 例子的問題結(jié)構(gòu),并設(shè)計一個激勵代理沿著用戶提供的邊緣(edge)集合(稱為高速公路)移動的方案[Cohen et al., 2015]。我們在簡單的膨脹方案(inflation scheme)的背景下使用基于經(jīng)驗圖(experience graph)的高速公路[Phillips et al., 2012]的想法,以導(dǎo)出新的啟發(fā)值(heuristic values),這個值用來激勵 MAPF 方法返回包括高速公路邊緣的路徑,這種方法能夠避免代理之間的迎面碰撞(head-to-h(huán)ead collisions),并實現(xiàn)其運動的一致性和可預(yù)測性。例如,在 Kiva 倉庫系統(tǒng)中,我們可以沿著存儲位置之間的狹窄通道設(shè)計高速公路,如圖2中的箭頭所示。我們已經(jīng)在模擬的 Kiva 倉庫系統(tǒng)中證明,這樣的高速公路能夠顯著加速 MAPF 方法,同時保持期望的 MAPF 解決方案成本的有限次優(yōu)性。 TAPF 和 PERR 例子的問題結(jié)構(gòu)也可以利用相同的方法。在可行性研究中,我們還開發(fā)了與用戶提供公路相媲美的自動生成公路的方法。
5 解決不完美的規(guī)劃執(zhí)行能力
  最先進(jìn)的 MAPF 或 TAPF 方法可以在合理的計算時間內(nèi)為數(shù)百個代理找到最佳的或者在用戶提供的次優(yōu)性保證下的不會發(fā)生碰撞的路徑。它們甚至在雜亂而緊湊的環(huán)境中也能正常工作,如Kiva 倉庫系統(tǒng)。然而,代理通常具有不完美的規(guī)劃執(zhí)行能力,并且不能完美地同步它們的運動,這可以導(dǎo)致頻繁的重新規(guī)劃并浪費時間。因此,我們提出了一個框架,使用一個簡單的時間網(wǎng)絡(luò)來有效地后期處理 MAPF 解決方案并創(chuàng)建一個規(guī)劃執(zhí)行安排,這適用于非完整機(jī)器人(non-h(huán)olonomic robot),考慮到它們的最大的平移和旋轉(zhuǎn)速度,提供了一個機(jī)器人之間安全距離和松弛邊界(定義為最新和最早進(jìn)入時間的地點的差異)的保證,以緩解不完美的規(guī)劃執(zhí)行并避免在許多情況下的時間密集的重新規(guī)劃[Honig ¨ et al., 2016]。這個框架已經(jīng)在仿真和真實機(jī)器人中得到評估。TAPF 和 PERR 方法也可以在同一框架中應(yīng)用。未來工作中要解決的問題包括增加用戶提供的安全距離、額外的運動約束、不確定性規(guī)劃和重新規(guī)劃。
6 結(jié)論
  我們討論了四個研究方向,以解決當(dāng)將 MAPF 方法推廣到實際場景中和探索問題結(jié)構(gòu)或現(xiàn)有 MAPF 方法時出現(xiàn)的問題。我們的目標(biāo)是為在 MAPF 領(lǐng)域工作的研究人員指出有趣的研究方向。

 


 

12下一頁

網(wǎng)友評論
文明上網(wǎng),理性發(fā)言,拒絕廣告

相關(guān)資訊

關(guān)注官方微信

手機(jī)掃碼看新聞