Time Optimal Ergodic Search
作者: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023
许可协议
- 开放获取
- 论文: CC BY 4.0
以下内容均依据论文全文，按其 CC BY 4.0 许可协议使用；其中的图已注明作者。
一句话总结
在遍历度量的上界 γ 约束下最小化搜索时间：一个参数决定覆盖的彻底程度，由优化器选择轨迹时长。
为何重要
对于搜索与救援或勘测飞行，操作员可以指定一次扫掠必须达到的彻底程度，并得到满足该要求的最快轨迹，而不必猜测时长。速度限制和障碍物屏障等约束位于同一个优化问题中，规划的时间迁移到真实四旋翼上时误差在 1.5 s 以内。
问题
遍历搜索规划连续轨迹，使其在每个区域停留的时间与该区域的信息量成正比，但现有方法会预先固定规划时域，因此用户无法在搜索彻底程度与时间之间进行权衡。在最小化遍历度量的同时最小化时间是一个不适定问题，因为轨迹只有在时间趋于无穷时才会完全遍历。
提出的方法
遍历度量成为最短时间问题中的不等式约束 E ≤ γ，因此 γ 决定覆盖需要多粗或多细，而终止时间 tf 是一个决策变量。作者利用“扩展遍历状态”，通过庞特里亚金极大值原理证明了局部最优性条件，然后在实践中通过在 N 个节点上的直接转录（Δt = tf/N），并配合定制的增广拉格朗日求解器来求解该问题。障碍物通过离散控制屏障函数约束来处理。
关键见解
- 把遍历性当作上界而不是目标，使最短时间搜索成为适定问题；当 γ → 0 时，最优时间无限增长，与遍历理论一致
- 在一个有四个峰的信息图上，把 γ 降低两个数量级（从 0.1 到 0.001），最优时间大约翻倍（从 9.86 s 到 19.59 s），而即便是粗略的规划也仍然访问了每个峰
- 按时间归一化的控制量在 γ 范围的中段较高，此时轨迹必须在覆盖与时间之间权衡，高于两端的情形
- 平滑的初始猜测（线性插值）给出一致的解；含噪声或随机的初始轨迹会落入遍历程度相同但时间更长的局部极小值
主要结果
- 使用 2 维质点进行均匀覆盖：改变 γ 可得到 5–10 s 的轨迹，其覆盖效果相当于固定时域的 10 s 遍历轨迹（E = 0.007）
- 非均匀信息图：γ = 0.1 时最优时间为 9.86 s，γ = 0.001 时为 19.59 s
- γ = 0.05 时的敏感性：将初始 tf 从 4 s 变到 8 s，最优时间为 4.97 ± 0.23 s；将节点数 N 从 50 变到 600，最优时间为 5.45 ± 0.39 s
- 使用控制屏障函数的杂乱 2 维环境：最优时间从 γ = 0.2 时的 7.79 s 到 γ = 0.002 时的 11.85 s，屏障约束使轨迹远离每一个障碍物
- γ = 0.1、0.05 和 0.01 时的无人机实验：实际飞行时间与优化时间的差距在 1.5 s 以内；图 1 中的轨迹在 13.5 s 内覆盖了杂乱区域
- 求解器还为处于随机椭球障碍物之间的非线性 3 维飞行器模型生成了均匀覆盖轨迹
局限
- 作者表示，由于遍历度量高度非线性且非凸，所得的解只是局部最优
- 作者发现庞特里亚金最优性条件在长时域下数值不稳定，因此实际使用的求解器是一种直接转录方法
- 规划是离线进行的，障碍物已知；作者将存在未知障碍物和环境不确定性时的实时规划列为未来工作
- 结果取决于初始轨迹和 N；当 γ 非常小时，所需时间变得非常大，求解器不再返回解
- 作者指出计算成本随探索空间的维度增长
对领域的影响
荣获 RSS 2023 最佳论文奖。作者在 github.com/ialab-yale/time_optimal_ergodic_search 发布了代码，并提供了一个多媒体演示页面。
摘要
能够在时间与搜索彻底程度之间取得平衡的机器人，有望在搜索与救援等应用中提供时间紧迫的援助。基于遍历覆盖的搜索方法的最新进展，已使机器人能够在固定的时间内完整地探索和搜索一个区域。然而，在时间与自主遍历搜索质量之间进行优化尚未得到展示。在本文中，我们研究时间最优遍历搜索问题的解，以实现快速、自适应的机器人搜索与探索。我们将该问题表述为一个带遍历不等式约束的最短时间问题，其上界调节并平衡搜索的粒度与时间。我们利用庞特里亚金（Pontryagin）最优性条件解析地给出了该问题的解，并通过直接转录优化方法进行了数值演示。我们在仿真中以及在杂乱环境中的无人机实验中，展示了该方法生成时间最优遍历搜索轨迹的有效性。结果表明，避障可以很容易地整合进我们的表述中，我们还进行了消融研究，考察参数对优化时间的依赖关系以及搜索的轨迹敏感性。
链接
- arXiv 2305.11643: https://arxiv.org/abs/2305.11643
- PDF: https://arxiv.org/pdf/2305.11643v1
- 代码: https://github.com/ialab-yale/time_optimal_ergodic_search
- 项目主页: https://sites.google.com/view/time-optimal-ergodic-search