路徑規(guī)劃概述課件講解

《車載智能技術(shù)》

無人駕駛汽車路徑規(guī)劃-路徑規(guī)劃概述主講人：黃侃江西交通職業(yè)技術(shù)學(xué)院路徑規(guī)劃概述路徑規(guī)劃是指在模型化的環(huán)境中按照一定的評價(jià)標(biāo)準(zhǔn)規(guī)劃出一條從起始狀態(tài)到目標(biāo)狀態(tài)的可行路徑。根據(jù)對環(huán)境信息的把握程度，路徑規(guī)劃可分為兩類:基于環(huán)境信息已知的全局路徑規(guī)劃，又稱為靜態(tài)規(guī)劃或離散規(guī)劃；基于傳感器信息的局部路徑規(guī)劃，又稱為動態(tài)規(guī)劃或在線規(guī)劃。兩者的主要區(qū)別在于:前者在規(guī)劃時(shí)沒有考慮環(huán)境的現(xiàn)場約束，如障礙物的形狀和位置、道路的寬度、道路的曲率半徑等；后者通過傳感器設(shè)備實(shí)時(shí)獲取周圍環(huán)境信息，

除了周圍障礙物的形狀、位置信息與道路的形狀信息外，還包括交通信號、車輛自身的行駛狀態(tài)等。路徑規(guī)劃概述路徑規(guī)劃的核心就是算法的設(shè)計(jì)，從傳統(tǒng)算法到智能算法，路徑規(guī)劃技術(shù)已經(jīng)得到了極大的發(fā)展。智能仿生算法是受自然界的啟發(fā)，通過模擬自然生物的行為規(guī)律從而實(shí)現(xiàn)優(yōu)化目標(biāo)的目的。目前智能仿生算法有蟻群算法、神經(jīng)網(wǎng)絡(luò)算法與遺傳算法等。路徑規(guī)劃概述蟻群算法(antcolonyoptimization，ACO)是一種迭代尋優(yōu)算法，其原理啟發(fā)于蟻群覓食的群落行為。螞蟻在覓食過程中會在道路上留下一定濃度的信息素，并會選擇信息素較多的路徑行走，在相同時(shí)間內(nèi)最短路徑上螞蟻經(jīng)過的次數(shù)最多，這條路徑含有的信息素最多，從而得出一條最佳路徑。該算法模擬蟻群覓食這一過程，其優(yōu)點(diǎn)是可以進(jìn)行全局尋優(yōu)，并且可以進(jìn)行并行計(jì)算，方便計(jì)算機(jī)實(shí)現(xiàn)。其缺點(diǎn)在于計(jì)算量大，并且容易陷入局部最優(yōu)解。1、蟻群算法路徑規(guī)劃概述神經(jīng)網(wǎng)絡(luò)算法是一種表現(xiàn)很優(yōu)秀的仿生智能算法，在人工智能領(lǐng)域中有著很廣泛的應(yīng)用。其思想主要來自生物神經(jīng)網(wǎng)絡(luò)行為，可用于實(shí)現(xiàn)分布式并行信息處理。神經(jīng)網(wǎng)絡(luò)具有非常優(yōu)秀的學(xué)習(xí)能力，而且學(xué)習(xí)能力魯棒性強(qiáng)。但是將其運(yùn)用于路徑規(guī)劃時(shí)，效果并不理想，因?yàn)閺?fù)雜的環(huán)境很難用公式進(jìn)行描述。不過，將該算法與其他算法結(jié)合用于路徑規(guī)劃卻是一個很好的嘗試。2、神經(jīng)網(wǎng)絡(luò)算法路徑規(guī)劃概述遺傳算法是一種應(yīng)用廣泛的智能算法，是人工智能領(lǐng)域的一個重要分支。算法思想來源于達(dá)爾文生物進(jìn)化論中的遺傳選擇和優(yōu)勝劣汰的自然法則，是一種迭代求解的優(yōu)化算法。其通過建立與基因遺傳學(xué)原理相似的數(shù)學(xué)模型來模擬基因的交叉、變異、選擇、適者生存的過程來解決問題。遺傳算法最大的優(yōu)點(diǎn)是可以通過與其他算法相結(jié)合來進(jìn)行迭代尋優(yōu)。3、遺傳算法知識拓展路徑規(guī)劃的主體是路徑計(jì)算，即規(guī)劃一條從起始地到目的地的一條合理路徑，路徑計(jì)算采用的算法是A*算法，實(shí)現(xiàn)A*算法還需要一些輔助步驟，以提高程序運(yùn)行的效率。因此在內(nèi)部把路徑規(guī)劃模塊細(xì)分為路徑計(jì)算模塊、內(nèi)存管理模塊、數(shù)據(jù)緩沖模塊和快速查表模塊，其主體是路徑計(jì)算模塊，其他模塊處于從屬地位，也就是說，其他模塊是為計(jì)算模塊提供輔助支持。路徑計(jì)算模塊需要實(shí)現(xiàn)起始點(diǎn)\目的地的定位、數(shù)據(jù)初始化、路徑計(jì)算等功能。知識拓展在路徑計(jì)算過程，需要維護(hù)一個Open表和Close表。當(dāng)擴(kuò)展一個節(jié)點(diǎn)的時(shí)候，需要把與該節(jié)點(diǎn)相鄰接的節(jié)點(diǎn)放入Open表，而把該節(jié)點(diǎn)放入Close表，因此會頻繁地從內(nèi)存區(qū)域申請小塊內(nèi)存以存放節(jié)點(diǎn)信息到Open表中，如果使用默認(rèn)的系統(tǒng)的內(nèi)存管理，會造成系統(tǒng)性能下降。因此要實(shí)現(xiàn)自己的內(nèi)存管理，內(nèi)存管理模塊主要實(shí)現(xiàn)一個內(nèi)存池，該內(nèi)存池對內(nèi)存分配、釋放以及回收進(jìn)行管理，以提高程序運(yùn)行的效率?！痢痢林R拓展全國的道路網(wǎng)分割成相同大小的區(qū)域（塊），路徑規(guī)劃時(shí)可以分批次加載路網(wǎng)數(shù)據(jù)，以避免一次性加載所有道路的