改進(jìn)RRT算法的機(jī)器人路徑規(guī)劃

譚波 羅均 羅雨松 胡春暉 卓俊康 白澤鑫 田金濤

doi：?10.11835/j.issn.1000-582X.2022.107

收稿日期：2021-10-14

網(wǎng)絡(luò)出版日期：2022-03-02

作者簡(jiǎn)介：譚波（1999—），男，碩士研究生，主要從事機(jī)器人路徑規(guī)劃研究，（E-mail）tanbo@cqu.edu.cn。

通信作者：羅均，男，教授，博士生導(dǎo)師，機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室主任，主要從事以控制為基礎(chǔ)的機(jī)器人運(yùn)動(dòng)載體對(duì)環(huán)境力載荷的抗干擾技術(shù)研究，（E-mail）luojun@shu.edu.cn。

摘要：機(jī)器人已被廣泛應(yīng)用于日常生活之中。路徑規(guī)劃作為機(jī)器人的主要技術(shù)之一，優(yōu)秀的路徑規(guī)劃算法能提升機(jī)器人的工作效率、降低其使用成本，并為研究機(jī)器人的導(dǎo)航打下良好的基礎(chǔ)。RRT（rapidly-exploring random trees）算法具有擴(kuò)展性強(qiáng)的優(yōu)點(diǎn)，但存在路徑長(zhǎng)度并非最優(yōu)、光滑性差等不足，為此提出反向?qū)?yōu)和三次樣條曲線插值以改進(jìn)算法，并在MATLAB和ROS（robot operating system）系統(tǒng)中仿真。結(jié)果表明：改進(jìn)后的RRT算法能降低路徑長(zhǎng)度，減少節(jié)點(diǎn)數(shù)目，提高光滑性，實(shí)現(xiàn)了算法的有效性。

關(guān)鍵詞：RRT算法；路徑規(guī)劃；反向?qū)?yōu)；三次樣條曲線插值；ROS系統(tǒng)

中圖分類號(hào)：TP242 ?????????文獻(xiàn)標(biāo)志碼：A ?????文章編號(hào)：1000-582X（2023）09-013-10

Robot path planning based on improved RRT algorithm

TAN Bo， LUO Jun， LUO Yusong， HU Chunhui， ZHUO Junkang， BAI Zexin， TIAN Jintao

（State Key Laboratory of Mechanical Transmissions， Chongqing University， Chongqing 400044， P. R. China）

Abstract： Robots have been widely used in daily life. Path planning is one of the main technologies of robots. An outstanding path planning algorithm can improve the work efficiency of robots， reduce cost， and lay a good foundation for the research of robot navigation. The RRT （rapidly-exploring random trees） algorithm， which is well known for its strong scalability， has some shortcomings， such as suboptimal path length and poor smoothness. An improved algorithm of reverse optimization and cubic spline interpolation is proposed， and then simulated in different scenarios in MATLAB. Taking the restaurant environment as an example in ROS （robot operating system）， the experimental results show that the improved RRT algorithm can decrease the path length and the number of nodes， and improve the smoothness， verifying the effectiveness of the algorithm.

Keywords： RRT algorithm; path planning; reverse optimization; cubic spline interpolation curve; robot operating system

進(jìn)入21世紀(jì)后，隨著前沿科學(xué)技術(shù)的發(fā)展，機(jī)器人技術(shù)被不少國(guó)家列為重點(diǎn)發(fā)展的一項(xiàng)高新技術(shù)，且相關(guān)產(chǎn)業(yè)被用作衡量綜合國(guó)力強(qiáng)弱的標(biāo)志^[1]。現(xiàn)實(shí)生活中廣泛為人們服務(wù)的機(jī)器人，其相關(guān)的路徑規(guī)劃問(wèn)題面臨著前所未有的機(jī)遇，同時(shí)也充滿著挑戰(zhàn)，使其成為機(jī)器人的核心技術(shù)之一^[2-3]。路徑規(guī)劃算法的好壞，直接決定事先設(shè)定的任務(wù)能否圓滿完成并達(dá)到理想的效果。優(yōu)秀的路徑規(guī)劃技術(shù)不僅能減少資金投入，降低運(yùn)行時(shí)間，而且還能提高機(jī)器人的搜索效率，為機(jī)器人導(dǎo)航的研究奠定良好的基礎(chǔ)^[4-6]。

