基于混合SA算法的智能汽车全局路径规划

针对目前智能汽车路径规划存在A~*算法规划的路径精度高却搜索耗时长、搜索耗时短但精度差的矛盾问题,提出了一种既保证搜索效率又可提高路径精度的混合连接SA算法.在原有连接方式的基础上,提出了一种新型的连接方式和S算法,设计了混合SA算法的切换机制,确保了SA算法可获取保证搜索效率的次优路径.进行了路径规划单一地图仿真试验,验证了SA算法在不同的单一环境地图中,重复规划的路径具有一致性、耗时具有一定局限性;同时进行了路径规划普适性仿真试验,对比分析了混合连接SA算法与四连接A~*算法的各项性能指标.结果表明:在全局工况下,SA算法相比于四连接A~*算法,在保证搜索耗时优势的同时,提高了规划路径精度,尤其是在低百分比障碍物地图下,效果更为明显.     

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

在栅格环境下利用蚁群算法规划出来的移动机器人路径存在转弯次数多,累计转折角大等问题。针对这些问题,提出了平滑蚁群算法。平滑蚁群算法是在蚁群算法规划出来的最优路径的基础上,将当前节点与其它不在同一条直线上的节点依次连线,如果新的连接线不穿越障碍物,则将当前连接线作为新路径代替原来路径,并删除中间节点,否则对当前路径不作任何修改。仿真结果表明,平滑蚁群算法能够在不同栅格规模和障碍物覆盖率不同的情况下,有效降低路径长度,减少转折次数和累计转折角度,并且路经规划结果优于免疫遗传算法和势场蚁群算法的路径规划结果。     

基于平滑A~*算法的移动机器人路径规划

栅格环境下A*算法规划出的移动机器人路径存在折线多、转折次数多、累计转折角度大等问题.为获得较优路径,提出平滑A*算法.在A*算法规划的路径基础上,遍历路径中的所有节点,当某一节点前后节点连线上无障碍物时,将延长线路的这一中间节点删除,建立平滑A*模型.仿真结果表明,平滑A*算法优于Ant(蚁群),Anyti me D*算法.平滑A*算法路径长度降低约5%,累计转折次数降低约50%,累计转折角度减少30%～60%.平滑A*算法能处理不同栅格规模下、障碍物随机分布的复杂环境下移动机器人路径规划问题.     

遗传算法在AGV全局路径优化中的应用

采用改进的链路可视图进行建模,使用遗传算法对AGV静态已知环境进行路径规划,并结合在AGV中的具体应用对其进行了改进.在建模过程中,对障碍物做了边界扩展,将障碍物顶点作为行走节点,达到AGV行走过程中避撞的目的.在路径搜索过程中,借鉴蚁群算法的基于可行表的路径搜索方式到初始种群的产生过程,避免了AGV实际问题中无效路径的产生,提高了搜索效率.在初始种群的搜索过程中,对死路情况做了处理,避免了搜索停滞.交叉过程中,采用重复点交叉的几种处理方式,既避免了AGV搜索到断路的情况,也较大提高了产生最优路径的效率.交叉变异过程中人为产生环路的做法,有利于优良个体的产生.将蚁群算法的正反馈优化策略引入遗传算法的多次迭代中的改进中,加快了算法向最优解收敛的速度.MATLAB仿真结果表明,改进后的遗传算法能够快速准确地搜索到AGV的全局最优路径.     

基于改进RRT算法的移动机器人路径规划研究

路径规划是移动机器人开发的核心技术,而传统RRT算法所规划的路径距离长、拐点多,对RRT算法进行改进,引入A~*算法思想,改进待扩展节点的选择。引入人工势力场思想,改进扩展方向的选择。对规划的路径消除冗余点,并采用三次样条函数进行平滑处理。将改进的RRT算法应用于虚拟简单环境地图、虚拟复杂环境地图中,结果表明改进RRT算法所规划的路径平顺性好、路径长度短且所用时间短。最后将改进的RRT算法应用于实际的移动机器人路径规划中,路径规划结果验证了该算法的可行性。     

