帝国竞争算法在无人机三维航线规划中的应用研究

针对实际飞行环境中无人机的三维航线规划问题,提出了一种创新启发式优化算法——牛顿帝国主义竞争算法(NICA,Newtonian imperialist competitive algorithm).该算法能够根据无人机的飞行轨迹,从起始位置到任务目标位置生成平滑的航线路径,约束航线规划,使得目标完成任务的时间最小化.该算法也能为无人机在真实地形上的航线提供最佳轨迹路径.最后通过与ICA、GA和PSO算法进行比较,验证了改进算法的有效性.结果表明:改进帝国算法提高了全局最优解的搜索能力,在收敛速度和精度上优于其他3种算法,适合用来解决无人机的三维航线规划问题.     

空地异构机器人系统协作巡逻路径规划方法EI北大核心CSCD

空地异构机器人系统由空中无人机和地面无人车组成,当两者协作执行持续巡逻任务时,使用无人车充当无人机的地面移动补给站能够解决无人机续航能力不足的问题.运动受限于路网中的无人车必须在适当地点为无人机补充能量,这使得两者的路径高度耦合,给空地协作路径规划带来了挑战.针对此问题,本文通过分析无人机能量、路网、空地汇合时间、巡逻任务全覆盖等多种约束,以无人机完成全部巡逻任务的总距离为代价,建立了空地协作巡逻路径规划模型.该模型可推广至多架无人机与多辆无人车协作的情形.然后,采用遗传算法与蚁群算法相融合的方法,对无人机巡逻路径和无人车能量补给路径进行优化求解.仿真实验表明,本文的方法不仅可以得到很好的路径规划结果,而且较其他算法具有更优的收敛性和执行速度.     

动态储位分配策略下仓储作业能耗优化调度

针对堆垛机式自动化立体仓库能耗优化任务调度问题,提出了一种动态储位分配策略下的任务调度集成优化方法。该策略允许在当前任务执行批次内重用拣货产生的空库位,产生了任务顺序约束;并结合不同运动状态下堆垛机的运行时间计算差异,建立了复合指令下以堆垛机任务总能耗最低为目标的调度模型。依据模型的特点,提出了一种改进帝国竞争算法进行求解。该算法通过设置校正机制使优化解能够满足任务顺序约束,并引入外来种群入侵的概念来避免算法陷入“早熟”。最后通过两组数据对提出的任务调度算法进行了验证,实验结果表明,改进算法在能耗和任务执行效率方面优于其他方法,能够有效减少堆垛机作业过程能耗,提升作业效率。     

基于多蚁群并行优化的网络路径规划研究

在军事后勤、应急救灾中,需要同时为多个任务、多批次物资运输制定保障方案,该问题可归结为多源多汇问题,是NP-C的。本文提出一种基于多蚁群并行优化的网络路径规划算法,按照一定的策略对关键网络资源进行调度分配,尽可能为每一个任务规划满足网络属性约束及用户服务质量要求的独立网络路径,使任务完成率最高。仿真示例验证了该模型和算法的正确性。     

一种为地面WSN充电的无人机碰撞规避路径规划方法

多个无人机为大面积分布的地面传感器节点无线充电的应用中,飞行路线的规划关系着无线传感器网络的覆盖率及生命周期,但无人机有限的续航时间及规避碰撞等约束增加了路径规划的难度。文中首先提出一种集中式逐次贪婪路径规划算法(Sequential Geedy Route Planning Scheme,SGRP),令无人机在已知节点位置信息的情况下,根据自身的资源逐个将节点纳入任务集并放置在路径的最合适顺序上。理论证明,SGRP算法在最差情况下也能获得最优规划算法50%的性能。接着在SGRP算法的基础上,基于改进的CPA碰撞检测模型设计了逐次贪婪碰撞规避路径规划算法SGACRP。该算法每次迭代选择一个节点、无人机及路径顺序的最佳匹配组合,在最大化收益的同时满足了无人机资源受限及碰撞规避的要求。最后以时间折扣型函数作为无人机收益函数,通过仿真验证了碰撞规避措施的有效性,同时验证了碰撞规避算法虽然增加了无线传感器网络的总充电完成时间,但并不影响其监测率。另一方面,仿真证明了根据与目标点的距离设置节点的固定收益,能有效改善地面无线传感器网络的监测概率。     

