论文1：Autonomous On-Demand Free Flight Operations in Urban Air Mobility using Monte Carlo Tree Search
摘要：
- 为保证VTOL飞机安全高效地自主飞行，设计了一种避免碰撞的计算指导算法
- 将这个问题建模为马尔可夫决策过程，使用蒙特卡罗树搜索的在线算法来解决
- 基于数值实验来测试算法性能，结果表明可以使飞机快速到达目的地，避免与其他飞机的冲突
前人研究：
避碰算法：基于规则、基于优化、遗传算法、力场技术 → 混合整数规划（对小网络较为合适，不适用于随机动态模型）→ 基于马尔可夫决策过程的方法（这些方法需要离散状态空间，可能会丢失信息）→ 在线蒙特卡罗树搜索算法（不需要对状态空间进行离散化，但对计算资源要求较高）
理论基础：
-
马尔可夫决策过程 MDP
- 蒙特卡洛树搜索算法 MCTS
用于解决顺序决策问题的在线启发式搜索算法，通过在决策空间中随机抽取样本，并根据结果构建搜索树来判断动作的值，以UCB for Tree(UCT)为例，计算过程如下：
-
选择selection：选择UCT值最大的子节点，UCT值计算公式中，第一项由总奖励除以被访问次数得到，第二项中C为常数，n为被探索
- 扩展node expansion：创建一个或者多个子节点
- 仿真simulation：在某一结点用随机策略进行游戏，又称playout或者rollout
-
反向传播back propagation：使用随机搜索的结果来更新整个结果树
问题定义：
问题假设：
- 所有飞机只能以固定的速度直线飞行，只有一架飞机使用MCTS算法飞向目的地
- 所有飞机在相同高度飞行
- 不考虑入侵飞机之间的碰撞
状态空间：包括所有飞机(1个本飞机，n个入侵飞机)各自的位置(x, y)和速度(v_x, v_y)，以及本飞机的航向角和目的地。所以一共是4×n+4×1+2=4n+7个数字，状态空间则有4n+7个维度
最终状态：发生碰撞（做出行动后，下一秒两飞机距离小于r_min）、冲出地图和达到目的地
动作空间：{左转2°，右转2°，直行}
奖励函数：包含两个目标，第一是短时间内将飞机引导到目的地，第二是避免被控制的飞机和其他飞机之间的碰撞。奖励函数设定为飞机无碰撞达到终点时R(s)=1，加上折扣系数小于1，可以保证较快达到终点
算法训练过程
参数设置：
- 仿真次数n
- 固定深度d（树结构到达该深度则停止，计算最终飞机位置与目的地的距离来确定结果好坏）
训练过程
-
随机生成根节点状态v_0，s_0，在规定时间内进行扩展，仿真和反向传播，最后选择UCT值最大的子节点，继续循环
论文2：Multi-Agent Autonomous On-Demand Free Flight Operations in Urban Air Mobility
摘要：
- 提出了一种多协作飞机集中计算指引算法，通过生成所有飞机的实时动作来引导所有飞机到达各自的目的地，同时避免了飞机之间潜在的冲突
- 将这个问题建模为马尔可夫决策过程，使用蒙特卡罗树搜索的在线算法来管理多架合作飞机
- 创建了空域模拟器来测试该算法性能，结果表明该算法可以帮助所有飞机到达目的地，而在飞行过程中冲突率仅为0.2%
- 相比于上一篇论文，本文的改进之处：上一篇论文只能控制一架飞机来避免与其他入侵者飞机的冲突，本文可以通过让当前在空域飞行的多架飞机相互通信，来帮助它们以合作的方式采取行动
前人研究：
- 集中式/分散式：由一个中央控制器(集中式)解决，还是每架飞机单独(分散式)解决
- 计划/反应：计划式提前生成可行路径，而反应式通常使用在线避碰系统来应对危险情况
- 合作/不合作:飞机之间或飞机与中央控制器之间是否存在在线通信。
集中式方法：中央控制器在飞行前为所有飞机单独设计整体轨迹，可以表述成最优控制问题，解决方法包括半定规划、非线性规划、混合整数线性规划、混合整数二次规划、序列凸规划、二阶锥规划、进化技术等。此外，visibility图和Voronoi图等路线图方法也可以处理飞机的路径规划问题。当状态空间变大或高维时，精确解的计算将变得不切实际，因此提出了基于样本的规划算法，如概率路线图、RRT、RRT等。这些集中式方法通常追求全局最优解。然而随着飞机数量的增加，这些方法的计算时间通常呈指数增长。此外，随着环境中的新信息的更新(例如，一架新飞机进入空域)，这些集中规划方法通常需要重新运行
分散式方法：所有的冲突由每架飞机单独解决，可以是合作的，也可以是非合作的。在agent数量方面具有更好的扩展性，也更健壮，因为它们不存在单点故障
在非通信模式下的避碰算法：蒙特卡罗树搜索→基于几何的方法 DAIDALUS (Detect and Avoid Alerting Logic for Unmanned Systems)
理论基础：
Multi-Agent Systems
多智能体系统是一组自主的、相互作用的实体，它们共享一个共同的环境，通过传感器进行感知，并在此基础上与执行器进行决策和行动
多智能体系统的两个难点
- 维数灾难
- 非平稳性（Nonstationarity）：最佳策略会随着其他飞机的变化而变化
问题定义：
单机视角下与上文相同，让所有的飞机一个接一个地进行决策
当一架飞机选择了行动后，它将把这个信息广播给所有其他飞机，然后飞机做出决定可以利用这个信息来选择更好的行动
