基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术 ,提出一种用于解决有限资源、不同重要性要求的任务路径规划问题的有效算法 ,通过对不同重要程度的任务进行分层调度 ,得到较为满意的决策结果。该算法具有搜索空间小、求解速度快的优点。

A^(*)蚁群融合的复合启发式路径规划算法

为提高无人机执行巡飞探查任务的效率,规划出一条最优的飞行路径,针对传统蚁群算法应用于路径规划时存在搜索效率低、迭代次数多、路径拐点多的问题,提出一种A^(*)蚁群融合的复合启发式路径规划算法。利用A^(*)算法预搜索差异化初始信息素,减少蚁群算法前期搜索盲目性,提高搜索效率。构造一种复合启发函数,引入A^(*)算法启发思想改进蚁群原本的启发式信息,设计路径平滑启发函数减少路径拐点。改进信息素更新规则,引入路径综合评分指标,使得每次迭代保留综合性能评分最优的路径。仿真实验表明,改进算法提高了搜索效率,一定程度上解决了拐点过多的问题,综合性能指标优于基本算法与对比文献算法,具有一定工程实践与理论研究意义。

基于多次采样启发式策略的改进RRT路径规划算法

在路径规划领域,快速探索随机树(RRT)算法是机械臂解决复杂环境中的路径规划问题的重要工具,然而其纯随机的采样环节导致大量的无效或低效尝试,浪费了计算资源;为解决此问题,提出一种基于多次采样启发式策略的改进RRT算法(MH-RRT);利用启发式函数评估多个采样点的代价值,选择代价值最低的采样点,引导路径树更快地向目标点生长;将启发式函数策略类似地有效改进了RRT*算法和双向RRT*算法;深入探讨不同参数对改进算法性能的影响,并确定最优参数组合;实验结果表明,改进算法在路径搜索时间、路径长度以及采样点数量等方面均能取得显著提升,提高了路径规划的有效性。

基于位置和能耗启发的改进蚁群算法路径规划

为了解决经典蚁群优化算法应用于移动机器人路径规划中存在综合寻优能力差、收敛速度慢和复杂环境中算法鲁棒性不强等问题,提出了一种基于位置和能耗启发的改进蚁群优化算法。综合考虑机器人行进路径长度、行进路径坡度和转弯带来的能耗问题,提出综合能耗启发因子;考虑路径起点与终点之间,直线距离最短,提出到起止点直线距离启发因子,引导蚂蚁往起止点直线附近路径靠近;提出到终点距离启发因子,引导蚂蚁往目标点方向行进。设计了综合三种启发因子的启发函数,优化状态转移计算方式。此外,通过引入动态信息素挥发因子、改进信息素增量、设计信息素限制等优化信息素更新策略。多种环境多次仿真实验结果对比分析表明,改进算法在寻优路径长度、路径高度均方差、综合性能等方面具有更加优秀的表现。

一种物流配送机器人路径搜索启发式算法研究

针对带有时间窗和配送机器人的车辆路径问题,提出了一种自适应大邻域搜索启发式算法(ALNS)。首先研究了带时间窗口的车辆路径问题,分析了在调度-等待-检索系统中,时间窗约束引起的同步问题以及两种不同的配送资源在时间问题上的关系,在此基础上提出了改进的自适应大邻域搜索(ALNS)启发式算法。该算法通过破坏和修复部分现有解,在每次迭代时改变大部分解,通过创建初始解决方案,并在自适应机制的基础上获得最优解决方案。通过实验证明了该算法在解决带有时间窗和配送机器人的车辆路径问题上的性能和有效性,最后对配送机器人的应用情况进行了敏感性分析。

基于多目标混合启发式算法的协同无冲突4D航迹规划

为促进基于航迹运行的框架下未来空中交通管理系统的协同决策,本文提出了一种协同无冲突4D航迹规划方法。首先以提高航班效率和航空公司间的公平性为目标,以无冲突为约束构建了一个多目标整数线性优化模型。其次,提出了一种基于基尼系数的指标以量化航空公司间的成本分配公平性。为了提高问题求解效率,采用了基于网格的探测方法以加速冲突检测,并设计了一种多目标混合启发式算法(Multi-objective hybrid-meta-heuristic optimization algorithm,MHMOA),通过结合模拟退火(Simulated annealing,SA)和爬山局部搜索算法来近似最优的非支配解。最后,利用实际航班计划和航路网络数据比较和分析了MHMOA、SA和两种常规多目标优化算法的优化结果。结果表明,MHMOA所获得的非支配解的质量更高、延误更低且航空公司间公平性更优,在3个多目标优化性能指标方面表现优异,可为空中交通管理员提供更详细的决策支持。

基于超启发式的多星协同任务规划算法研究

针对多星协同任务调度问题,分析了问题实际约束和问题调度目标,提出了多星协同任务规划调度模型。提出了一种新的基于超启发式算法应用框架对多种算法的管理和调度,研究超启发式多星对地观测任务规划求解方法。最后实验数据证明了算法的有效性和适用性。

对地观测卫星任务规划的启发式动态调整算法

