任意两点间最短路径的新算法研究

最短路径问题是图论研究中的一个经典算法问题,Dijkstra算法和Floyd算法是解决任意两点间最短路径的常用办法。从局部最优到整体最优的思想出发,得出求解最短路径的一个新方法,即两点间的最短路径是途经当前最短路径集的复合路径和直达路径的最短者,然后以此方法给出求解任意两点间最短路径的一个新算法,最后简述新算法在针对特定问题时相对于经典算法的优势。     

一种新型的路径规划方法--人工水流法

基于水的流动特性,提出了一种动态环境中移动机器人路径规划的新方法。将机器人的工作空间分解为若干个方形区域,构建了一张虚拟地形图(VTM)。在VTM中,地势高的地方对应于工作空间中障碍物所在的区域或不希望机器人进入的区域,地势低的地方对应于工作空间中目标位置或希望机器人进入的区域。机器人的初始位置设定为人工水源,人工水从当前位置流向地势低的地方,流到目标位置时,人工水所流经的区域构成了从初始位置到目标位置的无碰路径。实验结果表明了该方法的正确性和有效性。     

给定场景下机器人避障行走的最短路径模型及求解

文章基于"拉线原理",研究了给定场景下机器人避障行走的最短路径及最短时间路径问题。获得了给定场景下机器人避障行走的最短路径L=(b2-r2)(1/2)+(c2-r2)(1/2)+rθ;最短时间路径S=L圆v0/1+e10-0.1p2+L直v0。     

基于传统遗传算法的改进排爆机器人路径规划研究

针对传统遗传算法进化速度慢、容易陷入局部最优点等缺陷,提出了改进后新的路径规划算法。在判断路径中,基于闵科夫斯基原理对障碍物进行扩展;在构造路径中基于可视图原理进行改进,构造机器人的真正可行区域;在最短路径中对遗传算法中种群的初始化,个体的编码方法等问题做了详细的研究,并在选择算子中引入相似度的概念,大大扩大了初始种群的范围,避免进入局部最优点。最后通过仿真实验验证了此算法的可行性。     

基于Dijkstra算法的兰州某区热水管道铺设问题

本文将热水管道铺设的可行线路抽象为一个无向加权图，这样实际的最短路径问题抽象为无向加权图中两顶点之间的最短路径问题：采用Dijkstra算法找出图中起始顶点到达其余顶点的最短路径，即可得出在实际管道网状图中供热厂到达新建住宅区的的最短路径；并通过MATLAB7．0编程，实现对Dijkstra算法的求解以及对结果的检验。     

储罐探伤爬壁机器人全遍历路径规划方法

储罐探伤爬壁机器人全遍历路径规划要求机器人高效遍历储罐外壁全部无障碍物区域。结合邻接矩阵、路径选择函数,提出一种单元分解算法并应用于爬壁机器人路径规划中。首先,将爬壁机器人的工作环境简化为二维平面,并通过分析漏检面积确定机器人遍历基本路径;接着,建立栅格环境,对每个栅格赋予x_i值以表示其栅格状态;其次,采用矩形分解法将工作环境划分为若干子区域,通过图的深度优先搜索算法和邻接矩阵确定各子区域的衔接顺序;最后,在子区域的遍历和切换过程中,引入方向函数y_i来判断爬壁机器人是否陷入死区,结合x_i值提出路径选择函数f_i以引导爬壁机器人快速逃离死区。在虚拟环境中进行了仿真实验,仿真结果表明,该方法不仅能引导爬壁机器人以高覆盖率和低重复率遍历工作区域,而且能快速地逃离死区。全遍历路径规划的实现拓展了爬壁机器人在检测储罐罐壁中的应用。     

基于改进人工势场法的动态环境运动规划

移动机器人和智能无人驾驶车辆的路径规划问题是实现自主导航的关键问题。本文提出了基于改进人工势场法的局部路径规划算法,只需传感器提供局部环境信息,就可做出即时反应来指导机器人运动,算法简单,效率较高。实验结果表明该方法可以在动态环境下实时计算障碍物位置和信息,顺利到达目标点,高效、稳定,具有广泛适用性。     

基于可视切线图的未知环境建模新方法研究

针对移动机器人路径规划的环境建模问题,提出了一种基于可视切线图的未知环境建模新方法。首先给出可视切线图的定义,其节点为障碍物边界上的可视切点,边为视点与可视切点间的切线段。其次为避免机器人与障碍物相碰,对可视切线图进行了扩展。最后在建立可视切线图的基础上,采用两种启发函数搜索全局目标指导下的局部最优路径。仿真分析证明,可视切线图的数据结构简单,所需存储空间小,具有较好的环境适应能力,是一种有效的路径规划工具。     

