[發(fā)明專利]一種基于進(jìn)化算法的多智能體路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202211085630.4
• 申請(qǐng)日: 2022-09-06
• 公開(kāi)（公告）號(hào): CN115438860A
• 公開(kāi)（公告）日: 2022-12-06
• 發(fā)明（設(shè)計(jì)）人: 黃婷;劉靜;劉曉濤;莊峰
• 申請(qǐng)（專利權(quán)）人: 西安電子科技大學(xué)廣州研究院
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06N3/00
• 代理公司: 廣州大象飛揚(yáng)知識(shí)產(chǎn)權(quán)代理有限公司 44745
• 代理人: 李靜

本發(fā)明涉及一種路徑規(guī)劃方法，具體的說(shuō)是一種基于進(jìn)化算法的多智能體路徑規(guī)劃方法，包括實(shí)施步驟如下：A.計(jì)算最優(yōu)單智能體路徑候選節(jié)點(diǎn)；B.構(gòu)建進(jìn)化算法初始種群；C.評(píng)估種群中個(gè)體的適應(yīng)值；D.執(zhí)行選擇算子；E.執(zhí)行交叉算子；F.執(zhí)行變異算子；G.執(zhí)行沖突搜索操作；H.執(zhí)行沖突消解操作；I.執(zhí)行存檔更新操作；J.當(dāng)滿足停止條件時(shí)，提供存檔中的最佳個(gè)體，即無(wú)沖突且成本最低的多智能體路徑集合。發(fā)明采用進(jìn)化算法啟發(fā)式地規(guī)劃無(wú)沖突多智能體路徑集合，求解速度快，計(jì)算效率高，本方法采用基于種群的進(jìn)化算法同時(shí)搜索多組多智能體路徑集合，算法不易落入局部最優(yōu)，能夠在可控的時(shí)間內(nèi)不斷降低多智能體路徑集合成本。

技術(shù)領(lǐng)域

本發(fā)明涉及一種路徑規(guī)劃方法，具體為一種基于進(jìn)化算法的多智能體路徑規(guī)劃方法，屬于路徑規(guī)劃技術(shù)領(lǐng)域。

背景技術(shù)

多智能體路徑規(guī)劃是路徑規(guī)劃的主要研究?jī)?nèi)容之一。單個(gè)智能體路徑是從起點(diǎn)位置和終點(diǎn)位置節(jié)點(diǎn)的柵格地圖節(jié)點(diǎn)序列；多智能體路徑規(guī)劃是由單個(gè)智能體路徑集合構(gòu)成，要求智能體的路徑集合之間不存在沖突。

解決多智能體路徑規(guī)劃問(wèn)題的傳統(tǒng)方法主要包括單智能體路徑協(xié)同方法、基于優(yōu)先級(jí)搜索的多智能體路徑規(guī)劃方法、和基于沖突搜索的多智能體路徑規(guī)劃方法。在單智能體路徑協(xié)同方法中，常用A*作為一種高效的啟發(fā)式單智能體路徑規(guī)劃方法，沿著單智能體的最優(yōu)路徑，同步拓展多個(gè)智能體的所有節(jié)點(diǎn)，以期獲得無(wú)沖突路徑。然而但智能體路徑協(xié)同方法隨著智能體數(shù)量和地圖空間的增加，A*算法搜索空間呈指數(shù)級(jí)增加，因此該方法僅適用于解決規(guī)模較小的多智能體路徑問(wèn)題，且該方法是不完備且無(wú)法保證最優(yōu)性。基于優(yōu)先級(jí)搜索的多智能體路徑規(guī)劃方法為智能體指定優(yōu)先級(jí)，低優(yōu)先級(jí)個(gè)體避免與高優(yōu)先級(jí)智能體產(chǎn)生沖突，該方法是不完備且無(wú)法保證最優(yōu)性。基于沖突搜索的多智能體路徑規(guī)劃方法是主流的多智能體路徑規(guī)劃方法，其采用兩層交替路徑規(guī)劃構(gòu)造沖突樹(shù)。在高層搜索中檢測(cè)多個(gè)智能體之間的路徑?jīng)_突，在低層搜索中重新規(guī)劃滿足約束的單智能體路徑。如果在高層檢測(cè)到?jīng)_突，則拓展下層節(jié)點(diǎn)并添加約束。每次采用最佳路徑成本優(yōu)先的選擇方法，選擇路徑成本最小的節(jié)點(diǎn)進(jìn)行拓展。高層與低層算法交替搜索，直到拓展到無(wú)沖突的子節(jié)點(diǎn)，即為最終找到的最優(yōu)無(wú)沖突方案。基于沖突搜索的方法是完備的且能夠保證最優(yōu)性。由于無(wú)法獲知最優(yōu)路徑集合成本，最優(yōu)優(yōu)先搜索方式貪婪拓展約束節(jié)點(diǎn)能夠保證可行路徑集合的最優(yōu)性。但是，該方法存在兩個(gè)主要問(wèn)題：(1)雖然能夠保證首先找到無(wú)沖突路徑集合的最優(yōu)性，但隨著智能體數(shù)量和問(wèn)題規(guī)模的增加，無(wú)法保證算法的執(zhí)行時(shí)間，即在可接受的時(shí)間內(nèi)返回可使用的路徑集合，這是拓展至實(shí)際應(yīng)用的瓶頸問(wèn)題；(2)該方法采用增量式消解沖突，沖突樹(shù)中的每個(gè)節(jié)點(diǎn)僅消解一個(gè)沖突，每解決一個(gè)涉及N個(gè)智能體的沖突就需要拓展N個(gè)節(jié)點(diǎn)，因此需要占用大量的計(jì)算內(nèi)存保存沖突樹(shù)結(jié)構(gòu)，且容易陷入局部最優(yōu)，在無(wú)效分支上大量拓展節(jié)點(diǎn)。

傳統(tǒng)方法適用于智能體數(shù)量較少和地圖規(guī)模較小的問(wèn)題，在智能體數(shù)量較多和地圖規(guī)模較大的問(wèn)題中計(jì)算復(fù)雜度過(guò)高，以致在可接受的時(shí)間內(nèi)無(wú)法規(guī)劃出無(wú)沖突的智能體路徑集合。

有鑒于此特提出本發(fā)明。

發(fā)明內(nèi)容

本發(fā)明的目的就在于為了解決上述問(wèn)題而提供一種基于進(jìn)化算法的多智能體路徑規(guī)劃方法。

本發(fā)明通過(guò)以下技術(shù)方案來(lái)實(shí)現(xiàn)上述目的，一種基于進(jìn)化算法的多智能體路徑規(guī)劃方法，包括實(shí)施步驟如下：

A.計(jì)算最優(yōu)單智能體路徑候選節(jié)點(diǎn)；

B.構(gòu)建進(jìn)化算法初始種群；

C.評(píng)估種群個(gè)體的適應(yīng)值；

D.執(zhí)行選擇算子；

E.執(zhí)行交叉算子；

F.執(zhí)行變異算子；

G.執(zhí)行沖突搜索操作；

H.執(zhí)行沖突消解操作；

I.執(zhí)行存檔更新操作；