针对对地观测卫星任务规划,分析了单个资源失效与多个高优先级任务动态插入情况下已有任务规划方案的动态调整问题。以最大化规划方案任务权值总和为优化目标,提出了基于任务替换的启发式动态调整算法,包括选择替换任务的五种启发式策略:最大灵活度、最小冲突集、最小争议部分、区间剪枝以及任务剪枝策略。分析了影响动态调整算法运行效率的两个关键因素:冲突任务集与动态搜索深度。采用任务重规划率、规划权值变化率与算法运行时间三项指标考察算法效果,通过仿真实验验证了算法的可行性和有效性。

基于启发式最短路径的PAC任务调度算法

针对PAC实时系统中多种类型任务共存、部分任务之间具有时序相关性的特点,建立了混合关联任务系统的数学模型,将系统中待调度的任务看作构成状态空间树的状态节点,使任务执行序列的选择问题转化为状态空间树中寻找状态节点之间最短路径的问题;基于启发式搜索最短路径算法实现了PAC系统的任务调度机制,该算法通过在线搜索问题的状态空间树,在约束条件下寻找使代价评估函数取得极值的状态节点,从根节点出发并不停地寻找下个节点作为首发任务的后续任务,当根节点通过某条路径可以连接所有节点时,便形成了一个最优且可行的任务执行队列;实例分析和算法性能测试表明,该算法能较好地应用于PAC实时系统的任务调度中。

混合超启发式算法求解复杂两级车辆路径问题

针对模糊需求下的绿色两级车辆路径问题,以最小化车辆运营成本和油耗成本之和为优化目标,提出一种混合超启发式算法进行求解.首先,考虑两级问题解空间庞大且相互耦合,设计一种聚类分解策略将该问题分解为多个子问题,以合理缩小问题搜索空间;然后,提出增强超启发式分布估计算法(enhanced hyperheuristic estimation of distribution algorithm,EHHEDA)对各个子问题进行求解,进而获得原问题的解.EHHEDA基于超启发式算法框架,在高层策略域设计一种基于三维概率模型的分布估计算法,动态确定由底层操作域中各搜索算子所组成的排列(即高层个体),可有效控制和引导整个算法的搜索行为;同时,在底层操作域设计10种有效邻域搜索算子,并加入重升温操作的模拟退火机制作为问题解(即底层个体)的接受准则,有利于在问题解空间中执行深入搜索.仿真实验结果表明,所提出的算法在大多数测试集上优于近年来用于求解类似问题的算法,验证了所提出算法的有效性.

启发式搜索算法路径规划研究

通过对启发式搜索算法和盲目式搜索算法的对比分析,选择作为启发函数的A＊算法作为本文的研究对象。A＊算法因为其搜索效率高,一直受到专家学者的关注和研究,在传统A＊算法的基础上对其进行了改进,来改善A＊算法的规划出的路径。通过仿真验证了A＊算法,总结出A＊算法的缺点,然后针对A＊算法的缺陷进行了相应的改进。并对启发函数距离计算方法进行了改进,通过修改启发函数中的权值,使得在使用A＊算法进行路径搜索时,搜索的点数减少了50%,同时规划出的路径长度并没有发生太大的变化。然后对传统A＊算法规划出的路径进行了平滑处理,最后通过MATLAB仿真验证了改进的A＊算法的可行性和有效性。

基于启发式的快速扩展随机树路径规划算法

针对基于随机采样的路径规划缺乏确定性的问题,提出一种具有启发式的多自由度机器人路径规划算法。该算法在快速扩展随机树算法的基础上,引入了启发式估价函数,使扩展随机树有利于朝目标点方向进行生长。仿真结果表明。提高了复杂环境下机器人路径规划的效率,保证了规划的路径接近于最短路径,对同一任务的规划具有一定的可重复性。

海流环境下多AUV多目标生物启发任务分配与路径规划算法

针对多障碍物海流环境下多自治水下机器人(AUV)目标任务分配与路径规划问题,本文在栅格地图构建的基础上给出了一种基于生物启发神经网络(BINN)模型的新型自主任务分配与路径规划算法,并考虑海流对路径规划的影响.首先建立BINN模型,利用此模型表示AUV的工作环境,神经网络中的每一个神经元与栅格地图中的位置单元一一对应;接着,比较每个目标物在BINN地图中所有AUV的活性值,并选取活性值最大的AUV作为它的获胜AUV,实现多AUV任务分配;最后,考虑常值海流影响,根据矢量合成算法确定AUV实际的航行方向,实现AUV路径规划与安全避障.海流环境下仿真实验结果表明了生物启发模型在多AUV水下任务分配与路径规划中的有效性.

地标导向的启发式路径规划算法

为提高大规模交通网络路径规划算法的查询效率,以A*算法为基础,提出一种地标导向的启发式算法。在预处理中将重要的顶点和边选为地标,在点对点寻径时使用地标作为启发式函数的启发参数,并进行分段计算。实验结果表明,此算法在处理长距离的路径规划问题时有较高的查询效率和更合理的计算结果。

基于贪婪策略的灵巧卫星启发式任务规划算法

