融合人工勢(shì)場(chǎng)法的動(dòng)態(tài)快速行進(jìn)樹路徑規(guī)劃算法

摘 要：針對(duì)快速行進(jìn)樹算法（FMT*）由于隨機(jī)采樣導(dǎo)致的冗余探索問題以及不適用于動(dòng)態(tài)環(huán)境的問題，提出一種融合人工勢(shì)場(chǎng)法的動(dòng)態(tài)快速行進(jìn)樹路徑規(guī)劃算法（APF-Dynamic FMT*），該算法設(shè)計(jì)了一種基于人工勢(shì)場(chǎng)法的采樣點(diǎn)引導(dǎo)函數(shù)，該函數(shù)根據(jù)環(huán)境信息動(dòng)態(tài)的調(diào)整采樣點(diǎn)生成范圍，減少冗余探索。同時(shí)，該算法設(shè)計(jì)了一種路徑樹動(dòng)態(tài)調(diào)整機(jī)制，當(dāng)現(xiàn)有路徑受到環(huán)境改變的影響時(shí)，能在未受影響的剩余路徑樹的基礎(chǔ)上重新規(guī)劃出新的優(yōu)秀路徑，適用于解決動(dòng)態(tài)環(huán)境下的路徑規(guī)劃問題。仿真實(shí)驗(yàn)結(jié)果表明，APF-Dynamic FMT*算法在消耗相同計(jì)算資源的同時(shí)，顯著提高了路徑規(guī)劃的成功率與路徑質(zhì)量，且當(dāng)現(xiàn)有路徑受動(dòng)態(tài)環(huán)境影響后，能夠高效地重新規(guī)劃出可通行的優(yōu)秀路徑。

關(guān)鍵詞：FMT*算法；人工勢(shì)場(chǎng)法；動(dòng)態(tài)路徑規(guī)劃

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）09-025-2745-06

doi：10.19734/j.issn.1001-3695.2024.01.0004

Dynamic fast marching tree algorithm with integrated artificial potential fields

Wu Xupeng1，2，Jia Xiaolin1，2，Gu Yajun1，2

（1.RFID & IOT Laboratory，School of Computer Science & Technology，Southwest University of Science & Technology，Mianyang Sichuan 621010，China;2.Mobile Internet of Things & Radio Frequency Identification Technology Key Laboratory of Mianyang，Mianyang Sichuan 621010，China）

Abstract：Addressing the issues of redundant exploration and inapplicability in dynamic environments inherent in fast mar-ching tree algorithm（FMT*），this paper proposed the APF-Dynamic FMT* algorithm，which integrated artificial potential field method.This algorithm designed a sampling point guidance function based on artificial potential field method，which could dynamically adjust the sampling point generation range according to the environment information to reduce redundant exploration.Additionally，this algorithm designed a dynamic path tree adjustment mechanism，when the existing path was affected by the environment change，it could re-plan a new excellent path on the basis of the remaining path tree that is not affected，which was suitable for solving the path planning problem in dynamic environment.The results verify that the APF-Dynamic FMT* algorithm can significantly improve the success rate and path quality of path planning while consuming the same computational resources，and when the existing path is affected by the dynamic environment，it can efficiently re-plan the passable excellent path.

Key words：FMT* algorithm;artificial potential field method;dynamic path planning

0 引言

路徑規(guī)劃在機(jī)器人導(dǎo)航、自動(dòng)駕駛汽車以及眾多自動(dòng)化系統(tǒng)中扮演著至關(guān)重要的角色。它涉及在環(huán)境中尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的有效路徑，同時(shí)考慮優(yōu)化路徑的長(zhǎng)度、安全性和可行性［1，2］。

