[發(fā)明專利]路徑規(guī)劃方法、裝置、計(jì)算機(jī)設(shè)備和存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 201711461936.4
• 申請(qǐng)日: 2017-12-28
• 公開（公告）號(hào): CN109975748B
• 公開（公告）日: 2021-11-26
• 發(fā)明（設(shè)計(jì)）人: 張鑫;朱逸;王克己;譚凱田;劉暢
• 申請(qǐng)（專利權(quán)）人: 騰訊科技（深圳）有限公司
• 主分類號(hào): G01S5/02
• 分類號(hào): G01S5/02;G01C21/20
• 代理公司: 廣州華進(jìn)聯(lián)合專利商標(biāo)代理有限公司 44224
• 代理人: 何平;鄧云鵬

1.一種路徑規(guī)劃方法，所述方法包括：

獲取待規(guī)劃空間的路網(wǎng)數(shù)據(jù)，所述路網(wǎng)數(shù)據(jù)包括待規(guī)劃空間的多個(gè)路徑；

獲取多個(gè)候選路徑集合，所述各個(gè)候選路徑集合根據(jù)所述待規(guī)劃空間的路徑組成；

根據(jù)所述候選路徑集合內(nèi)部各個(gè)路徑的重復(fù)路段計(jì)算得到所述各個(gè)候選路徑集合對(duì)應(yīng)的冗余參數(shù)；

根據(jù)所述候選路徑集合內(nèi)部各個(gè)路徑的覆蓋路段計(jì)算得到所述各個(gè)候選路徑集合對(duì)應(yīng)的覆蓋參數(shù)；

根據(jù)所述候選路徑集合對(duì)應(yīng)的冗余參數(shù)、覆蓋參數(shù)以及適應(yīng)度算法得到所述候選路徑集合對(duì)應(yīng)的適應(yīng)度，其中，所述適應(yīng)度算法中，適應(yīng)度與所述冗余參數(shù)呈負(fù)相關(guān)關(guān)系以及適應(yīng)度與所述覆蓋參數(shù)呈正相關(guān)關(guān)系；

根據(jù)所述各個(gè)候選路徑集合對(duì)應(yīng)的適應(yīng)度篩選所述候選路徑集合得到目標(biāo)路徑集合；

根據(jù)所述目標(biāo)路徑集合進(jìn)行進(jìn)化處理得到進(jìn)化路徑集合；

將滿足預(yù)設(shè)規(guī)劃條件的進(jìn)化路徑集合對(duì)應(yīng)的路徑作為規(guī)劃路徑。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述獲取多個(gè)候選路徑集合的步驟包括：

從所述待規(guī)劃空間獲取當(dāng)前路徑；

獲取所述當(dāng)前路徑的端點(diǎn)，獲取與所述端點(diǎn)連接的延長路段；

將所述延長路段與所述當(dāng)前路徑進(jìn)行拼接得到延長后的當(dāng)前路徑；

返回所述獲取所述當(dāng)前路徑的端點(diǎn)的步驟進(jìn)行迭代延長，直至滿足第一預(yù)設(shè)條件，所述第一預(yù)設(shè)條件包括迭代延長的次數(shù)大于第一預(yù)設(shè)值、迭代延長后的當(dāng)前路徑長度大于預(yù)設(shè)長度以及不存在與迭代延 長后的當(dāng)前路徑的端點(diǎn)連接的路徑中的至少一種；

將迭代延長后的當(dāng)前路徑作為組成所述候選路徑集合的路徑。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述候選路徑集合對(duì)應(yīng)的冗余參數(shù)、覆蓋參數(shù)以及適應(yīng)度算法得到所述候選路徑集合對(duì)應(yīng)的適應(yīng)度包括：

計(jì)算冗余參數(shù)與對(duì)應(yīng)的參數(shù)值的乘積，以及計(jì)算覆蓋參數(shù)與對(duì)應(yīng)的參數(shù)值的乘積；所述冗余參數(shù)對(duì)應(yīng)的參數(shù)值為負(fù)數(shù)，所述覆蓋參數(shù)對(duì)應(yīng)的參數(shù)值為正數(shù)；

將計(jì)算得到的乘積進(jìn)行求和計(jì)算，得到所述候選路徑集合對(duì)應(yīng)的適應(yīng)度。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述各個(gè)候選路徑集合對(duì)應(yīng)的適應(yīng)度篩選所述候選路徑集合得到目標(biāo)路徑集合的步驟包括：

對(duì)所述各個(gè)候選路徑集合對(duì)應(yīng)的適應(yīng)度進(jìn)行統(tǒng)計(jì)，得到總適應(yīng)度；

根據(jù)所述候選路徑集合對(duì)應(yīng)的適應(yīng)度以及所述總適應(yīng)度計(jì)算得到所述各個(gè)候選路徑集合對(duì)應(yīng)的候選概率；

根據(jù)所述各個(gè)候選路徑集合對(duì)應(yīng)的候選概率篩選所述候選路徑集合得到目標(biāo)路徑集合。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述根據(jù)所述各個(gè)候選路徑集合對(duì)應(yīng)的候選概率篩選所述候選路徑集合得到目標(biāo)路徑集合的步驟包括：

獲取選取的數(shù)值范圍；

根據(jù)所述候選路徑集合對(duì)應(yīng)的候選概率從所述數(shù)值范圍內(nèi)為所述候選路徑集合分配對(duì)應(yīng)的數(shù)值區(qū)域；

在所述數(shù)值范圍內(nèi)產(chǎn)生隨機(jī)數(shù)；

將所述隨機(jī)數(shù)所在數(shù)值區(qū)域?qū)?yīng)的候選路徑集合作為目標(biāo)路徑集合。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述預(yù)設(shè)規(guī)劃條件包括適應(yīng)度最大，所述將滿足預(yù)設(shè)規(guī)劃條件的進(jìn)化路徑集合對(duì)應(yīng)的路徑作為規(guī)劃路徑的步驟包括：

從所述進(jìn)化路徑集合中選取適應(yīng)度最大的進(jìn)化路徑集合對(duì)應(yīng)的路徑作為規(guī)劃路徑。

7.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述各個(gè)候選路徑集合對(duì)應(yīng)的適應(yīng)度篩選所述候選路徑集合得到目標(biāo)路徑集合包括：

將適應(yīng)度排序在預(yù)設(shè)排序內(nèi)的候選路徑集合作為目標(biāo)路徑集合。