基于协同进化的混合变量多目标粒子群优化算法求解无人机协同多任务分配问题

无人机多机协同控制系统近年来已被广泛地应用在军事打击、海洋监测、陆地航拍和灾情探测等领域.针对无人机协同多任务分配问题,为了更加准确地描述无人机协同多任务分配场景,本文考虑实际应用场景下的多种复杂约束,并以无人机飞行总航程最少和任务完成时间最短为优化目标,构建了混合变量多约束的无人机协同多任务分配问题模型M-CMTAP.为了高效求解上述模型,本文提出一种基于协同进化的混合变量多目标粒子群优化算法C-MOPSO.C-MOPSO采用基于任务分配和路径规划的编码方法表示无人机的任务分配结果和路径规划结果及基于约束处理的可行解初始化方法生成可行粒子;同时利用基于结构学习的重组策略对粒子进行更新以提高种群的多样性和收敛性;并引入协同进化策略在两个子种群之间进行合作进化以提高算法的搜索效率.根据无人机和目标的分布状态设计4个代表性的测试实例并验证算法性能,实验结果表明,与其他采用协同进化策略的算法相比,所提算法在解的收敛性和解集多样性上均具有显著的性能优势.     

多约束下多无人机的任务规划研究综述

高度信息化的发展使得无人机作战优势凸显。准确的无人机任务规划技术是完成给定任务的重要保障。任务分配、路径规划是构成无人机任务规划技术的两个核心部分。基于该技术,首先讨论了无人机任务规划的发展状况、分类标准、体系结构。其次,分别详细介绍了影响任务分配、路径规划的重要指标,如分类标准、约束指标、相应模型、代表算法、评价指标等,然后,分别分析对比求解任务分配的启发式算法、数学规划方法、随机智能优化算法的优缺点和求解路径规划的数学规划方法、人工势场法、基于图形学法、智能优化算法的优缺点;最后,总结了无人机任务规划存在的开放性问题、未来发展方向和研究重点。     

自适应RRT无人机航路规划算法研究与仿真

在复杂环境的航路规划问题研究中,为了降低无人机的飞行代价,需要在规划耗时和路径质量两方面达到一个较好的均衡.为此,提出动态步长和自适应权重相结合的RRT算法,有效地解决了规划耗时和路径质量的均衡问题,并用三次多项式BSpline对路径进行平滑处理.仿真结果表明,在相同的任务环境中,与交叉PSO相比较,动态步长的自适应RRT算法失败次数减少了4252次,耗时降低了89ms,飞行距离减少了4.247 km,且平滑后的路径更加符合无人机实际飞行的需要.     

邻域约束下空地异构机器人系统路径规划方法

针对一类带邻域约束的空地异构机器人系统的路径规划问题,提出了一种利用混合整数凸优化模型进行求解的方法.异构机器人系统由一台空中飞行机器人与一台地面自主移动机器人构成.机器人系统的任务是按给定顺序访问已知的目标序列.由于空中机器人每次持续飞行时间受限,因此必须及时返回地面机器人以节省能量或补充能量.分别考虑了空中飞行机器人和地面移动机器人的最大运动速度,空中飞行机器人的最小充电时间、最大滞空时间,以及各目标位置的邻域等约束,以完成所有目标序列访问任务的总时间最短为代价,建立了相应的目标优化模型,从而将机器人系统的路径规划问题转化为混合整数凸优化问题.基于建立的凸优化模型,考虑飞行机器人起降过程的时间消耗,分析了无人机起降过程的敏捷性能对路径规划结果的影响.最后通过仿真实验验证了所提方法的可行性和有效性.     

基于滚动时域优化的机场起降动态调度

