基于改进A*算法的移动机器人路径规划

为了解决较大场景下A^*寻路算法存在的内存开销大、计算时间长等问题,本文在A^*算法的基础上,结合跳点搜索算法,提出一种改进的A^*算法．该算法通过筛选跳点进行扩展,直到生成最终路径,扩展过程中使用跳点代替A^*算法中大量可能被添加到OpenList和ClosedList的不必要节点,从而减少计算量．为了验证改进A^*算法的有效性,分别在不同尺寸的2维栅格地图中进行仿真,仿真结果表明,相比A^*算法,改进A^*算法在寻路过程中扩展更少的节点,寻路速度更快,且加速效果随环境地图的增大更加明显．最后将改进A^*算法应用于移动机器人Turtlebot2进行对比实验．实验结果表明,在生成相同路径的基础上,改进A^*算法的寻路速度较A^*算法提高了约200%,能够满足移动机器人路径规划的要求．     

多方向无人水面艇路径规划算法

针对海洋环境下无人水面艇路径（USV）规划安全性与平滑性问题,提出一种多方向A^*路径规划算法以获得全局最优路径。首先,结合电子海图生成栅格化环境信息,并根据安全航行距离约束建立USV安全区域模型,在传统A^*算法基础上设计一种带安全距离约束的A^*启发函数来保证生成的路径节点的安全;其次,改进传统A^*算法的八方向搜索模式,提出一种多方向搜索模式来调整生成路径中的冗余点与拐点;最后,采用路径平滑算法对路径拐点进行平滑处理以获得满足实际航行要求的连续平滑路径。在仿真实验中,改进A^*算法规划的路径距离为7 043 m,相较于Dijkstra算法、传统A^*四方向搜索算法和传统A^*八方向搜索算法分别降低了9.7%、26.6%和7.9%。仿真结果表明改进后的多方向A^*搜索算法能够有效减小路径距离,更适用于USV路径规划问题。     

多方向无人水面艇路径规划算法

针对海洋环境下无人水面艇路径（USV）规划安全性与平滑性问题，提出一种多方向A^*路径规划算法以获得全局最优路径。首先，结合电子海图生成栅格化环境信息，并根据安全航行距离约束建立USV安全区域模型，在传统A^*算法基础上设计一种带安全距离约束的A^*启发函数来保证生成的路径节点的安全；其次，改进传统A^*算法的八方向搜索模式，提出一种多方向搜索模式来调整生成路径中的冗余点与拐点；最后，采用路径平滑算法对路径拐点进行平滑处理以获得满足实际航行要求的连续平滑路径。在仿真实验中，改进A^*算法规划的路径距离为7 043 m，相较于Dijkstra算法、传统A^*四方向搜索算法和传统A^*八方向搜索算法分别降低了9.7%、26.6%和7.9%。仿真结果表明改进后的多方向A^*搜索算法能够有效减小路径距离，更适用于USV路径规划问题。     

基于改进A*算法的无人车路径规划

传统的A^*算法在无人车路径规划中存在规划时间较长和搜索范围较大的缺点。综合分析A^*算法的计算流程后,从四个方面对A^*算法进行改进：1）目标性拓展,即根据待扩展节点和目标节点的相对位置来有目标性地选择不同的象限进行节点拓展;2）目标可见性判断,即判断待扩展节点与目标点之间有无障碍物,若无障碍物则跳出A^*算法的探索过程,以此减少多余的搜索;3）改变A^*算法的启发函数,即增加待扩展节点的n辈父节点到目标点的代价估计,以此减少到目标点的代价估计的局部最优情况;4）改变扩展节点的选取方略,即改变传统的最小化启发函数来选择扩展节点的方式,通过引入模拟退火法来优化扩展节点的选择方式,使得搜索过程尽可能向靠近目标点的方向进行。最后通过Matlab仿真实验结果表明,在模拟的地图环境下,提出的改进A^*算法在运行时间上减少67.06%,经历的栅格数减少73.53%,优化路径长度浮动范围在±0.6%。     

融合安全A*算法与动态窗口法的机器人路径规划

