《人工智能控制技術(shù)》 課件 chap8-無(wú)人機(jī)路徑規(guī)劃案例

《人工智能控制技術(shù)》無(wú)人機(jī)三維最優(yōu)路徑規(guī)劃實(shí)例無(wú)人機(jī)路徑規(guī)劃簡(jiǎn)介無(wú)人機(jī)的應(yīng)用越來(lái)越廣泛,在多個(gè)場(chǎng)合都有所應(yīng)用,比如戰(zhàn)場(chǎng)上可以偵查甚至攻擊，搶險(xiǎn)救災(zāi)中可以察看災(zāi)情情況，農(nóng)業(yè)上可以作為噴灑農(nóng)藥、檢察作物生長(zhǎng)等等，如果提高無(wú)人機(jī)的智能性，讓其自動(dòng)完成一些人物，就需要用到路徑規(guī)劃的問(wèn)題。路徑規(guī)劃是智能控制中的一個(gè)重要組成部分，是動(dòng)態(tài)規(guī)劃的重要應(yīng)用。隨著無(wú)人機(jī)系統(tǒng)的功能越來(lái)越強(qiáng)大，其操縱越來(lái)越復(fù)雜，而現(xiàn)代飛行任務(wù)的難度及強(qiáng)度也在不斷增加，良好的三維路徑規(guī)劃成為提高無(wú)人機(jī)系統(tǒng)任務(wù)完成質(zhì)量和生存概率的重要途徑之一。無(wú)人機(jī)路徑規(guī)劃簡(jiǎn)介路徑規(guī)劃的算法有許多種，其中強(qiáng)化學(xué)習(xí)算法是非常有效的路徑規(guī)劃算法，所需要的的前提條件少，智能性高，規(guī)劃效果好。基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃方法不僅具有與隨機(jī)線路圖法相似的在規(guī)劃時(shí)間和航跡質(zhì)量之間進(jìn)行折中的能力，而且其本身具有一定的魯棒性和對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)能力。目前，強(qiáng)化學(xué)習(xí)方法已經(jīng)在智能機(jī)器人導(dǎo)航、路徑規(guī)劃和運(yùn)動(dòng)控制領(lǐng)域取得了許多成功的應(yīng)用。無(wú)人機(jī)路徑規(guī)劃簡(jiǎn)介本章以無(wú)人機(jī)為例，采用Q-Learning算法實(shí)現(xiàn)三維路徑規(guī)劃，規(guī)劃目標(biāo)為：1．通過(guò)C++編寫一段程序，采用Q-learning算法實(shí)現(xiàn)無(wú)人機(jī)的智能三維路徑規(guī)劃。2．定義無(wú)人機(jī)類，包含飛行半徑、最大平飛速度、最小平飛速度、垂直飛行速度、最大飛行高度、最小飛行高度、最大飛行過(guò)載等屬性。3．定義仿真環(huán)境中兩種環(huán)境類，自然環(huán)境與靜態(tài)障礙物，其中自然環(huán)境類包括地形、風(fēng)速、風(fēng)向、溫度、光照等屬性，障礙物包括位置、大小、輪廓頂點(diǎn)、移動(dòng)速度、移動(dòng)路線等屬性。定義多種相關(guān)的環(huán)境類時(shí)，使用繼承與多態(tài)的方法。4．通過(guò)算法和代碼實(shí)現(xiàn)無(wú)人機(jī)自動(dòng)分辨最佳路線，要求避開(kāi)障礙物，并根據(jù)具體環(huán)境分析出適合的路線，最后找出一條最佳路線完成目標(biāo)，即到達(dá)終點(diǎn)。無(wú)人機(jī)路徑規(guī)劃Q-Learning算法原理無(wú)人機(jī)的三維路徑規(guī)劃是在綜合考慮無(wú)人機(jī)的飛行時(shí)間、燃料消耗、外界威脅等因素的前提下，為無(wú)人機(jī)規(guī)劃出一條最優(yōu)或者是最滿意的三維飛行航跡，以保證飛行任務(wù)的圓滿完成。無(wú)人機(jī)通過(guò)Agent與環(huán)境交互，獲得航跡過(guò)程的本質(zhì)是馬爾可夫決策過(guò)程（Markovdecisionprocess，MDP），無(wú)人機(jī)的下一個(gè)空間狀態(tài)只與當(dāng)前的狀態(tài)信息有關(guān)，與之前的信息狀態(tài)無(wú)關(guān)，即無(wú)人機(jī)航跡規(guī)劃的過(guò)程具有馬爾可夫性。無(wú)人機(jī)路徑規(guī)劃Q-Learning算法原理馬爾可夫決策過(guò)程（Markovdecisionprocess，MDP），MDP