用于移动机器人路径规划的曲线轨迹算法

针对移动机器人路径规划方法--人工势场法在相近障碍物之间不能发现路径的局限性,经改进,提出了一种圆弧路径算法.该改进算法从轨迹方程的角度出发,将移动机器人的路径以规则曲线的形式进行规划,确定路径方程,并以圆的曲线方程来表示,以求便于计算,同时综合考虑了路径规划的实时性和最短路径,从而可得出最优路径.构建了三维激光扫描系...     

Path planning in multiple obstacle areas for omni-directional mobile manipulators based on the APFIGA

为解决机器人在多障碍区的路径规划问题,提出了一种基于由遗传算法改进的人工势场法(APFIGA)的全方位移动操作机器人路径规划方法.该规划方法通过在可穿越的障碍区添加障碍物穿越系数来鼓励机器人走捷径,进而提高其路径优化能力;利用当前点邻域内势场强度信息,结合遗传算法确定全方位移动操作机器人的运动方向及速度,并引入机器人速度及移动障碍物速度的影响,得出势场强度下降最快的路径,提高方法的动态环境规划能力.该方法能克服机器人在障碍物附近易于抖动的现象,通过在斥力势中添加与目标距离成正比的系数项解决目标不可达问题,并利用填平势场跳出局部极小.仿真与实物实验结果验证了所提出路径规划方法的正确性和有效性.     

基于动态运动基元的移动机器人路径规划

针对二维环境下移动机器人路径规划问题,提出一种基于动态运动基元(DMPs)的路径规划方法。该方法首先用手柄来控制机器人,记录机器人的运动轨迹,然后将记录的轨迹作为DMPs算法的学习样本,利用轨迹样本进行训练获得DMPs算法的模型参!,从而实现机器人的路径规划。当运动环境中有障碍物时,在已有学习基础上通过设计耦合因子规划出避障路径,在此基础上,改变机器人运动的目标位置,可以完成对新目标的泛化推广。仿真和实验结果表明,DMPs算法在移动机器人路径规划上具有可行性。     

基于功能尺寸最短路径的零件尺寸标注模式的设计

机械零件的尺寸标注模式有多种。尺寸标注模式影响着机械产品的精度和制造成本。为获得零件尺寸合理的标注模式,建立了包含零件尺寸标注所有可能模式的装配尺寸联系路径图;以满足装配体功能尺寸形成路径最短为目标,基于装配尺寸链最短路径原则和最短路径问题的求解,通过2种方法建立了装配体功能尺寸最短路径生成树。功能尺寸最短路径生成树确定了该装配体所有零件唯一合理的尺寸标注模式。研究结果为零件尺寸标注的合理设计提供了新途径,且其易于计算机辅助实现。     

面向大型机场草坪的割草机器人路径规划及轨迹跟踪控制研究

为了提高割草机器人的工作效率及环境适应能力,基于移动机器人平台设计了一种既受遥控操作又能自主运行的适用于大型机场草坪作业的割草机器人。首先,运用高精度差分GPS（global positioning system,全球定位系统）采集机场草坪边界和障碍物的位置信息,根据采集的信息将机场草坪分为最少数目的凸多边形工作区域;考虑到割草机器人无法原地无半径转弯,在传统迂回式路径规划算法的基础上提出一种往返直线型路径规划算法,并在凸多边形路径规划区内推导出遍历路径的显示方程表达式。其次,运用高精度差分GPS测得割草机器人实际轨迹并与规划轨迹对比,设计了一种区间判断型轨迹纠偏算法;以执行电机的PID（proportion integration differentiation,比例积分微分）控制和区间判断型轨迹纠偏算法构造割草机器人双闭环轨迹跟踪控制器,对按传统迂回式路径和往返直线型路径行进的割草机器人进行轨迹跟踪仿真分析。最后,以自制的割草机器人为例,按往返直线型路径运行方式进行样机实验。仿真结果发现：当割草机器人跟踪当前路径到达终点后会自动调头跟踪下一条路径,验证了轨迹跟踪算法的稳定性;传统迂回式路径运行方式下割草机器人的漏割率较高,达到46.42%,而往返直线型路径运行方式下其漏割率为7.15%,明显优于传统迂回式路径仿真结果。样机实验测得的漏割率为8.89%,与仿真实验结果一致,表明所设计的轨迹跟踪算法对大型机场草坪作业割草机器人是适用的。研究结果可为大型机场草坪割草机器人的开发提供理论指导。     

基于自适应VFH算法的移动机器人避障规划

