D-P算法的改进及其在飞行轨迹回放中的应用

飞行参数记录了飞行器飞过的位置、姿态和飞行状态,飞行结束后,对飞行参数进行可视化回放,无论是实际的飞行训练中,还是飞行仿真中都是必不可少的,但在回放时,如果逐点显示这些数据,将会消耗大量的系统资源.本文提出一种基于限定俯仰角和航向角变化率的道格拉斯—普克(Douglas-Poiker,D-P)压缩算法对将要显示的轨迹点进行压缩,并对算法进行了验证,效果良好.     

曲线数据压缩算法的研究及应用

针对经典的道格拉斯-普克数据压缩算法存在递归计算效率低、阈值选取不确定等不足，提出了一种改进的特征点提取方法，该算法通过直方图统计数据点的频数，根据数据点到基线的距离、数据点与相邻数据点间的夹角，考虑数据点的“孤立性”和频数，利用熵值法确定最终评价值，自动按照给定数据压缩率进行曲线数据压缩.在MATLAB上进行了仿真实验，利用自主研发的控制系统平台，对进油计量阀流量特性进行增量自学习，并在油泵台架和发动机台架上完成了相应的实验.实验结果表明，本算法可以有效的对数据进行压缩处理，满足测量系统和控制系统的数据压缩需求.     

依概率收敛的改进粒子群优化算法

粒子群优化算法是一种随机优化算法,但它不依概率1收敛到全局最优解。因此提出一种新的依概率收敛的粒子群优化算法。在该算法中,首先引入了具有探索和开发能力的两个变异算子,并依一定概率对粒子当前最好位置应用这两个算子,然后证明了该算法是依概率1收敛到ε-最优解。最后,把该算法应用到13个典型的测试函数中,并与其他粒子群优化算法比较,数值结果表明所给出的算法能够提高求解精度和收敛速度。     

基于改进概率路线图算法的煤矿机器人路径规划方法

路径规划是煤矿机器人在煤矿井下非结构化狭长受限空间中应用亟待解决的关键技术之一。针对传统概率路线图(PRM)算法在空间狭长封闭巷道环境中难以保障采样的节点均匀分布于自由空间中导致路径规划失效,以及节点可能距离障碍物较近导致规划的路径可通行性差等问题,提出了一种基于改进PRM算法的煤矿机器人路径规划方法。在构造阶段引入人工势场法,将落在障碍物中的节点沿与其距离最近自由空间中的节点连线方向推至自由空间,并在障碍物边缘建立斥力场,实现节点的均匀分布且使其距离障碍物有一定距离;在查询阶段融合D^*Lite算法,当遇到动态障碍物或前方无法通行时可实现路径的重规划。仿真结果表明：改进PRM算法的节点均匀分布在自由空间中,且均距离障碍物一定距离,提高了路径规划的安全性;当节点数为100个时,改进PRM算法成功率较传统PRM算法提高了25%;随着节点数增加,传统PRM算法和改进PRM算法路径规划成功次数均呈增长趋势,但改进PRM算法在效率方面优势更明显;当节点数为400个时,改进PRM算法运行效率较传统PRM算法提高了35.13%,且规划的路径更平滑,路径长度更短;当障碍物突然出现...     

smax图算法及其相关标度测度的改进

在给定相同度序列的条件下,讨论了计算smax的二种算法所存在的不同缺陷：基于边算法的时间和空间复杂度都为O（N2）,对较大的N会导致计算机存储空间不够;基于点算法是smax的一个近似值,通过实例说明其近似计算的误差不容忽视,而且该算法只能用来计算度序列中的最小度m=1的情况,对度序列中最小度m>1的情况,用该算法来计算smax就会失效。基于上述算法的缺陷,提出了一个改进算法,它具有smax值精度的优越性和对m>1情况的有效性。采用改进的算法求得smax值,通过对不同模型的模拟和分析,发现与smax值相关的标度测度S（g）关于网络规模、网络稠密度具有较大波动性,这会导致对网络无标度程度的误判,为消除网络规模、网络稠密度对测度的影响,对该测度做了改进,实验结果显示新的测度Snew（g）更稳定。     

基于近似最近邻搜索的改进PRM算法

