三坐标测量机无碰撞检测路径的生成

针对三坐标测量机检测路径的优化与安全问题,提出一种无碰撞检测路径的生成方法.先对测量点按其参数加权和大小规划检测顺序形成初始路径,再通过对测头扫描体表面与零件表面求截面交线进行碰撞检测,结合轴向包围盒过滤提高碰撞检测的效率;对于碰撞的路径段,先对可能存在的外圆特征进行碰撞规避,再对其他碰撞采用启发式规则进行避障移动规划,结合设计的一个扩展包围盒进行避障点设定.最后通过实验验证了文中方法的可行性.实验结果表明,该方法可以在较短时间内生成有效的较优路径,同时能很好地避免碰撞.     

飞机线缆自动检测系统布局优化设计研究

针对大型飞机约40000测试点的线缆自动检测系统中测试箱点数、测试箱位置和测试设备间控制电缆连接路径进行优化设计。利用近邻交换法实现机载插头自动分类,并基于0-1背包求解方法提升测试箱可接入点数利用率;利用分步遗传粒子群算法,以转接电缆总长最短为目标,优化测试箱可接入点数和测试箱位置;将控制电缆连接路径抽象为多支路无返回旅行商问题,取测试箱空间位置为节点,测试箱之间的控制线缆为边,测试箱内的对接点数量为权重,构建无向加权网络模型,并以支路总长最短、支路均衡为目标,采用混合离散粒子群算法搜索最佳连接路径,实现测试系统多支路优化设计。与原设计结果相比,测试箱可接入点数利用率从89.7%提高到100%,减少转接电缆10%、控制电缆18%。对线缆自动检测系统测试方案中待优化项目进行数学建模,涵盖了转接电缆的插头分类模型建立、转接电缆长度计算模型建立和控制电缆长度计算模型建立,并基于粒子群智能优化算法,优化线缆自动检测系统布局,从而达到了飞机线缆自动检测系统轻量化设计及最优成本实现。     

简化真实感地形中爬行路径设计的算法研究

该文在概括三维路径设计的基础上给出了爬行路径的定义,并且指出了真实感地形中爬行路径规划与点状图中路径规划的区别。文章首先对问题进行了简化,重点是把地形中地物的形状简化成包围其边界的凸多边形包围盒,提出使用改进的Dijkstra算法解决问题思想,并且提出了构造包围盒顶点间关联矩阵的方法。实验结果表明,该方案总能得到简化问题的解,并从理论上证明了解的最优性,具有较大应用价值。     

Shortest path problem with uncertain arc lengths

Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the α-shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the α-shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the α-shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm.     

基于改进蚁群算法求解最短路径和TSP问题

为了能高效地求饵最短路径和TSP问题,利用速度恒定的蚂蚁群,行走最短路径的蚂蚁首先达到终点这个基本原理,提出了一种改进的蚁群算法。因为只要有一个蚂蚁达到终点,算法停止,所以该算法避免了蚂蚁往返爬行所消耗的时间。针对一定规模的最短路径和TSP问题,设置足够量的蚂蚁群,通过该算法能较快地求出全局最优解或者能很好逼近最优解的近似解,算法的时间复径杂度是线性级的,迭代次数较少,而且该算法是并行处理的。通过实验仿真,结果表明算法是可行有效的。     

Optimal path planning for automated dimensional inspection of free-form surfaces

Structural dimensional inspection is vital for the process monitoring, quality control, and fault diagnosis in the mass production of auto bodies. Comparing with the non-contact measurement, the high-precision five-axis measuring machine with the touch-trigger probe is a preferred choice for data collection. It can assist manufacturers in making accurate inspection quickly. As the increase of free-form surfaces and diverse surface orientations in product design, existing inspection approaches cannot capture some new critical features in the curvature of products in an efficient way. Therefore, we need to develop new path planning methods for automated dimensional inspection of free-form surfaces. This paper proposes an optimal path planning system for automated programming of measuring point inspection by incorporating probe rotations and effective collision detection. Specifically, the methodological contributions include: (i) a dynamic searching volume-based algorithm is developed to detect potential collisions in the local path between measurement points; (ii) a local path generation method is proposed with the integration of the probe trajectory and the stylus rotation. Then, the inspection time matrix is proposed to quantify the measuring time of diverse local paths; (iii) an optimization approach of the global inspection path for all critical points on the product is developed to minimize the total inspection time. A case study has been conducted on an auto body to verify the performance of the proposed method. Results show that the collision-free path for the free-form auto body could be generated automatically with off-line programming, and the proposed method produces about 40% fewer dummy points and needs 32% less movement time in the auto body inspection process.     

