基于動(dòng)態(tài)三角網(wǎng)格和啟發(fā)式搜索算法路徑規(guī)劃研究

1、 基于動(dòng)態(tài)三角網(wǎng)格和啟發(fā)式搜索算法路徑規(guī)劃研究 王文霞摘 要： 在靜態(tài)三角網(wǎng)絡(luò)的基礎(chǔ)上設(shè)計(jì)實(shí)現(xiàn)了動(dòng)態(tài)三角網(wǎng)絡(luò)地圖算法，通過(guò)改變?nèi)蔷W(wǎng)格地圖障礙物變化過(guò)程中的網(wǎng)格節(jié)點(diǎn)代價(jià)值，設(shè)計(jì)相關(guān)算法模塊并對(duì)新生成的網(wǎng)格地圖實(shí)時(shí)獲取更新信息，實(shí)現(xiàn)動(dòng)態(tài)變化效果。結(jié)合搜索算法Anytime Replanning A*（ARA*）和D* Lite，實(shí)現(xiàn)在動(dòng)態(tài)環(huán)境中的路徑規(guī)劃方法Anytime Dynamic A*（AD*），通過(guò)對(duì)網(wǎng)格地圖中已擴(kuò)展信息的保存和在有限時(shí)間內(nèi)不斷縮小膨脹因子，找到網(wǎng)格地圖中代價(jià)值最小的節(jié)點(diǎn)，動(dòng)態(tài)規(guī)劃得到最優(yōu)路徑。在動(dòng)態(tài)環(huán)境中，通過(guò)模擬動(dòng)態(tài)場(chǎng)景圖，并應(yīng)用動(dòng)態(tài)規(guī)劃方法建立相應(yīng)的數(shù)據(jù)搜索結(jié)構(gòu)和

2、方法，對(duì)仿真效果進(jìn)行分析和對(duì)比。Key： 動(dòng)態(tài)三角網(wǎng)格； AD*算法； 路徑規(guī)劃； 模擬仿真： TN911.1?34； TM417 ： A ： 1004?373X（2017）11?0103?04Research on path planning based on dynamic triangular meshand heuristic search algorithmWANG Wenxia（Department of Computer Science and Technology， Yuncheng University， Yuncheng 044000， China）Abstract： Th

3、e dynamic triangular network map algorithm was designed and implemented on the basis of static triangular mesh to change the grid node cost value in the obstacle changing process of the triangular mesh map. The related algorithm was designed to acquire the updata information of the generated grid ma

4、p in real time to realize the dynamic change effect. The search algorithm Anytime Replanning A*（ARA*） and D* Lite are combined to realize the path planning method A*（AD*） in dynamic environmet. The extended information in grid map is saved， and the expansion factor is reduced constantly in the finit

5、e time to find the node with minimum cost value in the grid map， and obtain the optimul path of dynamic planning. The dynamic scene graph is simulated in dynamic environment. The dynamic planning method is used to establish the corresponding data search structure and method to analyze and contrast t

6、he simulation results.Keywords： dynamic triangular mesh； AD* algorithm； path planning； analog simulation隨著社會(huì)經(jīng)濟(jì)的發(fā)展，找到合適、優(yōu)化而且適用于各種額外條件如動(dòng)態(tài)環(huán)境、大規(guī)模人群、任意寬度路徑等一系列需求成為路徑規(guī)劃算法的研究方向1。本文研究在動(dòng)態(tài)地圖網(wǎng)格中通過(guò)動(dòng)態(tài)搜索算法，實(shí)時(shí)更新地圖信息的同時(shí)采用更加高效的搜索算法記錄當(dāng)前群體信息并反饋出動(dòng)態(tài)環(huán)境中的環(huán)境變化情況，如人群規(guī)模、路徑寬度等相關(guān)信息，以便在較短時(shí)間內(nèi)避免碰撞和到達(dá)目的地。1 動(dòng)態(tài)環(huán)境地圖網(wǎng)格構(gòu)建及生成1.1 動(dòng)態(tài)三角網(wǎng)格設(shè)