知识库上逻辑程序图搜索的一种启发函数

本文把A~*算法的启发搜索应用到逻辑程序的求解过程中,就逻辑程序这一特定的问题领域,构造出A~*算法相应的一种启发函数。利用该启发函数,通过A~*算法可求得逻辑程序的“最佳解”。     

A*算法与蚁群算法相结合的无人艇巡逻路径规划

针对无人艇海上巡逻路径规划问题,提出了一种A~*算法与蚁群算法相结合进行最短巡逻路径优化的方法.在传统A~*算法的八角度搜索基础上,设计了一种多角度A~*算法以获得更短的两点之间可行路径,并以A~*算法搜索结果构建任意两个巡逻点之间的最短路径网络.结合最短路径网络建立多点巡逻路径规划问题的目标函数,利用蚁群算法进行求解以获得全局最优的巡逻路径.针对巡逻路径转折角较大的问题,提出了一种平滑算法以获得更符合实际航行需求的平滑路径.仿真结果表明:该方法有效地去除了冗余节点,缩短了路径长度,提高了路径平滑度,规划出了一条更优的无人艇巡逻路径.     

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

针对复杂环境下移动机器人的局部最优路径规划,提出一种基于目标偏置扩展和Cantmull-Rom样条插值的双向RRT^*路径规划算法.双向RRT^*算法同时创建两颗搜索树,交替进行相向搜索,同时以一定的概率进行随机点的目标偏置选择,以提高算法的整体收敛效率;再对当前节点重选父节点和重布线,以增强算法对环境的敏感程度.为确保路径安全可行,对环境中的障碍物进行膨胀处理,再对初始路径进行碰撞检测;修剪冗余节点,缩短可行路径长度,再利用Cantmull-Rom样条插值法平滑路径.在Matlab仿真平台和ROS机器人仿真平台分别进行2D和3D的对比实验,验证了改进双向RRT^*算法的有效性和优越性.     

基于D*算法的农用履带机器人路径规划研究

针对传统A~*算法在路径规划中的不足,采用了一种实时性更强的D~*算法,与A~*算法不同的是,D~*算法的OPEN列表中包含了弧长代价递增的RAISE和弧长代价递减的LOWE两种状态类型。将传统A~*算法和D~*算法进行仿真试验对比,试验结果表明,D~*算法缩短了搜索长度和搜索时间且收敛速度快、计算量小。同时,在真实环境下进行了导航试验,结果表明机器人能稳定安全的按照规划路径到达目的点,验证了D~*算法的高效率性。     

基于改进A*算法的无人驾驶车辆路径规划方法研究

针对传统A*算法所规划路径距离障碍物近、转折点多、路径不平滑的问题,对A*算法进行改进并应用于无人驾驶车辆路径规划中.在传统A*算法分析的基础上对背向障碍物搜索和评价函数进行改进,同时采用3次样条插值方法对规划后路径平滑处理.将传统A*算法和改进A*算法应用于MATLAB环境下搭建的无人驾驶车辆模型进行路径规划仿真分析.结果表明,改进A*算法所规划的路径距离障碍物比较远,转折点数量明显减少,同时路径更加平滑.     

基于改进A~*算法的地图游戏寻径研究

【目的】对A~*算法进行研究和改进优化,以提高基于A~*算法的地图游戏寻径效率。【方法】使用最小二叉堆和标记数组两种混合数据结构优化OPEN表的存储和遍历,用夹角余弦值作为新的启发信息,减少搜索过程中对非最有节点的考察量,通过仿真实验对标准A~*算法、改进A~*算法地图寻径进行数据对比分析。【结果】综合地提高了路径搜索的效率。【结论】通过对A~*算法进行改进优化,有效提高了基于A~*算法的地图游戏寻径效率。     

