网站建设一秒互联,怎么填写网站icp备案,软件平台开发公司,深圳网站设计go文章目录前言介绍1. 路径规划在自动驾驶系统架构中的位置2. 全局路径规划的分类2.1 基础图搜索算法2.1.1 Dijkstra算法2.1.2 双向搜索算法2.1.3 Floyd算法2.2 启发式算法2.2.1 A*算法2.2.2 D*算法2.3 基于概率采样的算法2.3.1 概率路线图#xff08;PRM#xff09;2.3.2 快速…
文章目录前言介绍1. 路径规划在自动驾驶系统架构中的位置2. 全局路径规划的分类2.1 基础图搜索算法2.1.1 Dijkstra算法2.1.2 双向搜索算法2.1.3 Floyd算法2.2 启发式算法2.2.1 A*算法2.2.2 D*算法2.3 基于概率采样的算法2.3.1 概率路线图PRM2.3.2 快速随机探索树RRT2.4 基于人工智能的规划方法2.4.1 人工神经网络ANN2.4.2 遗传算法GA2.4.3 粒子群优化算法PSO2.4.4 蚁群优化算法ACO2.4.5 模拟退火算法SA2.4.6 人工鱼群算法2.4.7 人工蜂群算法2.4.8 入侵杂草算法参考文献前言 在GitHub上找到了路径规划与运动规划方面不错的学习资料 PathPlanning——https://github.com/zhm-real/PathPlanningMotionPlanning——https://github.com/zhm-real/MotionPlanning 介绍 路径规划在自动驾驶技术中起到承上启下的重要作用。路径规划在遵循道路交通规则的前提下计算出具体运动指令将车辆从当前位置导航到目的地。本文将介绍路径规划在自动驾驶系统中的架构以及路径规划的常见类型——基础图搜索算法、启发式算法、基于概率采样的算法以及基于人工智能的算法。
1. 路径规划在自动驾驶系统架构中的位置 Claudine Badue[1]等人以圣西班牙联邦大学UFES开发的自动驾驶汽车Intelligent Autonomous Robotics AutomobileIARA为例提出了自动驾驶汽车的自动驾驶系统的典型架构。如图所示自动驾驶系统主要由感知系统Perception System和规划决策系统Decision Making System组成。感知系统主要由交通信号检测模块Traffic Signalization DetectorTSD、移动目标跟踪模块Moving Objects TrackerMOT、定位与建图模块Localizer and Mapper等组成。规划决策系统主要由全局路径规划模块Route Planner、局部路径规划模块Path Planner、行为决策模块Behavior Selector、运动规划模块Motion Planner、自主避障模块(Obstacle Avoider)以及控制模块Controller组成。
图1-1 自动驾驶系统架构图 全局路径规划在此架构中主要是由全局路径规划模块完成的。该模块通过接收用户在离线地图Offline Maps中给出的目标点基于由感知系统提供的感知信息计算出从当前自动驾驶汽车的位置到最终目标点的路径WWW。路径WWW是一个路径点的序列即W{w1w2,,,,w∣W∣}W\{{w_1w_2,,,,w_{|W|}}\}W{w1w2,,,,w∣W∣}其中每个路径点wiw_iwi是一个坐标对在离线地图中wi(xi,yi)w_i(x_i,y_i)wi(xi,yi)。得到路径WWW后将路径Route信息传递给下一个模块——局部路径规划模块。
2. 全局路径规划的分类 全局路径规划模块负责计算一条从自动驾驶汽车的初始位置到由用户操作员定义的最终位置的路线W。路径W是一个路径点的序列即W{w1w2,,,,w∣W∣}W\{{w_1w_2,,,,w_{|W|}}\}W{w1w2,,,,w∣W∣}其中每个路径点wiw_iwi是一个坐标对在离线地图中wi(xi,yi)w_i(x_i,y_i)wi(xi,yi)。 如果我们将道路网络看做成一个带有边权值的有向图该有向图中的顶点通过带有权值的边连接起来可以将一般的路径规划问题转化为有向图中最短路径的求解问题。对于大型的静态路网问题Dijkstra[2]和A*[3]等经典算法由于时间复杂度过大难以取得较好的成果。 在过去的十年中道路网络中路径规划算法的性能有了显著的进展。新开发的算法可以以毫秒或更少的时间计算驾驶方向。道路网络中的路径规划技术在查询时间、预处理时间、空间使用和对输入变化的鲁棒性等方面提供了不同的权衡。不同的学者对路径规划算法的分类有所不同。Claudine Badue在他的文章中将全局路径规划算法分为以下几类:
基于目标导向的全局路径规划Goal-directed techniques基于分割的全局路径规划Separator-based techniques分级规划的全局路径规划Hierarchical techniques有界跳跃的全局路径规划Bounded-hop techniques Bast[4]等人的分类方式与Claudine作出的分类方式几乎一致。他们在上述四种算法的基础之上不仅仅是对静态网络中两点之间的最短路径的长度的求解。最重要的是他们还扩展到能够检索到最短的路径本身。此外他们还在批量计算最短路径如距离表更现实的场景如动态网络或处理多个目标函数等多方面进行探索与验证。 David González[5]等人虽然主要考虑了运动规划方面的分类方式但其中有些方法对于全局路径规划仍然是通用的。他们将一般的规划算法分为:
基于采样搜索的算法:Dijkstra 、 RRT 、 A *、 hybird A *和 Lattice 等基于曲线插值的算法: RS 曲线、 Dubins 曲线、多项式曲线、贝塞尔曲线和样条曲线等基于最优化的算法: Apollo 的 piecewise - jerk、EM Planner 等。 图2-1 Dijkstra算法、A*算法以及RRT算法 González还列举了常见的路径规划算法如图搜索算法、基于采样的算法、基于曲线插值的算法以及基于优化的算法。表2-1 路径规划常见算法分类 Brian Paden[24]对常见的路径规划算法从适用场合、最优性、完备性、时间复杂度以及实时性进行分析表2-2。
表2-2 常见路径规划算法的分析 2.1 基础图搜索算法
2.1.1 Dijkstra算法 Dijkstra算法[2]是由荷兰计算机科学家迪杰斯特拉于1959年提出的是从一个节点遍历其余各节点的最短路径算法解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始采用贪心算法的策略每次遍历到始点距离最近且未访问过的顶点的邻接节点直到扩展到终点为止。
Dijkstra算法将图上的初始点看作一个集合S其它点看作另一个集合U。根据初始点求出其它点到初始点的距离dist[i]若相邻则dist[i]为边权值若不相邻则dist[i]为无限大。之后选取最小的dist[i]记为dist[x]并将此dist[i]边对应的点记为x加入集合S实际上加入集合的这个点的dist[x]值就是它到初始点的最短距离。再根据x更新跟x相邻点y的dist[y]值:dist[y] min{ dist[y], dist[x] 边权值weight[x][y] }因为可能把距离调小所以这个更新操作叫做松弛操作。重复34两步直到目标点也加入了集合此时目标点所对应的dist[i]即为最短路径长度。注:重复第三步的时候应该从所有的dist[i]中寻找最小值而不是只从与x点相邻的点中寻找。 下图展示了Dijkstra算法、双向搜索算法以及A算法的搜索空间。Dijkstra算法的搜索空间较大双向搜索算法通过从起始点和终点同时搜索两个搜索空间相遇之时即在x点处结束算法其搜索空间比Dijkstra算法小。
图2-2 Dijkstra算法左、双向搜索中间和A算法右的搜索空间示意图 2.1.2 双向搜索算法 双向搜索算法可以用来减少搜索空间它同时运行s的前向搜索和t的向后搜索。一旦它们的搜索空间的交点被证明在从s到t的最短路径上包含一个顶点x该算法就会停止。对于静态路网最短路径问题双向搜索访问的顶点数量大约是单向方法的一半。
2.1.3 Floyd算法 Floyd算法[6]在Dijkstra算法的基础上进行了改进使之不仅能求得起始点到目标点的距离还能求得图中任意一节点到另一节点的最短距离。Floyd算法的实现依靠两个邻接矩阵其中一个临界矩阵存放各个路径的顶点另一个临界矩阵存放各个路径的距离值通过一行一行的更新最终获得图中任意一节点到另一节点的最短距离。
2.2 启发式算法 启发式方法一种比传统方法更快地解决问题的技术它会在每一个分支步骤评价可用信息并决定遵循哪个分支得到一个最优或近似最优解。大多数搜索问题的数据量都是指数级的而启发式方法可以将问题降低一个数量级而且当可评估的信息越多搜索的指向性就越明确从而提高搜索效率。常见的启发式方法有Astar算法和Dstar算法。
2.2.1 A*算法 Astar搜索方法[3]最初是Hart等人在1968年作为经典Dijkstra算法的修改版本引入的。Astar算法通过引导搜索方向的启发式算法来改进Dijkstra算法并通过这样做减少必要的计算次数。Astar算法的关键是建立评估函数f(n)f(n)f(n)f(n)g(n)h(n)f(n)g(n)h(n)f(n)g(n)h(n)其中g(n)g(n)g(n)表示实际成本h(n)h(n)h(n)表示最佳路径的估计成本。假设在一个二维平面中的目标位置坐标为xgoalygoalx_{goal}y_{goal}xgoalygoal对于一个平面中的坐标节点x,yx,yx,yh(n)h(n)h(n)的值通常取两个节点之间的欧几里德距离。但是这种方式很容易忽略了障碍物从而低估了实际成本也就是说存在障碍物的情况下距离目标点的距离很容易被低估。
2.2.2 D*算法 在现实世界中移动机器人通常对通向目标的路径上的障碍物信息知之甚少。随着机器人在运动过程中发现新的障碍这种知识会逐渐得到改善。因此当接收到有关环境的新信息时对目标的计算路径进行更新是非常重要的。换句话说当要搜索的区域发生时重新规划是必要的。前面介绍的Astar算法除了从头开始图搜索之外没有为重新规划问题提供任何解决方案。
图2-3 由D* Lite左和Field D*右在900x700代价地图中产生的路径。 在这里障碍物用深灰色表示可穿越的区域用黑色表示。 1994年Stemtz提出了D*
[8]算法它主要用于机器人探索路径。Dstar算法将配置空间表示为一系列状态状态表示机器人位置的方向。Dstar算法也称为动态Astar它的工作原理与Astar算法的原理基本相同但它在Astar的基础上过线性插值规划和重新规划生成较低成本和平滑的路径。此外一些学者研究了关于Dstar算法的变种如Field Dstar算法
[9]、Thetastar算法
[10]、Dstar Lite
[9]算法。图2-3显示了Dstar Lite和Field Dstar两种算法在代价地图中路径规划的效果。Field Dstar是一种基于插值的规划和重新规划算法通过均匀和非均匀分辨率网格生成低成本路径。该方法在传统基于栅格地图的路径规划算法的两个瓶颈处——所产生的路径的质量以及基于栅格的规划的内存和计算需求有所提升。表2-3 D* Lite与Field D*算法性能比较 D* LiteField D*Initial planning time (s)0.831.46Initial path cost (relative)1.000.96Traversal cost update time (s)0.060.01Replanning time (s)0.040.07Replanned path cost (relative)1.000.96
2.3 基于概率采样的算法 基于采样的算法在20世纪90年代末引入以获得路径规划问题的近似解。基于采样的方法将状态空间表示为图形并尝试使用不同的随机采样技术找到从初始状态到最终状态的路径。基于采样的规划器遵循概率完备性原则这意味着如果存在解决方案就一定会找到它。但需要注意的是这种方法不能保证解决方案的最优性。基于采样的算法是根据算法的收敛速度和平均收敛速度来判断的。根据实际实验观察和统计基于采样的算法平均至少比多项式时间分析算法快一个数量级。目前两个主要基于采样的算法是由Kavraki LE 1994年提出的概率路线图[11]PRM和LaValle SM 1998年提出的快速随机探索树[12]RRT。
2.3.1 概率路线图PRM 概率路线图算法包括两个步骤路线图构建和查询即学习阶段和查询阶段。在学习阶段对状态空间中的一定数量的随机状态进行采样并生成连接这些状态的图表。这是一个计算昂贵的预处理步骤但只需要执行一次。在查询阶段输入初始和最终状态并使用 Dijkstra或者Astar算法从图表中获得它们之间的轨迹。在多个查询的情况下概率路线图是非常有效的。但PRM存在许多问题所以相关学者对其做出了变种改进。PRMstar[13]引入了一种可变距离度量以提高优化性。灵活的随时动态随机路线图[14]Flexible Anytime Dynamic PRM FADPRM将地图环境划分为理想的区域根据边界边的优先级形成启发式算法进行了Astar搜索以不断改进该解决方案。
图2-4 在二值化地图中进行构型采样 图2-5 PRM算法的步骤 图2-4与图2-5阐述了PRM算法的流程。首先在二值化地图中进行构型采样大约750个点并进行碰撞检测筛选出无碰撞的点。再进行邻域计算对每个周围一定邻域距离以内的点进行连接并对连线进行碰撞检测。再对所有的点用图搜索算法找到一条最短路径最后通过路径修剪的方法得到最终的路径。
2.3.2 快速随机探索树RRT RRT 算法通过随机选择在非障碍物区域的点构建单向搜索树直到树权到达目标节点。RRT树在未占用空间中均匀扩展的属性使得在复杂的高维环境、非完整和运动约束环境中依旧是有效的。但是生成的路径往往不是最优的并且需要进行平滑优化。相比于PRMRRT作为一种增量算法不需要使用一定数量的样本预计算图对于具有动态环境和约束变化的场景更为有利。因此专家学者从规划时间、扩展节点、路径成本和路径间隙四个方面对RRT方法做出了相应地改进如RRT-Connect、RRTstar、Bi-RRT[15-17]等。图2-6展示了RRT、RRTstar以及RRTstarFN的算法效果。RRTstar的路径明显较RRT短RRTstarFN既保证了路径的距离优势同时节省了大量冗余的节点提升了算法速度。
图2-6 RRT、RRT*以及RRT*FN的算法效果 图2-7 RRT*FN算法以及ForcedRemova( )函数算法 RRTstarFN的核心在于在原有RRTstar的方法上通过强制移除一些子节点为空的节点从而减少运算时的节点数目。
2.4 基于人工智能的规划方法 经典的方法虽然被发现是有效的但需要更多的时间来确定可行的无碰撞路径。而且经典的方法往往被锁定在局部最优解中这可能远不及全局最优解。此外存在多个障碍物的移动机器人的路径规划被发现是非确定性多项式时间困难NP-hard问题。因此在动态环境情况下就会变得更加复杂。这些缺点使得传统方法在复杂环境中显得无能为力。因此人工神经网络ANN、遗传算法GA粒子群优化算法PSO蚁群优化算法ACO和模拟退火算法SA等进化算法来快速求解路径规划问题。
2.4.1 人工神经网络ANN 人工神经网络ANN可以表达路径规划感知到行为的映射关系。神经网络用于描述环境之间的约束并且将能量定义为关于路径点的函数。能量水平取决于路径点的位置而机器人朝着能量降低的方向移动。最后得到一条总能量最小的路径。虽然这条路径没有障碍但它并不一定是最短路径或最佳路径。同时很难定量地描述移动机器人随机的工作环境因此建立神经网络拓扑来描述移动环境也是非常困难的。另外复杂且庞大的结构也加大了神经网络权重设置的难度和复杂度。
2.4.2 遗传算法GA 遗传算法GA[18]由Holland于1975年提出。在遗传算法中问题的所有可能解都编码为形成初始种群的染色体。构建了几个基本操作∶交叉变异和选择。生成初始种群利用目标计算个体的适合度值以便确定可选择的基本操作。GA虽然具有强大的搜索能力和较高的搜索效率但容易提前收敛的问题使得它它接近问题的最优解时收敛速度降低。
2.4.3 粒子群优化算法PSO 1995年Eberhart和Kennedy[19-20] 研究鸟类群体的活动规律提出了粒子群优化算法PSO。它从随机解开始通过不停地迭代找到最优解。然后利用适应度值对解的质量进行评价最后与当前搜索的最优值进行比较找出全局最优解。该算法用于求解机器人路径规划问题具有实现简单、精度高、收敛速度快等优点。
图2-8 AERPSO算法在动态目标点下的搜索效果。(a) t 0 (b) t 700 © t 1200 (d) t 2000 (e) t 2900(f) t 4672 粒子群优化PSO是一种极好的基于种群的优化算法经常应用于群体机器人协同搜索工作。考虑到PSO的全局优化特性它很容易收敛到搜索环境中的特定位置从而错过了学习更多信息的机会。V. Garg[21]在PSO的基础上进行改进提出了一种自适应探索机器人PSOAERPSO来解决多目标搜索问题。该方法提高了探索未探索区域的机会并有助于利用进化速度和聚集程度进行避障。自适应惯性权重有助于增强探索。
2.4.4 蚁群优化算法ACO ACO算法由 Marco Dorigo于1992年提出。它的基本原理是每只蚂蚁在其行走的路径上释放分泌物作为参考并且还将感知其他蚂蚁释放的分泌物这种分泌物通常被称为信息素。在信息素的作用下蚁群可以相互通信并选择路径。当路径上的信息素比其他路径更多时蚁群会自发地移动到这条路径导致信息素浓度升高从而吸引后者的蚂蚁形成正向机制反馈。最后整个蚁群集中在最佳路径上。
图2-9 蚁群算法ACO示意图 蚁群算法不仅具有种群的全局搜索能力而且具有个体间的协同效应。它可以找到一条更好的道路即使环境的完整信息是未知的。然而在算法的早期阶段收敛速度慢计算量大。 在三维路径规划问题中理想的飞行路径应该是平衡总飞行路径长度和地形威胁并在此基础之上缩短飞行时间、减少碰撞的可能性。但传统的三位路径规划算法往往不能较好地权衡这些因素且优化后的目标函数缺乏实际约束导致建模不准确。对此Yuting Wan等[22]提出了APPMS算法该算法将路径规划任务转换为具有多约束的多目标优化任务同时对基于飞行总路径长度和地形威胁程度的目标进行优化。此外为了获得最优三维飞行路径引入了一种基于改进蚁群优化的精确群智能搜索方法该方法可以利用首选搜索方向和随机邻域搜索机制提高全局和局部搜索能力。图2-10描述了APPMS算法的流程。
图2-10 APPMS算法流程 2.4.5 模拟退火算法SA 模拟退火SA算法由N.Metropolis 等人1953年提出。它是一种基于蒙特卡洛迭代求解的随机优化算法。SA从一定的较高初始温度开始随着温度参数的不断减小随机求解空间中目标函数的全局最优解并结合概率跳跃特征。 Amylia Ait saadi[23]提出了一种基于混沌混合优化和模拟退火的混合优化方案CAOSA来解决无人机的路径规划问题。与其他九种经典的元启发算法相比其规划出的路径更短时间相对较短如图2-11与图2-12所示。
图2-11 经典九种算法和CAOSA算法规划路径长度 图2-12 经典九种算法和CAOSA算法规划时间 2.4.6 人工鱼群算法 通常来说,在任何水域中,鱼都能自行或尾随其他鱼找到营养物质丰富的地方。人工鱼群算法就是根据该特点,通过构造人工鱼来模仿鱼群的觅食、聚群和追尾以及鱼群之间的相互协助等自然行为,最终达到全局寻优的目的[25]。 人工鱼群算法通过生物界鱼类的3种自然行为进行相关迭代计算,从而获得路径规划最优解 。因此,该算法实际上也是一种仿生智能算法,每个人工鱼可以根据实时变化的环境因素自适应地调整角度进行搜索,最终使人工鱼聚集到食物源附近。因此,该算法与其他传统优化方法相比,在解决路径规划问题时能够良好地克服局部极值,并且具有一定的自适应能力。 接下来简要说明一下人工鱼群算法的基本含义。如图2-13所示,某一人工鱼当前的活动状态为XXX,首先假设它的最大视野范围为VisualVisualVisual。在该范围内某时刻人工鱼视点位置状态定义为XvX_vXv,如果该位置的状态优于当前状态,则向该位置方向前进一步,到达下一状态XnextX_{next}Xnext,否则继续搜索视野范围内的其他位置。如果搜寻的次数越多,则能对周围的环境有一个更加全面的感知,有助于作出合理的选择。另外,针对状态较多甚至无限多的情况,并不需要全部遍历,存在一定的不确定性对于搜索全局最优其实是更有利的。
图2-12 人工鱼群视觉模拟 通过观察,可以对鱼类行为作一个简单的分析,其主要分为以下4种行为。1)觅食行为:可以称为鱼类最基本的行为,简单来说,也就是循着食物较多的方向游动的一种行为 。2)聚群行为:这是它们的一种生存方式,或多或少的鱼总是聚集在一起,目的主要是为了躲避灾害和集体觅食。3)追尾行为:其实就是一种向邻近的最活跃个体靠近的行为,在寻优算法中可以认为为是向较优方向前进的过程 。4)随机行为:鱼在水中的游动行为,在某种程度上是随机的,最终目的是在更大的范围内寻找同伴以及食物。以上这些行为是鱼类的基本行为,它们与鱼的生存状态紧密联系。从学习方式上来说,觅食行为是一种个体极值寻优的过程,属于自学过程,而聚群与追尾行为是鱼和外界环境相互交互的过程。
2.4.7 人工蜂群算法 人工蜂群算法其实是由蜜蜂寻找食物源的过程启发而来的。该算法在求解路径规划问题时,蜜源代表一条可行路径,而蜜源的收益度代表该问题的约束条件(如时间、路径长度、避障情况等)。整体上来说,该算法就是一个迭代的过程 。该算法的基本模型主要涉及3种类型的蜜蜂:雇佣蜂、侦察蜂和观察蜂 。雇佣蜂在其当前处于的食物源附近进行局部搜索,若发现更优食物源,立刻更新所在位置。观察蜂则辅助雇佣蜂在食物源附近邻域搜索。当陷入局部最优情况时,雇佣蜂则转换为侦察蜂的角色,重新开始搜索。
2.4.8 入侵杂草算法 入侵杂草算法(invasive weed optimization)是一种模拟自然界杂草繁殖过程的一种新型智能优化方法,具有易于理解、参数少、稳定性高等优点。在农耕活动中,人们总会或多或少地残留一些多余的资源,杂草利用这些资源不断繁衍后代并占据其他的土地,产生更多的种子,这些种子又会继续繁殖下去。另外,杂草根据“适者生存”的法则,对环境条件适应性好的杂草将会生存下来,反之则被淘汰。受该自然现象的启发,Mehrabian和Lucas于2016年提出了一种新的智能优化方法—入侵杂草算法 。 在入侵杂草算法中,杂草代表路径规划问题的最优解,种群代表所有杂草的集合。在进化过程中,杂草通过不断繁殖产生种子,种子又陆陆续续发育成杂草,当种群中的杂草数量达到预先设定的最大种群规模时,则通过竞争法则来保存适应性好的杂草,淘汰适应性较差的 。
参考文献
[1] C. Badue, et al. Self-driving cars: A survey[J]. Expert Systems with Applications, 2021, 165. [2] Dijkstra, E. W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959,1(1), 269–271. [3] Hart, P. E., Nilsson, N. J., Raphael, B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics,1968, 4(2), 100–107. [4] Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R. F. Route planning in transportation networks[J]. arXiv preprint arXiv:1504.05140, 2015. [5] David González, Joshué Pérez, Vicente Milanés. A Review of Motion Planning Techniques for Automated Vehicles[J]. IEEE Transactions on intelligent transportation systems, vol. 17, NO. 4, april 2016. [6] Robert W. Floyd. Algorithm 97: Shortest path[J]. Communications of the ACM, 5(6):345, 1962. [7] 高佳佳. 基于全局地图的移动机器人路径规划研究[D].西安工业大学,2019.DOI:10.27391/d.cnki.gxagu.2019.000168. [8] Stentz. A. Optimal and efficient path planning for partially-known environnents[C]//Robotics and Automation, I994. Proceedings. 1994 IEEE International Conference on. IEEE,1994. [9] Dave Ferguson,Anthony Stentz. Using interpolation to improve path planning: The Field D* algorithm[J]. Journal of Field Robotics,2006,23(2). [10]肖国宝严宜辉.一种基于改进Theta*的机器人路径规划算法[J].智能系统学报2013,8(1):58-65. [11]Kavraki L E,Svestka,Petr,Latombe J C,et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Trans on Robotics Automation, 1994,12(4):566-580. [12]Lavalle S.Rapidly-exploring random trees : a new tool for path planning[J].Research Report,1998:293–308. [13]杨岱川文成林.基于蚁群和改进PRM算法的多目标点路径规划[J].杭州电子科技大学学报自然科学版20173∶63-67. [14]Belghith K,Kabanza F,Hartman L,et al.Anytime dynamic path-planning with flexible probabilistic roadmaps [C]//IEEE International Conference on Robotics and Automation (ICRA),Orlando,FL,15-22 May.2013,pp.2372-2377. [15]莫栋成刘国栋.改进的 RRT-Connect 双足机器人路径规划算法[J].计算机应用2013,33(08):2289-2292. [16]潘思宇徐向荣.基于改进RRT*的移动机器人运动规划算法[J].山西大学学报自然科学版2017402∶244-254. [17]Palmieri L, Koenig S, Kai O A. RRT-based nonholonomic motion planning using any-angle path biasing[C]/ IEEE International Conference on Robotics and Automation.ICRA,2016:2775-2781. [18]Holland, John. Adaptation In Natural And Artificial Systems[J]. University of Michigan Press, 1975. [19]Eberhart, R. C. and Kennedy, J. A new optimizer using particle swarm theory[J]. Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39-43, 1995. [20]Kennedy, J. and Eberhart, R. C. Particle swarm optimization[J]. Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995. [21]V. Garg, A. Shukla,R. Tiwari. AERPSO — An adaptive exploration robotic PSO based cooperative algorithm for multiple target searching[J]. Expert Systems with Applications, 2022, 209. [22]Y. Wan, et al. An Accurate UAV 3-D Path Planning Method for Disaster Emergency Response Based on an Improved Multiobjective Swarm Intelligence Algorithm[J]. IEEE Trans Cybern, 2022. [23]A. Ait-Saadi, et al. A novel hybrid Chaotic Aquila Optimization algorithm with Simulated Annealing for Unmanned Aerial Vehicles path planning[J]. Computers and Electrical Engineering, 2022, 104. [24]Brian Paden,Michal Cáp,Sze Zheng Yong,Dmitry S. Yershov,Emilio Frazzoli. A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles.[J]. IEEE Trans. Intelligent Vehicles,2016,1(1). [25]杜映峰,陈万米,范彬彬.群智能算法在路径规划中的研究及应用[J].电子测量技术,2016,39(11):65-70.DOI:10.19651/j.cnki.emt.2016.11.014.
