• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    面向移動(dòng)機(jī)器人快速全局路徑規(guī)劃的改進(jìn)跳點(diǎn)搜索算法

    2020-11-24 07:44:58宋曉茹任怡悅
    科學(xué)技術(shù)與工程 2020年29期
    關(guān)鍵詞:轉(zhuǎn)折點(diǎn)搜索算法對角線

    宋曉茹, 任怡悅

    (1.西安工業(yè)大學(xué)電子信息工程學(xué)院, 西安 710021; 2.西安工業(yè)大學(xué)自主智能創(chuàng)新團(tuán)隊(duì), 西安 710021)

    路徑規(guī)劃是移動(dòng)機(jī)器人實(shí)現(xiàn)自主化和智能化的關(guān)鍵技術(shù),路徑規(guī)劃算法的性能直接影響移動(dòng)機(jī)器人的工作效率,成為一個(gè)重要的研究領(lǐng)域[1-2]。柵格法因其便于機(jī)器人控制器存儲(chǔ)、處理、更新和使用[3],常用于完成環(huán)境的構(gòu)建和表示,基于此衍生出的全局路徑規(guī)劃算法有Dijkstra算法、A*算法、Swamps算法、SUB算法、跳點(diǎn)搜索算法等。

    Dijkstra算法[4]是典型的最短路徑算法,Chen等[5]基于Dijkstra算法建立了用于車輛疏散的動(dòng)態(tài)道路網(wǎng)絡(luò)模型,為公共場所的最優(yōu)緊急疏散路徑選擇和應(yīng)急救援決策提供了良好的方案;然而Dijkstra算法需要遍歷大量節(jié)點(diǎn),導(dǎo)致效率低下。針對此問題,Ren等[6]采用鄰接列表和循環(huán)鏈表,進(jìn)行權(quán)重排序得到改進(jìn)的Dijkstra算法,用于解決最短路徑的交通網(wǎng)絡(luò)問題。A*算法[7]是一種求解最短路徑最有效的直接搜索算法,針對其存在內(nèi)存開銷大,計(jì)算時(shí)間長等缺點(diǎn),Korf[8]提出IDA*,融合了迭代加深算法于A*算法中,不需要進(jìn)行狀態(tài)判重和估價(jià)排序,減少空間需求;Botea等[9]提出HPA*,通過提高啟發(fā)函數(shù)的準(zhǔn)確度,減小搜索空間,提高效率,但空間復(fù)雜度高。Pochter等[10]提出Swamps算法,采用離線預(yù)計(jì)算的方式將網(wǎng)格地圖分解為一系列相鄰的區(qū)域,識別并忽略與最優(yōu)解無關(guān)的無效區(qū)域,減少搜索時(shí)間與搜素節(jié)點(diǎn)。Uras等[11]提出SUB算法,通過預(yù)先將網(wǎng)格地圖轉(zhuǎn)換為可視化圖(稱為子目標(biāo)圖)來工作,然后算法存儲(chǔ)和搜索的是子目標(biāo)圖,而不是原始的網(wǎng)格來尋找最優(yōu)路徑。

    在柵格環(huán)境中,影響算法效率的最重要因素是存在大量對稱性路徑,將路徑視為無序的向量而不是有序的節(jié)點(diǎn)序列時(shí),可以看到地圖中有許多路徑共享相同的起點(diǎn)和終點(diǎn),且能通過交換其中一條路徑組成向量之間的順序,得到另一條路徑。這些大量對稱性路徑的存在導(dǎo)致算法需要去評估許多等效狀態(tài),阻止了向目標(biāo)點(diǎn)的真正進(jìn)展。然而上述研究均不是通過識別并消除對稱性而得到最優(yōu)路徑。

    Harabor[12]提出跳點(diǎn)搜索算法(jump point search,JPS),通過圖裁剪來減少搜索過程的對稱性,并在擴(kuò)展節(jié)點(diǎn)的過程中篩選特定的節(jié)點(diǎn)——“跳點(diǎn)”,不僅提升了性能而且降低了內(nèi)存成本。Jia等[13]在迷宮搜索方面對比了各算法的路徑規(guī)劃能力,比較了跳點(diǎn)搜索算法、A*算法與HPA*算法的搜索時(shí)間和效率,實(shí)驗(yàn)結(jié)果證明跳點(diǎn)搜索算法明顯優(yōu)于其他算法;趙曉等[14]結(jié)合跳點(diǎn)搜索算法改進(jìn)A*算法,篩選出關(guān)鍵點(diǎn)進(jìn)行擴(kuò)展,加速全局路徑規(guī)劃的效率。但以上都只是簡單的應(yīng)用跳點(diǎn)搜索算法,并未對其進(jìn)行改進(jìn)。

    跳點(diǎn)搜索法中識別關(guān)鍵跳點(diǎn)涉及了大量的迭代過程,成為了算法一個(gè)新的瓶頸,因此Harabor等[15]提出了JPS+算法,將柵格地圖信息預(yù)處理為查詢表,通過查找表格信息直接獲得路徑中的下一個(gè)跳轉(zhuǎn)點(diǎn),消除了跳點(diǎn)搜索算法引起的最大的處理開銷。Traish等[16]提出了BL-JPS算法,通過預(yù)處理網(wǎng)格內(nèi)障礙物邊界和地圖邊緣位置來加速跳躍點(diǎn)的識別。但以上對跳點(diǎn)搜索算法的兩種改進(jìn)方式都是離線操作,通過預(yù)處理地圖信息,大幅度提高搜索速度,當(dāng)?shù)貓D發(fā)生連續(xù)改變時(shí),重新評估最佳路徑過程中的任何開銷都會(huì)成為實(shí)時(shí)路徑規(guī)劃的性能問題。

    針對以上問題,采用“塊”操作方法,在一次搜索中快速掃描底層網(wǎng)格中的一個(gè)區(qū)域,將跳點(diǎn)搜索算法中的修剪規(guī)則一次應(yīng)用于多個(gè)節(jié)點(diǎn),以達(dá)到快速識別跳點(diǎn)的目的,并對僅僅只具有改變方向性質(zhì)的跳點(diǎn)進(jìn)行剔除。此策略完全為在線方式,不需要任何特殊的數(shù)據(jù)結(jié)構(gòu),也不存儲(chǔ)或計(jì)算任何其他信息,并同時(shí)保留了與原始算法相同的固有優(yōu)勢:完整性與最優(yōu)性。為了驗(yàn)證算法的有效性與可行性,分別在規(guī)則的網(wǎng)格地圖、測試庫基準(zhǔn)地圖及移動(dòng)機(jī)器人Turtlebot2進(jìn)行對比實(shí)驗(yàn)。

    1 跳點(diǎn)搜索算法(JPS)

    跳點(diǎn)搜索算法的主要思想是對稱修簡規(guī)則和跳點(diǎn)識別規(guī)則,搜索過程會(huì)遞歸的調(diào)用這兩種規(guī)則。優(yōu)勢在于考慮了與擴(kuò)展節(jié)點(diǎn)相關(guān)的父節(jié)點(diǎn)位置,即每條規(guī)則都會(huì)根據(jù)上一步的方向(直行或沿對角線)來決定這一步應(yīng)該朝什么方向前進(jìn),并為正在評估的節(jié)點(diǎn)標(biāo)識一組“自然”鄰居和“強(qiáng)制性”鄰居?!白匀弧编従佑蓴U(kuò)張方向定義:基本方向上(水平方向、豎直方向)的自然鄰居定義為同一方向的下一個(gè)節(jié)點(diǎn);對角線方向的自然鄰居集包括3個(gè)節(jié)點(diǎn):沿著對角線的下一個(gè)節(jié)點(diǎn),以及下一個(gè)垂直和水平節(jié)點(diǎn)。規(guī)則的例外是擴(kuò)展與障礙物相鄰的節(jié)點(diǎn),在這種情況下必須考慮無法直接從父節(jié)點(diǎn)訪問的路徑,識別強(qiáng)制性鄰居。

    1.1 修剪規(guī)則

    識別出不需要被評估的節(jié)點(diǎn),以便快速到達(dá)目標(biāo),具體通過比較兩條路徑的長度來完成。一條路徑起始于p(x),經(jīng)過節(jié)點(diǎn)x進(jìn)行直線或?qū)蔷€運(yùn)動(dòng);另一條同樣起始于p(x)進(jìn)行直線或?qū)蔷€運(yùn)動(dòng),但是不經(jīng)過節(jié)點(diǎn)x,如圖1所示。其中經(jīng)過節(jié)點(diǎn)x的路徑明顯更短且減少了對周圍鄰節(jié)點(diǎn)的重復(fù)訪問,因此為了篩選跳點(diǎn),需要?jiǎng)h掉這些不必要的節(jié)點(diǎn),即圖中的灰色柵格。不論兩條路徑中任意一條所涉及的節(jié)點(diǎn)必須屬于x的鄰居集內(nèi)。若鄰居集內(nèi)不包含障礙物,應(yīng)用直線或?qū)蔷€修剪之后的節(jié)點(diǎn)稱為x的自然鄰居,如圖1中的白色柵格;當(dāng)鄰居集內(nèi)包含障礙物時(shí),這時(shí)評估的節(jié)點(diǎn)稱為強(qiáng)制性節(jié)點(diǎn),如圖1中的斜杠柵格。

    圖1 修剪規(guī)則示意圖Fig.1 Diagram of pruning rule

    1.2 跳點(diǎn)識別規(guī)則

    識別并選擇性擴(kuò)展某些特定的點(diǎn),這些被選中的節(jié)點(diǎn)稱之為跳點(diǎn),用于加速尋找最優(yōu)路徑。兩個(gè)跳點(diǎn)所連接路徑上的中間節(jié)點(diǎn)不被擴(kuò)展,直接從一個(gè)跳點(diǎn)移動(dòng)到下一個(gè)跳點(diǎn)。跳點(diǎn)識別規(guī)則可歸納為y=x+kd,從x點(diǎn)出發(fā),通過在d方向移動(dòng)k步到達(dá)y,其中擁有最小k的節(jié)點(diǎn)y稱為x的跳點(diǎn)。

    (1)節(jié)點(diǎn)y目標(biāo)點(diǎn)。

    (2)節(jié)點(diǎn)y含有至少一個(gè)強(qiáng)制性節(jié)點(diǎn)。

    (3)若d為對角線移動(dòng),存在z=y+kidi,其中kiN,z是y的跳點(diǎn),則y也是x的跳點(diǎn)。

    跳點(diǎn)識別規(guī)則示意圖如圖2所示。

    圖2 跳點(diǎn)識別規(guī)則示意圖Fig.2 Diagram of jump point identification

    2 改進(jìn)的跳點(diǎn)搜索算法

    如何快速有效地發(fā)現(xiàn)跳點(diǎn)已成為跳點(diǎn)搜索算法的瓶頸問題。表1給出了在3種模擬真實(shí)環(huán)境的測試庫基準(zhǔn)地圖上運(yùn)行大量示例所獲得的數(shù)據(jù),可觀察到跳點(diǎn)搜索算法需要花費(fèi)約90%的時(shí)間用于生成后繼者,A*算法花費(fèi)約40%的時(shí)間,而在對Openlist和Closedlist列表中節(jié)點(diǎn)的操作約占10%,因此跳點(diǎn)搜索算法的效率取決于能否快速生成后繼節(jié)點(diǎn)。

    表1 3種模擬真實(shí)環(huán)境的基準(zhǔn)地圖上所占搜索時(shí)間比例的對比Table 1 Comparison of the proportion of search time on three benchmark maps that simulate real environments %

    提出在一次搜索中快速掃描一個(gè)區(qū)域而不是單獨(dú)的節(jié)點(diǎn),將修剪規(guī)則一次應(yīng)用于多個(gè)節(jié)點(diǎn),節(jié)省大量且毫無意義的節(jié)點(diǎn)操作,以達(dá)到快速識別跳點(diǎn)的目的,并在采取對角優(yōu)先的方式的前提下,剔除僅具有改變方向的中間轉(zhuǎn)折點(diǎn)。當(dāng)遞歸的應(yīng)用這些規(guī)則時(shí),可達(dá)到快速識別跳轉(zhuǎn)點(diǎn)的目的,有效提升最優(yōu)路徑搜尋的效率,顯著提高尋路搜索的整體性能。

    2.1 基于“塊”操作

    跳點(diǎn)搜索法產(chǎn)生跳點(diǎn)的原因有3個(gè):在當(dāng)前行檢測到死胡同、在相鄰行找到強(qiáng)制鄰居和檢測到目標(biāo)節(jié)點(diǎn)。首先針對死胡同的檢測,將網(wǎng)格編碼為位矩陣,其中一個(gè)位表示一個(gè)位置,記錄障礙物信息,指示關(guān)聯(lián)節(jié)點(diǎn)是否可遍歷。當(dāng)沿著固定的行或列遞歸搜索時(shí),一次性讀取固定設(shè)置好的32位輸入,這32位的節(jié)點(diǎn)信息賦予算法“遠(yuǎn)眺”功能,快速檢測出當(dāng)前行是否為死胡同,并立即給出是否應(yīng)當(dāng)放棄對當(dāng)前行的進(jìn)一步操作的指令。

    在算法第一次遇到死胡同之前,可能存在“直線-對角線”的轉(zhuǎn)折點(diǎn),即在鄰行中出現(xiàn)強(qiáng)制性鄰節(jié)點(diǎn),這時(shí)需要綜合當(dāng)前行、當(dāng)前行的上一行及下一行3行信息。若在上一行或下一行檢測出前一位置存在障礙物而在當(dāng)前位置沒有障礙物,則在當(dāng)前位置上存在潛在的強(qiáng)制鄰居,如圖3(a)所示。但算法也可能出現(xiàn)一直前跳的情況,以設(shè)置好的固定長度丈量地圖,可實(shí)現(xiàn)對地圖的快速遍歷。

    為了避免算法跳過目標(biāo)節(jié)點(diǎn),將目標(biāo)位置、當(dāng)前跳點(diǎn)與下一個(gè)跳點(diǎn)的連接,若此路徑與目標(biāo)位置所在的行或者列存在交集,則在交集位置添加一個(gè)中間節(jié)點(diǎn)。如圖3(b)所示,當(dāng)從N跳到S時(shí),可看出路徑穿過目標(biāo)點(diǎn)所在的列,為避免跳過目標(biāo)點(diǎn)T,在點(diǎn)T的列上插入一個(gè)中間后繼點(diǎn)J。

    圖3 基于“塊”操作示例Fig.3 Example of “block” operation based

    2.2 剔除中間轉(zhuǎn)折點(diǎn)

    路徑中的轉(zhuǎn)折點(diǎn)代表著路徑方向發(fā)生了改變,即當(dāng)nk-1到nk的行進(jìn)方向與nk到nk+1的行進(jìn)方向不同時(shí),節(jié)點(diǎn)nk為轉(zhuǎn)折點(diǎn)。最優(yōu)路徑π中轉(zhuǎn)折點(diǎn)會(huì)有以下3種情況:對角線-對角線、直線-對角線、對角線-直線,如圖4所示。

    圖4 最優(yōu)路徑的3種轉(zhuǎn)折點(diǎn)Fig.4 Three turning points of the optimal path

    對于這3種情況需要進(jìn)一步區(qū)分至少有一個(gè)強(qiáng)制性鄰居的轉(zhuǎn)折點(diǎn)和沒有強(qiáng)制性鄰居的轉(zhuǎn)折點(diǎn),第1種類型至少緊鄰一個(gè)障礙物,如果將其修剪就可能無法返回最優(yōu)路徑;第2種類型的跳點(diǎn)不緊鄰障礙物,只是一個(gè)用來改變方向的中間節(jié)點(diǎn)。

    對以上3種情況進(jìn)行分析,首先“對角線-對角線”轉(zhuǎn)折點(diǎn):因?yàn)棣惺亲顑?yōu)的,所以在緊鄰nk和nk-1的附近必然存在一個(gè)障礙物,強(qiáng)制路徑繞行。若不存在障礙物,必然存在dist(nk-1,nk+1)

    提出刪除第2種類型的跳點(diǎn),將其后繼節(jié)點(diǎn)存儲(chǔ)在列表中,并且每個(gè)新孤立的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)將成為開始跳轉(zhuǎn)的起始位置,后繼節(jié)點(diǎn)的g并沒有因此而發(fā)生改變,在提取具體的路徑時(shí),以“對角優(yōu)先”的方式從最后路徑中的一個(gè)跳點(diǎn)移動(dòng)到下一個(gè)跳點(diǎn)。此策略完全為在線方式,不需要任何特殊的數(shù)據(jù)結(jié)構(gòu),也不存儲(chǔ)或計(jì)算任何其他信息。

    3 仿真實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

    為了驗(yàn)證本文算法的可行性和有效性,將本文算法與傳統(tǒng)A*算法、JPS算法和JPS+算法進(jìn)行對比,分析定性和定量結(jié)果。實(shí)驗(yàn)環(huán)境為規(guī)則的網(wǎng)格地圖、測試庫基準(zhǔn)地圖,計(jì)算機(jī)配置為Windows7,處理器為AMD A8-4500M,運(yùn)行內(nèi)存為4 GB。

    3.1 網(wǎng)格地圖仿真實(shí)驗(yàn)

    在兩種規(guī)格的網(wǎng)格地圖中進(jìn)行仿真,分別為13×19和30×60。圖5所示為13×19網(wǎng)格地圖下的仿真實(shí)驗(yàn),障礙物隨機(jī)生成,障礙物的平均密度設(shè)定約為20%。

    綠色帶圓圈柵格表示起始節(jié)點(diǎn);紅色帶星星柵格為目標(biāo)節(jié)點(diǎn);灰色柵格表示尋路算法在搜索過程中訪問過的節(jié)點(diǎn);藍(lán)色折線表示生成的最終路徑。圖5 A*、JPS及改進(jìn)后的JPS網(wǎng)格地圖仿真實(shí)驗(yàn)結(jié)果Fig.5 Grid map simulation experiment results of A*、JPS and improved JPS algorithm

    從圖5中可直觀看出,A*搜索過的節(jié)點(diǎn)幾乎覆蓋所有網(wǎng)格,搜索量巨大,導(dǎo)致耗時(shí)長,實(shí)時(shí)性差;JPS減少了搜索的節(jié)點(diǎn)數(shù)量,在搜索過程中識別出跳點(diǎn),然后直接從一個(gè)跳點(diǎn)移動(dòng)到下一個(gè)跳點(diǎn),并在對稱性路徑中進(jìn)行對角優(yōu)先選擇;改進(jìn)后的JPS進(jìn)一步減少搜索的節(jié)點(diǎn)數(shù)量,并一次性讀取固定長度的節(jié)點(diǎn)信息,快速識別出當(dāng)前行是否存在死胡同,若為死胡同則快速舍棄對當(dāng)前行的操作,并剔除了僅具有改變方向的中間轉(zhuǎn)折點(diǎn),加快關(guān)鍵跳點(diǎn)的搜尋。

    表2所示為30×60網(wǎng)格環(huán)境下仿真實(shí)驗(yàn)的數(shù)據(jù)對比。分析表2數(shù)據(jù)得知,與傳統(tǒng)A*算法相比,改進(jìn)后的JPS擴(kuò)展節(jié)點(diǎn)數(shù)目縮減了68.9%,搜索耗費(fèi)時(shí)間降低了71.9%,與JPS相比,擴(kuò)展節(jié)點(diǎn)數(shù)目縮減了41.3%,搜索耗費(fèi)時(shí)間降低了33.4%。主要在于改進(jìn)后的JPS通過“塊”操作提高了節(jié)點(diǎn)數(shù)目查詢的效率,剔除中間轉(zhuǎn)折點(diǎn)縮減了擴(kuò)展節(jié)點(diǎn)數(shù)目,使得最終在返回同等長度最優(yōu)路徑的前提下,搜索耗費(fèi)時(shí)間下降。

    表2 30×60柵格環(huán)境下數(shù)據(jù)對比Table 2 Data comparison in 30×60 grid environment

    3.2 基準(zhǔn)庫地圖仿真實(shí)驗(yàn)

    實(shí)驗(yàn)地圖采用基于網(wǎng)格路徑規(guī)劃競賽(grid-based path planning competition,GPPC)[17]中的基準(zhǔn)庫地圖,該比賽旨在提供一套標(biāo)準(zhǔn)的地圖,對算法性能進(jìn)行有意義的比較,已得到IBM Research,University of New South Wales等研究機(jī)構(gòu)的廣泛認(rèn)可,地圖集可從比賽官網(wǎng)上直接獲得。實(shí)驗(yàn)選用Rooms、Dragon Age Origins及Adaptive depth三類地圖,如圖6、表3所示。

    表3 基準(zhǔn)庫地圖Table 3 Benchmark sets

    為了進(jìn)行有說服力的算法驗(yàn)證,將改進(jìn)后的JPS算法與JPS、JPS+算法進(jìn)行性能比較,評估了搜索時(shí)間和路徑長度。在搜索的過程中重復(fù)生成起點(diǎn)到終點(diǎn)之間的最優(yōu)路徑,最優(yōu)路徑上每相鄰的兩點(diǎn)搜尋時(shí)間至少計(jì)算100次,直到這兩點(diǎn)間最優(yōu)路徑運(yùn)行時(shí)間累加到至少需要5 ms,然后最優(yōu)路徑平均搜索時(shí)間為總時(shí)間除以總迭代次數(shù)。

    JPS+將柵格地圖信息預(yù)處理為查詢表,通過查找表格直接獲得路徑中的下一個(gè)跳轉(zhuǎn)點(diǎn),提出的改進(jìn)算法是通過“塊”操作方法獲得路徑中的跳點(diǎn),相較于JPS,以上兩者一個(gè)是通過預(yù)處理來獲得更快的搜索速度,一個(gè)是一次性將修剪規(guī)則用于獲得更多的節(jié)點(diǎn)信息來加快運(yùn)行速度。JPS、JPS+與本文算法三者所使用的修剪規(guī)則與跳點(diǎn)識別規(guī)則是一致的,雖然本文算法剔除了僅具有改變方向的中間轉(zhuǎn)折點(diǎn),但保留了后繼點(diǎn)在列表中,這步操作只是減少了擴(kuò)展節(jié)點(diǎn)數(shù)目,是加快搜索速度的一部分,所以在每幅測試地圖中3種算法返回的最優(yōu)路徑的長度是一致的。

    抽取實(shí)驗(yàn)中部分?jǐn)?shù)據(jù)如圖7所示。圖7中橫坐標(biāo)表示測試的每幅地圖中最優(yōu)路徑長度,縱坐標(biāo)表示所耗費(fèi)的搜索時(shí)間,可看出在每幅地圖中,JPS+都快于在線搜索的JPS和改進(jìn)的JPS,但本文算法也大幅度提高了搜索速度,且是完全在線的,不需要任何特殊的數(shù)據(jù)結(jié)構(gòu),也不存儲(chǔ)或計(jì)算任何其他信息,充分表明了本文算法的優(yōu)越性。

    圖7 基準(zhǔn)庫地圖下3種算法時(shí)間對比Fig.7 Time comparison of three algorithms under the benchmark sets

    4 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

    為了驗(yàn)證改進(jìn)算法在實(shí)際應(yīng)用中的可行性,在基于機(jī)器人操作系統(tǒng)(robot operating system, ROS)的移動(dòng)機(jī)器人Turtlebot2進(jìn)行真實(shí)場景下的實(shí)驗(yàn),計(jì)算機(jī)為華碩筆記本(i5-5200),系統(tǒng)為Ubuntu14.04+ROS Indigo版本。該機(jī)器人基于差速兩輪驅(qū)動(dòng),配備了由微軟開發(fā)的Kinect深度傳感器作為視覺傳感器,韓國的Yujin Kobuki作為移動(dòng)基座,如圖8所示。

    圖8 TurtleBot 2移動(dòng)機(jī)器人Fig.8 TurtleBot 2 mobile robot

    實(shí)驗(yàn)場景為5 m×3 m,障礙物隨機(jī)放置,占有率為20%。首先,3D體感相機(jī)Kinect獲取外界環(huán)境信息,然后調(diào)用Gmapping模塊的數(shù)據(jù)創(chuàng)建地圖,初始掃描設(shè)置為20 cm/s的前進(jìn)速度和20 cm/s的旋轉(zhuǎn)速度,確保機(jī)器人可充分分析環(huán)境數(shù)據(jù)并建立環(huán)境地圖,如圖9所示,其中黑色部分被認(rèn)為是檢測和識別后的障礙物。

    圖9 實(shí)驗(yàn)場景與SLAM構(gòu)建的環(huán)境地圖Fig.9 Experimental scene and environment map constructed by SLAM

    在上述SLAM構(gòu)建的環(huán)境地圖中進(jìn)行改進(jìn)JPS算法的實(shí)驗(yàn)驗(yàn)證,起點(diǎn)選擇為SLAM地圖的原點(diǎn),即建圖的起始位置,目標(biāo)點(diǎn)選為起始點(diǎn)的對角位置,amcl模塊完成機(jī)器人自定位,move_base模塊調(diào)用改進(jìn)后的JPS算法,驅(qū)動(dòng)和控制機(jī)器人移動(dòng)到選定的目標(biāo),在rviz可視化界面中,點(diǎn)擊2Dpose Esitimate選取地圖中機(jī)器人初始位姿,2DNavGoal給定小車在地圖中的目標(biāo)位置,綠線為機(jī)器人規(guī)劃出的路徑,實(shí)驗(yàn)過程如圖10所示,實(shí)驗(yàn)結(jié)果如圖11所示。

    圖10 改進(jìn)的JPS Turtlebot2路徑規(guī)劃過程Fig.10 Path planning process of improved JPS on Turtlebot2

    圖11 改進(jìn)的JPS Turtlebot2路徑規(guī)劃結(jié)果圖及示意圖Fig.11 Path planning real result of improved JPS on Turtlebot2 and diagrammatic drawing

    5 結(jié)論

    針對JPS搜尋跳點(diǎn)時(shí)所涉及大量迭代產(chǎn)生的過大計(jì)算量,提出通過“塊”操作方法,在一次搜索中快速掃描底層網(wǎng)格中的一個(gè)區(qū)域,將JPS中的修剪規(guī)則一次應(yīng)用于多個(gè)節(jié)點(diǎn),并在采取對角優(yōu)先方式的前提下,剔除僅具有改變方向的中間轉(zhuǎn)折點(diǎn),提高了單個(gè)節(jié)點(diǎn)的平均處理時(shí)間,達(dá)到了快速識別跳轉(zhuǎn)點(diǎn)的目的,同時(shí)保留了與原始算法相同的固有優(yōu)勢:完整性、最優(yōu)性。最終實(shí)驗(yàn)結(jié)果表明了本文方法的優(yōu)越性。下一步計(jì)劃利用歧路檢測和狀態(tài)空間的剪枝算法,如Dead-end heuristic,Swamps或者Portal heuristic算法,在搜索過程中通過識別并忽略無需探測的區(qū)域來最優(yōu)化地到達(dá)目標(biāo)點(diǎn)。

    猜你喜歡
    轉(zhuǎn)折點(diǎn)搜索算法對角線
    用活平行四邊形對角線的性質(zhì)
    畫與理
    未來訪談:站在轉(zhuǎn)折點(diǎn)上
    出版人(2023年3期)2023-03-10 06:53:44
    改進(jìn)的和聲搜索算法求解凸二次規(guī)劃及線性規(guī)劃
    我國中等收入陷阱解構(gòu):收入分配與庫茲涅茨轉(zhuǎn)折點(diǎn)
    邊、角、對角線與平行四邊形的關(guān)系
    看四邊形對角線的“氣質(zhì)”
    基于汽車接力的潮流轉(zhuǎn)移快速搜索算法
    基于逐維改進(jìn)的自適應(yīng)步長布谷鳥搜索算法
    母雞下蛋
    一进一出抽搐gif免费好疼| 一区在线观看完整版| www.999成人在线观看| 国产欧美日韩一区二区三| 成人三级黄色视频| 好男人电影高清在线观看| 亚洲成人久久性| 少妇熟女aⅴ在线视频| 级片在线观看| 一区在线观看完整版| 亚洲一卡2卡3卡4卡5卡精品中文| 久久精品人人爽人人爽视色| 好男人电影高清在线观看| 久久国产乱子伦精品免费另类| 侵犯人妻中文字幕一二三四区| 亚洲中文日韩欧美视频| 看黄色毛片网站| 精品高清国产在线一区| 亚洲 欧美一区二区三区| 国产高清videossex| 黑人欧美特级aaaaaa片| 免费在线观看日本一区| 午夜日韩欧美国产| 又黄又爽又免费观看的视频| 亚洲熟女毛片儿| 999精品在线视频| 欧美一区二区精品小视频在线| 国产精品免费视频内射| 又紧又爽又黄一区二区| 999久久久精品免费观看国产| 无限看片的www在线观看| 久久久久国产精品人妻aⅴ院| 免费一级毛片在线播放高清视频 | 亚洲全国av大片| 一进一出抽搐gif免费好疼| 最好的美女福利视频网| 一区二区三区高清视频在线| 国产成人欧美| 午夜两性在线视频| 每晚都被弄得嗷嗷叫到高潮| 亚洲精品中文字幕在线视频| 夜夜看夜夜爽夜夜摸| 亚洲欧美激情在线| 欧美成人午夜精品| 女人被躁到高潮嗷嗷叫费观| 婷婷精品国产亚洲av在线| 乱人伦中国视频| 亚洲少妇的诱惑av| 欧美av亚洲av综合av国产av| 美女午夜性视频免费| 搡老岳熟女国产| av欧美777| 一进一出好大好爽视频| 黄色女人牲交| 欧美黑人欧美精品刺激| 老汉色av国产亚洲站长工具| 久久精品人人爽人人爽视色| 丝袜美腿诱惑在线| 亚洲一码二码三码区别大吗| cao死你这个sao货| 99riav亚洲国产免费| 99精品久久久久人妻精品| 别揉我奶头~嗯~啊~动态视频| 久久天躁狠狠躁夜夜2o2o| 高清毛片免费观看视频网站| 久久午夜亚洲精品久久| 亚洲人成伊人成综合网2020| 成人国语在线视频| √禁漫天堂资源中文www| 高清在线国产一区| 精品国内亚洲2022精品成人| 国产精品亚洲美女久久久| 久久精品亚洲熟妇少妇任你| 国产精品99久久99久久久不卡| 欧美日韩瑟瑟在线播放| 夜夜看夜夜爽夜夜摸| 国产高清视频在线播放一区| 国产精品久久久久久亚洲av鲁大| ponron亚洲| 日韩成人在线观看一区二区三区| 午夜影院日韩av| 97人妻精品一区二区三区麻豆 | 50天的宝宝边吃奶边哭怎么回事| 欧美久久黑人一区二区| 日日夜夜操网爽| 欧美乱码精品一区二区三区| 日韩国内少妇激情av| 成人国产综合亚洲| 国产精品1区2区在线观看.| 欧美成人午夜精品| 亚洲熟女毛片儿| 老司机靠b影院| 午夜影院日韩av| 国产又色又爽无遮挡免费看| 国产私拍福利视频在线观看| 亚洲精品粉嫩美女一区| 亚洲av日韩精品久久久久久密| 国产一区二区在线av高清观看| 欧美日韩中文字幕国产精品一区二区三区 | 精品福利观看| 777久久人妻少妇嫩草av网站| 欧美 亚洲 国产 日韩一| 亚洲最大成人中文| 亚洲欧美激情在线| 日本欧美视频一区| 婷婷六月久久综合丁香| 久久婷婷人人爽人人干人人爱 | 男人的好看免费观看在线视频 | 日韩欧美国产在线观看| 欧美久久黑人一区二区| 免费一级毛片在线播放高清视频 | 琪琪午夜伦伦电影理论片6080| 久久久久久国产a免费观看| 免费观看人在逋| 免费看十八禁软件| 亚洲成av人片免费观看| 非洲黑人性xxxx精品又粗又长| bbb黄色大片| 日本撒尿小便嘘嘘汇集6| 久久精品国产99精品国产亚洲性色 | 男人操女人黄网站| 亚洲免费av在线视频| 久久伊人香网站| 欧美最黄视频在线播放免费| 91在线观看av| 亚洲最大成人中文| 亚洲欧美激情在线| 国产野战对白在线观看| 国产精品久久久久久精品电影 | 国产蜜桃级精品一区二区三区| avwww免费| 天堂√8在线中文| а√天堂www在线а√下载| 亚洲精品久久国产高清桃花| 久久午夜亚洲精品久久| 久久久久久亚洲精品国产蜜桃av| 成人国语在线视频| 国产高清videossex| 最近最新中文字幕大全电影3 | 亚洲七黄色美女视频| 久久久久国内视频| 欧美乱妇无乱码| 日本一区二区免费在线视频| 午夜福利成人在线免费观看| 两个人看的免费小视频| 搡老熟女国产l中国老女人| 亚洲欧美精品综合一区二区三区| 曰老女人黄片| 久久精品91蜜桃| 国产又爽黄色视频| 国产精品九九99| 久久天躁狠狠躁夜夜2o2o| 非洲黑人性xxxx精品又粗又长| av片东京热男人的天堂| 级片在线观看| 一区二区三区国产精品乱码| 亚洲国产精品合色在线| 999精品在线视频| 国产91精品成人一区二区三区| 天堂动漫精品| 最近最新中文字幕大全免费视频| av网站免费在线观看视频| www.www免费av| 操出白浆在线播放| www国产在线视频色| 久久热在线av| 亚洲最大成人中文| 亚洲国产欧美日韩在线播放| 免费看a级黄色片| 精品人妻在线不人妻| 国产亚洲欧美在线一区二区| 国产精品 国内视频| 成年女人毛片免费观看观看9| 免费久久久久久久精品成人欧美视频| 亚洲精品国产一区二区精华液| 久久久久国产一级毛片高清牌| 久久久久国产一级毛片高清牌| 日韩大尺度精品在线看网址 | 国产一区二区激情短视频| 免费在线观看黄色视频的| 脱女人内裤的视频| 午夜福利高清视频| 丰满的人妻完整版| 精品免费久久久久久久清纯| 大香蕉久久成人网| 国产精品久久电影中文字幕| 女性被躁到高潮视频| 乱人伦中国视频| 成人亚洲精品一区在线观看| 一级,二级,三级黄色视频| 女警被强在线播放| 高清在线国产一区| 欧美性长视频在线观看| 18禁观看日本| 久久亚洲精品不卡| 精品国产乱码久久久久久男人| 高清黄色对白视频在线免费看| 一本久久中文字幕| 精品日产1卡2卡| 成人精品一区二区免费| 国产一区二区三区视频了| 午夜福利一区二区在线看| 国内毛片毛片毛片毛片毛片| 亚洲色图 男人天堂 中文字幕| 亚洲成国产人片在线观看| 成人欧美大片| 亚洲一区二区三区色噜噜| 久久精品国产亚洲av香蕉五月| 亚洲精品美女久久av网站| tocl精华| 丰满人妻熟妇乱又伦精品不卡| 日韩欧美在线二视频| 搡老熟女国产l中国老女人| 99久久久亚洲精品蜜臀av| 国产精品久久久人人做人人爽| 亚洲精品国产精品久久久不卡| 男人舔女人下体高潮全视频| 少妇被粗大的猛进出69影院| 国产av精品麻豆| 18禁黄网站禁片午夜丰满| 免费在线观看日本一区| 欧美成人午夜精品| 午夜福利欧美成人| 亚洲无线在线观看| 国产欧美日韩综合在线一区二区| 老司机午夜福利在线观看视频| 可以在线观看毛片的网站| 精品国产超薄肉色丝袜足j| 男女做爰动态图高潮gif福利片 | 久久人妻熟女aⅴ| bbb黄色大片| 啦啦啦观看免费观看视频高清 | 国产成人精品在线电影| 日韩高清综合在线| 人妻久久中文字幕网| 在线观看舔阴道视频| 黑人巨大精品欧美一区二区蜜桃| 性少妇av在线| 美女高潮到喷水免费观看| 久久人人精品亚洲av| 亚洲欧美激情在线| 91在线观看av| 成熟少妇高潮喷水视频| 欧美成人一区二区免费高清观看 | 91av网站免费观看| 12—13女人毛片做爰片一| 成人精品一区二区免费| 欧洲精品卡2卡3卡4卡5卡区| 色综合欧美亚洲国产小说| 一级,二级,三级黄色视频| 欧美在线一区亚洲| 91精品三级在线观看| 宅男免费午夜| 日本精品一区二区三区蜜桃| 久久欧美精品欧美久久欧美| 亚洲av五月六月丁香网| 精品一区二区三区av网在线观看| 国产色视频综合| 亚洲精品中文字幕一二三四区| 国产精品,欧美在线| 91成人精品电影| 777久久人妻少妇嫩草av网站| 免费久久久久久久精品成人欧美视频| 1024视频免费在线观看| 老鸭窝网址在线观看| 久久久水蜜桃国产精品网| 99热只有精品国产| 日韩欧美一区二区三区在线观看| 成人三级黄色视频| 午夜影院日韩av| 久久久国产成人精品二区| 免费人成视频x8x8入口观看| 叶爱在线成人免费视频播放| 亚洲中文av在线| 成人三级黄色视频| 久久久久久免费高清国产稀缺| 在线观看舔阴道视频| 国产aⅴ精品一区二区三区波| 如日韩欧美国产精品一区二区三区| 久久精品影院6| av在线播放免费不卡| 婷婷精品国产亚洲av在线| 此物有八面人人有两片| 亚洲成人久久性| 午夜免费成人在线视频| 美女大奶头视频| 日本黄色视频三级网站网址| 国产亚洲精品av在线| 亚洲精品国产色婷婷电影| 欧美黄色淫秽网站| 国产极品粉嫩免费观看在线| 最近最新免费中文字幕在线| 一夜夜www| 欧美日韩亚洲综合一区二区三区_| 免费av毛片视频| 村上凉子中文字幕在线| 久久久久久免费高清国产稀缺| 久久精品亚洲熟妇少妇任你| 成人三级黄色视频| 欧美激情高清一区二区三区| 首页视频小说图片口味搜索| 好看av亚洲va欧美ⅴa在| 久久 成人 亚洲| 亚洲成a人片在线一区二区| 久久久国产精品麻豆| 精品高清国产在线一区| 搡老妇女老女人老熟妇| 国产精品98久久久久久宅男小说| av福利片在线| 久久精品国产99精品国产亚洲性色 | 日韩一卡2卡3卡4卡2021年| 精品高清国产在线一区| 亚洲少妇的诱惑av| 久久精品国产亚洲av高清一级| 欧洲精品卡2卡3卡4卡5卡区| 亚洲专区国产一区二区| 亚洲视频免费观看视频| 在线观看午夜福利视频| 国产精品永久免费网站| 亚洲人成网站在线播放欧美日韩| 日韩精品免费视频一区二区三区| 制服丝袜大香蕉在线| 99久久综合精品五月天人人| 亚洲一区中文字幕在线| 欧美黑人精品巨大| 青草久久国产| 色播在线永久视频| 国产成人系列免费观看| 欧美成人性av电影在线观看| 亚洲第一电影网av| 一二三四在线观看免费中文在| 最好的美女福利视频网| 满18在线观看网站| 亚洲欧美精品综合久久99| 久久国产精品影院| 精品乱码久久久久久99久播| 欧美老熟妇乱子伦牲交| 麻豆av在线久日| 色尼玛亚洲综合影院| 少妇 在线观看| 久久久精品欧美日韩精品| 亚洲成国产人片在线观看| 国产精品1区2区在线观看.| 欧美黑人欧美精品刺激| 国产麻豆成人av免费视频| 国产伦一二天堂av在线观看| 日韩精品免费视频一区二区三区| 一夜夜www| 成人18禁在线播放| 欧美亚洲日本最大视频资源| 日韩三级视频一区二区三区| 免费在线观看黄色视频的| 在线国产一区二区在线| av欧美777| 欧美乱妇无乱码| 99精品在免费线老司机午夜| 韩国精品一区二区三区| 国内毛片毛片毛片毛片毛片| 国产亚洲欧美精品永久| 亚洲精品在线美女| 成人免费观看视频高清| 亚洲第一欧美日韩一区二区三区| 欧美乱码精品一区二区三区| 久久天堂一区二区三区四区| 麻豆国产av国片精品| 黑人操中国人逼视频| 国产xxxxx性猛交| 十八禁人妻一区二区| 久久 成人 亚洲| 丁香欧美五月| 满18在线观看网站| 91大片在线观看| 成人av一区二区三区在线看| 久久久国产精品麻豆| 自拍欧美九色日韩亚洲蝌蚪91| 精品久久久久久久人妻蜜臀av | 在线观看免费视频网站a站| 桃红色精品国产亚洲av| 久久青草综合色| 国产一区在线观看成人免费| 午夜福利在线观看吧| 亚洲 欧美一区二区三区| 亚洲伊人色综图| 人成视频在线观看免费观看| 国产日韩一区二区三区精品不卡| 亚洲中文字幕一区二区三区有码在线看 | 亚洲精品一卡2卡三卡4卡5卡| 亚洲精品久久成人aⅴ小说| 麻豆国产av国片精品| 色婷婷久久久亚洲欧美| 亚洲精品美女久久久久99蜜臀| 欧美色视频一区免费| 女人爽到高潮嗷嗷叫在线视频| 人人妻,人人澡人人爽秒播| 午夜福利在线观看吧| 亚洲 欧美一区二区三区| 国产三级在线视频| 一级,二级,三级黄色视频| 一级毛片精品| 久久国产精品男人的天堂亚洲| 免费人成视频x8x8入口观看| 欧美最黄视频在线播放免费| 美女免费视频网站| 亚洲成av人片免费观看| 少妇熟女aⅴ在线视频| 国产蜜桃级精品一区二区三区| 高清毛片免费观看视频网站| 99国产精品99久久久久| 一区福利在线观看| 久久久国产成人免费| 又黄又爽又免费观看的视频| 国产一区二区在线av高清观看| e午夜精品久久久久久久| 999久久久精品免费观看国产| 嫩草影院精品99| 免费观看精品视频网站| 国产蜜桃级精品一区二区三区| 给我免费播放毛片高清在线观看| 真人做人爱边吃奶动态| 男女下面进入的视频免费午夜 | 久久久久精品国产欧美久久久| 悠悠久久av| 免费搜索国产男女视频| 看黄色毛片网站| 亚洲激情在线av| 亚洲欧美激情综合另类| 午夜激情av网站| 精品久久久久久久毛片微露脸| svipshipincom国产片| 日韩精品青青久久久久久| 老鸭窝网址在线观看| 男男h啪啪无遮挡| 欧美老熟妇乱子伦牲交| 久久久久久亚洲精品国产蜜桃av| 久热爱精品视频在线9| 免费高清在线观看日韩| 黄色丝袜av网址大全| 夜夜看夜夜爽夜夜摸| 啦啦啦免费观看视频1| 国产欧美日韩综合在线一区二区| 好看av亚洲va欧美ⅴa在| 亚洲熟妇中文字幕五十中出| 精品欧美一区二区三区在线| 老熟妇仑乱视频hdxx| av超薄肉色丝袜交足视频| 在线国产一区二区在线| 亚洲第一青青草原| 日韩一卡2卡3卡4卡2021年| 妹子高潮喷水视频| 一夜夜www| 在线国产一区二区在线| 精品乱码久久久久久99久播| √禁漫天堂资源中文www| 女人高潮潮喷娇喘18禁视频| 大香蕉久久成人网| av免费在线观看网站| 俄罗斯特黄特色一大片| 50天的宝宝边吃奶边哭怎么回事| 午夜福利18| 人人妻人人澡人人看| 女警被强在线播放| 美女国产高潮福利片在线看| 91成年电影在线观看| 精品久久久久久久久久免费视频| 男女午夜视频在线观看| 精品熟女少妇八av免费久了| 在线观看免费视频日本深夜| 搡老妇女老女人老熟妇| 91九色精品人成在线观看| 在线天堂中文资源库| 精品久久久久久成人av| 免费看a级黄色片| 久久午夜亚洲精品久久| 成年版毛片免费区| 久久精品人人爽人人爽视色| 人妻丰满熟妇av一区二区三区| 美女免费视频网站| 国产97色在线日韩免费| 18禁观看日本| 大香蕉久久成人网| 亚洲欧美精品综合一区二区三区| 大陆偷拍与自拍| 看黄色毛片网站| 国产午夜精品久久久久久| 黄片播放在线免费| av欧美777| 一卡2卡三卡四卡精品乱码亚洲| 嫩草影视91久久| 99香蕉大伊视频| 妹子高潮喷水视频| 亚洲精品久久国产高清桃花| 欧美不卡视频在线免费观看 | 黄色a级毛片大全视频| 婷婷六月久久综合丁香| av福利片在线| 精品一区二区三区视频在线观看免费| 日本a在线网址| 欧美乱码精品一区二区三区| 琪琪午夜伦伦电影理论片6080| 日本三级黄在线观看| 啦啦啦免费观看视频1| 性欧美人与动物交配| 国产99白浆流出| 男人的好看免费观看在线视频 | www.www免费av| 国产精品99久久99久久久不卡| 俄罗斯特黄特色一大片| 成人欧美大片| 老汉色av国产亚洲站长工具| 九色国产91popny在线| 少妇熟女aⅴ在线视频| 国内毛片毛片毛片毛片毛片| 黄色毛片三级朝国网站| 免费av毛片视频| 国产激情久久老熟女| 国产又爽黄色视频| 久久精品国产99精品国产亚洲性色 | 精品福利观看| 日韩av在线大香蕉| 757午夜福利合集在线观看| 少妇裸体淫交视频免费看高清 | 国产亚洲精品久久久久久毛片| 免费看美女性在线毛片视频| 国产精品野战在线观看| АⅤ资源中文在线天堂| 人人澡人人妻人| 国产精品久久久久久精品电影 | 欧美色欧美亚洲另类二区 | 亚洲九九香蕉| 一区二区三区国产精品乱码| 亚洲av成人av| 高潮久久久久久久久久久不卡| 欧美黑人精品巨大| 欧美成人免费av一区二区三区| 少妇 在线观看| a在线观看视频网站| 国产亚洲精品久久久久久毛片| 亚洲熟女毛片儿| 男人的好看免费观看在线视频 | 久久精品国产亚洲av高清一级| 丝袜美足系列| 久久精品人人爽人人爽视色| 国产亚洲精品av在线| 国产精品爽爽va在线观看网站 | 亚洲七黄色美女视频| 香蕉久久夜色| 淫秽高清视频在线观看| 一级毛片精品| 亚洲精品国产精品久久久不卡| 精品日产1卡2卡| 此物有八面人人有两片| 无人区码免费观看不卡| 亚洲 国产 在线| 香蕉国产在线看| 一二三四在线观看免费中文在| 亚洲七黄色美女视频| 欧美绝顶高潮抽搐喷水| 久久精品国产亚洲av高清一级| 欧美日本视频| 91成年电影在线观看| 麻豆一二三区av精品| 国产三级黄色录像| 亚洲午夜理论影院| 亚洲人成77777在线视频| 麻豆一二三区av精品| 国产精品日韩av在线免费观看 | 免费少妇av软件| 色av中文字幕| 久热这里只有精品99| av天堂久久9| 国产av一区二区精品久久| 正在播放国产对白刺激| 久久精品国产清高在天天线| av天堂久久9| 在线免费观看的www视频| 国产精品电影一区二区三区| 亚洲成人国产一区在线观看| 国产av一区在线观看免费| 久久婷婷人人爽人人干人人爱 | 中文亚洲av片在线观看爽| 免费看十八禁软件| 久久久久久免费高清国产稀缺| 国产一区二区三区在线臀色熟女| 精品一区二区三区av网在线观看| 久久天堂一区二区三区四区| 久久人人爽av亚洲精品天堂| 深夜精品福利| 亚洲精品av麻豆狂野| 久久精品人人爽人人爽视色| 精品久久久精品久久久| 久久中文字幕一级| 免费在线观看视频国产中文字幕亚洲| 国产一区二区三区在线臀色熟女| 国产精品野战在线观看| 成人亚洲精品一区在线观看| 在线国产一区二区在线| 午夜亚洲福利在线播放| 欧美精品亚洲一区二区| tocl精华| 嫩草影视91久久| 国产精品亚洲av一区麻豆| 久久狼人影院| 亚洲精品国产色婷婷电影| 亚洲久久久国产精品| 日日爽夜夜爽网站| 久久中文字幕人妻熟女| 国产精品国产高清国产av| 禁无遮挡网站| 97碰自拍视频| 首页视频小说图片口味搜索| 国产xxxxx性猛交| 久久久久精品国产欧美久久久| 国产蜜桃级精品一区二区三区| 性欧美人与动物交配| 亚洲精品久久成人aⅴ小说|