基于A~*算法的四轴飞行器三维路径规划仿真

在机器人智能控制的研究中,路径规划是移动机器人研究的重要内容,而四轴飞行器是移动机器人的典型代表。文章以A~*算法为基础,通过四轴飞行器的动力学和运动学建模,提出了一种新的四轴飞行器三维路径规划方法。首先通过A~*算法在三维空间内寻径;然后提取该路径的每个关键节点;即四轴飞行器飞行方向改变的节点;最后结合四轴飞行器建模得出完成该段路径的电机控制策略的路径规划。仿真实验结果表明,四轴飞行器可以通过A~*算法及其数学模型完成所需的路径规划要求。     

智能疏散系统导向标志计算及疏散路径仿真

为了解决大型综合建筑中智能疏散系统在火灾等突发情况发生时可根据复杂建筑结构规划出合理、安全的疏散路径问题,提出了一种基于改进A~*算法的多起点、多出口路径规划方法。通过增加转弯惩罚值,结合火灾影响区域实时信息和火灾中心点的距离改进了估价函数,进而计算出最优疏散路径。依据搜索出的最优路径调整三维楼层地图中各个导向标志方向,从而引导不同位置人员从最优路径疏散逃生。仿真实验结果表明,在计算多起点、多出口疏散路径时,改进A~*算法与传统Dijkstra算法和A~*算法相比,搜索方向更加明确,路径更加平滑,搜索效率更高,运行时间更短,并能结合火灾信息保证疏散路径的安全性。该算法在求解大型综合建筑火灾安全疏散路径方面具有很好的应用前景。     

利用跳点搜索算法加速A*寻路

介绍广泛应用于游戏寻路中的标准A*算法,指出跳点搜索(JPS)算法使A*生成并扩展的节点数量很少,而且到达目标的速度很快.因为跳点搜索能够消除路径间的对称性,通过在直线和对角线方向上修剪节点来识别后继,在搜索时跳过了大量可能会添加到open列表和closed列表中的中间节点以及其他计算,这使搜索速度有了很大提升.在5个基准网格地图上测试A*+JPS对A*的相对加速比,实验结果表明:跳点搜索可将标准A*搜索的速度提高一个数量级甚至更多,并且速度收益的程度取决于基础网格地图的地貌,对于大的开放区域,跳点搜索更加高效.另外,跳点搜索对A*在节点扩展数量上的改进甚至比搜索时间的改进更加显著.无论从搜索时间还是从节点扩展数量上,A*+JPS都明显优于A*,利用跳点搜索算法可显著加速A*寻路.     

无人驾驶汽车离散优化的轨迹规划算法

针对双向两车道无人车行驶场景,基于离散优化的方法,提出一种新的轨迹解耦规划算法.该算法将带有时间戳的三维轨迹规划问题解耦成分别对路径和速度规划,速度规划时引入ST图,用以描述无人车与障碍物之间的运动关系.通过分层采样的方法构建路径Lattice图搜索初始路径,并基于多目标A~*搜索算法在ST图中规划出初始速度剖面,减少算法的计算量.同时,优化轨迹规划,使轨迹收敛到全局最优解.最后,通过仿真实验,验证了该算法的有效性和可靠性.     

基于A*扩展自适应蚁群算法的移动机器人路径规划

针对传统蚁群算法存在收敛速度慢、搜索效率低等问题,提出一种A~*扩展自适应蚁群算法.首先利用A~*算法在栅格环境下搜索初始路径,扩展初始路径构建优势区域,优化优势区域的初始信息素,避免蚁群算法在初期陷入盲目搜索;然后在转移概率中引入变向启发函数和参数自适应伪随机比例规则,提升算法搜索效率与收敛速度并淘汰劣质蚂蚁路径;最后采用B样条曲线对路径进行平滑.对比2种栅格环境下的仿真结果可知:所提出的算法能够有效地解决蚁群算法搜索效率低以及收敛速度过慢的问题,同时可以保证搜索路径的质量.     

