Hierarchical Planning for Long-Horizon Multi-Target Tracking Under Target Motion Uncertainty

Abstract

Achieving persistent tracking of multiple dynamic targets over a large spatial area poses significant challenges for a single-robot system with constrained sensing capabilities. As the robot moves to track different targets, the ones outside the field of view accumulate uncertainty, making them progressively harder to track. An effective path planning algorithm must manage uncertainty over a long horizon and account for the risk of permanently losing track of targets that remain unseen for too long. However, most existing approaches rely on short planning horizons and assume small, bounded environments, resulting in poor tracking performance and target loss in large-scale scenarios. In this paper, we present a hierarchical planner for tracking multiple moving targets with an aerial vehicle. To address the challenge of tracking non-static targets, our method incorporates motion models and uncertainty propagation during path execution, allowing for more informed decision-making. We decompose the multi-target tracking task into sub-tasks of single target search and detection, and our proposed pipeline consists of a novel low-level coverage planner that enables searching for a target in an evolving belief area, and an estimation method to assess the likelihood of success for each sub-task, making it possible to convert the active target tracking task to a Markov decision process (MDP) that we solve with a tree-based algorithm to determine the sequence of sub-tasks. We validate our approach in simulation, demonstrating its effectiveness compared to existing planners for active target tracking tasks, and our proposed planner outperforms existing approaches, achieving a reduction of 11–70% in final uncertainty across different environments. We also conduct a real-robot experiment to verify our method’s practical deployability.

System Overview

Observed maps are processed through three independent global map prediction models, generating prediction maps. These maps are averaged and passed through a convolutional encoder to extract a 256-dimensional feature vector. This vector is concatenated with frontier centers, prediction and utility scores, distances from the agent, and remaining budget. The resulting vector is fed into a fully connected network that outputs N values, and the argmax is selected as the index of the frontier action.

Target Search under Motion Uncertainty

Each moving target is represented by a time-evolving belief distribution that propagates under motion uncertainty when the target is not observed. As the belief region expands and drifts with the predicted target motion, the agent first intercepts the belief center and then executes a shifting spiral coverage path that continuously adapts to the moving and growing uncertainty region.

Shifting spiral coverage for a moving target under motion uncertainty. Colored point clouds show 10,000 Monte Carlo samples of the target belief propagated under the same motion model at different time instances, while ellipses depict the corresponding covariance abstractions.

Outcome Estimation + MCTS Global Planning

To enable long-horizon decision making, we estimate the outcome of each target search task before committing to execution. Given a predicted belief evolution and a coverage strategy, we approximate how likely the target can be found and how much time the search is expected to consume. This allows each search attempt to be summarized by a small set of outcome statistics that capture both success likelihood and cost. Using these estimates, we formulate the multi-target tracking problem as a sequential decision process and apply a tree-based planner to determine which target to pursue next under a fixed time budget. During execution, the planner can be re-invoked as new observations arrive, enabling adaptive and robust long-horizon planning.

Results

Quantitative comparison of final tracking uncertainty across different numbers of targets. We compare against ARVI [1], heuristic A* [2], and learning-based method [3]. Lower values indicate better long-horizon tracking performance.

[1] B. Schlotfeldt, D. Thakur, N. Atanasov, V. Kumar, and G. J. Pappas, Anytime Planning for Decentralized Multirobot Active Information Gathering
[2] B. Schlotfeldt, N. Atanasov, and G. J. Pappas, Maximum Information Bounds for Planning Active Sensing Trajectories
[3] H. Jeong, C. Zhang, G. J. Pappas, and D. D. Lee, Assumed Density Filtering Q-Learning

4 targets

6 targets

BibTeX

@article{yuan2025hptracking, title = {Hierarchical Planning for Long-Horizon Multi-Target Tracking Under Target Motion Uncertainty}, author = {Yuan, Junbin and Moon, Brady and Cao, Muqing and Scherer, Sebastian}, journal = {IEEE Robotics and Automation Letters}, year = {2025}, doi = {10.1109/LRA.2025.3625492} }