MIT_papers_reading

Num	title	author	time
1	Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning	Yu Fan Chen, Miao Liu, Michael Everett, and Jonathan P. How	2017
2	Socially Aware Motion Planning with Deep Reinforcement Learning	Yu Fan Chen, Michael Everett, Miao Liuy, and Jonathan P. How	2017
3	Robot Designed for Socially Acceptable Navigation	Michael F. Everett	2017
4	Motion Planning Among Dynamic, Decision-Making Agents with Deep Reinforcement Learning	Michael Everettz, Yu Fan Cheny, and Jonathan P. How	2018
5	Safe Reinforcement Learning with Model Uncertainty Estimates	Bj¨orn L¨utjens, Michael Everett, Jonathan P. How	2019

1 - Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning

摘要

   考虑与相邻机器人交互来规划路径很消耗算力。基于新的DRL应用，本文提出分散式的多智能体免碰撞算法。考虑周围智能体的影响，构建一个值函数网络用来估计到目标的所需时间。

一、介绍

   集中式的路径规划方法应对大规模智能体时需要很多算力，无法保证实时性。本文聚焦于通信不能可靠建立（communication cannot be reliably established）的场景。现有工作分2类方法：基于反应（reaction-based）和基于轨迹（trajectory-based）。前者是采用当前几何条件下的单步交互规则，如RVO（reciprocal velocity obstacle）是调整每一个智能体的速度向量来避免碰撞。但基于反应的方法不会考虑相邻机器人未来状态而导致短视，在某些情景下产生振动和不自然的行为。
   相反，基于轨迹的方法通过预测其他机器人的运动来考虑联合体（自身+相邻机器人）的未来状态。

• 一类基于非协同的子方法是考虑其他智能体的将来动态，然后基于预测路径规划出无碰撞的路径。但在拥挤环境下的生成的预测轨迹会包含大部分不可达、不安全的空间，这样会导致freezing robot problem。
  一种解决方案是：考虑交互，智能体的轨迹会相互影响
• 另一类基于协同的子方法就是预测其他智能体的意图，规划出环境中所有相邻智能体都可行的路径。
• 基于路径协同的方法比基于反应的要好，但计算开销大，且需要能获取的准确信息。环境模型和计算的不确定性会导致对其他机器人的预测规划不准确。尤其是好几秒后的轨迹预测。所以基于轨迹的方法需要很高的频率快速更新，这又会导致巨大的计算开销。

问题和方案

   多智能体碰撞规划的主要难点在于预测联合状态（路径）的演化是可行的，但计算开销上不可行。本文方案：使用RL，把开销巨大的在线的计算降解为离线的学习过程（to offload the expensive online computation to an offline training procedure）。具体来说，通过学习一个“隐式编码协同行为”的值函数，得到一种计算高效（实时实现）的交互法则。

本文主要贡献：

1. 基于新DRL方法的双智能体碰撞规避
2. 可推广到多智能体的原理性方法（a principled way for generalizing to more (n > 2) agents）
3. 一种新的表征运动学约束的扩展公式（an extended formulation to capture kinematic constraints）
4. 仿真结果对比显示，新方法在质量上与现有的基于反应方法相比有很大提高。

二、问题描述

连续决策过程

  智能体在$t$时刻的状态和动作分别表示为$\mathbf{s_t}$, $\mathbf{a_t}$

$$\mathbf{s_t} = [\mathbf{s_t^{o}}, \mathbf{s_t^{h}}]$$

• $\mathbf{s_t^{o}}$表示被其他机器人能观测的信息，$\mathbf{s^{o}}=[p_x, p_y, v_x, v_y, r] \in \mathbb{R^{5}}$
• $\mathbf{s_t^{h}}$表示仅智能体自己知道的信息，$\mathbf{s^{h}}=[p_{gx}, p_{gy}, v_{pref}, \theta] \in \mathbb{R^{4}}$

$$\mathbf{a} = \mathbf{v}$$

• $\mathbf{v}$是2D中的速度向量
  下面仅考虑双智能体的碰撞规避问题，智能体和另一个智能体的状态分别表示为$\mathbf{s}$和$\mathbf{\widetilde{s}}$。策略为$\pi:(\mathbf{s_{0:t}}, \mathbf{\widetilde{s}_{0:t}^{o}}) \mapsto \mathbf{a_t}$。

