能耗最小的校园无人机路径规划设计问题研究文献综述
摘要：无人飞行系统由无人机、无人浮空器、跨介质无人飞行器等各类飞行平台、任务设备、信息传输设备及地面配套设备组成，可以自主感知、自主决策、相互协同执行任务，具有“平台无人、系统有人”的属性和环境适应能力强、自主程度高、非接触、零伤亡、可长时间工作的特点，在军事和民用领域中具有广阔的应用发展前景，是世界各国高度重视的新技术、新方向。中国的无人机生产和设计享誉海内外，带动了大量的潜在应用。但是无人机存在携能少、续航时间短等问题。这一问题制约着无人机技术的运用。
本文旨在分析当前已有的技术成就，对其各方面进行探讨，结合已有的知识，进行概括总结，着力解决这一问题。
关键词：无人机；Dijkstra算法；优化
一、Dijkstra算法与不足
Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。改算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
但这个算法存在不足之处。Dijkstra算法主要诞生于计算机科学及运筹学领域，大多数算法均存在一个问题：在设计过程中只考虑了抽象网络的拓扑特性，力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间、复杂度而忽略了具体网络可能具有的空间分布特性。而要利用于GIS网络分析中，又不能不考虑具体应用网络中的相关空间分布特性，所以必须解决这个问题。另一方面，在Dijkstra一般算法中，临时标记结点无序地存储在无序表中，这无疑成为Dijkstra算法的瓶颈。
- Dijkstra算法的优化（椭圆限制搜索区域算法）
鉴于Dijkstra算法的不足，需要提出一个新的算法，或者在此基础上进行优化，以设计出一个能够符合人们要求的算法，解决当前的问题。付梦印，李杰，邓志红在《限制搜索区域的距离最短路径规划算法》一文中提出了一种优化的算法---限制搜索区域的距离最短路径规划算法。从几何学知，两点间直线距离最短。受此启发，在实际城市道路网中对给定两点进行路径规划时，从起始点s到目标点D的连线方向，基本上代表了最短路径的大致走向也就是说,最终的最短路径基本是在两节点连线的两侧，而且通常在其附近，在两节点间存在一条边的情况下，边本身就是最短路径。应该说明的是，在靠近两节点的附近，有时可能会出现短距离的反向路径(所谓反向路径,这里指在线段SD的两端点外,沿SD或DS延长线方向的路径，反映在实际系统中，这通常代表车辆为转入合适车道行驶所走过的路径)图1给出了在给定路径规划的起始点S和目标点D时，经典Dikstra算法和新算法(为叙述方便,将限制搜索区域距离最短路径规划算法简称为新算法)从S到D的距高最短路径扫过的搜索区域对比示意图。
图1 经典Dijkstra算法和新算法的搜索区域对比示意图
