2. 中国科学院沈阳自动化研究所数字工厂研究室, 辽宁 沈阳 110016;
3. 中国科学院沈阳自动化研究所机器人学国家重点实验室, 辽宁 沈阳 110016
2. Digital Factory Research Office, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China;;
3. State key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
0 引言
无人机在三维环境下的路径规划问题是当前机器人领域的研究热点，路径规划是无人机自主导航的基本环节之一，它是指在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始状态到目标状态的最优路径的过程[1].路径规划的一般步骤可总结为环境建模、路径搜索、路径平滑三个环节，其中环境建模是将实际的空间环境信息抽象成计算机规划算法能处理的数学模型，因此环境建模是路径规划的基础，合理的环境建模对路径规划的最终效果有重要的影响[2].
无人机在三维环境下的建模方法[3-6]主要有几何建模法[7]、单元分解建模法[8]和拓扑建模法.单元分解建模法是将无人机飞行环境划分为若干单元，其中，传统栅格法是最通用的单元分解建模法之一，在环境建模过程中，利用传统栅格法描述的环境信息便于计算机存储与显示，栅格间的邻接关系简单直观，在实际应用中易于编写程序实现，与规划算法结合时能够获得更好的规划结果[7-10].
在国内外机器人路径规划领域，传统栅格法作为一种典型的环境建模方法，一直受到研究学者的广泛关注，随着环境信息的不断复杂以及机器人自主能力的不断提升，传统栅格法也面临着一些问题，分析众多研究，王伟峰等[11]将单元遍历的思想融入传统栅格法中，提高了传统栅格法的精确度，刘晓磊等[12]将传统栅格法运用于非结构环境的建模，并通过仿真实验验证了传统栅格法对复杂环境的适应性. Nakahashi[13]将传统栅格法应用于三维环境建模.上述研究将传统栅格法利用在三维环境建模问题中时，仍存在一定的问题.与二维环境相比，在三维环境中直接使用传统栅格法进行环境建模，考虑到环境建模的精度，要求栅格粒度应尽量小，因而使得栅格数量大幅增加，从而导致规划算法处理数量庞大的栅格数据，规划效率明显降低.
针对传统栅格法在三维环境建模时模型数据规模大且路径规划效率低的问题，本文提出一种高度降维的三维环境建模方法，该方法在保留了传统栅格法简单直观的基础上，实现了三维环境至二维环境的转化，大大减小了传统栅格法进行三维环境建模的栅格数量，同时可以很大程度上减小栅格粒度，增大了环境建模的精确程度，最后通过A*算法进行路径规划，通过仿真验证高度降维的三维环境建模方法的有效性.
1 高度降维的三维环境建模方法 1.1 传统栅格法进行三维环境建模的问题传统栅格法进行三维环境建模[14]，是将有限范围的三维规划空间分割成等大的单元，如图 1所示，将三维空间分割成n×n×n个栅格，每个栅格为一个立方体，实际情况下，若三维空间不是一个等高、等宽、等长的立方体，则在最小补充的情况下使其扩展成标准的立方体，将其扩展的部分作为障碍物栅格，进行环境建模.将每个栅格的中心作为规划算法的一个计算单位，其中包含障碍物的障碍物栅格赋值为1，不包含障碍物的自由栅格赋值为0.由此可知，n的取值越大，栅格越小，环境的分辨率越高.理论上来说，当n值足够大的情况下，传统栅格法所建立的环境模型可以无限趋近于真实规划空间，传统栅格法建立的环境模型精度越高；反之，n值越小，栅格越大，环境分辨率越低，传统栅格法建立的环境模型精度越低.
|
| 图 1 传统栅格法空间分割图 Figure 1 Space segmentation diagram by traditional grid method |
在完成环境建模的基础上，利用规划算法进行路径规划的过程中，如果栅格数量越多，环境分辨率越高，规划算法的准确率越高，因此规划算法所计算的最优路径越接近于理论的最优路径，但由于规划算法计算的单元数量庞大，路径规划的效率将大大降低，同时，当栅格数过大，规划算法往往容易陷入组合爆炸的情形，如果栅格数量少，规划算法的搜索效率高，但往往无法在密集障碍物的环境下规划出有效路径.
相比二维环境，在利用传统栅格法针对无人机三维规划空间进行环境建模时，栅格数量将会呈现倍数的增加，规划算法在建立的环境模型中的效率将会大大降低，这种情况下若要提升规划算法在环境模型中的效率，唯一途径是减小n值，降低环境分辨率，此时环境建模的精度和规划算法的准确率将明显下降，规划的最优路径准确度无法满足要求.
对于环境建模的精度与规划算法效率冲突的问题，通常的解决方案是采用四叉树或八叉树法来进行单元分解[15]，在三维环境建模问题中，通常将所有栅格划分成8个单元，并将栅格分为自由栅格、障碍物栅格、包含一部分障碍物的混合栅格，对每个单元进行判断并将单元内的混合栅格进行继续划分，直到所有子单元都只包含自由栅格与障碍物栅格为止.这种方法在一定程度上克服了传统栅格法的缺陷，但是该方法改变了栅格的均匀性，相邻栅格间的关系复杂度提升，在障碍物边缘的判断与建模过程中耗费了计算时间，增加了建模的复杂度，同时该方法并没有从根本上减少栅格数量，无法有效提高规划算法在精确环境模型上的处理效率.根据上述分析，利用传统栅格法进行环境建模时存在的问题即是无法克服环境描述精度与规划算法效率冲突的矛盾.
1.2 高度降维的三位环境建模方法 1.2.1 高度降维的三维环境建模流程及分析针对传统栅格法存在的问题，本文在传统栅格法的基础上，提出高度降维的三维环境建模方法，该方法的流程为：
步骤1 首先建立三维坐标，设定起始点及目标终点的坐标，并用传统的传统栅格法处理三维环境，如图 2举例所示，使用传统栅格法将三维环境分割成30×30×30个栅格，包含障碍物的栅格赋值为1，并用深色处理，不包含障碍物的栅格赋值为0，用浅色处理，每个单位栅格的中心将作为该栅格的坐标.
|
| 图 2 初始环境设置 Figure 2 Setting of initial environment |
步骤2 按照上述步骤完成对三维环境的初步处理之后，过起始点及目标终点，生成垂直于yz平面的平面F，如图 3所示，平面F包含起始点S与目标终点E，并切过高度高于平面F的障碍物栅格.
|
| 图 3 建立平面F Figure 3 Building plane F |
步骤3 经过上述两个步骤处理后，用传统栅格法对该二维平面F进行处理，如图 3所示，平面F分割成栅格的过程，实际是将xy平面的二维栅格映射至F平面，平面F的单位栅格大小由平面F与xy平面的夹角和xy平面的单位栅格大小确定.平面F与高于该平面的三维障碍物栅格形成的切面即作为平面F的二维障碍物栅格，其余部分将作为平面F的二维自由栅格.
为了清晰描述平面F中障碍物栅格的判断方法，并分析该处理方式在起始点S与目标终点E三种不同高度情形下的计算原理，给出定义：
1) 起始点S(Sx, Sy, Sz)及起始点在yz平面的投影点S1(Sy, Sz).
2) 目标终点E(Ex, Ey, Ez)及目标终点在yz平面的投影点E1(Ey, Ez).
3) 平面F上的任意一点P(Px, Py, Pz)，该点在yz平面的投影点P1(Py, Pz).
4) 平面F与xy平面所成的锐角α.
5) S1与E1连线的延长线与y轴的交点C(Cy, 0).
6) 三维障碍物栅格坐标B(Bx, By, Bz).
起始点S与目标终点E三种不同高度情形包括起始点高度大于目标终点高度、起始点高度小于目标终点高度、起始点与目标终点高度一致.
如图 4所示，该图是传统栅格法处理后的三维环境，起始点高度大于目标终点高度.
|
| 图 4 建立起始点高度高于终点高度的初始环境 Figure 4 Initial environment with higher start point |
过起始点及目标终点，生成垂直于yz平面的平面F，如图 5所示，图 6为起始点S、终点E、平面F及该平面上的任意一点在yz平面的投影图.
|
| 图 5 建立起始点高度高于终点高度的平面F Figure 5 Building plane F with higher start point |
|
| 图 6 平面F在yz平面的投影图 Figure 6 The projection drawing on yz plane |
分析图 6可得出锐角α的正切值，
|
(1) |
图 7描述的是起始点高度低于目标终点高度情形下，利用传统栅格法处理后的三维环境.
|
| 图 7 起始点高度低于目标终点高度的初始环境 Figure 7 Initial environment with higher end point |
过起始点及目标终点，生成垂直于yz平面的平面，如图 8所示，图 9为起始点、终点、平面及该平面上的任意一点在yz平面的投影图.
|
| 图 8 建立起始点高度低于终点高度的平面F Figure 8 Building plane F with higher end point |
|
| 图 9 起始点高度低于目标终点高度的投影图 Figure 9 The projection drawing with higher end point |
在此情形下，
|
(2) |
起始点与目标终点一致的情形如图 2和图 3所示，在此情形下，平面F平行于xy平面，Pz=Ez=Sz.
综合上述三种情形的分析及式(1)、式(2)的描述，当已知起始点S(Sx, Sy, Sz)及目标终点E(Ex, Ey, Ez)时，平面F中任意一点P(Px, Py, Pz)的坐标满足关系：
|
(3) |
遵循步骤3中的方法将平面F分割成二维栅格后，遍历步骤1的三维障碍物栅格，设平面F中某点坐标Px=Bx，Py=By，代入式(3)可求得Pz，此时若Pz>Bz，则平面F上以点S(Sx, Sy, Sz)为中心的栅格为自由栅格，若Pz < Bz，则平面F上以点P(Px, Py, Pz)为中心的栅格为障碍物栅格.
设三维单位栅格的大小为a×a×a的正方体.在完成上述步骤后，平面F的单位栅格将变为大小为a×(a/cosa)的长方形.
1.2.2 高度降维的三维环境建模方法的效果对于上文描述的3种情况，通过高度降维的三维环境建模方法建立二维环境模型的最终效果如图 10所示.相比传统栅格法而言，高度降维的三维环境建模方法降低了空间高度坐标这一维度，在传统栅格法的基础上，将规划空间从三维环境转化成二维平面，如果按照步骤1中描述的方法，传统栅格法将三维空间分割成27 000个三维栅格，经过高度降维后，规划算法只需处理平面F中的900个二维栅格，栅格数量大大减小.
|
| 图 10 最终建模效果 Figure 10 The final result of environment mode |
高度降维的三维环境建模方法在降低维度并减少栅格数量的基础上带来2个好处：第一，规划算法在进行三维路径规划时所考虑的环境转换成了二维平面，计算处理的栅格数量减少，规划算法的计算复杂度降低，规划效率提升.因此如果在步骤1中，适当增加三维栅格的数量，提升对环境描述的精度，再通过高度降维的三维环境建模方法进行处理，降低环境维度并减少栅格数量，在提升环境描述精度的同时也能满足规划算法的效率要求，弥补传统栅格法的不足.第二，如图 10所示，通过高度降维的三维环境建模方法生成的平面F作为规划算法处理的环境模型，该平面忽略了一部分高度较低且对飞行器飞行路径无影响的障碍物，规划算法在对该二维平面的环境模型进行计算的过程中，避免了不必要的计算，该方法在这一方面也能相应地提升规划算法的效率.
2 基于A*算法的全局路径规划 2.1 A*算法的原理依据前文描述，将上文提出的高度降维的三维环境建模方法所建立的二维栅格平面F作为A*算法的规划环境模型[16-17]，二维栅格平面中的单位栅格作为A*算法搜索的节点，在A*算法中，可以通过设置合理的启发函数，从而选择代价值最小的节点作为下一步待搜索的节点.
A*算法[18-20]的本质是贪心算法与启发式搜索算法[21-23]的结合，所以A*算法结合了贪心算法以及启发式搜索算法的优点，继承了二者的特性[24].与传统的贪心算法相比，A*算法因为具备最佳优先搜索算法的启发式性质，因此可以通过设计合理的代价函数，利用这个特点，A*算法可以选择代价最少并且当前局部最优的节点作为待搜索或待扩展的节点[25].
在路径规划问题上，A*算法作为启发式算法，具有很高的搜索效率，同时A*算法在运算过程中所具备的贪心算法的性质能够保证算法在规划环境内找到最优解，即如果路径规划环境中从起始点到目标终点的最优路径存在，那么A*算法在环境建模准确和算法自身的代价函数设计合理的情况下，能快速有效地搜索到一条最优路径.
A*算法的核心在于代价函数的设计，代价函数的通用表达式如式(4)所示.
|
(4) |
其中，f(n)为每个节点的代价函数；g(n)表示起始点到节点n的代价；h(n)表示从节点到目标点的启发函数，针对不同情形的问题，应重点设计启发函数h(n).当h(n)设计为小于等于当前节点到目标终点的真实最小代价，A*算法在理论上就能在规划空间内找到最优路径，因为当前节点到目标终点的真实最小代价事先无法估计与计算，且h(n)要求与真实代价最大限度地接近，因此要保证A*算法寻路的准确性，h(n)必须结合实际问题本身精心设计.
2.2 A*算法的全局路径规划的实现 2.2.1 算法代价函数的确定及实现流程为了计算g(n)与h(n)，需要选定两点之间距离的计算方法，最常见的几种距离算法：曼哈顿距离、对角线距离及欧几里得[26]距离.在本文讨论的无人机路径规划问题中，在环境模型即平面F中，规定无论无人机处于任一栅格，其可以向当前栅格的四周栅格运动，因此在计算g(n)与h(n)的过程中，选用欧几里得距离计算栅格之间的距离，以二维平面为例，欧几里得距离计算方式如式(5)所示，其中Dist表示两点之间距离，两点坐标为(x1, y1)和(x2, y2).
|
(5) |
设在无人机当前节点为m，在节点m的邻域上有n个待选节点k，k=1, 2, 3, …, n, 其中在二维平面F上节点k的空间坐标为(kx, ky, kz)，目标终点E(Ex, Ey, Ez)，g(m)为起始点到节点m的代价值，在平面F上利用A*算法进行路径规划的代价函数设计如式(6)~式(8)所示.
|
(6) |
|
(7) |
|
(8) |
A*算法在路径规划问题中的实现流程和总结为：从起始点开始，搜索邻域节点内代价函数值最小的点，逐步向外扩展，直至算法搜索到终点结束.
首先从起始点开始，将起始点存入开启集并扫描其邻域内的所有节点，计算邻域内所有节点中自由栅格节点的f(k)值，并存入开启集中，完成对起始点的节点扩展，将起始点从开启集中删除加入关闭集.选取在开启集中f(k)值最低的待选节点作为临时路径点，将当前节点的指针指向新节点，完成第二个临时路径点建立，此后开始新的节点扩展，流程如图 11所示.
|
| 图 11 A*算法节点扩展流程图 Figure 11 The process of A* algorithm node expansion |
按照上述流程，当A*算法搜索至目标终点时，从目标终点开始，按照各节点的父节点指针进行回溯，直到扫描到起始点，完成路径规划.
2.2.2 仿真验证仿真验证的规划环境采用第1小节中所模拟的三维环境，在起始点高度等于终点高度、起始点高度高于终点高度、起始点高度低于终点高度三种情形下的起始点与终点坐标信息如表 1所示.
| 起始点坐标 | 终点坐标 | |
| 起始点高度等于终点高度 | (2，2，6) | (17，26，6) |
| 起始点高度大于终点高度 | (2，2，6) | (17，26，3) |
| 起始点高度小于终点高度 | (2，2，3) | (17，26，6) |
在建立的模拟三维环境下，通过第1小节中提出的“高度降维的三维环境建模方法”建立了环境栅格平面，利用A*算法在该栅格平面上进行全局路径规划仿真，仿真效果如图 12所示.
|
| 图 12 仿真结果 Figure 12 Simulation result |
图 12(a)~图 12(c)表示在相同三维环境下，起始点高度与目标终点高度不同所产生的不同环境模型的规划结果.在起始点高度等于终点高度(图 12(a))、起始点高度高于终点高度(图 12(b))、起始点高度低于终点高度(图 12(c))的三种情形下，针对同一三维环境降维后产生的环境模型不相同，路径规划的最终效果也不同.
2.2.3 高度降维的三维环境建模方法与传统栅格法的实验效果对比通过上述仿真实验，设三维单位栅格的大小为n×n×n，由1.2.1节叙述可得，降维后生成的环境模型平面F单位栅格大小为n×(n/cosa)，在仿真实验中，假设三维规划空间的大小为300 m×300 m×300 m的立方体，由此在不同情形下通过高度降维的三维环境建模方法得出的全局规划的路径长度与时间，对比传统栅格法[27]进行环境建模时得出的实验效果，结果如表 2~表 4所示.
| 高度降维后规划时间/ms | 传统栅格法规划时间/ms | 高度降维后规划路径长度/m | 传统栅格法规划路径长度/m | |
| 起始点高度等于终点高度 | 5.896 | 71.588 | 287.99 | 301.17 |
| 起始点高度高于终点高度 | 6.023 | 77.475 | 296.13 | 324.34 |
| 起始点高度低于终点高度 | 6.107 | 83.298 | 302.03 | 345.22 |
| 降维后规划时间/ms | 传统栅格法规划时间/ms | 降维后规划路径长度/m | 传统栅格法规划路径长度/m | |
| 起始点高度等于终点高度 | 7.365 | 89.734 | 257.91 | 286.38 |
| 起始点高度高于终点高度 | 7.772 | 97.126 | 261.38 | 303.72 |
| 起始点高度低于终点高度 | 8.018 | 108.835 | 273.56 | 328.30 |
| 降维后规划时间/ms | 传统栅格法规划时间/ms | 降维后规划路径长度/m | 传统栅格法规划路径长度/m | |
| 起始点高度等于终点高度 | 11.826 | 134.132 | 218.43 | 252.73 |
| 起始点高度高于终点高度 | 12.234 | 151.573 | 226.52 | 277.87 |
| 起始点高度低于终点高度 | 12.943 | 170.625 | 235.20 | 291.19 |
表 2为通过高度降维后的环境建模方法与传统栅格法将三维空间分割成30×30×30个栅格得出的实验结果.分析实验结果得知，在规划时间和路径规划长度方面，从环境模型的精度还有规划算法的处理效率两个方面来分析，起始点高度等于目标终点高度的情形下，路径规划的最终效果较好.而起始点高度低于目标终点高度的情形下，路径规划的最终效果较差，在起始点高度高于目标终点高度的情形下，路径规划的最终效果一般.在三种情形中，经过高度降维的二维平面环境模型下的规划时间比传统栅格法在三维环境模型的时间少.在此基础上，二维规划的路径长度比三维规划的路径长度短.由此看出，将三维空间分割成30×30×30的情况下，经过高度降维的三维环境建模方法相比于传统栅格法在规划算法中处理效率更高，路径规划的效果更好.
表 3为通过高度降维后的环境建模方法与传统栅格法将三维空间分割成50×50×50个栅格得出的实验结果.分析实验结果得知，将三维空间分割的越精细，得到的栅格数量越多，环境分辨率越高，环境模型精度越高，规划算法的准确率越高.但是在传统栅格法进行环境建模时，规划的时间增加较多，导致规划算法的处理效率将明显下降.相比于表 2中的实验结果得知，当三维空间分割由30×30×30个栅格变为50×50×50个栅格时，经过高度降维的三维环境建模方法比传统栅格法增加的规划时间少而且减小的规划路径长度多.
表 4为通过高度降维后的环境建模方法与传统栅格法将三维空间分割成100×100×100个栅格得出的实验结果.分析实验结果并结合表 2与表 3的实验结果得出，经过高度降维的三维环境建模方法相比于传统栅格法在提高环境模型精度的同时，增加的规划时间更少而且减小的规划路径长度更多.进一步验证将三维空间分割的越精细时，经过高度降维的三维环境建模方法比传统栅格法路径规划的最终效果更好.
综上所述，经过高度降维的三维环境建模方法在保留了栅格法简单直观的基础上，实现了三维环境至二维环境的转化，大大减小了传统栅格法进行三维环境建模的栅格数量，因此可以更加精细地切分规划空间，增大了环境建模的精确程度，在提升环境描述精度的同时也能满足规划算法的效率要求，弥补传统栅格法的不足.
3 结论传统栅格法用来构建无人机路径规划三维环境模型时无法克服环境描述精度与规划算法效率的冲突.针对上述问题，本文提出一种高度降维的三维环境建模方法，试图降低路径规划方法对三维环境建模精度的依赖性.与传统栅格法相比，本文提出的方法通过降维操作实现了三维环境建模的二维化处理，同时将无人机的三维路径规划巧妙转化成二维环境下的规划，解决了环境建模精度与算法实时性的矛盾问题.通过A*算法实现了降维环境下的路径规划仿真，验证了本文所提三维环境建模方法的有效性.下一步将开展包含动态和静态障碍物的室内环境无人机路径规划实验，验证路径规划方法的优化性和实时性.
| [1] |
李妍, 陈欣, 李春涛.
无人机飞行控制计算机4通道FlexRay总线通信与余度管理设计[J]. 信息与控制, 2017, 46(3): 318–327.
Li Y, Chen X, Li C T. Design of 4 channel FlexRay bus communication and redundancy management for UAV flight control computer[J]. Information and Control, 2017, 46(3): 318–327. |
| [2] | Wang G G, Chu H C E, Mirjalili S. Three-dimensional path planning for UCAV using an improved bat algorithm[J]. Aerospace Science & Technology, 2016, 49(1): 231–238. |
| [3] | Coveney S, Roberts K. Lightweight UAV digital elevation models and orthoimagery for environmental applications:Data accuracy evaluation and potential for river flood risk modelling[J]. International Journal of Remote Sensing, 2017, 38(8/9/10): 3159–3180. |
| [4] |
王幼琴, 赵忠盖, 刘飞.
一种间歇过程多批次融合线性变参数建模方法[J]. 信息与控制, 2017, 46(1): 46–52.
Wang Y Q, Zhao Z G, Liu F. A multi batch fusion linear modeling method for batch process[J]. Information and Control, 2017, 46(1): 46–52. |
| [5] | Aguilera P A, Fernández A, Fernández R, et al. Bayesian networks in environmental modeling[J]. Environmental Modelling & Software, 2012, 26(12): 1376–1388. |
| [6] | David O, Ascough Ii J C, Lloyd W, et al. A software engineering perspective on environmental modeling framework design:The object modeling system[J]. Environmental Modelling & Software, 2013, 39(1): 201–213. |
| [7] | Zhang Y J. Geometric modeling and mesh generation from scanned images[J]. International Journal of Radiation Biology & Related Studies in Physics Chemistry & Medicine, 2016, 17(17): 449–58. |
| [8] |
何雨枫. 室内微小型无人机路径规划算法研究[D]. 南京: 南京航空航天大学, 2014: 249-283. He Y F. Study on the path planning algorithm for indoor micro UAV[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2014: 249-283. |
| [9] |
曾辰, 许瑛.
一种蜂巢栅格下机器人路径规划的蚁群算法[J]. 机械科学与技术, 2016, 35(8): 1308–1312.
Zeng C, Xu Y. A kind of ant colony algorithm for path planning of honey beetle under grid[J]. Mechanical Science and Technology, 2016, 35(8): 1308–1312. |
| [10] |
吴国松, 倪宏, 赵海丽, 等.
一种改进的栅格法航迹巡线方法研究与实现[J]. 技术与市场, 2017, 24(8): 31–32, 35.
Wu G S, Ni H, Zhao H L, et al. Research and realization of an improved method of line inspection by raster method[J]. Technology and market, 2017, 24(8): 31–32, 35. |
| [11] | Wang W F, Wu Y C, Zhang X, et al. Research of the unit decomposing traversal method based on grid method of the mobile robot[J]. Techniques of Automation & Applications, 2013: 34–38. |
| [12] | Liu X L, Jiang L, Jin Z, et al. Mobile robot path planning based on environment modeling of grid method in unstructured environment[J]. Machine Tool & Hydraulics, 2016: 1–7. |
| [13] | Nakahashi K, Deiwert G S. Three-dimensional adaptive grid method[J]. AIAA Journal, 2015, 24(6): 948–954. |
| [14] | Jr Lermusiaux P J H, Yilmaz N K. Environmental prediction, path planning and adaptive sampling:Sensing and modeling for efficient ocean monitoring, management and pollution control[J]. Sea Technology, 2007, 48(9): 254–259. |
| [15] | Liu M. Robotic online path planning on point cloud[J]. IEEE Transactions on Cybernetics, 2016, 46(5): 1217–1228. DOI:10.1109/TCYB.2015.2430526 |
| [16] | Tsai C C, Huang H C, Chan C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[J]. IEEE Transactions on Industrial Electronics, 2011, 58(10): 4813–4821. DOI:10.1109/TIE.2011.2109332 |
| [17] | Kadayif I, Kandemir M. Intelligent mining for path planning using evolutionary algorithms and artificial neural network for UAV[J]. ACM Transactions on Embedded Computing Systems, 2015, 4(5): 388–414. |
| [18] | Zafar K, Baig A R, Badar S, et al. Multi agent based mine detection and route planning using learning real time A* algorithm[C]//International Conference on Computer Science and ITS Applications. Piscataway, NJ, USA: IEEE, 2010: 1-7. |
| [19] | Ye X, Han S P, Lin A. A note on the connection between the primal-dual and the A* algorithm[J]. International Journal of Operations Research & Information Systems, 2017, 1(1): 73–85. |
| [20] | Kala R, Shukla A, Tiwari R. Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning[J]. Artificial Intelligence Review, 2010, 33(4): 307–327. DOI:10.1007/s10462-010-9157-y |
| [21] | Rasmussen S J, Shima T, Mitchell J W, et al. State-space search for improved autonomous UAVs assignment algorithm[C]//Proceedings of the 2004 IEEE Conference on Decision and Control. Piscataway, NJ, USA: IEEE, 2004: 2911-2916. |
| [22] | Kahveci N, Ioannou P, Mirmirani M. A heuristic search algorithm for maneuvering of UAVs across dense thermal areas[C]//AIAA Guidance, Navigation and Control Conference and Exhibit. Keystone, CO, USA: AIAA, 2013: 309-314. |
| [23] | Lin L, Goodrich M A. Hierarchical heuristic search using a gaussian mixture model for UAV coverage planning[J]. IEEE Transactions on Cybernetics, 2014, 44(12): 2532–2544. DOI:10.1109/TCYB.2014.2309898 |
| [24] | Barron A R, Cohen A, Dahmen W, et al. Approximation and learning by greedy algorithms[J]. Annals of Statistics, 2008, 36(1): 64–94. DOI:10.1214/009053607000000631 |
| [25] | Noy E, Goldblum A. Flexible protein-protein docking based on best-first search algorithm[J]. Journal of Computational Chemistry, 2010, 31(9): 1929–1943. |
| [26] | Shrivastav A, Nalwaya B, Kumar S, et al. Improvement on initial seed selection for k-means algorithm[J]. International Journal of Pharmacy & Technology, 2016, 8(4): 26000–26005. |
| [27] | Thakar M K, Sharma T. Digital grid method for fingerprint identification and objective report writing[J]. Egyptian Journal of Forensic Sciences, 2016, 6(2): 194–201. DOI:10.1016/j.ejfs.2016.05.008 |