由＜S，A，P，R，γ＞五個(gè)元素構(gòu)成：1．S表示空間狀態(tài)的集合，s∈S，st

表示t時(shí)刻的空間狀態(tài)；2．A表示動(dòng)作策略的集合，a∈A，at

表示t時(shí)刻的動(dòng)作策略；3．P表示狀態(tài)轉(zhuǎn)移概率，表示當(dāng)前狀態(tài)s下，經(jīng)過(guò)動(dòng)作策略a后，狀態(tài)變?yōu)閟'的概率；4．R表示環(huán)境根據(jù)智能體的狀態(tài)與動(dòng)作，給予智能體的獎(jiǎng)勵(lì)，是獎(jiǎng)勵(lì)取值的集合；5．γ為“折扣”，表示后續(xù)策略對(duì)當(dāng)前狀態(tài)的影響，γ為0表示只關(guān)心當(dāng)前獎(jiǎng)勵(lì)，γ越大表示對(duì)未來(lái)獎(jiǎng)勵(lì)越看重。無(wú)人機(jī)路徑規(guī)劃Q-Learning算法原理

無(wú)人機(jī)路徑規(guī)劃Q-Learning算法原理基于Q-Learning學(xué)習(xí)的無(wú)人機(jī)路徑規(guī)劃方法是基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃領(lǐng)域最重要的方法之一，仍然是基于預(yù)先定義的代價(jià)函數(shù)生成一條具有最小代價(jià)的航跡。其規(guī)劃過(guò)程中沒(méi)有考慮諸如無(wú)人機(jī)的最大爬升、下降率和最小轉(zhuǎn)彎半徑等航跡約束條件，使其存在2個(gè)重要的缺點(diǎn)：1．算法獲得的最小代價(jià)航跡不一定滿足實(shí)際要求，甚至對(duì)無(wú)人機(jī)來(lái)說(shuō)根本無(wú)法飛行實(shí)施；2．算法的規(guī)劃空間離散化過(guò)程缺少依據(jù)，往往采用較小的離散化步長(zhǎng)以保證離散化過(guò)程的合理性，這使得最終離散規(guī)劃問(wèn)題具有很大的搜索空間，因此其只適用于二維平面內(nèi)的航跡規(guī)劃問(wèn)題。當(dāng)這類算法在無(wú)人機(jī)路徑規(guī)劃問(wèn)題中應(yīng)用時(shí)，由于其無(wú)法充分利用無(wú)人機(jī)的三維飛行能力，故其規(guī)劃獲得的航跡從根本上說(shuō)就是次優(yōu)航跡。無(wú)人機(jī)路徑規(guī)劃Q-Learning算法原理本文無(wú)人機(jī)最優(yōu)路徑規(guī)劃在現(xiàn)有的基于Q-Learning學(xué)習(xí)的航跡規(guī)劃算法的基礎(chǔ)上，設(shè)計(jì)出一種能夠有效完成無(wú)人機(jī)三維航跡規(guī)劃任務(wù)的路徑規(guī)劃方法。該方法利用無(wú)人機(jī)的航跡約束條件指導(dǎo)規(guī)劃空間離散化，不僅減小了最終離散規(guī)劃問(wèn)題的規(guī)模，也在一定程度上提高規(guī)劃獲得的優(yōu)化航跡的可用性。無(wú)人機(jī)三維路徑規(guī)劃實(shí)現(xiàn)過(guò)程無(wú)人機(jī)整個(gè)路徑規(guī)劃實(shí)現(xiàn)的流程無(wú)人機(jī)最優(yōu)路徑規(guī)劃流程基于Q-learning的三維模型創(chuàng)建要實(shí)現(xiàn)基于Q-learing的無(wú)人機(jī)智能航線規(guī)劃，需建立回報(bào)獎(jiǎng)勵(lì)地圖，本章采用對(duì)空間進(jìn)行柵格化，將模擬的現(xiàn)實(shí)空間柵格化為M*M*M的三維數(shù)組模型，對(duì)數(shù)組中每一柵格進(jìn)行賦值處理，賦上用環(huán)境回報(bào)函數(shù)所求得的回報(bào)獎(jiǎng)勵(lì)，完成對(duì)現(xiàn)實(shí)空間的模擬。基于Q-learning的三維模型創(chuàng)建在程序設(shè)計(jì)的無(wú)人機(jī)類中，需要包含飛行半徑、最大平飛速度、最小平飛速度、垂直飛行速度、最大飛行高度、最小飛行高度、最大飛行過(guò)載這些屬性。其中飛行半徑用無(wú)人機(jī)最大可以走的格子數(shù)來(lái)實(shí)現(xiàn)；最大平飛速度和最小平飛速度用于在順風(fēng)和逆風(fēng)環(huán)境中與風(fēng)速相結(jié)合在設(shè)置的獎(jiǎng)勵(lì)方程中求環(huán)境的獎(jiǎng)勵(lì)；垂直飛行速度用于在高山環(huán)境這類在現(xiàn)實(shí)中需要做出垂直高度調(diào)整的環(huán)境中與風(fēng)速結(jié)合代入設(shè)置的獎(jiǎng)勵(lì)方程中求環(huán)境的獎(jiǎng)勵(lì)；最大飛行高度和最小飛行高度用于與每個(gè)環(huán)境的高度，障礙物的大小作比較，考慮到現(xiàn)實(shí)情況，當(dāng)最大飛行高度低于環(huán)境高度或最小飛行高度高于環(huán)境高度時(shí)，在該環(huán)境處的會(huì)為很小的負(fù)值，表示無(wú)法通過(guò)。基于Q-learning的三維模型創(chuàng)建在程序設(shè)計(jì)的自然環(huán)境類中，需要包含地形、風(fēng)速、風(fēng)向、溫度、光照、環(huán)境獎(jiǎng)勵(lì)這些屬性，并且對(duì)每一種環(huán)境設(shè)置環(huán)境獎(jiǎng)勵(lì)方程，該方程由無(wú)人機(jī)中有影響的環(huán)境類屬性組成，用于求該環(huán)境的回報(bào)獎(jiǎng)勵(lì)。其中，地形主要參數(shù)設(shè)置為高度，考慮到實(shí)際地形作為判斷無(wú)人機(jī)能否通過(guò)該環(huán)境的首要因素；風(fēng)向和風(fēng)向結(jié)合，風(fēng)速分為順風(fēng)和逆風(fēng)兩種，用1來(lái)表示順風(fēng)，-1來(lái)表示逆風(fēng)，作為風(fēng)速的系數(shù)，風(fēng)速大小用絕對(duì)值的大小來(lái)體現(xiàn)；溫度和光照也作為了環(huán)境獎(jiǎng)勵(lì)方程中的一部分?；赒-learning的三維模型創(chuàng)建在程序設(shè)計(jì)的障礙物類中要設(shè)置位置、大小、輪廓頂點(diǎn)等屬性。其中位置用x,y,z來(lái)表示，用于確定障礙物在設(shè)置的地圖中的坐標(biāo)；大小類似于環(huán)境類中的地形，將它設(shè)置為高度；輪廓頂點(diǎn)則用于表示該障礙物會(huì)占用他自身坐標(biāo)周圍多少個(gè)格子數(shù)。基于Q-learning的三維模型創(chuàng)建在定義多種相關(guān)的環(huán)境類時(shí)需要用到繼承和多態(tài)。在定義自然環(huán)境類時(shí)，首先定義一個(gè)基類，包含要求的各種基本屬性和計(jì)算環(huán)境回報(bào)獎(jiǎng)勵(lì)的虛函數(shù)，在這之后定義環(huán)境類基類的七個(gè)派生類，分別是高山環(huán)境類，用以模擬地形過(guò)高的環(huán)境；平原環(huán)境類，用以模擬地形過(guò)低的環(huán)境；順風(fēng)環(huán)境類，用以模擬風(fēng)向?yàn)檎较颍L(fēng)速系數(shù)為正值的環(huán)境；逆風(fēng)環(huán)境類，用以模擬風(fēng)向?yàn)榉捶较?，風(fēng)速系數(shù)為負(fù)值的環(huán)境；沙漠環(huán)境類，用以模擬溫度過(guò)高，光照過(guò)強(qiáng)的環(huán)境；極地環(huán)境類，用以模擬溫度過(guò)低，光照過(guò)弱的環(huán)境；光照異常環(huán)境類，用以模擬各處柵格的光照差異過(guò)大的環(huán)境。在每個(gè)派生類中，都依據(jù)基類中定義的虛函數(shù)進(jìn)行了函數(shù)的重載，以實(shí)現(xiàn)在每種派生類中由于模擬的環(huán)境的不同導(dǎo)致的對(duì)環(huán)境獎(jiǎng)勵(lì)回報(bào)方程的不同寫法，從而實(shí)現(xiàn)繼承和多態(tài)。訓(xùn)練過(guò)程Q-table是一張表，存儲(chǔ)著無(wú)人機(jī)的每一個(gè)狀態(tài)下執(zhí)行不同行為時(shí)的預(yù)期獎(jiǎng)勵(lì)。在路徑規(guī)劃訓(xùn)練中，對(duì)于固定的一張地圖，無(wú)人機(jī)的狀態(tài)可以由向量（x，y，z）表示其位置，現(xiàn)實(shí)世界是不變的，所以不算作狀態(tài)；在程序設(shè)計(jì)中，數(shù)組Q-tablexyzi代表智能體在（x，y）位置下執(zhí)行動(dòng)作i時(shí)的預(yù)期獎(jiǎng)勵(lì)，由于是三維空間，i有26個(gè)值。訓(xùn)練過(guò)程優(yōu)化決策的過(guò)程由馬爾科夫決策過(guò)程對(duì)Q-table進(jìn)行優(yōu)化。該過(guò)程的核心方程如公式：即：執(zhí)行一個(gè)策略之后無(wú)人機(jī)從x,y,z

