无人机路径规划_路径规划遗传算法

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/629db795a1ab4536ad06fc57/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/629db795a1ab4536ad06fc57/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x1 h3 y2 ff1 fs1 fc0 sc0 ls0 ws0"></div><div class="t m0 x1 h4 y3 ff2 fs2 fc0 sc0 ls0 ws0">复杂城市环境下无人机三维路径规划</div><div class="t m0 x2 h5 y4 ff2 fs1 fc0 sc0 ls0 ws0">①</div><div class="t m0 x1 h6 y5 ff3 fs3 fc0 sc0 ls0 ws0">卢成阳<span class="ff1">,</span>王文格</div><div class="t m0 x1 h7 y6 ff1 fs4 fc0 sc0 ls0 ws0">(<span class="ff3">湖南大学</span><span class="ff3">机械与运载工程学院</span>,<span class="ff3">长沙</span>410082)</div><div class="t m0 x1 h7 y7 ff3 fs4 fc0 sc0 ls0 ws0">通信作者<span class="ff1">:</span>卢成阳<span class="ff1">,E-mail:lcy_xmj@163.com</span></div><div class="t m0 x1 h3 y8 ff2 fs1 fc0 sc0 ls1 ws0">摘　要<span class="ff1">:<span class="ff3">基于转移的快速扩展随机<span class="ls2">树</span></span>(T-RRT<span class="ls2">)</span><span class="ff3">算法</span>,<span class="ff3">能够较快寻找到机器人在二维复杂成本空间的低危险度路径</span>,</span></div><div class="t m0 x1 h3 y9 ff3 fs1 fc0 sc0 ls3 ws0">但面对无人机的三维飞行工况<span class="ff1">,</span>其规划结果较差<span class="ff1">,</span>针对此问题<span class="ff1">,</span>提出了一种基于探索、启发和转移<span class="ls4">的</span><span class="ff1">EHT-RRT</span></div><div class="t m0 x1 h3 ya ff1 fs1 fc0 sc0 ls5 ws0">(exploringheuristictransition-basedRRT<span class="ls6">)</span><span class="ff3">算法</span>.<span class="ff3">首先</span>,<span class="ff3">算法<span class="ls6">在</span></span>T-RR<span class="ls6">T</span><span class="ff3">的基础上引<span class="ls6">入</span></span>A*<span class="ff3">算法中的启发式思想</span>,<span class="ff3">进行启</span></div><div class="t m0 x1 h3 yb ff3 fs1 fc0 sc0 ls7 ws0">发式成本探索<span class="ff1">,</span>从危险度、路径长度、路径偏转角度和高度变化估计路径成本<span class="ff1">,</span>以提高路径质量<span class="ff1">;</span>接着<span class="ff1">,</span>利用局部节</div><div class="t m0 x1 h3 yc ff3 fs1 fc0 sc0 ls7 ws0">点滑移策略<span class="ff1">,</span>让路径偏向低危险区域<span class="ff1">,</span>并对每个节点添加局部最好方向属性<span class="ff1">;</span>最后<span class="ff1">,</span>通过随机方向、目标方向和局部</div><div class="t m0 x1 h3 yd ff3 fs1 fc0 sc0 ls8 ws0">最好方向<span class="ff1">,<span class="ls9">3</span></span>个方向向量改进树节点扩展机制<span class="ff1">,</span>摆<span class="ls9">脱</span><span class="ff1">T-RR<span class="ls9">T</span></span>算法在路径寻找上的盲目性<span class="ff1">.</span>同时<span class="ff1">,</span>算法采用<span class="ls9">了</span><span class="ff1">20<span class="ls9">%</span></span>概</div><div class="t m0 x1 h3 ye ff3 fs1 fc0 sc0 lsa ws0">率的目标点偏置<span class="ff1">,</span>提升规划效率<span class="ff1">.</span>仿真实验表明<span class="ff1">,</span>与同样添<span class="lsb">加</span><span class="ff1">20<span class="lsb">%</span></span>目标点偏置<span class="lsb">的</span><span class="ff1">T-RRT</span>、<span class="ff1">BT-RR<span class="lsb">T<span class="ff3">和</span></span>T-RRT*</span></div><div class="t m0 x1 h3 yf ff3 fs1 fc0 sc0 lsc ws0">算法相比<span class="ff1">,EHT-RR<span class="lsd">T</span></span>算法可生成路径更短、安全性更高、更加平滑的三维路径<span class="ff1">,</span>能更好地解决复杂城市环境下的</div><div class="t m0 x1 h3 y10 ff3 fs1 fc0 sc0 ls0 ws0">无人机三维路径规划问题<span class="ff1">.</span></div><div class="t m0 x1 h3 y11 ff2 fs1 fc0 sc0 ls0 ws0">关键词<span class="ff1">:<span class="ff3">旋翼无人机</span>;<span class="ff3">复杂成本空间</span>;<span class="ff3">三维路径规划</span>;EHT-RRT;T-RRT</span></div><div class="t m0 x1 h8 y12 ff3 fs5 fc0 sc0 lse ws0">引用格式<span class="ff1">:</span>卢成阳<span class="ff1">,</span>王文格<span class="ff1">.</span>复杂城市环境下无人机三维路径规划<span class="ff1">.</span>计算机系统应用<span class="ff1">,2022,31(5):184–194.<span class="fc1">http://www.c-s-a.org.cn/1003-</span></span></div><div class="t m0 x1 h8 y13 ff1 fs5 fc1 sc0 ls0 ws0">3254/8514.html</div><div class="t m0 x1 h9 y14 ff4 fs3 fc0 sc0 ls0 ws0">3D Path Planning of UAV in Complex Urban Environment</div><div class="t m0 x1 h3 y15 ff1 fs1 fc0 sc0 ls0 ws0">LUCheng-Yang,WANGWen-Ge</div><div class="t m0 x1 h7 y16 ff1 fs4 fc0 sc0 ls0 ws0">(CollegeofMechanicalandVehicleEngineering,HunanUniversity,Changsha410082,China)</div><div class="t m0 x1 h3 y17 ff4 fs1 fc0 sc0 lsf ws0">Abstract<span class="ff1">:Atransition-basedrapidly-exploringrandomtree(T-RRT)algorithmcanquicklyfindalow-riskpathfora</span></div><div class="t m0 x1 h3 y18 ff1 fs1 fc0 sc0 ls10 ws0">robotinatwo-dimensionalcomplexcostspace,butitdeliversapoorplanningresultforanunmannedaerialvehicle</div><div class="t m0 x1 h3 y19 ff1 fs1 fc0 sc0 ls11 ws0">(UAV)inthethree-dimensionalflightcondition.Tosolvethisproblem,thisstudyproposesanexploringheuristic</div><div class="t m0 x1 h3 y1a ff1 fs1 fc0 sc0 ls12 ws0">transition-basedRRT(EHT-RRT)algorithm.ThealgorithmintroducestheheuristicideaoftheA*algorithmonthebasis</div><div class="t m0 x1 h3 y1b ff1 fs1 fc0 sc0 ls13 ws0">oftheT-RRTtoexploretheheuristiccost,anditestimatesthepathcostfromtheperspectivesofriskdegree,pathlength,</div><div class="t m0 x1 h3 y1c ff1 fs1 fc0 sc0 ls14 ws0">pathdeflectionangle,andheightchangetoimprovethequalityofthepath.Then,thelocalnodeslipstrategyisemployed</div><div class="t m0 x1 h3 y1d ff1 fs1 fc0 sc0 ls15 ws0">tomakethepathdeviatetothelow-riskarea,andthelocalbestdirectionattributeisaddedtoeachnode.Atlast,thetree</div><div class="t m0 x1 h3 y1e ff1 fs1 fc0 sc0 ls16 ws0">nodeexplorationmechanismisimprovedthroughthreedirectionalvectors,i.e.,randomdirection,targetdirection,and</div><div class="t m0 x1 h3 y1f ff1 fs1 fc0 sc0 ls17 ws0">localbestdirection,togetridoftheblindnessoftheT-RRTalgorithminpathfinding.Inaddition,atargetpointoffset</div><div class="t m0 x1 h3 y20 ff1 fs1 fc0 sc0 ls18 ws0">withaprobabilityof20%isusedtoimprovetheplanningefficiency.Theresultsofsimulationexperimentsshowthat</div><div class="t m0 x1 h3 y21 ff1 fs1 fc0 sc0 ls19 ws0">comparedwithT-RRT,BT-RRT,andT-RRT*algorithmswiththesametargetpointoffseteach,theEHT-RRTalgorithm</div><div class="t m0 x1 h3 y22 ff1 fs1 fc0 sc0 ls1a ws0">cangenerateashorter,safer,andsmoother3Dpathandbettersolvethe3DpathplanningproblemofUAVincomplex</div><div class="t m0 x1 h3 y23 ff1 fs1 fc0 sc0 ls0 ws0">urbanenvironments.</div><div class="t m0 x1 h3 y24 ff4 fs1 fc0 sc0 ls1b ws0">Key words<span class="ff1">:rotary-wingUAV;complexcostspace;3Dpathplanning;exploringheuristictransition-basedRRT(EHT-</span></div><div class="t m0 x1 h3 y25 ff1 fs1 fc0 sc0 ls0 ws0">RRT);transition-basedrapidly-exploringrandomtree(T-RRT)</div><div class="t m0 x1 ha y26 ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1 hb y27 ff3 fs7 fc0 sc0 ls0 ws0">计算机系统应用<span class="ff1">ISSN1003-3254,CODENCSAOBN<span class="_ _0"> </span>E-mail:<span class="fc1">csa@iscas.ac.cn</span></span></div><div class="t m0 x1 hb y28 ff1 fs7 fc0 sc0 ls0 ws0">ComputerSystems&Applications,2022,31(5):184−194[doi:<span class="fc1">10.15888/j.cnki.csa.008514</span>]<span class="_ _1"> </span><span class="fc1">http://www.c-s-a.org.cn</span></div><div class="t m0 x1 hb y29 ff1 fs7 fc0 sc0 ls0 ws0">©<span class="ff3">中国科学院软件研究所版权所有</span>.<span class="_ _2"> </span>Tel:+86-10-62661041</div><div class="t m0 x3 hb y2a ff3 fs7 fc0 sc0 ls0 ws0">①<span class="ff1"></span>基金项目<span class="ff1">:</span>湖南省自然科学基<span class="ls1c">金</span><span class="ff1">(2020JJ4201)</span></div><div class="t m0 x4 hb y2b ff3 fs7 fc0 sc0 ls0 ws0">收稿时间<span class="ff1">:2021-07-15;</span>修改时间<span class="ff1">:2021-08-24;</span>采用时间<span class="ff1">:2021-10-09;cs<span class="ls1c">a</span></span>在线出版时间<span class="ff1">:2022-02-25</span></div><div class="t m0 x3 h7 y2c ff1 fs4 fc0 sc0 ls0 ws0">184<span class="fs7"><span class="ff3">软件技术</span>•<span class="ff3">算法</span>SoftwareTechnique•Algorithm</span></div><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a></div><div class="pi" data-data='{"ctm":[1.612903,0.000000,0.000000,1.612903,1.546774,-24.748226]}'></div></div> </body> </html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/629db795a1ab4536ad06fc57/bg2.jpg"><div class="t m0 x5 h3 y2d ff3 fs1 fc0 sc0 ls1d ws0">电子商务的快速发展<span class="ff1">,</span>让我国快递数量<span class="ls1e">在</span><span class="ff1">201<span class="ls1e">7</span></span>年</div><div class="t m0 x1 h3 y2e ff3 fs1 fc0 sc0 ls1f ws0">就进入了<span class="ff1">“</span>单日亿件<span class="ff1">”</span>时代<span class="ff1">,</span>为了降低地面货运交通的</div><div class="t m0 x1 h3 y2f ff3 fs1 fc0 sc0 ls20 ws0">压力<span class="ff1">,</span>提高快递服务质量<span class="ff1">,</span>国内外各大物流公司早早将</div><div class="t m0 x1 h3 y30 ff3 fs1 fc0 sc0 ls21 ws0">旋翼无人机加入物流配送环节<span class="ff1">,</span>作为解决<span class="ff1">“</span>最后一公</div><div class="t m0 x1 h3 y31 ff3 fs1 fc0 sc0 ls22 ws0">里<span class="ff1">”</span>问题的答案</div><div class="t m0 x6 hc y32 ff1 fs8 fc0 sc0 ls22 ws0">[<span class="fc1">1</span>]</div><div class="t m0 x7 h3 y31 ff1 fs1 fc0 sc0 ls22 ws0">;<span class="ff3">另一方面</span>,“<span class="ff3">无人机</span>+<span class="ff3">行业细分</span>”<span class="ff3">的发</span></div><div class="t m0 x1 h5 y33 ff3 fs1 fc0 sc0 ls23 ws0">展模式也让旋翼无人机在城市内的安防和抢险救灾等</div><div class="t m0 x1 h5 y34 ff3 fs1 fc0 sc0 ls0 ws0">方面发挥着重要作用</div><div class="t m0 x8 hc y35 ff1 fs8 fc0 sc0 ls0 ws0">[<span class="fc1">2</span>]</div><div class="t m0 x9 h3 y34 ff1 fs1 fc0 sc0 ls0 ws0">.</div><div class="t m0 x5 h3 y36 ff3 fs1 fc0 sc0 ls24 ws0">面对复杂的城市环境<span class="ff1">,</span>旋翼无人机的路径规划技</div><div class="t m0 x1 h3 y37 ff3 fs1 fc0 sc0 ls20 ws0">术格外重要<span class="ff1">.</span>一条好的飞行路径<span class="ff1">,</span>直接关系到无人机的</div><div class="t m0 x1 h5 y38 ff3 fs1 fc0 sc0 ls25 ws0">运行效率、自身安全和对地面的安全影响</div><div class="t m0 xa hc y39 ff1 fs8 fc0 sc0 ls25 ws0">[<span class="fc1">3</span>]</div><div class="t m0 xb h3 y38 ff1 fs1 fc0 sc0 ls25 ws0">.<span class="ff3">如何在复</span></div><div class="t m0 x1 h3 y3a ff3 fs1 fc0 sc0 ls26 ws0">杂城市环境下<span class="ff1">,</span>快速找到距离更短、能耗更低、安全</div><div class="t m0 x1 h3 y3b ff3 fs1 fc0 sc0 ls26 ws0">性更高、更符合旋翼无人机运动约束的路径<span class="ff1">,</span>是目前</div><div class="t m0 x1 h3 y3c ff3 fs1 fc0 sc0 ls0 ws0">急需解决的问题<span class="ff1">.</span></div><div class="t m0 x5 h3 y3d ff3 fs1 fc0 sc0 ls27 ws0">传统的路规划<span class="ls28">如</span><span class="ff1">A*</span>算法和生物启发类算法<span class="ff1">,</span>计算</div><div class="t m0 x1 h3 y3e ff3 fs1 fc0 sc0 ls29 ws0">量大、规划时间长<span class="ff1">,</span>不能很好地应对高维复杂环境</div><div class="t m0 xc hc y3f ff1 fs8 fc0 sc0 ls29 ws0">[<span class="fc1">4</span>–<span class="fc1">5</span>]</div><div class="t m0 xd h3 y3e ff1 fs1 fc0 sc0 ls29 ws0">;</div><div class="t m0 x1 h3 y40 ff3 fs1 fc0 sc0 ls26 ws0">数学模型法、人工势场法<span class="ff1">,</span>对环境和机器人的建模要</div><div class="t m0 x1 h3 y41 ff3 fs1 fc0 sc0 ls2a ws0">求较高<span class="ff1">,</span>且容易陷入局部最优</div><div class="t m0 xe hc y42 ff1 fs8 fc0 sc0 ls2a ws0">[<span class="fc1">6</span>–<span class="fc1">7</span>]</div><div class="t m0 xf h3 y41 ff1 fs1 fc0 sc0 ls2a ws0">;<span class="ff3">基于采样的路径规</span></div><div class="t m0 x1 h5 y43 ff3 fs1 fc0 sc0 ls2b ws0">划方法</div><div class="t m0 x10 hc y44 ff1 fs8 fc0 sc0 ls2b ws0">[<span class="fc1">8</span>–<span class="fc1">10</span>]</div><div class="t m0 x11 h3 y43 ff1 fs1 fc0 sc0 ls2b ws0">,<span class="ff3">通过随机性的节点采样</span>,<span class="ff3">能快速寻找到空</span></div><div class="t m0 x1 h3 y45 ff3 fs1 fc0 sc0 ls20 ws0">间中的路径<span class="ff1">,</span>受维度变化的影响小<span class="ff1">,</span>但较强的随机性和</div><div class="t m0 x1 h3 y46 ff3 fs1 fc0 sc0 ls20 ws0">盲目的路径寻找策略<span class="ff1">,</span>导致求解效率较低<span class="ff1">,</span>较难找到高</div><div class="t m0 x1 h3 y47 ff3 fs1 fc0 sc0 ls0 ws0">质量路径解<span class="ff1">.</span></div><div class="t m0 x5 h3 y48 ff1 fs1 fc0 sc0 ls2c ws0">LaVall<span class="ls2d">e</span><span class="ff3">教授<span class="ls2d">在</span></span>199<span class="ls2d">9</span><span class="ff3">年提出了快速搜索随机树</span></div><div class="t m0 x1 h3 y49 ff1 fs1 fc0 sc0 ls2e ws0">(RRT<span class="ls1e">)</span><span class="ff3">算法</span></div><div class="t m0 x12 hc y4a ff1 fs8 fc0 sc0 ls2e ws0">[<span class="fc1">11</span>]</div><div class="t m0 x13 h3 y49 ff1 fs1 fc0 sc0 ls2e ws0">,<span class="ff3">以其独特的节点扩展机制</span>,<span class="ff3">成功应用于</span></div><div class="t m0 x1 h3 y4b ff3 fs1 fc0 sc0 ls26 ws0">多种路径规划场景中<span class="ff1">,</span>如覆盖路径规划、机械臂路径</div><div class="t m0 x1 h3 y4c ff3 fs1 fc0 sc0 ls2f ws0">规划、车辆路径规划等<span class="ff1">.</span>随后<span class="ff1">,RRT*</span>算法</div><div class="t m0 x14 hc y4d ff1 fs8 fc0 sc0 ls2f ws0">[<span class="fc1">12</span><span class="ls30">]</span></div><div class="t m0 x15 h3 y4c ff3 fs1 fc0 sc0 ls2f ws0">被提出<span class="ff1">,</span></div><div class="t m0 x1 h3 y4e ff3 fs1 fc0 sc0 ls31 ws0">在<span class="ff1 ls32">RR<span class="ls31">T</span><span class="ff3">算法的基础上增加了父节点重新选择和局部</span></span></div><div class="t m0 x1 h3 y4f ff3 fs1 fc0 sc0 ls33 ws0">节点重连步骤<span class="ff1">,</span>弥补<span class="ls34">了</span><span class="ff1">RR<span class="ls34">T</span></span>算法的一些不足<span class="ff1">,</span>且被证</div><div class="t m0 x1 h5 y50 ff3 fs1 fc0 sc0 ls35 ws0">实能够达到路径最优</div><div class="t m0 x16 hc y51 ff1 fs8 fc0 sc0 ls35 ws0">[<span class="fc1">13</span>]</div><div class="t m0 x17 h3 y50 ff1 fs1 fc0 sc0 ls35 ws0">.<span class="ff3">然而以上算法及其变体只能</span></div><div class="t m0 x1 h3 y52 ff3 fs1 fc0 sc0 ls36 ws0">面<span class="ls6">向</span><span class="ff1">[0,1<span class="ls6">]</span></span>地图环境<span class="ff1">,</span>针对机器人在连续成本变化空间</div><div class="t m0 x1 h3 y53 ff3 fs1 fc0 sc0 ls37 ws0">的路径规划问题<span class="ff1">,Jaille<span class="ls38">t</span></span>等人提出<span class="ls38">了</span><span class="ff1">T-RR<span class="ls38">T</span></span>算法</div><div class="t m0 x18 hc y54 ff1 fs8 fc0 sc0 ls37 ws0">[<span class="fc1">14</span>]</div><div class="t m0 x19 h3 y53 ff1 fs1 fc0 sc0 ls37 ws0">,<span class="ff3">在</span></div><div class="t m0 x1 h3 y55 ff1 fs1 fc0 sc0 ls39 ws0">RR<span class="ls3a">T</span><span class="ff3">算法的基础上引入了模拟退火的思想</span>,<span class="ff3">自行判断</span></div><div class="t m0 x1 h3 y56 ff3 fs1 fc0 sc0 ls26 ws0">新成本节点能否被扩展<span class="ff1">,</span>让路径的探索偏向低成本区</div><div class="t m0 x1 h3 y57 ff3 fs1 fc0 sc0 ls20 ws0">域<span class="ff1">,</span>可用于机器人在三维连续成本空间的路径规划<span class="ff1">.</span>紧</div><div class="t m0 x1 h3 y58 ff3 fs1 fc0 sc0 ls3b ws0">随其后<span class="ff1">,T-RRT*</span>算法</div><div class="t m0 x16 hc y59 ff1 fs8 fc0 sc0 ls3b ws0">[<span class="fc1">15</span><span class="ls3c">]</span></div><div class="t m0 x1a h3 y58 ff3 fs1 fc0 sc0 ls3b ws0">被提出<span class="ff1">,</span><span class="ls3c">将</span><span class="ff1">RRT*</span>算法的思想</div><div class="t m0 x1 h3 y5a ff3 fs1 fc0 sc0 ls3d ws0">与<span class="ff1 ls0">T-RR<span class="ls3d">T</span><span class="ff3">算法相结合</span>,<span class="ff3">进一步降低了路径成本</span>.</span></div><div class="t m0 x5 h3 y5b ff3 fs1 fc0 sc0 ls3e ws0">另一方面<span class="ff1">,</span>针<span class="ls3f">对</span><span class="ff1">RR<span class="ls3f">T</span></span>算法随机性强的问题<span class="ff1">,</span>文<span class="ls3f">献</span><span class="ff1">[<span class="fc1">16</span>]</span></div><div class="t m0 x1 h3 y5c ff3 fs1 fc0 sc0 ls40 ws0">提出<span class="ls38">的</span><span class="ff1">I-RR<span class="ls38">T</span></span>算法<span class="ff1">,</span>以目标点概率性偏置的方式<span class="ff1">,</span>让搜</div><div class="t m0 x1 h3 y5d ff3 fs1 fc0 sc0 ls41 ws0">索树的新节点扩展指向目标点<span class="ff1">;</span>文<span class="ls42">献</span><span class="ff1">[<span class="fc1">17</span><span class="ls42">]</span></span>提<span class="ls42">出</span><span class="ff1">Informed-</span></div><div class="t m0 x1 h3 y5e ff1 fs1 fc0 sc0 ls43 ws0">RRT*<span class="ff3">算法</span>,<span class="ff3">通过约束地图上的采样区域</span>,<span class="ff3">减少盲目性</span></div><div class="t m0 x1 h3 y5f ff3 fs1 fc0 sc0 ls44 ws0">的同时<span class="ff1">,</span>较好地提高了路径质量<span class="ff1">;</span>文<span class="ls45">献</span><span class="ff1">[<span class="fc1">18</span>,<span class="fc1">19</span><span class="ls45">]</span></span>结合人</div><div class="t m0 x1b h3 y2d ff3 fs1 fc0 sc0 ls46 ws0">工势场法的思想<span class="ff1">,</span>提<span class="ls47">出</span><span class="ff1">APF-RR<span class="ls47">T</span></span>算法<span class="ff1">,</span>将目标点方向</div><div class="t m0 x1b h3 y60 ff3 fs1 fc0 sc0 ls48 ws0">参与到每一次新树节点扩展中<span class="ff1">,</span>影响节点扩展<span class="ff1">.</span>然而<span class="ff1">,</span></div><div class="t m0 x1b h3 y61 ff3 fs1 fc0 sc0 ls26 ws0">在面对城市环境下的旋翼无人机路径规划工况<span class="ff1">,</span>上述</div><div class="t m0 x1b h3 y62 ff3 fs1 fc0 sc0 ls0 ws0">方法还存在以下问题<span class="ff1">:</span></div><div class="t m0 x1c h3 y63 ff1 fs1 fc0 sc0 ls0 ws0">(1<span class="ls3d">)</span><span class="ff3">空间成本类型考虑不充足</span>;</div><div class="t m0 x1c h3 y64 ff1 fs1 fc0 sc0 ls0 ws0">(2<span class="ls3d">)</span><span class="ff3">路径节点的扩展质量差</span>;</div><div class="t m0 x1c h3 y65 ff1 fs1 fc0 sc0 ls0 ws0">(3<span class="ls3d">)</span><span class="ff3">路径抖动性强</span>.</div><div class="t m0 x1c h3 y66 ff3 fs1 fc0 sc0 ls49 ws0">针对这些问题<span class="ff1">,</span>本文<span class="ls31">在</span><span class="ff1">T-RR<span class="ls31">T</span></span>算法的基础上<span class="ff1">,</span>提</div><div class="t m0 x1b h3 y67 ff3 fs1 fc0 sc0 ls4a ws0">出基于探索、启发和转移<span class="ls4b">的</span><span class="ff1">EHT-RRT(exploring</span></div><div class="t m0 x1b h3 y68 ff1 fs1 fc0 sc0 ls4c ws0">heuristictransition-basedRRT<span class="ls4d">)</span><span class="ff3">算法</span>,<span class="ff3">综合全局路径规</span></div><div class="t m0 x1b h3 y69 ff3 fs1 fc0 sc0 ls4e ws0">划和局部路径规划的特点<span class="ff1">,</span>通过多层球形危险度探</div><div class="t m0 x1b h5 y6a ff3 fs1 fc0 sc0 ls23 ws0">索、启发式成本估计、局部节点滑移、添加节点的局</div><div class="t m0 x1b h3 y6b ff3 fs1 fc0 sc0 ls4f ws0">部最好方向属性<span class="ff1">,</span>以及改进了的节点扩展机制<span class="ff1">,</span>让算法</div><div class="t m0 x1b h3 y6c ff3 fs1 fc0 sc0 ls26 ws0">在三维空间中的规划路径更加稳定、平滑和安全<span class="ff1">,</span>减</div><div class="t m0 x1b h3 y6d ff3 fs1 fc0 sc0 ls26 ws0">少路径后处理和轨迹规划的难度<span class="ff1">,</span>更适合解决旋翼无</div><div class="t m0 x1b h3 y6e ff3 fs1 fc0 sc0 ls0 ws0">人机在复杂三维环境下的路径规划问题<span class="ff1">.</span></div><div class="t m0 x1b ha y6f ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1b h6 y70 ff1 fs3 fc0 sc0 ls0 ws0">1<span class="ff3">研究基础</span></div><div class="t m0 x1b ha y71 ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1b h5 y72 ff4 fs1 fc0 sc0 ls0 ws0">1.1 RR<span class="ls3d">T</span><span class="ff2">算法</span></div><div class="t m0 x1c h3 y73 ff1 fs1 fc0 sc0 ls50 ws0">RR<span class="ls4d">T</span><span class="ff3">算法首先将起<span class="ls4d">点</span><span class="ff5">X</span></span></div><div class="t m0 x1d hd y74 ff1 fs9 fc0 sc0 ls50 ws0">ini<span class="ls4d">t</span></div><div class="t m0 x1e h3 y73 ff3 fs1 fc0 sc0 ls50 ws0">加入树中<span class="ff1">,</span>然后在无障</div><div class="t m0 x1b h5 y75 ff3 fs1 fc0 sc0 ls51 ws0">碍空<span class="ls52">间</span><span class="ff5">D</span></div><div class="t m0 x1f hd y76 ff1 fs9 fc0 sc0 ls51 ws0">fre<span class="ls52">e</span></div><div class="t m0 x20 h5 y75 ff3 fs1 fc0 sc0 ls51 ws0">中生成随机采样<span class="ls52">点</span><span class="ff5">X</span></div><div class="t m0 x21 hd y76 ff1 fs9 fc0 sc0 ls51 ws0">rand</div><div class="t m0 x22 h3 y75 ff1 fs1 fc0 sc0 ls51 ws0">,<span class="ff3">遍历当前树节点</span>,</div><div class="t m0 x1b h5 y77 ff3 fs1 fc0 sc0 ls53 ws0">找到<span class="ls1e">离</span><span class="ff5">X</span></div><div class="t m0 x23 hd y78 ff1 fs9 fc0 sc0 ls53 ws0">ran<span class="ls1e">d</span></div><div class="t m0 x24 h5 y77 ff3 fs1 fc0 sc0 ls53 ws0">点最近<span class="ls1e">的</span><span class="ff5">X</span></div><div class="t m0 x25 hd y78 ff1 fs9 fc0 sc0 ls53 ws0">nea<span class="ls1e">r</span></div><div class="t m0 x26 h3 y77 ff3 fs1 fc0 sc0 ls53 ws0">节点<span class="ff1">,</span>随后<span class="ls1e">以</span><span class="ff5">X</span></div><div class="t m0 x27 hd y78 ff1 fs9 fc0 sc0 ls53 ws0">near</div><div class="t m0 x28 h3 y77 ff1 fs1 fc0 sc0 ls53 ws0">–<span class="ff5">X</span></div><div class="t m0 x29 hd y78 ff1 fs9 fc0 sc0 ls53 ws0">ran<span class="ls1e">d</span></div><div class="t m0 x2a h5 y77 ff3 fs1 fc0 sc0 ls53 ws0">的</div><div class="t m0 x1b h3 y79 ff3 fs1 fc0 sc0 ls54 ws0">方向<span class="ff1">,</span>按照固定步<span class="lsd">长<span class="ff5">d</span></span>生成可行新节<span class="lsd">点</span><span class="ff5">X</span></div><div class="t m0 x2b hd y7a ff1 fs9 fc0 sc0 ls54 ws0">new</div><div class="t m0 x2c h3 y79 ff1 fs1 fc0 sc0 ls54 ws0">,<span class="ff3">重复以上</span></div><div class="t m0 x1b h5 y7b ff3 fs1 fc0 sc0 ls55 ws0">步骤直到新节<span class="ls38">点</span><span class="ff5">X</span></div><div class="t m0 x2d hd y7c ff1 fs9 fc0 sc0 ls55 ws0">ne<span class="ls38">w</span></div><div class="t m0 x2e h5 y7b ff3 fs1 fc0 sc0 ls55 ws0">距目标<span class="ls38">点</span><span class="ff5">X</span></div><div class="t m0 x21 hd y7c ff1 fs9 fc0 sc0 ls55 ws0">goa<span class="ls38">l</span></div><div class="t m0 x2f h3 y7b ff3 fs1 fc0 sc0 ls55 ws0">一定距离<span class="ff1">,</span>从而反</div><div class="t m0 x1b h3 y7d ff3 fs1 fc0 sc0 ls0 ws0">向找到路径解<span class="ff1">,</span>原理如<span class="fc1 ls3d">图<span class="ff1">1</span></span>所示<span class="ff1">.</span></div><div class="t m0 x1b h6 y7e ff1 fs3 fc0 sc0 ls0 ws0"></div><div class="c x30 y7f w2 he"><div class="t m0 x31 hf y80 ff6 fs7 fc0 sc0 ls0 ws0">X</div><div class="t m0 x32 h10 y81 ff7 fsa fc0 sc0 ls0 ws0">init</div><div class="t m0 x10 hf y82 ff6 fs7 fc0 sc0 ls0 ws0">X</div><div class="t m0 x33 h10 y83 ff7 fsa fc0 sc0 ls0 ws0">near</div><div class="t m0 x34 hf y84 ff6 fs7 fc0 sc0 ls0 ws0">X</div><div class="t m0 x35 h10 y85 ff7 fsa fc0 sc0 ls0 ws0">new</div><div class="t m0 x36 hf y86 ff6 fs7 fc0 sc0 ls0 ws0">X</div><div class="t m0 x37 h10 y87 ff7 fsa fc0 sc0 ls0 ws0">rand</div><div class="t m0 x38 hf y88 ff6 fs7 fc0 sc0 ls0 ws0">X</div><div class="t m0 x39 h10 y89 ff7 fsa fc0 sc0 ls0 ws0">goal</div><div class="t m0 x3a hf y88 ff6 fs7 fc0 sc0 ls0 ws0">D</div><div class="t m0 x3b h10 y89 ff7 fsa fc0 sc0 ls0 ws0">free</div></div><div class="t m0 x1b h3 y8a ff1 fs1 fc1 sc0 ls0 ws0"></div><div class="t m0 x3c h7 y8b ff3 fs4 fc0 sc0 ls56 ws0">图<span class="ff1 ls0">1RR<span class="ls56">T</span><span class="ff3">算法扩展原理</span></span></div><div class="t m0 x1b h11 y8c ff1 fsb fc0 sc0 ls0 ws0"></div><div class="t m0 x1b ha y8d ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1b h5 y8e ff4 fs1 fc0 sc0 ls0 ws0">1.2 T-RR<span class="ls3d">T</span><span class="ff2">算法</span></div><div class="t m0 x1c h3 y8f ff1 fs1 fc0 sc0 ls57 ws0">T-RR<span class="ls9">T</span><span class="ff3">算法<span class="ls9">在</span></span>RR<span class="ls9">T</span><span class="ff3">的框架上改进而来</span>,<span class="ff3">引入了模</span></div><div class="t m0 x1b h3 y90 ff3 fs1 fc0 sc0 ls4f ws0">拟退火的思想<span class="ff1">,</span>通过对比两节点间的成本变化<span class="ff1">,</span>决定新</div><div class="t m0 x1b h3 y91 ff3 fs1 fc0 sc0 ls58 ws0">节点能否被扩展<span class="ff1">.</span>算法在生成无碰撞的新节<span class="lsd">点</span><span class="ff5">X</span></div><div class="t m0 x3d hd y92 ff1 fs9 fc0 sc0 ls58 ws0">ne<span class="lsd">w</span></div><div class="t m0 x3e h3 y91 ff3 fs1 fc0 sc0 ls58 ws0">后<span class="ff1">,</span></div><div class="t m0 x1b h3 y93 ff3 fs1 fc0 sc0 ls59 ws0">需要进行转移测试审核<span class="ff1">:</span>如果新节点成<span class="ls28">本</span><span class="ff5">c<span class="ff1">(</span>X</span></div><div class="t m0 x3f hd y94 ff1 fs9 fc0 sc0 ls59 ws0">new</div><div class="t m0 x40 h3 y93 ff1 fs1 fc0 sc0 ls28 ws0">)<span class="ff3 ls59">比最</span></div><div class="t m0 x1b h3 y95 ff3 fs1 fc0 sc0 ls5a ws0">近点的成<span class="ls45">本</span><span class="ff5">c<span class="ff1">(</span>X</span></div><div class="t m0 x41 hd y96 ff1 fs9 fc0 sc0 ls5a ws0">near</div><div class="t m0 x42 h3 y95 ff1 fs1 fc0 sc0 ls45 ws0">)<span class="ff3 ls5a">低<span class="ff1">,</span>那么通过测试<span class="ff1">,</span>如果比最近点</span></div><div class="t m0 x1b h3 y97 ff3 fs1 fc0 sc0 ls20 ws0">的高<span class="ff1">,</span>需要通过模拟退火思想下的概率公式<span class="ff1">,</span>才可通过</div><div class="t m0 x1b h3 y5f ff3 fs1 fc0 sc0 ls0 ws0">转移测试<span class="ff1">.</span>转移测试函数如算<span class="ls3d">法<span class="ff1">1</span></span>所示<span class="ff1">.</span></div><div class="t m0 x43 h7 y98 ff1 fs4 fc0 sc0 ls0 ws0">2022<span class="fsc"></span><span class="ff3">年</span><span class="ff3">第</span><span class="fsc"></span>31<span class="fsc"></span><span class="ff3">卷</span><span class="ff3">第</span><span class="fsc"></span>5<span class="fsc"></span><span class="ff3">期</span></div><div class="t m0 x44 h3 y99 ff1 fs1 fc1 sc0 ls0 ws0">http://www.c-s-a.org.cn</div><div class="t m0 x45 h12 y9a ff3 fs4 fc0 sc0 ls5b ws0">计算机系统应用</div><div class="t m0 x46 h7 y2c ff1 fs7 fc0 sc0 ls0 ws0">SoftwareTechnique•Algorithm<span class="ff3">软件技术</span>•<span class="ff3">算法</span><span class="fs4">185</span></div><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a></div><div class="pi" data-data='{"ctm":[1.612903,0.000000,0.000000,1.612903,1.546774,-24.748226]}'></div></div>

