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

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

改进的生物激励神经网络的机器人路径规划

介绍了基于生物激励神经网络的移动机器人路径规划。机器人的路径生成过程是由神经网络组成动态变化的神经元活性值状态路线图实现的。通过神经元活性值的传播,机器人被吸引到目标点,而同时障碍物使自己处在活性值最低点,起到推开机器人避碰的目的。仿真研究表明该方法生成的由起始点到目标点的路径是连续的、平滑的、避障的,不会陷入U形障碍物,与障碍物形状和所处位置无关,能对快速变化的环境做出迅速反应。但在当前位置邻近位置中具有最大活性值的位置不惟一的情况下,产生路径可能不理想,即到达目标点的避障路径是较长的,而不是最短或者是接近最短的。文中对该不足进行了分析,并提出了改进方法,使生成路径是最短的或是接近最短。对改进方法进行了仿真,实验结果证明该方法是有效的和可行的。     

改进的生物激励神经网络的机器人路径规划

介绍了基于生物激励神经网络的移动机器人路径规划。机器人的路径生成过程是由神经网络组成动态变化的冲经元活性值状态路线图实现的。通过神经元活性值的传播，机器人被吸引到目标点，而同时障碍物使自己处在活性值最低点，起到推开机器人避碰的目的。仿真研究表明该方法生成的由起始点到目标点的路径是连续的、平滑的．避障的，不会陷入U形障碍物，与障碍物形状和所处位置无关，能对快速变化的环境做出迅速反应。但在当前位置邻近位置中具有最大活性值的位置不惟一的情况下，产生路径可能不理想，即到达目标点的避障路径是较长的，而不是最短或者是接近最短的。文中对该不足进行了分析，并提出了改进方法，使生成路径是最短的或是接近最短。对改进方法进行了仿真，实验结果证明该方法是有效的和可行的。     

移动机器人避障路径规划算法的研究

避障路径规划问题是在障碍物环境中,在满足与障碍物不相碰撞的前提条件下,规划一条从起点到达终点的路径.在此过程中,往往符合条件的路径不止一条,如何在其中找到最短路径则是我们关心的问题.本文以构建障碍物模型为基础,将路径规划问题转化为求解一条经过起点和终点的最短路径,并在此基础上构建了算法程序.通过计算机仿真表明该方法具备良好的路径规划能力.     

障碍物存在的最短路径算法及其在车载导航中的应用

车载导航系统中的动态路线选择是其必备功能之一,文中分析了经典Dijkstra算法存在的不足,并在此基础上,采用优化的邻接矩阵存储结构,讨论了有障碍物存在情况下的最短路径问题。同时用Vc＋＋与Mapx实现了有障碍物存在的动态最短路径算法。实验结果表明,该算法能有效求出有障碍物存在时的最短路径。     

最短路径原理正射影像镶嵌线自动提取

<正>射影像镶嵌过程中,镶嵌线的选取是一个重要的步骤,其自动化程度是影响全自动镶嵌的一个重要因素。本文提出一种基于图论最短路径原理的正射影像镶嵌线自动提取方法。该算法将图像上提取得到的底层视觉信息(Canny边缘)作为镶嵌过程中的障碍物信息,在边缘图像上根据像素点的邻接关系构建带权有向图,利用初始镶嵌线作为初始条件计算图中有向边的权值,将正射影像镶嵌线的提取过程转化为图论中最短路径问题。实验表明,该算法可以较为准确提取镶嵌线,对全自动镶嵌具有重要应用价值。     

引入必经点约束的路径规划算法研究

针对传统A*算法存在搜索范围广、运行效率低的问题,提出了一种引入必经点约束的路径规划算法。该算法结合障碍物分布特点,通过寻找最短路径必经点,实现对A*搜索方向的约束,再对最短路径段进行拼接得到最短路径。最后,在100×100网格地图中进行对比实验,结果表明,引入必经点约束的改进算法比传统A*算法的结点访问量大幅降低,运行效率得到显著提高。     

蚁群算法在复杂地形下的路径规划应用

研究存在障碍物的三维空间的最短路径规划,并采用蚁群算法解决这一问题。路径规划问题是计算机领域内的经典问题。它可以描述为已知起始点、c以及环境信息,并确定一条从起始点到目标点的线路。一般来说,所规划的路径必须满足距离最短或代价最小的目标。路径规划技术有着广泛的应用,涉及我们的生活、工作、科研和娱乐等方面。     

矢量图中绕过障碍物的最短路径算法研究

