Flexible Informed Trees (FIT*): Adaptive Batch-Size Approach in Informed Sampling-Based Path Planning

📄 arXiv: 2310.12828v2 📥 PDF

作者: Liding Zhang, Zhenshan Bing, Kejia Chen, Lingyun Chen, Kuanqi Cai, Yu Zhang, Fan Wu, Peter Krumbholz, Zhilin Yuan, Sami Haddadin, Alois Knoll

分类: cs.RO

发布日期: 2023-10-19 (更新: 2024-03-02)

备注: 7 pages,7 figures

期刊: 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

DOI: 10.1109/IROS58592.2024.10802466

💡 一句话要点

提出FIT*以解决路径规划中的批量大小适应性问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 路径规划 自适应批量大小 采样方法 移动机器人 优化算法

📋 核心要点

  1. 现有的基于采样的路径规划方法如批量信息树（BIT*）在初始路径寻找和任务分配上存在效率不足的问题。
  2. 本文提出FIT*，通过自适应批量大小的方法，动态调整批量大小以提高路径收敛速度，适应不同的配置空间。
  3. FIT*在R^2到R^8的测试中表现优异，相比现有方法在解决方案的成功率和初始成本上均有显著提升。

📝 摘要（中文）

在路径规划中，任何时候几乎肯定是渐近最优的规划器在基于采样的规划器基准中占据主导地位。本文提出了灵活信息树（FIT），这是一种基于采样的规划器，集成了自适应批量大小的方法，以提高初始路径收敛率。FIT根据配置空间的固有维度和n维超椭球的超体积动态调整批量大小，通过稠密和稀疏采样策略，FIT*在找到成功解决方案的同时，以更低的初始解决成本提高了收敛率。该方法在优化阶段增加了批量顶点的采样频率，并在R^2到R^8的测试问题上超越了现有的单查询基于采样的规划器，并在实际的移动操作任务中得到了验证。

🔬 方法详解

问题定义：本文旨在解决现有基于采样的路径规划方法在初始路径寻找和批量大小固定带来的效率低下问题。现有方法如BIT*在处理复杂环境时，无法灵活调整批量大小，导致收敛速度慢。

核心思路：FIT*的核心思路是引入自适应批量大小，根据配置空间的维度和超椭球的超体积动态调整批量大小，以提高路径收敛率和优化性能。这样的设计使得规划器能够更有效地在狭窄空间中进行路径搜索。

技术框架：FIT*的整体架构包括两个主要阶段：初始路径寻找阶段和优化阶段。在初始阶段，采用稠密采样策略以快速找到可行路径；在优化阶段，利用稀疏采样策略提高批量顶点的采样频率，进一步优化路径。

关键创新：FIT的主要创新在于其自适应批量大小的机制，这与现有方法的固定批量大小形成鲜明对比。通过动态调整，FIT能够在不同的环境条件下保持高效的路径规划能力。

关键设计：FIT*在设计中考虑了配置空间的维度和超椭球的超体积，设置了相应的参数以实现批量大小的动态调整。此外，采用了稠密与稀疏采样策略的结合，以优化路径搜索的效率和成功率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

FIT*在R^2到R^8的测试中表现出色，相比于现有的单查询基于采样的规划器，成功率显著提高，初始解决成本降低，收敛速度加快，展示了其在实际应用中的优越性。

🎯 应用场景

FIT在移动机器人、无人驾驶汽车及其他需要实时路径规划的领域具有广泛的应用潜力。其自适应批量大小的机制能够有效应对复杂环境中的路径规划挑战，提高任务执行的效率和安全性。未来，FIT有望在更复杂的动态环境中得到进一步应用和发展。

📄 摘要（原文）

In path planning, anytime almost-surely asymptotically optimal planners dominate the benchmark of sampling-based planners. A notable example is Batch Informed Trees (BIT), where planners iteratively determine paths to batches of vertices within the exploration area. However, utilizing a consistent batch size is inefficient for initial pathfinding and optimal performance, it relies on effective task allocation. This paper introduces Flexible Informed Trees (FIT), a sampling-based planner that integrates an adaptive batch-size method to enhance the initial path convergence rate. FIT employs a flexible approach in adjusting batch sizes dynamically based on the inherent dimension of the configuration spaces and the hypervolume of the n-dimensional hyperellipsoid. By applying dense and sparse sampling strategy, FIT improves convergence rate while finding successful solutions faster with lower initial solution cost. This method enhances the planner's ability to handle confined, narrow spaces in the initial finding phase and increases batch vertices sampling frequency in the optimization phase. FIT* outperforms existing single-query, sampling-based planners on the tested problems in R^2 to R^8, and was demonstrated on a real-world mobile manipulation task.