针对移动机器人工作环境范围复杂时,使用传统概率路线图(PRM)算法非常耗时的问题,提出一种改进的PRM算法.PRM算法最耗时的部分是构建无向路径图,构建无向路径图的关键是近邻搜索.通过使用近似最近邻搜索中的局部敏感哈希算法代替原先最近邻搜索算法,在不降低生成路线图质量的前提下,加快无向路线图的构建速度,减少PRM算法的运行时间.仿真结果表明,改进的PRM算法相较于传统的PRM算法在无向路径图建立时间上减少27.36％ ～33.27％,使PRM算法效率大大提高.     

提高链式Lin-Kernighan算法性能的一种新策略

在笔者前期工作(王东, 吴湘滨. 提高链式Lin-Kernighan算法性能的策略. 计算机应用,2007,27(11): 2826-2829)的基础上,通过对经典旅行商问题(TSP)优化解边集之间交集的特性分析,给出了一种新的Lin-Kernighan算法参照优化边集生成模型。该模型建立的边集中边的数量少于常规方法以及前期研究成果生成边集中边的数量,同时以更高概率保留全局最优解中的边。将该模型应用于Lin-Kernighan算法,在不损失单次调用该算法求解精度的前提下,进一步缩短了算法的执行时间,从而进一步提高了链式Lin-Kernighan算法的求解性能。结合前期研究成果,能进一步提高使用Lin-Kernighan算法作为启发式算法的所有混合算法性能。     

基于水平集的PSO算法的改进

粒子群优化算法PSO(Particle Swarm Optimization)目前仍存在着早熟收敛和收敛速度较慢的难题,提出一种新的PSO改进算法.该算法利用水平集对PSO的每一代粒子按照适应度进行划分,把与目标相关的所有信息结合在一起,改变了原有的PSO进化公式,提高了算法的收敛速度;其次,对于每一代的某个个体进行变异,使其变异到粒子密度低的空间中去,从而提高了粒子的多样性,减少早熟发生的机会.实验证明,这种算法是有效的.     

基于改进的PSO算法在Shearlet图像去噪中的应用研究

本文主要通过对标准粒子群优化算法的分析与研究,根据不同特点的粒子群进化模型,提出基于不同进化模型的粒子群改进算法,增加算法群体多样性,提高算法的全局收敛性能。最后将改进的PSO算法应用于Shearlet图像去噪研究。     

A configuration deactivation algorithm for boosting probabilistic roadmap planning of robots

We present a method to improve the execution time used to build the roadmap in probabilistic roadmap planners. Our method intelligently deactivates some of the configurations during the learning phase and allows the planner to concentrate on those configurations that are most likely going to be useful when building the roadmap. The method can be used with many of the existing sampling algorithms. We ran tests with four simulated robot problems typical in robotics literature. The sampling methods applied were purely random, using Halton numbers, Gaussian distribution, and bridge test technique. In our tests, the deactivation method clearly improved the execution times. Compared with pure random selections, the deactivation method also significantly decreased the size of the roadmap, which is a useful property to simplify roadmap planning tasks.     

Biologically inspired node generation algorithm for path planning of hyper-redundant manipulators using probabilistic roadmap

This article describes a biologically inspired node generator for the path planning of serially connected hyper-redundant manipulators using probabilistic roadmap planners. The generator searches the configuration space surrounding existing nodes in the roadmap and uses a combination of random and deterministic search methods that emulate the behaviour of octopus limbs. The strategy consists of randomly mutating the states of the links near the end-effector, and mutating the states of the links near the base of the robot toward the states of the goal configuration. When combined with the small tree probabilistic roadmap planner, the method was successfully used to solve the narrow passage motion planning problem of a 17 degree-of-freedom manipulator.     

改进的几何定理机器证明的概率性算法

将几何定理机器证明的研究方法概括为确定性算法与概率性算法两大类,针对已有的确定性算法和概率性算法的证明速率偏低或占用内存过大等问题,提出一种改进的概率性算法。主要是在改进对多项式中独立变元次数的上界估计的算法的基础上,结合Schwartz-Zippel定理和统计学理论,通过随机检验若干实例来证明几何定理,并能控制证明结果不真的概率在给定的小范围内。通过改进的概率性算法,成功在2秒内证明出代数法难以证明的五圆定理。最后的多组对比实验进一步表明,改进的概率性算法具有明显高效性。     