$$\arg\min_{\pi(\mathbf{s}, \mathbf{\tilde{s^{o}}})} \mathbb{E}[t_g|\mathbf{s_{0:t}}, \mathbf{\tilde{s}},\pi,\tilde{\pi}]$$ $$s.t. ||\mathbf{P}_t - \mathbf{\widetilde{P}}_t||_2 \geq r+\widetilde{r}$$ $$\mathbf{P}_{t_g} = \mathbf{P}{_g}$$ $$\mathbf{P}_t = \mathbf{P}_{t-1}+\triangle t \cdot\pi(\mathbf{s_{0:t}}, \mathbf{\widetilde{s}_{0:t}^{o}})$$ $$\mathbf{\widetilde{P}}_{t} = \mathbf{\widetilde{P}}_{t-1} + \triangle t \cdot\widetilde{\pi}(\mathbf{s_{0:t}}, \mathbf{\widetilde{s}_{0:t}^{o}})$$

  常见假设是双方策略相同，$\pi = \widetilde{\pi}$。主要困难在于如何处理对方的未知信息$\mathbf{s}^{h}$。

基于反应

  基于反应的方法通常假设马尔科夫性，即：$\pi(\mathbf{s_{0:t}}, \mathbf{\widetilde{s}{0:t}^{o}}) = \pi(\mathbf{s_t}, \mathbf{\widetilde{s}{t}^{o}})$

  考虑免碰撞约束时只考虑一个步长的代价。虽然依靠高频计算实现对对方运动做出实时反应，但是不能预测对方的潜在意图。这种简化可以减小计算开销，但是短视容易生成不自然的轨迹。

基于轨迹

1. 从观测到的轨迹获得智能体的内在状态 $\hat{\tilde{\mathbf{s}}}{t}^{h}=f(\tilde{\mathbf{s}}^{o}{0:t})$.

2. 使用集中式的路径规划算法 $\pi(\mathbf{s_{0:t}}, \mathbf{\widetilde{s}{0:t}^{o}}) = \pi{central}(\mathbf{s}_t, \mathbf{\widetilde{s}_t^o}, \mathbf{\widetilde{s}_t^h})$。

   通过规划或预测复杂路径可以避免短视，但计算开销很大。

本文方法

1. 使用RL通过预计算值函数$V(\mathbf{s}, \mathbf{\tilde{s}^{o}})$估计到达目标的预计时间
2. 将集中式的在线计算降解成分布式的离线计算过程
3. 训练好的值函数保证单步前视操作的使用(The learned value function enables the use of a computationally efficient one-step lookahead operation)

强化学习

• 状态空间: 双智能体的联合状态 $\mathbf{s}^{jn}=[\mathbf{s}, \mathbf{\tilde{s}}^{o}] \in \mathbb{R}^{14}$
• 动作空间: 可行的速度向量 $\mathbf{a}(\mathbf{s})=\mathbf{v}$ for $\Vert\mathbf{v}\Vert_ 2 < v _{pref}$
• 报酬函数:

