# EGO-Swarm
[论文来源](https://github.com/ZJU-FAST-Lab/ego-planner-swarm)
## 摘要
这篇文章主要是提出一个在复杂环境下去中心化异步系统性的多无人机自动导航解决方案。在基于梯度的局部规划框架中，通过将*碰撞风险作为一种惩罚非线性优化问题*来避免碰撞。为了提高鲁棒性和避免局部最小，本算法运用了**轻量级的拓扑学路径生成方法**；使用**可依赖的路径分享网络**，多无人机能够生成安全、平坦、满足动态可行性的路径。
## 介绍
### 背景
很少有研究工作将四旋翼群在未知环境下的单智能体自主导航和已知环境下的多智能体精确编队控制结合起来**展示能够导航共享相同未知空间的四旋翼群的真实世界系统**，特别是只有onboard处理。
### 问题
在未知环境中部署多个四旋翼遇到的问题包括但不限于
* *障碍物参数化的重要性*(nontriviality of obstacle parameterization)
* *感应范围有限*(limited sensing range)
* *不可靠和带宽有限通信*(unreliable and bandwidth limited communication)
* *定位漂移*(position drift)
### EGO-Swarm的优点
它在**不需要外部本地化和计算或预先构建的地图**的情况下，使得无人机群高性能的在拥挤环境中飞行，并且完美的解决上述问题。
### 算法组成
*
拓扑规划(topological planning)
* 拓扑规划有效的**避免了局部最优**。
* 因为在EGO-planner中**前端拓扑路径搜索是隐式完成的**，所以大大**节省了计算时间**。
*
相互碰撞避免(reciprocal collision avoidance)
* 去中心化的相互碰撞避免算法是通过**在目标函数中添加一个无人机碰撞的权重惩罚来实现的**。通过将未来时间的代理分布与正在优化的轨迹进行比较来评估这种惩罚。
* 为了**尽量减少数据传输并允许不可靠的通信**，**广播网络**(broadcast network)用于分享轨迹。 为了纠正相对定位漂移(relative localization)，附近的无人机的观察和来自轨迹评估的预测进行比较。(应该就是将别的无人机看到的情况和自己本身的路径规划进行比较)
## 算法大致步骤
### 基于梯度的局部规划的隐式拓扑轨迹生成
* A.一个无 ESDF 的基于梯度的局部规划器：EGO-Planner
* B.隐式拓扑轨迹生成
### 无人机群导航
* 相互碰撞避免
* 定位漂移补偿
> 一种简化且轻量级的相对漂移通过比较从接收到的代理轨迹评估的预测位置和从目击代理的深度图像中测量的位置，提出了估计方法。
* 从深度图像中去除无人机
> 移动的无人机已经在**相互碰撞避免**中考虑过了，所以在地图建造和轨迹规划的时候没有必要将无人机考虑进去。
## SYSTEM ARCHITECTURE
* **单无人机导航系统 **：EGO-Planner+VIO（vision inertial odometry）偏移补偿+从深度图像中去除其他无人机
* **通信框架**
* 一个共享轨迹的**广播网络**(broadcast network)
> 一旦无人机生成一个新的无碰撞轨迹，立即向所有无人机广播 。然后其他无人机接收并存储该轨迹用于在必要时为自己生成安全轨迹。这种闭环策略在理想情况下正常工作连接稳定和延迟的情况 可以忽略不计。但是，这在实践中并不能保证。 因此提出了两种方法来降低这种可能性碰撞的 方法
>
> * 在网络容量满足的情况下以给定频率将轨迹进行广播。包含三维位点的轨迹一般小于0.5KB，一般的无线网络可以达到1Mbps。
> * 每个无人机检查碰撞，一旦从广播网络接收到轨迹， 如果检测到潜在的碰撞，则无人机生成新的无碰撞轨迹 。
* 一个用于同步时间戳和管理顺序启动的**链式网络**( chain network)
>这个策略避免在系统启动期间,无人机因为没有其他无人机轨迹的信息同步造成的 生成轨迹时引起的混乱 。
## 比较
### Topological Planning
EGO-Swarm和Fast-Planner的比较：
* EGO-Swarm找到的可行轨迹（candidates trajectory）较少，这意味着找到全局最优的概率较低，但速度更快。
* Fast-Planner通过 PRM图搜索、路径缩短和路径修剪来寻找拓扑路线，这些都是耗时的方法，但与隐式拓扑路径搜索方法（EGO-Swarm使用的方法）比较而言，相对自由度更高。
### Swarm Planning
下面的表格表示使用4种不同的规划器在*飞行距离d~fly~(m)、飞行时间t~fly~(s)、每个无人机碰撞次数Collision和计算时间t~cal~(s)*进行比较。
* RBP：RBP 倾向于产生**安全的但保守的轨迹，因为凸形的飞行轨迹相对安全，但是减少了解决方案的空间**（就是每一条轨迹太占地方了）。
* DMPC：专为分布式部署而设计。然而，它需要**准确和高频姿势通信**，在真实的应用程序中无法保证。
* ORCA： 高效的规则使ORCA 更新很快。 然而，**使用速度作为控制命令使其与四旋翼等三阶系统不兼容**。 这样的碰撞风险也限制了它的应用。
* EGO-Swarm：所提出的方法**生成最短的无碰撞、非保守轨迹，计算速度最快**。
## 总结
在本文中，提出了一种仅使用onboard资源在未知杂乱环境中进行多机器人导航的系统解决方案。 基准（Benchmark）比较表明其计算时间短，轨迹质量高。 真实世界的实验验证了它的稳健性和效率。
