基于A星算法的无人机路径规划优化模型研究

在分析传统无人机路径规划方法应用局限的基础上,针对传统A星算法启发函数单一、拐点冗余,以及效率不够高等系列问题,以虚拟城市地理环境为研究背景,通过提出面向起讫节点方位角的A星算法加速优化、启发式搜索中动态加权重构评价函数的A星算法加速优化和顾及Floyd算法插点策略的A星算法路径优化等层次递进的算法优化策略,解决了对A星算法搜索方向的量化约束、搜索权重数值的优化重构及冗余拐点的插点删除等技术问题,实现了改进后的A星算法运行效率的显著提高及最短路径判定准确性的明显提升。     

一种基于道路网分层的最短路径算法

D ijkstra算法是求解最短路径的经典算法,A*是目前最流行的启发式搜索算法,分析了这两种算法的搜索空间和时间复杂度。在此基础上,提出了一种基于道路网分层最短路径算法。实验证明:该算法是一种效率好、实用性强的最短路径算法。     

基于蚁群算法深海采矿机器人工作路径规划

针对深海采矿机器人路径规划问题,提出一种适合于采矿作业的改进蚁群算法。该算法利用位图法建立环境模型,依据构型空间的思想将路径规划问题简化为质点运动问题;利用改进的蚁群算法对问题进行描述,蚁群搜索中采用邻居搜索原则和中线偏移策略。最后通过仿真实验表明,该算法精度高,在海底环境中,能够完成机器人采矿作业的要求。     

基于改进量子粒子群算法的AUV路径规划研究

针对海洋环境下自主水下机器人（AUV）的路径规划问题,提出了一种基于框架四叉树的改进量子粒子群算法（QPSO）,首先使用框架四叉树的方法对障碍物建模,该方法提高了建模的精度且对后续算法的效率也有极大的改进,之后设计改进的量子粒子群算法,并且结合水下环境的特殊性设计适应度函数,综合考虑航线路径长度、偏转角度以及海流影响,使得算法可以在水下环境中寻得能耗最短的解路径。最后通过仿真试验验证,相比于传统的栅格法和粒子群算法,改进量子粒子群算法的运算时间更短,收敛速度更快,其独特的适应度函数可以使AUV能更好适应水下多变的环境,且能利用海流设计能耗更小的路径,具有很大的实用价值。     

最短时间航线自动生成的改进方法

针对已有的最短时间航线自动生成算法存在搜索效率较低、航线准确度较低的不足,提出了基于瞬时水深模型的最短时间航线自动生成改进算法。利用无效点定义和动态包络矩形的策略,优化最短时间航线生成;采用高精度的瞬时水深模型提高最短时间航线自动生成的准确度。实验结果表明:此方法与已有的方法相比,在自动生成航线的质量和效率上都有明显的提高。     

一种基于改进蚁群优化算法的载人潜水器全局路径规划

基础蚁群优化算法在解决复杂障碍环境下的载人潜水器路径规划问题时,易过早收敛于局部最优解,信息素挥发系数的设置过于依靠经验,路径规划结果受概率影响大且不稳定。为此,提出了一种改进蚁群算法用于解决载人潜水器的全局路径规划问题。该算法提出"路径延伸块"的概念。算法前期采用动态更新信息素参数的蚁群优化算法进行简单迭代计算获得原始路径,并对原始路径进行栅格延伸以得到"路径延伸块";后期在路径延伸块中再次使用蚁群算法或其他寻优算法(Dijkstra算法)寻找最优路径。改进的算法与基础蚁群优化算法相比,算法效率及稳定性更高,不易收敛于局部最优解,能更好地适应U型槽环境和复杂障碍环境。     

无人水面航行器全局路径规划方法研究

针对无人水面航行器(unmanned surface vehicle,USV)的路径规划问题,提出了基于粒子群优化算法(particle swarm optimization,PSO)和费马螺旋曲线(Fermat’s spiral,FS)的全局路径规划算法。首先,采用PSO全局路径规划算法,搜索航路点序列并将其顺序连接,以获得可行、最短且绝对安全的折线路径。其次,利用FS曲率可从零变化且连续的特点,设计FS光顺折线路径策略,使得所规划路径的方位和曲率均为连续函数,进而可应用于精确的路径跟踪等运动控制中。考虑到USV的机动性能限制,在FS过渡曲线设计中加入了最小回转半径约束。仿真结果表明,本文所提方法能够生成一条满足USV自身机动性能限制,且方位和曲率均为连续函数的可行光滑路径,从而能够使得USV实现真正意义上的完全自主航行。     

一种求解旅行商问题的改进蚁群算法

提出一种求解旅行商问题的改进蚁群算法。该算法在信息素更新过程中,利用信息素局部更新和全局动态更新结合的方法,使得当前最优路径上的信息素值能够动态地调配,避免算法陷入停滞状态;在局部搜索过程中,仅对部分走出更优路径的售货员使用2-opt方法,加快了最优解的收敛速度。仿真实验验证了算法的有效性,与其它算法相比,本文算法在解的质量和收敛速度上都显示出了良好的性能。     

面向多区域高效搜索的UUV集群任务分配

UUV 集群在执行大范围搜索任务时分配方案的优劣对于提高任务执行效率至关重要。研究解决 UUV 集群同时进行多区域搜索中的任务分配问题,使得全部区域搜索完成时长最小。针对传统匈牙利算法无法高效解决不平衡任务分配的问题,提出一种改进匈牙利多轮分配算法。该算法通过多轮任务分配,实现空闲 UUV 高效利用和目标区域合理分配,通过在代价函数中引入边际代价和保守估计时长,大大减小了全部区域搜索完成时长。仿真实验结果表明：提出的算法相比传统匈牙利算法能够合理分配空闲 UUV,提高分配效率。此外,相较于仅采用搜索时长为代价函数,在代价函数中引入边际代价和保守估计时长能够针对耗时长的区域最大限度缩短搜索时长,保证随着 UUV 数量的增加,全部区域搜索完成时长单调递减。     