快速擴(kuò)展隨機(jī)樹(shù)（rapidly-exploring random trees，RRT）算法作為一種基于采樣的路徑規(guī)劃算法，地圖不需要做預(yù)處理，且可以迅速搜索。但是，RRT也有不足之處，譬如，搜索時(shí)較為盲目，在復(fù)雜或者動(dòng)態(tài)環(huán)境里往往會(huì)出現(xiàn)計(jì)算極其復(fù)雜、所需的時(shí)間過(guò)長(zhǎng)、易于陷入死區(qū)等情況。針對(duì)以上問(wèn)題，康亮等^[7]將滾動(dòng)窗口應(yīng)用于RRT算法，保留了漸進(jìn)最優(yōu)的特點(diǎn)，并且減少了運(yùn)行時(shí)間，增強(qiáng)了算法對(duì)未知區(qū)域的探索能力；賈李紅等^[8]提出一種融合算法，即將人工勢(shì)場(chǎng)法與RRT算法配合使用，該算法有效地解決了RRT算法局部避障的難題，而且使規(guī)劃效率大幅度提升；孫欽鵬等^[9]提出了一種適應(yīng)變步長(zhǎng)的調(diào)整方法，對(duì)新目標(biāo)點(diǎn)設(shè)計(jì)出一種新的選擇方式來(lái)改進(jìn)RRT算法，通過(guò)仿真實(shí)驗(yàn)證明，改進(jìn)的RRT算法在復(fù)雜和狹窄環(huán)境中的平均路徑長(zhǎng)度更短。

以上對(duì)RRT算法的改進(jìn)，使搜索能力進(jìn)一步增強(qiáng)，搜索具有目標(biāo)性，路徑長(zhǎng)度縮短或節(jié)點(diǎn)數(shù)目減少，但路徑光滑性依舊很差，路徑長(zhǎng)度還是很長(zhǎng)且不是最優(yōu)，算法有待進(jìn)一步改進(jìn)。因此，筆者提出反向?qū)?yōu)和三次樣條曲線插值改進(jìn)算法，在MATLAB中仿真驗(yàn)證并進(jìn)行實(shí)例分析，并在ROS系統(tǒng)中以餐廳為例做進(jìn)一步仿真分析，驗(yàn)證了改進(jìn)算法的有效性。

1RRT算法簡(jiǎn)介

1.1RRT算法基本原理

LaValle^[10]在1998年首次提出的RRT算法是一種高效的路徑規(guī)劃算法。RRT算法以初始的一個(gè)根節(jié)點(diǎn)，通過(guò)隨機(jī)采樣的方法在空間搜索，然后添加一個(gè)又一個(gè)的葉節(jié)點(diǎn)來(lái)不斷擴(kuò)展隨機(jī)樹(shù)。當(dāng)目標(biāo)點(diǎn)進(jìn)入隨機(jī)樹(shù)里面后，隨機(jī)樹(shù)擴(kuò)展立即停止，此時(shí)能找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的路徑。擴(kuò)展樹(shù)的具體結(jié)構(gòu)如圖1所示。

1.2RRT算法缺點(diǎn)

1）穩(wěn)定性差。由于擴(kuò)展樹(shù)節(jié)點(diǎn)的生長(zhǎng)方向是隨機(jī)的，所以在相同的任務(wù)下重復(fù)規(guī)劃，也會(huì)出現(xiàn)不同的路徑，導(dǎo)致每次規(guī)劃的結(jié)果都不同，甚至偏離最優(yōu)路徑。