7、計(jì)實(shí)現(xiàn)在構(gòu)建動(dòng)態(tài)網(wǎng)格（Dynamic Local Clearance Triangulation，DLCT）2的過(guò)程中需要保持原有的LCT三角網(wǎng)格3中對(duì)路徑寬度的要求，在動(dòng)態(tài)化的過(guò)程中添加和刪除障礙物時(shí)通過(guò)多邊形障礙物ID進(jìn)行操作，在添加算法中把所有障礙物的限制條件遍歷直至找到需要添加障礙物的ID；在之后的刪除算法中會(huì)把與找到的障礙物ID相關(guān)的限制條件同時(shí)刪除。由于在地圖中障礙物之間可以相互覆蓋，因此每個(gè)ID可能關(guān)聯(lián)相互覆蓋的限制條件。1.1.1 障礙物插入模塊該模塊在原有LCT（S）的存儲(chǔ)單元中插入新的多邊形障礙物，在插入過(guò)程中，給障礙物設(shè)置新的ID。S設(shè)置為現(xiàn)在LCT（S）已存在的限制規(guī)劃

8、，O是將插入的新多邊形障礙物。插入過(guò)程如下：（1） 將多邊形障礙物O中的k條線段插入CDT中，對(duì)于需要修改的頂點(diǎn)和限制邊界分別存儲(chǔ)在兩個(gè)List中。List V中存儲(chǔ)所有已修改邊的鄰接頂點(diǎn)（其中包括因CDT交換的邊）；List C中存儲(chǔ)在插入障礙物過(guò)程中受限制的邊界。（2） 對(duì)于List C中的限制邊界，通過(guò)搜索算法判斷S是否被阻塞。對(duì)于每個(gè)被阻塞的遍歷找到后，相關(guān)聯(lián)頂點(diǎn)加入List V。如圖1所示，通過(guò)搜索加入頂點(diǎn)兩邊可能因S引起阻隔。對(duì)每次遍歷來(lái)說(shuō)，相關(guān)聯(lián)的阻隔頂點(diǎn)v被加入到List V中。圖1 尋找被阻斷過(guò)程（3） 在遍歷過(guò)程所有被List V中頂點(diǎn)影響的頂點(diǎn)將重新測(cè)試其屬性，判斷在當(dāng)前

9、情況是否需要被限制， Local_Ref函數(shù)定義和遍歷了在變化過(guò)程中與V相鄰的頂點(diǎn)。對(duì)于每一個(gè)所有與相鄰的三角形都要被訪問(wèn)。設(shè)為當(dāng)前與臨近被訪問(wèn)的三角形，此時(shí)需要調(diào)用函數(shù)檢測(cè)是否有遍歷過(guò)的節(jié)點(diǎn)需要重新定義；函數(shù)查看的后繼節(jié)點(diǎn)是否被影響，當(dāng)找到被影響的路徑時(shí)，頂點(diǎn)和若不在List V中則系統(tǒng)自動(dòng)進(jìn)行添加，然后重新測(cè)試所有在V中的頂點(diǎn)。1.1.2 障礙物刪除模塊該模塊將把現(xiàn)有地圖中的多邊形障礙物移除，移除過(guò)程中通過(guò)在插入中設(shè)置的ID找到該障礙物。由于障礙物之間可以發(fā)生覆蓋，故對(duì)于每一個(gè)障礙物來(lái)說(shuō)可能同時(shí)具有多個(gè)ID。刪除過(guò)程如下：（1） 將已存儲(chǔ)的障礙物O從CDT中刪除，并把所有已修改與邊相關(guān)的頂

