Track A*: Fast Visibility-Aware Trajectory Planning for Active Target Tracking
Pith reviewed 2026-05-08 16:19 UTC · model grok-4.3
The pith
Track A* finds high-quality visibility-aware target tracking trajectories over 20 times faster than standard A* while nearly preserving visibility scores.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
TA star performs beam-pruned heuristic search over a layered directed acyclic graph that encodes a discretized 4D spatio-temporal state space. Three engineering additions—bounding-volume-hierarchy caching of obstacle distances, per-layer beam pruning, and a tunable multi-ray visibility evaluator—allow the planner to produce trajectories whose average visibility differs from an unoptimized A* baseline by only -0.15 percentage points on the 141 scenarios both methods solve, while reducing mean planning time by a factor of 23.0 and worst-case time by 11.8 and raising convergence from 56.9 % to 100 % across 248 controlled trials.
What carries the argument
Beam-pruned A* search on a layered DAG with BVH distance caching and configurable multi-ray visibility evaluation.
If this is right
- Enables routine generation of large multi-modal tracking datasets from offline computation.
- Supplies repeatable, high-convergence reference trajectories for benchmarking online planners.
- Scales to 1000 scenarios across eight CARLA maps in under a minute of wall-clock time with modest parallelism.
- Maintains visibility within 5 pp of baseline on every overlapping case while trading away strict optimality.
- Reveals concrete failure modes in dense vegetation environments such as Town07.
Where Pith is reading between the lines
- The same caching and pruning pattern could be reused for other 4D visibility or line-of-sight planning tasks.
- Dynamic adjustment of beam width during search might further reduce runtime on easier scenarios.
- Transfer to physical robots would require checking that discrete-grid visibility predictions match continuous sensor measurements.
- The offline reference trajectories could serve as expert demonstrations for imitation learning of online trackers.
Load-bearing premise
The chosen grid resolution, beam-pruning thresholds, and multi-ray visibility evaluator produce trajectories whose real-world visibility and safety properties remain close to the discrete optimum.
What would settle it
Compute an exhaustive optimal visibility score on a small grid instance where the 4D state space can be searched completely, then compare that score against the visibility achieved by TA* on the same instance.
Figures
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents Track A* (TA*), an offline search-based planner for visibility-aware active target tracking on a discretized 4D (x, y, z, t) spatio-temporal grid. It uses a layered DAG heuristic search augmented by three engineering optimizations—cross-time BVH caching for obstacle distances, per-layer beam pruning, and a configurable multi-ray visibility evaluator—while explicitly trading strict optimality for scalability. The central empirical claims are that TA* converges on all 1000+ CARLA scenarios (vs. 56.9% for baseline), reduces mean planning time by 23.0× and worst-case by 11.8× versus an unoptimized BinaryHeap A* under identical inputs and expansion caps, and changes average visibility by only −0.15 pp on the n=141 converged subset, with no scenario exceeding a 5 pp drop.
Significance. If the results hold, TA* supplies a practical offline reference generator for multi-modal tracking datasets and repeatable benchmarking of online planners. The scale of the evaluation (1000-scenario stress test across eight CARLA maps plus a 248-scenario controlled comparison) and the concrete timing/visibility metrics constitute a clear strength. The work is positioned as an engineering contribution that accepts discretization trade-offs, which is appropriate for the robotics application.
major comments (2)
- [§5 / 248-scenario controlled comparison] §5 / 248-scenario controlled comparison: the 23.0× mean and 11.8× worst-case speed-ups and the −0.15 pp visibility change are reported only for one fixed choice of grid resolution, beam width, pruning threshold, and ray count, with no ablation isolating the contribution of BVH caching versus beam pruning versus the multi-ray evaluator and no sensitivity sweeps over these free parameters. Because the paper acknowledges that it trades strict optimality for scalability and flags failure modes in Town07 vegetation, the absence of such analysis leaves the claim that TA* trajectories remain close to the discrete optimum unsupported beyond the specific parameter set tested.
- [§5 / visibility metric definition] §5 / visibility metric definition: the multi-ray visibility evaluator is described as “configurable,” yet no quantitative sensitivity of the reported visibility scores to ray count or ray placement is provided. If visibility is sensitive to these choices (as the skeptic note on Town07 vegetation suggests), the −0.15 pp average change cannot be taken as evidence that the pruned trajectories preserve the visibility properties of the underlying discrete optimum.
minor comments (2)
- [Abstract] Abstract: mean timing and visibility figures are given without error bars, standard deviations, or any indication of statistical significance, which weakens the reader’s ability to judge the reliability of the 23.0× and −0.15 pp claims.
- [Methods] Methods: the precise definition of the layered DAG, the beam-pruning rule, and the cross-time BVH caching data structure would benefit from a small pseudocode listing or diagram to make the three optimizations reproducible from the text alone.
Simulated Author's Rebuttal
We thank the referee for the constructive feedback and positive overall assessment of the work as a practical engineering contribution. We agree that the absence of ablations and sensitivity analysis limits the strength of claims about robustness beyond the tested configuration. We address each major comment below and will incorporate the requested analyses in the revised manuscript.
read point-by-point responses
-
Referee: [§5 / 248-scenario controlled comparison] §5 / 248-scenario controlled comparison: the 23.0× mean and 11.8× worst-case speed-ups and the −0.15 pp visibility change are reported only for one fixed choice of grid resolution, beam width, pruning threshold, and ray count, with no ablation isolating the contribution of BVH caching versus beam pruning versus the multi-ray evaluator and no sensitivity sweeps over these free parameters. Because the paper acknowledges that it trades strict optimality for scalability and flags failure modes in Town07 vegetation, the absence of such analysis leaves the claim that TA* trajectories remain close to the discrete optimum unsupported beyond the specific parameter set tested.
Authors: We acknowledge that the 248-scenario results reflect the combined optimizations under one fixed parameter set chosen via preliminary tuning for practical performance. The controlled comparison (identical inputs, grid, expansion cap, and visibility evaluator) directly measures the net effect on time and visibility relative to unoptimized A*. We agree, however, that isolating individual contributions and providing sensitivity sweeps would better substantiate robustness of the near-baseline visibility claim. In the revision we will add an ablation study and parameter sensitivity analysis (beam width, pruning threshold, ray count) on a representative subset of scenarios, reporting effects on planning time and visibility. revision: yes
-
Referee: [§5 / visibility metric definition] §5 / visibility metric definition: the multi-ray visibility evaluator is described as “configurable,” yet no quantitative sensitivity of the reported visibility scores to ray count or ray placement is provided. If visibility is sensitive to these choices (as the skeptic note on Town07 vegetation suggests), the −0.15 pp average change cannot be taken as evidence that the pruned trajectories preserve the visibility properties of the underlying discrete optimum.
Authors: The multi-ray evaluator approximates continuous visibility via a fixed sampling pattern chosen for consistency across all experiments. The reported −0.15 pp average change is measured under this identical approximation for both TA* and the baseline, so the relative comparison remains valid. We concur that quantitative sensitivity to ray count and placement would strengthen evidence that pruning preserves visibility properties. We will add a sensitivity study in the revised manuscript showing visibility score variation with different ray counts and placements on the same scenarios. revision: yes
Circularity Check
No circularity: empirical benchmark of heuristic planner with explicit optimality trade-off
full rationale
The paper introduces TA* as a beam-pruned DAG search on a 4D grid with BVH caching and multi-ray visibility, explicitly framed as a practical heuristic that trades strict optimality for scalability. All reported claims (23.0x mean speedup, 100% convergence, -0.15 pp visibility delta) are direct empirical measurements on CARLA scenarios against an unoptimized BinaryHeap A* baseline under identical inputs and expansion caps. No fitted parameters are renamed as predictions, no self-citations bear the central result, and the algorithm derivation does not reduce to its own outputs by construction. The evaluation is self-contained against external simulation benchmarks.
Axiom & Free-Parameter Ledger
free parameters (3)
- grid resolution (x,y,z,t)
- beam width / pruning threshold
- number of visibility rays
axioms (2)
- standard math A* with admissible heuristic finds optimal paths on the discrete graph
- domain assumption Beam pruning preserves near-optimal solutions for the visibility objective
Forward citations
Cited by 1 Pith paper
-
CosFly: Plan in the Matrix, Fly in the World
CosFly introduces a box-structured planning and multimodal simulation pipeline for aerial target tracking in CARLA, paired with the public CosFly-Track dataset containing 250 trajectories and approximately 100,000 ren...
Reference graph
Works this paper leans on
-
[1]
R. Bonatti, W. Wang, C. Ho, A. Ahuja, M. Gschwindt, E. Camci, E. Kayacan, S. Choudhury, and S. Scherer, “Towards a robust aerial cinematography platform: Localizing and tracking moving targets in unstructured environments,” inIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2019, pp. 229–236
work page 2019
-
[2]
Visibility-aware trajectory optimization with application to aerial tracking,
Q. Wang, Y . Chen, and F. Gao, “Visibility-aware trajectory optimization with application to aerial tracking,” inIEEE/RSJ International Confer- ence on Intelligent Robots and Systems (IROS). IEEE, 2021, pp. 5549– 5556
work page 2021
-
[3]
Real-time obstacle avoidance for manipulators and mobile robots,
O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,”The International Journal of Robotics Research, vol. 5, no. 1, pp. 90–98, 1986
work page 1986
-
[4]
Predictive active steering control for autonomous vehicle systems,
P. Falcone, F. Borrelli, J. Asgari, H. E. Tseng, and D. Hrovat, “Predictive active steering control for autonomous vehicle systems,”IEEE Trans- actions on Control Systems Technology, vol. 15, no. 3, pp. 566–580, 2007
work page 2007
-
[5]
A formal basis for the heuristic determination of minimum cost paths,
P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,”IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968
work page 1968
-
[6]
Sampling-based algorithms for optimal motion planning,
S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,”The International Journal of Robotics Research, vol. 30, no. 7, pp. 846–894, 2011
work page 2011
-
[7]
L. Xin, P. Wang, C.-Y . Chan, J. Chen, S. E. Li, and B. Jiang, “Enable faster and smoother spatio-temporal trajectory planning for autonomous vehicles in constrained dynamic environment,”Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, vol. 235, no. 10-11, pp. 2838–2853, 2021
work page 2021
-
[8]
Efficient spatiotemporal graph search for local trajectory planning on oval race tracks,
M. Rowold and J. Betz, “Efficient spatiotemporal graph search for local trajectory planning on oval race tracks,”Actuators, vol. 11, no. 11, p. 319, 2022
work page 2022
-
[9]
Spatio-temporal trajectory planning using search and optimizing method for autonomous driving,
L. Zhong, Z. Li, Z. Wang, Y . Zhenget al., “Spatio-temporal trajectory planning using search and optimizing method for autonomous driving,” inSAE Technical Paper. SAE International, 2024
work page 2024
-
[10]
Eva-planner: Environmental adaptive quadrotor planning,
L. Wang, H. Wei, T. Yang, Y . Tang, L. Yu, and X. Yang, “Eva-planner: Environmental adaptive quadrotor planning,”IEEE Transactions on Intelligent Vehicles, 2023, cited as “Eva-Tracker” in the related work section
work page 2023
-
[11]
Svpto: safe visibility-guided perception-aware trajectory optimization for aerial tracking,
H. Wang, Y . Zhang, L. Hanet al., “Svpto: safe visibility-guided perception-aware trajectory optimization for aerial tracking,”IEEE Transactions on Industrial Informatics, 2023
work page 2023
-
[12]
Path planning for uav tracking target based on improved a-star algorithm,
Y . Cai, Q. Xi, X. Xing, H. Gui, and Q. Liu, “Path planning for uav tracking target based on improved a-star algorithm,” inIEEE International Conference on Unmanned Systems (ICUS). IEEE, 2019, pp. 1–5
work page 2019
-
[13]
Uav target tracking: a survey,
P. Wu, Y . Li, and D. Xue, “Uav target tracking: a survey,”Artificial Intelligence Review, vol. 58, no. 1, pp. 1–45, 2025
work page 2025
-
[14]
Theta*: Any-angle path planning on grids,
A. Nash, K. Daniel, S. Koenig, and A. Felner, “Theta*: Any-angle path planning on grids,” inAAAI Conference on Artificial Intelligence, 2007, pp. 1177–1183
work page 2007
- [15]
-
[16]
CARLA: An open urban driving simulator,
A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V . Koltun, “CARLA: An open urban driving simulator,” inProceedings of the 1st Annual Conference on Robot Learning, 2017, pp. 1–16
work page 2017
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.