2）隨機(jī)性強(qiáng)。因?yàn)閿U(kuò)展樹(shù)是在整個(gè)區(qū)域內(nèi)隨機(jī)搜索，不受目標(biāo)點(diǎn)的引導(dǎo)和啟發(fā)，因此，存在大量無(wú)效的擴(kuò)展節(jié)點(diǎn)，使算法具有很強(qiáng)的隨機(jī)性。

3）光滑性差。RRT算法生成的路徑是很多折線段相連，并不是一條光滑的曲線。

4）不適合動(dòng)態(tài)環(huán)境。RRT算法規(guī)劃出一條可行路徑后，當(dāng)環(huán)境中出現(xiàn)動(dòng)態(tài)障礙物時(shí)，RRT算法不能有效地檢測(cè)，因此，不適合動(dòng)態(tài)環(huán)境下的路徑規(guī)劃問(wèn)題^[11-12]。

1.3RRT算法改進(jìn)思路

針對(duì)RRT算法存在的缺點(diǎn)，總結(jié)各類改進(jìn)方法，得到如下幾點(diǎn)常見(jiàn)的改進(jìn)思路。

1）偏向性方面：為了提高收斂速度和搜索效率，擴(kuò)展樹(shù)生長(zhǎng)方向是目標(biāo)點(diǎn)還是隨機(jī)點(diǎn)是依靠隨機(jī)概率來(lái)確定的，與原始的RRT算法相比，改進(jìn)后的算法能夠加速收斂。

2）節(jié)點(diǎn)選取方面：通過(guò)改進(jìn)父節(jié)點(diǎn)選取的方式來(lái)改進(jìn)RRT算法，改進(jìn)后的算法能夠提高收斂速度，減少節(jié)點(diǎn)數(shù)目，改善路徑質(zhì)量。

3）光滑性方面：通過(guò)數(shù)學(xué)中的曲率約束，使生成規(guī)劃路徑光滑無(wú)節(jié)點(diǎn)，使路徑更具有可行性^[13-14]。

在上述改進(jìn)思路的啟發(fā)下，在節(jié)點(diǎn)選取方面本研究中提出了反向?qū)?yōu)改進(jìn)RRT算法，在光滑性方面用三次樣條曲線插值優(yōu)化。

2RRT算法改進(jìn)

2.1反向?qū)?yōu)

機(jī)器人的路徑若不是最優(yōu)，就會(huì)增加工作時(shí)間，降低運(yùn)作效率。為了改善RRT算法的路徑長(zhǎng)度，通過(guò)反向?qū)?yōu)的方法來(lái)改進(jìn)RRT算法，如圖2所示。反向?qū)?yōu)方法充分應(yīng)用兩點(diǎn)之間線段最短這一數(shù)學(xué)思想，達(dá)到縮短路徑長(zhǎng)度的目的。圖中A點(diǎn)為起點(diǎn)，B點(diǎn)為終點(diǎn)，原始的RRT算法擴(kuò)展產(chǎn)生的節(jié)點(diǎn)為X_i（i=1，2，…，6），障礙物用黑色矩形表示，原始的RRT算法初步生成的路徑為A與B之間的細(xì)實(shí)線，圖中A與B之間的粗實(shí)線為改進(jìn)后生成的路徑。

