吴汶钊 (威海紫光实验学校 山东 威海 264200)
【摘 要】 随着“互联网+”时代的到来,物流行业需求迅速扩大,迎来高速繁荣发展,与此同时,传统物流行业效率低下、成本较高等弊病也日益明显。无人机已经在诸多领域具有成功实践基础,将成为有效解决以上问题的方式之一。本文将结合人工智能相关算法和技术,简要阐述无人机在物流运输过程中的现状以及运输原理,提出用于此领域的蚁群算法的优化方案,并于其实现与检验进行设计,旨在为物流运输情境下的的无人机路径规划优化提供参考,以达到提高物流运输效率的最终目的。
【关键词】 无人机 物流运输 蚁群算法 协同路径规划技术
中图分类号: V249 文献标识码: A 文章编号:ISSN1004-1621(2020)11-049-04
1 引言
1.1无人机在物流产业的应用现状
从2013年国际电商巨头亚马逊创始人贝佐斯提出“Prime Air”无人机快递项目到2016年末商业性无人机送货首飞的成功,短短三年时间,亚马逊极富前瞻性地将无人机产业与物流产业巧妙结合,为传统物流行业的改革奠定了基础。同样,2020年初,新冠疫情导致许多乡村封村封路,与外界隔绝,京东物流也利用无人机将物资运输到所需地点,为居民提供了便利。可见,无人化、智能化将会是物流运输转型的一个必然导向。
无人驾驶飞机是一种以无线电遥控或由自身程序控制为主的不载人飞机。目前而言,无人机控制系统的自动化可以保证自动控制飞行,但是智能控制程度不高,这就必然会增加无人机在物流系统运用时的人力成本,同时会因为运输分配缺乏统筹规划而降低运输效率。因此,为实现无人机下一步在物流运输中的产业化、全域化发展,就必须依托人工智能技术的进步。
无人机运输的智能化是从单机智能、多机协作等多方面展开的,目前无人机领域对于人工智能技术的应用已经有了充足基础,下文将对于部分应用原理进行阐释。
1.2单机的自主规避原理
单机智能是指面向实时变化的任务环境,无人机应该能够做到感知周边环境、自主识别目标属性并规避障碍物、机动灵活并容错飞行、具有人脸或指纹识别能力、能够用自然语言与人交流等。而在运输过程中尤为重要的是自主规避即对路况信息的采集、对目标属性及特点的识别以及调节最优飞行路线。
路况信息的采集可以通过微波遥感技术来实现。微波遥感技术是利用各种物体或物质反射或发射出不同特性的电磁波进行遥感的微波遥感器。它不受或很少受云、雨、雾的影响,不需要光照条件,可以全天候、全天时地取得图像和数据。又因为微波有一定的穿透能力,故便于探测出障碍物密集环境的信息。这些特点与物流运输环境复杂、运输目标多样等局限性相适应,可以更好地发挥其所长。
采集信息的识别主要利用深度学习算法(卷积神经网络 CNN 算法)识别微波遥感传输来的图片数据。卷积神经网络是第一个真正多层结构的有监督的深度学习算法。深度卷积神经网络具有准确率高、所需训练样本集较大的特点,相比于传统方法能够取得较优的结果[1]。首先根据无人机运输实际可能遇到的目标,收集海量路况数据,利用卷积神经网络算法进行训练,学习各个目标的特征,形成障碍物特征数据库。在物流运输过程中,根据微波遥感传回的数据实时处理单元提取图像关键点,对图像进行图像变换和滤波预处理,将处理后的图像输入到障碍物特征数据库中进行比对,达到目标识别的目的。
飞行路线的调整将依据遗传算法进行实施路线规划。遗传算法(Genetic Algorithm)[2]是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。它从代表问题可能潜在的解集的一个种群(population)开始的,一个种群是由经过基因(gene)编码的一定数目的个体(individual)组成,每个个体实际上又是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,决定了个体的形状的外部表现。在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解。同理应用在飞行路线的规划,首先对应对障碍物的飞行路线进行数字化编码,然后用随机数初始化一个种群,种群中的个体即前一步数字化的编码。通过适当的解码过程后,用适应性函数对每一个基因个体作一次适应度评估,进而选择一条飞行环境温和的线路,再操纵动力系统依据已选路线进行飞行控制。
单机作为协作的单体,承担着向中枢反馈实时信息以及接收中枢传达方向性指令的责任,其智能程度影响着多机协作的任务复杂度,下文有关多机协作的构想建立在单机智能程度足够高的基础上。
1.3多机协作中协同路径规划的原理
多机协同智能具体含义包括:①执行任务时协同行动的能力;②利用和共享跨领域UAS传感器的信息来无缝地指挥、控制和通信的能力;③能够接收不同系统的数据、信息和功能服务,并使他们有效协作的能力;④能够提供数据、信息和功能服务给其他有/无人系统的能力[3]。而广泛应用于物流运输领域的关键技术包括协同路径规划技术以及协同态势生成与评估技术。
多无人机的协同路径规划作为多机协作的一个应用,是指在单个无人机基础上的以协同完成任务为目的的多目标规划方法,一般用在任务集较大且任务完成有先后次序的规划上效果尤为凸显。[4]从宏观上着手海量物件的分配运输就需要协同路径规划技术作为支撑。
在诸多无人机的路径规划的最短路线算法中,能处理动态环境的智能动态算法主要包括蚁群算法、神经网络算法、遗传算法、粒子群算法等。[5]本文将就蚁群算法做出总结并对其进行优化的猜想。蚁群算法是一种模拟蚂蚁在现实中觅食行为而产生的一种具有随机不确定性的智能优化算法。通常,设定物件的派发处为起始点,不同物件的派发目的地为路线节点,再设定无人机回收地点为目标点,同时需要给予环境状态的规划图,且赋予各点之间连线相同的信息素。“人工蚂蚁”从起始点出发,遇节点时进行自主判断,待有限的蚂蚁覆盖全部节点且到达目标点,一次迭代结束。接着,进行各路线上的信息素更新,重复迭代,直到收敛到最优解,算法结束。此时,多无人机的最优派送路线即已生成。
蚁群算法具有鲁棒性强以及高度并行性的特点,然而容易陷入局部最优解,且其计算开销较大,对物流产业计算效率和引入成本问题上出现了较大的挑战。
2协同路径规划算法优化方案
2.1多机协作中协同路径规划的原理
无人机在物流运输环境中往往有多个威胁源,即,运输过程中可能导致事故的静态建筑物或动态障碍物等。这些威胁源由于自身属性不同和分布不同对无人机的物流运输有着不同的影响。本文将不同的威胁源分布抽象成一些规则,用函数表示其变化规律,基于此假定一种带有综合威胁场的带权Voronoi图作为本文无人机的环境的描述模型。
带权Voronoi图是由二维平面中的生成点生成的一种能模拟无人机场景中威胁场分布的图形。它是由一组是空间中生成点两两连线的垂直平分线段组成的平面图。随着无人机环境的不断变化,带权Voronoi图会实时随着威胁源位置的改变而更新,动态地构建与分析。
本文设定的初始环境是空间内的二维Voronoi图,且Voronoi图是由多个障碍物生成的。此外,Voronoi 图中的线段段为无人机的飞行可行轨迹,交点为无人机飞行过程中航线的拐点,称为航迹点。为了更好地对问题进行描述,在无人机的实际飞行中做出以下假设[5]
(1)无人机视为质点,且飞行速度恒定;
(2)环境中的威胁源均为已知威胁源;
(3)无人机飞行过程中高度不变。
Voronoi图环境建立后,本文对其中的边赋权值,目的是更好地衡量无人机在飞行过程中受到威胁的程度。为满足实际物流运输需求,本文对不同种类威胁源威胁程度做了不同的处理,由此确定Voronoi图中各边的权值。图1为一个可能遇到的Voronoi图。
.png)
2.2多机协作中协同路径规划的原理
为解决基于环境先验知识的无人机路径规划问题,可采用的最短路搜索方法很多,当环境的生成点规模较大时,传统的确定算法性能上耗费较大,本文拟使用改进蚁群算法在给定起止点和Voronoi图环境的情况下进行最短路径的搜索。
基于带权Voronoi图的无人机的规划时,需要做到几点准备工作:
(1)记录无人机的巡航高度、起始点和目标点(单任务),
(2)获取巡航环境内的威胁源信息,
(3)构造对应高度的无人机环境二维Voronoi图,
(4)使用最短路优化算法在二维平面Voronoi图中从起始点到目标点的带权初始最短路径,
(5)平滑最短路径。
图2是环境建模下单架无人机的路径规划过程。研究无人机协同规划的前提,需要理解单架无人机的路径规划问题。通常情况下,无人机的飞行环境是三维的,但由于飞机在飞行过程中一般不频繁改变高度,所以无人机在大部分时候都是沿着预定的高度飞行。为简化起见,本研究中使用二维路线进行路线规划优化的研究。图2表示的是某一高度的二维带权Voronoi图的构建流程,基于三维空间该高度可能存在一些来自地面或者高空威胁物的威胁,获取到这些威胁源的信息分析并做出威胁值的预测,用确定的威胁源作为生成点生成二维Voronoi图,并对图上的边赋予威胁权值,接着采用最短路算法进行最短路的搜索工作,最终得出静态环境下无人机的初始最短路,再用平滑算法对初始路径进行平滑,得到最终的最短路径。
.png)
2.3蚁群算法的优化设计
蚁群算法是通过模拟蚂蚁在现实自然过程中的觅食行为而产生的一种智能优化算法,也是一种随机不确定算法,其优势在于它可以解决不确定性问题,物流运输的过程数据庞大,确定性算法无法在多项式时间内解决问题,且问题本身对解的要求又不严格,新兴的智能性算法有了自己的舞台。
蚁群算法的前提需要给定出发点和目标点,以及能表示环境状态的规划图,赋予图中边相同的信息素。信息素是蚂蚁找到食物以后,向环境释放的一种挥发性分泌物,信息素浓度的大小表征路径的远近,可以吸引其他的蚂蚁过来,达到指引的目的,这个概念在算法中以Voronoi图的权值体现。此后,一批给定数量m的人工蚂蚁将从起点p出发,并且沿着规划好的环境图中的边寻找终点q,在蚂蚁走到一个节点时,是会根据自己独特的思维去判断接下来的路口该选择那个方向,如此继续,直到当这一批蚂蚁中所有蚂蚁均完成了一次搜索,一次迭代结束。接着,蚁群算法需要对每个蚂蚁各条解路径进行信息素的更新。每次迭代均须更新信息素,这些信息素信息将导致接下来的每一代蚂蚁选路的重要参考,直到固定迭代次数D完毕,算法此一般都已经收敛到了最优解,此时算法结束。[4]
2.3.1 设定禁忌路线
传统的蚁群算法默认蚂蚁都能找到一条从起始点到目标点的完整路径,本文的环境是基于复合威胁场的Voronoi图,仿真的目的需要寻找一条从起始点到目标点的带权最短路。如下图所示,由于蚂蚁在随机搜索路径时有一定的随机性,当蚂蚁走到Voronoi图中的某些边时,例如图3中的红色X边,由于禁忌表(蚂蚁不能往回走已经走过的路)存在的缘故,蚂蚁此时已经无解,且当前蚂蚁搜索结束,无法获得完整解。
.png)
我们需要明确城市飞行禁忌区域,定时下达禁止飞行的命令,就可以大大减少运算过程中蚂蚁算法的计算量。禁忌路线根据车流量人流量以及特殊功用进行实时检测设定。
2.3.2添加启发式信息
在Voronoi图中,各条边都受到综合威胁场的影响,都带有一定的权值,算法最终选择威胁度最小的路径为最终路径,传统的蚁群算法由于算法初始化参数的不同,会呈现不同的收敛情况。并且在Voronoi图的环境较复杂时,蚂蚁最终的结果也会受到开始几代蚂蚁的结果的影响,由于原始蚁群可能存在的问题,在目标点处,可以加入一种启发式因子,这种启发式信息会随着迭代次数的增加不断衰变。我们可以运用万物互联的思想,在设计运输路线时,将已有物流案例进行分析和基础信息素的采集并导入,增加蚂蚁对Voronoi图的了解程度。
2.3.3设定信息素阈值
引用最大最小蚂蚁系统的阈值限定方法,应对蚁群算法易陷入局部最优解的缺点。设信息素的上限A,下限B。上下限信息素的限定,确保了算法的稳定性。若信息素浓度超过最大信息素A则保持最大信息素不更新,若小于最小信息素B则保持最小信息素不更新。在信息素更新过后对各边上的信息素的量进行限定,使其处在范围[A,B]内。
由于物流运输对于最优路线无要求,只需将含恶劣环境的路线排除,保证运输环境保持相对温和即可。因而局部最优解仍然可能适用,但是仍然存在局部最优整体恶劣的可能,因而通过阈值的设定对算法进行进一步优化。
3协同路径规划优化算法检验方案设计
3.1 实验设施
由于实验具有不确定性和危险性,且主要是对算法的有效性进行检测,因而主要通过虚拟现实技术模拟试飞行场景。这样既可以避免事故所造成的伤害,又能设置理想环境,调节环境障碍物的参数。
在本实验设计中,使用大疆禅思 Zenmuse H20系列载物无人机,同时配备轻质容器,以便模拟装载不同状态的物品。另装载不同质量金属砝码数块,和一定量的水。
3.2 实验环境
虚拟现实的环境应该为可控的动态理想户外环境。
环境应从以下方面提供变化:
(1)威胁物的威胁值。对于真实环境的已有静态威胁输入相关赋值,对于动态变化的环境输入威胁值范围,将真实环境数据化,再利用虚拟现实技术模型化。赋值的标准含物体的体积,外观规整度,运动速度方向等方面。
(2)威胁物密度。依据不同高度实际情况下威胁物多少,构建虚拟环境中不同高度的威胁物
3.3 实验验证设计
实验中基本流程根据随机生成的威胁源生成Voronoi图,并对图中的各条边赋予威胁权值,然后利用改进蚁群算法搜索最短初始路径,设定蚂蚁只数为50,最大迭代次数为Dmax=100,改进的蚁群算法对其他参数做出修改,通过对运输效果的判断比较计算效果。下表给出了实验中两算法重要参数的对比。
.png)
我们设定E为算法最终效果参量,该参量主要由三个变量控制。
(1)计算机得到路线的收敛速度δ,该参数主要以迭代次数的形式呈现。
(2)运输路线所需理想时间T,即虚拟环境中从无人机开始送货至到达目的地的时间间隔。
(3)运输路线平稳度ω,该变量通过无人机负载的容器所装液体倾撒量体现。实验中将装载容器分别盛放满水进行实验,在抵达目的地后测量容器内剩余水所占比例,继而得出相关变量ω的值。
据实验得到的数据,代入表达式E=δT:(γω)。其中γ是针对不同运输物品可人工设置的平稳度要求参数。据此,当所得E值越小时,即可在理论上证明算法收敛路线效率高,进而证明算法优化的效果。由于受到时间、资源和信息的限制,在本研究中尚未对具体的路径规划作出验证。相关的研究可望在未来条件具备时进一步开展。
4结语
随着无人机融入人工智能,具备了自主运行的能力,其涉及的社会问题将更为复杂,如隐私侵犯、航行安全以及无人机容易遭到人为破坏等。要解决这些问题,实现无人机在物流运输行业的广泛应用,需要全社会共同努力——政府完善监管体系,国家出台相关法律;对无人机进行实名制管制,依法追责到人;可以规定限制空中飞行路线,划定无人机飞行区域;可以让无人机提供商的云数据库提供输入接口,进行数据共享和监控;公民养成防范意识,树立包容态度等等。
同即使以上社会问题得到妥善解决,要做到于物流运输行业的无人机普及也还有很长的路要走。完成物流无人机的普及需要对当前物流硬件进行大规模升级改装,同时需要大量相关服务站点提供待机位置,后台网络串联客户与无人机的服务信息,以及相关专业的常驻技术维护人员,这些都不是能够一蹴而就的。相信在当前科学技术水平迅速发展的时代,我们所畅想的无人机智能配送将会很快实现。
参考文献:
[1]郭迎, 吴蕴翔. 人工智能背景下的无人机手势识别设计研究[J]. 科技创新与应用, 2018, No.242(22):44-45.
[2]https://baike.sogou.com/v100038.htm?fromTitle=
遗传算法
[3]樊邦奎, 张瑞雨. 无人机系统与人工智能[J]. 武汉大学学报(信息科学版), 2017(11):1523-1529.
[4]袁利平, 夏洁, 陈宗基. 多无人机协同路径规划研究综述[J]. 飞行力学, 2009(05):1-5.
[5]刘浩. 多无人机协同路径规划技术研究及模拟实现[D].15-16,31-32.