概率路線圖快速探索隨機(jī)樹（rapidly exploring random trees，RRT）與快速行進(jìn)樹算法（fast marching tree，F(xiàn)MT*）都是基于采樣的路徑規(guī)劃算法［3，4］。RRT算法雖然路徑規(guī)劃效率較高，但已被證明無法規(guī)劃出最優(yōu)的路徑［5］。在高維空間中，傳統(tǒng)路徑規(guī)劃算法往往因計(jì)算復(fù)雜度高而效率不佳，為了克服這一限制，Janson等人［6］于2013年提出了FMT*算法。FMT*算法是一種基于采樣的漸近最優(yōu)算法。該算法通過有效地利用采樣點(diǎn)來構(gòu)建一棵覆蓋搜索空間的樹，從而高效地找到從起點(diǎn)到終點(diǎn)的路徑。FMT*算法在多種應(yīng)用場(chǎng)景下展現(xiàn)了出色的性能，但在特定條件下，如復(fù)雜地形或動(dòng)態(tài)環(huán)境中，它仍然面臨一些挑戰(zhàn)［7～9］。

針對(duì)FMT*算法的研究主要集中在如何提高其在復(fù)雜環(huán)境中的適應(yīng)性和效率上。為了提高FMT*算法的路徑規(guī)劃效率，Starek等人［10］提出了一種雙向拓展的FMT*算法（bidirectional fast marching Tree，BFMT*），縮短了搜索時(shí)間，但增加了計(jì)算資源消耗；Gao等人［11］將BFMT*與A*算法結(jié)合，形成了一種雙向搜索的啟發(fā)式路徑規(guī)劃算法（heuristic bidirectional fast marching tree，HBFMT*），提高了探索效率，但傳統(tǒng)啟發(fā)函數(shù)使用的樣本信息不夠充分，有時(shí)會(huì)影響計(jì)算效率。Wu等人［12］提出APF-IRRT*算法（artificial potential field-informed RRT*），通過引入人工勢(shì)場(chǎng)方法來提高移動(dòng)機(jī)器人路徑規(guī)劃的效率和質(zhì)量，但在動(dòng)態(tài)環(huán)境中，一旦環(huán)境變化影響了現(xiàn)有路徑，需要從頭開始重新規(guī)劃路徑，效率較低。

針對(duì)FMT*算法在采樣點(diǎn)數(shù)量較少時(shí)路徑規(guī)劃成功率較低、路徑不夠優(yōu)秀且無法應(yīng)對(duì)動(dòng)態(tài)環(huán)境的問題，提出一種融合人工勢(shì)場(chǎng)法的動(dòng)態(tài)快速行進(jìn)樹路徑規(guī)劃算法（dynamic fast marching tree algorithm with integrated artificial potential field，APF-Dynamic FMT*）。APF-Dynamic FMT*與APF-IRRT*算法在利用人工勢(shì)場(chǎng)法改善路徑規(guī)劃效率與質(zhì)量方面有著共同的理念。然而，APF-Dynamic FMT*算法在此基礎(chǔ)上進(jìn)一步針對(duì)動(dòng)態(tài)環(huán)境的路徑規(guī)劃問題進(jìn)行優(yōu)化，展現(xiàn)出針對(duì)動(dòng)態(tài)環(huán)境適應(yīng)性的創(chuàng)新和進(jìn)步。該算法結(jié)合了人工勢(shì)場(chǎng)法的環(huán)境適應(yīng)性和FMT*算法的路徑規(guī)劃策略，顯著提高了在采樣點(diǎn)數(shù)量較少時(shí)的路徑規(guī)劃成功率與路徑質(zhì)量，同時(shí)采用路徑樹動(dòng)態(tài)調(diào)整機(jī)制，在動(dòng)態(tài)環(huán)境中能高效地規(guī)劃出新路徑。通過仿真實(shí)驗(yàn)驗(yàn)證了APF-Dynamic FMT*算法的有效性以及在動(dòng)態(tài)環(huán)境下的可用性。

1 問題描述

