基于改进蚁群算法的导览机器人平滑路径规划

为了解决传统蚁群算法在导览机器人路径规划中,存在路径拐点多、规划路径非最短,路径搜索盲目性大等不足,提出一种改进蚁群算法。首先,选用栅格地图模拟导览机器人的运行环境,采用起点、终点双向搜索的16方向24邻域搜索策略,增加搜索方向,扩大蚂蚁搜索视野,提高全局搜索能力;然后把起点、当前节点、下一节点和终点的信息加入启发函数中,增加搜索路径时的针对性;另外引入伪随机状态转移策略和动态调整的信息素挥发系数,提高收敛速度和避免算法早熟;最后采用三次B样条曲线对上述得到的路径进行平滑处理。在仿真平台上,经过与其他算法对比,验证了论文算法在不同复杂程度环境地图中的有效性和优越性。

改进双向蚁群算法的移动机器人路径规划

针对机器人在静态环境下全局路径规划存在无法找到最短路径,收敛速度慢,路径搜索盲目性大,拐点多等问题,提出一种改进双向蚁群算法。以栅格地图为机器人运行环境,对障碍物有效顶点进行定义、编码和运用,同时结合以相同障碍物有效顶点为相遇条件的双向蚁群算法,双向交替进行路径搜索,能够快速地找到更短路径,得到的路径拐点更少。引入改进的状态转移规则,能够加快搜索速度。在启发函数中引入可调常数因子,在以障碍物有效顶点为路径搜索的节点,每走一步相当于传统算法的一步或多步行走。动态调整挥发系数并设置信息素浓度范围,能够避免陷入早熟。通过与其他算法仿真对比,验证了改进算法的可行性、有效性和优越性。

基于分层网络拓扑结构的最优路径算法

由于Dijkstra算法的基础是平面网络拓扑模型,因此当计算网络的节点数目较大时,计算的时间将急剧膨胀。为了快速地搜索到最优路径,基于分层网络拓扑结构(HiTopo),提出了双向分层搜索最优路径算法(BHWA);该算法对现有分层路径算法进行了以下两点改进(1)将分级网络的局部连通性作为划分子图的指标;(2)在路径计算过程中,使用弧段作为搜索目标,并采取了双向搜索策略。通过北京道路数据的实验表明该算法在保持分层路径算法高效性的基础上,还提高了路径搜索结果的准确性;通过进一步研究表明,如果使用启发式搜索来对算法进行优化,则可以使算法的速度有更大的提升。

基于融合A^(*)-蚁群优化算法的移动机器人全局优化

针对传统蚁群算法在室内移动机器人全局路径规划中,存在的搜索效率低下、路径不够平滑、易陷入局部最优及死锁状况等问题,设计出一种融合改进A^(*)算法的双向搜索蚁群优化算法。首先利用改进A^(*)算法在栅格环境中快速收敛得到初始路径,构建初始信息素矩阵,并引入障碍物因子来减少蚂蚁死锁状况的发生;其次设定双向搜索蚁群优化算法规则,并改进双向搜索中的启发函数模型,引入精英蚂蚁搜索策略和自适应信息素挥发因子策略;最后利用三阶贝塞尔曲线对路径进行平滑处理。通过Pycharm平台仿真结果表明,该算法融合了A^(*)算法全局搜索能力强及蚁群算法正反馈的特性,使得融合改进后算法比传统蚁群算法和麻雀算法在路径长度上优化12.85%和7.76%,搜索时间上优化38.17%和23.46%,迭代次数上优化67.71%和54.41%,全局路径优化效果较明显。

对K则最短路径若干算法的探讨

最短路径问题应用极其普遍,尤其是在一些抢险救灾活动中,它的价值就更显得突出了,而K则最短路径则是在最短路径上的延伸,意思就是在最短路径不适宜时,有多条备选路径可供选择。文中重点介绍了K则最优路径的去边算法、邻近点算法、稀疏矩阵算法和双向搜索四种算法的计算原理,最后结合简单的网络图加以验证。

Layered heuristic algorithm for multiple restriction routes

A layered algorithm by bidirectional searching is proposed in this paper to solve the problem that it is difficult and time consuming to reach an optimal solution of the route search with multiple parameter restrictions for good quality of service. Firstly, a set of reachable paths to each intermediate node from the source node and the sink node based on adjacent matrix transformation are calculated respectively. Then a temporal optimal path is selected by adopting the proposed heuristic method according to a non-linear cost function. When the total number of the accumulated nodes by bidirectional searching reaches n-2, the paths from two directions to an intermediate node should be combined and several paths via different nodes from the source node to the sink node can be obtained, then an optimal path in the whole set of paths can be taken as the output route. Some simulation examples are included to show the effectiveness and efficiency of the proposed method. In addition, the proposed algorithm can be implemented with parallel computation and thus, the new algorithm has better performance in time complexity than other algorithms. Mathematical analysis indicates that the maximum complexity in time, based on parallel computation, is the same as the polynomial complexity of O(kn2-3kn+k), and some simulation results are shown to support this analysis.

部队铁路输送路径选择算法研究

根据部队铁路输送要求和铁路路网特点,设计了基于辅助信息的双向A*路径搜索算法,采用二次读入边数据方法表示路网,利用前向关联边存储结构存储路网,应用经验知识限制算法的搜索区域,通过使用常量系数β提高了启发函数的信息性。实验结果表明,算法的改进是有效和实用的。