A^*算法通过启发信息指引搜索方向,被广泛应用于移动机器人的路径规划,但其规划出的搜索路径存在冗余节点且与障碍物相近,无法满足动态避障需求。对标准A^*算法进行改进,设计安全A^*算法并融合动态窗口法进行路径规划。定义安全距离因子引入A^*算法的启发函数中,提高算法规划路径的安全性,同时采用平面结构法对算法规划得到的路径进行优化,根据相邻节点与障碍物之间的位置关系判断该相邻节点间是否存在障碍物,由此减少路径拐点数,提高路径平滑度。由于当移动机器人处于未知环境时,仅靠A^*算法不能避开障碍物到达目标点,因此借助动态窗口法的局部避障功能。通过安全A^*算法规划全局最优路径节点坐标,设计融合子函数改进动态窗口法的评价函数,解决动态窗口法易陷入局部最优的问题。实验结果表明,在复杂环境中,该方法通过融合安全A^*算法和动态窗口法,能够确保在安全路径基础上实时随机避障,使机器人安全到达终点。     

改进A*算法的移动机器人最短路径规划

针对复杂室内环境下移动机器人路径规划存在实时性差的问题,通过对Dijkstra算法、传统A^*算法以及一些改进的A^*算法的分析比较,提出了对A^*算法的进一步改进的思路。首先对当前节点及其父节点的估计路径代价进行指数衰减的方式加权,使得A^*算法在离目标点较远时能够很快地向目标点靠近,在距目标点较近时能够局部细致搜索保证目标点附近障碍物较多时目标可达;然后对生成的路径进行五次多项式平滑处理,使得路径进一步缩短且便于机器人控制。仿真结果表明,改进算法较传统A^*算法时间减少93.8%,路径长度缩短17.6%、无90°转折点,使得机器人可以连续不停顿地跟踪所规划路径到达目标。在不同的场景下,对所提算法进行验证,结果表明所提算法能够适应不同的环境且有很好的实时性。     

Enhanced A algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases

The multiple alignment of the sequences of DNA and proteins is applicable to various important fields in molecular biology. Although the approach based on Dynamic Programming is well-known for this problem, it requires enormous time and space to obtain the optimal alignment. On the other hand, this problem corresponds to the shortest path problem and the A^* algorithm, which can efficiently find the shortest path with an estimator, is usable.

First, this paper directly applies the A^* algorithm to multiple sequence alignment problem with more powerful estimator in more than two-dimensional case and discusses the extensions of this approach utilizing an upper bound of the shortest path length and of modification of network structure. The algorithm to provide the upper bound is also proposed in this paper. The basic part of these results was originally shown in Ikeda and Imai [11]. This part is similar to the branch-and-bound techniques implemented in MSA program in Gupta et al. [6]. Our framework is based on the edge length transformation to reduce the problem to the shortest path problem, which is more suitable to generalizations to enumerating suboptimal alignments and parametric analysis as done in Shibuya and Imai [15–17]. By this enhanced A^* algorithm, optimal multiple alignments of several long sequences can be computed in practice, which is shown by computational results.

Second, this paper proposes a k-group alignment algorithm for multiple alignment as a practical method for much larger-size problem of, say multiple alignments of 50–100 sequences. A basic part of these results were originally presented in Imai and Ikeda [13]. In existing iterative improvement methods for multiple alignment, the so-called group-to-group two-dimensional dynamic programming has been used, and in this respect our proposal is to extend the ordinary two-group dynamic programming to a k-group alignment programming. This extension is conceptually straightforward, and here our contribution is to demonstrate that the k-group alignment can be implemented so as to run in a reasonable time and space under standard computing environments. This is established by generalizing the above A^* search approach. The k-group alignment method can be directly incorporated in existing methods such as iterative improvement algorithms [2, 5] and tree-based (iterative) algorithms [9]. This paper performs computational experiments by applying the k-group method to iterative improvement algorithms, and shows that our approach can find better alignments in reasonable time. For example, through larger-scale computational experiments here, 34 protein sequences with very high homology can be optimally 10-group aligned, and 64 sequences with high homology can be optimally 5-group aligned.     

改进A*算法的机器人全局最优路径规划

针对传统A^*算法规划的路径存在很多冗余点和拐点的问题,提出了一种基于A^*算法改进的高效路径规划算法。首先,改进评价函数的具体计算方式,减小算法搜索每个区间的计算量,从而降低寻路时间,并改变生成路径;其次,在改进评价函数具体计算方式的基础上,改进评价函数的权重比例,减少生成路径中的冗余点和拐点;最后,改进路径生成策略,删除生成路径中的无用点,从而提高路径的平滑性;此外,考虑到机器人的实际宽度,改进后算法引入障碍物扩展策略保证规划路径的可行性。将改进A^*算法与三种算法进行仿真对比,实验结果表明,改进后的A^*算法规划的路径更加合理,寻路时间更短,平滑性更高。     

