提出首个完整且有界次优的3D移动目标路径规划算法
A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D
- 高层搜索求解带时间窗的广义旅行商问题，确定访问顺序
- 低层用FMC*算法在凸集图中寻找最短路径，支持动态目标
- 适用于无人机等需拦截多移动目标的场景，性能优于基线
移动目标旅行商问题带障碍物（MT-TSP-O）要求为一个代理规划一条无碰撞轨迹，使其在指定时间窗口内依次拦截一组移动目标，并返回起始位置。每个目标以恒定速度在时间窗口内运动，代理速度不低于任一目标速度。本文提出FMC*-TSP，首个针对配置空间为ℝ³的完整且有界次优算法。该算法融合高层与低层搜索：高层求解广义旅行商问题带时间窗（GTSP-TW），确定目标访问序列与时间窗；低层则通过新算法FMC*，在凸集图（GCS）上利用隐式图搜索与专为动态目标设计的剪枝技术，求解代理轨迹。我们在含最多40个目标的280个实例上测试，结果表明其平均运行时间低于基于先前工作的基线方法。
原文摘要 · Abstract (English)
The moving target traveling salesman problem with obstacles (MT-TSP-O) seeks an obstacle-free trajectory for an agent that intercepts a given set of moving targets, each within specified time windows, and returns to the agent's starting position. Each target moves with a constant velocity within its time windows, and the agent has a speed limit no smaller than any target's speed. We present FMC*-TSP, the first complete and bounded-suboptimal algorithm for the MT-TSP-O, and results for an agent whose configuration space is $\mathbb{R}^3$. Our algorithm interleaves a high-level search and a low-level search, where the high-level search solves a generalized traveling salesman problem with time windows (GTSP-TW) to find a sequence of targets and corresponding time windows for the agent to visit. Given such a sequence, the low-level search then finds an associated agent trajectory. To solve the low-level planning problem, we develop a new algorithm called FMC*, which finds a shortest path on a graph of convex sets (GCS) via implicit graph search and pruning techniques specialized for problems with moving targets. We test FMC*-TSP on 280 problem instances with up to 40 targets and demonstrate its smaller median runtime than a baseline based on prior work.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。