本文主要考慮二維路徑規(guī)劃問題，F(xiàn)MT*算法的核心理念是在一組預(yù)先生成的采樣點(diǎn)上實(shí)施動(dòng)態(tài)遞歸探索，通過設(shè)定的連接半徑和鄰域篩選策略來構(gòu)建出一棵高效的路徑樹。在FMT*算法中，采樣點(diǎn)是隨機(jī)生成并均勻分布于整個(gè)搜索空間的，如圖1所示，其中矩形代表障礙物，藍(lán)色點(diǎn)是起點(diǎn)，綠色點(diǎn)是目標(biāo)點(diǎn)，紅色小點(diǎn)是采樣點(diǎn)（見電子版），這種均勻分布的采樣方法會(huì)導(dǎo)致較多的冗余探索，影響探索效率。

在FMT*算法的路徑規(guī)劃過程中，如圖2所示，路徑樹會(huì)均勻地向各個(gè)方向擴(kuò)展。然而，由于某些采樣點(diǎn)距離較遠(yuǎn)，它們無法有效地被整合到路徑樹中，這導(dǎo)致了計(jì)算資源的不必要浪費(fèi)。

由于FMT*算法在規(guī)劃開始之前對(duì)整個(gè)搜索空間進(jìn)行一次性采樣，并在這些采樣點(diǎn)上構(gòu)建一棵樹。在動(dòng)態(tài)環(huán)境中，障礙物的位置可能隨時(shí)間改變，這使得預(yù)先采樣的點(diǎn)可能變得不再有效或安全，因而需要重新采樣和構(gòu)建路徑。并且FMT*算法沒有應(yīng)對(duì)環(huán)境變化的響應(yīng)機(jī)制，在動(dòng)態(tài)環(huán)境下，一旦環(huán)境發(fā)生變化，需要從起點(diǎn)開始重新規(guī)劃，包括重新采樣和構(gòu)建路徑樹。這一過程消耗了大量的計(jì)算資源與時(shí)間，特別是在環(huán)境頻繁發(fā)生變化的情況下，這會(huì)大大降低算法的實(shí)用性。

綜上所述，F(xiàn)MT*算法進(jìn)行路徑規(guī)劃時(shí)，采樣點(diǎn)隨機(jī)生成導(dǎo)致的冗余探索，計(jì)算資源浪費(fèi)等問題是導(dǎo)致FMT*算法在采樣點(diǎn)數(shù)量較少時(shí)路徑規(guī)劃成功率低、路徑不夠優(yōu)秀的主要原因，且由于FMT*算法通常針對(duì)靜態(tài)環(huán)境設(shè)計(jì)，難以適應(yīng)環(huán)境的實(shí)時(shí)變化［13］。在已有的環(huán)境基礎(chǔ)上，如果向環(huán)境中動(dòng)態(tài)添加障礙物以阻擋現(xiàn)有路徑，由于FMT*算法無法對(duì)實(shí)時(shí)的環(huán)境變化作出應(yīng)對(duì)，不適用于動(dòng)態(tài)環(huán)境［14］。

2 APF-Dynamic FMT*算法

針對(duì)FMT算法在動(dòng)態(tài)環(huán)境下的局限性，本文提出了APF-Dynamic FMT算法。該算法設(shè)計(jì)了一種基于人工勢(shì)場(chǎng)法的采樣點(diǎn)引導(dǎo)函數(shù)SampleAPF（n），不同于FMT*的隨機(jī)采樣策略，SampleAPF（n）能夠根據(jù)環(huán)境的障礙物占比信息動(dòng)態(tài)調(diào)整采樣點(diǎn)的生成范圍。同時(shí)，APF-Dynamic FMT算法設(shè)計(jì)了一種路徑樹動(dòng)態(tài)調(diào)整機(jī)制以實(shí)時(shí)監(jiān)測(cè)環(huán)境變化（如障礙物的新增），若新的障礙物出現(xiàn)阻擋了現(xiàn)有路徑，能夠快速規(guī)劃出新的優(yōu)秀路徑。

2.1 基于人工勢(shì)場(chǎng)法的采樣點(diǎn)生成函數(shù)

