“優(yōu)化”是生活中經(jīng)常使用的詞：開(kāi)車時(shí)希望能在安全的前提下以最短時(shí)間到達(dá)目的地；雙11做功課考慮各種優(yōu)惠活動(dòng)，希望獲得最大優(yōu)惠；超市進(jìn)貨時(shí)需要考慮動(dòng)銷存，最大化提高物品周轉(zhuǎn)效率。 這些問(wèn)題都是“最優(yōu)化問(wèn)題”，也是數(shù)學(xué)建模中的典型問(wèn)題，是各大數(shù)學(xué)建模比賽里的常客。 優(yōu)化題型有三要素：決策變量、目標(biāo)函數(shù)、約束條件。 （1）決策變量：是決策者可以控制的因素，例如根據(jù)不同的實(shí)際問(wèn)題，決策變量可以選為產(chǎn)品的產(chǎn)量、物資的運(yùn)量及工作的天數(shù)等。 （2） 目標(biāo)函數(shù)：是以函數(shù)形式來(lái)表示決策者追求的目標(biāo)。例如目標(biāo)可以是利潤(rùn)最大或成本最小等。 （3） 約束條件：是決策變量需要滿足的限定條件。 歷年國(guó)賽優(yōu)化問(wèn)題： 優(yōu)化問(wèn)題的出發(fā)點(diǎn)是系統(tǒng)思維，其基本思路是在一定的約束條件下，保證各方面資源的合理分配， 最大限度地提升系統(tǒng)某一性能或系統(tǒng)整體性能，最終實(shí)現(xiàn)最理想結(jié)果。對(duì)于這類問(wèn)題，想要建立并求解數(shù)學(xué)模型，可以參考以下思路： （1）明確目標(biāo)，分析問(wèn)題背景，確定約束條件，搜集全面的客觀數(shù)據(jù)和信息。 （2）建立數(shù)學(xué)模型，構(gòu)建變量之間的數(shù)學(xué)關(guān)系，設(shè)立目標(biāo)函數(shù)。 （3）分析數(shù)學(xué)模型，綜合選擇最適合該模型的優(yōu)化方法。 （4）求解模型，通常借助計(jì)算機(jī)和數(shù)學(xué)分析軟件完成。 （5）對(duì)最優(yōu)解進(jìn)行檢驗(yàn)和實(shí)施。 PS.北太天元內(nèi)已有優(yōu)化工具箱optimization，可以調(diào)用工具箱解決優(yōu)化類問(wèn)題。 下面給大家分享幾種數(shù)學(xué)建模中常用優(yōu)化算法： 1、線性規(guī)劃 在人們的生產(chǎn)實(shí)踐中，經(jīng)常會(huì)遇到如何利用現(xiàn)有資源來(lái)安排生產(chǎn)，以取得最大經(jīng)濟(jì)效益的問(wèn)題。此類問(wèn)題構(gòu)成了運(yùn)籌學(xué)的一個(gè)重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(Linear Programming 簡(jiǎn)記 LP)則是數(shù)學(xué)規(guī)劃的一個(gè)重要分支。 1.1 用北太天元求解線性規(guī)劃問(wèn)題 北太天元內(nèi)已有優(yōu)化工具箱optimization，其中的linprog等相關(guān)函數(shù)可用于求解線性規(guī)劃問(wèn)題。 1.2 線性規(guī)劃特點(diǎn) 優(yōu)點(diǎn)： （1）作為經(jīng)營(yíng)管理決策中的數(shù)學(xué)手段，在現(xiàn)代決策中的應(yīng)用非常廣泛。 （2）有統(tǒng)一算法，任何線性規(guī)劃問(wèn)題都能求解，解決多變量最優(yōu)決策的方法。 （3）訓(xùn)練速度快。 （4）預(yù)測(cè)速度快，可以推廣到非常大的數(shù)據(jù)集，對(duì)稀疏數(shù)據(jù)也很有效。 缺點(diǎn)： （1）對(duì)于數(shù)據(jù)的準(zhǔn)確性要求高，只能對(duì)線性的問(wèn)題進(jìn)行規(guī)劃約束，而且計(jì)算量大。 1.3 相關(guān)問(wèn)題 運(yùn)輸問(wèn)題(產(chǎn)銷平衡)、指派問(wèn)題（匈牙利算法）、對(duì)偶理論與靈敏度分析、投資的收益和風(fēng)險(xiǎn)。 2、整數(shù)規(guī)劃 規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒(méi)有一種方法能有效地求解一切整數(shù)規(guī)劃。 2.1 用北太天元求解線性混合整數(shù)規(guī)劃問(wèn)題 可在北太天元內(nèi)調(diào)用優(yōu)化工具箱optimization，使用intlinprog等相關(guān)函數(shù)求解線性混合整數(shù)規(guī)劃問(wèn)題。 2.2 整數(shù)規(guī)劃的分類 如不加特殊說(shuō)明，一般指整數(shù)線性規(guī)劃。對(duì)于整數(shù)線性規(guī)劃模型大致可分為兩類： （1）變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。 （2）變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。 2.3 整數(shù)規(guī)劃特點(diǎn) 原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況： （1）原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 （2）整數(shù)規(guī)劃無(wú)可行解。 （3）有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。 整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。 2.4 求解方法分類 （1）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。 （2）割平面法—可求純或混合整數(shù)線性規(guī)劃。 （3）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：過(guò)濾隱枚舉法；分枝隱枚舉法。 （4）匈牙利法—解決指派問(wèn)題（“0-1”規(guī)劃特殊情形）。 （5）蒙特卡洛法—求解各種類型規(guī)劃。 3、非線性規(guī)劃 如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問(wèn)題為非線性規(guī)劃問(wèn)題。一般說(shuō)來(lái)，解非線性規(guī)劃要比解線性規(guī)劃問(wèn)題困難得多。而且，也不象線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒(méi)有適于各種問(wèn)題的一般算法，各個(gè)方法都有自己特定的適用范圍。 3.1 線性規(guī)劃與非線性規(guī)劃的區(qū)別 如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點(diǎn)上達(dá)到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點(diǎn)達(dá)到。 3.2 相關(guān)問(wèn)題 無(wú)約束問(wèn)題（一維搜索方法、二次插值法、無(wú)約束極值問(wèn)題的解法）、約束極值問(wèn)題（二次規(guī)劃、罰函數(shù)法）、飛行管理問(wèn)題 4、動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃（dynamic programming）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程（decisionprocess）最優(yōu)化的數(shù)學(xué)方法。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。 雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過(guò)程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。應(yīng)指出，動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。因此，在學(xué)習(xí)時(shí)，除了要對(duì)基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 5、多目標(biāo)規(guī)劃 多目標(biāo)規(guī)劃已經(jīng)應(yīng)用到科學(xué)的許多領(lǐng)域，包括工程、經(jīng)濟(jì)和物流，在兩個(gè)或更多沖突的目標(biāo)之間存在取舍時(shí)，需要采取最優(yōu)決策。 解決多目標(biāo)規(guī)劃問(wèn)題的方法： （1）將多目標(biāo)化為單目標(biāo) (給多個(gè)目標(biāo)賦予權(quán)重) （2）保持多目標(biāo)不變，根據(jù)自己的偏好選擇解 實(shí)際問(wèn)題中，目標(biāo)函數(shù)相互沖突是很常見(jiàn)的，例如購(gòu)買汽車時(shí)，要求花費(fèi)少且舒適度高或者要求性能好油耗低，這種問(wèn)題并沒(méi)有絕對(duì)最優(yōu)解（因?yàn)椴](méi)有確定多個(gè)目標(biāo)的權(quán)值），但是我們可以根據(jù)自己的需要選擇一個(gè)相對(duì)好的（達(dá)到我們想要的最佳平衡）。為了尋求這種“最佳平衡”，可以采用算法帕累托最優(yōu)（Pareto optimal）。 以上部分內(nèi)容引用公眾號(hào)“科研交流”，希望對(duì)大家有幫助，覺(jué)得有用就點(diǎn)個(gè)贊吧。小助手會(huì)不定期更新數(shù)學(xué)建模干貨，可以多多關(guān)注喲。
線性調(diào)頻信號(hào)是一種頻譜擴(kuò)展調(diào)制技術(shù)，在雷達(dá)等領(lǐng)域具有廣泛應(yīng)用，信號(hào)頻率是一個(gè)關(guān)于時(shí)間t的線性函數(shù)。線性調(diào)頻信號(hào)時(shí)域表達(dá)式如下：其中，T為采樣周期，K為線性調(diào)頻率，K=B/T，B為信號(hào)帶寬。基于北太天元仿真線性調(diào)頻信號(hào)如下：北太天元代碼如下：
clear
clc
close all
clf
tao=1e-5;%脈沖寬度
B=20e6;%帶寬20MHz
fs=2*B;%采樣頻率
Ts=1/fs;
K=B/tao;%調(diào)頻斜率
N=floor(tao/Ts);
% 線性調(diào)頻信號(hào)
t=linspace(-tao/2,tao/2,N);
st=exp(j*pi*K*t.*t);%線性調(diào)頻信號(hào)
figure(1)sst = real(st);
plot(t*1e5,sst);
title('線性調(diào)頻信號(hào)時(shí)域?qū)嵅?#39;);
f=linspace(-fs/2,fs/2,N);
load_plugin("fft")
sf=abs(fft(st));%線性調(diào)頻信號(hào)頻域信號(hào)
figure(2)
ssf = [sf(N/2+1:end),sf(1:N/2)];
plot(f*1e5,ssf);
title('線性調(diào)頻信號(hào)頻譜幅值');
figure(3)
plot(angle(st))
title('線性調(diào)頻信號(hào)相位');
17.1 原理 完整思想請(qǐng)看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言,，和其他的基于搜索的路徑規(guī)劃算法的區(qū)別僅在于啟發(fā)式函數(shù)的不同. 雙向A*則稍微復(fù)雜些，但可以簡(jiǎn)單理解為起始節(jié)點(diǎn)和終點(diǎn)同時(shí)將對(duì)方視為目標(biāo)節(jié)點(diǎn)，并按照A*的啟發(fā)式函數(shù)，相向生長(zhǎng)，當(dāng)兩者相遇時(shí)，則停止迭代，并分別往回追溯自己的父節(jié)點(diǎn)即可得到路徑。17.2 程序示例
16.1 原理 完整思想請(qǐng)看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言，，和其他的基于搜索的路徑規(guī)劃算法的區(qū)別僅在于啟發(fā)式函數(shù)的不同 A*則是結(jié)合了Best-first Searching和Dijkstra，它將當(dāng)前節(jié)點(diǎn)到初始節(jié)點(diǎn)和到目標(biāo)節(jié)點(diǎn)的距離之和作為啟發(fā)式函數(shù)。16.2 程序示例16.3 參考A Formal Basis for the heuristic Determination of Minimum Cost Paths
15.1 原理完整思想請(qǐng)看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言，和其他的基于搜索的路徑規(guī)劃算法的區(qū)別僅在于啟發(fā)式函數(shù)的不同Dijkstra則和Best-first-searching相反，它不是將到目標(biāo)節(jié)點(diǎn)的距離作為啟發(fā)式函數(shù)，而是將到起始節(jié)點(diǎn)的距離作為啟發(fā)式函數(shù)。15.2 程序示例
14.1 原理這里的Best-first-searching和數(shù)據(jù)結(jié)構(gòu)里學(xué)的圖搜索算法BFS（廣度優(yōu)先搜索）不是一個(gè)東西。完整思想請(qǐng)看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言下面說(shuō)說(shuō)Best-first-searching的核心思想：Best-first Searching的啟發(fā)式函數(shù)f(x)=dist(x,x_goal)，即Best-first Searching每一步都在預(yù)選集合中尋找距離目標(biāo)節(jié)點(diǎn)最近的的那個(gè)節(jié)點(diǎn)。這里的dist(x,y)，如果節(jié)點(diǎn)x,y無(wú)法通過(guò)碰撞檢測(cè)，則為inf，如果能通過(guò)碰撞檢測(cè)，可以直接用歐幾里得距離代替。14.2 程序示例14.3 參考https://blog.csdn.net/potato_uncle/article/details/109124362?ops_request_misc=&request_id=&biz_id=102&utm_term=best%20first%20search&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-109124362.nonecase&spm=1018.2226.3001.4187
基于搜索的路徑規(guī)劃算法基本都是一個(gè)套路，它們都是根據(jù)啟發(fā)函數(shù)重備用節(jié)點(diǎn)的集合中來(lái)尋找下一個(gè)節(jié)點(diǎn)，不同的啟發(fā)函數(shù)也就有不同的搜索類算法。搜索類算法是離散化的算法，體現(xiàn)在整個(gè)圖的區(qū)域是由有限個(gè)小方塊區(qū)域組成的。我們暫且把這些小方塊區(qū)域稱為“節(jié)點(diǎn)”。因此，整個(gè)區(qū)域被有限個(gè)節(jié)點(diǎn)填充，且每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)為有限個(gè)。設(shè)置兩個(gè)集合OPEN,CLOSE，OPEN初始狀態(tài)設(shè)為{x_init}，CLOSE 初始狀態(tài)設(shè)為空集。依據(jù)不同的啟發(fā)式函數(shù)，從open集中選擇一個(gè)點(diǎn)加入到close集中，然后拓展open集，如上圖，右下角的某個(gè)點(diǎn)被某種啟發(fā)式函數(shù)選中，加入到close集中，并相繼拓展open集下面介紹下搜索類算法的前進(jìn)過(guò)程：當(dāng)上述偽碼退出循環(huán)后，沿著x_goal的父節(jié)點(diǎn)往前回溯極為路徑各搜索類算法的區(qū)別在于第三行啟發(fā)函數(shù)的類型的不同，導(dǎo)致連接的節(jié)點(diǎn)不同。
幾種RRT對(duì)比如下：幾種RRT對(duì)比視圖mp4 RRT及其變種都是依托于采樣+在樹(shù)結(jié)構(gòu)上加減枝的形式進(jìn)行路徑規(guī)劃的，具有全局收斂特性，但是效率穩(wěn)定性不高。不過(guò)可以針對(duì)性地對(duì)其主要函數(shù)進(jìn)行優(yōu)化進(jìn)行效率的改進(jìn)：優(yōu)化采樣，優(yōu)化樹(shù)結(jié)構(gòu)等。一種加速RRT的思路就是，從起始點(diǎn)和目標(biāo)節(jié)點(diǎn)同時(shí)生長(zhǎng)RRT樹(shù)，這就是connected_RRT。此外，針對(duì)變化的環(huán)境，還有extend_RRT和Dynamic_RRT。 RRT*是一種趨近于最優(yōu)路徑的方案，它通過(guò)重布線來(lái)實(shí)現(xiàn)這一目的，它在理論上能達(dá)到最優(yōu)解，但它全局隨機(jī)撒點(diǎn)的特性導(dǎo)致它在遠(yuǎn)離目標(biāo)路徑的地方做了過(guò)多的生長(zhǎng)。 為了集中優(yōu)化資源，RRT*-smart應(yīng)運(yùn)而生，它比較在乎路徑和障礙物的拐點(diǎn)的附近的優(yōu)化，它通過(guò)路徑優(yōu)化步驟判斷出路徑和障礙物的拐點(diǎn)，并在拐點(diǎn)的鄰域內(nèi)投入更多的資源（即撒更多的點(diǎn)），以實(shí)現(xiàn)集中優(yōu)化資源。 但RRT*-smart依然浪費(fèi)了太多的隨機(jī)點(diǎn)在遠(yuǎn)離目標(biāo)路徑的區(qū)域，那什么才叫不遠(yuǎn)離目標(biāo)路徑的區(qū)域呢？informed RRT*則解決了這一問(wèn)題，它利用初始路徑的長(zhǎng)度，起始點(diǎn)和目標(biāo)點(diǎn)，畫出了一個(gè)橢圓，informed RRT*認(rèn)為，這個(gè)橢圓區(qū)域就是不遠(yuǎn)離目標(biāo)路徑的區(qū)域，生成這個(gè)橢圓后，后續(xù)的隨機(jī)撒點(diǎn)只灑在這個(gè)橢圓區(qū)域內(nèi)，當(dāng)更優(yōu)的路徑被發(fā)現(xiàn)，則根據(jù)這個(gè)新路徑的長(zhǎng)度，縮小橢圓，進(jìn)一步在有效區(qū)域集中撒點(diǎn)資源，以實(shí)現(xiàn)加速。 然而，RRT*類的算法是總會(huì)面臨一個(gè)問(wèn)題，那就是重布線，這個(gè)令RRT*能夠逼近最優(yōu)解的創(chuàng)新恰恰成為了它慢的原因。 于是，另一種思路被提出，那就是提前給定隨機(jī)點(diǎn)，然后通過(guò)啟發(fā)式函數(shù)來(lái)連接這些點(diǎn)以生長(zhǎng)路徑，這就是FMT*，F(xiàn)MT*專門針對(duì)解決高維構(gòu)型空間中的復(fù)雜運(yùn)動(dòng)規(guī)劃問(wèn)題，在預(yù)先確定的采樣點(diǎn)數(shù)量上執(zhí)行前向動(dòng)態(tài)規(guī)劃遞歸，并相應(yīng)地通過(guò)在代價(jià)到達(dá)空間中穩(wěn)步向外移動(dòng)生成路徑樹(shù)。FMT*能很快的找到一條路徑，但是當(dāng)我們想對(duì)這條路徑進(jìn)行優(yōu)化時(shí)，只有通過(guò)加密隨機(jī)采樣點(diǎn)的方式，然而，F(xiàn)MT*是一種單批算法，面對(duì)新的采樣點(diǎn)分布時(shí)，它只能重新開(kāi)始計(jì)算。 為了融合informed RRT*在有效區(qū)域集中隨機(jī)點(diǎn)的特點(diǎn)和FMT*快速生長(zhǎng)的特點(diǎn)，就誕生了BIT*。它能夠在橢圓區(qū)域內(nèi)分批撒點(diǎn)，實(shí)現(xiàn)快速生長(zhǎng)的同時(shí)，還能自我優(yōu)化。參考https://www.youtube.com/watch?v=TQIoCC48gp4
11.1 原理 簡(jiǎn)單來(lái)說(shuō)，BIT*是結(jié)合了Informed RRT*和FMT*的優(yōu)點(diǎn)的一種算法?；仡櫼幌?，Informed RRT*是對(duì)RRT*的一種優(yōu)化，在RRT*生成一個(gè)初始路徑后，則以初始路徑的長(zhǎng)度，起始點(diǎn)和目標(biāo)點(diǎn)為焦點(diǎn)，畫一個(gè)橢圓，Informed RRT*在后續(xù)隨機(jī)采點(diǎn)時(shí)，只取落在這個(gè)橢圓內(nèi)的點(diǎn)，一次采一個(gè)點(diǎn)，重復(fù)lm次。FMT*則與RRT那一套不同，它不是邊采點(diǎn)，邊生長(zhǎng)樹(shù)，而是一次性提前在整個(gè)區(qū)域（不包含障礙物區(qū)域）內(nèi)采lm個(gè)點(diǎn)，只重復(fù)一次。 下面我們來(lái)說(shuō)說(shuō)，Informed RRT*和優(yōu)缺點(diǎn)FMT*，然后就知道為什么要引出BIT*了。 先說(shuō)FMT*，F(xiàn)MT*的優(yōu)點(diǎn)是從起始位置開(kāi)始構(gòu)建，沒(méi)有重布線過(guò)程，因此節(jié)約時(shí)間，適用于復(fù)雜的障礙物環(huán)境。但是FMT*的缺點(diǎn)是，它只有1批，F(xiàn)MT*路徑的精度完全取決于當(dāng)前批撒點(diǎn)的密度，當(dāng)你想要提升精度時(shí)，只能重新開(kāi)始一批，重新更密集的撒點(diǎn)，然后重新開(kāi)始規(guī)劃。 再說(shuō)Informed RRT*，Informed RRT*的優(yōu)點(diǎn)恰好彌補(bǔ)了FMT*的缺點(diǎn)，想要提升精度，只需撒更多的點(diǎn)就好了，而Informed RRT*的撒點(diǎn)過(guò)程時(shí)一直在進(jìn)行的，它一批只撒一個(gè)點(diǎn)，重復(fù)很多批，開(kāi)始新的批的時(shí)候之前的信息不會(huì)被拋棄，只要Informed RRT*一直撒點(diǎn)，就可以達(dá)到任意精度。但是Informed RRT*的缺點(diǎn)也顯而易見(jiàn)，它需要重布線，計(jì)算效率低。 所以自然就想到，能不能利用FMT*的優(yōu)點(diǎn)，提前撒好點(diǎn)，不用重布線，提升計(jì)算效率，又能多批進(jìn)行，以不斷提升精度？當(dāng)然能，這就是BIT*算法 BIT*的過(guò)程總結(jié)為下圖：11.2 偽碼11.3 參考1、Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search2、Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs
10.1 原理 在RRT中，當(dāng)初始路徑已經(jīng)生成之后，如果重點(diǎn)在初始路徑周圍進(jìn)行采樣的話，可以明顯提高路徑優(yōu)化效率。Informed RRT就是進(jìn)一步優(yōu)化了采樣函數(shù)，采樣的方式是以起點(diǎn)和終點(diǎn)為焦點(diǎn)構(gòu)建橢圓形采樣區(qū)域。 回顧一下RRT*-smart，因?yàn)樵谀硡^(qū)域撒點(diǎn)越多，該區(qū)域的優(yōu)化效果越好，而單純的RRT*是在全域內(nèi)隨機(jī)撒點(diǎn)，優(yōu)化效果沒(méi)有得以集中，RRT*-smart認(rèn)為經(jīng)過(guò)路徑優(yōu)化后的路徑的拐點(diǎn)在障礙物的附近，它認(rèn)為這個(gè)拐點(diǎn)的附近需要著重優(yōu)化，所以RRT*-smart在進(jìn)一步撒點(diǎn)的過(guò)程中，將一些隨機(jī)點(diǎn)偏袒的撒在這個(gè)拐點(diǎn)的附近鄰域。 這里的informed RRT*也是這樣認(rèn)為，它認(rèn)為單純的RRT*在整個(gè)區(qū)域內(nèi)隨機(jī)撒點(diǎn)，優(yōu)化效果太過(guò)分散，如果我能知道我最終優(yōu)化的路徑在哪一塊區(qū)域，那我就只在這一區(qū)域內(nèi)撒點(diǎn)不就好了嗎？informed RRT*就是這樣做的。注意： informed RRT*是在RRT*算法給出一條初始路徑后，對(duì)這個(gè)初始路徑繼續(xù)優(yōu)化的步驟才起作用的，它對(duì)于這個(gè)初始路徑的生成沒(méi)有幫助。10.2 思路 根據(jù)高中數(shù)學(xué)知識(shí)可以知道，在橢圓上的點(diǎn)到橢圓兩焦點(diǎn)的距離之和相同，橢圓外的點(diǎn)的距離到兩焦點(diǎn)的距離之和大于橢圓上的點(diǎn)到兩焦點(diǎn)的距離之和，橢圓內(nèi)的點(diǎn)反之。 回顧一下RRT*的搜索圖，根據(jù)上面這個(gè)知識(shí)點(diǎn)可以發(fā)現(xiàn)，其實(shí)RRT在已經(jīng)得到一條可行路徑之后，可以將采樣空間收縮到一個(gè)橢圓形區(qū)域中，區(qū)域之外的點(diǎn)對(duì)于縮短規(guī)劃出的路徑長(zhǎng)度并沒(méi)有實(shí)際價(jià)值。 informed RRT就是的主要思想就是上面這種思想，在獲取可行路徑之后，將采樣空間限制在一個(gè)橢圓形區(qū)域中，并且隨著路徑長(zhǎng)度的不斷縮短，逐漸縮小該橢圓形區(qū)域。這個(gè)思想其實(shí)在以前就有，但是提出informed RRT的論文中提出了對(duì)這個(gè)橢圓形區(qū)域直接采樣的方法。 可能有人會(huì)直接想，這里只不過(guò)是縮小了采樣空間，并不會(huì)明顯改進(jìn)算法。但是實(shí)際上，當(dāng)拓展到高維空間時(shí)，效率的提升是巨大的。那么，如何表達(dá)這個(gè)橢圓呢？下面介紹橢圓采樣區(qū)域的表達(dá)方式方法1：先在標(biāo)準(zhǔn)橢圓的方程中采樣，再將采樣點(diǎn)旋轉(zhuǎn)平移到實(shí)際采樣區(qū)域，需要兩個(gè)矩陣：平移向量、旋轉(zhuǎn)矩陣。這兩個(gè)參數(shù)只需要在初始化時(shí)計(jì)算即可轉(zhuǎn)換后的坐標(biāo)為：方法2：利用超橢圓體然后在二維平面映射這里放一段.m文件取橢圓隨機(jī)點(diǎn)的代碼（思路如方法2）：除了采樣過(guò)程外，Informed RRT*的流程和RRT*是一樣的。10.3 偽碼偽代碼中是在RRT的偽代碼基礎(chǔ)上改的，標(biāo)紅的地方是informed RRT 更改的地方?？梢钥闯觯鋵?shí)主體框架上面并沒(méi)有太多更改，實(shí)際上也是，主要的更改都在第七行，也就是采樣這一步。這是采樣這一步的偽代碼。informed RRT將目前已經(jīng)搜索到的最短路徑作為cbest，起點(diǎn)和終點(diǎn)之間的距離作為cmin，以此構(gòu)建橢圓。當(dāng)還沒(méi)有規(guī)劃結(jié)果時(shí)，cbest為inf，也就是和經(jīng)典RRT沒(méi)有區(qū)別。10.4 程序示例程序在尋找初始路徑的過(guò)程和普通RRT*一樣，在全局域中隨機(jī)撒點(diǎn)，迭代到1282次時(shí)首次找到初始路徑，然后我們以起始點(diǎn)和目標(biāo)點(diǎn)為焦點(diǎn)，初始路徑的長(zhǎng)度為點(diǎn)到兩焦點(diǎn)的距離之和，畫出一個(gè)橢圓：我們隨后的隨機(jī)點(diǎn)的選取范圍不再是全局域了，新采的樣本點(diǎn)被限制在這個(gè)橢圓中，下圖中的圓圈代表迭代1283-2509次的隨機(jī)點(diǎn)的分布，可見(jiàn)，新的隨機(jī)點(diǎn)全部被限制在橢圓中：當(dāng)?shù)?510次時(shí)，新的總長(zhǎng)度更短的路徑被找到，，隨后，我們以起始點(diǎn)和目標(biāo)點(diǎn)為焦點(diǎn)，以這個(gè)新的路徑的長(zhǎng)度為到兩焦點(diǎn)的距離，畫出一個(gè)比之前更小的橢圓：同樣的，迭代次數(shù)為2510-2865次的循環(huán)中的新的隨機(jī)點(diǎn)被限制在這個(gè)新的更小的橢圓中，使隨機(jī)點(diǎn)資源進(jìn)一步集中：當(dāng)?shù)?866次時(shí)，找到一個(gè)路徑更短的路徑：10.5 參考Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic
9.1 原理 FMT*算法專門針對(duì)解決高維構(gòu)型空間中的復(fù)雜運(yùn)動(dòng)規(guī)劃問(wèn)題，它是為高密度障礙物的環(huán)境構(gòu)建的算法。該算法被證明是漸近最優(yōu)的，并且比同類型算法（RRT*）更快收斂到最優(yōu)解。FMT*算法在預(yù)先確定的概率繪制的樣本數(shù)量上執(zhí)行“惰性”動(dòng)態(tài)規(guī)劃遞歸，以生長(zhǎng)路徑樹(shù)，該路徑樹(shù)在成本到達(dá)空間中穩(wěn)定地向外移動(dòng)。 FMT*的最終產(chǎn)物是一棵樹(shù)，它在連續(xù)空間中獲取一批樣本，然后它能在圖中使用惰性的動(dòng)態(tài)編程搜索該樣本集合，并以此找到路徑，這也是一個(gè)漸進(jìn)最優(yōu)的解決方案，F(xiàn)MT*相比于RRT*的加速效果優(yōu)勢(shì)在高維和碰撞檢查很昂貴的情況下尤其突出。很棒的一點(diǎn)是，F(xiàn)MT*是從起始位置開(kāi)始構(gòu)建，而不是像RRT*是在空間的任意位置采點(diǎn)，因?yàn)檫@可能會(huì)得到非常遠(yuǎn)的點(diǎn)或非常近的點(diǎn)，這有什么好處呢？這意味著你不必在樹(shù)中回溯以進(jìn)行重布線，因?yàn)檫@在計(jì)算上效率低下。FMT*比RRT*更好，因?yàn)樗鼊?chuàng)建的連接接近最佳，沒(méi)有重布線。 FMT*算法在預(yù)先確定的采樣點(diǎn)數(shù)量上執(zhí)行前向動(dòng)態(tài)規(guī)劃遞歸，并相應(yīng)地通過(guò)在代價(jià)到達(dá)空間中穩(wěn)步向外移動(dòng)生成路徑樹(shù)。FMT*執(zhí)行動(dòng)態(tài)規(guī)劃遞歸，其特點(diǎn)有三個(gè)關(guān)鍵特征:·它是為磁盤連接圖量身定制的，其中兩個(gè)樣本的距離低于給定的界限（稱為連接半徑）則這兩個(gè)樣本被認(rèn)為是鄰居，因此是可連接的。·它同時(shí)執(zhí)行圖構(gòu)造和圖搜索?！榱嗽u(píng)估動(dòng)態(tài)規(guī)劃遞歸中的即時(shí)成本，算法“懶惰地”忽略了障礙物的存在，每當(dāng)與新樣本的局部最優(yōu)(假設(shè)沒(méi)有障礙物)連接與障礙物相交時(shí)，該樣本就會(huì)簡(jiǎn)單地跳過(guò)并留待以后，而不是在鄰域中尋找其他連接。注意：FMT*的樣本點(diǎn)是提前生成好的，然后把這些點(diǎn)固定，再利用這些固定好的點(diǎn)來(lái)生成行進(jìn)樹(shù)，注意區(qū)別于RRT*那一套，RRT*是生成隨機(jī)點(diǎn)的同時(shí)，生成行進(jìn)樹(shù)。9.2 算法思路上圖（a）是RRT*添加新節(jié)點(diǎn)的某一步，上圖（b）（c）是FMT*添加新節(jié)點(diǎn)的某一步。 先看RRT*，節(jié)點(diǎn)9是新考慮的節(jié)點(diǎn)，它在第一次重布線時(shí)，需要從它的所有鄰居節(jié)點(diǎn)中找出一個(gè)父節(jié)點(diǎn)，使得節(jié)點(diǎn)9到達(dá)起始節(jié)點(diǎn)的cost最小，因此節(jié)點(diǎn)9需要計(jì)算它到4、5、6、8號(hào)節(jié)點(diǎn)的距離并同時(shí)進(jìn)行碰撞檢測(cè)，因此，第一次重布線過(guò)程就要求待加入的節(jié)點(diǎn)對(duì)它的所有鄰居節(jié)點(diǎn)進(jìn)行一次碰撞檢測(cè)，第二次重布線過(guò)程也需要計(jì)算距離和碰撞檢測(cè)，但這在第一次重布線過(guò)程中做過(guò)了，可以記錄先來(lái)直接利用，因此第二次重布線過(guò)程碰撞檢測(cè)這一步可以不用重復(fù)進(jìn)行，因此，總的來(lái)說(shuō)，RRT*每新加入一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)需要對(duì)它的所有鄰居節(jié)點(diǎn)進(jìn)行一次碰撞檢測(cè)。 再看FMT*，上圖（b）（c）中的x就是新考慮的節(jié)點(diǎn)，在圖（b）中，x需計(jì)算它到集合V_open中所有的鄰居節(jié)點(diǎn)的cost，但不需要進(jìn)行碰撞檢測(cè)，從中選擇一個(gè)能使它到達(dá)初始節(jié)點(diǎn)總cost最小的節(jié)點(diǎn)作為它的父節(jié)點(diǎn)，然后，對(duì)它和這個(gè)父節(jié)點(diǎn)的連線進(jìn)行碰撞檢測(cè)，如果能通過(guò)碰撞檢測(cè)，則加入x，若不能，則下一個(gè)x，因此，總的來(lái)說(shuō)，F(xiàn)MT*每新加入一個(gè)節(jié)點(diǎn)，永遠(yuǎn)只需要進(jìn)行一次碰撞檢測(cè)。FMT*比RRT*每新加入一個(gè)節(jié)點(diǎn)需要進(jìn)行的碰撞檢測(cè)次數(shù)少得多，而且FMT*也是漸進(jìn)最優(yōu)的，這就是FMT*相比于RRT*的優(yōu)勢(shì)所在。9.3 偽碼9.4 程序示例下圖中的 圓圈代表提前采好的隨機(jī)點(diǎn)9.5 參考Fast Marching Tree: a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions?
8.1 原理 最初，RRT*-Smart 像 RRT* 一樣隨機(jī)搜索狀態(tài)空間。類似地，找到第一條路徑就像 RRT* 會(huì)嘗試通過(guò)配置空間中的隨機(jī)采樣來(lái)找到路徑一樣。一旦找到第一條路徑，它就會(huì)通過(guò)互連直接可見(jiàn)的節(jié)點(diǎn)來(lái)優(yōu)化它。此優(yōu)化路徑產(chǎn)生用于智能采樣的偏置點(diǎn)。在這些偏置點(diǎn)，采樣以規(guī)則的間隔進(jìn)行 隨著算法的進(jìn)展和路徑的不斷優(yōu)化，此過(guò)程將繼續(xù)進(jìn)行。每當(dāng)找到更短的路徑時(shí)，偏差就會(huì)轉(zhuǎn)向新路徑。 RRT*是一邊生長(zhǎng)一邊優(yōu)化的，RRT*的重心在于找到最優(yōu)路徑。RRT*樹(shù)生長(zhǎng)到能連接起點(diǎn)和終點(diǎn)后，這就已經(jīng)有一條初始路徑了。 這顆RRT*樹(shù)可以繼續(xù)生長(zhǎng)，越生長(zhǎng)可以得到的路徑相比初始路徑會(huì)越優(yōu)。然而，這個(gè)繼續(xù)生長(zhǎng)的過(guò)程對(duì)于RRT*而言效率非常低，由此衍生出RRT*-smart算法，專門解決這一問(wèn)題。 注意到，RRT*-smart是在RRT*算法已生成初始路徑后，在此基礎(chǔ)上，想對(duì)初始路徑繼續(xù)優(yōu)化的步驟才起作用，所以RRT*-smart對(duì)于生成初始路徑并沒(méi)有加速幫助。 RRT*-smart的優(yōu)勢(shì)在于：它專注于提升路徑接近障礙物拐點(diǎn)處的優(yōu)化速度。RRT*-smart算法的思路是這樣的：在原始RRT*算法的基礎(chǔ)上加了兩步：①路徑優(yōu)化路徑優(yōu)化的本質(zhì)是利用三角形兩邊之和大于第三邊 假設(shè)RRT*生成的初始路徑長(zhǎng)這樣 具體操作如下： 一旦RRT*給出了一條初始路徑，將初始路徑中彼此可見(jiàn)的節(jié)點(diǎn)直接相連。迭代過(guò)程從xgoal開(kāi)始，向xinit檢查與每個(gè)節(jié)點(diǎn)的連續(xù)父節(jié)點(diǎn)的直接連接，直到無(wú)沖突條件失敗。下圖給出一個(gè)示例。 信標(biāo)（Z_beacons）：經(jīng)過(guò)路徑優(yōu)化后的路徑中除了起點(diǎn)和終點(diǎn)之外的節(jié)點(diǎn)，標(biāo)記為信標(biāo)（Z_beacons），如上圖中的綠點(diǎn)。②智能采樣在RRT*算法中，在生成初始路徑后，在此RRT*樹(shù)的基礎(chǔ)上繼續(xù)采點(diǎn)，采點(diǎn)越多，路徑優(yōu)化效果越好，但此采點(diǎn)，是完全隨機(jī)的采點(diǎn)，因此效率低下，RRT*-smart則不是完全隨機(jī)的采點(diǎn)。在RRT*-smart算法中，利用了這樣一種思想：智能采樣背后的想法是通過(guò)生成盡可能靠近障礙物頂點(diǎn)的節(jié)點(diǎn)來(lái)接近最優(yōu)性。在基于采樣的RRT*-smart中，路徑僅沿著靠近障礙物拐點(diǎn)的外圍進(jìn)行優(yōu)化，解決的辦法就是：在障礙物拐點(diǎn)的外圍多多采點(diǎn)。如下圖所示： 問(wèn)：那么RRT*-smart如何實(shí)現(xiàn)在障礙物拐點(diǎn)的外圍多多采點(diǎn)呢？答：利用①路徑優(yōu)化過(guò)程中給出的信標(biāo)（Z_beacons）。一旦找到初始路徑，智能采樣就會(huì)開(kāi)始，在以Z beacons為中心的半徑為R beacons的球中直接生成一定數(shù)量的樣本。采樣偏向于這些信標(biāo)，因?yàn)樗鼈兲峁┝擞嘘P(guān)障礙物頂點(diǎn)（或圓形障礙物的外圍）位置的有用線索。因此，這些信標(biāo)需要被最大節(jié)點(diǎn)包圍，以優(yōu)化這些轉(zhuǎn)彎處的路徑。與 RRT* 相比，這一特征迫使所提出的算法以更少的迭代次數(shù)達(dá)到最優(yōu)解。注意：信標(biāo)（Z_beacons）是需要隨著優(yōu)化路徑的更新而更新的。即當(dāng)z_goal.cost變小時(shí)，說(shuō)明路徑得到了優(yōu)化，那么就要啟用之前①路徑優(yōu)化算法來(lái)重新確定新的z_beacons。 8.2 偽碼 8.3 程序示例下圖中的線段代表由RRT*生成的初始RRT樹(shù)，圓圈代表在初始RRT樹(shù)基礎(chǔ)上，繼續(xù)采點(diǎn)的分布，可見(jiàn)在幾個(gè)“拐點(diǎn)處”的圓形領(lǐng)域內(nèi)我們有額外的采點(diǎn)以加強(qiáng)在這部分的采點(diǎn) 路徑優(yōu)化后確定出拐點(diǎn) 經(jīng)過(guò)路徑優(yōu)化后的路徑： 8.4 參考1、RRT*-SMART: A Rapid Convergence Implementation of RRT*2、Rapid convergence implementation of RRT* towards optimal solution
7.1 原理 RRT*是一種基于采樣的最優(yōu)化路徑規(guī)劃方式，與RRT的區(qū)別是，RRT盡量使新節(jié)點(diǎn)以及其周圍的節(jié)點(diǎn)到起點(diǎn)的cost(可以是路徑或者時(shí)間等目標(biāo)函數(shù))最短，而不是僅僅尋找離它近的節(jié)點(diǎn)，而且在找到路徑后不會(huì)停止，而是繼續(xù)進(jìn)行采樣來(lái)優(yōu)化得到的路徑。 盡管RRT算法是一個(gè)相對(duì)高效率，同時(shí)可以較好的處理帶有非完整約束的路徑規(guī)劃問(wèn)題的算法，并且在很多方面有很大的優(yōu)勢(shì)，但是RRT算法并不能保證所得出的可行路徑是相對(duì)優(yōu)化的。因此許多關(guān)于RRT算法的改進(jìn)也致力于解決路徑優(yōu)化的問(wèn)題，RRT*算法就是其中一個(gè)。RRT*算法的主要特征是能快速的找出初始路徑，之后隨著采樣點(diǎn)的增加，不斷地進(jìn)行優(yōu)化直到找到目標(biāo)點(diǎn)或者達(dá)到設(shè)定的最大循環(huán)次數(shù)。RRT*算法是漸進(jìn)優(yōu)化的，也就是隨著迭代次數(shù)的增加，得出的路徑是越來(lái)越優(yōu)化的，而且永遠(yuǎn)不可能在有限的時(shí)間中得出最優(yōu)的路徑。因此換句話說(shuō)，要想得出相對(duì)滿意的優(yōu)化路徑，是需要一定的運(yùn)算時(shí)間的。所以RRT*算法的收斂時(shí)間是一個(gè)比較突出的研究問(wèn)題。但不可否認(rèn)的是，RRT*算法計(jì)算出的路徑的代價(jià)相比RRT來(lái)說(shuō)減小了不少。RRT*算法與RRT算法的區(qū)別主要在于兩個(gè)針對(duì)新節(jié)點(diǎn) xnew 的重計(jì)算過(guò)程，分別為：·重新為 xnew 選擇父節(jié)點(diǎn)的過(guò)程·重布線隨機(jī)樹(shù)的過(guò)程7.1.1 重新選擇父節(jié)點(diǎn)過(guò)程 在新產(chǎn)生的節(jié)點(diǎn) xnew 附近以定義的半徑范圍內(nèi)尋找“近鄰”，作為替換 xnew 父節(jié)點(diǎn)的備選。依次計(jì)算“近鄰”節(jié)點(diǎn)到起點(diǎn)的路徑代價(jià)加上 xnew 到每個(gè)“近鄰”的路徑代價(jià)，具體過(guò)程見(jiàn)上圖。 圖(a)中表現(xiàn)的是隨機(jī)樹(shù)擴(kuò)展過(guò)程中的一個(gè)時(shí)刻，節(jié)點(diǎn)標(biāo)號(hào)表示產(chǎn)生該節(jié)點(diǎn)的順序，0節(jié)點(diǎn)是初始節(jié)點(diǎn)，9節(jié)點(diǎn)是新產(chǎn)生的節(jié)點(diǎn) xnew，6節(jié)點(diǎn)是產(chǎn)生9節(jié)點(diǎn)的 xnear，節(jié)點(diǎn)與節(jié)點(diǎn)之間連接的邊上數(shù)字代表兩個(gè)節(jié)點(diǎn)之間的歐氏距離(這里我們用歐氏距離來(lái)表示路徑代價(jià))。 在重新找父節(jié)點(diǎn)的過(guò)程中，以9節(jié)點(diǎn) xnew 為圓心，以事先規(guī)定好的半徑，找到在這個(gè)圓的范圍內(nèi) xnew 的近鄰，也就是4，5，8節(jié)點(diǎn)。 原來(lái)的路徑0 - 4 - 6 - 9代價(jià)為10 + 5 + 1 = 16，備選的三個(gè)節(jié)點(diǎn)與 xnew 組成的路徑0 - 1 - 5 - 9，0 - 4 - 9和0 - 1 - 5 - 8 - 9代價(jià)分別為3 + 5 + 3 = 11，10 + 4 = 14和3 + 5 + 1 + 3 = 12，因此如果5節(jié)點(diǎn)作為9節(jié)點(diǎn)的新父節(jié)點(diǎn)，則路徑代價(jià)相對(duì)是最小的，因此我們把9節(jié)點(diǎn)的父節(jié)點(diǎn)由原來(lái)的節(jié)點(diǎn)4變?yōu)楣?jié)點(diǎn)5，則重新生成的隨機(jī)樹(shù)如圖(b)所示。7.1.2 重布線隨機(jī)樹(shù)過(guò)程 在為xnew 重新選擇父節(jié)點(diǎn)之后，為進(jìn)一步使得隨機(jī)樹(shù)節(jié)點(diǎn)間連接的代價(jià)盡量小，為隨機(jī)樹(shù)進(jìn)行重新布線。過(guò)程示意如上圖重布線的過(guò)程也可以被表述成：如果近鄰節(jié)點(diǎn)的父節(jié)點(diǎn)改為 xnew 可以減小路徑代價(jià)，則進(jìn)行更改。 如圖(c)，9節(jié)點(diǎn)為新生成的節(jié)點(diǎn) xnew ，近鄰節(jié)點(diǎn)分別為節(jié)點(diǎn)4 , 6 , 8 。它們父節(jié)點(diǎn)分別為節(jié)點(diǎn)0 , 4 , 5。路徑分別為0 - 4，0 - 4 - 6，0 - 1 - 5 - 8，代價(jià)分別為10，10 + 5 = 15 和3 + 5 + 1 = 9。 如果將4節(jié)點(diǎn)的父節(jié)點(diǎn)改為9節(jié)點(diǎn) xnew ，則到達(dá)節(jié)點(diǎn)4的路徑變?yōu)? - 1 - 5 - 9 - 4，代價(jià)為3 + 5 + 3 + 4 = 15 大于原來(lái)的路徑代價(jià)10，因此不改變4節(jié)點(diǎn)的父節(jié)點(diǎn)。 同理，改變了8節(jié)點(diǎn)的父節(jié)點(diǎn)，路徑代價(jià)將由原來(lái)的9變?yōu)?4，也不改變8節(jié)點(diǎn)的父節(jié)點(diǎn)。如果改變6節(jié)點(diǎn)的父節(jié)點(diǎn)為 xnew 則路徑變?yōu)? - 1 - 5 - 9 - 6，代價(jià)為3 + 5 + 3 + 1 = 12小于原來(lái)的路徑代價(jià)15，因此將6的父節(jié)點(diǎn)改為節(jié)點(diǎn)9，生成的新隨機(jī)樹(shù)如圖(d)。 重布線過(guò)程的意義在于每當(dāng)生成了新的節(jié)點(diǎn)后，是否可以通過(guò)重新布線，使得某些節(jié)點(diǎn)的路徑代價(jià)減少。如果以整體的眼光看，并不是每一個(gè)重新布線的節(jié)點(diǎn)都會(huì)出現(xiàn)在最終生成的路徑中，但在生成隨機(jī)樹(shù)的過(guò)程中，每一次的重布線都盡可能的為最終路徑代價(jià)減小創(chuàng)造機(jī)會(huì)。 RRT*算法的核心在于上述的兩個(gè)過(guò)程：重新選擇父節(jié)點(diǎn)和重布線。這兩個(gè)過(guò)程相輔相成，重新選擇父節(jié)點(diǎn)使新生成的節(jié)點(diǎn)路徑代價(jià)盡可能小，重布線使得生成新節(jié)點(diǎn)后的隨機(jī)樹(shù)減少冗余通路，減小路徑代價(jià)。7.2 偽碼7.3 程序示例7.4 參考1、Sampling-based Algorithms for Optimal Motion Planning2、https://blog.csdn.net/weixin_43795921/article/details/88557317#t03、https://zhuanlan.zhihu.com/p/51087819
6.1原理 Dynamic RRT和Extended RRT一樣，也是用來(lái)解決動(dòng)態(tài)路徑規(guī)劃問(wèn)題，它們的思想有一點(diǎn)是共通的，那就是不要完全放棄初始RRT生成的樹(shù)或初始路徑的信息，而是在此基礎(chǔ)上重新規(guī)劃。Dynamic RRT和Extended RRT的區(qū)別在于，Extended RRT利用的是RRT生成的初始路徑的信息，而Dynamic RRT利用的是RRT生成的初始RRT樹(shù)的信息。思路如下： 在老地圖中，用RRT算法生成了一個(gè)RRT樹(shù)，在新地圖中，原始RRT樹(shù)的節(jié)點(diǎn)信息（坐標(biāo)、父節(jié)點(diǎn)）存儲(chǔ)在一個(gè)節(jié)點(diǎn)集合中。在新地圖中，先檢測(cè)新地圖中比老地圖多出的障礙物，然后，以碰撞檢測(cè)為評(píng)判根據(jù)，刪除老節(jié)點(diǎn)集合中與新障礙物無(wú)法通過(guò)碰撞檢測(cè)的節(jié)點(diǎn)和邊。的到一顆修建過(guò)后的與新地形無(wú)碰撞的修剪后RRT樹(shù)，然后再在這顆修剪后的額RRT樹(shù)的基礎(chǔ)上，繼續(xù)生長(zhǎng)這棵樹(shù)，直到這棵樹(shù)連接起點(diǎn)和終點(diǎn)，然后回溯路徑，得出新路徑。①?gòu)膹某跏寂渲玫侥繕?biāo)配置生成的 RRT 開(kāi)始（圖（a））。 ②當(dāng)配置空間發(fā)生變化時(shí)（例如通過(guò)接收新信息），將RRT中因這些變化而失效的所有部分標(biāo)記為無(wú)效（圖（b）和（c））。 ③然后我們修剪樹(shù)以去除所有這些無(wú)效部分（圖（d））。 ④此時(shí)，保證樹(shù)中剩余的所有節(jié)點(diǎn)和邊都是有效的，但樹(shù)可能不再達(dá)到目標(biāo)。最后，我們把樹(shù)長(zhǎng)出來(lái)，直到再次達(dá)到目標(biāo)6.2 偽碼6.3 程序示例加入新的障礙物后，被該障礙物折斷的剩余的圖：在原來(lái)的樹(shù)的基礎(chǔ)上，繼續(xù)生長(zhǎng)后的圖：6.4 參考Replanning with RRTs
5.1 原理 在現(xiàn)實(shí)世界的場(chǎng)景中，通常會(huì)出現(xiàn)這樣的情況:有關(guān)環(huán)境的初始可用信息是不完整的，或者環(huán)境本身是動(dòng)態(tài)的。在這些情況下，當(dāng)接收到新信息時(shí)，初始解決方案可能會(huì)失效，例如通過(guò)機(jī)載傳感器。當(dāng)這種情況發(fā)生時(shí)，通常會(huì)放棄當(dāng)前的 RRT，并從零開(kāi)始生長(zhǎng)新的 RRT。這可能是一項(xiàng)非常耗時(shí)的操作，尤其是在規(guī)劃問(wèn)題很復(fù)雜的情況下。另一方面，在確定性規(guī)劃界存在重規(guī)劃算法，當(dāng)這種變化發(fā)生時(shí)，它們能夠有效地修復(fù)之前的解決方案，而不需要從頭重新規(guī)劃。這就是通過(guò)連續(xù)域規(guī)劃路徑的問(wèn)題，如果每次更新地圖，都用RRT重新規(guī)劃，效率相當(dāng)?shù)拖?。Extended_RRT則專門用于解決這種動(dòng)態(tài)路徑規(guī)劃問(wèn)題。 Extended_RRT的思路是這樣的：在老地圖中，由RRT算法得出的路徑，在障礙物動(dòng)態(tài)變化不太大的前提下，在新地圖中，大概率也是能通過(guò)的，就算障礙物變化很大，之前的路徑也或多或少包含了當(dāng)前障礙物區(qū)域的信息，所以，在新障礙物區(qū)域中，在重新規(guī)劃路徑時(shí)，原有的初始RRT路徑的信息可以利用上，而沒(méi)有必要完完全全重零開(kāi)始用RRT來(lái)規(guī)劃。 那么如何利用上初始RRT路徑的信息呢？思路如下： 在老地圖上先用RRT算法的處一條初始路徑，將這條初始路徑上的節(jié)點(diǎn)存儲(chǔ)在集合waypoints中，當(dāng)環(huán)境更新后，希望在新地圖上得出一條路徑，在隨機(jī)撒點(diǎn)的步驟，新的隨機(jī)點(diǎn)有概率p落在目標(biāo)節(jié)點(diǎn)處，此外，還有r的概率落在waypoints的節(jié)點(diǎn)中，剩余1-p-r的概率在目標(biāo)區(qū)域內(nèi)隨即撒點(diǎn)。這樣在重規(guī)劃時(shí)，就可以把初始路徑的信息利用進(jìn)來(lái)。完成隨機(jī)點(diǎn)選取后，剩余的碰撞檢測(cè)、樹(shù)的生長(zhǎng)、路徑回溯步驟與RRT一致?？偨Y(jié)：Extended_RRT適用于需要反復(fù)路徑重規(guī)劃的場(chǎng)景中，效率比直接重新進(jìn)行RRT要高得多，和RRT的主要區(qū)別在于，在選取新的隨機(jī)點(diǎn)時(shí)，利用上了初始路徑的信息，而不是完全隨機(jī)撒點(diǎn)。5.2偽碼5.3 程序示例5.4 參考1、Real-Time Randomized Path Planning for Robot Navigation* 2、Extended RRT algorithm with dynamic N-dimensional cuboid domains3、Replanning with RRTs
原理相比于最原始的 RRT 算法的一些缺點(diǎn)，提出的一種改進(jìn)的 RRT 算法 為了加快隨機(jī)樹(shù)到達(dá)目標(biāo)點(diǎn)的速度，簡(jiǎn)單的改進(jìn)方法是：在隨機(jī)樹(shù)每次的生長(zhǎng)過(guò)程中，根據(jù)隨機(jī)概率（0.0 到 1.0 的隨機(jī)值 p）來(lái)選擇生長(zhǎng)方向是目標(biāo)點(diǎn)還是隨機(jī)點(diǎn)。2001 年，LaValle在采樣策略方面引入 RRT GoalBias 與 RRT GoalZoom，RRT GoalBias 方法中，規(guī)劃器隨機(jī)采樣的同時(shí),以一定概率向最終目標(biāo)運(yùn)動(dòng)；RRTGoalZoom 方法中，規(guī)劃器分別在整個(gè)空間和目標(biāo)點(diǎn)周圍的空間進(jìn)行采樣。 和普通RRT的區(qū)別僅在于隨機(jī)撒點(diǎn)的時(shí)候有區(qū)別，這個(gè)p越大，算法越快，但對(duì)于復(fù)雜地形，可能會(huì)陷入局部極小處，反而變慢。一般取p=0.1程序示例參考Rapidly-Exploring Random Trees: A New Tool for Path Planning
2.1 原理雙樹(shù)RRT是在原本RRT的基礎(chǔ)上多加了?顆隨機(jī)探索樹(shù)，各自從起點(diǎn)和終點(diǎn)向外探索拓展，直到兩棵樹(shù)相遇時(shí)規(guī)劃算法收斂。這種改進(jìn)過(guò)的探索策略可以??提?RRT的運(yùn)?效率。 雙樹(shù)RRT中存在兩顆隨機(jī)樹(shù)，我們將其命名為A和B，A以起點(diǎn)為根節(jié)點(diǎn)，B以終點(diǎn)為根節(jié)點(diǎn)。兩顆隨機(jī)樹(shù)的拓展方式和單樹(shù)RRT的別無(wú)二致，同樣都需要經(jīng)歷隨機(jī)采樣+步?限制+碰撞檢測(cè)這三個(gè)步驟，但是不同的地?在于雙樹(shù)RRT的隨機(jī)樹(shù)是交替生長(zhǎng)的，??說(shuō)第?輪迭代中A樹(shù)向外??，第?輪便切換為B樹(shù)??，如此循環(huán)。 在每輪迭代中，隨機(jī)樹(shù)除了向外拓展之外，還會(huì)多出?個(gè)步驟，就是遍歷另一顆隨機(jī)樹(shù)中的所有節(jié)點(diǎn)，找出離NewNode最近的節(jié)點(diǎn)，用于判斷兩顆隨機(jī)樹(shù)是否相遇。 假設(shè)算法經(jīng)歷了N次迭代以后，已經(jīng)拓展出如下圖所示的兩顆隨機(jī)樹(shù)。并且在下?輪迭代中，輪到A樹(shù)進(jìn)?拓展，A樹(shù)在圖中?綠?線條表示，B樹(shù)?黃色線條表示。當(dāng)進(jìn)?本輪迭代后，算法成功拓展出A樹(shù)的新節(jié)點(diǎn)NewNode_A，此時(shí)算法將遍歷B樹(shù)中的所有節(jié)點(diǎn)，找出B樹(shù)中離NewNode_A最近的節(jié)點(diǎn)ClosestNode_B。并判斷?者是否滿?步?限制以及是否可以通過(guò)步?檢測(cè)。如下圖所示，這種情況明顯?法通過(guò)碰撞檢測(cè)。那么A樹(shù)和B樹(shù)在這?輪迭代中?法相遇，需要接著下?輪迭代。進(jìn)?下?輪迭代，這次便切換為B樹(shù)進(jìn)?拓展，假設(shè)算法拓展出的NewNode_B以及遍歷A樹(shù)后得到的ClosestNode_A如下圖所示，經(jīng)過(guò)判斷發(fā)現(xiàn)?者滿?步?限制并且通過(guò)了碰撞檢測(cè)，那么這時(shí)A樹(shù)和B樹(shù)就成功得相遇了，規(guī)劃算法收斂當(dāng)算法收斂以后，只需在兩棵樹(shù)的相遇處分別沿著?節(jié)點(diǎn)回溯便可以找出從起點(diǎn)到終點(diǎn)的有效路徑。注意：雙向RRT和RRT的區(qū)別不僅僅是在于雙向生長(zhǎng)，雙向RRT比RRT更“貪心”，相比于RRT在生長(zhǎng)RRT樹(shù)的時(shí)候，是每產(chǎn)生一個(gè)隨機(jī)點(diǎn)，如果能通過(guò)碰撞檢測(cè)，就往該隨機(jī)點(diǎn)的方向生長(zhǎng)一次，然后該隨機(jī)點(diǎn)就被廢棄了，下一步想繼續(xù)生長(zhǎng)RRT樹(shù)的話，就只能繼續(xù)生成新的隨機(jī)點(diǎn)，每個(gè)隨機(jī)點(diǎn)最多利用一次。而雙向RRT在生長(zhǎng)RRT樹(shù)時(shí)，先先生成一個(gè)隨機(jī)點(diǎn)，然后，該樹(shù)往該隨機(jī)點(diǎn)的方向生長(zhǎng)，直到碰到障礙物或則生長(zhǎng)到該隨機(jī)點(diǎn)，這樣，一個(gè)隨機(jī)點(diǎn)就被多次利用，加快了速度。2.2 偽碼2.3 程序示例2.4 收斂性分析雙向RRT的收斂性分析可以應(yīng)用RRT的收斂性分析2.5 參考1、RRT-Connect: An Efficient Approach to Single-Query Path Planning2、https://www.guyuehome.com/9405
1.1 RRT算法思路我們有兩個(gè)節(jié)點(diǎn)，一個(gè)綠色的起點(diǎn)，一個(gè)黃色的終點(diǎn)對(duì)于RRT，我們做的第一件事就是將起點(diǎn)設(shè)置為隨機(jī)樹(shù)的根，那么我們就擁有了一顆只有根節(jié)點(diǎn)的樹(shù)這棵樹(shù)光禿禿的，只有根節(jié)點(diǎn)的話不但難看，而且還沒(méi)用。那么我們這時(shí)候就需要從這個(gè)根節(jié)點(diǎn)出發(fā)，向外拓展出新的葉?。拓展的方式很簡(jiǎn)單，就是隨機(jī)采樣+步?限制+碰撞檢測(cè)。 RRT在每輪迭代中會(huì)?成?個(gè)隨機(jī)采樣點(diǎn)NewNode，如果NewNode位于自由區(qū)域，那么我們就可以遍歷隨機(jī)樹(shù)中已有的全部節(jié)點(diǎn)，找出距離NewNode最近的節(jié)點(diǎn)ClosestNode。利?距離函數(shù)dist(NewNode, ClosestNode)得到二者之間的距離，如果滿足步長(zhǎng)限制的話，我們將接著對(duì)這兩個(gè)節(jié)點(diǎn)進(jìn)?碰撞檢測(cè)，如果不滿足步長(zhǎng)限制的話，我們需要沿著NewNode和ClosestNode的連線?向，找出?個(gè)符合步長(zhǎng)限制的中間點(diǎn)，用來(lái)替代NewNode。最后如果NewNode和ClosestNode通過(guò)了碰撞檢測(cè)，就意味著二者之間存在邊（edge），我們便可以將NewNode添加進(jìn)隨機(jī)樹(shù)中。首先以第一輪迭代為例，因?yàn)閯傞_(kāi)始我們的隨機(jī)樹(shù)中只有根節(jié)點(diǎn)，所以?論NewNode位于何處，遍歷出的最近節(jié)點(diǎn)ClosestNode必然是根節(jié)點(diǎn)。 假設(shè)我們遇到下圖這種情況，雖然采樣點(diǎn)NewNode位于步?限制之內(nèi)，但是卻很不巧沒(méi)有落在自由區(qū)域，即采樣點(diǎn)落在障礙物的位置時(shí)，這個(gè)采樣點(diǎn)會(huì)被算法舍棄。假設(shè)我們的步?限制為R，也就是說(shuō)對(duì)于每個(gè)ClosestNode節(jié)點(diǎn)來(lái)說(shuō)，只有當(dāng)NewNode落在其半徑為R的圓的范圍內(nèi)時(shí)，這個(gè)隨機(jī)采樣點(diǎn)NewNode才有可能被直接采納。如下圖所示，該紅?隨機(jī)采樣點(diǎn)雖然位于?由區(qū)域，但是明顯在根節(jié)點(diǎn)的步?限制之外。不過(guò)這個(gè)節(jié)點(diǎn)并不會(huì)被簡(jiǎn)單粗暴地舍棄。?是會(huì)沿著ClosestNode和NewNode的連線，找出符合步?限制的中間點(diǎn)，將這個(gè)中間點(diǎn)作為新的采樣點(diǎn)。如下圖所示，藍(lán)點(diǎn)就可以替代紅點(diǎn)作為新的采樣點(diǎn)。那么假設(shè)我們已經(jīng)通過(guò)第?輪迭代拓展出第?個(gè)葉?節(jié)點(diǎn)A，毫?疑問(wèn)地A的?節(jié)點(diǎn)就是根節(jié)點(diǎn)，假設(shè)我們第?輪迭代的隨機(jī)采樣點(diǎn)NewNode為圖中的點(diǎn)B，B落在A的步?限制范圍內(nèi)，但是A，B之間由于障礙物的阻擋，?法通過(guò)碰撞檢測(cè)，于是B就會(huì)被算法舍棄。假設(shè)我們的隨機(jī)采樣點(diǎn)是下圖中的B’，明顯B’位于?由區(qū)域，滿?步?條件，并且可以通過(guò)與點(diǎn)A的碰撞檢測(cè)，那么我們就在B’和A之間添加?條邊，并且將A設(shè)置為B’的?節(jié)點(diǎn)。學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的?伙伴?定知道，在樹(shù)結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)最多只有?個(gè)?節(jié)點(diǎn)，?節(jié)點(diǎn)可以擁有多個(gè)?節(jié)點(diǎn)。在經(jīng)歷了N輪迭代后，我們已經(jīng)獲得了?顆如下圖所示的隨機(jī)樹(shù)，這時(shí)我們發(fā)現(xiàn)此時(shí)的隨機(jī)采樣點(diǎn)竟然幸運(yùn)地落在了終點(diǎn)的步?限制范圍內(nèi)，并且?者之間不存在障礙物。這時(shí)我們便可以認(rèn)為，該采樣點(diǎn)和終點(diǎn)之間存在?條邊，于是將該節(jié)點(diǎn)設(shè)為終點(diǎn)的?節(jié)點(diǎn)，并把終點(diǎn)添加進(jìn)隨機(jī)樹(shù)。此時(shí)算法就可以結(jié)束迭代了，即規(guī)劃算法收斂。當(dāng)規(guī)劃算法收斂以后，只需要從終點(diǎn)開(kāi)始，沿著其?節(jié)點(diǎn)進(jìn)?回溯，就可以找 到起點(diǎn)-終點(diǎn)之間的有效路徑。那么總結(jié)?下，RRT?成的每輪迭代中都包含以下這些流程：1. ?成?個(gè)隨機(jī)采樣點(diǎn)NewNode，并判斷采樣點(diǎn)是否位于?由區(qū)域2. 遍歷隨機(jī)樹(shù)，找出距離NewNode最近的節(jié)點(diǎn)ClosestNode3. 判斷NewNode是否在ClosestNode的步?限制范圍內(nèi)，否則尋找中間點(diǎn)替代NewNode4. 判斷NewNode和ClosestNode之間是否存在障礙物，即碰撞檢測(cè)。5. 如果NewNode滿?以上所有約束條件，則將NewNode添加進(jìn)隨機(jī)樹(shù)，設(shè)置ClosestNode為NewNode的?節(jié)點(diǎn)。6. 判斷NewNode是否在終點(diǎn)的步?限制范圍內(nèi)，并對(duì)其?者做碰撞檢測(cè)。如果滿?條件則將該NewNode設(shè)為終點(diǎn)的?節(jié)點(diǎn)，并將終點(diǎn)加?隨機(jī)樹(shù)，即可結(jié)束迭代。否則繼續(xù)迭代。1.2 偽碼1.3 RRT的收斂性分析本節(jié)主要介紹了該規(guī)劃?法的理論特性。Theorem 1 如果存在長(zhǎng)度為k的連接序列，則將 x_init 連接到 x_goal 所預(yù)期的迭代次數(shù)不超過(guò)k/p Pf. 參考S.M. Lavalle and J.J. Kuffffner. "Randomized Kinodynamic Planning." The International Journal of Robotics Research. Vol. 20, Number 5, 2001, pp. 378 – 400. 第392頁(yè)Theorem 2 Pf. 參考S.M. Lavalle and J.J. Kuffffner. "Randomized Kinodynamic Planning." The International Journal of Robotics Research. Vol. 20, Number 5, 2001, pp. 378 – 400. 第393頁(yè)Theorem 3 當(dāng)頂點(diǎn)數(shù)趨于無(wú)窮時(shí)，在 x_init 處初始化的RRT包含 x_goal 的概率將趨近于1 Pf. 參考S.M. Lavalle and J.J. Kuffffner. "Randomized Kinodynamic Planning." The International Journal of Robotics Research. Vol. 20, Number 5, 2001, pp. 378 – 400. 第394頁(yè)定理1和定理2表示了規(guī)劃器的收斂率，定理3建?了規(guī)劃器是概率完備的（即，當(dāng)?shù)鷶?shù)趨于?窮時(shí)，找到解的概率趨于1我們可以看出，由于算法在未達(dá)到收斂條件之前是在不斷進(jìn)?迭代的，所以只要在規(guī)劃的起點(diǎn)和終點(diǎn)之間是存在有效的路徑，那么只要迭代的次數(shù)夠多，那么采樣點(diǎn)就夠多，隨機(jī)樹(shù)就長(zhǎng)得越茂密，能探索到的區(qū)域就?夠?，就必然可以找到有效的路徑。所以RRT是概率完備的。但是由于采樣點(diǎn)每次都是隨機(jī)的，所以算法并不能保證找到的路徑是最優(yōu)的路徑。因此RRT是?最優(yōu)的。1.4 程序示例1.5 參考1、S.M. Lavalle and J.J. Kuffffner. "Randomized Kinodynamic Planning." The International Journal of Robotics Research. Vol. 20, Number 5, 2001, pp. 378 – 400.2、Rapidly-Exploring Random Trees: A New Tool for Path Planning3、https://www.guyuehome.com/9405
什么是路徑規(guī)劃？ 路徑規(guī)劃（也叫運(yùn)動(dòng)學(xué)規(guī)劃），任務(wù)是確定控制輸入，以驅(qū)動(dòng)機(jī)器人從初始配置和速度到目標(biāo)配置和速度，同時(shí)服從基于物理的動(dòng)力學(xué)模型，且能確保機(jī)器人在環(huán)境中避開(kāi)障礙。說(shuō)白了，就是給你一張地圖，且已知障礙物分布，以及起始點(diǎn)和目標(biāo)點(diǎn)的坐標(biāo)，希望你根據(jù)這些信息，找到一條從起點(diǎn)到終點(diǎn)的能繞開(kāi)障礙物的有效路徑，如果可以，還希望這條有效路徑盡可能最優(yōu)（最短），并且希望找到這條有效路徑的時(shí)間盡可能短（算法足夠高效） 目前流行的路徑規(guī)劃分為兩大類：基于采樣的路徑規(guī)劃和基于搜索的路徑規(guī)劃。運(yùn)動(dòng)規(guī)劃的狀態(tài)空間是應(yīng)用于機(jī)器人變換的集合，稱為位姿空間（configuration space），引入了 C-空間、C-空間障礙物、自由空間等一系列概念，下面介紹一些概念：位姿（configuration）機(jī)器人一個(gè)位姿指的是一組相互獨(dú)立的參數(shù)集，它能完全確定機(jī)器人上所有的點(diǎn)在工作空間 W 中的位置，這些參數(shù)用來(lái)完整描述機(jī)器人在工作空間 W 中的狀態(tài)。一個(gè)位姿通常表示為帶有位置和方向參數(shù)的一個(gè)向量(vector)，用 q 表示。自由度（degrees of freedom）機(jī)器人的自由度定義為機(jī)器人運(yùn)動(dòng)過(guò)程中決定其運(yùn)動(dòng)狀態(tài)的所有獨(dú)立參數(shù)的數(shù)目，即 q 的維數(shù)。位姿空間（configuration space）位姿空間是機(jī)器人所有可能位姿組成的集合，代表了機(jī)器人所有可能的運(yùn)動(dòng)結(jié)果，稱為 C-空間，也可簡(jiǎn)記為 C。距離函數(shù)（distance function）C-空間中的距離函數(shù)定義為該空間中的一個(gè)映射
公眾號(hào)
版權(quán)所有 ©北太振寰（重慶）科技有限公司 | 渝ICP備2022008375號(hào)-4渝公網(wǎng)安備50009802002174號(hào) 法律聲明 隱私政策