提出高效可见性感知的离线轨迹规划算法，显著提升目标追踪规划速度与成功率。
Track A*: Fast Visibility-Aware Trajectory Planning for Active Target Tracking
- 基于分层有向无环图与束剪枝搜索，在四维时空网格上规划轨迹。
- 在8个CARLA地图上1000场景测试中全部收敛，平均耗时仅45秒，提速23倍。
- 适合需要重复可测的离线追踪数据集构建与规划器基准测试场景。
主动目标追踪所需的离线参考轨迹，既用于构建多模式追踪数据集，也用于在可重复条件下评估在线规划器。本文提出Track A*（TA star），一种基于离散四维时空网格（x, y, z, t）的可见性感知轨迹规划算法。TA star结合分层有向无环图（DAG）搜索与三项工程优化：跨时间障碍物距离缓存（基于包围体层次结构BVH）、逐层束剪枝及可配置多射线可见性评估器。该方法在离散图上采用束剪枝启发式搜索，高效生成高质量追踪轨迹。虽牺牲严格理论最优性以换取实际可扩展性，但实验表明其在计算成本极低的情况下仍保持接近基线的可见性表现。在8个CARLA优化地图上进行1000场景压力测试，所有场景均成功收敛，使用32个工作进程总耗时45秒；在248场景控制对比中，相较于未优化的优先队列A*基线（BinaryHeap实现），在相同输入与5×10⁶扩展上限下，平均规划时间减少23.0倍，最坏情况减少11.8倍，收敛率从56.9%提升至100%。在n=141的基线收敛子集上，平均可见性仅下降-0.15个百分点，无任一场景下降超过5个百分点。本文将TA star定位为特定条件下的实用离线参考规划器，同时讨论了如Town07密集植被环境中的局限性与失败案例。
原文摘要 · Abstract (English)
Offline reference trajectories for active target tracking are needed both for building multi-modal tracking datasets and for benchmarking online tracking planners under repeatable conditions. We present Track A star (TA star), an offline search-based trajectory planner that targets the visibility-aware target tracking objective on a discretized four-dimensional spatio-temporal grid (x, y, z, t). TA star combines a layered Directed Acyclic Graph (DAG) search with three engineering optimizations: cross-time obstacle distance caching against a Bounding Volume Hierarchy (BVH), per-layer beam pruning, and a configurable multi-ray visibility evaluator. TA star employs a beam-pruned heuristic search on this discrete graph to efficiently find high-quality tracking trajectories. While it trades strict theoretical optimality for practical scalability, our empirical results demonstrate robust, near-baseline visibility performance at a fraction of the computational cost. On a 1000-scenario stress test across eight CARLA Optimized maps, TA star converges on all scenarios and completes in 45 s using 32 workers; on a 248-scenario controlled comparison against an unoptimized priority-queue A star baseline (BinaryHeap implementation) under identical scenario inputs and a 5 x 10^6 expansion cap, TA star reduces mean planning time by 23.0x and worst-case planning time by 11.8x, while raising convergence from 56.9% to 100%. On the n=141 baseline-converged subset, TA star changes average visibility by only -0.15 percentage points (pp), with no scenario exceeding a 5 pp drop. We position TA star as a practical offline reference planner under these specific conditions, with limitations and failure cases discussed for environments such as Town07 dense vegetation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。