为了减少作战时军用飞机实际起降时刻与计划起降时刻产生的偏差,提出一种基于滚动时域优化原理的动态机场起降调度策略,分析军用飞机起降过程中的时间窗口约束和尾流间隔约束。对进入每个预测窗口内的飞机队列,以加权提前/延误时间和最小作为目标函数,将军用飞机起降调度模型转换为带到达时间的单机加权E/T调度模型。设计一种针对自然数域的离散粒子群算法,并应用该算法进行模型求解。通过仿真实验确定了算法的参数,仿真结果说明了模型和算法的有效性。     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

物流配送中心配载车辆调度问题研究

物流配载车辆调度目标就是针对特定任务调配车辆资源以降低成本费用。分析了车辆和特定运输任务的相关约束条件,提出了物流中心配载车辆调度问题数学模型。重点研究了基于任务时间窗逻辑顺序约束求取可行解的“分组”算法、以及基于时间窗约束冲突概率对可行解基因实施交叉的优化算法。实验结果表明在多任务、多约束条件下采用该算法可快速求取物流配载调度问题的最优解。     

基于改进动态规划的无人机搜寻航迹规划研究

针对传统动态规划算法在无人机航迹规划中存在耗时长以及冗余节点的问题,提出了一种基于多阶段决策的改进动态规划算法.在单向动态规划算法中加入双向策略,结合顺序法和逆序法以减少搜寻空间的状态总数;利用区间单调性和四边形不等式进一步减少每次决策涉及的状态点,得到优化后的状态转移方程,降低了搜寻的时间复杂度.最后,对改进动态规划...     

基于三维时空地图和运动分解的多机器人路径规划算法

针对当前多机器人路径规划策略中存在的路径耦合性高、总路径长、避碰等待时间长等缺点，以及由此导致的系统鲁棒性低、机器人利用率低等问题，提出了基于三维时空地图和运动分解的多机器人路径规划算法。首先，根据已有路径集和当前机器人的位置生成时间维度上的动态临时障碍物，将其与静态障碍物一并拓展为三维搜索空间；其次，在三维搜索空间内，将路径运动总时间拆分为运动时间、转向时间和原地停留时间这三个参数，并使用条件深度优先搜索策略计算出从起始节点到达目标节点的所有符合参数要求的路径集合；最后，遍历路径集合中的所有路径，对于每条路径，计算其实际总耗时。如果某一路径的实际总耗时和理论总耗时之间的差距小于规定的最大误差，则可认为该路径为最短路径，否则，继续遍历剩下的其余路径；而如果路径集合中所有路径的实际总耗时和理论总耗时之差全都大于最大误差，则需要动态调整参数，然后继续执行算法的初始步骤。实验结果表明，所提算法规划的路径具有总长短、运行时间少、系统无碰撞、鲁棒性高等优点，解决了多机器人系统完成持续随机任务的问题。     

精英扩散蚁群优化算法求解运输无人机三维路径规划

针对受灾山区运输物资的三维无人机路径规划问题,提出了一种精英扩散蚁群优化算法EDACO,首先通过极值限定策略限定了信息素浓度的范围,防止算法前期陷入局部最优;然后采用精英策略改进信息素浓度更新公式,加强优质个体对种群的影响力; 再引入信息素扩散策略,加强距离较近个体间的交流协作,以防止蚂蚁个体间联系不紧密造成的算法停滞。最后,将精英扩散蚁群优化算法、传统蚁群算法、遗传算法和萤火虫算法运用于4个山区受灾无人机运输实例中,结果表明了EDACO的优越性和有效性,且该算法对无人机三维路径规划问题有着良好的适应性。     

基于顺序扩展一致性包算法的多无人机分布式任务分配