基于随机游走的多目标A*算法的改进

针对基于降维技术改进的多目标A^*（NAMOA_dr^*）算法中存在的高原搜索现象,结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A^*（RWNAMOA_dr^*）算法,其基本思想是当NAMOA_dr^*算法陷入高原搜索时,利用随机游走策略及时找到一个出口（具有被上次扩展标签的启发值非支配的启发值的标签）逃离该高原搜索。针对NAMOA_dr^*算法何时陷入高原搜索的问题,提出了一种检测高原搜索的方法,即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOA_dr^*算法陷入了高原搜索。使用多目标搜索算法的标准测试平台——随机网格进行了实验。实验结果表明RWNAMOA_dr^*算法比NAMOA_dr^*算法的运行时间平均减少了50.69%,占用的空间平均减少了约10%,能够为现实生活中加速多目标路径搜索提供理论支撑。     

A*算法的改进及并行化

针对串行A^*算法时间性能较差的问题,提出了一种基于并行搜索和快速插入(PSFI)的算法。首先,研究了共享存储平台上的常见并行启发式搜索算法;然后,通过使用一种延迟的单表搜索(DSTS)方法和新的数据结构,改进了串行算法;其次,在此基础上,设计出一种基于共享存储平台的并行算法;最后,采用OpenMP加以实现。对24数码问题的测试结果表明,改进的串行和并行算法将运行时间分别减少到原算法的1/140和1/450;与并行的NBlock优先(PBNF)算法相比,并行算法将加速比提高到3.2,同时,改进算法是严格的最佳优先搜索算法,保证了解的质量,且易于实现。     

基于改进的A*算法与动态窗口法的移动机器人路径规划

提出了一种改进的A^*算法与动态窗口法相结合的混合算法,以解决移动机器人在多目标复杂环境中的路径规划问题．首要,为了提升算法的运行效率,实现单次规划的路径可通过多个目标点,同时提升路径平滑处理的灵活性并满足移动机器人非完整约束条件,本文利用目标成本函数对所有目标进行优先级判定,进而利用改进的A^*算法规划一条经过多个目标点的最优路径,同时采用自适应圆弧优化算法与加权障碍物步长调节算法,有效地将路径长度缩短5%,转折角总度数降低26.62%．其次,为实现移动机器人在动态复杂环境中局部避障并追击动态目标点．提出将改进动态窗口算法与全局路径规划信息相结合的在线路径规划法,采用预瞄偏差角追踪法成功捕捉移动目标点,并提升了路径规划效率．最后,对所提方法进行仿真实验,结果表明该方法能够在复杂动态环境中更有效地实现路径规划．     

改进A*算法在机器人室内路径规划中的应用

传统A^*算法在面向机器人室内多U型障碍的特殊场景下规划路径时，容易忽略机器人实际大小，且计算时间较长。针对这个问题，提出一种改进A^*算法。首先引入邻域矩阵进行障碍搜索以提升路径安全性，然后研究不同类型和尺寸的邻域矩阵对算法性能的影响，最后结合角度信息和分区自适应距离信息对启发函数进行改进以提高计算效率。实验结果表明，改进A^*算法可以通过更改障碍搜索矩阵的尺寸来获得不同的安全间距，以保证不同机器人在不同地图环境下的安全性；而且在复杂大环境中与传统A^*算法相比寻路速度提高了28.07%，搜索范围缩小了66.55%，提高了机器人在遇到动态障碍时二次规划的灵敏性。     

Heuristic fault-tolerant routing strategies for a multiprocessor network

We examine the suitability of three heuristic search algorithms (Greedy Constructive Scheme, Best First Search and A^*) for use as routing strategies on a faulty multiprocessor network. Our search space is a simulated 5 × 5 × 5 (125-node) multiprocessor mesh network. Each virtual node comprises a processor and a communications switch supporting explicit message backtracking. Their performances are compared for up to 20% of randomly generated faulty links. The results show that heuristic search algorithms can be implemented as fault-tolerant routing strategies and that the modified Best First Search routing strategy performed consistently better with significantly less degradation than the Greedy Constructive Scheme and the A^* strategies.     

Performance evaluation of parallel iterative deepening A on clusters of workstations

In this paper we investigate the performance of distributed heuristic search methods based on a well-known heuristic search algorithm, the iterative deepening A^* (IDA^*). The contribution of this paper includes proposing and assessing a distributed algorithm for IDA^*. The assessment is based on space, time and solution quality that are quantified in terms of several performance parameters such as generated search space and real execution time among others. The experiments are conducted on a cluster computer system consisting of 16 hosts built around a general-purpose network. The objective of this research is to investigate the feasibility of cluster computing as an alternative for hosting applications requiring intensive graph search. The results reveal that cluster computing improves on the performance of IDA^* at a reasonable cost.     

