《結(jié)合遺傳算法的RRT路徑規(guī)劃算法優(yōu)化研究11000字》

結(jié)合遺傳算法的RRT路徑規(guī)劃算法優(yōu)化研究內(nèi)容提要：本文研究了基于快速搜索隨機(jī)樹RRT算法的機(jī)器人路徑規(guī)劃，任務(wù)是在給定的歹徒上尋求一條從設(shè)定的起始點(diǎn)開始到設(shè)定的目標(biāo)點(diǎn)結(jié)束規(guī)劃出一條無碰撞路徑。完成了利用MATLAB程序構(gòu)建的平臺實現(xiàn)路徑規(guī)劃進(jìn)行路徑規(guī)劃算法進(jìn)行仿真實驗的測試。設(shè)計通過多個不同環(huán)境用來驗證算法的實用性，有效性和普遍性。通過在復(fù)雜地圖中通過改變RRT算法的步長，隨機(jī)采樣來對比實驗結(jié)果用來驗證對算法的影響。大量結(jié)果表明，通過改進(jìn)算法的步長，采樣概率能極大的影響算法中隨機(jī)樹向著目標(biāo)點(diǎn)前進(jìn)的路徑的長度，合理性和最終的探索時間。該算法可以很容易的處理有障礙物約束以及機(jī)器人本身約束的地圖當(dāng)中去，因而被廣泛的適用于到各種有著路徑規(guī)劃背景智能機(jī)器人中去，可以有效去處理，有存在大量形狀不規(guī)則障礙物和其障礙物分布位置不均勻的復(fù)雜環(huán)境中且有著髙自由度的機(jī)器人的運(yùn)動規(guī)劃問題。關(guān)鍵詞目錄28645內(nèi)容提要 I17934關(guān)鍵詞 I10209目錄 (張靜怡,趙天宇,2022)20148第一章緒論 1188921.1課題的研究背景及意義 1195851.2國內(nèi)外研究現(xiàn)狀 1246661.3本論文主要研究內(nèi)容及章節(jié)安排 210518第二章RRT算法功能和優(yōu)缺點(diǎn)的闡述 3310992.1.RRT算法的優(yōu)缺點(diǎn)具體闡述; 387492.1.1RRT算法的優(yōu)點(diǎn) 3198152.1.2RRT算法的缺點(diǎn) 3171452.2RRT算法功能闡述 417782.2.1度量函數(shù) 4280722.2.2隨機(jī)采樣 5326662.2.3最近鄰函數(shù) 576092.2.4碰撞檢測功能 65358第三章仿真實驗 846803.1地圖實驗 9108133.2參數(shù)調(diào)整實驗 1016560第四章RRT-connet仿真實驗 138411第五章結(jié)論 1429106參考文獻(xiàn) 16山西大學(xué) 山西大學(xué)自動化系本科畢業(yè)論文撰寫規(guī)范 1第一章緒論1.1課題的研究背景及意義機(jī)器人作為新時代的生成工具為人類服務(wù)，代替人類從事在有著危險惡劣的工作環(huán)境的繁重工作。它們被廣泛應(yīng)用在醫(yī)療，服務(wù)，軍事，工業(yè)等領(lǐng)域。對人類的探索新環(huán)境，提高生產(chǎn)力，提高生活水平具有重要的意義。智能路徑規(guī)劃能夠根據(jù)移動機(jī)器人的不同的要求規(guī)劃出所需要的路徑，其主要的任務(wù)是是確保計提供算法的計算機(jī)為機(jī)器人提供一條在給定環(huán)境中從給定起點(diǎn)到給定目的地的無碰撞路徑。同時在此基礎(chǔ)上能夠提高性能（即路徑最短，最短用時，降低能耗）等諸多條件(張逸凡,周紫晴,2022)。路徑規(guī)劃在尖端領(lǐng)域的應(yīng)用有：在無人機(jī)的飛行期間規(guī)避障礙物的路線設(shè)計；導(dǎo)彈躲避敵方雷達(dá)搜索以及攔截、防反彈襲擊,月球探索車的路徑規(guī)劃，從這些信息可以看出工業(yè)機(jī)械臂的路徑規(guī)劃，巡檢機(jī)器人的路徑規(guī)劃。在居民日常生活領(lǐng)域的應(yīng)用有：汽車，船舶等GPS的導(dǎo)航應(yīng)用，掃地機(jī)器人的路徑規(guī)劃（機(jī)器人自主尋找充電樁和規(guī)劃最短路徑）(潘奕凡,朱可欣,2023)。在物流運(yùn)輸領(lǐng)域的應(yīng)用有：快遞分類機(jī)器人的軌跡運(yùn)輸路線設(shè)計問題，卡車的的軌跡。路徑規(guī)劃不僅在今天的生活中大放異彩，從這些數(shù)據(jù)可以明顯看出它也將成為未來人類開拓新領(lǐng)域的重要研究課題。如今，機(jī)器人在制造業(yè)的發(fā)展中發(fā)揮著重要的作用，社會對它們的需求也越來越大。移動機(jī)器人需要自主、實時和快速地去避開地圖上存在的的障礙物，找到一條供給給機(jī)器人的可持續(xù)的路徑到達(dá)目的地。由于這個原因，路徑規(guī)劃問題是移動機(jī)器人基礎(chǔ)的課題(魏琪琳,邵宇翔,2021)。迄今為止，傳統(tǒng)移動機(jī)器人的軌跡徑規(guī)劃算法都需要對機(jī)器人移動的工作空間進(jìn)行數(shù)學(xué)建模和描述，在解決具有低自由度的簡單路徑規(guī)劃具有優(yōu)勢算法如人工勢場法，蟻群算法，深度學(xué)習(xí)，概率路線圖，可視圖，遺傳算法，等。但還是存在很多不足，尤其是解決非完整性的（局部規(guī)劃）、約朿（機(jī)器人的空間約束，路徑約束）規(guī)劃情況下，過多的考慮導(dǎo)致了算法的冗余(李高,張蕓,2023)。同時,限制了其只能在低維度空間使用的原因是這些傳統(tǒng)算法的計算的復(fù)雜性，而且在復(fù)雜維度空間自適應(yīng)差，適應(yīng)性低。以此為前提在諸多常見的規(guī)劃方法中具有代表性的方法有：Djikstra提出的算法Dijkstra法REF_Ref28101\r\h[13]、Hart提出的A*算法REF_Ref28101\r\hREF_Ref28692\r\h[14]、stentz提出的D*算法，Phi*算法，模糊邏輯算法、模擬退火法、可視圖法REF_Ref28888\r\h[16]等，這些算法往往在著手解決問題的過程中有著上述提道的問題，建模難、搜索地圖能力的不足且占用計算機(jī)的大量計算空間，不同的問題之間使用的算法不通用。1.2國內(nèi)外研究現(xiàn)狀由于RRT算法的優(yōu)勢;不需要對機(jī)器人移動的工作環(huán)境空間進(jìn)行數(shù)學(xué)建模和描述，強(qiáng)大且靈活的搜索能力，使得很快從眾多路徑規(guī)劃算法中脫穎而出引起諸多學(xué)者的關(guān)注在完善的路線規(guī)劃算法時，各種規(guī)劃算法都會遇到很多困難，尤其是其自身算法的上限帶來的局限性約束(王晨曦,周瑤瑤,2022)。大量的研究暴露了針對與RRT算法的不足：RRT算法本身不同于其他算法的優(yōu)勢，圍繞這種局面展開反而可能制約到了其發(fā)展。因此國內(nèi)外學(xué)者針對RRT算法進(jìn)行了不同的改進(jìn)，使其可以適應(yīng)于日益增長的路徑規(guī)劃應(yīng)用要求。Kuffner和LaValle提出了雙向搜索隨機(jī)數(shù)（Bi-RRT）,在目標(biāo)點(diǎn)不在作為單純的目的地存在，也有作為起始點(diǎn)的作用，在此情境之下向周圍探索生成路徑，加快算法的收斂，由此衍生出RRT-connect，相較于前者極大的極高了隨機(jī)樹生成速度(趙心怡,李宇昕,2020)。為適應(yīng)復(fù)雜環(huán)境（多不規(guī)則障礙，多狹窄通道），提出了一種RRT算法，該算法根據(jù)障礙物邊界優(yōu)先選擇狹窄空間。Cheng在RRT運(yùn)動規(guī)劃中提出改進(jìn)度量函數(shù)，在RRT搜索過程中給利用代價算多次探索來達(dá)到度量函數(shù)自主學(xué)習(xí)改進(jìn)路徑(劉瑞琳,陳云霞,2021)。Dubins路徑被引入以解決路徑的非光滑性問題，但這些路徑是不連續(xù)的，因為它們是直線和直線的結(jié)合，在這一狀況里生成不連續(xù)路徑，效果不理想。為了解決這些問題Fraichard和Scheuer建議了使用回旋曲線來處理。不同上述的方法DynamicRRT(DRRT)算法，為了去除不合適的節(jié)點(diǎn)和分支，在快速擴(kuò)展隨機(jī)樹生長環(huán)節(jié)中添加了一個修剪與合并多余的冗余節(jié)點(diǎn)和分支的算法流程，然后用DRRT算法去篩選由于環(huán)境變化而變得無效的節(jié)點(diǎn)和分支，在這種情況框架下同時保留剩余可用的分支形成了一個隨機(jī)樹路徑(周杰倫,楊星雨,2023)。魏琪琳,邵宇翔提出引導(dǎo)隨機(jī)樹標(biāo)記狹窄通道的進(jìn)行探索擴(kuò)展，提高隨機(jī)樹窄道尋路的能力。以上結(jié)果在一定程度上引證了本文先前構(gòu)建的理論模型。首先已有的研究結(jié)果分析與理論預(yù)測保持了較高的一致性，驗證了理論框架中中提出的機(jī)制的有效性。具體而言，通過研究發(fā)現(xiàn)關(guān)鍵變量之間的相關(guān)性及趨勢與模型預(yù)測相吻合，這不僅增強(qiáng)了理論框架的可信度，也為進(jìn)一步探索該領(lǐng)域內(nèi)的復(fù)雜關(guān)系提供了實證基礎(chǔ)。其次結(jié)果的符合性表明，理論模型中所考慮的影響因素和它們之間的相互作用是合理的，這對于理解研究現(xiàn)象的本質(zhì)具有重要意義。該算法不適合自動執(zhí)行的原因是:這種方式雖然解決了隨機(jī)樹選擇路徑問題，但每個人的尋路標(biāo)準(zhǔn)是不同的，使得這種人與計算機(jī)的交互也增加了人的工作量，1.3本論文主要研究內(nèi)容及章節(jié)安排本文共分五章，具體內(nèi)容如下：緒論，通過對機(jī)器人近幾年的發(fā)展，路徑規(guī)劃的應(yīng)用，其他算法的缺點(diǎn)闡述，國內(nèi)外學(xué)者對RRT算法的研究，介紹了其十幾年的發(fā)展。介紹了快速和擴(kuò)展的隨機(jī)樹路線規(guī)劃（RRT）算法的優(yōu)點(diǎn)和缺點(diǎn)，隨后詳細(xì)介紹了經(jīng)典RRT算法的特性，并總結(jié)了研究有移動目標(biāo)的機(jī)器人的路線規(guī)劃時遇到的問題。第三章，通過MATLAB平臺仿真實驗來驗證RRT算法的可行性。通過構(gòu)建多個地圖來驗證RRT算法的優(yōu)勢，介紹算法的的建模過程研究針對RRT算法的步長，概率等方面對探索樹生長的影響，通過在簡單區(qū)域和復(fù)雜區(qū)域的探索時間和碰撞次數(shù)來體現(xiàn)。第四章，介紹研究基于RRT算法的改進(jìn)算法RRT-connect算法的研究本章主要介紹有：1.敘述RRT-connect算法的原理。2利用MATLAB平臺實驗算法的成功，通過結(jié)果分析，驗證其相較于RRT算法的優(yōu)勢。第五章，總結(jié)實驗結(jié)果，同時總結(jié)研究中過程中的不足和缺陷，對未來工作做了合理的展望。