改進(jìn)后的算法偽代碼如表2所示，具體優(yōu)化過(guò)程如下。首先直接連接起點(diǎn)A和終點(diǎn)B，再判斷A與B連線是否被障礙物覆蓋，若沒(méi)有被障礙物覆蓋，則此次搜索最優(yōu)路徑就是A與B兩點(diǎn)間的連線；若被障礙物覆蓋，則按照節(jié)點(diǎn)順序找到B的父節(jié)點(diǎn)X₆，判斷A與X₆連線之間是否被障礙物覆蓋，若A與X₆之間沒(méi)有被障礙物覆蓋，則直接把X₆當(dāng)作A的子節(jié)點(diǎn)，依次連接A-X₆-B，此路徑作為搜索的最優(yōu)路徑；若A與X₆連線被障礙物覆蓋，則繼續(xù)尋找X₆的父節(jié)點(diǎn)，即圖中的X₅，判斷起點(diǎn)A與X₅連線是否被障礙物覆蓋；按照上述方法一直進(jìn)行下去，優(yōu)化后得到圖中X₂作為A的子節(jié)點(diǎn)，然后再把子節(jié)點(diǎn)X₂當(dāng)作下一步算法改進(jìn)的起點(diǎn)，不斷地重復(fù)以上步驟，當(dāng)整個(gè)路徑優(yōu)化完成時(shí)，得到如圖2所示的最優(yōu)路徑，即算法結(jié)束。

2.2三次樣條曲線插值

RRT算法規(guī)劃出的路徑往往不光滑，機(jī)器人在節(jié)點(diǎn)處需要先減速，然后再加速前行，增加了機(jī)器人的能量消耗和工作時(shí)間。為了讓路徑更加光滑，使機(jī)器人平穩(wěn)移動(dòng)，用三次樣條曲線插值優(yōu)化反向?qū)?yōu)改進(jìn)算法。三次樣條曲線是一種常用的插值平滑算法，通過(guò)一系列的控制點(diǎn)得到一條連續(xù)平滑的曲線。

2.2.1 數(shù)學(xué)基本原理

三次樣條曲線插值是將原始長(zhǎng)序列分成若干段，每一段都是一個(gè)三次函數(shù)，在分段處左右兩邊函數(shù)值相等，一階導(dǎo)數(shù)和二階導(dǎo)數(shù)都連續(xù)^[15]。

假設(shè)有n+1個(gè)節(jié)點(diǎn)，把n+1個(gè)節(jié)點(diǎn)劃分成以下n個(gè)區(qū)間：

每個(gè)分段區(qū)間的三次多項(xiàng)式構(gòu)造形式如下：

所以，S（x）表達(dá)式是一個(gè)分段函數(shù)：

分段函數(shù)滿足以下4個(gè)條件。

條件1：函數(shù)穿過(guò)所有已知節(jié)點(diǎn)，可得n+1個(gè)方程。

條件2：節(jié)點(diǎn)處0階連續(xù)，即前一段方程在節(jié)點(diǎn)處的函數(shù)值和后一段方程在相同節(jié)點(diǎn)處的函數(shù)值都相等，可得n-1個(gè)方程。

條件3：在所有節(jié)點(diǎn)（除了第1個(gè)節(jié)點(diǎn)和最后的節(jié)點(diǎn)）處1階連續(xù)，保證節(jié)點(diǎn)處有相同的斜率，原函數(shù)曲線上沒(méi)有劇烈的跳變，可得n-1個(gè)方程。

條件4：在所有節(jié)點(diǎn)（除了第1個(gè)節(jié)點(diǎn)和最后的節(jié)點(diǎn)）處2階連續(xù)，保證節(jié)點(diǎn)處有相同的曲率，意味著每個(gè)點(diǎn)的曲率半徑有定義，共n-1個(gè)方程。

2.2.2 端點(diǎn)條件

1）自由邊界

首尾兩端沒(méi)有任何讓曲線彎曲的力，則要求解線性方程組：

2）固定邊界

在端點(diǎn)有固定的斜率，則要求解線性方程組：

3）非節(jié)點(diǎn)邊界

指定樣條曲線的三次微分相等，則要求解線性方程組：

3基于MATLAB仿真分析