A*算法在AGV路径规划上的改进与验证

针对单AGV路径规划时,A^*算法的启发函数采用曼哈顿距离时遇到障碍物会出现局部绕行这一问题,将带有障碍物的栅格地图作为环境模型,研究出两种改进A^*算法的路径规划方法。第一种方法是在遇到障碍物时将启发函数中曼哈顿距离换成欧氏距离,利用欧氏距离规划路径代价最小的特性避免绕行;第二种方法通过比较AGV遇到障碍物的位置与障碍物左右两端距离大小,通过规定行驶方向避免绕行。仿真结果表明,两种方法均可以在单AGV遇到障碍物时避免绕行,有效地减少了行驶时间,也使得路径更加平滑,提高了AGV的运行效率。     

规则网格数字高程模型中基于距离与坡度的路径规划算法

针对A^*算法在数字高程模型（DEM）路径规划中的低效问题,提出一种基于距离与坡度的改进A^*寻路算法。该算法面向规则网格DEM,以距离和坡度作为路径搜索评估指标,设计新的评价函数,并以地表障碍评判路径的可通行性。在寻路过程中,根据实际场景DEM数据计算相匹配的参数,使得改进算法能自适应不同场景下DEM数据分辨率的变化;采用动态权值调整完备性函数和启发性函数对评价结果的影响,优化路径选择。仿真测试结果表明,改进算法能够通过参数调整适应DEM分辨率的变化,搜索出优化的路径,降低搜索时间,提高搜索效率。     

基于带电粒子搜索的无人潜航器航路规划方法

针对无人潜航器（UUV）在复杂环境、多约束条件下航路规划过程耗时长、占用空间大等问题,提出了基于带电粒子搜索（CSS）的航路规划方法。首先,建立UUV航路规划问题模型,设计代价函数;然后,给出了基于CSS的航路规划方法,带电粒子在搜索空间中会受到其他带电粒子电场力的作用进而迭代寻优;另外,提出了一种非线性调整速度与加速度参数的方法,通过该方法有效地平衡全局搜索与局部搜索过程,避免算法的早熟收敛。最后,通过对比实验从规划航路的质量和算法耗时两个角度将所提方法与A^*算法、蚁群算法、粒子群航路规划方法进行对比。实验结果表明该方法在保证规划出的航路质量的同时,具有更快的收敛速度、更低的时间复杂度。     

基于混合模拟退火算法的机场进场程序优化

针对人工设计机场进场程序耗时较长且很难定量优化路径长度的问题,提出多条进场程序的三维自动优化设计方法.首先,根据区域导航规范(RNAV)对进场程序的几何构型及汇聚结构进行建模;然后,综合考虑机场布局以及障碍物规避、航路间隔等航空器运行约束,以最小化进场程序总长度为目标,建立了完整的数学模型;最后,开发了基于模拟退火算法...     

Mean and standard deviation for the facilities design problem

An important problem in facilities design to find an assignment of n facilities to n locations so that total materials handling cost is minimized. For problems of moderate size, suboptimal solutions must be accepted since optimal algorithms are computationally infeasible. If the mean and standard deviation of the layout cost distribution is known, then statistical methods may be used to measure and compare the efficiencies of various suboptimal solutions as well as to monitor the efficiency of the same assignment under changing production environments. In this paper a new, simple algorithm to calculate the exact value of the standard deviation of the layout cost distribution is presented (the mean is easy). This algorithm has a computational efficiency of O(n²) arithmetic operations for a problem of size n × n, an improvement over previous methods which are either inexact or have a computational efficiency of O(n⁴). Results of tests verifying the accuracy and claimed efficiency of this algorithm, as implemented on a microcomputer, are also presented (about 0.85 second for a 30 × 30 problem).     

复杂环境下基于采样空间自调整的航迹规划算法

针对具有渐进最优性的快速扩展随机树(RRT*)算法在面对高维、复杂环境时所表现出的寻路效率低、收敛速度缓慢的问题,在RRT*的基础上,提出一种基于采样空间自调整的渐进最优快速扩展随机树(AS-RRT*)无人机(UAV)航迹规划算法.该算法可以自适应调整采样空间,进而引导树更为高效地生长,而这些主要通过有偏采样、节点筛选...