第二章RRT算法功能和優(yōu)缺點(diǎn)的闡述本章基于研究其余算法的前提下，對RRT算法對比其余算法的優(yōu)勢進(jìn)行闡述。然有優(yōu)點(diǎn)就有缺點(diǎn)，人無完人，算法由人提出肯定有缺點(diǎn)，基于提出的缺點(diǎn)，對RRT功能的分析。在第三章通過仿真實驗，確保路徑的生成。2.1.RRT算法的優(yōu)缺點(diǎn)具體闡述;2.1.1RRT算法的優(yōu)點(diǎn)RRT在概率完全算法中，如果路徑存在且時間?限時，那么路徑設(shè)計是確定的。該算法通過從周圍的空間中隨機(jī)取樣，引導(dǎo)擴(kuò)展隨機(jī)樹以指定的步長朝著的取樣的方向向著空間未被探索部分生長，在這種局面下考量直至整個空間被填滿或者到達(dá)指定的生長位置，從而確定路徑節(jié)點(diǎn)，生成路徑(張靜怡,趙天宇,2022)。這一結(jié)果與已有的文獻(xiàn)結(jié)論大致相同，這也驗證了前期研究中所提出的構(gòu)思，從而進(jìn)一步鞏固了本文對該現(xiàn)象本質(zhì)的認(rèn)識。這一發(fā)現(xiàn)不僅為學(xué)術(shù)討論提供了新的證據(jù)支持，還為實踐領(lǐng)域提供了可依賴的理論依據(jù)。它促使本文重新審視現(xiàn)有的理論模型，思考如何通過細(xì)微調(diào)整或創(chuàng)新來增強(qiáng)模型的解釋力和預(yù)測精度。它可以解決多自由度的高緯度空間環(huán)境下機(jī)器人的大段獨(dú)立性的復(fù)雜路徑規(guī)劃問題是因為該算法不需要預(yù)處理任何地圖，并可直接應(yīng)用于具有不完整約束的地圖當(dāng)中去。因應(yīng)這情況的發(fā)展在當(dāng)前的路徑規(guī)劃的算法研究當(dāng)中，多數(shù)算法無法做到在高維空間兼有算法簡單性，在低緯空間中做到算法的普適性，低緯空間和高維空間算法無法同時兼用(陳瑤瑤,王彥君,2020)。從這些信息可以看出由于算法的局限以及復(fù)雜性，工作空間必須提前處理并且處理的精度要高的情況下才能運(yùn)用，在適用空間中隨著空間維度和障礙物密度的提高，從這些數(shù)據(jù)可以明顯看出占用的計算量也逐步增大，生成的路徑的效率低并且無法在路徑規(guī)劃的過程中路徑中大量生成的折線等都無法使用在日常生活中，適應(yīng)范圍相對有限，對參數(shù)的調(diào)整有著較大的敏感性。為了解決上述提道的路徑問題，在其他采樣的經(jīng)典算法基礎(chǔ)上，RRT算法不需要對要求的環(huán)境進(jìn)行單獨(dú)的建模，以此為前提對環(huán)境的要求被降低，實現(xiàn)了低緯到高維空間的聯(lián)系，并且在輸入的環(huán)境中只需要利用隨機(jī)采樣的方式來培養(yǎng)隨機(jī)樹來探索空間中的每個角落，空間中生成的隨機(jī)點(diǎn)能夠確保生成的路徑能夠充分探索到整個地圖，確保了算法的全局的兼?zhèn)?，充分利用生成的隨機(jī)點(diǎn)，大幅度的降低了高緯度空間中的路徑規(guī)劃問題的難度(李雨軒,鄧曉璇,2021)。圍繞這種局面展開在現(xiàn)實生活中，人理解的維度在三維，但是為了算法的方便，做復(fù)雜機(jī)械臂的路徑規(guī)劃中，可能對三維空間做劃分，使得實際應(yīng)用出現(xiàn)更高維的空間規(guī)劃問題(趙心瑜,王凱文,2022)。在此情境之下由此可以看到RRT算法比較與其他算法的優(yōu)勢，在這一狀況里極大的減少了空間規(guī)劃的計算量，對機(jī)器人路徑規(guī)劃的實際運(yùn)用有了極大的提高。2.1.2RRT算法的缺點(diǎn)雖然其RRT算法的保證了算法在地圖內(nèi)規(guī)劃路徑問題求出一個解時，能夠找到合適的解去解決問題，但是它的隨機(jī)性也存在不穩(wěn)性,RRT算法的隨機(jī)采樣特性將致使多個不同的路徑的結(jié)果是產(chǎn)生在同一地圖下重復(fù)規(guī)劃的路徑往往還是是次優(yōu)路徑或不是最優(yōu)解；在這種局面下考量搜索樹沒有特定的目標(biāo)方向的去生長，緩慢的收斂速度；在后續(xù)的研究中會對已有的研究成果進(jìn)一步從不同的角度進(jìn)行優(yōu)化，會致力于開發(fā)新的技術(shù)方法和工具，以提升數(shù)據(jù)收集、處理和分析的效率與準(zhǔn)確性。通過引入前沿的科技手段，如人工智能、大數(shù)據(jù)處理等，本文期望能夠更深入地挖掘數(shù)據(jù)中的隱藏信息，為研究提供更為堅實的實證基礎(chǔ)。動態(tài)環(huán)境下無法作為解決方案去考慮，只在環(huán)境中沒有干擾時使用(周依娜,劉天宇,2023)。這是因為算法使得隨機(jī)搜索樹先探索整個空間的，因應(yīng)這情況的發(fā)展再去除多余節(jié)點(diǎn)出留下路徑，如果路徑無法生成，排除地圖設(shè)置的缺陷，則RRT算法將無法找到一條路徑解。只保留一顆生長不完全的隨機(jī)樹，體現(xiàn)了傳統(tǒng)算法不穩(wěn)定和緩慢收斂甚至得不到路徑解的問題。在簡單環(huán)境中和復(fù)雜的環(huán)境中，它都沒有最優(yōu)解，比如在設(shè)置了通道多個狹長的地圖內(nèi)部，隨機(jī)擴(kuò)展樹很難快速通過狹窄通道，從這些信息可以看出隨機(jī)樹生長的方式總是差強(qiáng)人意，大量的節(jié)點(diǎn)堆積在了狹窄通道當(dāng)中，使得隨機(jī)樹看起來是在窄道內(nèi)擁擠直至“擠”出窄道去繼續(xù)生長，生成的路徑其中包含很多不需要的路徑．降低算法的效率，從這些數(shù)據(jù)可以明顯看出路徑內(nèi)包含很多不需要的折點(diǎn)生成的路徑是曲折甚至混亂的(楊思琪,陳澤宇,2020)。導(dǎo)致增加了路徑的長度，僅適用于提高一個解決方案滿足路徑設(shè)計模板。RRT算法的隨機(jī)搜索占用了大量計算機(jī)內(nèi)的算法資源。因為“隨機(jī)”導(dǎo)致RRT很盲目，所以路徑只會毫無目標(biāo)的向四周擴(kuò)散，直到找到目標(biāo)為止，但實際上，移動機(jī)器人是對周圍環(huán)境有一個大致了解的(趙曉菲,張軒瑞,2021)。研究過程中希望移動機(jī)器人能朝著目標(biāo)能多一點(diǎn)的探索，以此為前提不必把過多的資源浪費(fèi)在探索周圍環(huán)境中去。在隨機(jī)采樣過程中，由于RRT算法檢測到的碰撞檢測較多，算法的效率降低。文章基于RRT快速擴(kuò)張隨機(jī)樹算法。算法通過使調(diào)整支點(diǎn)的偏向目標(biāo)點(diǎn)搜索的策略生長策略和步長的有效地去探索路徑，避免路徑陷入窄通道內(nèi)；，使生長樹規(guī)劃出的路徑更有多的是用來達(dá)目的地的而不是探索周圍空間(李建華,王梓馨,2023)。2.2RRT算法功能闡述RRT算法的結(jié)構(gòu)包括五個主要功能：一，度量，二，隨機(jī)采樣，三，最近鄰函數(shù)，四，碰撞檢測功能2.2.1度量函數(shù)度量函數(shù)如圖1.1也叫距離函數(shù)，多用于空間距離的測量在隨機(jī)樹的生長過程中正確的選取度量函數(shù)不僅影響生長的枝干而且對生成的路徑的長度有著重要的判斷，由于測試空間的復(fù)雜度，在此情境之下障礙物的隨機(jī)性，機(jī)器人本身帶有的運(yùn)動限制，最后得出的路徑是不規(guī)則，想要出現(xiàn)一條簡單路徑是不可能的(黃佳怡,劉志軒,2022)。RRT的建立基于三維歐式空間，在這種情況框架下也即歐幾里得距離作為度量函數(shù)。也就是常用到的兩點(diǎn)的線段的長度，用來計算最后生成的路徑長度，尋找最接近隨機(jī)采樣的Xrand節(jié)點(diǎn)的樹節(jié)點(diǎn)(趙佳怡,孫俊杰,2020)圖2.1如果(p)為1、2或∞，則度量函數(shù)分別命名為曼哈頓、歐?里得2.2.2隨機(jī)采樣在沒有障礙物的情況下，隨機(jī)采樣點(diǎn)通常是在地圖內(nèi)部均勻分布的，樹在各個方向生長會大致相等地生長。當(dāng)然如果能夠預(yù)先給出了最有可能發(fā)現(xiàn)目標(biāo)點(diǎn)的區(qū)域信息在地圖的數(shù)學(xué)描述和建模中，在這種局面下考量那么算法就會控制生長樹的自然生長方向?qū)Ｗ⒂谔剿髟搮^(qū)域。為了解決均勻生長帶來的問題，引導(dǎo)隨機(jī)樹向著目標(biāo)位置生長，加快求解的速度。在隨機(jī)樹的生長過程加入偏向概率p1，根據(jù)概率p1的值來決定隨機(jī)樹的的生長方向是向著周圍環(huán)境擴(kuò)展還是向著目標(biāo)前進(jìn)，加速路徑得出解的速度(周詩,李高峰,2021)。每次隨機(jī)樹的生長，因應(yīng)這情況的發(fā)展都會產(chǎn)生一個（0，1）的隨機(jī)值p，當(dāng)0<p<p1時，意味著隨機(jī)樹向目標(biāo)方向前進(jìn)；當(dāng)p1<p<1時隨機(jī)樹向任意方向生長。從上可以可以看出該方案相比于其他方案具有更好的性價比，同時在操作簡便性和用戶體驗方面也有顯著提升。這不僅有助于縮短項目周期，還能降低培訓(xùn)成本和用戶適應(yīng)新系統(tǒng)的時間，從而更快地實現(xiàn)投資回報。這樣的生長策略可以很好的去糾正隨機(jī)樹的生長路徑，在很大程度上的起到了防止了隨機(jī)樹的“隨機(jī)性”如圖所示，可以看到這顆“隨機(jī)樹”沒有很好的生長，沒有如預(yù)期一樣去探索周圍空間，這樣的算法是不能承擔(dān)起空間探索的作用，因此，增加一個隨機(jī)概率p1可以有效地促進(jìn)對周圍空間或目標(biāo)的探索(鄧月婷,陳俊杰,2023)。圖2.3圖最近鄰函數(shù)通過降低距離，采用簡單的邏輯，做到降低路徑長度，路徑簡單處理，節(jié)省實際應(yīng)用中移動機(jī)器人的移動時間(王子安,黃怡然,2020)。首先以新節(jié)點(diǎn)為圓心，給定半徑畫一個圓。圈中的節(jié)點(diǎn)都是可能的節(jié)點(diǎn)，然后依次計算起始圈中節(jié)點(diǎn)的成本與圈中節(jié)點(diǎn)到新節(jié)點(diǎn)的成本之和，選其中最小的代價為新節(jié)點(diǎn)Xnew的代價，從這些信息可以看出相應(yīng)的節(jié)點(diǎn)為Xnew的父節(jié)點(diǎn)。如下圖2.3所示節(jié)點(diǎn)d為原始樹中距離采樣點(diǎn)最近的節(jié)點(diǎn)，節(jié)點(diǎn)c根據(jù)采樣點(diǎn)和最近節(jié)點(diǎn)生成的新節(jié)點(diǎn)Xnew，在圈中共有a、b、d、e四個節(jié)點(diǎn)，挨個將其當(dāng)作c的父節(jié)點(diǎn)然后計算c的代價，發(fā)現(xiàn)成本最小，那么就將c的父節(jié)點(diǎn)賦值為a?？梢钥?2到新的父節(jié)點(diǎn)的路徑代價比前者小了很多(李明陽,張藝琳,2021)。這步工作完成之后還有重新布線的過程，以c為父節(jié)點(diǎn)即尋找新的子節(jié)點(diǎn)，從這些數(shù)據(jù)可以明顯看出如圖-1假如以b作為新的子節(jié)點(diǎn)路徑（b-c-a-f-g）代價為3+3+5+3=14，其b節(jié)點(diǎn)原來路徑（b-a-f-g）代價為1+5+3=9，所以b不作為新的子節(jié)點(diǎn)與c相連。而代價以e為子節(jié)點(diǎn)路徑（e-c-a-f-g）代價為1+3+5+3=10，其原來路徑（e-d-g）代價5+10=15，故e作為新的子節(jié)點(diǎn)與c相連接(周佳琦,王子杰,2022)。上述是理想過程，如果節(jié)點(diǎn)之間有障礙物，最近鄰算法勁量適用于寬闊的環(huán)境中去節(jié)點(diǎn)與節(jié)點(diǎn)之間相連的情況就需要多加考慮。2.2.4碰撞檢測功能碰撞檢測從地圖維度可分為平面碰撞檢測和物體體積的碰撞檢測，并可根據(jù)時間變化進(jìn)一步分為靜態(tài)和動態(tài)?？臻g中物體的可以通過投影轉(zhuǎn)化為平面圖形進(jìn)行碰撞檢測，以減少計算量。以此為前提靜態(tài)檢測對實時性要求不高，但對精度的要求相當(dāng)高。本文只做平面靜態(tài)碰撞檢測研究，不考慮機(jī)器人的自由度。本文路徑規(guī)劃中障礙物取為圓性，矩形(張俊杰,楊瑞婷,2020)。該設(shè)計成果是在詳盡分析現(xiàn)有情況并充分利用現(xiàn)有的資源與技術(shù)后達(dá)成的。相較于傳統(tǒng)方法，此方法在多方面顯示出明顯優(yōu)越性。首先，通過采用更具創(chuàng)意的設(shè)計思路，它實現(xiàn)了更高的工作效率和更低的失誤率，大大提高了項目的可行性。其次，在成本效益上，新方法減少了執(zhí)行與維護(hù)費(fèi)用，避免了資源浪費(fèi)，增強(qiáng)了經(jīng)濟(jì)收益。同時，也提升了系統(tǒng)的兼容性和擴(kuò)展能力，以適應(yīng)未來發(fā)展的需要。（1）圓形障礙物的避障問題通常地圖內(nèi)的圓形是多個矩形組成的多邊形，因為地圖是基于01矩陣生成的。本實驗以矩陣中的1作為障礙，以此為前提不予生成子節(jié)點(diǎn)，0作為空曠環(huán)境生成隨機(jī)樹。只需要判斷生成的Xnew子節(jié)點(diǎn)橫縱坐標(biāo)是否在生成圓所覆蓋的坐標(biāo)內(nèi)。Xnew的橫縱坐標(biāo)與記錄的圓形障礙物坐標(biāo)重合的部分，則認(rèn)為這是一次碰撞(趙睿琳,周藝文,2023)。該算法的原理如下：圓形障礙物的檢測，在此情境之下首先生成一個圓心（X,Y）半徑為R的圓形障礙物，實際應(yīng)用對到機(jī)器人的尺寸有要求則有必要對擴(kuò)展障礙物判斷邊界。當(dāng)然在實際應(yīng)用中要詳細(xì)分析機(jī)器人的形狀，當(dāng)確定發(fā)生碰撞時，當(dāng)前機(jī)器人當(dāng)前狀態(tài)超出了當(dāng)前運(yùn)動范圍，可以調(diào)整機(jī)器人的姿態(tài)完成避障任務(wù)(李澤民,劉雪娜,2021)。設(shè)置機(jī)器人的尺寸為inf,只需判斷新生成的Xnew坐標(biāo)（x1,y1）是否在圓內(nèi)即可,其碰撞條件為如圖所示：X-R-inf<x1<X+R+infY-R-inf<y1<Y+R+inf圖2.5圖2.6若生成的子節(jié)點(diǎn)Xnew不在圓形障礙物中，則需要判斷Xnew與Xnear生成的路徑是否與障礙物有碰撞，在這一狀況里問題可看做檢測直線與圓是否有交點(diǎn)，那么可以直接計算圓心到直線中點(diǎn)的距離，然后判斷該距離是否大于圓半徑即可若0<GO<R出現(xiàn)，說明點(diǎn)位于AB中間，即如圖情況，則視為碰撞，不予生成路徑，若出現(xiàn)R<GO則說明線段與障礙物無碰撞，給予生成路徑（2）矩形的碰撞檢測本文所研究搭建的地圖中多采用長方形障礙物，碰撞檢測算法原理如下：碰撞檢測問題可視為為直線與矩形相交問題(劉海濤,張琪琳,2022)。矩形障礙物的不與以Xnear與Xnew為端點(diǎn)的線段相交，否則視為碰撞。判斷直線與矩形相交的分為兩步：第一步,矩形的一側(cè)是否有Xnew與Xnear存在。如果沒有，則無需后續(xù)判斷,Xnear與Xnew連線不與矩形相交。在這種局面下考量這里不出現(xiàn)兩點(diǎn)坐標(biāo)都位于矩形內(nèi)部的情況，因為Xnew由Xnear產(chǎn)生,而Xnear必處在矩形外面空間位置。第二步,有Xnear與Xnew分別與生成矩形任意一邊的不同側(cè)，分為兩種情況:,第一種情況如果生成的支點(diǎn)Xnew坐標(biāo)位于矩形內(nèi)部,視為一次碰撞。第二種情況，矩形內(nèi)部無任何點(diǎn)生成但兩連線與矩形相交(黃婷玉,李明杰,2023)。如圖2.7兩點(diǎn)位于矩形ABCD一側(cè)且與AD和CD相交。因應(yīng)這情況的發(fā)展該問題可以由直線與矩形的性質(zhì)得出；如圖2.7，Xnear與Xnew位于兩點(diǎn)連線與矩形障礙物AB與AD邊相交，D（Xd,Yd)與A(Xa,Ya)是構(gòu)成矩形的邊界，即當(dāng)Xnear（X1,Y1）與Xnew(X2,Y)連線的斜率位于Xnear與D（Xd,Yd)連線之下和Xnear與A(Xa,Ya)所在直線之上，視作一次碰撞。若不在則不視為一次碰撞。在優(yōu)化設(shè)計的過程中，特別關(guān)注了成本效益和方案的廣泛適用性，因此與初始版本相比，在多個維度上進(jìn)行了改良。首先，通過去除冗余步驟、選用更經(jīng)濟(jì)有效的策略，顯著降低了執(zhí)行費(fèi)用，使方案更為實惠。此外，為了提升其普及潛力，設(shè)計方案時充分考量了各地不同環(huán)境的需求，確保該方案在各種情況下都能平穩(wěn)運(yùn)作，并且方便他人借鑒實施。碰撞的過程由圖2.7表示，圖2.7圖2.8（3）線段的碰撞檢測最后的碰撞判斷，路徑與路徑之間是否有交叉，問題簡化為：線段是否與線段相交，方法可以通過向量叉積的方法進(jìn)行判斷(楊家瑤,王雪,2020)。如圖2.8，線段AB與線段CD相交，那么它們必然滿足條件：從這些信息可以看出矩形的頂點(diǎn)C和D位于線段AB的兩端。為了證明頂點(diǎn)C、D位于線段AB的兩側(cè)，那么可以連接AC、AD，計算向量AB與向量AC、AD的叉積，只要兩者的叉積結(jié)果異號，那么說明它們位于線段AB兩端。若m×n>0,則說明兩者同號，從這些數(shù)據(jù)可以明顯看出頂點(diǎn)C,D位于AB的同側(cè)，線段之間不相交；反之m×n≤0，兩線段相交，或者AB與CD可能位于同一直線上，則需要考慮四個點(diǎn)的順序關(guān)系(鄧子赫,陳怡彤,2021)。第三章仿真實驗本文利用MATLAB搭建了一個仿真實驗環(huán)境平臺，其RRT算法偽代碼如圖3.1圖3.1上述偽代碼所講述的其RRT代碼的基本步驟是：

