Trajectory planning for multi-robot systems: Methods and applications 综述阅读笔记_sampling based method

1.Introduction

本文中Multi-Robot System (MRS) 并不局限于机器人，指代的是UAV和UGV
要求：安全到达指定地点，尽量选择短距离、短时间

介绍了无人机和自动驾驶：

1. UAV：3D path planning，要调整飞行高度，需要考虑天气大风等影响因素
2. UGV：2D，有一定局限性，因为不能像无人机一样跨过障碍；自主性更强，可以到达较远的地点

2.Multi-robots systems

1. 定义：Multi-Robot Systems includes all those groups formed by two or more robots sharing the same work space. （机械臂、无人机、自动驾驶汽车等）
2. 相关术语：
   ① Multi-Robot Systems：包含多个机器人的系统，很广的概念
   ② Multi-Agent System：多个能够相互交互的智能agent组成的系统，不仅仅属于机器人领域，生物学、心理学等领域也适用
   ③ Robotic Swarms：一般与可伸缩性，机器人间的通信有关
   ④ Sensor Networks：传感器网络
3. 控制和决策结构：
   ① Centralized Architecture 中心化结构，拥有一个通信中心，通信会受到距离影响/通讯设备，一旦中心被破坏，就糟糕了
   ②Decentralized Architecture 非中心化结构，分为 分布式架构 or 层次架构
4. homogeneous MRS 指所有机器人都一样， heterogeneous MRS 指有不同的机器人
   
5. agent间的关系：
   ① Indifference：各自是独立的
   ② Cooperation：有一个共同任务
   ③ Competition or antagonism：竞争关系

3.Path Planning

（综述的名字明明是trajectory planning，但是文中全在讲path planning）

1. 常用术语：
   ① Path-planning：找到一条连续的路 in C-space（free space & obstacle space），可能不是平滑的；侧重于提供解方案（找到就行，不要求最优） feasibility，Optimality
   ② Optimal Path Planning：有cost function，需要优化代价函数
   ③ Trajectory Planning：考虑到了车辆的动态特性，速度、加速度
   

3.1. Decomposition graph-based methods

将环境分解为多个网格，获取环境表示，需要识别哪些地方是起始点、障碍。相当于一张无向图啦
那么，问题就变成 找到一条从初始节点到终止节点的路径

3.1.1. Dijkstra algorithm

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

3.1.2. A* algorithm

A star 启发式算法，在广度优先的基础上加入了估价函数
考虑到了离目的地的距离，因此速度会快很多

1. 计算节点优先级的函数：$f(n)=g(n)+h(n)$；去掉$h(n)$则退化成Dijkstra算法
2. $g(n)$是节点n距离起点的代价，$h(n)$是节点n距离终点的代价（启发函数）
3. $h(n)$其实只是个猜测，因为只有我们真正经过了才会知道真正的距离（中间有障碍）；常用的启发函数：曼哈顿距离（只允许上下左右移动）、对角距离（允许朝八个方向移动）、欧几里得距离（允许朝任何方向移动）

路径规划之 A* 算法 - 阿里云云栖号的文章 - 知乎

3.1.3. D* algorithm

Dynamic A star；和A*类似，但是考虑的是动态最短路径

1. 检测动态障碍，也用到了启发式函数
2. 同A* 算法类似，D-star通过一个**维护一个优先队列（OpenList）**来对场景中的路径节点进行搜索，所不同的是，D*不是由起始点开始搜索，而是以目标点为起始（反向搜索），通过将目标点置于Openlist中来开始搜索，直到机器人当前位置节点由队列中出队为止（当然如果中间某节点状态有动态改变，需要重新寻路，所以才是一个动态寻路算法）。

3.2 Sampling based methods

基于环境的随机映射，抽样是以节点或者cell进行
就是一直不停采样，不停扩展
分类：① active method：选择最优路径 ② passive method：生成路网即可

3.2.1. Probabilistic Road Map (Passive)

路径规划: PRM 路径规划算法 (Probabilistic Roadmaps 随机路标图)

1. 随机撒点，有障碍的地方去除
2. 将最近的k个点连起来，如果中间有障碍物，不能连接；得到似然概率路线图
3. 使用A*算法进行搜索

优点：能够以较低的计算成本探索三维空间

3.2.2. Voronoi diagram (Passive)

1. Voronoi diagram解决的问题实际上就是基于一组特定点将平面分割成不同区域，而每一区域又仅包含唯一的特定点，并且该区域内任意位置到该特定点的距离比到其它的特定点都要更近。
2. 个人理解：有一批定点，我们使用一个区域包裹每个定点，该区域里的任意点距离定点的距离 都小于 该任意点距离其他区域里的定点。
   

3.2.3. Rapidly exploring random trees (Active)

RPT通过在状态空间内随机撒点，控制路径树的生长点和生长方向：

1. 分为free space和obstacle space，设定start node和end node
2. 初始化一个random node，必须能与start node连接起来，查看end node是否能与其连接，有的话就结束
3. 没有的话，就再次生成随机点，要求能和end节点连接

特点：

1. 比RMP更有方向性
2. 非最优解
3. 效率低
4. 在整个空间中采样

3.2.4. Artificial potential field methods (Active)

人工势场法：将目标和障碍物对机器人运动的影响具体化成人造势场。目标处势能低，障碍物处势能高。

计算复杂度低，但是并不能保证成功，也不知道何时能成功。

3.3. Mathematics model based methods

基于数学模型的方法，建立动力学和动态约束，用于建模环境和系统。
代价函数进行约束。（这部分网上能搜到的信息并不多）

3.3.1. Mixed integer linear program

混合整数线性规划(MILP)模型：基于cost函数，考虑了 运动动力学约束、最小距离、能量或环境中的威胁。

3.3.2. Mixed integer quadratic program

与MILP类似，但是需要执行目标二次函数的解析

3.3.3. Optimal control

最优控制，从一组微分方程找到state和path。

3.4. Bio-inspired methods

模拟生物学行为， not being fully deterministic, presenting parallel structures, and being adaptive

3.4.1. Neuronal network

文中给出的related work：

1. CNN分析环境，DQN生成action；
2. 利用MADDPG；
3. WoLFPHC (Win or Learn Fast Policy Hill-Climbing)：解决了学习速度慢、在未知环境难以学习等问题；每个智能体只用保存自己的动作来完成学习任务。
   WolF是指，当智能体做的比期望值好的时候小心缓慢的调整参数，当智能体做的比期望值差的时候，加快步伐调整参数。
   PHC是一种单智能体在稳定环境下的一种学习算法。该算法的核心就是通常强化学习的思想，增大能够得到最大累积期望的动作的选取概率。该算法具有合理性，能够收敛到最优策略。其算法流程如下
4. multi-layer architecture：Q-learning 决定车辆的配置，PG保证不碰撞

3.4.2. Evolutionary algorithms

基于随机搜索，如蚁群算法、遗传算法等等

Table

常用的规划算法代码以及动画演示
【总结整理】【路径规划】- 浅谈路径规划算法
基于强化学习的路径规划学习
增强学习做路径规划的优势？
Multi-agent pathfinding 传统方法和强化学习结合的多智能体路径规划
【论文笔记】AAAI2022多智能体强化学习论文五篇
机器人协同路径规划的github项目