日韩成人激情_欧美黑人xxx_国产一区二精品区在线_精品在线一区_97成人资源_久久久久久一区

多代理路徑尋找（Multi－agent path finding／MAPF）已在人工智能、機(jī)器人、理論計(jì)算機(jī)科學(xué)和實(shí)際操作研究中得到大量的研究。本文討論了在將MAPF方法推廣到實(shí)際場(chǎng)景時(shí)出現(xiàn)的問(wèn)題與解決這些問(wèn)題的四個(gè)研究方向。我們強(qiáng)調(diào)的是解決這些問(wèn)題的重要性，而不是為MAPF問(wèn)題的標(biāo)準(zhǔn)模型開(kāi)發(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）。現(xiàn)有的 MAPF 使用的方法包括：從可滿足性減少問(wèn)題（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í)際場(chǎng)景時(shí)出現(xiàn)的各種問(wèn)題，包括 Kiva（Amazon Robotics）倉(cāng)庫(kù)系統(tǒng)［Wurman et al．， 2008］（圖1）和自動(dòng)飛行器牽引車［Morris et al．， 2016］。這些問(wèn)題可以分為兩個(gè)一般問(wèn)題：

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

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

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

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

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