由于FMT*算法采用隨機(jī)生成采樣點(diǎn)的策略，導(dǎo)致大量冗余探索和計(jì)算資源的浪費(fèi)。FMT*算法所生成的采樣點(diǎn)中，如圖3所示，圖中綠色橢圓虛線所圈住的范圍內(nèi)的采樣點(diǎn)與FMT*算法路徑規(guī)劃的成功率、路徑質(zhì)量高度相關(guān)，但位于綠色橢圓虛線圈外范圍的采樣點(diǎn)，對(duì)路徑規(guī)劃的影響程度低且數(shù)量占比較大，將其定義為冗余采樣點(diǎn)。

設(shè)定一組實(shí)驗(yàn)，設(shè)定采樣點(diǎn)數(shù)量為100，在障礙物占比分別為0%、10%、20%、30%、40%、50%的地圖環(huán)境下，進(jìn)行路徑規(guī)劃，統(tǒng)計(jì)冗余采樣點(diǎn)的占比數(shù)據(jù)。如表1所示，隨著環(huán)境障礙物占比的增加，冗余采樣點(diǎn)的占比由74%降至54%，雖有小幅降低，但仍有大量冗余采樣點(diǎn)，這導(dǎo)致了大量的冗余探索。

為解決由于采樣點(diǎn)隨機(jī)生成所導(dǎo)致的冗余探索問題，APF-Dynamic FMT*算法設(shè)計(jì)了一種基于人工勢(shì)場(chǎng)法的采樣點(diǎn)引導(dǎo)函數(shù)SampleAPF（n）以調(diào)整采樣點(diǎn)的生成范圍，該函數(shù)可以根據(jù)環(huán)境信息動(dòng)態(tài)地調(diào)整采樣點(diǎn)生成范圍，適用于不同障礙物比例的情況，該函數(shù)返回一個(gè)具有q∈n（n為采樣點(diǎn)數(shù)量）個(gè)點(diǎn)的集合，具體實(shí)現(xiàn)細(xì)節(jié)如算法1所示，主要使用以下函數(shù)：

a）random（0，J（q））生成一個(gè)取值為（0，J（q））的隨機(jī)值，J（q）表示對(duì)采樣點(diǎn)q的限制勢(shì)力。

b）U（q）表示采樣點(diǎn)q的合力勢(shì)絕對(duì)值，用于判斷采樣點(diǎn)q是否滿足生成條件。

算法1 SampleAPF（n）

輸入：采樣點(diǎn)數(shù)量n。

輸出：一個(gè)有n個(gè)采樣點(diǎn)的集合Sample（n）。

1 N=n，m=0，Sample（n）←{}

2 for m≤N do

3 Generate a random sample point q

4 θ=random（0，J（q））

4 if U（q）≤θ then

5 Sample（n）←Sample（n）∪{q}

6 m+=1

7 end if

8 end for

9 return Sample（n）

SampleAPF（n）返回一個(gè)有n個(gè)采樣點(diǎn)的集合，首先根據(jù)目標(biāo)位置和障礙物位置，構(gòu)建一個(gè)勢(shì)能場(chǎng)，如圖4所示，勢(shì)能場(chǎng)將地圖范圍內(nèi)的起點(diǎn)與目標(biāo)視為引力極，障礙物視為斥力極。抽象定義引力極產(chǎn)生的引力勢(shì)為采樣點(diǎn)位置與引力極位置的距離相關(guān)函數(shù)；斥力極產(chǎn)生的斥力勢(shì)為采樣點(diǎn)位置與斥力極位置的距離相關(guān)函數(shù)。

假設(shè)地圖中新生成一個(gè)采樣點(diǎn)q，SampleAPF（n）將根據(jù)合力勢(shì)絕對(duì)值U（q）判斷該采樣點(diǎn)是否滿足生成條件，相關(guān)公式如式（1）所示。

4 仿真實(shí)驗(yàn)分析

4.1 采樣點(diǎn)分布對(duì)比