基于变邻域蚁群算法的自动光学检测路径规划

在确定取像窗口最少数量及其约束移动范围的前提下,为解决蚁群算法用于自动光学检测路径规划存在的问题,提出一种基于变邻域蚁群算法的自动光学检测路径规划方法。针对蚁群算法收敛速度慢、易陷入局部最优解的问题,提出含有3种邻域结构的变邻域路径搜索方法,改进蚁群算法以快速获得质量优异的可优化路径;针对取像窗口位置可调整的问题,提出变邻域窗口位置调整方法,进一步改善可优化路径,获得最短路径。实验结果表明,该算法比基本的蚁群算法具有更高的求解效率和求解质量,有效提升了自动光学检测系统的在线检测效率。     

救灾无人机的优化A*航迹规划算法

针对抢险救灾中无人机派遣量及空间航迹规划最短路径相制约的问题,提出了一种优化A*的航迹算法。通过设计的蛇形割圆法对圆形巡查区域进行路径规划,通过提取感兴趣区域的方法选择较佳搜索方向,提高搜索效率,采用加权评估法优化自然威胁权重系数,重定义航迹估计函数。将提出的方法在灾情巡查和生命勘测实际问题中进行性能检测。仿真结果表明,该算法能够合理分配无人机数量且能快速规划出较优飞行轨迹,实现巡查覆盖率达88.96%。     

Efficiently determining a locally exact shortest path on polyhedral surfaces

In this paper, we present an efficient visibility-based algorithm for determining a locally exact shortest path (LESP) from a source point to a destination point on a (triangulated) polyhedral surface. Our algorithm, of a finitely-iterative scheme, evolves an initial approximately shortest path into a LESP. During each iteration, we first compute the exact shortest path restricted on the current face sequence according to Fermat’s principle which affirms that light always follows the shortest optical path, and then optimize the face sequence where the path is not locally shortest on the polyhedral surface. Since the series of paths we obtained are monotonic decreasing in length, the algorithm gives a LESP which is shorter than the initial path, at conclusion.

For comparison, we use various methods to provide an initial path. One of the methods is Dijkstra’s algorithm, and the others are the Fast Marching Method (FMM) and its improved version. Our intention for improvement is to overcome the limitation of acute triangulations in the original version. To achieve this goal, we classify all the edges into seven types according to different wavefront propagation manners, and dynamically determine the type of each edge for controlling the subsequent wavefront expansion. Furthermore, we give two approaches for backtracing the approximately shortest paths directed at the improved FMM. One exploits the known propagation manners of the edges as well as the Euler’s method. This is another contribution in this paper.     

基于改进粒子群算法的移动机器人多目标点路径规划

针对移动机器人遍历多个目标点的路径规划问题,提出了一种基于改进粒子群算法和蚁群算法相结合的路径规划新方法。该方法将目标点的选择转化为旅行商问题,并利用蚁群算法进行优化,定义了每两个目标点之间的路径规划目标函数,利用粒子群算法对其进行优化。针对粒子群算法存在的早熟现象,将反向学习策略引入粒子群算法,并对粒子群算法的惯性权重和学习因子进行改进。性能测试结果表明,改进的粒子群算法能有效避免粒子早熟现象,提高粒子群算法的寻优能力及稳定性。仿真实验结果验证了新方法能有效地实现机器人的多目标点无碰撞路径规划。真实环境下的实验结果证明了新方法在机器人多目标点路径规划的实际应用中也具有有效性。     

蚁群算法求解带约束火焰切割路径优化问题

