Implement multi-frame assignment algorithm

[joldf]

This pull request adds support for multi-frame assignment (MFA).

• This implementation is heavily based on the previous pull request for MFA #344. However, while that was written in MATLAB using the MATLAB wrapper to call it from Stone Soup, this version is written in pure Python and does not require a MATLAB installation.
• As with the original MATLAB implementation, this is based on the article: Xia, Y., Granström, K., Svensson, L., García-Fernández, Á.F., and Williams, J.L., 2019. Multiscan Implementation of the Trajectory Poisson Multi-Bernoulli Mixture Filter. J. Adv. Information Fusion, 14(2), pp. 213–235.
• The actual logic of the algorithm is contained within two files, mfa_init.py and mfa_step.py, which are intentionally independent of any other Stone Soup code so that they could be used as-is in any other code base where they might be useful.
• The results are track oriented (or, in the language of the above paper, trajectory orientated). The hypotheses for each track are stored its tag field (as in the MATLAB implementation). Each time step, the algorithm computes the best overall hypothesis (i.e. the best combination of track hypotheses) based on the whole sliding window but does not directly expose this result. However it would be easy to add if a suitable way of expressing the result could be found. Ultimately, they get exposed indirectly by the n-scan pruning (which prunes track hypotheses that don't match the best hypotheses before the sliding window).
• There are two optimisation steps that call out to external libraries. The first is the Hungarian algorithm in the dual subproblem; this uses linear_sum_assignment in scipy, which is an existing dependency of Stone Soup. The other is solving the linear programming primal problem, which is done using Google OR Tools; this is a mature library with a liberal licence (Apache v2.0), and can also be called from C++ which would aid if this MFA implementation were to be translated to C++. In this pull request, OR Tools is added as a required dependency for Stone Soup, but that could be omitted in which case you would get a reasonably self-explanatory error if you tried to import the MFADataAssociator.

[orosoman-dstl]

I tried running the example script linked in PR #344, and that failed with the following error: I think this is to do with the timestamp being nested inside an object inside the Gaussian Mixture. Are you able to provide a working example?

[joldf]

Sorry about the trouble to get this working, especially the lack of a link in the pull request text to the example script you found referenced from #344 – I had intended to include a link to it, but there was a lot of detail I wanted to mention and I ended up missing that part by accident.

I have just tried the script on a fresh clone of this branch (in case I somehow pushed a different version than I tested locally) and it did work for me. I ran these commands:

git clone https://github.com/joldf/Stone-Soup stone_soup
cd stone_soup
git checkout
git checkout multi_frame_assignment_python
curl -O https://gist.githubusercontent.com/sglvladi/2aeebd831f1264541266f777d00c241b/raw/f228a9b023246510935c14297ebf9809035279fd/MFA_example.py
python MFA_example.py

I also tried merging latest changes from master in case things were broken by more recent commits, and that also worked fine:

git checkout main
git pull https://github.com/dstl/Stone-Soup
git checkout multi_frame_assignment_python
git merge main
# Fix merge conflicts in graphical tool and commit
python MFA_example.py

I set a breakpoint at line 126 of kalman.py, where you got that exception AttributeError: 'GaussianMixture' object has no attribute 'timestamp'. But, for me, the prior object has type TaggedWeightedGaussianState, which does have a prior.timestamp attribute. Additionally, the timestamp parameter is not None anyway, so that expression is not even evaluated. Do you have any ideas on what could be different about your test setup?

[orosoman-dstl]

Ah yes it looks like it does indeed work when using the github version of the branch. I made some very minor changes on my local version which must have caused the error above, so sorry I didn't revert these before checking properly (I wrongly thought it wouldn't make any difference). On a slightly related note though, the best way we can be confident this code works (now and in the future when new code is added) is with some unit tests. You could probably make heavy use of the example script to make that easier.

[sdhiscocks]

@joldf Could you look at adding some unit tests for the code please? Also, could we include tutorial/example, maybe derived from #344?

[sdhiscocks]

I've rebased this onto main, done a minor restructure, added some flake8 fixes, a bug fix for track ordering, and added an animated example based on the one referenced in #344.

TODO:

• [x] Unit tests
• [x] Add additional information about MFA to the example.
• [x] Make ortools optional dependency.

[codecov[bot]]

Codecov Report

Patch coverage: 95.83% and project coverage change: +0.15 :tada:

Comparison is base (2b69b97) 94.66% compared to head (3be5bd1) 94.81%.

:exclamation: Current head 3be5bd1 differs from pull request most recent head acf613c. Consider uploading reports for the commit acf613c to get more accurate results

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #568      +/-   ##
==========================================
+ Coverage   94.66%   94.81%   +0.15%     
==========================================
  Files         171      172       +1     
  Lines        8773     8487     -286     
  Branches     1707     1627      -80     
==========================================
- Hits         8305     8047     -258     
+ Misses        342      323      -19     
+ Partials      126      117       -9     

Flag	Coverage Δ
integration	70.07% <88.14%> (+0.05%)	:arrow_up:
unittests	92.60% <94.55%> (+1.84%)	:arrow_up:

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
stonesoup/dataassociator/mfa/_step.py	93.10% <93.10%> (ø)
stonesoup/dataassociator/mfa/__init__.py	94.59% <94.59%> (ø)
stonesoup/types/mixture.py	94.04% <94.73%> (+2.15%)	:arrow_up:
stonesoup/dataassociator/mfa/_init.py	100.00% <100.00%> (ø)
stonesoup/hypothesiser/mfa.py	100.00% <100.00%> (ø)
stonesoup/types/update.py	100.00% <100.00%> (ø)

... and 4 files with indirect coverage changes

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

[sdhiscocks]

Added a few more changes to add some consistency with changes that had occurred on main branch.

Once merged, I'll raise an issue in regards of how measurement history is stored, as use of indices in tags, I don't think is the ideal approach.

[joldf]

🎉