設(shè)定實(shí)驗(yàn)環(huán)境為30×50的矩形地圖如圖7所示，圖中灰色線條為地圖邊界，灰色矩形為障礙物，藍(lán)色點(diǎn)為起點(diǎn)，綠色點(diǎn)為目標(biāo)點(diǎn)，紅色小圓點(diǎn)為采樣點(diǎn)。相比于FMT*算法，在相同數(shù)量采樣點(diǎn)的情況下，APF-Dynamic FMT*算法所生成的采樣點(diǎn)大部分位于以起點(diǎn)與目標(biāo)點(diǎn)連線為長(zhǎng)軸的橢圓內(nèi)，且越靠近起點(diǎn)與目標(biāo)點(diǎn)的連線范圍內(nèi)采樣點(diǎn)越密集，而FMT*算法所生成的采樣點(diǎn)則隨機(jī)分布于整個(gè)地圖范圍。

由于FMT*算法在空間中隨機(jī)生成采樣點(diǎn)，導(dǎo)致大部分與目標(biāo)方向無關(guān)的冗余采樣點(diǎn)需要被探索，這占用了大量的計(jì)算資源。而APF-Dynamic FMT*算法生成的采樣點(diǎn)絕大部分分布在具有探索價(jià)值的范圍內(nèi)，較少生成與目標(biāo)方向無關(guān)的采樣點(diǎn)。如圖8所示，在相同數(shù)量采樣點(diǎn)的情況下，F(xiàn)MT*算法中有大量與目標(biāo)點(diǎn)方向無關(guān)的采樣點(diǎn)被探索，且有部分采樣點(diǎn)一直未被探索，這導(dǎo)致部分計(jì)算資源浪費(fèi)，影響了路徑規(guī)劃效率。而APF-Dynamic FMT*算法中大部分被探索的采樣點(diǎn)都具有一定的探索價(jià)值，并且APF-Dynamic FMT*算法進(jìn)行路徑規(guī)劃的過程中未被探索到的采樣點(diǎn)數(shù)量遠(yuǎn)少于FMT*算法，因此采用APF-Dynamic FMT*算法具有更高的采樣點(diǎn)利用率。

4.2 路徑規(guī)劃效果對(duì)比

以下是APF-Dynamic FMT*與FMT*算法在仿真實(shí)驗(yàn)中的路徑規(guī)劃效果對(duì)比分析。如圖9～11所示，兩種算法在采樣點(diǎn)數(shù)量同為100、200、300的情況下均能成功規(guī)劃一條可行路徑，但是FMT*所規(guī)劃出的路徑長(zhǎng)度過長(zhǎng)，且路徑不平滑，冗余拐點(diǎn)較多。相比于FMT*算法，APF-Dynamic FMT*算法所規(guī)劃出的路徑長(zhǎng)度明顯更短且路徑更加平滑，更加趨向于最優(yōu)路徑。

由于APF-Dynamic FMT*算法與FMT*算法基于采樣點(diǎn)探索的特性，采樣點(diǎn)分布的有效性影響了路徑規(guī)劃的成功率。如圖12所示，當(dāng)出現(xiàn)面積較大障礙物擋住采樣點(diǎn)之間的聯(lián)通路線時(shí)，由于采樣點(diǎn)分布不合理，可能會(huì)導(dǎo)致FMT*算法路徑規(guī)劃失敗，所以采樣點(diǎn)的分布會(huì)對(duì)路徑規(guī)劃的成功率有較大影響。

在環(huán)境一致的情況下，分別采用APF-Dynamic FMT*與FMT*、RRT、APF-IRRT*算法的路徑規(guī)劃成功率隨采樣點(diǎn)數(shù)量的變化曲線如圖13所示，可以得知在較少采樣點(diǎn)的情況下采用APF-Dynamic FMT*算法進(jìn)行路徑規(guī)劃的成功率明顯高于其余算法，且APF-Dynamic FMT*算法的路徑規(guī)劃成功率能夠更快地收斂于95%以上的高成功率并且保持穩(wěn)定，采用APF-Dynamic FMT*算法進(jìn)行路徑規(guī)劃有著更高的成功率，解決了FMT*算法在較少采樣點(diǎn)數(shù)量時(shí)路徑規(guī)劃成功率低的問題。