將原始的RRT算法、反向?qū)?yōu)改進(jìn)的RRT算法、三次樣條曲線插值（自由邊界）優(yōu)化后的RRT算法在MATLAB（R2018a）中仿真分析。實(shí)驗(yàn)地圖為二維場(chǎng)景圖，仿真分為無(wú)障礙物、單個(gè)障礙物、復(fù)雜環(huán)境、狹窄通道4個(gè)不同的場(chǎng)景，這樣可以使仿真結(jié)果更具有可比性，更能驗(yàn)證算法的有效性。起點(diǎn)坐標(biāo)（0，0），終點(diǎn)坐標(biāo)（750，750），搜索步長(zhǎng)80。在下面的路徑規(guī)劃圖中，白色區(qū)域表示算法可覆蓋的區(qū)域。

3.1無(wú)障礙物情況

在無(wú)障礙情況下，3種算法對(duì)應(yīng)的結(jié)果如圖3所示。沒(méi)有障礙物時(shí)，在安全區(qū)域中，隨機(jī)擴(kuò)展樹(shù)需要擴(kuò)展大量的節(jié)點(diǎn)數(shù)，迅速規(guī)劃出了一條可行的路徑，但路徑長(zhǎng)度不是最優(yōu)，算法的收斂速度較緩慢，節(jié)點(diǎn)較多；反向?qū)?yōu)改進(jìn)的RRT算法大大減少了隨機(jī)擴(kuò)展樹(shù)節(jié)點(diǎn)的數(shù)量，找到了一條最短路徑，即起點(diǎn)與終點(diǎn)間的連線段，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的RRT算法路徑質(zhì)量顯著提高；在反向?qū)?yōu)的基礎(chǔ)上，三次樣條曲線插值優(yōu)化的RRT算法路徑長(zhǎng)度變化不大，但光滑性變好。

3.2單個(gè)障礙物情況

在單個(gè)障礙情況下，3種算法對(duì)應(yīng)的結(jié)果如圖4所示。由圖可知，當(dāng)環(huán)境地圖中存在障礙物時(shí)，原始RRT算法能很快規(guī)劃出一條路徑，但是路徑節(jié)點(diǎn)較多，光滑性很差，路徑長(zhǎng)度不是最優(yōu)；反向?qū)?yōu)改進(jìn)的RRT算法大大減少了節(jié)點(diǎn)數(shù)量，路徑長(zhǎng)度縮短，路徑質(zhì)量顯著提高；在反向?qū)?yōu)的基礎(chǔ)上，三次樣條曲線插值優(yōu)化后的RRT算法路徑長(zhǎng)度相差不大，但是節(jié)點(diǎn)數(shù)目進(jìn)一步減少，光滑性變好。

3.3復(fù)雜環(huán)境情況

在復(fù)雜環(huán)境情況下，即存在很多障礙物，3種算法對(duì)應(yīng)的結(jié)果如圖5所示。由圖可知，當(dāng)障礙物很多時(shí)，原始RRT算法搜索時(shí)間較長(zhǎng)，規(guī)劃出的路徑節(jié)點(diǎn)很多，光滑性很差，路徑長(zhǎng)度不是最優(yōu)；反向?qū)?yōu)改進(jìn)的RRT算法搜索時(shí)間沒(méi)有太大變化，但是路徑節(jié)點(diǎn)數(shù)量明顯減少，路徑長(zhǎng)度縮短，顯著提高了路徑的質(zhì)量；在反向?qū)?yōu)的基礎(chǔ)上，三次樣條曲線插值優(yōu)化后的RRT算法路徑長(zhǎng)度相差不大，但是節(jié)點(diǎn)數(shù)目進(jìn)一步減少，光滑性變好。

3.4狹窄通道情況