灵巧卫星具有姿态机动能力强、卫星载荷动作使用灵活的特点,使得灵巧卫星任务规划难度显著增加。针对任务规划高时效性要求,基于贪婪思想,建立了目标选择、成像时间选择、前瞻处理等贪婪规则,并将卫星使用约束抽象为规划规则,设计了灵巧卫星启发式任务规划算法。该算法能针对灵巧卫星不同工作模式,综合考虑成像目标序列、卫星动作序列与数据传输序列进行优化决策,快速生成卫星任务规划方案。仿真结果表明,该算法可以有效解决灵巧卫星任务规划问题。

基于三维环境模型的启发式路径规划算法

针对多自由度机器人手臂在未知环境中实时避障的问题,提出了一种基于环境信息的连杆机器人实时路径规划方法。采用笛卡尔空间内的障碍物检测信息建立了障碍物的空间模型,并依据该模型设计一种基于启发式规则的机器人路径规划算法。该算法不断猜测和修正路径,通过模糊推理得到下一位姿点,通过曲线拟合得到到达该位姿点的路径。在Matlab下利用机器人工具箱建立了PUMA560型机器人的运动学模型,并在运动空间设置障碍物,对该算法进行仿真分析,分析结果说明所提出的路径规划算法可以在较短时间内完成避障运动,具有较好的实时性,同时运动关节的角度变化曲线比较平滑,运动中冲击力较小,这些特点使其便于在实际工程中使用。

战时舰船抢修任务规划模型及启发式构造算法

针对战时舰船抢修问题,研究在维修资源有限的情况下,如何合理地安排维修活动,以最短的时间、最少的手段使装备至少具有完成部分任务的能力,其目标是从整体上高效分配资源,缩短维修所需的时间。根据规划调度理论,采用基于人工智能的规划调度方法,提出了贪婪随机变邻域搜索算法,该算法求解速度快、解质量稳定。在此基础上建立了舰船抢修任务规划约束优化模型,并研究了战时舰船抢修任务的启发式求解框架和启发式构造规则。模型及算法在战时维修保障决策支持系统得到了实际应用,经证明该算法是一种非常实用的求解途径。

基于启发式算法的路径规划

对路径规划中的最优路径选择算法进行了研究。目前广泛采用的A*最优路径规划算法,在实际的执行过程中容易陷入"死循环",并且其找到的路径并非最优路径。为了提高最优路径规划的准确度和寻优速度,在分析了基本的A*算法的基础上,提出了一种双向A*递归算法,主要通过加入搜索方向因子,充分利用硬件资源和并行编程技术,克服原有A*算法的缺点。最后通过实验和对比证明,双向A*递归算法充分利用双核CPU并行工作的优势,结合并行算法设计,并改进了估价函数模型,大幅提高了算法的性能和运行效率,特别是在大规模路径图搜索的情况下,体现了它的实用性。

融合改进A^(*)算法与动态窗口法的煤矿足式机器人路径规划

为提高煤矿足式机器人路径规划算法的运行效率、搜索精度及避障灵活性,提出了一种融合改进A^(*)算法与动态窗口法(DWA)的煤矿足式机器人路径规划方法。首先对A^(*)算法进行改进,通过去冗余节点策略减短规划路径的长度,通过改进邻域搜索方式和代价函数提高路径规划速度,采用分段二阶贝塞尔曲线进行路径平滑。将改进A^(*)算法规划出的路径节点依次作为局部路径规划DWA的局部目标点进行算法融合,筛选邻近的障碍物节点,从而再次缩短路径长度,并通过调整DWA代价函数中的权值比例提升避障性能。针对机器人遇到无法避开的障碍物而陷入“假死”状态的问题,以当前初始点为起点,重新调用融合算法,即重新进行全局路径规划,将得到的新节点代替原有的局部目标点,按照新路径进行后续工作。仿真结果表明:在保证机器人行走安全稳定的基础上,改进A^(*)算法较传统A^(*)算法的计算时间缩短了65%,路径长度缩短了24.1%,路径节点数量减少了27.65%,最终得出的路径更为平滑;融合算法进一步提升了全局路径规划能力,在多障碍物环境下能够绕开新增的动态和静态障碍物;机器人遇到“L”型障碍物进入“假死”状态时,在“假死”位置重新进行全局路径规划,更新行走路径,成功到达了最终目标点。基于融合算法的JetHexa六足机器人路径规划实验结果验证了融合算法的有效性和优越性。

基于改进遗传算法的无人艇集群多任务分配路径规划

为完成多任务的分配并确保USV集群航行的总路径最短,同时确保各USV的路径长度差距最小,针对USV集群全局路径规划问题从初始种群生成方法、选择算子和变异算子等3方面对遗传算法进行改进。针对航行区域障碍物特点,采用切线法对改进遗传算法生成的路径进行优化。为验证算法的有效性,基于MATLAB/Simulink仿真平台构建仿真模型,并针对具体航行环境进行多任务全局路径规划测试。仿真结果显示,所提出的算法可实现USV集群多任务分配的全局路径规划。