基于无向图Floyd加速模型的海图抽选方法研究

为解决传统海图抽选存在的主观性高和抽选效率低的问题,尝试将图论中的Floyd算法应用到海图抽选问题中,通过在无向图多路径数据结构中对Floyd算法进行加速改进,提出了一种基于无向图Floyd加速模型的海图抽选方法。该方法通过对网络图及算法进行优化,实现了抽选海图航路覆盖范围的最大化和抽选海图数量的最小化,并将时间复杂度降至O(1/2(n)(n-1)~2);通过利用基于等价点数组的最短路径集算法,实现了同等海图数量前提下的不同海图选取方案。最后通过实验验证了上述模型在海图选取中的可行性和优越性。     

Smoothed A* algorithm for practical unmanned surface vehicle path planning

An effective path planning or route planning algorithm is essential for guiding unmanned surface vehicles (USVs) between way points or along a trajectory. The A* algorithm is one of the most efficient algorithms for calculating a safe route with the shortest distance cost. However, the route generated by the conventional A* algorithm is constrained by the resolution of the map and it may not be compatible with the non-holonomic constraint of the USV. In this paper an improved A* algorithm has been proposed and applied to the Springer USV. A new path smoothing process with three path smoothers has been developed to improve the performance of the generated route, reducing unnecessary ‘jags’, having no redundant waypoints and offering a more continuous route. Both simulation and experimental results show that the smoothed A* algorithm outperforms the conventional algorithm in both sparse and cluttered environments that have been uniformly rasterised. It has been demonstrated that the proposed improved A* route planning algorithm can be applied to the Springer USV providing promising results when tracking trajectories.     

一种改进的水下声学定位算法

通过分析讨论泰勒级数展开法和Chan算法的优缺点,提出了一种先由Chan算法解算求得初始参考值,再由泰勒级数展开法在该初始值处展开进行迭代求解的协同定位算法。通过实验,将本方法与传统定位算法(泰勒法)、Chan算法进行对比。结果表明,该方法无需额外提供初始值,解算出较好的结果的同时且能保持良好的时间效率。通过此方法,在实际生产作业中可节约定位时间,改善定位精度。     

电子海图最优航线自动生成算法的改进

从航路二叉树的构建、可操作性质量评价指标的构建以及最短距离航线算法与最短时间航线算法相结合三方面,初步探讨了航线自动生成的改进算法,以得到更合理和实用的航线。     

Parallel trajectory planning for shipborne Autonomous collision avoidance system

Collision at sea is always a significant issue affecting the safety of ship navigation. The shipborne autonomous collision avoidance system (SACAS) has the great advantage to minimize collision accidents in ship navigation. A parallel trajectory planning architecture is proposed in this paper for SACAS system. The fully-coupled deliberative planner based on the modified RRT algorithm is developed to search for optimal global trajectory in a low re-planning frequency. The fully-coupled reactive planner based on the modified DW algorithm is developed to generate the optimal local trajectory in a high re-planning frequency to counteract the unexpected behavior of dynamic obstacles in the vicinity of the vessel. The obstacle constraints, ship maneuvering constraints, COLREGs rules, trajectory optimality, and real-time requirements are satisfied simultaneously in both global and local planning to ensure the collision-free optimal navigation in compliance with COLREGs rules. The on-water tests of a trimaran model equipped with a model-scale SACAS system are presented to demonstrate the effectiveness and efficiency of the proposed algorithm. The good balance between the computational efficiency and trajectory optimality is achieved in parallel trajectory planning.     

Huffman与LZW算法在海洋观测浮标通信数据压缩中的应用研究

在现有两种比较主流无损压缩算法基础上(Huffman算法和LZW算法),根据海洋观测浮标采集的观测数据特点,比较两种压缩算法的优缺点,并通过布放在西太平洋海域的一套观测浮标数据进行数据验证。结果表明,使用Huffman算法和LZW算法分别对海洋观测浮标数据进行压缩,两者的压缩率都基本可达50%左右甚至更低,Huffman算法压缩率较优,而LZW算法复杂度较优。通过分析,可证明这两种无损压缩算法都能有效地提高深远海通信效率和降低通信成本,同时也提高了科学观测数据的安全性和保密性,可根据实际情况选择在深远海观测浮标数据通信中应用。     

利用CUBE算法剔除多波束测深粗差研究

针对国内基于不确定度信息处理多波束测深数据相对滞后现状,将CUBE算法应用于大批量多波束测深粗差剔除研究。通过与人工交互编辑结果对比,表明CUBE算法剔除粗差效率较高并能保证测深成果质量,具有较高的推广应用价值。该研究对进一步优化我国多波束测深粗差处理算法也具有重要意义。     

基于辛几何算法的高斯束叠前深度偏移

辛几何算法是专门针对动力学过程设计的算法,以提高动力学问题求解的精度与效率。高斯束偏移过程中的运动学与动力学射线追踪,从物理上讲是一个动力学过程,可以利用辛几何算法对其进行优化。本文将基于辛几何算法的运动学射线追踪引入高斯束叠前深度偏移中,并在推导了动力学射线追踪方程组的辛差分格式基础上,实现了基于辛几何算法的高斯束叠前深度偏移。模型实验表明,基于辛几何算法的运动学射线追踪,其效率与精度相比常规算法都具有一定优势,而基于辛几何算法的高斯束叠前深度偏移方法能够对复杂构造模型精确成像。