在狹窄通道情況下，即可搜索區(qū)域和障礙物之間構(gòu)成很多的狹窄通道，3種算法對(duì)應(yīng)結(jié)果的如圖6所示。3種算法規(guī)劃出的路徑中，由于通道狹窄，擴(kuò)展樹(shù)會(huì)在障礙物和可搜索區(qū)域之間來(lái)回不停地碰撞，導(dǎo)致搜索時(shí)間較長(zhǎng)。RRT算法擴(kuò)展節(jié)點(diǎn)太多，光滑性非常差，路徑并非最優(yōu)；而反向?qū)?yōu)改進(jìn)后的RRT算法由于改變了父節(jié)點(diǎn)的選取，規(guī)劃出的路徑長(zhǎng)度降低，節(jié)點(diǎn)數(shù)目減少，光滑性相對(duì)變好；在反向?qū)?yōu)的基礎(chǔ)上，三次樣條曲線插值優(yōu)化的RRT算法節(jié)點(diǎn)數(shù)目進(jìn)一步減少，光滑性變好，且路徑長(zhǎng)度相差甚小。

為了便于進(jìn)一步和原始RRT算法的相關(guān)數(shù)據(jù)進(jìn)行比較，驗(yàn)證反向?qū)?yōu)改進(jìn)和三次樣條曲線插值優(yōu)化后的算法的有效性和準(zhǔn)確性，在仿真條件下對(duì)以上4個(gè)不同的場(chǎng)景進(jìn)行了200次路徑規(guī)劃，計(jì)算對(duì)應(yīng)算法的平均路徑長(zhǎng)度和平均節(jié)點(diǎn)數(shù)目，結(jié)果如表3和4所示。

計(jì)算結(jié)果顯示原始RRT算法路徑長(zhǎng)度較大，且節(jié)點(diǎn)數(shù)多；反向?qū)?yōu)改進(jìn)后的算法路徑長(zhǎng)度明顯減小，節(jié)點(diǎn)數(shù)急劇減少，說(shuō)明光滑性變好，算法改進(jìn)效果顯著；三次樣條曲線插值在反向?qū)?yōu)的基礎(chǔ)上進(jìn)行優(yōu)化后，雖然路徑長(zhǎng)度略微增加，但是節(jié)點(diǎn)數(shù)歸零，光滑性非常好。

結(jié)合以上改進(jìn)算法驗(yàn)證結(jié)果分析，可得以下結(jié)論：移動(dòng)機(jī)器人在路徑規(guī)劃中如果更偏重于路徑長(zhǎng)度的要求，可以選擇反向?qū)?yōu)改進(jìn)后的算法；如果更偏重于光滑性的要求，使移動(dòng)機(jī)器人行走更加平穩(wěn)，可以選擇三次樣條曲線插值優(yōu)化后的算法。

4基于ROS系統(tǒng)的仿真驗(yàn)證

為進(jìn)一步驗(yàn)證改進(jìn)算法的有效性，以餐廳環(huán)境為例在ROS平臺(tái)進(jìn)行仿真，使用gmapping實(shí)現(xiàn)機(jī)器人的SLAM建圖，如圖7所示。

啟動(dòng)相應(yīng)的launch文件，啟動(dòng)gazebo并加載機(jī)器人URDF模型的餐廳環(huán)境，啟動(dòng)rviz并加載了gmapping建立的地圖^[17-18]，如圖8和9所示。

根據(jù)現(xiàn)實(shí)餐廳障礙物情況，分為空餐廳情況、障礙物較少、障礙物很多3個(gè)不同的場(chǎng)景進(jìn)行仿真，設(shè)置相同的起點(diǎn)和終點(diǎn)，并對(duì)它們的路徑長(zhǎng)度和運(yùn)行時(shí)間進(jìn)行對(duì)比分析。

4.1空餐廳環(huán)境

餐廳內(nèi)部全空時(shí)，機(jī)器人規(guī)劃出的從當(dāng)前位置到目標(biāo)位置的有效路徑如圖10所示。從圖中可以看出，機(jī)器人在運(yùn)動(dòng)過(guò)程中的路徑長(zhǎng)度較短且光滑。

4.2障礙物較少