向量场直方图(VFH)方法具有对传感器误差不敏感以及响应速率快等特点而广泛应用于移动机器人的运动避障问题。该方法将各方向的障碍物信息量化为强度值,并以设定的阈值判断可行性。而不同的阈值会造成机器人避障效果的差异,对不同任务环境的适应性较差。本文针对传统VFH方法的阈值敏感性问题进行改进,提出一种自适应阈值调整策略,通过构建阈值评价函数,结合环境信息对候选方向范围内每组阈值进行代价分析,实时地选取适于当前运动的阈值,使机器人能够自主完成避障。为验证算法的有效性和可靠性,设计模拟障碍物的场景并进行对比实验。结果表明,采用改进自适应阈值策略的VFH算法,能够改善传统算法对阈值敏感的问题,能保证机器人可以在狭窄通道中以较短的无碰撞路径到达目标位置。     

储罐检测爬壁机器人全遍历路径规划

针对爬壁机器人难以在储罐外壁实现全遍历检测的问题,提出了一种基于滚动窗口的优先级启发式路径规划算法。在滚动的可视窗口内基于栅格地图进行环境建模,利用优先级启发式算法在滚动的规划窗口内实现对遍历路径的搜索;针对环境中存在U型障碍物的情况,进行了U型障碍物识别和U型障碍物区域直接填充;当机器人陷入死区时,采用死区逃离算法使机器人顺利逃离死区。仿真结果表明,该路径规划方法能指导爬壁机器人在未知储罐外壁环境的情况下实现高效全遍历。研究结果对提高爬壁机器人在储罐外壁的遍历效率具有一定的理论和工程意义。     

英研发复合材料构件机器人无损检测系统

正使用人员可以将要检测零件的CAD图形加载到一种软件工具中,选取要被检测的区域。之后,软件为机器人生成扫描路径。机器人的运动可以在3D环境中进行仿真,以便在机器人实际工作之前验证机器人的非接触性和到达极限。近日,英国TWI公司宣称2014年底将交付一台机器人无损     

基于多传感器信息融合的机器人障碍物检测

针对单一传感器在机器人避障过程中不能全面且准确定位障碍物的缺点,提出基于多传感器信息融合的障碍物检测方法。第一阶段使用视觉传感器检测未知环境中的障碍物,通过Zernike矩边缘检测方法提取障碍物图像边缘,然后采用Hough变换原理提取障碍物的直线特征,获得障碍物大概位置;第二阶段使用超声波传感器和红外传感器对障碍物进行检测,获得障碍物准确位置;最后使用联合卡尔曼滤波对3种传感器获得的信息进行融合,得出融合后的障碍物位置信息。实验结果表明:该方法克服视觉传感器、超声波传感器和红外传感器的局限性,可以精确感知机器人周围的未知环境信息,并能够检测和定位机器人路径上的障碍物,定位误差6 cm,满足机器人避障的实时性和可靠性需求。     

两点沿曲面最短路径的遗传算法研究

求两点沿曲面最小距离的关键是正确选择两点间沿曲面的最短路径。遗传算法是一种全局性概率搜索算法。它在整个问题空间实施搜索,可得到问题的全局最优解,本文应用了遗传算法的理论与方法。首先,将整个曲面作为搜索空间,路径长度作为目标函数,设定了路径优化问题。其次,建立了椭圆坐标系,满足了遗传编码完备性的要求,实现了二维实数编码。运用排序选择方法,单一交叉和最小变异操作,完成了遗传算法,同时获得了最短路径。该方法适用于各种形式的曲面。     

基于改进卷积网络的无人驾驶汽车动态避障路径规划方法

为了提高无人驾驶汽车动态避障的成功率,实现路径最优规划目标,本文引入了改进卷积网络,并开展了基于该网络的无人驾驶汽车动态避障路径规划方法研究。首先,建立了精确的汽车运动学模型,以描述无人驾驶汽车在行驶过程中的运动学特性。其次,对道路障碍物目标位置进行检测,连续获取道路动态障碍物目标的信息,预测障碍物未来的位置和速度。最后,在此基础上,利用改进卷积网络计算了无人驾驶汽车动态避障路径损失函数,评估了规划避障路径与实际目标路径之间的差距。同时,辅助人工势场法求解势能的最小值,得到了汽车避障路径。试验结果表明,应用本文提出的规划方法后,在6个车道上,无人驾驶汽车的动态避障成功率始终高于另外2个对照组,均达到了99%以上,可以有效地识别障碍物并进行避障。     

Dijkstra改进算法在地震救援中的应用

讨论关于地震救援机器人行走避障的最短路径问题.首先用了Dijkstra最短路径的改进算法,得出其最短路径.但由于这样得出的路径往往会有很多迂回,所以又对其进行一定的优化,最终得到一条较为合理的路径,达到省时和运算代价少的目的.