1.隨機(jī)生成一個點(diǎn)Xinit2.在地圖隨機(jī)采樣生成的點(diǎn)和生成點(diǎn)的方向上取一定步長，得到新的枝點(diǎn)3.判斷有無碰撞檢測生成，沒有通過則添加新的支點(diǎn)到隨機(jī)樹內(nèi)4.重復(fù)上述1,2,3,步直到找到目標(biāo)點(diǎn)5.從目標(biāo)點(diǎn)反推回來便能得到路徑，無需搜索(趙雨琪,劉健宇,2022)。初始節(jié)點(diǎn)設(shè)置為Xinit,此時樹中有以一個樹節(jié)點(diǎn)，在地圖中隨機(jī)采樣得出一個點(diǎn)Xrand，以此為前提然后通過節(jié)點(diǎn)與節(jié)點(diǎn)之間的代價，即上述提道的度量函數(shù)，選取到樹上的合適的節(jié)點(diǎn)定義為Xnear，連接Xrand和Xnear,在Xrand和Xnear直線方向上以Xnear為起點(diǎn)取設(shè)定的步長為長度，在步長另一端生成Xnew，以此生成樹中的一個新的子節(jié)點(diǎn)，通過碰撞函數(shù)決定，是否有障礙物碰撞，決定是否生成路徑，生成后Xnew將加入隨機(jī)樹當(dāng)中去，在允許的最大嘗試次數(shù)內(nèi)，不斷循環(huán)，在此情境之下直至生成的節(jié)點(diǎn)在最大可容忍范圍內(nèi)停止隨機(jī)樹的生長，最后連接Xinit到Xgoal生成路徑，路徑規(guī)劃完成(張璇子,王雪寧,2023)。3.1地圖實驗設(shè)置初始位置為（1,1）目標(biāo)位置為（490,490）。步長設(shè)置為20，地圖內(nèi)最大嘗試次數(shù)為100，50%的幾率向目標(biāo)前進(jìn)(周瑞文,李一凡,2020)。圖3.2時間為1.267秒，路徑長度為846圖3.3時間為2.186秒，路徑長度為1353此時的最大嘗試次數(shù)已經(jīng)無法滿足路徑規(guī)劃的基本要求了，本圖是多次實驗下的少有的幾次成功例子。多數(shù)如圖圖3.4，時間為1.704秒，路徑長度為864，3.2參數(shù)調(diào)整實驗基于MATLAB實驗平臺，設(shè)置起始點(diǎn)位置為（490,490），目標(biāo)點(diǎn)位置（1,1）對RRT步長，隨機(jī)采樣幾率進(jìn)行調(diào)整(馮凡,陳思琪,2021)。