$$R(a)=\left\{ \begin{array}{rcl} -0.25 && {if d_{min} < 0}\\ =0.1-d_{min}/2 && {elif d_{min} < 0.2}\\ 1 && {elif \mathbf{P}=\mathbf{P}_g}\\ 0 && {o.w.} \end{array} \right.$$

• 状态转移模型：未知，依赖智能体学好的策略
• 值函数 $V^{*}(\mathbf{s}_{0}^{jn})=\sum_{t=0}^{T}\gamma^{t\cdot{v_{pref}}}R(\mathbf{s}^{jn}_t, \pi^{*}(\mathbf{s}^{jn}_t))$
• 最佳策略 $\pi^{*}(\mathbf{s}_{0}^{jn})=\arg \max_{a} R(\mathbf{s}_0,\mathbf{a})+\gamma^{\triangle t\cdot{v_{pref}}} \int_{\mathbf{s}_{1}^{jn}}P(\mathbf{s}_{0}^{jn}, \mathbf{s}_{1}^{jn}|\mathbf{a}) V^{*}(\mathbf{s}_{1}^{jn})d\mathbf{s}_{1}^{jn}$ 本文的工作选择优化$V(\mathbf{s}^{jn}, \mathbf{a})$而不是选择以前更普遍的$Q(\mathbf{s}^{jn}, \mathbf{a})$。因为以前的工作采用离散有限的动作空间，而本文采用连续的动作空间，且最佳速度向量取决于智能体的状态（最佳速度）。

三、方法

  联合状态向量$\mathbf{s}^{jn}$是连续14维空间，且大量训练时刻可以在仿真中获得。本文应用一个基于ReLU的全连接深度神经网络(DNN)参数化值函数。值函数网络$V(\cdot;\mathbf{w})$。$\mathbf{w}$-神经网络中权重

参数化

1. 为避免歧义，以当前机器人为原点，指向目标点的方向为X轴。 $s^{'} = \mathbf{rotate(\mathbf{s}^{jn})}$

$$=[d_g, v_{pref}, v^{'}_x, v^{'}_y, r, \theta^{'}, \tilde{v}^{'}_x, \tilde{v}^{'}_y, \tilde{p}^{'}_x, \tilde{p}^{'}_y, \tilde{r}, r+\tilde{r}, cos(\theta^{'}), sin(\theta^{'}), d_a]$$

• 智能体到目标的距离（欧式距离）$d_g = \Vert\mathbf{p}_g - \mathbf{p}\Vert_2$
• 和对方的距离（欧式距离） $d_a = \Vert\mathbf{p} - \tilde{\mathbf{p}}\Vert_2$
• 这种参数化的方法只在DNN中使用

用值网络生成路径

训练网络

1. 使用ORCA(optimal reciprocal collision avoidance)生成500条轨迹集，包括大约20000对状态-值。
2. 一条轨迹训练生成一个状态-值${(\mathbf{s}^{jn}, y)k}{k=1}^{N}$ 集合，$y=\gamma^{t_g\cdot v_{pref}}$， $t_g$是到达目标用时
3. 值网络用反向传播最小化二次回归误差（quadratic regression error） $\arg \min_\mathbf{w}\sum_{k=1}^{N}(y_k-V(\mathbf{s}^{jn}_{k};\mathbf{w}))^2$
   • 初试化的注意事项：
   • 训练的轨迹未必最优
   • 不是简单模拟ORCA，而是学习值函数，可用算法1生成新轨迹。
   • 训练好的值函数可能是次优 - 训练第二步通过 $\epsilon$-greedy策略 - 值网络最终用样本子集中的随机梯度下降（反向传播）来更新 - 协同也是重要的考察指标。当智能体额外的时间消耗小于或大于指标时会有惩罚，来限制激进的行为。

合并运动约束

1. 实际机器人需要考虑运动约束，已有的工作中这种约束很难编码或提高计算要求。但在RL框架内可直接引入: $\mathbf{a}(s)=[v_s, \phi] \ \ for\ \ v_s<v_{pref},\ \left|\phi-\theta\right|<\pi/6, \ \left|\theta_{t+1}-\theta_t\right|<\triangle t \cdot v_{pref}$
2. 机器人可以选择在指向目标时全速前进，也可以选择先旋转直到指向目标点。CADRL学会了如何平衡这2种选择并最小化移动时间。

多智能体碰撞规避

结果

计算复杂性

1. 3个隐藏层（150，100，100）。
2. CPU-i7-5820K

   穿梭场景表现对比

2 - Socially Aware Motion Planning with Deep Reinforcement Learning

摘要

   机器人在人群环境中安全、高效的导航，很重要的一点是建模人类行为和导航规则。现有工作是使用特征匹配技术来描述和模仿人类路径，但无法处理复杂信息。

介绍

1. 行人遵循潜在的社会规范，意图难以识别。
   • 常见方法将行人视为动态障碍物，使用特定的反应规则来避免碰撞。但不能理解人类行为，有时会产生不安全、不自然的行为。尤其移速与行人相近时。
   • 改进做法：推理附件行人的意图，并生成预测轨迹，再用传统路径规划算法生成无碰撞的路径。但将预测和规划分离的做法会导致freezing robot problem。
   • 考虑协同（account for cooperation），建模并预测附件行人对机器人运动的影响。
2. 基于协同、遵从社会的导航工作大致分为2类：
   • 基于模型（model-based）：加入参数化的社会性交互影响，扩展多智能体免碰撞算法。这类方法通常基于直观的几何关系设计成计算高效的，但不清楚人是否遵循精确的几何规则，因人而异。且会导致振荡路径。
   • 基于学习（learning-based）：
     • 从人的演示中用逆向强化学习（IRL）学习代价函数和概率分布
     • 可以学得更人性化的路径，但计算消耗大。因为计算\匹配轨迹特征通常需要预测周围行人的联合路径，其中就包括观测不到的信息。
     • 人类行为的随机性，导致在行人特征统计中不同人的路径特征差异很大。甚至同一场景下也是如此。
   • 现有工作关注建模和重现社会约束的细节机制。因为人类行为的随机性很难评估。但人类天生具有在遵循社会约束下省时的导航能力。

背景

社会规范特征

1. 相比于直接量化人类行为，复杂的规范运动模式可以是简单局部交互的结果
2. 社会规范是基于省时、相互碰撞规避机制下的一类紧急行为
3. 相互性可以显式的编码其他智能体的行为，导航规则不唯一，左手-右手法则均可。
4. CADRL不可控-依赖于值网络的初始值和随机生成的测试样本集

方法

1. 基于DRL的具有社会意识的多智能体碰撞规避方法
2. 给不符合规范的行为更多惩罚，使用考虑了社会规范的奖励函数

---

• Previous
  EKF_Code_Reading