由于APF-Dynamic FMT*、FMT*、RRT與APF-IRRT*算法基于采樣點(diǎn)探索的特性，在相同空間內(nèi)，采樣點(diǎn)數(shù)量越多，所生成的路徑相對(duì)越短且越平滑，但相對(duì)而言所消耗的計(jì)算資源就越大，所以采樣點(diǎn)的數(shù)量設(shè)定并不是越多越好，而是需要隨著采樣點(diǎn)數(shù)量的增加更快地收斂于最優(yōu)路徑。APF-Dynamic FMT*與FMT*算法和RRT算法路徑規(guī)劃所得的路徑長(zhǎng)度隨采樣點(diǎn)數(shù)量的變化曲線，如圖14所示，隨著采樣點(diǎn)數(shù)量的遞增，F(xiàn)MT*算法規(guī)劃所得路徑長(zhǎng)度起伏較大，受采樣點(diǎn)數(shù)量影響較大，在采樣點(diǎn)數(shù)量達(dá)到400以上才逐漸收斂于最短路徑長(zhǎng)度且保持相對(duì)穩(wěn)定；由于采樣點(diǎn)數(shù)量不足，RRT算法規(guī)劃所得路徑長(zhǎng)度起伏較大，且未收斂于最優(yōu)路徑；APF-IRRT*算法相較于RRT算法有不錯(cuò)的提升，但收斂于最優(yōu)路徑的速度較為緩慢；APF-Dynamic FMT*算法規(guī)劃所得路徑長(zhǎng)度整體相對(duì)穩(wěn)定且更快地收斂于最短路徑長(zhǎng)度，受采樣點(diǎn)數(shù)量的影響較小，具有不錯(cuò)的穩(wěn)定性，相比于FMT*算法規(guī)劃所得路徑更為優(yōu)秀，解決了FMT*算法在較少采樣點(diǎn)數(shù)量時(shí)規(guī)劃所得路徑不夠優(yōu)秀的問題。

4.3 APF-Dynamic FMT*算法在動(dòng)態(tài)環(huán)境下路徑規(guī)劃效果

APF-Dynamic FMT*算法具有路徑樹動(dòng)態(tài)調(diào)整機(jī)制，環(huán)境發(fā)生變化時(shí)，算法會(huì)判斷當(dāng)前路徑是否被障礙物所阻擋。若有障礙物阻礙了當(dāng)前已規(guī)劃出的路徑時(shí)，路徑樹動(dòng)態(tài)調(diào)整機(jī)制會(huì)實(shí)時(shí)調(diào)整當(dāng)前的路徑樹，剔除掉被障礙物覆蓋的采樣點(diǎn)以及被障礙物阻擋的路徑樹，并在現(xiàn)存路徑樹的基礎(chǔ)上進(jìn)行路徑規(guī)劃。如圖15所示，在采樣點(diǎn)數(shù)量設(shè)定為300的情況下，初次進(jìn)行路徑規(guī)劃成功后，在地圖中連續(xù)三次添加圓形障礙物障礙物（如圖中灰色圓形）阻礙當(dāng)前路徑后，APF-Dynamic FMT*算法均能在未重新采樣的前提下規(guī)劃出一條可通行路徑，證明了該算法在動(dòng)態(tài)環(huán)境下的可用性。

為驗(yàn)證APF-Dynamic FMT*算法在動(dòng)態(tài)環(huán)境下重新規(guī)劃出新路徑的高效性，與文獻(xiàn)［15］提出的一種動(dòng)態(tài)RRT路徑規(guī)劃算法（replanning algorithm for rapidly-exploring random trees，replanning-RRT）進(jìn)行對(duì)比實(shí)驗(yàn)。replanning-RRT算法能刪除RRT算法在動(dòng)態(tài)環(huán)境中失效部分并保留其他部分，且在已生成的擴(kuò)張樹的基礎(chǔ)上繼續(xù)生長(zhǎng)，直到規(guī)劃出新的路徑。設(shè)定實(shí)驗(yàn)環(huán)境為動(dòng)態(tài)二維地圖環(huán)境，采樣點(diǎn)數(shù)量為500，在首次路徑規(guī)劃成功后，向地圖中逐次添加障礙物以阻擋現(xiàn)有路徑，記錄重新規(guī)劃出新路徑的平均時(shí)間。實(shí)驗(yàn)結(jié)果如圖16所示，隨著添加障礙物次數(shù)的增加，replanning-RRT算法的平均路徑規(guī)劃時(shí)間增幅較大，且沒有達(dá)到穩(wěn)定的趨勢(shì)，而APF-Dynamic FMT*算法的平均路徑規(guī)劃時(shí)間的增幅較小，且逐漸趨向穩(wěn)定，證明了其在動(dòng)態(tài)環(huán)境中的高效性。