10、點(diǎn)信息存儲(chǔ)在List V1中；（2） 將與List V1被限制頂點(diǎn)的周圍臨近頂點(diǎn)找到后存入List V2；（3） 把List V1中相關(guān)的頂點(diǎn)信息從CDT中刪除；（4） 對(duì)于所有在執(zhí)行過(guò)程中需要限制的頂點(diǎn)，通過(guò)調(diào)用Local_Ref函數(shù)再次遍歷與其臨近的頂點(diǎn)信息，并對(duì)發(fā)生變化的進(jìn)行改變。1.1.3 動(dòng)態(tài)三角網(wǎng)格構(gòu)建過(guò)程基于動(dòng)態(tài)三角網(wǎng)格地圖的動(dòng)態(tài)環(huán)境構(gòu)建步驟如下：（1） 獲取三角網(wǎng)格發(fā)生變化后的地圖信息。（2） 獲取地圖中障礙物變化信息。（3） 地圖網(wǎng)格中障礙物節(jié)點(diǎn)信息發(fā)生改變時(shí)，若有新節(jié)點(diǎn)加入，則添加后更新相鄰節(jié)點(diǎn)；若有節(jié)點(diǎn)刪除，則刪除后更新相鄰節(jié)點(diǎn)信息。（4） 反復(fù)執(zhí)行步驟（3），直至所有的

11、更新信息都處理完畢。（5） 更新地圖中三角網(wǎng)格節(jié)點(diǎn)信息。1.2 動(dòng)態(tài)地圖構(gòu)建實(shí)現(xiàn)動(dòng)態(tài)三角網(wǎng)格地圖構(gòu)建過(guò)程如圖2所示，其中第一幅圖展示了在原始地圖中通過(guò)添加障礙物實(shí)現(xiàn)了地圖中存在若干個(gè)障礙物的情況，然后通過(guò)改變地圖網(wǎng)格中障礙物的個(gè)數(shù)、重新劃分三角網(wǎng)格以及移動(dòng)障礙物和刪除算法等方法，實(shí)現(xiàn)了仿真過(guò)程中對(duì)真實(shí)地圖情況的模擬和地圖網(wǎng)格的構(gòu)建過(guò)程。圖2 動(dòng)態(tài)地圖實(shí)現(xiàn)效果2 啟發(fā)式搜索動(dòng)態(tài)路徑規(guī)劃方法2.1 啟發(fā)式動(dòng)態(tài)路徑規(guī)劃方法（AD*）Anytime Dynamic A*（AD*）算法是在原有的動(dòng)態(tài)環(huán)境下將D* Lite和ARA*結(jié)合，解決了在動(dòng)態(tài)環(huán)境下高效率的路徑規(guī)劃問(wèn)題4。在AD*算法中利用ARA*

12、中膨脹因子不斷遞減的過(guò)程進(jìn)行一系列路徑搜索。當(dāng)三角網(wǎng)格地圖環(huán)境發(fā)生改變并影響到邊的代價(jià)值時(shí)，在D*算法的OPEN表中對(duì)應(yīng)節(jié)點(diǎn)的Key值發(fā)生相應(yīng)改變。AD*算法具體執(zhí)行過(guò)程如下：（1） 程序初始化。將OPEN，CLOSED和INCONS表清空，膨脹因子初始值為（2） 計(jì)算最短路徑。計(jì)算最短路徑的過(guò)程中節(jié)點(diǎn)的擴(kuò)展順序?yàn)閺哪繕?biāo)點(diǎn)goal到起始點(diǎn)start進(jìn)行擴(kuò)展，尋找出從源點(diǎn)到目標(biāo)點(diǎn)的最短路徑。（3） 個(gè)體從start開(kāi)始沿路徑向goal前進(jìn)。（4） 在擴(kuò)展過(guò)程中，將已擴(kuò)展過(guò)的節(jié)點(diǎn)存儲(chǔ)在INCONS表中。（5） 判斷前進(jìn)過(guò)程中網(wǎng)格代價(jià)值是否發(fā)生變化，如果發(fā)生變化，則以當(dāng)前節(jié)點(diǎn)為新的起始點(diǎn)，并減小膨脹