以异构多无人机协同执行复杂的耦合多任务为背景,提出一种求解分布式任务分配问题非死锁的顺序扩展一致性包算法.首先,建立考虑任务载荷资源、任务时序、威胁区等约束条件的时序多任务分配模型;其次,对一致性包算法的任务包构建过程和冲突消解规则进行扩展,并设计一种基于有向图深度优先搜索的方法进行任务方案的死锁检测和修正,以实现无冲突和无死锁的任务分配;然后,将关联任务之间的时序约束转化为软时间窗约束,利用顺序分层的策略进行求解;最后,为了提高任务分配结果的可靠性,采用Dubins曲线路径将航路规划耦合到任务分配中.仿真实验表明,所提出的算法能够快速有效地求解异构多无人机分布式耦合多任务分配问题,具备良好的最优性和时效性.     

考虑冲突和拥堵的自动导引车调度与路径规划协同优化

针对自动化集装箱码头自动导引车（AGV）调度与无冲突路径规划问题,提出了AGV冲突拥堵解决策略以生成无冲突路径。首先,考虑堆场缓冲支架的容量,运行路径无拥堵、节点无冲突约束,以最大完工时间最小、AGV总行驶时间最短为目标建立两阶段混合整数规划模型;其次,设计改进的自适应遗传算法、基于冲突拥堵解决策略的迪杰斯特拉算法求得AGV调度方案与无冲突路径。算例分析结果表明：改进的自适应遗传算法相较遗传算法平均求解时间降低了13.56%,且目标函数平均差距率为9.01%;基于冲突拥堵解决策略相较停车等待策略使得水平运输区拥堵度降低67.6%,AGV等待时间减少66.7%。可见,所提算法求解质量高且速度快,同时验证了所提策略的有效性。     

基于三维时空地图和运动分解的多机器人路径规划算法

针对当前多机器人路径规划策略中存在的路径耦合性高、总路径长、避碰等待时间长等缺点，以及由此导致的系统鲁棒性低、机器人利用率低等问题，提出了基于三维时空地图和运动分解的多机器人路径规划算法。首先，根据已有路径集和当前机器人的位置生成时间维度上的动态临时障碍物，将其与静态障碍物一并拓展为三维搜索空间；其次，在三维搜索空间内，将路径运动总时间拆分为运动时间、转向时间和原地停留时间这三个参数，并使用条件深度优先搜索策略计算出从起始节点到达目标节点的所有符合参数要求的路径集合；最后，遍历路径集合中的所有路径，对于每条路径，计算其实际总耗时。如果某一路径的实际总耗时和理论总耗时之间的差距小于规定的最大误差，则可认为该路径为最短路径，否则，继续遍历剩下的其余路径；而如果路径集合中所有路径的实际总耗时和理论总耗时之差全都大于最大误差，则需要动态调整参数，然后继续执行算法的初始步骤。实验结果表明，所提算法规划的路径具有总长短、运行时间少、系统无碰撞、鲁棒性高等优点，解决了多机器人系统完成持续随机任务的问题。     

基于改进蚁群算法的无人天车路径规划

针对无人天车在吊运过程中的路径规划问题,提出了改进蚁群算法以优化天车路径.首先,综合考虑无人天车的行驶距离和任务等待时间,建立具有时空约束的路径规划数学模型.其次,改进常规蚁群算法的启发信息和信息素更新机制,并根据任务执行顺序限制条件和任务优先级系数改进蚂蚁的路径选择策略,以得到改进的蚁群算法.仿真结果表明,改进蚁群算法规划所得路径在路径长度和任务等待时间上均优于传统算法,证明了应用改进方法优化无人天车路径的可行性和有效性.     

卡车搭载无人机的同时取送货路径规划研究

降低“最后一公里”配送和“最初一公里”取货成本是物流行业亟待解决的难题，无人机配送不受地形限制、速度快、能耗小，据此提出卡车搭载无人机的同时取送货运输模式。以总运输成本最小为求解目标，建立混合整数规划模型，通过K-means聚类算法求出无人机的起降点，采用遗传算法求出卡车和无人机的运输路径。在仿真实验中，提出的卡车搭载无人机同时取送货运输模式的成本比取货-送货分离运输模式降低了26.78%,比卡车与无人机独立的同时取送货运输模式降低了21.91%。