5 結(jié)束語

為了解決FMT*算法在采樣點(diǎn)數(shù)量較少時(shí)路徑規(guī)劃效率低以及不適用于動(dòng)態(tài)路徑規(guī)劃等問題，本文提出一種融合人工勢(shì)場(chǎng)法的動(dòng)態(tài)快速行進(jìn)樹路徑規(guī)劃算法（APF-Dynamic FMT*）。APF-Dynamic FMT*設(shè)計(jì)了一種基于人工勢(shì)場(chǎng)法的采樣點(diǎn)引導(dǎo)函數(shù)SampleAPF（n），該函數(shù)可以根據(jù)環(huán)境信息動(dòng)態(tài)的調(diào)整采樣點(diǎn)生成范圍，適用于不同障礙物比例的情況，這減少了對(duì)空間的冗余探索，提高了采樣點(diǎn)的利用率。同時(shí)，APF-Dynamic FMT*算法設(shè)計(jì)了一種路徑樹動(dòng)態(tài)調(diào)整機(jī)制，監(jiān)測(cè)環(huán)境是否發(fā)生改變，當(dāng)環(huán)境發(fā)生改變時(shí)，算法會(huì)判斷當(dāng)前路徑是否被障礙物所阻擋。若有障礙物阻礙了當(dāng)前已規(guī)劃出的路徑時(shí)，算法會(huì)實(shí)時(shí)調(diào)整當(dāng)前的路徑樹，剔除掉被障礙物覆蓋的采樣點(diǎn)以及被障礙物阻擋的路徑樹，并在剩余路徑樹的基礎(chǔ)上進(jìn)行路徑規(guī)劃。仿真實(shí)驗(yàn)結(jié)果表明，APF-Dynamic FMT*算法在消耗相同計(jì)算資源的同時(shí)，顯著提高了路徑規(guī)劃的成功率與路徑質(zhì)量。在動(dòng)態(tài)環(huán)境中，能夠高效地再次規(guī)劃出可通行的優(yōu)秀路徑。

參考文獻(xiàn)：

［1］劉澳霄，周永錄，劉宏杰.基于改進(jìn)人工勢(shì)場(chǎng)法的醫(yī)療配送機(jī)器人路徑規(guī)劃［J］.計(jì)算機(jī)應(yīng)用研究，2024，41（3）：842-847.（Liu Aoxiao，Zhou Yonglu，Liu Hongjie.Path planning of medical delivery robot based on improved artificial potential field method［J］.Application Research of Computers，2024，41（3）：842-847.

［2］張艷菊，吳俊，程錦倩，等.多搬運(yùn)任務(wù)下考慮碰撞避免的AGV路徑規(guī)劃［J］.計(jì)算機(jī)應(yīng)用研究，2024，41（5）：1462-1469.（Zhang Yanju，Wu Jun，Cheng Jinqian，et al.AGV path planning considering collision avoidance of multiple handling tasks［J］.Application Research of Computers，2024，41（5）：1462-1469.

［3］Chen Jiagui，Zhao Yun，Xu Xing.Improved RRT-connect based path planning algorithm for mobile robots［J］.IEEE Access，2021，9：145988-145999.