13、因子的值。（6） 在下一次擴(kuò)展過(guò)程中，用作為啟發(fā)函數(shù)，在擴(kuò)展OPEN表中剩余的點(diǎn)之前，把上一輪INCONS表中的點(diǎn)插入OPEN表中，在原來(lái)OPEN表的基礎(chǔ)上修改所有與變化節(jié)點(diǎn)相關(guān)的rhs，key的值，清空CLOSE表。（7） 以新的start點(diǎn)為起始點(diǎn)，goal為目標(biāo)點(diǎn)，運(yùn)行步驟（3）直至到達(dá)目標(biāo)點(diǎn)。2.2 地圖網(wǎng)格密度計(jì)算基于三角網(wǎng)格密度的改進(jìn)方法5，模擬人群仿真的過(guò)程在不同時(shí)間內(nèi)每個(gè)三角網(wǎng)格參數(shù)值因agents數(shù)量的不同而發(fā)生變化，因此把密度信息添加到Key值的計(jì)算中，可以估算每一個(gè)OPEN表中節(jié)點(diǎn)的優(yōu)先權(quán)從而得到最優(yōu)路徑。density（n）表示第個(gè)節(jié)點(diǎn)所在三角網(wǎng)格的密度值；是通過(guò)節(jié)點(diǎn)和

14、距離信息來(lái)估算到目標(biāo)點(diǎn)的路徑長(zhǎng)度6。此時(shí)OPEN中擴(kuò)展節(jié)點(diǎn)的優(yōu)先權(quán)的計(jì)算公式如下：（1）式中：膨脹因子要滿足條件將agents標(biāo)記在不同三角形網(wǎng)格中，通過(guò)計(jì)算當(dāng)前三角網(wǎng)格的密度信息決定不同節(jié)點(diǎn)在OPEN表中的優(yōu)先權(quán)，此時(shí)Key的值計(jì)算公式（2）如下所示：（2）通過(guò)不斷減小在搜索路徑過(guò)程中膨脹因子的值找到最優(yōu)路徑。3 動(dòng)態(tài)路徑規(guī)劃算法設(shè)計(jì)與實(shí)現(xiàn)3.1 搜索節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)在動(dòng)態(tài)環(huán)境中，以DLCT三角網(wǎng)格7作為地圖的劃分方法，將地圖網(wǎng)格中的動(dòng)態(tài)變化信息和移動(dòng)個(gè)體動(dòng)態(tài)搜索路徑方法相關(guān)聯(lián)，構(gòu)造如下數(shù)據(jù)結(jié)構(gòu)，在Map_Node中存儲(chǔ)動(dòng)態(tài)網(wǎng)格中障礙物發(fā)生變化后節(jié)點(diǎn)的構(gòu)建網(wǎng)格信息；Agent_Node中記錄移動(dòng)

15、個(gè)體在尋路過(guò)程所擴(kuò)展的三角網(wǎng)格邊。規(guī)劃路徑時(shí)根據(jù)當(dāng)前Open_Node節(jié)點(diǎn)中存放的信息計(jì)算最優(yōu)路徑。3.2 動(dòng)態(tài)搜索算法實(shí)現(xiàn)在動(dòng)態(tài)搜索算法中，當(dāng)動(dòng)態(tài)環(huán)境發(fā)生變化時(shí)更新三角網(wǎng)格地圖信息，通過(guò)在OPEN表中擴(kuò)展邊，更新變化的頂點(diǎn)信息與其鄰接節(jié)點(diǎn)，判斷當(dāng)前移動(dòng)個(gè)體路徑是否受到影響，未受影響的個(gè)體按原路徑移動(dòng)；由于網(wǎng)格變化需要重新尋路時(shí)，計(jì)算節(jié)點(diǎn)代價(jià)值如下所示：（3）通過(guò)計(jì)算新添加節(jié)點(diǎn)（添加障礙物）或位置變更節(jié)點(diǎn)（移動(dòng)障礙物）的代價(jià)值得到當(dāng)前三角網(wǎng)格地圖的節(jié)點(diǎn)序列，在OPEN中節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)根據(jù)代價(jià)值的排序重新規(guī)劃路徑，通過(guò)執(zhí)行RecomputeShortestPath（）得到從當(dāng)前位置為起始點(diǎn)到目標(biāo)