在障礙物較少的情況下，機(jī)器人迅速規(guī)劃出一條路徑，如圖11所示。與空餐廳場(chǎng)景相比，路徑仍然保持光滑，路徑長(zhǎng)度幾乎不變，這是由于障礙很少，對(duì)路徑長(zhǎng)度沒(méi)有影響。

4.3障礙物很多

在障礙物很多的情況下，機(jī)器人規(guī)劃出的路徑如圖12所示。此路徑并非最優(yōu)，相對(duì)于障礙物較少的情況路徑長(zhǎng)度明顯增加，其原因在于障礙物太多，機(jī)器人需要不停地避開(kāi)障礙物，因此路徑長(zhǎng)度增加。

為了更好地對(duì)比以上3種場(chǎng)景，統(tǒng)計(jì)路徑長(zhǎng)度和運(yùn)行時(shí)間，如表5所示。

分析以上圖可知，障礙物較少的情況相對(duì)于空餐廳情況，路徑長(zhǎng)度和運(yùn)行時(shí)間略微增加，總體變化不大；在障礙物很多的情況下，路徑長(zhǎng)度和運(yùn)行時(shí)間明顯增加，原因在于機(jī)器人為躲避較多的障礙物，規(guī)劃的路徑并非最優(yōu)，導(dǎo)致路徑長(zhǎng)度和運(yùn)行時(shí)間明顯增加。

5結(jié)??論

1）針對(duì)RRT算法存在的缺點(diǎn)提出了反向?qū)?yōu)和三次樣條曲線插值改進(jìn)方法。

2）將改進(jìn)的RRT算法在MATLAB中不同的場(chǎng)景下進(jìn)行多次仿真，結(jié)果表明，改進(jìn)后的算法可以縮短路徑長(zhǎng)度，減少節(jié)點(diǎn)數(shù)目，提高光滑性，驗(yàn)證了改進(jìn)算法的有效性。

3）以餐廳環(huán)境為例在ROS系統(tǒng)中進(jìn)一步仿真，結(jié)果表明，機(jī)器人能實(shí)現(xiàn)路徑規(guī)劃功能，驗(yàn)證了改進(jìn)算法的有效性，后續(xù)重點(diǎn)研究工作將搭建實(shí)物機(jī)器人驗(yàn)證，未來(lái)有望應(yīng)用到送餐機(jī)器人中，提高工作效率，降低人工成本，產(chǎn)生經(jīng)濟(jì)效益。

參考文獻(xiàn)

［1］??金碚. 中國(guó)制造2025[M]. 北京： 中信出版集團(tuán)， 2015.

Jin B. Made in China 2025[M]. Beijing： Citic Publishing Group， 2015. （in Chinese）

［2］??王淘淘. 中國(guó)機(jī)器人產(chǎn)業(yè)發(fā)展報(bào)告： 我國(guó)機(jī)器人市場(chǎng)進(jìn)入高速增長(zhǎng)期[J]. 今日制造與升級(jí)， 2018（8）： 22.

Wang T T. China robot industry development report： Chinas robot market has entered a period of rapid growth[J]. Manufacture & Upgrading Today， 2018（8）： 22. （in Chinese）

［3］??中國(guó)電子學(xué)會(huì). 機(jī)器人簡(jiǎn)史[M]. 北京： 電子工業(yè)出版社， 2015.

Chinese Society of Electronics. A brief history of robot Brief history of robot[M]. Beijing： Publishing House of Electronics Industry， 2015. （in Chinese）

［4］??Yang L， Qi J T， Xiao J Z， et al. A literature review of UAV 3D path planning[C]//Proceeding of the 11th World Congress on Intelligent Control and Automation， June 29 - July 4， 2014， Shenyang. IEEE， 2014： 2376-2381.

［5］??Karasev V， Ayvaci A， Heisele B， et al. Intent-aware long-term prediction of pedestrian motion[C]//2016 IEEE International Conference on Robotics and Automation （ICRA）， May 16-21， 2016， Stockholm， Sweden. IEEE， 2016： 2543-2549.

