提出两种新算法，加速机器人避障多面体构建，提升运动规划效率。
Faster Algorithms for Growing Collision-Free Convex Polytopes in Robot Configuration Space
- 利用采样快速定位障碍物，优化非线性规划或直接并行搜索
- IRIS-ZO比IRIS-NP快一个数量级，且可控制碰撞概率上限
- 适合复杂环境下的机器人路径规划研究者使用
本文提出两种新算法，用于在机器人配置空间中构建凸的无碰撞多面体。这类多面体是实现更强运动规划框架（如基于图的凸集轨迹优化）的关键，但当前构建过程仍是主要瓶颈。本文基于IRIS-NP（通过半定与非线性规划迭代膨胀区域）改进其可调性、运行时间及复杂环境扩展能力。核心思想是：通过采样低成本获取邻近障碍物信息，显著加速区域生成。提出两个算法：一是更高效地使用非线性规划（IRIS-NP2），二是采用大规模并行零阶优化策略绕过非线性规划（IRIS-ZO）。同时提出一种终止条件，可控制用户指定的允许碰撞比例，解决原方法调参困难问题。在八个机器人环境中对比测试，结果显示IRIS-ZO相比IRIS-NP提速一个数量级；IRIS-NP2也显著更快，且用更少超平面构建更大多面体，加速下游计算。
原文摘要 · Abstract (English)
We propose two novel algorithms for constructing convex collision-free polytopes in robot configuration space. Finding these polytopes enables the application of stronger motion-planning frameworks such as trajectory optimization with Graphs of Convex Sets [1] and is currently a major roadblock in the adoption of these approaches. In this paper, we build upon IRIS-NP (Iterative Regional Inflation by Semidefinite & Nonlinear Programming) [2] to significantly improve tunability, runtimes, and scaling to complex environments. IRIS-NP uses nonlinear programming paired with uniform random initialization to find configurations on the boundary of the free configuration space. Our key insight is that finding near-by configuration-space obstacles using sampling is inexpensive and greatly accelerates region generation. We propose two algorithms using such samples to either employ nonlinear programming more efficiently (IRIS-NP2 ) or circumvent it altogether using a massively-parallel zero-order optimization strategy (IRIS-ZO). We also propose a termination condition that controls the probability of exceeding a user-specified permissible fraction-in-collision, eliminating a significant source of tuning difficulty in IRIS-NP. We compare performance across eight robot environments, showing that IRIS-ZO achieves an order-of-magnitude speed advantage over IRIS-NP. IRISNP2, also significantly faster than IRIS-NP, builds larger polytopes using fewer hyperplanes, enabling faster downstream computation. Website: https://sites.google.com/view/fastiris
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。