Globally Optimal Multi-Object Tracking with Splitting and Merging

Mihaela Mihaylova, Jelle Piepenbrock, Johannes Textor
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4514-4527, 2026.

Abstract

In multi-object tracking (MOT), the trajectories of moving objects – e.g., molecules, cells, or people – must be recovered from detected positions. MOT is often solved using network flow approaches to find globally optimal solutions. Here, we consider a version of MOT where objects can split or merge – such as cells that are moving but also dividing while being tracked. We show that this problem is NP-hard, phrase it as a Max-SAT problem, and ask: (1) To what extent can modern optimized satisfiability solvers be applied to realistic MOT problems? (2) Are the globally optimal solutions better than those generated by existing methods? Using both simulated data and real-world cell tracking data, we show that Max-SAT is a computationally costly but feasible approach that can lead to substantially improved solutions for problems of realistic size. We hope that the Max-SAT instances generated by the MOT problem can serve as practically relevant benchmarking cases for the future improvement of Max-SAT solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-mihaylova26a, title = {Globally Optimal Multi-Object Tracking with Splitting and Merging}, author = {Mihaylova, Mihaela and Piepenbrock, Jelle and Textor, Johannes}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4514--4527}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/mihaylova26a/mihaylova26a.pdf}, url = {https://proceedings.mlr.press/v337/mihaylova26a.html}, abstract = {In multi-object tracking (MOT), the trajectories of moving objects – e.g., molecules, cells, or people – must be recovered from detected positions. MOT is often solved using network flow approaches to find globally optimal solutions. Here, we consider a version of MOT where objects can split or merge – such as cells that are moving but also dividing while being tracked. We show that this problem is NP-hard, phrase it as a Max-SAT problem, and ask: (1) To what extent can modern optimized satisfiability solvers be applied to realistic MOT problems? (2) Are the globally optimal solutions better than those generated by existing methods? Using both simulated data and real-world cell tracking data, we show that Max-SAT is a computationally costly but feasible approach that can lead to substantially improved solutions for problems of realistic size. We hope that the Max-SAT instances generated by the MOT problem can serve as practically relevant benchmarking cases for the future improvement of Max-SAT solvers.} }
Endnote
%0 Conference Paper %T Globally Optimal Multi-Object Tracking with Splitting and Merging %A Mihaela Mihaylova %A Jelle Piepenbrock %A Johannes Textor %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-mihaylova26a %I PMLR %P 4514--4527 %U https://proceedings.mlr.press/v337/mihaylova26a.html %V 337 %X In multi-object tracking (MOT), the trajectories of moving objects – e.g., molecules, cells, or people – must be recovered from detected positions. MOT is often solved using network flow approaches to find globally optimal solutions. Here, we consider a version of MOT where objects can split or merge – such as cells that are moving but also dividing while being tracked. We show that this problem is NP-hard, phrase it as a Max-SAT problem, and ask: (1) To what extent can modern optimized satisfiability solvers be applied to realistic MOT problems? (2) Are the globally optimal solutions better than those generated by existing methods? Using both simulated data and real-world cell tracking data, we show that Max-SAT is a computationally costly but feasible approach that can lead to substantially improved solutions for problems of realistic size. We hope that the Max-SAT instances generated by the MOT problem can serve as practically relevant benchmarking cases for the future improvement of Max-SAT solvers.
APA
Mihaylova, M., Piepenbrock, J. & Textor, J.. (2026). Globally Optimal Multi-Object Tracking with Splitting and Merging. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4514-4527 Available from https://proceedings.mlr.press/v337/mihaylova26a.html.

Related Material