Narrow passage sampling for probabilistic roadmap planning

Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.     

采用半初始化和概率扰动策略改进的遗传算法

针对遗传算法在函数寻优过程中收敛速度慢、易陷入局部最优解的问题,提出一种采用半初始化和概率扰动策略改进的遗传算法DIAGA。首先,通过引入概率扰动策略增加了算法迭代后期的种群多样性,采用半初始化从根本上改变了算法在全局最优解比较过程中的局限性;然后利用马尔可夫链理论证明了DIAGA的收敛性;最后,对六个标准测试函数进行仿真测试。仿真实验结果表明,提出的DIAGA有效摆脱了局部收敛,在搜索精度、收敛速度上具有明显优势,就多维测试函数而言,寻优精度提高了约29%。     

Sampling and node adding in probabilistic roadmap planners

The probabilistic roadmap approach is one of the leading motion planning techniques. Over the past decade the technique has been studied by many different researchers. This has led to a large number of variants of the approach, each with its own merits. It is difficult to compare the different techniques because they were tested on different types of scenes, using different underlying libraries, implemented by different people on different machines. In this paper we provide a comparative study of a number of these techniques, all implemented in a single system and run on the same test scenes and on the same computer. In particular we compare collision checking techniques, sampling techniques, and node adding techniques. The results were surprising in the sense that techniques often performed differently than claimed by the designers. The study also showed how difficult it is to evaluate the quality of the techniques. The results should help future users of the probabilistic roadmap planning approach in deciding which technique is suitable for their situation.     

加速概率存在场目标检测的改进算法

概率存在场（POM）算法是一种多视角目标检测算法,其根据各视角对应的二值前景图像,估计检测场景中所有3D位置对应地面上存在目标的概率。当检测场地面积过大时,POM算法估计所有3D位置上存在目标的概率会十分耗时,拖累算法速度。提出了一种加快POM算法速度的方法：根据二值前景图像和3D位置信息,大幅减少POM算法需要处理的3D位置数量,从而提高算法速度。实验结果表明：在对算法检测结果影响很小的情况下,对于单目标和多目标检测场景,算法速度都得到了较大的提升。     

基于改进概率地图的无人机实时避障研究

基于空间点采样的概率地图方法能够很好地表示出自由空间的连通性,该方法已在路径规划领域得到了成功的应用。但是,由于在由已得到的采样点基础上构造连通图时,需要检查图的边是否与障碍物发生碰撞,即进行相交检验,限制了概率地图的构造速度,难以满足在实际应用中的实时性要求。针对无人机路径规划问题,以等高线地图作为任务空间,提出了一种新的采样模型,在该模型框架下,依据适当的规则构造临近点集,便可以避免相交检验,提高了路径规划速度。     

改进的概率潜在语义分析下的文本聚类算法

概率潜在语义分析(PLSA)模型用期望最大化(EM)算法进行参数训练,由于算法参数的随机初始化,致使聚类的效果过度拟合且过分依赖于参数初始值。将潜在语义分析(LSA)模型参数概率化,用以初始化概率潜在语义分析模型的参数,得到的改进算法有效解决了参数随机初始化问题。经实验验证,所提出的方法对文本聚类的归一化互信息(NMI)和准确度都有明显提高。     

基于改进的随机路径图及和声算法的舰船航线规划

针对海上航行中障碍物躲避问题,提出改进的随机路径图及和声算法为舰船进行航线规划.该算法首先利用改进的随机路径图,在障碍物边缘、起点与终点连线等关键区域进行节点设置及扩充,根据舰船及障碍物运动特征,分阶段在海图上设置节点并连接,利用较少的节点生成完备的路径网络图,基于此选择节点生成初始全局航线;其次利用改进的和声算法对航线进行优化,障碍物的运动特性导致解空间为复杂的多峰形态,为避免节点位置变动导致新生成航线不可行,设置限定条件,仅对满足要求的航线利用航线交叉、消除节点、微调等策略进行优化.实验结果表明,相较对比算法,所提算法能够有效生成更高质量的全局航线,且在优化过程中生成的不可行航线数量远低于其余几种算法,具有更高的可靠性及稳定性.