火焰切割路径优化的主要目的是控制切割路径不当引起的热变形误差并对路径长度寻优。通过零件位置关系动态定义切割过程中的可选打孔点集合,将热变形约束条件量化;引入虚拟结点并定义距离矩阵,将路径规划转化为动态描述的TSP问题;基于蚁群算法提出约束条件下增大解空间的方法和信息素更新策略。实验结果表明,改进后的蚁群算法能够有效控制问题的规模并且得到更高质量的解,对热变形约束条件下的数控火焰切割路径优化有较好的效果和实用性。     

交通道路网中任意两点之间最短路径的快速算法

寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。     

On the performance of self-organizing maps for the non-Euclidean Traveling Salesman Problem in the polygonal domain

In this paper, two state-of-the-art algorithms for the Traveling Salesman Problem (TSP) are examined in the multi-goal path planning problem motivated by inspection planning in the polygonal domain W. Both algorithms are based on the self-organizing map (SOM) for which an application in W is not typical. The first is Somhom’s algorithm, and the second is the Co-adaptive net. These algorithms are augmented by a simple approximation of the shortest path among obstacles in W. Moreover, the competitive and cooperative rules are modified by recent adaptation rules for the Euclidean TSP, and by proposed enhancements to improve the algorithms’ performance in the non-Euclidean TSP. Based on the modifications, two new variants of the algorithms are proposed that reduce the required computational time of their predecessors by an order of magnitude, therefore making SOM more competitive with combinatorial heuristics. The results show how SOM approaches can be used in the polygonal domain so they can provide additional features over the classical combinatorial approaches based on the complete visibility graph.     

The shortest path problem with discrete fuzzy arc lengths

In the past, the fuzzy shortest path problem in a network has attracted attention from many researchers for its importance to various applications. In this paper, we propose a new algorithm to deal with the fuzzy shortest path problem. It is composed of fuzzy shortest path length procedure and similarity measure. The former is presented to determine the fuzzy shortest path length from source node to the destination node in the network, and the latter is used to measure the similarity degree between fuzzy length sets. This algorithm not only can yield shortest length but also can offer the actual shortest path to decision makers. An illustrative example is also included to demonstrate our proposed algorithm.     

基于共享边的时延约束组播路由算法

为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH.该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价.仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能较好.     

Shortest polygonal paths in space

A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.     

改进的求解TSP混合分支裁剪法

分支裁减法是一种有效的求解小规模TSP的整数规划方法.随着TSP规模的逐步扩大,问题求解的复杂性也随之增加.在TSP的可计算数学研究领域中,局部搜索算法能快速求解TSP的局部最优解.通过将局部搜索算法与分支裁减法结合,利用局部搜索算法对分支裁减法获得上界所对应环路进行优化,使分支限界算法的上界更快地向全局最优解靠近,提高算法的求解效率,扩大了分支裁减法求解TSP的规模.     

新型树启发式搜索算法的机器人路径规划

面对三维空间移动机器人从起始点到终止点的最短路径问题,提出一种新型的边缘点树启发式搜索(TreeEP)算法,该方法将地图空间进行密度可调的三维离散化处理,根据障碍安全距离筛选出障碍物的可靠边缘点信息,再利用树扩散架构选出最能引导搜索方向的潜力点进行扩散搜索,最终得出最短路径。提出局部调整策略,得到改进的Tree-EP算法。实验结果表明,在带障碍复杂地形最短路径搜索应用中,提出的Tree-EP算法与已有方法相比,能找到更短的移动路径。     

Dijkstra算法在蛋白质序列比对中的研究

提出一种基于Dijkstra算法的序列比对方法,该算法主要用于求最短路径,而序列比对可以转化为在有向无环图中寻找最短路径问题。对于少量序列比对,使用该算法可以求出最优解。对于多序列比对,可将在N维空间求解最短路径问题转化为在二维空间求解最短路径。该算法可以简化问题复杂度,能求得相对最优解。     

一种求解高校路网问题的新型自平衡SDPSO算法

根据智能算法中的粒子群(PSO)算法思想,利用实际的高校地理数据,以离散PSO算法为核心,结合运筹学旅行商问题,给出一种规划高校交通路网的新型自平衡机制PSO算法模型,即SDPSO算法。以Visual Studio 2005、MapInfo8.0、MapX5.0为系统开发工具,实现算法求解。实验结果表明,此算法不但能解决实际路网问题,而且具有一定的自我平衡搜索能力,改善了原有性能。