16、點(diǎn)的路徑規(guī)劃方法8。例如，個(gè)體Agent移動(dòng)到節(jié)點(diǎn)所連接的邊edge時(shí)，移動(dòng)障礙物模塊至三角網(wǎng)格edge邊移動(dòng)方向的前方，此時(shí)動(dòng)態(tài)規(guī)劃域與個(gè)體移動(dòng)域有交集，在此區(qū)域里由于頂點(diǎn)變化三角網(wǎng)格地圖重新劃分，若劃分后節(jié)點(diǎn)不存在，通過(guò)不斷執(zhí)行Pred（s）找到前驅(qū)節(jié)點(diǎn)至此節(jié)點(diǎn)在更新后的網(wǎng)格地圖中存在，同理，后繼節(jié)點(diǎn)通過(guò)執(zhí)行Succ（s）不斷向后查找直至找到的后繼節(jié)點(diǎn)與新生成的網(wǎng)格地圖中匹配的節(jié)點(diǎn)（未找到則重新規(guī)劃此區(qū)域的路徑），在前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)之間的區(qū)域D中根據(jù)式（3）計(jì)算得到網(wǎng)格地圖變化后Agent個(gè)體從當(dāng)前位置到目標(biāo)點(diǎn)移動(dòng)的規(guī)劃路徑。 4 基于動(dòng)態(tài)環(huán)境的動(dòng)態(tài)規(guī)劃仿真與實(shí)現(xiàn)4.1 地圖規(guī)模變化策略

17、為了驗(yàn)證動(dòng)態(tài)搜索算法在不同規(guī)模三角網(wǎng)格地圖上的適用性和模擬仿真場(chǎng)景中復(fù)雜逼真程度，同時(shí)證明DLCT網(wǎng)格劃分方法對(duì)不同地圖的劃分結(jié)果的差異。本實(shí)驗(yàn)應(yīng)用動(dòng)態(tài)搜索算法AD*實(shí)現(xiàn)在不同規(guī)模地圖上個(gè)體規(guī)劃路徑過(guò)程。如圖3所示，圖中地圖網(wǎng)格的復(fù)雜程度由簡(jiǎn)到繁分別采用55，1010，2020，4040的網(wǎng)格拓?fù)浣Y(jié)構(gòu)，通過(guò)不斷增大迷宮場(chǎng)景圖的復(fù)雜程度，在地圖中選擇起始點(diǎn)和目標(biāo)點(diǎn)后通過(guò)啟發(fā)式動(dòng)態(tài)路徑搜索算法，AD*在不斷變化的三角網(wǎng)格中進(jìn)行路徑規(guī)劃，最終找到當(dāng)前狀態(tài)下的最優(yōu)路徑。通過(guò)采用不同規(guī)模地圖對(duì)單一移動(dòng)個(gè)體規(guī)劃路徑，不同的搜索算法尋路過(guò)程與地圖的復(fù)雜程度正相關(guān)，隨著地圖復(fù)雜程度的增加，搜索路徑的過(guò)程在地圖