<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/629db795a1ab4536ad06fc57/bg3.jpg"><div class="t m0 x1 h8 y9b ff3 fs5 fc0 sc0 ls0 ws0">算<span class="ls5c">法</span><span class="ff1">1.<span class="ff4"> </span>TransitionTest(<span class="ff5">c</span>(<span class="ff5">X</span></span></div><div class="t m0 x47 h13 y9c ff1 fsd fc0 sc0 ls0 ws0">near</div><div class="t m0 x48 h8 y9b ff1 fs5 fc0 sc0 ls0 ws0">),<span class="ff5">c</span>(<span class="ff5">X</span></div><div class="t m0 x49 h13 y9c ff1 fsd fc0 sc0 ls0 ws0">new</div><div class="t m0 x4a h8 y9b ff1 fs5 fc0 sc0 ls0 ws0">),<span class="ff5">d</span>(<span class="ff5">X</span></div><div class="t m0 x4b h13 y9c ff1 fsd fc0 sc0 ls0 ws0">near</div><div class="t m0 x4c h8 y9b ff1 fs5 fc0 sc0 ls0 ws0">–<span class="ff5">X</span></div><div class="t m0 x4d h13 y9c ff1 fsd fc0 sc0 ls0 ws0">new</div><div class="t m0 x4e h8 y9b ff1 fs5 fc0 sc0 ls0 ws0">))</div><div class="t m0 x1 h14 y9d ff4 fs5 fc0 sc0 ls0 ws0">begin</div><div class="t m0 x1 h8 y9e ff3 fs5 fc0 sc0 ls0 ws0">　　<span class="ff1">if<span class="ff5">c</span>(<span class="ff5">X</span></span></div><div class="t m0 x4f h13 y9f ff1 fsd fc0 sc0 ls0 ws0">new</div><div class="t m0 x50 h8 y9e ff1 fs5 fc0 sc0 ls0 ws0">)><span class="ff5">c</span></div><div class="t m0 x51 h13 y9f ff1 fsd fc0 sc0 ls0 ws0">max</div><div class="t m0 x52 h8 y9e ff1 fs5 fc0 sc0 ls0 ws0">thenreturnFalse;</div><div class="t m0 x1 h8 ya0 ff3 fs5 fc0 sc0 ls0 ws0">　　<span class="ff1">if<span class="ff5">c</span>(<span class="ff5">X</span></span></div><div class="t m0 x4f h13 ya1 ff1 fsd fc0 sc0 ls0 ws0">near</div><div class="t m0 x50 h8 ya0 ff1 fs5 fc0 sc0 ls0 ws0">)><span class="ff5">c</span>(<span class="ff5">X</span></div><div class="t m0 x6 h13 ya1 ff1 fsd fc0 sc0 ls0 ws0">new</div><div class="t m0 x53 h8 ya0 ff1 fs5 fc0 sc0 ls0 ws0">)thenreturnTrue;</div><div class="c x54 ya2 w3 h15"><div class="t m0 x0 h16 ya3 ff8 fse fc0 sc0 ls0 ws0">p<span class="ff9">=<span class="ffa">exp(</span></span></div><div class="t m0 x55 h17 ya4 ffb fsf fc0 sc0 ls0 ws0">−<span class="ffa">(<span class="ff8">c</span>(<span class="ff8">X</span></span></div><div class="t m0 x56 h18 ya5 ffc fsf fc0 sc0 ls0 ws0">new</div><div class="t m0 x57 h17 ya4 ffa fsf fc0 sc0 ls0 ws0">)<span class="ffb">−<span class="ff8">c</span></span>(<span class="ff8">X</span></div><div class="t m0 x58 h18 ya5 ffc fsf fc0 sc0 ls0 ws0">near</div><div class="t m0 x5 h19 ya4 ffa fsf fc0 sc0 ls0 ws0">))<span class="ffd">/<span class="ff8">d</span></span>(<span class="_ _3"></span><span class="ff8">X</span></div><div class="t m0 x33 h18 ya5 ffc fsf fc0 sc0 ls0 ws0">near</div><div class="t m0 x59 h17 ya4 ffb fsf fc0 sc0 ls0 ws0">−<span class="ff8">X</span></div><div class="t m0 x5a h18 ya5 ffc fsf fc0 sc0 ls0 ws0">new</div><div class="t m0 x5b h1a ya4 ffa fsf fc0 sc0 ls0 ws0">)</div><div class="t m0 x5c h17 ya6 ff8 fsf fc0 sc0 ls0 ws0">K<span class="_ _3"></span><span class="ffb">·</span>T</div><div class="t m0 x52 h16 ya3 ffa fse fc0 sc0 ls0 ws0">)</div></div><div class="t m0 x1 h8 ya7 ff3 fs5 fc0 sc0 ls0 ws0">　　<span class="_ _4"> </span><span class="ff1"></span></div><div class="t m0 x1 h8 ya8 ff3 fs5 fc0 sc0 ls0 ws0">　　<span class="ff1">ifRand(0,1)<<span class="ff5">p</span>then</span></div><div class="t m0 x1 h8 ya9 ff3 fs5 fc0 sc0 ls0 ws0">　　　　<span class="ff5">T<span class="ff1">=</span>T<span class="ff1">/</span>α<span class="ff1">;</span></span></div><div class="t m0 x1 h1b yaa ff3 fs5 fc0 sc0 ls0 ws0">　　　　<span class="ff5">n</span></div><div class="t m0 x5d h13 yab ff1 fsd fc0 sc0 ls0 ws0">Fail</div><div class="t m0 x5e h8 yaa ff1 fs5 fc0 sc0 ls0 ws0">=0;</div><div class="t m0 x1 h8 yac ff3 fs5 fc0 sc0 ls0 ws0">　　　　<span class="ff1">returnTrue;</span></div><div class="t m0 x1 h8 yad ff3 fs5 fc0 sc0 ls0 ws0">　　<span class="ff1">else</span></div><div class="t m0 x1 h8 yae ff3 fs5 fc0 sc0 ls0 ws0">　　　　<span class="ff1">if<span class="ff5">n</span></span></div><div class="t m0 x50 h13 yaf ff1 fsd fc0 sc0 ls0 ws0">Fail</div><div class="t m0 x5f h8 yae ff1 fs5 fc0 sc0 ls0 ws0">><span class="ff5">n</span></div><div class="t m0 x5b h13 yaf ff1 fsd fc0 sc0 ls0 ws0">Failmax</div><div class="t m0 x60 h8 yae ff1 fs5 fc0 sc0 ls0 ws0">then</div><div class="t m0 x1 h8 yb0 ff3 fs5 fc0 sc0 ls0 ws0">　　　　　　<span class="ff5">T<span class="ff1">=</span>T<span class="ff1">×</span>α<span class="ff1">;</span></span></div><div class="t m0 x1 h1b yb1 ff3 fs5 fc0 sc0 ls0 ws0">　　　　　　<span class="ff5">n</span></div><div class="t m0 x5f h13 yb2 ff1 fsd fc0 sc0 ls0 ws0">Fail</div><div class="t m0 x13 h8 yb1 ff1 fs5 fc0 sc0 ls0 ws0">=0;</div><div class="t m0 x1 h8 yb3 ff3 fs5 fc0 sc0 ls0 ws0">　　　　<span class="ff1">else</span></div><div class="t m0 x1 h1b yb4 ff3 fs5 fc0 sc0 ls0 ws0">　　　　　　<span class="ff5"> n</span></div><div class="t m0 x5a h13 yb5 ff1 fsd fc0 sc0 ls0 ws0">Fail</div><div class="t m0 x61 h8 yb4 ff1 fs5 fc0 sc0 ls0 ws0">=<span class="ff5">n</span></div><div class="t m0 x53 h13 yb5 ff1 fsd fc0 sc0 ls0 ws0">Fail</div><div class="t m0 x60 h8 yb4 ff1 fs5 fc0 sc0 ls0 ws0">+1;</div><div class="t m0 x1 h8 yb6 ff3 fs5 fc0 sc0 ls0 ws0">　　　　<span class="ff1">returnFalse;</span></div><div class="t m0 x1 h14 yb7 ff4 fs5 fc0 sc0 ls0 ws0">end</div><div class="t m0 x5 h3 yb8 ff3 fs1 fc0 sc0 ls5d ws0">算<span class="ls5e">法<span class="ff1">1</span></span>中<span class="ff1 ls5f">,<span class="ff5 ls5e">K</span></span>为起始点和目标点的空间成本算数平</div><div class="t m0 x1 h3 yb9 ff3 fs1 fc0 sc0 ls60 ws0">均数<span class="ff1 ls61">;<span class="ff5 ls62">T</span></span>为模拟的温度值<span class="ff1 ls61">;<span class="ff5 ls62">α</span></span>为温度变化系数<span class="ff1 ls61">;<span class="ff5">n</span></span></div><div class="t m0 x15 hd yba ff1 fs9 fc0 sc0 ls61 ws0">Fai<span class="ls62">l</span></div><div class="t m0 x62 h5 yb9 ff3 fs1 fc0 sc0 ls60 ws0">为失</div><div class="t m0 x1 h3 ybb ff3 fs1 fc0 sc0 ls63 ws0">败扩展次数<span class="ff1 ls64">;<span class="ff5">n</span></span></div><div class="t m0 x63 hd ybc ff1 fs9 fc0 sc0 ls64 ws0">Failma<span class="ls65">x</span></div><div class="t m0 x64 h3 ybb ff3 fs1 fc0 sc0 ls63 ws0">为最大扩展失败次数<span class="ff1 ls64">;<span class="ff5">c</span>(·<span class="ls65">)</span></span>为节点的</div><div class="t m0 x1 h3 ybd ff3 fs1 fc0 sc0 ls66 ws0">空间成本<span class="ff1 ls67">,</span>这里用危险度进行表示<span class="ff1 ls67">;<span class="ff5">d</span>(·<span class="ls68">)</span></span>为内部向量的模<span class="ff1 ls67">.</span></div><div class="t m0 x1 ha ybe ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1 h6 ybf ff1 fs3 fc0 sc0 ls0 ws0">2EHT-RR<span class="ls5b">T</span><span class="ff3">算法</span></div><div class="t m0 x5 h3 yc0 ff1 fs1 fc0 sc0 ls69 ws0">EHT-RR<span class="ls6a">T</span><span class="ff3">算法基<span class="ls6a">于</span></span>T-RR<span class="ls6a">T</span><span class="ff3">算法改进</span>,<span class="ff3">保留了完</span></div><div class="t m0 x1 h3 yc1 ff3 fs1 fc0 sc0 ls6b ws0">整的转移测试函数<span class="ff1">,</span>去除节点细化<span class="ff1">/</span>扩展审核函数<span class="ff1">,</span>在此</div><div class="t m0 x1 h3 yc2 ff3 fs1 fc0 sc0 ls20 ws0">基础上<span class="ff1">,</span>提出节点滑移策略和启发式成本探索策略<span class="ff1">,</span>利</div><div class="t m0 x1 h3 yc3 ff3 fs1 fc0 sc0 ls26 ws0">用球形节点结构<span class="ff1">,</span>将探索出的滑移方向危险度和滑移</div><div class="t m0 x1 h5 yc4 ff3 fs1 fc0 sc0 ls23 ws0">节点带来的启发式路径长度、路径偏角变化、路径高</div><div class="t m0 x1 h3 yc5 ff3 fs1 fc0 sc0 ls20 ws0">度变化<span class="ff1">,</span>共同组成总的启发式成本<span class="ff1">,</span>用于路径节点的局</div><div class="t m0 x1 h3 yc6 ff3 fs1 fc0 sc0 ls20 ws0">部滑移<span class="ff1">,</span>并分析出局部最好方向<span class="ff1">,</span>添加到扩展基点的属</div><div class="t m0 x1 h3 yc7 ff3 fs1 fc0 sc0 ls0 ws0">性中<span class="ff1">,</span>以改进节点的扩展过程<span class="ff1">.</span></div><div class="t m0 x1 ha yc8 ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1 h5 yc9 ff4 fs1 fc0 sc0 ls0 ws0">2.1 <span class="ff2">启发式成本探索</span></div><div class="t m0 x5 h5 yca ff3 fs1 fc0 sc0 ls6c ws0">由于城市环境下的楼宇、信号、人流等因素的影</div><div class="t m0 x1 h3 ycb ff3 fs1 fc0 sc0 ls6d ws0">响<span class="ff1">,</span>算法借鉴了车辆路径规划中的多<span class="ls6e">层</span><span class="ff1">Morphi<span class="ls6e">n</span></span>搜索</div><div class="t m0 x1 h5 ycc ff3 fs1 fc0 sc0 ls6f ws0">树的局部路径规划方法</div><div class="t m0 x65 hc ycd ff1 fs8 fc0 sc0 ls6f ws0">[<span class="fc1">20</span><span class="ls70">]</span></div><div class="t m0 x36 h3 ycc ff3 fs1 fc0 sc0 ls70 ws0">和<span class="ff1 ls6f">A*<span class="ff3">算法中的启发式成本</span></span></div><div class="t m0 x1 h3 yce ff3 fs1 fc0 sc0 ls20 ws0">估计思想<span class="ff1">,</span>提出节点滑移策略<span class="ff1">,</span>对滑移方向及节点进行</div><div class="t m0 x1 h3 ycf ff3 fs1 fc0 sc0 ls0 ws0">启发式成本探索<span class="ff1">,</span>为后续步骤做准备<span class="ff1">.</span></div><div class="t m0 x1 ha yd0 ff1 fs6 fc1 sc0 ls0 ws0"></div><div class="t m0 x1 h3 yd1 ff1 fs1 fc0 sc0 ls0 ws0">2.1.1<span class="ff3">危险度索引和计算</span></div><div class="t m0 x5 h3 yd2 ff3 fs1 fc0 sc0 ls71 ws0">全局地图环境下的城市障碍危险物如<span class="fc1 ls72">图<span class="ff1">2</span></span>所示<span class="ff1">,</span></div><div class="t m0 x1 h3 yd3 ff3 fs1 fc0 sc0 ls0 ws0">分为楼宇障碍物、信号干扰和地面人流密度<span class="ff1">.</span></div><div class="t m0 x5 h3 yd4 ff3 fs1 fc0 sc0 ls73 ws0">楼宇障碍物<span class="ff1">,</span><span class="ls74">用</span><span class="ff1">[0,1<span class="ls74">]</span></span>模型表示<span class="ff1">,<span class="ls74">0</span></span>代表可行区域<span class="ff1">,</span></div><div class="t m0 x1 h3 yd5 ff1 fs1 fc0 sc0 ls3d ws0">1<span class="ff3 ls0">代表楼宇障碍物<span class="ff1">,</span>则节点的楼宇危险度为<span class="ff1">:</span></span></div><div class="c x1 y5f w4 h1c"><div class="t m0 x3 h1d yd6 ff8 fs10 fc0 sc0 ls0 ws0">C</div><div class="t m0 x58 h1e yd7 ff8 fse fc0 sc0 ls0 ws0">b</div><div class="t m0 x66 h1f yd6 ff9 fs10 fc0 sc0 ls0 ws0">=</div><div class="t m0 x67 h20 yd8 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x10 h21 yd9 ffa fs10 fc0 sc0 ls0 ws0">0<span class="_ _5"> </span><span class="ffc">,<span class="_ _5"> </span><span class="ff8">C</span></span></div><div class="t m0 x12 h22 yda ffc fse fc0 sc0 ls0 ws0">building</div><div class="t m0 x7 h21 yd9 ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y<span class="ffd">,<span class="_ _6"></span><span class="fff">z</span></span></span>)<span class="_ _7"> </span><span class="ff9">=<span class="_ _7"> </span><span class="ffa">0</span></span></div><div class="t m0 x10 h21 ydb ffc fs10 fc0 sc0 ls0 ws0">inf<span class="_ _5"> </span>,<span class="_ _7"> </span><span class="ff8">C</span></div><div class="t m0 x68 h22 ydc ffc fse fc0 sc0 ls0 ws0">building</div><div class="t m0 x69 h21 ydb ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y<span class="ffd">,<span class="_ _6"></span><span class="fff">z</span></span></span>)<span class="_ _7"> </span><span class="ff9">=<span class="_ _7"> </span><span class="ffa">1</span></span></div><div class="t m0 x6a h21 yd6 ffc fs10 fc0 sc0 ls0 ws0">(1)</div></div><div class="t m0 x1b h3 y2d ff3 fs1 fc0 sc0 ls0 ws0">其中<span class="ff1">,<span class="ff5">C</span></span></div><div class="t m0 x6b hd ydd ff1 fs9 fc0 sc0 ls0 ws0">buildin<span class="ls3d">g</span></div><div class="t m0 x6c h3 y2d ff3 fs1 fc0 sc0 ls0 ws0">为楼宇障碍物的索引矩阵<span class="ff1">.</span></div><div class="t m0 x1c h3 yde ff3 fs1 fc0 sc0 ls75 ws0">信号干扰模型<span class="ff1">,</span>用干扰源三维坐标和干扰半径的</div><div class="t m0 x1b h3 ydf ff3 fs1 fc0 sc0 ls0 ws0">列<span class="ls3d">表</span><span class="ff1">[<span class="ff5">x</span>,<span class="ff5"> y</span>,<span class="ff5">z</span>,<span class="ff5">r</span><span class="ls3d">]</span></span>表示<span class="ff1">,</span>则节点的信号危险度为<span class="ff1">:</span></div><div class="c x1b ye0 w4 h23"><div class="t m0 x6d h1d ye1 ff8 fs10 fc0 sc0 ls0 ws0">C</div><div class="t m0 x6e h1e ye2 ff8 fse fc0 sc0 ls0 ws0">si</div><div class="t m0 x55 h1f ye1 ff9 fs10 fc0 sc0 ls0 ws0">=</div><div class="t m0 x6f h20 ye3 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 ye4 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 ye5 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 ye6 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 ye7 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 ye8 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 ye9 ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 yea ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 yeb ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 yec ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x6f h20 yed ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x32 h21 yee ffa fs10 fc0 sc0 ls0 ws0">0<span class="_ _5"> </span><span class="ffc">,<span class="_ _7"> </span><span class="ff8">C</span></span></div><div class="t m0 x70 h22 yef ffc fse fc0 sc0 ls0 ws0">signal</div><div class="t m0 x71 h21 yee ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y<span class="ffd">,<span class="_ _6"></span><span class="fff">z</span></span></span>)<span class="_ _7"> </span><span class="ffd">><span class="_ _7"> </span><span class="ff8">r</span></span></div><div class="t m0 x5b h1e yf0 ff8 fse fc0 sc0 ls0 ws0">i</div><div class="t m0 x32 h1d yf1 ff8 fs10 fc0 sc0 ls0 ws0">r</div><div class="t m0 x72 h1e yf2 ff8 fse fc0 sc0 ls0 ws0">i</div><div class="t m0 x73 h24 yf1 ffb fs10 fc0 sc0 ls0 ws0">−<span class="_ _6"></span><span class="ff8">C</span></div><div class="t m0 x74 h22 yf3 ffc fse fc0 sc0 ls0 ws0">signal</div><div class="t m0 x75 h21 yf1 ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y<span class="ffd">,<span class="_ _6"></span><span class="fff">z</span></span></span>)<span class="_ _5"> </span>,<span class="_ _5"> </span>0.2<span class="ff8">r</span></div><div class="t m0 x35 h1e yf2 ff8 fse fc0 sc0 ls0 ws0">i</div><div class="t m0 x69 h1d yf1 ff10 fs10 fc0 sc0 ls0 ws0">⩽<span class="_ _7"> </span><span class="ff8">C</span></div><div class="t m0 x48 h22 yf3 ffc fse fc0 sc0 ls0 ws0">signal</div><div class="t m0 x49 h21 yf1 ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y<span class="ffd">,<span class="_ _6"></span><span class="fff">z</span></span></span>)<span class="_ _7"> </span><span class="ff10">⩽<span class="_ _7"> </span><span class="ff8">r</span></span></div><div class="t m0 x76 h1e yf2 ff8 fse fc0 sc0 ls0 ws0">i</div><div class="t m0 x32 h21 yf4 ffc fs10 fc0 sc0 ls0 ws0">inf<span class="_ _5"> </span>,<span class="_ _7"> </span><span class="ff8">C</span></div><div class="t m0 x77 h22 yf5 ffc fse fc0 sc0 ls0 ws0">signal</div><div class="t m0 x78 h21 yf4 ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y<span class="ffd">,<span class="_ _6"></span><span class="fff">z</span></span></span>)<span class="_ _7"> </span><span class="ffd"><<span class="_ _7"> </span><span class="ffa">0</span>.<span class="ffa">2<span class="ff8">r</span></span></span></div><div class="t m0 x79 h1e yf6 ff8 fse fc0 sc0 ls0 ws0">i</div><div class="t m0 x6a h21 ye1 ffc fs10 fc0 sc0 ls0 ws0">(2)</div></div><div class="c x1b yf7 w4 h25"><div class="t m0 x7a h1d yf8 ff8 fs10 fc0 sc0 ls0 ws0">C</div><div class="t m0 x59 h1e yf9 ff8 fse fc0 sc0 ls0 ws0">s</div><div class="t m0 x5f h1f yf8 ff9 fs10 fc0 sc0 ls0 ws0">=</div><div class="t m0 x5b h1e yfa ff8 fse fc0 sc0 ls0 ws0">M</div><div class="t m0 x13 h20 yfb ffe fs10 fc0 sc0 ls0 ws0"></div><div class="t m0 x7b h16 yfc ff8 fse fc0 sc0 ls0 ws0">i<span class="ff9">=<span class="ffa">1</span></span></div><div class="t m0 x7 h1d yf8 ff8 fs10 fc0 sc0 ls0 ws0">C</div><div class="t m0 x7c h1e yf9 ff8 fse fc0 sc0 ls0 ws0">si</div><div class="t m0 x6a h21 yf8 ffc fs10 fc0 sc0 ls0 ws0">(3)</div></div><div class="t m0 x1b h3 yfd ff3 fs1 fc0 sc0 ls76 ws0">其中<span class="ff1">,<span class="ff5">C</span></span></div><div class="t m0 x7d hd yfe ff1 fs9 fc0 sc0 ls76 ws0">signa<span class="ls70">l</span></div><div class="t m0 x20 h3 yfd ff3 fs1 fc0 sc0 ls76 ws0">为节点到信号干扰源的距离<span class="ff1">,<span class="ff5 ls70">M</span></span>为信号干</div><div class="t m0 x1b h3 yff ff3 fs1 fc0 sc0 ls0 ws0">扰源数量<span class="ff1">.</span></div><div class="t m0 x1b h8 y100 ff1 fs5 fc0 sc0 ls0 ws0"></div><div class="c x30 y101 w2 h26"><div class="t m0 x7e h27 y102 ff11 fs7 fc0 sc0 ls0 ws0">300</div><div class="t m0 x7e h27 y103 ff11 fs7 fc0 sc0 ls0 ws0">250</div><div class="t m0 x7e h27 y104 ff11 fs7 fc0 sc0 ls0 ws0">200</div><div class="t m0 x7e h27 y105 ff11 fs7 fc0 sc0 ls0 ws0">150</div><div class="t m2 x6e h27 y106 ff12 fs7 fc0 sc0 ls0 ws0">z</div><div class="t m3 x72 h28 y107 ff12 fs11 fc0 sc0 ls0 ws0">x</div><div class="t m4 x7f h29 y108 ff12 fs12 fc0 sc0 ls0 ws0">y</div><div class="t m0 x7e h27 y109 ff11 fs7 fc0 sc0 ls0 ws0">100</div><div class="t m0 x80 h27 y10a ff11 fs7 fc0 sc0 ls0 ws0">50</div><div class="t m0 x81 h27 y10b ff11 fs7 fc0 sc0 ls0 ws0">100</div><div class="t m0 x82 h27 y10c ff11 fs7 fc0 sc0 ls0 ws0">200</div><div class="t m0 x1 h27 y10d ff11 fs7 fc0 sc0 ls0 ws0">300</div><div class="t m0 x83 h27 y10e ff11 fs7 fc0 sc0 ls0 ws0">100</div><div class="t m0 x51 h27 y10f ff11 fs7 fc0 sc0 ls0 ws0">200</div><div class="t m0 x7 h27 y110 ff11 fs7 fc0 sc0 ls0 ws0">300</div><div class="t m0 x8 h27 y111 ff11 fs7 fc0 sc0 ls0 ws0">400</div><div class="t m0 x84 h27 y112 ff11 fs7 fc0 sc0 ls0 ws0">500</div><div class="t m0 x85 h27 y113 ff11 fs7 fc0 sc0 ls0 ws0">600</div><div class="t m0 x86 h27 y114 ff11 fs7 fc0 sc0 ls0 ws0">700</div><div class="t m0 x87 h27 y115 ff11 fs7 fc0 sc0 ls0 ws0">800</div><div class="t m0 x57 h2a y116 ff13 fs7 fc0 sc0 ls0 ws0">信号干扰</div><div class="t m0 x11 h2a y117 ff13 fs7 fc0 sc0 ls0 ws0">建筑物</div><div class="t m0 x71 h2a y118 ff13 fs7 fc0 sc0 ls0 ws0">人流密度</div></div><div class="t m0 x1b h3 y119 ff1 fs1 fc1 sc0 ls0 ws0"></div><div class="t m0 x88 h7 y11a ff3 fs4 fc0 sc0 ls56 ws0">图<span class="ff1 ls0">2<span class="ff3">城市环境模型</span></span></div><div class="t m0 x1b h2b y11b ff1 fsc fc0 sc0 ls0 ws0"></div><div class="t m0 x1c h3 y11c ff3 fs1 fc0 sc0 ls24 ws0">地面人流密度模型<span class="ff1">,</span>由地面人流密度二维矩阵表</div><div class="t m0 x1b h3 y11d ff3 fs1 fc0 sc0 ls0 ws0">示<span class="ff1">,</span>等级<span class="ls3d">为</span><span class="ff1">1–100,</span>则节点的人流危险度为<span class="ff1">:</span></div><div class="c x1b y11e w4 h2c"><div class="t m0 x78 h1d y11f ff8 fs10 fc0 sc0 ls0 ws0">C</div><div class="t m0 x5d h1e y120 ff8 fse fc0 sc0 ls0 ws0">p</div><div class="t m0 x89 h1d y11f ff9 fs10 fc0 sc0 ls0 ws0">=<span class="_ _7"> </span><span class="ff8">C</span></div><div class="t m0 x51 h22 y121 ffc fse fc0 sc0 ls0 ws0">people</div><div class="t m0 x3b h21 y11f ffc fs10 fc0 sc0 ls0 ws0">(<span class="_ _3"></span><span class="ff8">x<span class="ffd">,<span class="_ _6"> </span></span>y</span>)<span class="_ _8"> </span>(4)</div></div><div class="t m0 x1b h3 y122 ff3 fs1 fc0 sc0 ls0 ws0">其中<span class="ff1">,<span class="ff5">C</span></span></div><div class="t m0 x6b hd y123 ff1 fs9 fc0 sc0 ls0 ws0">peopl<span class="ls3d">e</span></div><div class="t m0 x8a h3 y122 ff3 fs1 fc0 sc0 ls0 ws0">为地面人流密度索引矩阵<span class="ff1">.</span></div><div class="t m0 x1c h3 y124 ff3 fs1 fc0 sc0 ls0 ws0">综上<span class="ff1">,</span>单一空间节点的总危险度为<span class="ff1">:</span></div><div class="c x1b y125 w4 h2d"><div class="t m0 x70 h1d y126 ff8 fs10 fc0 sc0 ls0 ws0">C</div><div class="t m0 x4 h1e y127 ff8 fse fc0 sc0 ls0 ws0">x</div><div class="t m0 x8b h1d y126 ff9 fs10 fc0 sc0 ls0 ws0">=<span class="_ _9"> </span><span class="ff8">p</span></div><div class="t m0 x8c h16 y127 ffa fse fc0 sc0 ls0 ws0">1</div><div class="t m0 x8d h24 y126 ffb fs10 fc0 sc0 ls0 ws0">·<span class="_ _6"></span><span class="ff8">C</span></div><div class="t m0 x8e h1e y127 ff8 fse fc0 sc0 ls0 ws0">b</div><div class="t m0 x5a h1d y126 ff9 fs10 fc0 sc0 ls0 ws0">+<span class="_ _7"> </span><span class="ff8">p</span></div><div class="t m0 x8f h16 y127 ffa fse fc0 sc0 ls0 ws0">2</div><div class="t m0 x3a h24 y126 ffb fs10 fc0 sc0 ls0 ws0">·<span class="_ _6"></span><span class="ff8">C</span></div><div class="t m0 x90 h1e y127 ff8 fse fc0 sc0 ls0 ws0">s</div><div class="t m0 x91 h1d y126 ff9 fs10 fc0 sc0 ls0 ws0">+<span class="_ _7"> </span><span class="ff8">p</span></div><div class="t m0 x92 h16 y127 ffa fse fc0 sc0 ls0 ws0">3</div><div class="t m0 x1a h24 y126 ffb fs10 fc0 sc0 ls0 ws0">·<span class="_ _6"></span><span class="ff8">C</span></div><div class="t m0 x93 h1e y127 ff8 fse fc0 sc0 ls0 ws0">p</div><div class="t m0 x6a h21 y126 ffc fs10 fc0 sc0 ls0 ws0">(5)</div></div><div class="t m0 x1b h3 y128 ff3 fs1 fc0 sc0 ls0 ws0">其中<span class="ff1">,(<span class="ff5">p</span></span></div><div class="t m0 x7d hd y129 ff1 fs9 fc0 sc0 ls0 ws0">1</div><div class="t m0 x94 h3 y128 ff1 fs1 fc0 sc0 ls0 ws0">,<span class="ff5">p</span></div><div class="t m0 x95 hd y129 ff1 fs9 fc0 sc0 ls0 ws0">2</div><div class="t m0 x96 h3 y128 ff1 fs1 fc0 sc0 ls0 ws0">,<span class="ff5">p</span></div><div class="t m0 x97 hd y129 ff1 fs9 fc0 sc0 ls0 ws0">3</div><div class="t m0 x98 h3 y128 ff1 fs1 fc0 sc0 ls3d ws0">)<span class="ff3">为</span>3<span class="ff3 ls0">种危险的权重<span class="ff1">.</span></span></div><div class="t m0 x1c h3 y12a ff3 fs1 fc0 sc0 ls24 ws0">算法在进行节点扩展时<span class="ff1">,</span>只是从欧式距离上选择</div><div class="t m0 x1b h5 y12b ff3 fs1 fc0 sc0 ls77 ws0">了<span class="ls78">离</span><span class="ff5">X</span></div><div class="t m0 x99 hd y12c ff1 fs9 fc0 sc0 ls77 ws0">ran<span class="ls78">d</span></div><div class="t m0 x95 h5 y12b ff3 fs1 fc0 sc0 ls77 ws0">更近<span class="ls78">的</span><span class="ff5">X</span></div><div class="t m0 x9a hd y12c ff1 fs9 fc0 sc0 ls77 ws0">nea<span class="ls78">r</span></div><div class="t m0 x9b h3 y12b ff3 fs1 fc0 sc0 ls77 ws0">节点作为扩展基点<span class="ff1">,</span>却没有考</div><div class="t m0 x1b h5 y12d ff3 fs1 fc0 sc0 ls62 ws0">虑<span class="ff5 ls79">X</span></div><div class="t m0 x9c hd y12e ff1 fs9 fc0 sc0 ls79 ws0">nea<span class="ls62">r</span></div><div class="t m0 x9d h3 y12d ff3 fs1 fc0 sc0 ls79 ws0">节点的周围环境情况<span class="ff1">.</span>从文<span class="ls62">献</span><span class="ff1">[<span class="fc1">21</span><span class="ls62">]</span></span>可知<span class="ff1">,</span>对节</div><div class="t m0 x1b h3 y12f ff3 fs1 fc0 sc0 ls26 ws0">点的路径碰撞检查会消耗大量时间<span class="ff1">,</span>所以本文采用更</div><div class="t m0 x1b h3 y130 ff3 fs1 fc0 sc0 ls7a ws0">加细密的多层球形节点结构进行危险度索引和计算<span class="ff1">,</span></div><div class="t m0 x1b h3 y131 ff3 fs1 fc0 sc0 ls26 ws0">以避免路径偏向建筑障碍物附近<span class="ff1">,</span>提高路径扩展的成</div><div class="t m0 x1b h3 y132 ff3 fs1 fc0 sc0 ls0 ws0">功率<span class="ff1">,</span>减少碰撞检查次数<span class="ff1">.</span></div><div class="t m0 x1c h3 y133 ff3 fs1 fc0 sc0 ls1d ws0">如<span class="fc1 ls2">图<span class="ff1">3</span></span>所示<span class="ff1">,</span><span class="ls2">以<span class="ff1">3</span></span>层结构为例<span class="ff1">,</span>为了保证较好的方</div><div class="t m0 x1b h3 y134 ff3 fs1 fc0 sc0 ls0 ws0">向扩展密度<span class="ff1">,</span>结构的相邻方向偏角采<span class="ls3d">用</span><span class="ff1">45°.</span></div><div class="t m0 x1c h3 y135 ff3 fs1 fc1 sc0 ls7b ws0">图<span class="ff1 ls7c">3(a<span class="ls7b">)</span><span class="ff3 fc0">显示的为探索球的二<span class="ls7b">维<span class="ff1">3</span></span>层结构<span class="ff1">,</span>共有</span></span></div><div class="t m0 x1b h3 y136 ff1 fs1 fc0 sc0 ls70 ws0">8<span class="ff3 ls7d">个方向<span class="ff1">,</span>每个方向按半径不同<span class="ls70">有</span></span>3<span class="ff3 ls7d">个节点<span class="ff1">.</span>首层节点</span></div><div class="t m0 x1b h3 y137 ff3 fs1 fc0 sc0 ls4f ws0">因为要用于路径的局部节点滑移<span class="ff1">,</span>不宜过大<span class="ff1">,</span>所以设置</div><div class="t m0 x1b h3 y5f ff3 fs1 fc0 sc0 ls7e ws0">为标准扩展步<span class="lsd">长<span class="ff5">d</span>的</span><span class="ff1">1/3,</span>末层节点考虑到局部节点滑</div><div class="t m0 x43 h12 y9a ff3 fs4 fc0 sc0 ls5b ws0">计算机系统应用</div><div class="t m0 x44 h3 y99 ff1 fs1 fc1 sc0 ls0 ws0">http://www.c-s-a.org.cn</div><div class="t m0 x9e h7 y98 ff1 fs4 fc0 sc0 ls0 ws0">2022<span class="fsc"></span><span class="ff3">年</span><span class="ff3">第</span><span class="fsc"></span>31<span class="fsc"></span><span class="ff3">卷</span><span class="ff3">第</span><span class="fsc"></span>5<span class="fsc"></span><span class="ff3">期</span></div><div class="t m0 x3 h7 y2c ff1 fs4 fc0 sc0 ls0 ws0">186<span class="fs7"><span class="ff3">软件技术</span>•<span class="ff3">算法</span>SoftwareTechnique•Algorithm</span></div><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a><a class="l" rel='nofollow' onclick='return false;'><div class="d m1"></div></a></div><div class="pi" data-data='{"ctm":[1.612903,0.000000,0.000000,1.612903,1.546774,-24.748226]}'></div></div>