移動(dòng)到x1,y1,z1

點(diǎn)，那么在狀態(tài)x,y,z

下執(zhí)行動(dòng)作i

的獎(jiǎng)勵(lì)就是：下一個(gè)行為本身的收益+走到下一個(gè)方格之后，最好的預(yù)期收益。上式中，rate為一個(gè)比例系數(shù)，決定了預(yù)期收益的權(quán)重。本算法中取0.8。訓(xùn)練過(guò)程貪心系數(shù)Greedy=0.2。Q-learning本質(zhì)上是貪心算法。但是如果每次都取預(yù)期獎(jiǎng)勵(lì)最高的行為去做，那么在訓(xùn)練過(guò)程中可能無(wú)法探索其他可能的行為，甚至?xí)M(jìn)入“局部最優(yōu)”，無(wú)法完成游戲。所以，由貪心系數(shù)使得無(wú)人機(jī)有Greedy的概率采取最優(yōu)行為，也有一定概率探索新的路徑。訓(xùn)練過(guò)程

訓(xùn)練過(guò)程在巡線訓(xùn)練中，無(wú)人機(jī)經(jīng)過(guò)的每一柵格都有由環(huán)境所得的獎(jiǎng)勵(lì)作為該位置的分?jǐn)?shù)。按照如上的訓(xùn)練策略，本例在最終測(cè)試前進(jìn)行3000次訓(xùn)練，以得到盡可能準(zhǔn)確的Q-table表,使得無(wú)人機(jī)在最終測(cè)試時(shí)能夠走最優(yōu)航線。通過(guò)訓(xùn)練得到盡可能準(zhǔn)確的Q-table表以后，就可以測(cè)試驗(yàn)證訓(xùn)練結(jié)果，將最終走出的最優(yōu)路徑輸出。由于可能遇到局部最優(yōu)的問(wèn)題，所以如果最大的Q-table值無(wú)法走出，就原路返回，尋找第二大的Q-table值，如此直到走出循環(huán)，從而解決局部最優(yōu)的問(wèn)題。其次需要注意的問(wèn)題是Q-table數(shù)組要足夠大，否則將無(wú)法完成訓(xùn)練。路徑規(guī)劃實(shí)現(xiàn)結(jié)果由于算法得出的結(jié)果與訓(xùn)練次數(shù)有關(guān)，訓(xùn)練次數(shù)越多，其規(guī)劃最優(yōu)路線的效果越好，所以本例程序中設(shè)定訓(xùn)練次數(shù)為3000次。每一次訓(xùn)練中還包括執(zhí)行步數(shù)，即算法做出的決策及其相應(yīng)的獎(jiǎng)勵(lì)，本例執(zhí)行步驟設(shè)置了上限80，每次訓(xùn)練走到終點(diǎn)或者走夠80步時(shí)結(jié)束，如圖8-2所示。每次飛行中的飛行方向以及經(jīng)過(guò)地方對(duì)應(yīng)的位置坐標(biāo)可以記錄，如下一頁(yè)圖像所示。路徑規(guī)劃實(shí)現(xiàn)結(jié)果訓(xùn)練步數(shù)結(jié)果飛行路徑記錄路徑