融合改进A~*算法和动态窗口法的全局动态路径规划

针对移动机器人路径规划全局最优、实时避障的需求,提出了一种融合改进A~*算法和动态窗口法的全局动态路径规划方法。首先,基于传统A~*算法,结合Manhattan和Euclidean距离,设计了一种优化的启发搜索函数;然后,利用关键点选取策略,剔除冗余路径点和不必要的转折点;最后,融合动态窗口法,构造了顾及全局最优路径的评价函数,基于该评价函数,应用动态窗口法,进行实时动态路径规划,在保证规划路径全局最优性的基础上,提高了平滑性及路径规划的局部避障能力。实验结果表明:与传统A~*算法相比,所提算法规划的路径更平滑,可实时动态避障,且能输出控制参数,这利于机器人的自动控制;与动态窗口法相比,所提算法能够保证规划路径的全局最优性,路径长度由28.879m缩短为22.285m。该研究对于移动机器人自主导航的应用具有重要的参考价值。     

基于双向同时无碰撞检测目标偏置RRT算法的路径规划方法

针对传统RRT算法在复杂环境中对不必要区域的搜索和路径规划的时间代价过高等问题,提出了一种双向同时无碰撞检测目标偏置快速扩展随机树算法——TNCG RRT*。该算法将B RRT*中的双向搜索策略和BIT*中的启发式搜索融合作为文中的基础算法,引入神经网络的批量抓取数量决定一次采样的节点数目从而影响采样速度;然后,将正向树和反向树的扩展同时进行以加快路径搜索速度,通过对目标偏向策略中扩展顶点队列的改进和对采样区域的不断更新明确扩展方向,缩小随机树生长的范围;最后,利用3次B样条曲线使生成的路径趋于平滑。与B RRT算法和BIT*算法进行对比实验,实验结果表明:TNCG RRT*算法在路径生成时间上缩短4.5%,剪枝数增加80%,路径代价（即路径长度）缩短9%,证明了TNCG RRT*算法的有效性。     

复杂环境下六自由度机械臂路径规划的Biased-RRT修正算法

为解决复杂环境下六自由度机械臂的路径规划问题,提出一种基于采样规则目标导向设计、父节点重选的修正算法。该算法在原目标偏置策略的基础上对随机采样点的选取规则进行重新设定,以引导算法搜索树在尽可能向目标区域扩展的同时有效避开复杂障碍物。在节点扩展方面,依据新节点距离目标点的远近采用变步长扩展方式,即在距离远时选用大步长,加快搜索树扩展;进入目标区域后选用小步长,防止节点扩展陷入局部死循环。在路径优化方面,所提算法通过引入基于路径代价最小的重选父节点操作及多余路径节点剔除操作,来使规划出的路径相对优化。最后,利用三次样条插值技术为机械臂各关节规划出一条光滑、连续且无障的运动曲线。仿真结果表明,所提算法可有效缩短路径规划时间、减少路径长度,较好地完成了复杂环境下六自由度机械臂的预期路径规划任务。     

两种改进的最优路径规划算法

在对经典Dijkstra算法和A*算法分析的基础上对它们分别进行了改进.在经典Dijkstra算法中,针对当前不相连节点间路径长度为无穷大这一特点,首先对两个节点是否相连进行判断;若发现两个节点并不相连时,则舍去相应计算,从而减小计算量.针对A*算法在实际应用中搜索效率低的缺点,将经典A*算法搜索出的原始最优路径中的节点依次进行封堵后,再按照经典A*算法搜索出相应的新最优路径,最后再将原始最优路径与这些新最优路径进行对比,以便确定最终的最优路径.仿真研究表明:改进的Dijkstra算法可以减少大量的无关节点计算,提高运算的效率;改进的A*算法则可以提高搜索到最优路径的成功率.