對RRT步長進(jìn)行調(diào)整，在這一狀況里設(shè)置步長分別為10，20，40，80，100。最大嘗試次數(shù)設(shè)置為10000確保路徑能夠生成，數(shù)據(jù)見表3.1，可以看到隨著步長的增加，路徑的生成時間逐步降低，但是由于步長的增加，反而使得路徑出現(xiàn)“不同程度的曲折”導(dǎo)致路徑變的更長。此文采用了先前的設(shè)計理念來構(gòu)建計算框架，并進(jìn)行了適當(dāng)?shù)暮喕?，旨在增?qiáng)其實用價值和操作簡便性。通過詳細(xì)分析與評估現(xiàn)有方法，識別并去除了冗余復(fù)雜的步驟，優(yōu)化了流程，從而形成了一種簡潔高效的計算模型。這樣做不僅減少了資源消耗，還縮短了處理周期，同時維持了原有性能，便于執(zhí)行和普及，加入了多樣的驗證和質(zhì)量控制機(jī)制。在這種局面下考量實驗采用的地圖較為復(fù)雜，在窄道路口步長的設(shè)置決定，探索樹是否能夠成功通過窄路(黃欣怡,李俊杰,2022)。實驗所用到的地圖為490*490的地圖，如果步長設(shè)置的長度（例如200）相對地圖邊界還大，那么隨機(jī)樹會出現(xiàn)生長終止的情況對RRT步長進(jìn)行調(diào)整，設(shè)置步長分別為0.2，0.4，0.6，0.8。最大嘗試次數(shù)設(shè)置為10000確保路徑能夠生成，數(shù)據(jù)見表3.2表3.1表3.2第四章RRT-connet仿真實驗本文實驗也做了雙樹隨機(jī)樹仿真實驗，算法的主要思路是，隨機(jī)樹不在是由起始點(diǎn)單一的向目標(biāo)點(diǎn)進(jìn)行探索，因應(yīng)這情況的發(fā)展目標(biāo)點(diǎn)也將生長出隨機(jī)樹，兩顆隨機(jī)樹一起探索整個空間，加快探索速率。部分實驗結(jié)果如圖圖4.1同時如下圖，可以看到，由于算法的瑕疵導(dǎo)致了，兩顆隨機(jī)樹并沒有在合適的地方做連接路徑的處理，路徑不太理想(趙瑞彤,周雪怡,2023)。圖4.2第五章結(jié)論通過改變RRT算法的步長，采樣概率，可以有效的提高RRT算法中隨機(jī)樹的生長效率，同時在實驗過程中要給與隨機(jī)樹足夠的嘗試次數(shù)，否則會出現(xiàn)隨機(jī)樹無法生長到目標(biāo)位置，從這些信息可以看出無法得到路徑，同時地圖中目標(biāo)點(diǎn)和起始點(diǎn)由于是矩陣位置與傳統(tǒng)XY坐標(biāo)系不同，要注意區(qū)分未來方向以往的運(yùn)動規(guī)劃算法；對于算法的的改進(jìn)思路為在地圖中間做引導(dǎo)點(diǎn)Xsign，引導(dǎo)隨機(jī)樹的連接?；蛘咛幚硪呀?jīng)生成的路徑，將從Xinit到Xgoal生成的節(jié)點(diǎn)Xrandn做新的排列處理，從這些數(shù)據(jù)可以明顯看出具體內(nèi)容如：Xinit對生成的Xrandn計算路徑代價，如果Xrandn+1可以與Xinit直接相連，則去除Xrandn，反之保留Xrandn作為新的Xinit與剩下的Xrandn相連，直至到達(dá)Xgoal范圍當(dāng)中去。對于RRT-connect從起始位置到目標(biāo)位置生長出的節(jié)點(diǎn)也不需要兩顆隨機(jī)樹共同生成一個路徑，可以考慮由兩顆隨機(jī)樹生成的兩條路徑進(jìn)行比較選取出合理的路徑，還可以在此基礎(chǔ)上對兩條路徑折中處理得出第三條路徑參考文獻(xiàn)張逸凡,周紫晴等人.改進(jìn)RRT算法的機(jī)器人路徑規(guī)劃[J/OL].重慶大學(xué)學(xué)報:1-13[2022-04-16]..2022.1410.005.html潘奕凡,朱可欣.改進(jìn)RRT算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].信息與電腦(理論版),2023,33(18):37-41.魏琪琳,邵宇翔.基于改進(jìn)RRT算法的移動機(jī)器人路徑規(guī)劃[J].智能計算機(jī)與應(yīng)用,2021,11(07):32-35+42李高,張蕓.基于改進(jìn)雙向RRT算法的機(jī)器人路徑規(guī)劃[J].山東科學(xué),2021,34(03):109-118.王晨曦,周瑤瑤.基于改進(jìn)RRT算法的機(jī)器人路徑規(guī)劃研究[D].西安建筑科技大學(xué),2021.DOI:10.27393/ki.gxazu.2021.000129.趙心怡,李宇昕.基于RRT改進(jìn)的機(jī)器人路徑規(guī)劃算法研究[D].廣西大學(xué),2020.DOI:10.27034/ki.ggxiu.2020.001061.劉瑞琳,陳云霞.基于改進(jìn)RRT算法的移動機(jī)器人路徑規(guī)劃研究[D].聊城大學(xué),2020.DOI:10.27214/ki.glcsu.2020.000591.周杰倫,楊星雨.改進(jìn)RRT算法的室內(nèi)移動機(jī)器人路徑規(guī)劃[J].計算機(jī)工程與應(yīng)用,2020,56(09):190-197.張靜怡,趙天宇.基于改進(jìn)RRT算法的移動機(jī)器人路徑規(guī)劃研究[D].西安工程大學(xué),2019.DOI:10.27390/ki.gxbfc.2019.000183.TaheriEhsan,FerdowsiMohammadHossein,DaneshMohammad.FuzzyGreedyRRTPathPlanningAlgorithminaComplexConfigurationSpace[J].InternationalJournalofControl,Automationand周詩,李高峰tems,2018,16(6).陳瑤瑤,王彥君.基于RRT優(yōu)化算法的移動機(jī)器人路徑規(guī)劃[J].兵