18、網(wǎng)格中與擴(kuò)展的三角邊總數(shù)呈正相關(guān)的趨勢(shì)增長(zhǎng)。因此，在復(fù)雜多變的環(huán)境中模擬真實(shí)場(chǎng)景時(shí)，采用高效的地圖網(wǎng)格剖分方法能夠使路徑規(guī)劃效率得到提高。4.2 群體移動(dòng)策略4.2.1 碰撞檢測(cè)方法采用的規(guī)避方法是隨機(jī)處理方式和球體處理方法相結(jié)合，在Agents碰撞發(fā)生后進(jìn)行處理，設(shè)置兩個(gè)移動(dòng)個(gè)體之間距離的最小值，若小于最小值時(shí)則認(rèn)為碰撞發(fā)生。在碰撞發(fā)生后，若個(gè)體所在三角網(wǎng)格密度信息較大，則重新規(guī)劃路徑進(jìn)行移動(dòng)直至目標(biāo)點(diǎn)；若個(gè)體所在三角網(wǎng)格在密度范圍內(nèi)則個(gè)體延時(shí)等待一段時(shí)間后，通過(guò)避讓的方法繞過(guò)障礙物繼續(xù)前行到達(dá)目標(biāo)點(diǎn)。4.2.2 個(gè)體規(guī)避策略方法實(shí)現(xiàn)在動(dòng)態(tài)三角網(wǎng)格地圖環(huán)境中，當(dāng)障礙物發(fā)生移動(dòng)時(shí)，移動(dòng)個(gè)體會(huì)根

19、據(jù)當(dāng)前規(guī)劃路徑是否受到影響決定移動(dòng)策略，根據(jù)對(duì)方向進(jìn)行判斷，若在移動(dòng)過(guò)程中碰撞發(fā)生，記錄當(dāng)前位置信息CurPosition，判斷當(dāng)前三角網(wǎng)格密度值density，在密度滿足閾值條件時(shí)應(yīng)用規(guī)避方法重新規(guī)劃路徑繼續(xù)移動(dòng)；其他情況下，需改變移動(dòng)方向，密度滿足要求時(shí)進(jìn)行重新規(guī)劃。模擬仿真過(guò)程截圖如圖4圖7所示，在圖4和圖5中，障礙物的移動(dòng)沒(méi)有對(duì)個(gè)體移動(dòng)的路徑產(chǎn)生影響，仍按照原規(guī)劃路徑前行；在圖6中，當(dāng)動(dòng)態(tài)地圖網(wǎng)格中障礙物變化導(dǎo)致網(wǎng)格布局發(fā)生改變，從而對(duì)個(gè)體原路徑產(chǎn)生影響時(shí)，個(gè)體重新規(guī)劃路徑；在圖7中，當(dāng)?shù)貓D網(wǎng)格發(fā)生動(dòng)態(tài)改變時(shí)，若同時(shí)存在的若干移動(dòng)個(gè)體發(fā)生碰撞，此時(shí)應(yīng)用個(gè)體移動(dòng)的規(guī)避策略對(duì)路徑進(jìn)行重新規(guī)

20、劃。4.3 群體動(dòng)態(tài)路徑規(guī)劃方法4.3.1 群體動(dòng)態(tài)路徑方法群體路徑規(guī)劃方法是在單獨(dú)個(gè)體基礎(chǔ)上對(duì)每個(gè)移動(dòng)物體進(jìn)行路徑規(guī)劃的過(guò)程。為了模擬大規(guī)模人群仿真技術(shù)提出群行為模擬方法，移動(dòng)個(gè)體對(duì)不同的Agent的影響有很大差異，主要問(wèn)題有如下幾個(gè)方面：（1） 如在此移動(dòng)個(gè)體之前有另一個(gè)體相向而行，則其中一個(gè)物體應(yīng)該改變速度方向避免碰撞發(fā)生。（2） 若兩個(gè)移動(dòng)個(gè)體同向時(shí)，其中較慢的個(gè)體應(yīng)在人群密度較小的情況下改變速度方向超過(guò)前方遮擋個(gè)體；而在人群密度較大時(shí)，跟在前方物體之后行走。綜合以上問(wèn)題描述，本文通過(guò)碰撞類型分類對(duì)優(yōu)先級(jí)進(jìn)行劃分。按照優(yōu)先級(jí)原則對(duì)仿真環(huán)境中的Agents個(gè)體進(jìn)行優(yōu)先級(jí)排序（模擬真實(shí)場(chǎng)景