［6］??Bakdi A， Hentout A， Boutami H， et al. Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy-logic control[J]. Robotics and Autonomous Systems， 2017， 89： 95-109.

［7］??康亮， 趙春霞， 郭劍輝. 未知環(huán)境下改進(jìn)的基于RRT算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 模式識(shí)別與人工智能， 2009， 22（3）： 337-343.

Kang L， Zhao C X， Guo J H. Improved path planning based on rapidly-exploring random tree for mobile robot in unknown environment[J]. Pattern Recognition and Artificial Intelligence， 2009， 22（3）： 337-343. （in Chinese）

［8］??賈李紅. 基于GPS的雙向搜索路徑的研究[D]. 安徽淮南： 安徽理工大學(xué)， 2017.

Jia L H. Research on two-way search path based on GPS[D]. Huainan， Anhui： Anhui University of Science & Technology， 2017. （in Chinese）

［9］??孫欽鵬， 李猛， 王中華. 基于改進(jìn)快速擴(kuò)展隨機(jī)樹(shù)算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2019， 33（5）： 431-438.

Sun Q P， Li M， Wang Z H. Mobile robot path planning based on improved rapidly-exploring random tree algorithm[J]. Journal of University of Jinan （Science and Technology）， 2019， 33（5）： 431-438. （in Chinese）

［10］??Lavalle S M. Rapidly-exploring random trees： a new tool for path planning[R]. Ames， Iowa： Iowa State University， 1998.

［11］??Chen W B， Wu X B， Lu Y. An improved path planning method based on artificial potential field for a mobile robot[J]. Cybernetics and Information Technologies， 2015， 15（2）： 181-191.

［12］??Zhang C. Path planning for robot based on chaotic artificial potential field method[J]. IOP Conference Series： Materials Science and Engineering， 2018， 317： 012056.

［13］??潘思宇， 徐向榮. 基于改進(jìn)RRT^*的移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃算法[J]. 山西大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 40（2）： 244-254.

Pan S Y， Xu X R. Mobile robot motion planning algorithm based on improved RRT^*[J]. Journal of Shanxi University：（Natural Science Edition）， 2017， 40（2）： 244-254. （in Chinese）

［14］??李金良， 舒翰儒， 劉德建， 等. 基于改進(jìn)RRT路徑規(guī)劃算法[J]. 組合機(jī)床與自動(dòng)化加工技術(shù)， 2021（2）： 22-24，29.

Li J L， Shu H R， Liu D J， et al. Path planning algorithm based on improved RRT[J]. Modular Machine Tool & Automatic Manufacturing Technique， 2021（2）： 22-24，29. （in Chinese）

［15］??Saranrittichai P， Niparnan N， Sudsang A. Robust local obstacle avoidance for mobile robot based on dynamic window approach[C]//2013 10th International Conference on Electrical Engineering/Electronics， Computer， Telecommunications and Information Technology， May 15-17， 2013， Krabi， Thailand. IEEE， 2013： 1-4.

［16］??Choi B， Kim B， Kim E， et al. A modified dynamic window approach in crowded indoor environment for intelligent transport robot[C]//2012 12th International Conference on Control， Automation and Systems， October 17-21， 2012， Jeju， South Korea. IEEE， 2012： 1007-1009.

［17］??于清曉. 輪式餐廳服務(wù)機(jī)器人移動(dòng)定位技術(shù)研究[D].上海：上海交通大學(xué)， 2013.

Yu Q X. Research on mobile localization techniques for wheeled restaurant service robots[D]. Shanghai： Shanghai Jiaotong University， 2013. （in Chinese）

［18］??胡春旭. ROS機(jī)器人開(kāi)發(fā)實(shí)踐[M]. 北京： 機(jī)械工業(yè)出版社， 2018.

Hu C X. ROS robot development practice[M]. Beijing： China Machine Press， 2018. （in Chinese）

（編輯??羅敏）