Sequentially connected 2D assignment problems solved using Lagrangian dual methods

Visa enkel post
dc.contributor.authorCarlsson, Camilla
dc.contributor.authorEkelund, Hanna
dc.contributor.departmentChalmers tekniska högskola / Institutionen för matematiska vetenskapersv
dc.contributor.examinerStrömberg, Ann-Brith
dc.contributor.supervisorStrömberg, Ann-Brith
dc.date.accessioned2022-07-08T13:54:05Z
dc.date.available2022-07-08T13:54:05Z
dc.date.issued2022sv
dc.date.submitted2020
dc.description.abstractMulti-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.sv
dc.identifier.coursecodeMVEX03sv
dc.identifier.urihttps://hdl.handle.net/20.500.12380/305151
dc.language.isoengsv
dc.setspec.uppsokPhysicsChemistryMaths
dc.subjectMulti-object tracking, Connected assignment problems, Subgradient, ADMM, Integrality property, Mixed binary linear program, LP relaxationsv
dc.titleSequentially connected 2D assignment problems solved using Lagrangian dual methodssv
dc.type.degreeExamensarbete för masterexamensv
dc.type.uppsokH
local.programmeEngineering mathematics and computational science (MPENM), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
Master_Thesis_CamillaCarlsson_HannaEkelund_2022.pdf
Storlek:
1.44 MB
Format:
Adobe Portable Document Format
Beskrivning:
Ladda ner
License bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
license.txt
Storlek:
1.51 KB
Format:
Item-specific license agreed upon to submission
Beskrivning:
Ladda ner
Samling
Examensarbeten för masterexamen