21、中的出場(chǎng)順序或根據(jù)重要程度排序等），根據(jù)優(yōu)先級(jí)遞減劃分成不同的組別，對(duì)于中的每個(gè)Agent個(gè)體，保存其start，goal，position，DesSpeed，velDir變量信息。在規(guī)劃群體路徑過(guò)程中，根據(jù)Agents的優(yōu)先級(jí)大小對(duì)速度方向進(jìn)行修改，若在中Agents和中的移動(dòng)個(gè)體移動(dòng)方向相同則需要在判斷優(yōu)先級(jí)的條件下重新規(guī)劃其余組別的路徑方向。在采用以上方法避免碰撞發(fā)生的條件下，若碰撞發(fā)生，記錄當(dāng)前碰撞發(fā)生時(shí)移動(dòng)個(gè)體的位置信息position，計(jì)算當(dāng)前三角網(wǎng)格的密度density和相鄰節(jié)點(diǎn)構(gòu)造網(wǎng)格密度值，根據(jù)Agents的優(yōu)先級(jí)以及已得到的密度信息進(jìn)行重新排序，若此時(shí)的移動(dòng)個(gè)體滿足優(yōu)先級(jí)條

22、件，則重新計(jì)算地圖網(wǎng)格的代價(jià)值并重新規(guī)劃由當(dāng)前位置position到目標(biāo)點(diǎn)的路徑；若此時(shí)碰撞個(gè)體優(yōu)先級(jí)較低，則處于等待狀態(tài)至下一次重新規(guī)劃。4.3.2 群體規(guī)劃路徑實(shí)現(xiàn)為了驗(yàn)證本文的群體動(dòng)態(tài)路徑規(guī)劃方法，對(duì)在地圖網(wǎng)格中可能發(fā)生碰撞的Agents個(gè)體采用碰撞規(guī)避策略對(duì)每個(gè)Agents個(gè)體進(jìn)行路徑規(guī)劃，在仿真的過(guò)程中不斷增加Agents規(guī)模，分別對(duì)Agents=50，Agents=100，Agents=150，Agents=200在不同時(shí)刻的尋路情況仿真模擬，實(shí)現(xiàn)結(jié)果截圖如圖8所示，圖中不同顏色的小方格分別代表不同的Agents移動(dòng)個(gè)體，每個(gè)移動(dòng)個(gè)體從初始點(diǎn)出發(fā)到目標(biāo)點(diǎn)規(guī)劃出各自的路徑，當(dāng)有Agents個(gè)體之間發(fā)生相互碰撞時(shí)（此時(shí)原規(guī)劃路徑移動(dòng)方向被阻擋），則Agent個(gè)體根據(jù)本文中采用的碰撞規(guī)避原則，采用AD*算法繞過(guò)對(duì)方后重新規(guī)劃路徑。圖8 群體規(guī)劃路徑實(shí)現(xiàn)由仿真效果可知，隨著網(wǎng)格地圖中Agents個(gè)體數(shù)的不斷增加，發(fā)生碰撞的幾率明顯增大，因此在動(dòng)態(tài)環(huán)境中，在采用高效的動(dòng)態(tài)路徑搜索算法的同時(shí)，需要針對(duì)群體中發(fā)生碰撞的規(guī)避策略來(lái)避免碰撞發(fā)生。4.4 仿真實(shí)驗(yàn)結(jié)果分析通過(guò)對(duì)動(dòng)態(tài)環(huán)境中的動(dòng)態(tài)網(wǎng)格效果、動(dòng)態(tài)路徑規(guī)劃算法進(jìn)行驗(yàn)證，將二者結(jié)合實(shí)現(xiàn)本文關(guān)于動(dòng)態(tài)環(huán)境中的路徑規(guī)劃方法的研究。在動(dòng)態(tài)網(wǎng)格地圖中分別移動(dòng)和增添障礙物后，實(shí)現(xiàn)了地圖網(wǎng)格發(fā)生變化情況的模擬。在動(dòng)態(tài)