多机协同路径规划算法验证
- 采用Inself的三级算法，相比传统图论算法或A*、Dijkstra算法，随着地图规模上升，时间空间复杂度优势非常明显
- 系统较为完整，人机交互完整，能够为管理员、用户端提供不同的交互方式
- 基于多基站式的分治策略，更符合未来空域管理思路
- 模拟一种微信用户下单，无人机系统派送，多基站管理系统实时根据天气和无人机运行情况进行统一调度，并通过云服务器异步通信，完成整个系统功能
本算法杨文哲同学大二刚刚转系后杜老师的计算机基础课上，参加的个人向课外设计，通过一学期的设计和开发，完成了初步的三步走的调度算法设计，以控制台打印形式简单演示，并不断优化迭代，最终获得该必修课满分免试。
后到大三时与杜佳诺、李明翔进行冯如杯论文比赛时，对算法进行了更加详细可复现的性能对比、论文撰写；并与张斌、王伟哲等几位同学再次进行小程序、web后端开发封装，将其作为一个完整系统作为大三下综合创新课程大作业提交。
后端调度策略代码见此文件夹 算法主要在Inself.h, Inself.cpp 中，其他为外部加载、项目前后端代码
在Dijkstra、A*算法中，随着路径的拓展，每轮维护的优先队列数量会越来越大，导致计算时间越来越慢，(A*为加入启发项，但均为最短路径算法，本质没有改变，均为维护一个优先队列，区别在于Dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A*算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。
而DFS算法属于无头苍蝇横冲直撞，撞出一条路来，优点是内存固定，不会存在优先队列数量剧增问题，但缺点也很明显：会走很多弯路，路径长度不稳定。
本文想法是将A*和DFS进行结合，利用DFS中内存固定的优点，加入启发项让其每次只走没走过的且距离评估更小的路径，保证了较快搜索出一条相对较短的路径；对于死角死胡同等情况，第一次会出现一摊连续面积的路径，故在第一级算法搜出的路径中采用A*, Dijkstra进行最短源搜索。两步组合在一起，能够在时间和路径长度上进行折中。最后，由于现实路径非栅格地图，可能存在非0/45/90°的路径，于是对路径的拐点角折线进行缩短优化，得到最终的现实路径。以上为Inself算法的三步走策略概述。最终在此算法基础上，加入小程序开发、web后端等功能，形成一套可以多机器多进程运行，多用户测试的系统，设计为多无人机路径规划导航，用于未来无人机外卖等场景，测试视频已附。