Sampling-Based Path Planning in Highly Dynamic and Crowded Pedestrian Flow

Cai K, Chen W, Dugas D, et al. Sampling-Based Path Planning in Highly Dynamic and Crowded Pedestrian Flow[J]. IEEE Transactions on Intelligent Transportation Systems, 2023. 慕尼黑工大 PDF

1. 摘要

在行人环境中，自由空间是有限的并且时刻保持变化，传统的规划算法很难找到无碰撞的路径

思想： 与传统方法相比，该方法旨在根据不同类型的行人流生成最优策略。如果有同向行人流，则规划出一条前往同向流的路径；如果没有同向行人流，则贴着障碍走，例如墙壁。避免对行人迎面而来，实现了对行人的最小侵入和速度差异最小两个原则。

创新点：

提出了一种基于流量图的模型，其中包括速度层和最小侵入层，用于对行人移动方向和非侵入区域进行建模
- 速度层：至少存在与机器人方向相同的行人流，定义为正方向。为机器人提供有关行人流沿同一方向移动的区域的信息。
- 最小侵入层：行人流方向全部与机器人方向相反。定义为负方向。呈现墙壁和其他障碍物的边界。这些区域对行人有排斥力，在这个区域运动，机器人只需要注意一侧的行人。
引入了基于 RRT 的路径规划器，该路径规划器结合了流量图模型 (FM-RRT*)，并结合了偏置采样，以引导机器人走向侵入最小或行人流速度差异较小的区域。

2. 方法

2.1 架构

全局规划：
- 实现了方向判断模块，判断机器人方向与行人流方向的异同
- 根据方向异同建立流图模型的速度层或最小侵入层。
- 引入了基于RRT*的轨迹生成模块，包含生成步骤、优化步骤、B样条步骤和过滤步骤。
局部规划：
- 当机器人沿着全局路径移动时，实现了局部规划器来躲避动态行人

2.2 流图模型构建

判断方向：定义行人方向向量和机器人方向向量，通过向量的乘积判断是否同向
速度层构建：
- 速度层的目的利用行人速度来推断行人流对地图上未占用区域的影响，从而引导机器人向速度相近的区域导航。构建一个概率密度，与行人的速度向量相乘，计算未占用区域的对应速度，并定义函数进行更新： $V^i(q)=\vec{v^i}N(q|μ^i,\sum^i)$
- 由于环境中行人的密度很高，因此可以为一个未占用区域分配不同的速度。因此，定义函数来更新不同行人的速度重叠情况： $V(q)=max(||V^i(q)||)·\vec {n^i}$
最小侵入层构建：
- 最小侵入层的目的是引导机器人沿着障碍物进行导航，以减少对行人空间的侵入。
- 将不同的障碍物根据其连续性进行聚类，并根据不同的聚类创建不同的层。

2.3 轨迹生成模块

轨迹生成：在流图中根据RRT采样得到初步的全局路径
偏置采样：在生成初步全局路径的基础上，在与行人相同的方向上或在最小侵入层中进行采样，找到距离机器人最近且行人最少的层
寻找最优路径：定义两个代价函数进行求解，分别对应速度层和最小侵入层
- 速度层：寻找速度与机器人的偏差最小的最佳采样点，避免机器人在速度层相对于行人运动过快或过慢所带来的影响。
- 最小侵入层：定义了碰撞层的排斥力和行人的社会力，寻找能够平衡最小侵入和碰撞避免的采样点

3. 实验

3.1 评估实验

评估速度层和最小侵入层的效果

使用RVO和baseline方法结合速度层和最小侵入层进行实验

结合速度层和最小侵入层的RVO算法比单纯的RVO算法具有更快的平均速度、更短的时间和更短的轨迹长度；且碰撞次数减少。

在单纯导航效率上，纯baseline要更好，但结合该论文的方法后，能够以更快的速度移动，并且碰撞次数减少，具有更高的安全性。

3.2 对比实验

对比方法：RVO，DWA，Baseline

结合该论文提出的路径规划器FM-RRT*之后，Baseline和RVO都拥有了更高的性能和安全性

目录