“優(yōu)化”是生活中經(jīng)常使用的詞：開車時希望能在安全的前提下以最短時間到達目的地；雙11做功課考慮各種優(yōu)惠活動，希望獲得最大優(yōu)惠；超市進貨時需要考慮動銷存，最大化提高物品周轉(zhuǎn)效率。 這些問題都是“最優(yōu)化問題”，也是數(shù)學建模中的典型問題，是各大數(shù)學建模比賽里的?？?。 優(yōu)化題型有三要素：決策變量、目標函數(shù)、約束條件。 （1）決策變量：是決策者可以控制的因素，例如根據(jù)不同的實際問題，決策變量可以選為產(chǎn)品的產(chǎn)量、物資的運量及工作的天數(shù)等。 （2） 目標函數(shù)：是以函數(shù)形式來表示決策者追求的目標。例如目標可以是利潤最大或成本最小等。 （3） 約束條件：是決策變量需要滿足的限定條件。 歷年國賽優(yōu)化問題： 優(yōu)化問題的出發(fā)點是系統(tǒng)思維，其基本思路是在一定的約束條件下，保證各方面資源的合理分配， 最大限度地提升系統(tǒng)某一性能或系統(tǒng)整體性能，最終實現(xiàn)最理想結(jié)果。對于這類問題，想要建立并求解數(shù)學模型，可以參考以下思路： （1）明確目標，分析問題背景，確定約束條件，搜集全面的客觀數(shù)據(jù)和信息。 （2）建立數(shù)學模型，構(gòu)建變量之間的數(shù)學關(guān)系，設(shè)立目標函數(shù)。 （3）分析數(shù)學模型，綜合選擇最適合該模型的優(yōu)化方法。 （4）求解模型，通常借助計算機和數(shù)學分析軟件完成。 （5）對最優(yōu)解進行檢驗和實施。 PS.北太天元內(nèi)已有優(yōu)化工具箱optimization，可以調(diào)用工具箱解決優(yōu)化類問題。 下面給大家分享幾種數(shù)學建模中常用優(yōu)化算法： 1、線性規(guī)劃 在人們的生產(chǎn)實踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟效益的問題。此類問題構(gòu)成了運籌學的一個重要分支—數(shù)學規(guī)劃，而線性規(guī)劃(Linear Programming 簡記 LP)則是數(shù)學規(guī)劃的一個重要分支。 1.1 用北太天元求解線性規(guī)劃問題 北太天元內(nèi)已有優(yōu)化工具箱optimization，其中的linprog等相關(guān)函數(shù)可用于求解線性規(guī)劃問題。 1.2 線性規(guī)劃特點 優(yōu)點： （1）作為經(jīng)營管理決策中的數(shù)學手段，在現(xiàn)代決策中的應(yīng)用非常廣泛。 （2）有統(tǒng)一算法，任何線性規(guī)劃問題都能求解，解決多變量最優(yōu)決策的方法。 （3）訓練速度快。 （4）預測速度快，可以推廣到非常大的數(shù)據(jù)集，對稀疏數(shù)據(jù)也很有效。 缺點： （1）對于數(shù)據(jù)的準確性要求高，只能對線性的問題進行規(guī)劃約束，而且計算量大。 1.3 相關(guān)問題 運輸問題(產(chǎn)銷平衡)、指派問題（匈牙利算法）、對偶理論與靈敏度分析、投資的收益和風險。 2、整數(shù)規(guī)劃 規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。 2.1 用北太天元求解線性混合整數(shù)規(guī)劃問題 可在北太天元內(nèi)調(diào)用優(yōu)化工具箱optimization，使用intlinprog等相關(guān)函數(shù)求解線性混合整數(shù)規(guī)劃問題。 2.2 整數(shù)規(guī)劃的分類 如不加特殊說明，一般指整數(shù)線性規(guī)劃。對于整數(shù)線性規(guī)劃模型大致可分為兩類： （1）變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。 （2）變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。 2.3 整數(shù)規(guī)劃特點 原線性規(guī)劃有最優(yōu)解，當自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況： （1）原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 （2）整數(shù)規(guī)劃無可行解。 （3）有可行解（當然就存在最優(yōu)解），但最優(yōu)解值變差。 整數(shù)規(guī)劃最優(yōu)解不能按照實數(shù)最優(yōu)解簡單取整而獲得。 2.4 求解方法分類 （1）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。 （2）割平面法—可求純或混合整數(shù)線性規(guī)劃。 （3）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：過濾隱枚舉法；分枝隱枚舉法。 （4）匈牙利法—解決指派問題（“0-1”規(guī)劃特殊情形）。 （5）蒙特卡洛法—求解各種類型規(guī)劃。 3、非線性規(guī)劃 如果目標函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且，也不象線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個方法都有自己特定的適用范圍。 3.1 線性規(guī)劃與非線性規(guī)劃的區(qū)別 如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達到（特別是可行域的頂點上達到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點達到。 3.2 相關(guān)問題 無約束問題（一維搜索方法、二次插值法、無約束極值問題的解法）、約束極值問題（二次規(guī)劃、罰函數(shù)法）、飛行管理問題 4、動態(tài)規(guī)劃 動態(tài)規(guī)劃（dynamic programming）是運籌學的一個分支，是求解決策過程（decisionprocess）最優(yōu)化的數(shù)學方法。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。 雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。應(yīng)指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理。因此，在學習時，除了要對基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 5、多目標規(guī)劃 多目標規(guī)劃已經(jīng)應(yīng)用到科學的許多領(lǐng)域，包括工程、經(jīng)濟和物流，在兩個或更多沖突的目標之間存在取舍時，需要采取最優(yōu)決策。 解決多目標規(guī)劃問題的方法： （1）將多目標化為單目標 (給多個目標賦予權(quán)重) （2）保持多目標不變，根據(jù)自己的偏好選擇解 實際問題中，目標函數(shù)相互沖突是很常見的，例如購買汽車時，要求花費少且舒適度高或者要求性能好油耗低，這種問題并沒有絕對最優(yōu)解（因為并沒有確定多個目標的權(quán)值），但是我們可以根據(jù)自己的需要選擇一個相對好的（達到我們想要的最佳平衡）。為了尋求這種“最佳平衡”，可以采用算法帕累托最優(yōu)（Pareto optimal）。 以上部分內(nèi)容引用公眾號“科研交流”，希望對大家有幫助，覺得有用就點個贊吧。小助手會不定期更新數(shù)學建模干貨，可以多多關(guān)注喲。
數(shù)學實驗與數(shù)學建模：基于Baltamatica作者：華中科技大學 馬世拓首先非常感謝北京大學盧朓老師和李若老師等大咖對本項目的支持。這個項目是我春節(jié)的時候?qū)懙?，為了促進新手學習數(shù)學建模并推廣北太天元軟件。書稿是我編寫，參考了我大二的時候?qū)懙摹稊?shù)據(jù)科學基礎(chǔ)：from 0 to 1》和正在北大出版社審稿的《MATLAB數(shù)學建模》。有些地方可能寫的還有點生草，因為的確是對我在前期書稿的一個重排、刪改與整合。里面如果有一些有誤的地方歡迎與我聯(lián)系。項目的下載地址鏈接：github下載鏈接: github版數(shù)學建模教程gitee下載鏈接: gitee版數(shù)學建模教程百度網(wǎng)盤鏈接：鏈接：https://pan.baidu.com/s/17Q4_kcgP8Hx7hF6kWaykmA 提取碼：g79k為什么要寫這本教材我在華中科技大學的時候就很喜歡數(shù)學建模競賽，一直探索數(shù)學建模的教與學。我講過基于Python版本的數(shù)學建模，也講過基于MATLAB版本的數(shù)學建模。但是基于北太天元，我們還是第一次嘗試。Python和MATLAB這兩個系列更多的要求我們“先知其然，后知其所以然”，這也是“學術(shù)”和“工程”的辯證統(tǒng)一。北太天元則不同，它是剛起步的，有很多插件還沒有弄好，還存在一些底層的問題，所以在使用北太天元做建模的時候要注意從底層原理學習起，寧可學的東西沒那么多，但是要理解底層邏輯。這本教材的優(yōu)點據(jù)盧朓老師跟我說，這應(yīng)該是業(yè)內(nèi)第一本開源的北太天元教程。我的初衷是推廣到競賽中，讓學生有膽氣沖擊北太數(shù)模之星的冠名獎。在編寫過程中，我不喜歡市面上大多數(shù)教材的寫法，太死板，也太沒人性化。恕我直言，對于那些不講人話的學術(shù)類書稿，你如果是給同行傳閱倒也罷了，但是你的受眾是學生，我考教師資格證的時候就明確記得有“量力性”這一條要求。不講人話的書稿我必須得奉上一句“RNM退錢”，所以，我在編寫過程中盡可能做到通俗易懂，讓讀者能夠輕易上手接受。此外，書稿大綱是我在華中科大給同學們作數(shù)學建模培訓磨了幾輪才形成的大綱，在此基礎(chǔ)上進行了刪改，將過于復雜的一些章節(jié)去掉了，更容易被同學們接受。作為計科人，我始終記得譚志虎副院長和秦磊華副院長給我們強調(diào)的軟硬協(xié)同觀。在本書編寫的過程中，雖然更多的是數(shù)值計算與模擬方面的東西，但是也同樣以自己的理解從軟硬協(xié)同的角度在看這個軟件。本人在計算機領(lǐng)域功力尚淺，是當時專業(yè)課學的很拉胯的程度，如果有一些錯誤之處歡迎批評斧正，讀者朋友們見笑。特此聲明本書將免費開源不收取任何費用，但是請注意一些版權(quán)問題。如果是從我的github或gitee主頁下載的書稿，還請star一下可以咩謝謝。最后再次感謝盧朓老師和李若老師等人的支持！~
基于Baltamulink的汽車單自由度振動力學模型的建立由于汽車在行走時，路面不平，汽車行駛中的路面可簡化成正弦函數(shù)?？砂哑囆凶叩穆访婵醋黾睿雎暂喬サ膹椥耘c質(zhì)量，得到分析車身垂直振動的最簡單的單質(zhì)量系統(tǒng)，適用于低頻激勵情況。汽車行駛可看作如下模型： 上圖為單一自由度系統(tǒng)的簡圖，設(shè)X(t)及Xs(t)分別是質(zhì)量塊及支承的位移，支承的運動規(guī)律是：Xs =asinwt由于支承的運動，質(zhì)量塊收到的彈性恢復力為k(X - Xs)，阻尼力為c(Vx-Vxs)根據(jù)達朗伯原理可得如下的運動微分方程： 由（1）和（2）得： 在此系統(tǒng)中除了有彈性恢復力及阻尼力作用外，還始終作用于簡諧激勵力： Px=P0sinwt簡諧激勵：激勵隨時間的變化規(guī)律可用正弦或余弦函數(shù)表示；振動響應(yīng)亦為時間的正弦和余弦函數(shù)（簡諧振動）。結(jié)合上面的運動微分方程和簡諧激勵力方程，可得系統(tǒng)的運動微分方程為： 令：物體質(zhì)：m = 1 kg，彈簧剛度：k = 3 N/m，阻尼：c = 4 N·s/m，作用力P = 2sin(2t + π/3)，研究物體的位移隨時間的變化規(guī)律。通過北太真元建立系統(tǒng)運動微分方程模型，如下圖所示：設(shè)置參數(shù)：正弦波產(chǎn)生模塊：幅值：2；偏置：0；頻率(弧度/秒)：2；相位(弧度)：pi/3≈1；一階積分模塊：積分初始值：0.5；增益模塊：增益數(shù)值：4；常量模塊：常量值：3；結(jié)束時間：10s；求解器：ode4；步長：0.01s。得到的仿真結(jié)果，如下圖所示：
問題：二階電路動態(tài)系統(tǒng)中，該系統(tǒng)是由電阻R、電感L和電容C組成的無源網(wǎng)絡(luò)；ui(t)為輸入，i(t)為電流，u0(t)為輸出；設(shè)R=1Ω，L= 2H，C=2F；系統(tǒng)的初始狀態(tài)為0，外加的輸入為單位階躍信號。求系統(tǒng)的輸出波形。圖：二階電路動態(tài)系統(tǒng)首先，在解決該問題時，需要了解基爾霍夫電壓定律；它的內(nèi)容是，在任何一個閉合回路中，各元件上的電壓降的代數(shù)和等于電動勢的代數(shù)和，即從一點出發(fā)繞回路一周回到該點時，各段電壓的代數(shù)和恒等于零，即∑U=0。基爾霍夫電壓定律表明：沿著閉合回路所有元件兩端的電勢差（電壓）的代數(shù)和等于零?；蛘呙枋鰹椋貉刂]合回路的所有電動勢的代數(shù)和等于所有電壓降的代數(shù)和。以方程表達，對于電路的任意閉合回路有：其中，m 是這閉合回路的元件數(shù)目，vk 是元件兩端的電壓，可以是實數(shù)或復數(shù)?；鶢柣舴螂妷憾刹粌H應(yīng)用于閉合回路，也可以把它推廣應(yīng)用于回路的部分電路。根據(jù)上述原理，可寫出上面問題的回路方程如下：L di(t)/dt + 1/C∫i(t)dt + Ri(t) = ui(t)消去中間變量i(t)，可以得到描述網(wǎng)絡(luò)輸入輸出關(guān)系的微分方程為：LC d2u0(t)/dt2 + RC du0(t)/dt + u0(t) = ui(t)帶入電路參數(shù)R=1Ω，L= 2H，C=2F；整理可得：d2u0(t)/dt2 + 0.5 du0(t)/dt + 0.25u0(t) = 0.25ui(t)從方面方程可以得到，傳遞函數(shù)分子等式右邊系數(shù)：[0.25]；分母為左邊等式系數(shù)：[1 0.5 0.25]根據(jù)該系數(shù)，在北太真元設(shè)計傳遞函數(shù)仿真模型，再加入一個階躍信號模塊，得到仿真模型如下圖所示：設(shè)置：仿真時長：40s求解器為：定步長；步長：1s；得到仿真結(jié)果如下圖所示：在MATLAB中創(chuàng)建相同模型，仿真時間、仿真求解器、步長均相同；仿真模型和仿真結(jié)果如下圖所示： 通過對比發(fā)現(xiàn)，北太真元計算結(jié)果與MATLAB仿真結(jié)果完全一致。
問題：單質(zhì)量彈簧阻尼機械系統(tǒng)類似于下圖，外力f(x)為輸入量；質(zhì)量位移x(t)為輸出量；質(zhì)量m為1kg；剛度為5N/m；阻尼系數(shù)f為0.3N·s/m。繪制系統(tǒng)位移輸出響應(yīng)曲線。圖1：單質(zhì)量彈簧阻尼機械系統(tǒng)首先：單質(zhì)量彈簧阻尼機械系統(tǒng)的震動方程為：m dx2/dt2 + c dx/dt + kx = f(x)取狀態(tài)向量為X(t) = [x(t) dx/dt]’，輸出向量為U=[f(x)]，輸出向量為Y=[x(t)]，則狀態(tài)方程為： dX/dt = AX(t) + BUY = CX(t) + DU式中，A = [0 1; -k/m -c/m]; B = [0; 1/m]; C = [1 0]; D = 0;(m = 1; k = 5; c = 0.3)。其次，通過計算得到傳遞函數(shù)的分子分母系數(shù)為：[1]； [1 0.3 5];即，傳遞函數(shù)為G(s) = 1/(s^2 + 0.3 s + 5);最后，利用北太真元建立傳遞函數(shù)仿真模型，如下圖所示：設(shè)置：仿真時長：10s求解器為：定步長 ode4；步長：1s輸入常量10仿真結(jié)果如下圖所示：在MATLAB中創(chuàng)建相同模型，仿真時間、仿真求解器、步長均相同；仿真模型和仿真結(jié)果如下圖所示：通過對比發(fā)現(xiàn)，北太真元計算結(jié)果與MATLAB仿真結(jié)果完全一致。
1 模型假設(shè)1) 忽略轉(zhuǎn)向系的影響，以前、后輪轉(zhuǎn)角作為輸入；2) 汽車只進行平行于地面的平面運動，而忽略懸架的作用；3) 汽車前進（縱軸）速度不變，只有沿y軸的側(cè)向速度和繞z軸的橫擺運動(ay<0.4g) ；4) 驅(qū)動力不大，對側(cè)偏特性無影響；5) 忽略空氣阻力；6) 忽略左右輪胎因載荷變化引起輪胎特性的變化；7) 忽略回正力矩的變化。2 模型建立根據(jù)模型假設(shè)建立如圖1所示的二自由度汽車模型。對模型受力分析，存在3個方向的受力平衡，分別為x、y和繞Z的力矩平衡，建立力學方程如下。3 模型仿真在baltamulink中搭建狀態(tài)空間模型，模型如圖所示。（1）在前輪偏轉(zhuǎn)角為1，后輪偏轉(zhuǎn)角為1，車速為40km/h的情況下，輸出前后輪的橫向位移情況，輸出結(jié)果如圖3。圖34 結(jié)論通過建立汽車動力學模型，對汽車操縱性進行餓模擬。根據(jù)仿真結(jié)果可以發(fā)現(xiàn)車速和前輪轉(zhuǎn)角都對二自由度汽車的操縱穩(wěn)定性有很大影響。汽車以較低速度、較小的前輪轉(zhuǎn)角行駛時，是相對安全的。通過分析圖3可以看出前、后輪的橫向位移都是發(fā)散的，這是因為給前輪的一個階躍響應(yīng)，一直存在前輪轉(zhuǎn)角，同時系統(tǒng)沒有加入閉環(huán)控制，屬于開環(huán)控制，這就導致前后輪的橫向位移處于發(fā)散狀態(tài)。附錄baltamatica代碼如下clc;clear;close all;%% 基本車輛參數(shù)v=40/3.6;%輸入為km/h，方程單位為m/sm=16000;%車重I=10.85*m;%轉(zhuǎn)動慣量cf=340000;%側(cè)偏剛度cr=cf;lf=2.65;%前軸到重心的距離lr=3.35;%后軸到重心的距離a=pi/180;%% 組裝矩陣A=[-(cf+cr)/(m*v) -1-(cf*lf-cr*lr)/(m*v^2) 0 0 -(cf*lf-cr*lr)/I -(cf*lf^2+cr*lr^2)/(I*v) 0 0 v lf 0 0 v -lr 0 0];B=[cf/(m*v) cr/(m*v) cf*lf/I cr*lr/I 0 0 0 0];C=[0 0 1 0 0 0 0 1];D=zeros(2,2);
點擊鏈接查看：英才計劃與中學生培養(yǎng)（一）：卡脖子形勢下，人才培養(yǎng)方向何在？本文為北京大學重慶大數(shù)據(jù)研究院基礎(chǔ)軟件科學研究中心執(zhí)行主任、北太振寰創(chuàng)始人盧朓副教授在中國科協(xié)組織的中學生創(chuàng)新人才培養(yǎng)論壇上的分享。前文觀點 計算是求解數(shù)學模型的手段?？墒菍τ谥袑W生來說，很多算法的實現(xiàn)并非易事，因此可選擇的可以求解的數(shù)學模型就很少了。例如，求函數(shù)的最大值的問題，往往只能對二次函數(shù)，三角函數(shù)來求解，稍微復雜的函數(shù)就不會了。使用數(shù)值計算通用軟件，消除中學生求解難的疑慮 其實，很多數(shù)學模型對中學生來說還是比較容易掌握的。為了讓學生建模的時候可以選擇更多的模型，我建議學生使用數(shù)值計算通用軟件來消除求解難的顧慮。 借助數(shù)值計算通用軟件，更有利于培養(yǎng)同學們的數(shù)學建模能力，我舉幾個例子： 第一個例子是線性規(guī)劃、二次規(guī)劃和整數(shù)規(guī)劃之類的模型。實際上，中學生已經(jīng)接觸過這樣的問題了，但是往往局限在很小的數(shù)值范疇內(nèi)。這種模型的威力并未得到充分展現(xiàn)。 中學生如果使用數(shù)值計算通用軟件來求解此類問題，那么就可以把更多精力放在體會這種數(shù)學模型的特點上。 我在B站上給出了一個視頻，展示了如何使用數(shù)值計算通用軟件求解整數(shù)規(guī)劃問題，我相信感興趣的中學生可以很快學會使用計算機求解整數(shù)規(guī)劃問題的方式。 第二個例子與使用常微分方程的初值問題建模有關(guān)，這個可以和物理學科結(jié)合起來。我們可以通過測量物體在不同時刻的位移，把數(shù)據(jù)畫出來，借助于常微分方程給出物理運動規(guī)律，這樣就是在重走牛頓當年的發(fā)現(xiàn)之路。至于常微分方程初值問題的求解則可以借助數(shù)值計算通用軟件來完成。 第三個例子是關(guān)于機器學習和人工智能的算法。 我在B站上給出了如何使用數(shù)值計算通用軟件讀取Excel數(shù)據(jù)，然后如何使用樸素貝葉斯來判斷西瓜好壞的例子，也可以供中學生學習。 總之，我建議中學生借助數(shù)值計算通用軟件來了解讀取數(shù)據(jù)、數(shù)學建模、數(shù)值計算以及計算結(jié)果的可視化等環(huán)節(jié)，然后選取自己感興趣的部分多下功夫，其它環(huán)節(jié)則可以通過數(shù)值計算通用軟件具有的內(nèi)置函數(shù)以及插件來完成。 參加“英才計劃”的學生不一定都要找現(xiàn)實中的問題來做數(shù)學建模，還可以通過閱讀文獻來學習。如果對數(shù)學或者其他學科的某些定理和知識點感興趣，可以通過數(shù)值計算通用軟件來驗證，加深對這些定理的理解。 這樣的計算不能代替證明，但是幫助大家體會這個知識點的含義。 通過“英才計劃”，我希望學生在多個方面有所收獲，如： 1.提升搜集、理解、組織數(shù)據(jù)的技能，數(shù)學建模能力，團隊協(xié)作能力以及論文寫作能力； 2.培養(yǎng)定量研究發(fā)展變化規(guī)律的習慣，培養(yǎng)好奇心、想象力、創(chuàng)造力和表達力； 3.了解計算機算法和原理、數(shù)值計算通用軟件的基本用法，對數(shù)學知識的用途有更深的認識等。從數(shù)值計算通用軟件的推薦談開去：“被禁”以后，我們該做些什么？ 科學計算已經(jīng)成為與理論和實驗并列的科學研究的基本手段?？茖W計算軟件可以分成兩種類型：專用型和通用型。 通用型科學計算軟件是開發(fā)工業(yè)軟件的重要基礎(chǔ)性工具，長期以來，這一部分的市場由國外公司壟斷。通用型數(shù)值計算軟件就好像連接各個工廠的高速公路一樣，是數(shù)值計算軟件中的基礎(chǔ)設(shè)施。有了高速公路的連接，工廠的原材料才能運進來，生產(chǎn)的產(chǎn)品才能更方便地送到用戶手里。 在向參加“英才計劃”的學生推薦數(shù)值計算通用軟件時，我最初考慮的是MATLAB。但由于這是一款商業(yè)軟件，我擔心購買軟件會給學生帶來額外的經(jīng)濟負擔，所以并未選擇。 2020年，美國商務(wù)部宣布新增33 家中國公司及機構(gòu)列入 “實體清單”，中國大陸共有 13 所高校被列入該清單，分別為哈爾濱工業(yè)大學、哈爾濱工程大學、中國人民大學、北京航空航天大學、西安交通大學、西北工業(yè)大學、四川大學、電子科技大學、湖南大學、國防科技大學、同濟大學、南昌大學、廣東工業(yè)大學。MATLAB 所屬公司 MathWorks 中止了對以上高校的正版授權(quán)。 這讓我為當初自己的選擇感到慶幸，也讓很多人意識到通用型數(shù)值計算軟件是一個“卡脖子”技術(shù)，沒有這個技術(shù)，我們自己開發(fā)的專用軟件或者算法就無法得到廣泛的應(yīng)用。但當時我仍想著：好在，我們還有Python可以使用。 可在俄羅斯-烏克蘭戰(zhàn)爭爆發(fā)后，據(jù)相關(guān)報道顯示“目前已經(jīng)有多達30個開源項目加入了對俄羅斯的抵制，其中甚至包括亞馬遜（AWS Terraform modules）和Oracle等科技巨頭的項目，也不乏MongoDB、pnpm、es5-ext、Drupal、Redis Desktop Manager等流行項目”。這讓我進一步認識到：這類開源軟件的主導權(quán)如果是掌握在別人的手里，仍然蘊藏著危險。 事實上，中國的基礎(chǔ)數(shù)學和理論數(shù)學研究在國際上還是處于領(lǐng)先地位。在涉及具體的算法或?qū)Ｓ眯蛿?shù)值計算軟件領(lǐng)域，我們中國的科學家也取得了很好的成績，在有關(guān)算法的頂級雜志上，中國人發(fā)表論文的數(shù)量和質(zhì)量都位于前列，有很多算法被國外的通用型數(shù)值計算軟件集成，得到了廣泛的應(yīng)用。 但是我們?nèi)狈ο馦ATLAB這樣的數(shù)值計算通用軟件。這是為什么呢？ 因為，通用型的數(shù)值計算軟件的開發(fā)需要耗費大量的時間，需要投入大量的人力物力，無法在短期內(nèi)做出高精尖的成果。研發(fā)過程中需要有關(guān)鍵的技術(shù)基礎(chǔ)，要掌握核心關(guān)鍵的規(guī)律、知識和方法，這些都只能通過“學中干”和“干中學”相結(jié)合才能獲得。 工業(yè)軟件可以說是現(xiàn)代產(chǎn)業(yè)體系之魂。目前，歐美的工業(yè)軟件幾乎已經(jīng)滲透了所有工業(yè)領(lǐng)域的核心環(huán)節(jié)。發(fā)展具有自主知識產(chǎn)權(quán)的工業(yè)軟件刻不容緩，對掌握我國產(chǎn)業(yè)發(fā)展的主導權(quán)，增強工業(yè)體系的韌性和抗打擊性都非常重要。 而通用型數(shù)值計算軟件的研發(fā)意義尤為重大：它不僅自己就是一個工業(yè)軟件，還能夠成為其他工業(yè)軟件的底座，防止國產(chǎn)工業(yè)軟件被釜底抽薪；同時，數(shù)值計算通用軟件也是一個非常好的創(chuàng)新平臺；正如前文所述，此類軟件對于人才培養(yǎng)也至關(guān)重要。 通用型數(shù)值計算軟件的成功研發(fā)，將是對人類文明的貢獻，也是國家軟實力的標志之一。因此，雖然困難重重，我和其他志同道合的伙伴們還是決心開發(fā)具有自主知識產(chǎn)權(quán)的通用型數(shù)值計算軟件，破解“卡脖子”問題。 （未完待續(xù)）作者簡介
17.1 原理 完整思想請看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言,，和其他的基于搜索的路徑規(guī)劃算法的區(qū)別僅在于啟發(fā)式函數(shù)的不同. 雙向A*則稍微復雜些，但可以簡單理解為起始節(jié)點和終點同時將對方視為目標節(jié)點，并按照A*的啟發(fā)式函數(shù)，相向生長，當兩者相遇時，則停止迭代，并分別往回追溯自己的父節(jié)點即可得到路徑。17.2 程序示例
16.1 原理 完整思想請看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言，，和其他的基于搜索的路徑規(guī)劃算法的區(qū)別僅在于啟發(fā)式函數(shù)的不同 A*則是結(jié)合了Best-first Searching和Dijkstra，它將當前節(jié)點到初始節(jié)點和到目標節(jié)點的距離之和作為啟發(fā)式函數(shù)。16.2 程序示例16.3 參考A Formal Basis for the heuristic Determination of Minimum Cost Paths
15.1 原理完整思想請看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言，和其他的基于搜索的路徑規(guī)劃算法的區(qū)別僅在于啟發(fā)式函數(shù)的不同Dijkstra則和Best-first-searching相反，它不是將到目標節(jié)點的距離作為啟發(fā)式函數(shù)，而是將到起始節(jié)點的距離作為啟發(fā)式函數(shù)。15.2 程序示例
14.1 原理這里的Best-first-searching和數(shù)據(jù)結(jié)構(gòu)里學的圖搜索算法BFS（廣度優(yōu)先搜索）不是一個東西。完整思想請看我前面寫的路徑規(guī)劃（十三）基于搜索的路徑規(guī)劃算法-前言下面說說Best-first-searching的核心思想：Best-first Searching的啟發(fā)式函數(shù)f(x)=dist(x,x_goal)，即Best-first Searching每一步都在預選集合中尋找距離目標節(jié)點最近的的那個節(jié)點。這里的dist(x,y)，如果節(jié)點x,y無法通過碰撞檢測，則為inf，如果能通過碰撞檢測，可以直接用歐幾里得距離代替。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ī)劃算法基本都是一個套路，它們都是根據(jù)啟發(fā)函數(shù)重備用節(jié)點的集合中來尋找下一個節(jié)點，不同的啟發(fā)函數(shù)也就有不同的搜索類算法。搜索類算法是離散化的算法，體現(xiàn)在整個圖的區(qū)域是由有限個小方塊區(qū)域組成的。我們暫且把這些小方塊區(qū)域稱為“節(jié)點”。因此，整個區(qū)域被有限個節(jié)點填充，且每個節(jié)點的鄰居節(jié)點為有限個。設(shè)置兩個集合OPEN,CLOSE，OPEN初始狀態(tài)設(shè)為{x_init}，CLOSE 初始狀態(tài)設(shè)為空集。依據(jù)不同的啟發(fā)式函數(shù)，從open集中選擇一個點加入到close集中，然后拓展open集，如上圖，右下角的某個點被某種啟發(fā)式函數(shù)選中，加入到close集中，并相繼拓展open集下面介紹下搜索類算法的前進過程：當上述偽碼退出循環(huán)后，沿著x_goal的父節(jié)點往前回溯極為路徑各搜索類算法的區(qū)別在于第三行啟發(fā)函數(shù)的類型的不同，導致連接的節(jié)點不同。
幾種RRT對比如下：幾種RRT對比視圖mp4 RRT及其變種都是依托于采樣+在樹結(jié)構(gòu)上加減枝的形式進行路徑規(guī)劃的，具有全局收斂特性，但是效率穩(wěn)定性不高。不過可以針對性地對其主要函數(shù)進行優(yōu)化進行效率的改進：優(yōu)化采樣，優(yōu)化樹結(jié)構(gòu)等。一種加速RRT的思路就是，從起始點和目標節(jié)點同時生長RRT樹，這就是connected_RRT。此外，針對變化的環(huán)境，還有extend_RRT和Dynamic_RRT。 RRT*是一種趨近于最優(yōu)路徑的方案，它通過重布線來實現(xiàn)這一目的，它在理論上能達到最優(yōu)解，但它全局隨機撒點的特性導致它在遠離目標路徑的地方做了過多的生長。 為了集中優(yōu)化資源，RRT*-smart應(yīng)運而生，它比較在乎路徑和障礙物的拐點的附近的優(yōu)化，它通過路徑優(yōu)化步驟判斷出路徑和障礙物的拐點，并在拐點的鄰域內(nèi)投入更多的資源（即撒更多的點），以實現(xiàn)集中優(yōu)化資源。 但RRT*-smart依然浪費了太多的隨機點在遠離目標路徑的區(qū)域，那什么才叫不遠離目標路徑的區(qū)域呢？informed RRT*則解決了這一問題，它利用初始路徑的長度，起始點和目標點，畫出了一個橢圓，informed RRT*認為，這個橢圓區(qū)域就是不遠離目標路徑的區(qū)域，生成這個橢圓后，后續(xù)的隨機撒點只灑在這個橢圓區(qū)域內(nèi)，當更優(yōu)的路徑被發(fā)現(xiàn)，則根據(jù)這個新路徑的長度，縮小橢圓，進一步在有效區(qū)域集中撒點資源，以實現(xiàn)加速。 然而，RRT*類的算法是總會面臨一個問題，那就是重布線，這個令RRT*能夠逼近最優(yōu)解的創(chuàng)新恰恰成為了它慢的原因。 于是，另一種思路被提出，那就是提前給定隨機點，然后通過啟發(fā)式函數(shù)來連接這些點以生長路徑，這就是FMT*，F(xiàn)MT*專門針對解決高維構(gòu)型空間中的復雜運動規(guī)劃問題，在預先確定的采樣點數(shù)量上執(zhí)行前向動態(tài)規(guī)劃遞歸，并相應(yīng)地通過在代價到達空間中穩(wěn)步向外移動生成路徑樹。FMT*能很快的找到一條路徑，但是當我們想對這條路徑進行優(yōu)化時，只有通過加密隨機采樣點的方式，然而，F(xiàn)MT*是一種單批算法，面對新的采樣點分布時，它只能重新開始計算。 為了融合informed RRT*在有效區(qū)域集中隨機點的特點和FMT*快速生長的特點，就誕生了BIT*。它能夠在橢圓區(qū)域內(nèi)分批撒點，實現(xiàn)快速生長的同時，還能自我優(yōu)化。參考https://www.youtube.com/watch?v=TQIoCC48gp4
11.1 原理 簡單來說，BIT*是結(jié)合了Informed RRT*和FMT*的優(yōu)點的一種算法?；仡櫼幌?，Informed RRT*是對RRT*的一種優(yōu)化，在RRT*生成一個初始路徑后，則以初始路徑的長度，起始點和目標點為焦點，畫一個橢圓，Informed RRT*在后續(xù)隨機采點時，只取落在這個橢圓內(nèi)的點，一次采一個點，重復lm次。FMT*則與RRT那一套不同，它不是邊采點，邊生長樹，而是一次性提前在整個區(qū)域（不包含障礙物區(qū)域）內(nèi)采lm個點，只重復一次。 下面我們來說說，Informed RRT*和優(yōu)缺點FMT*，然后就知道為什么要引出BIT*了。 先說FMT*，F(xiàn)MT*的優(yōu)點是從起始位置開始構(gòu)建，沒有重布線過程，因此節(jié)約時間，適用于復雜的障礙物環(huán)境。但是FMT*的缺點是，它只有1批，F(xiàn)MT*路徑的精度完全取決于當前批撒點的密度，當你想要提升精度時，只能重新開始一批，重新更密集的撒點，然后重新開始規(guī)劃。 再說Informed RRT*，Informed RRT*的優(yōu)點恰好彌補了FMT*的缺點，想要提升精度，只需撒更多的點就好了，而Informed RRT*的撒點過程時一直在進行的，它一批只撒一個點，重復很多批，開始新的批的時候之前的信息不會被拋棄，只要Informed RRT*一直撒點，就可以達到任意精度。但是Informed RRT*的缺點也顯而易見，它需要重布線，計算效率低。 所以自然就想到，能不能利用FMT*的優(yōu)點，提前撒好點，不用重布線，提升計算效率，又能多批進行，以不斷提升精度？當然能，這就是BIT*算法 BIT*的過程總結(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中，當初始路徑已經(jīng)生成之后，如果重點在初始路徑周圍進行采樣的話，可以明顯提高路徑優(yōu)化效率。Informed RRT就是進一步優(yōu)化了采樣函數(shù)，采樣的方式是以起點和終點為焦點構(gòu)建橢圓形采樣區(qū)域。 回顧一下RRT*-smart，因為在某區(qū)域撒點越多，該區(qū)域的優(yōu)化效果越好，而單純的RRT*是在全域內(nèi)隨機撒點，優(yōu)化效果沒有得以集中，RRT*-smart認為經(jīng)過路徑優(yōu)化后的路徑的拐點在障礙物的附近，它認為這個拐點的附近需要著重優(yōu)化，所以RRT*-smart在進一步撒點的過程中，將一些隨機點偏袒的撒在這個拐點的附近鄰域。 這里的informed RRT*也是這樣認為，它認為單純的RRT*在整個區(qū)域內(nèi)隨機撒點，優(yōu)化效果太過分散，如果我能知道我最終優(yōu)化的路徑在哪一塊區(qū)域，那我就只在這一區(qū)域內(nèi)撒點不就好了嗎？informed RRT*就是這樣做的。注意： informed RRT*是在RRT*算法給出一條初始路徑后，對這個初始路徑繼續(xù)優(yōu)化的步驟才起作用的，它對于這個初始路徑的生成沒有幫助。10.2 思路 根據(jù)高中數(shù)學知識可以知道，在橢圓上的點到橢圓兩焦點的距離之和相同，橢圓外的點的距離到兩焦點的距離之和大于橢圓上的點到兩焦點的距離之和，橢圓內(nèi)的點反之。 回顧一下RRT*的搜索圖，根據(jù)上面這個知識點可以發(fā)現(xiàn)，其實RRT在已經(jīng)得到一條可行路徑之后，可以將采樣空間收縮到一個橢圓形區(qū)域中，區(qū)域之外的點對于縮短規(guī)劃出的路徑長度并沒有實際價值。 informed RRT就是的主要思想就是上面這種思想，在獲取可行路徑之后，將采樣空間限制在一個橢圓形區(qū)域中，并且隨著路徑長度的不斷縮短，逐漸縮小該橢圓形區(qū)域。這個思想其實在以前就有，但是提出informed RRT的論文中提出了對這個橢圓形區(qū)域直接采樣的方法。 可能有人會直接想，這里只不過是縮小了采樣空間，并不會明顯改進算法。但是實際上，當拓展到高維空間時，效率的提升是巨大的。那么，如何表達這個橢圓呢？下面介紹橢圓采樣區(qū)域的表達方式方法1：先在標準橢圓的方程中采樣，再將采樣點旋轉(zhuǎn)平移到實際采樣區(qū)域，需要兩個矩陣：平移向量、旋轉(zhuǎn)矩陣。這兩個參數(shù)只需要在初始化時計算即可轉(zhuǎn)換后的坐標為：方法2：利用超橢圓體然后在二維平面映射這里放一段.m文件取橢圓隨機點的代碼（思路如方法2）：除了采樣過程外，Informed RRT*的流程和RRT*是一樣的。10.3 偽碼偽代碼中是在RRT的偽代碼基礎(chǔ)上改的，標紅的地方是informed RRT 更改的地方?？梢钥闯?，其實主體框架上面并沒有太多更改，實際上也是，主要的更改都在第七行，也就是采樣這一步。這是采樣這一步的偽代碼。informed RRT將目前已經(jīng)搜索到的最短路徑作為cbest，起點和終點之間的距離作為cmin，以此構(gòu)建橢圓。當還沒有規(guī)劃結(jié)果時，cbest為inf，也就是和經(jīng)典RRT沒有區(qū)別。10.4 程序示例程序在尋找初始路徑的過程和普通RRT*一樣，在全局域中隨機撒點，迭代到1282次時首次找到初始路徑，然后我們以起始點和目標點為焦點，初始路徑的長度為點到兩焦點的距離之和，畫出一個橢圓：我們隨后的隨機點的選取范圍不再是全局域了，新采的樣本點被限制在這個橢圓中，下圖中的圓圈代表迭代1283-2509次的隨機點的分布，可見，新的隨機點全部被限制在橢圓中：當?shù)?510次時，新的總長度更短的路徑被找到，，隨后，我們以起始點和目標點為焦點，以這個新的路徑的長度為到兩焦點的距離，畫出一個比之前更小的橢圓：同樣的，迭代次數(shù)為2510-2865次的循環(huán)中的新的隨機點被限制在這個新的更小的橢圓中，使隨機點資源進一步集中：當?shù)?866次時，找到一個路徑更短的路徑：10.5 參考Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic
9.1 原理 FMT*算法專門針對解決高維構(gòu)型空間中的復雜運動規(guī)劃問題，它是為高密度障礙物的環(huán)境構(gòu)建的算法。該算法被證明是漸近最優(yōu)的，并且比同類型算法（RRT*）更快收斂到最優(yōu)解。FMT*算法在預先確定的概率繪制的樣本數(shù)量上執(zhí)行“惰性”動態(tài)規(guī)劃遞歸，以生長路徑樹，該路徑樹在成本到達空間中穩(wěn)定地向外移動。 FMT*的最終產(chǎn)物是一棵樹，它在連續(xù)空間中獲取一批樣本，然后它能在圖中使用惰性的動態(tài)編程搜索該樣本集合，并以此找到路徑，這也是一個漸進最優(yōu)的解決方案，F(xiàn)MT*相比于RRT*的加速效果優(yōu)勢在高維和碰撞檢查很昂貴的情況下尤其突出。很棒的一點是，F(xiàn)MT*是從起始位置開始構(gòu)建，而不是像RRT*是在空間的任意位置采點，因為這可能會得到非常遠的點或非常近的點，這有什么好處呢？這意味著你不必在樹中回溯以進行重布線，因為這在計算上效率低下。FMT*比RRT*更好，因為它創(chuàng)建的連接接近最佳，沒有重布線。 FMT*算法在預先確定的采樣點數(shù)量上執(zhí)行前向動態(tài)規(guī)劃遞歸，并相應(yīng)地通過在代價到達空間中穩(wěn)步向外移動生成路徑樹。FMT*執(zhí)行動態(tài)規(guī)劃遞歸，其特點有三個關(guān)鍵特征:·它是為磁盤連接圖量身定制的，其中兩個樣本的距離低于給定的界限（稱為連接半徑）則這兩個樣本被認為是鄰居，因此是可連接的?！に瑫r執(zhí)行圖構(gòu)造和圖搜索?！榱嗽u估動態(tài)規(guī)劃遞歸中的即時成本，算法“懶惰地”忽略了障礙物的存在，每當與新樣本的局部最優(yōu)(假設(shè)沒有障礙物)連接與障礙物相交時，該樣本就會簡單地跳過并留待以后，而不是在鄰域中尋找其他連接。注意：FMT*的樣本點是提前生成好的，然后把這些點固定，再利用這些固定好的點來生成行進樹，注意區(qū)別于RRT*那一套，RRT*是生成隨機點的同時，生成行進樹。9.2 算法思路上圖（a）是RRT*添加新節(jié)點的某一步，上圖（b）（c）是FMT*添加新節(jié)點的某一步。 先看RRT*，節(jié)點9是新考慮的節(jié)點，它在第一次重布線時，需要從它的所有鄰居節(jié)點中找出一個父節(jié)點，使得節(jié)點9到達起始節(jié)點的cost最小，因此節(jié)點9需要計算它到4、5、6、8號節(jié)點的距離并同時進行碰撞檢測，因此，第一次重布線過程就要求待加入的節(jié)點對它的所有鄰居節(jié)點進行一次碰撞檢測，第二次重布線過程也需要計算距離和碰撞檢測，但這在第一次重布線過程中做過了，可以記錄先來直接利用，因此第二次重布線過程碰撞檢測這一步可以不用重復進行，因此，總的來說，RRT*每新加入一個節(jié)點，該節(jié)點需要對它的所有鄰居節(jié)點進行一次碰撞檢測。 再看FMT*，上圖（b）（c）中的x就是新考慮的節(jié)點，在圖（b）中，x需計算它到集合V_open中所有的鄰居節(jié)點的cost，但不需要進行碰撞檢測，從中選擇一個能使它到達初始節(jié)點總cost最小的節(jié)點作為它的父節(jié)點，然后，對它和這個父節(jié)點的連線進行碰撞檢測，如果能通過碰撞檢測，則加入x，若不能，則下一個x，因此，總的來說，F(xiàn)MT*每新加入一個節(jié)點，永遠只需要進行一次碰撞檢測。FMT*比RRT*每新加入一個節(jié)點需要進行的碰撞檢測次數(shù)少得多，而且FMT*也是漸進最優(yōu)的，這就是FMT*相比于RRT*的優(yōu)勢所在。9.3 偽碼9.4 程序示例下圖中的 圓圈代表提前采好的隨機點9.5 參考Fast Marching Tree: a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions?
8.1 原理 最初，RRT*-Smart 像 RRT* 一樣隨機搜索狀態(tài)空間。類似地，找到第一條路徑就像 RRT* 會嘗試通過配置空間中的隨機采樣來找到路徑一樣。一旦找到第一條路徑，它就會通過互連直接可見的節(jié)點來優(yōu)化它。此優(yōu)化路徑產(chǎn)生用于智能采樣的偏置點。在這些偏置點，采樣以規(guī)則的間隔進行 隨著算法的進展和路徑的不斷優(yōu)化，此過程將繼續(xù)進行。每當找到更短的路徑時，偏差就會轉(zhuǎn)向新路徑。 RRT*是一邊生長一邊優(yōu)化的，RRT*的重心在于找到最優(yōu)路徑。RRT*樹生長到能連接起點和終點后，這就已經(jīng)有一條初始路徑了。 這顆RRT*樹可以繼續(xù)生長，越生長可以得到的路徑相比初始路徑會越優(yōu)。然而，這個繼續(xù)生長的過程對于RRT*而言效率非常低，由此衍生出RRT*-smart算法，專門解決這一問題。 注意到，RRT*-smart是在RRT*算法已生成初始路徑后，在此基礎(chǔ)上，想對初始路徑繼續(xù)優(yōu)化的步驟才起作用，所以RRT*-smart對于生成初始路徑并沒有加速幫助。 RRT*-smart的優(yōu)勢在于：它專注于提升路徑接近障礙物拐點處的優(yōu)化速度。RRT*-smart算法的思路是這樣的：在原始RRT*算法的基礎(chǔ)上加了兩步：①路徑優(yōu)化路徑優(yōu)化的本質(zhì)是利用三角形兩邊之和大于第三邊 假設(shè)RRT*生成的初始路徑長這樣 具體操作如下： 一旦RRT*給出了一條初始路徑，將初始路徑中彼此可見的節(jié)點直接相連。迭代過程從xgoal開始，向xinit檢查與每個節(jié)點的連續(xù)父節(jié)點的直接連接，直到無沖突條件失敗。下圖給出一個示例。 信標（Z_beacons）：經(jīng)過路徑優(yōu)化后的路徑中除了起點和終點之外的節(jié)點，標記為信標（Z_beacons），如上圖中的綠點。②智能采樣在RRT*算法中，在生成初始路徑后，在此RRT*樹的基礎(chǔ)上繼續(xù)采點，采點越多，路徑優(yōu)化效果越好，但此采點，是完全隨機的采點，因此效率低下，RRT*-smart則不是完全隨機的采點。在RRT*-smart算法中，利用了這樣一種思想：智能采樣背后的想法是通過生成盡可能靠近障礙物頂點的節(jié)點來接近最優(yōu)性。在基于采樣的RRT*-smart中，路徑僅沿著靠近障礙物拐點的外圍進行優(yōu)化，解決的辦法就是：在障礙物拐點的外圍多多采點。如下圖所示： 問：那么RRT*-smart如何實現(xiàn)在障礙物拐點的外圍多多采點呢？答：利用①路徑優(yōu)化過程中給出的信標（Z_beacons）。一旦找到初始路徑，智能采樣就會開始，在以Z beacons為中心的半徑為R beacons的球中直接生成一定數(shù)量的樣本。采樣偏向于這些信標，因為它們提供了有關(guān)障礙物頂點（或圓形障礙物的外圍）位置的有用線索。因此，這些信標需要被最大節(jié)點包圍，以優(yōu)化這些轉(zhuǎn)彎處的路徑。與 RRT* 相比，這一特征迫使所提出的算法以更少的迭代次數(shù)達到最優(yōu)解。注意：信標（Z_beacons）是需要隨著優(yōu)化路徑的更新而更新的。即當z_goal.cost變小時，說明路徑得到了優(yōu)化，那么就要啟用之前①路徑優(yōu)化算法來重新確定新的z_beacons。 8.2 偽碼 8.3 程序示例下圖中的線段代表由RRT*生成的初始RRT樹，圓圈代表在初始RRT樹基礎(chǔ)上，繼續(xù)采點的分布，可見在幾個“拐點處”的圓形領(lǐng)域內(nèi)我們有額外的采點以加強在這部分的采點 路徑優(yōu)化后確定出拐點 經(jīng)過路徑優(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é)點以及其周圍的節(jié)點到起點的cost(可以是路徑或者時間等目標函數(shù))最短，而不是僅僅尋找離它近的節(jié)點，而且在找到路徑后不會停止，而是繼續(xù)進行采樣來優(yōu)化得到的路徑。 盡管RRT算法是一個相對高效率，同時可以較好的處理帶有非完整約束的路徑規(guī)劃問題的算法，并且在很多方面有很大的優(yōu)勢，但是RRT算法并不能保證所得出的可行路徑是相對優(yōu)化的。因此許多關(guān)于RRT算法的改進也致力于解決路徑優(yōu)化的問題，RRT*算法就是其中一個。RRT*算法的主要特征是能快速的找出初始路徑，之后隨著采樣點的增加，不斷地進行優(yōu)化直到找到目標點或者達到設(shè)定的最大循環(huán)次數(shù)。RRT*算法是漸進優(yōu)化的，也就是隨著迭代次數(shù)的增加，得出的路徑是越來越優(yōu)化的，而且永遠不可能在有限的時間中得出最優(yōu)的路徑。因此換句話說，要想得出相對滿意的優(yōu)化路徑，是需要一定的運算時間的。所以RRT*算法的收斂時間是一個比較突出的研究問題。但不可否認的是，RRT*算法計算出的路徑的代價相比RRT來說減小了不少。RRT*算法與RRT算法的區(qū)別主要在于兩個針對新節(jié)點 xnew 的重計算過程，分別為：·重新為 xnew 選擇父節(jié)點的過程·重布線隨機樹的過程7.1.1 重新選擇父節(jié)點過程 在新產(chǎn)生的節(jié)點 xnew 附近以定義的半徑范圍內(nèi)尋找“近鄰”，作為替換 xnew 父節(jié)點的備選。依次計算“近鄰”節(jié)點到起點的路徑代價加上 xnew 到每個“近鄰”的路徑代價，具體過程見上圖。 圖(a)中表現(xiàn)的是隨機樹擴展過程中的一個時刻，節(jié)點標號表示產(chǎn)生該節(jié)點的順序，0節(jié)點是初始節(jié)點，9節(jié)點是新產(chǎn)生的節(jié)點 xnew，6節(jié)點是產(chǎn)生9節(jié)點的 xnear，節(jié)點與節(jié)點之間連接的邊上數(shù)字代表兩個節(jié)點之間的歐氏距離(這里我們用歐氏距離來表示路徑代價)。 在重新找父節(jié)點的過程中，以9節(jié)點 xnew 為圓心，以事先規(guī)定好的半徑，找到在這個圓的范圍內(nèi) xnew 的近鄰，也就是4，5，8節(jié)點。 原來的路徑0 - 4 - 6 - 9代價為10 + 5 + 1 = 16，備選的三個節(jié)點與 xnew 組成的路徑0 - 1 - 5 - 9，0 - 4 - 9和0 - 1 - 5 - 8 - 9代價分別為3 + 5 + 3 = 11，10 + 4 = 14和3 + 5 + 1 + 3 = 12，因此如果5節(jié)點作為9節(jié)點的新父節(jié)點，則路徑代價相對是最小的，因此我們把9節(jié)點的父節(jié)點由原來的節(jié)點4變?yōu)楣?jié)點5，則重新生成的隨機樹如圖(b)所示。7.1.2 重布線隨機樹過程 在為xnew 重新選擇父節(jié)點之后，為進一步使得隨機樹節(jié)點間連接的代價盡量小，為隨機樹進行重新布線。過程示意如上圖重布線的過程也可以被表述成：如果近鄰節(jié)點的父節(jié)點改為 xnew 可以減小路徑代價，則進行更改。 如圖(c)，9節(jié)點為新生成的節(jié)點 xnew ，近鄰節(jié)點分別為節(jié)點4 , 6 , 8 。它們父節(jié)點分別為節(jié)點0 , 4 , 5。路徑分別為0 - 4，0 - 4 - 6，0 - 1 - 5 - 8，代價分別為10，10 + 5 = 15 和3 + 5 + 1 = 9。 如果將4節(jié)點的父節(jié)點改為9節(jié)點 xnew ，則到達節(jié)點4的路徑變?yōu)? - 1 - 5 - 9 - 4，代價為3 + 5 + 3 + 4 = 15 大于原來的路徑代價10，因此不改變4節(jié)點的父節(jié)點。 同理，改變了8節(jié)點的父節(jié)點，路徑代價將由原來的9變?yōu)?4，也不改變8節(jié)點的父節(jié)點。如果改變6節(jié)點的父節(jié)點為 xnew 則路徑變?yōu)? - 1 - 5 - 9 - 6，代價為3 + 5 + 3 + 1 = 12小于原來的路徑代價15，因此將6的父節(jié)點改為節(jié)點9，生成的新隨機樹如圖(d)。 重布線過程的意義在于每當生成了新的節(jié)點后，是否可以通過重新布線，使得某些節(jié)點的路徑代價減少。如果以整體的眼光看，并不是每一個重新布線的節(jié)點都會出現(xiàn)在最終生成的路徑中，但在生成隨機樹的過程中，每一次的重布線都盡可能的為最終路徑代價減小創(chuàng)造機會。 RRT*算法的核心在于上述的兩個過程：重新選擇父節(jié)點和重布線。這兩個過程相輔相成，重新選擇父節(jié)點使新生成的節(jié)點路徑代價盡可能小，重布線使得生成新節(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
公眾號
版權(quán)所有 ©北太振寰（重慶）科技有限公司 | 渝ICP備2022008375號-4 法律聲明 隱私政策
