Sequentially connected 2D assignment problems solved using Lagrangian dual methods
Typ
Examensarbete för masterexamen
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2022
Författare
Carlsson, Camilla
Ekelund, Hanna
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Multi-object tracking (MOT) algorithms are used to track different objects over
time. The GOSPA metric has been used to accurately quantify object tracking in
one time step, but it does not take into account the so-called track switches. This
thesis will explore how an extended GOSPA metric can be solved efficiently. The
extended GOSPA metric is modeled as a mixed binary linear program, which consists
of several connected 2D assignment problems. To solve these, we utilize LP
relaxation which results in a lower bound on the optimal value unless the problem
possesses integrality property, in which case it equals the optimal value. We have
implemented two methods to quantify MOT algorithms, multi-block ADMM, and
a subgradient method. Our results show that both algorithms work well and scale
linearly with the number of time steps and cubic with the number of estimates and
ground truths. Thanks to a well-working heuristic which can be used as initialization,
both methods converge fast for most instances. The heuristic finds optimal
values for all besides one of our test instances. The optimal solutions to all instances
are integer, indicating that the. Because of this, we formulate a conjecture that the
connected assignment problem also possesses integrality property, although the constraint
matrix is not totally unimodular. To improve the results, we suggest that
one should prove or disprove the conjecture, to know whether the problem always
has integrality property or not. Also, one should improve the numerical solution
of the 2D assignment problems, since most of the computing time is spent on the
solution of the subproblems.
Beskrivning
Ämne/nyckelord
Multi-object tracking, Connected assignment problems, Subgradient, ADMM, Integrality property, Mixed binary linear program, LP relaxation