［4］司徒華杰，雷海波，莊春剛.動(dòng)態(tài)環(huán)境下基于人工勢(shì)場(chǎng)引導(dǎo)的RRT路徑規(guī)劃算法［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（3）：714-717，724.（Situ Huajie，Lei Haibo，Zhuang Chungang.Artificial potential field based RRT algorithm for path planning in dynamic environment［J］.Application Research of Computers，2021，38（3）：714-717，724.）.

［5］Fareh R，Baziyad M，Rabie T，et al.Enhancing path quality of real-time path planning algorithms for mobile robots：a sequential linear paths approach［J］.IEEE Access，2020，8：167090-167104.

［6］Janson L，Pavone M.Fast marching trees：a fast marching sampling-based method for optimal motion planning in many dimensions-exten-ded version［EB/OL］.（2013-06-15）.https：//arxiv.org/abs/1306.3532.

［7］Fan Jiaming，Chen Xia，Liang Xiao.UAV trajectory planning based on bi-directional APF-RRT* algorithm with goal-biased［J］.Expert Systems with Applications，2023，213：119137.

［8］Li Qiongqiong，Xu Yiqi，Bu Shenqiang，et al.Smart vehicle path planning based on modified PRM algorithm［J］.Sensors，2022，22（17）：6581.

［9］Xu Jing，Song Kechen，Zhang Defu，et al.Informed anytime fast ma-rching tree for asymptotically optimal motion planning［J］.IEEE Trans on Industrial Electronics，2020，68（6）：5068-5077.

［10］Starek J A，Gomez J V，Schmerling E，et al.An asymptotically-optimal sampling-based algorithm for bi-directional motion planning［C］//Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems.Piscataway，NJ：IEEE Press，2015：2072-2078.

［11］Gao Wenxiang，Tang Qing，Yao Jin，et al.Heuristic bidirectional fast marching tree for optimal motion planning［C］//Proc of the 3rd Asia-Pacific Conference on Intelligent Robot Systems.Piscataway，NJ：IEEE Press，2018：71-77.

［12］Wu Daohua，Wei Lisheng，Wang Guanling，et al.APF-IRRT*：an improved informed rapidly-exploring random trees-star algorithm by introducing artificial potential field method for mobile robot path planning［J］.Applied Sciences，2022，12（21）：10905-10905.

［13］Janson L，Schmerling E，Clark A，et al.Fast marching tree：a fast marching sampling-based method for optimal motion planning in many dimensions［J］.The International journal of robotics research，2015，34（7）：883-921.

［14］Wang Kuan，Xu Jing，Song Kechen，et al.Informed anytime bi-directional fast marching tree for optimal motion planning in complex cluttered environments［J］.Expert Systems with Applications，2023，215：119263.

［15］Ferguson D，Kalra N，Stentz A.Replanning with RRTs［C］//Proc of IEEE International Conference on Robotics and Automation.Pisc-ataway，NJ：IEEE Press，2006：1243-1248.

收稿日期：2024-01-06

修回日期：2024-03-08

基金項(xiàng)目：國(guó)家自然科學(xué)基金面上項(xiàng)目（61471306）；四川省自然科學(xué)基金資助項(xiàng)目（2022NSFSC0548）；四川省重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2020YFS0360）；四川省教育廳教改資助項(xiàng)目（JG2021-1414）

作者簡(jiǎn)介：吳旭鵬（1999—），男，四川眉山人，碩士，CCF會(huì)員，主要研究方向?yàn)橐苿?dòng)物聯(lián)網(wǎng)技術(shù)、移動(dòng)機(jī)器人導(dǎo)航技術(shù)；賈小林（1975—），男（通信作者），四川南江人，教授，博導(dǎo)，博士，CCF高級(jí)會(huì)員，主要研究方向?yàn)樯漕l識(shí)別（RFID）技術(shù)、物聯(lián)網(wǎng)（IoT）技術(shù)、計(jì)算機(jī)應(yīng)用系統(tǒng)（my_jiaxl@163.com）；顧婭軍（1979—），女，四川綿陽人，講師，碩士，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)、物聯(lián)網(wǎng)（IoT）技術(shù).