通过比较几种常见的有障碍物时求最短路径的算法．在线探索算法的基础上提出了一种改良的求障碍物群中两点间最短路径的近似算法．     

基于理论最短距离变权重A*算法的路径规划

在栅格化的障碍物地图中,将简单高效的A*算法引入解决路径规划问题。为了提高路径规划效率,减少搜索节点数量,提出了一种在规定的椭圆区域内,基于理论最短距离动态改变A*算法中估价函数权重的最短路径算法。该算法将搜索范围限定在规定的椭圆区域内,椭圆以起点和终点为焦点,利用统计分析与路径中障碍物尺寸相结合的方法计算长轴参数。将各节点实际代价权重赋予动态变化的权值,以实际代价与起点 到终点 的直线距离的比值为该点权重,且规定了上下限以保证搜索精度。同时,对节点估计代价赋予惩罚函数,远离理论最短路径距离的节点将获得较大的惩罚值,使最终路径靠近理论最短路径。通过仿真实验证明,该算法在保证搜索精度的前提下,大大提高了搜索效率。     

公交车网络的最短路径算法及实现

最短路径问题是图论研究中的一个经典算法问题．旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点问的最短路径。为了保证实用性，公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径，即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法，再举例详细说明其过程，最后指出此算法的扩充用途。     

基于梯形模糊中智数的最短路径求解方法

最短路径的选择是图论中的经典问题之一.复杂环境中对象之间的关系通常具有模糊性、犹豫性、不确定性和不一致性,而中智集是元素的真实程度、不确定程度及谬误程度的集合,更有能力捕捉不完全信息.基于此,基于中智集理论和图理论的中智图最短路径选择成为一个关键问题.针对边长表述为梯形模糊中智数的中智图最短路径求解问题,提出一种扩展的动态规划求解方法.利用基于梯形模糊中智数的得分函数和精确函数来比较路径长度,并给出扩展的动态规划求解最短路径方法,从而得到最短路径和最短路径长度.最后,通过两个算例验证此方法的可行性,通过与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.     

Manhattan空间有障碍的最短路径和3-Steiner树算法

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).     

Refreshment of the shortest path cache with change of single edge

The problem of caching shortest paths has been widely studied. All of existing methods that address this problem assume that the condition of road networks does not change with time. In this paper, we study how to refresh a cache when one edge of the underlying road network (graph) changes. A bitmap-based cache structure is proposed to store and give access to shortest paths. In the following, algorithms are developed to detect shortest paths that are affected by the change of edge. After detecting affected paths, several heuristic-based refreshment strategies are proposed to update the cache. We have conducted a series of experiments to compare the performance of proposed strategies. It shows that replacing affected shortest paths with new paths whose benefit values are the largest should be applied in the shortest path caching applications such as navigation and map services.     

基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.     

Classification of the Dubins set

Given two points in a plane, each with a prescribed direction of motion in it, the question being asked is to find the shortest smooth path of bounded curvature that joins them. The classical 1957 result by Dubins gives a sufficient set of paths (each consisting of circular arcs and straight line segments) which always contains the shortest path. The latter is then found by explicitly computing all paths on the list and then comparing them. This may become a problem in applications where computation time is critical, such as in real-time robot motion planning. Instead, the logical classification scheme considered in this work allows one to extract the shortest path from the Dubins set directly, without explicitly calculating the candidate paths. The approach is demonstrated on one of two possible cases that appear here — when the distance between the two points is relatively large (the case with short distances can be treated similarly). Besides computational savings, this result sheds light on the nature of factors affecting the length of paths in the Dubins problem, and is useful for further extensions, e.g. for finding the shortest path between a point and a manifold in the corresponding configuration space.     

An intelligent search path

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; In this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment. In this paper, a simple method to find the shortest path in a fuzzy environment is proposed. Here the edge weights of the network are considered as fuzzy numbers so that the imprecise data values can be represented. © 2010 Wiley Periodicals, Inc.     

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.     

基于全局时延最小化的移动Sink数据收集算法

针对Sink节点移动所带来的时延问题,提出了一种基于最优路径的移动Sink数据收集方案OPDG（Data Gathering Based on Optimal-Path）。首先由MWHA（Minimum Weighted Heuristic Algorithm）算法得到汇聚节点RP（Rendezvous Point）的集合,然后根据这些RP节点求出移动Sink的最佳驻留点集合,最后求出经过驻留点的最短路径。Sink沿着这条路径周期性采集数据。通过NS-2中大量的仿真实验结果表明,与已有算法相比,OPDG算法能最大限度的减小时延,延长网络的生命周期。