UniSaT: Unified-Objective Belief Model and Planner to Search for and Track Multiple Objects

Leonardo T. B. Santos, Brady Moon, Sebastian Scherer, Hoa Van Nguyen

Abstract

Path planning for autonomous search and tracking of multiple objects is a critical problem in applications such as reconnaissance, surveillance, and data gathering. Due to the inherent competing objectives of searching for new objects while maintaining tracks for found objects, most current approaches rely on multi-objective planning methods, leaving it up to the user to tune parameters to balance between the two objectives, usually based on heuristics or trial and error. In this paper, we introduce UniSaT (Unified Search and Track), a novel unified-objective formulation for the search and track problem based on Random Finite Sets (RFS). Our approach models unknown and known objects using a combined generalized labeled multi-Bernoulli (GLMB) filter. For unseen objects, UniSaT leverages both cardinality and spatial prior distributions, allowing it to operate without prior knowledge of the exact number of objects in the search space. The planner maximizes the mutual information of this unified belief model, creating balanced search and tracking behaviors. We demonstrate our work in a simulated environment, presenting both qualitative results and quantitative improvements over a multi-objective method.

Introduction: The Search-Track Dilemma

Autonomous agents, such as drones, often face a fundamental conflict when monitoring an environment: should they stay with known targets to ensure high-fidelity tracking, or should they explore new areas to find undiscovered objects? Traditionally, this is framed as a multi-objective optimization problem where engineers manually tune weights to balance "search" and "track" rewards. However, these "magic numbers" are often brittle and environment-specific.

UniSaT (Unified Search and Track) addresses this by treating searching and tracking as a single mathematical problem. By modeling both discovered and undiscovered targets within a single belief state, the system uses a single information-theoretic objective to naturally coordinate complex missions without manual parameter tuning.

Conceptual overview of UniSaT's unified belief model, incorporating cardinality and spatial priors.

The UniSaT Framework

The core of UniSaT is a Generalized Labeled Multi-Bernoulli (GLMB) filter that maintains a unified belief. This belief is initialized with "priors"—probabilistic guesses about how many objects might exist (cardinality prior) and where they might be located (spatial prior).

Hybrid Representation

To balance computational efficiency with accuracy, UniSaT employs a hybrid filtering approach:

  • Sequential Monte Carlo (SMC): Particles represent "potential" objects in the search space, allowing the model to handle complex, multi-modal spatial distributions.
  • Gaussian Mixture (GM): Once an object is detected and its uncertainty is reduced, it is converted into a GM representation for efficient, high-fidelity tracking.

The Algorithmic Loop

The system operates in a continuous loop of observation, update, and planning. A key feature is the use of "negative information": if the drone observes an area where it expected a target but finds nothing, the filter updates to reflect that a target likely does not exist there, effectively "clearing" the search space.

The UniSaT algorithmic loop: from belief initialization to POMDP planning and action.

Planning with Mutual Information

Instead of balancing two separate reward functions, the UniSaT planner maximizes Mutual Information (MI). Because both "expected" and "found" objects exist within the same GLMB framework, the planner naturally chooses paths that reduce the total uncertainty of the entire system. If the drone is confident in its current tracks but knows there is a high probability of targets in an unexplored region, the MI calculation automatically prioritizes searching that region.

Experimental Results

UniSaT was evaluated against a state-of-the-art multi-objective baseline across various simulated scenarios, including bimodal target distributions and cases where the initial target count was significantly over- or underestimated. Performance was measured using the OSPA$^2$ (Optimal Sub-pattern Assignment) metric, which accounts for errors in both target localization and cardinality (the estimated number of targets).

Key findings include:

  • Superior Accuracy: UniSaT outperformed the baseline in all tested scenarios. In cases where the target count was underestimated, UniSaT achieved an error of 22.35m, compared to 33.79m for the baseline.
  • Robustness to Priors: The system is not "trapped" by its initial guesses. If more targets are present than expected, the "birth model" allows the system to instantiate new tracks as they are observed.
  • Faster Convergence: UniSaT identifies the correct number of targets significantly faster than traditional methods by effectively leveraging spatial priors and negative observations.

Conclusion

UniSaT provides a mathematically principled way to solve the search-and-track problem without the need for heuristic weight tuning. By unifying the belief model and the planning objective, it enables more robust and autonomous behavior in complex, uncertain environments. Future work will focus on improving computational efficiency for high-target densities and modeling correlations between target locations to further enhance search performance.

Summary updated

Abstract

Path planning for autonomous search and tracking of multiple objects is a critical problem in applications such as reconnaissance, surveillance, and data gathering. Due to the inherent competing objectives of searching for new objects while maintaining tracks for found objects, most current approaches rely on multi-objective planning methods, leaving it up to the user to tune parameters to balance between the two objectives, usually based on heuristics or trial and error. In this paper, we introduce UniSaT (Unified Search and Track), a novel unified-objective formulation for the search and track problem based on Random Finite Sets (RFS). Our approach models unknown and known objects using a combined generalized labeled multi-Bernoulli (GLMB) filter. For unseen objects, UniSaT leverages both cardinality and spatial prior distributions, allowing it to operate without prior knowledge of the exact number of objects in the search space. The planner maximizes the mutual information of this unified belief model, creating balanced search and tracking behaviors. We demonstrate our work in a simulated environment, presenting both qualitative results and quantitative improvements over a multi-objective method.
BibTeX
@misc{santos2024unisat,
  author = {Leonardo T. B. Santos and Brady Moon and Sebastian Scherer and Hoa Van Nguyen},
  title = {{UniSaT: Unified-Objective Belief Model and Planner to Search for and Track Multiple Objects}},
  year = {2024},
  eprint = {2405.15997},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.15997},
}

Loading related content...

Figure