Skip to Main content Skip to Navigation
New interface
Conference papers

Quadratic Programming for Multi-Target Tracking

Raghav Aras 1, 2 Alain Dutech 1 François Charpillet 1 
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We consider the problem of tracking multiple, partially observed targets using multiple sensors arranged in a given configuration. We model the problem as a special case of a (finite horizon) DEC-POMDP. We present a quadratic program whose globally optimal solution yields an optimal tracking joint policy, one that maximizes the expected targets detected over the given horizon. However, a globally optimal solution to the QP cannot always be found since the QP is nonconvex. To remedy this, we present two linearizations of the QP to equivalent 0-1 mixed integer linear programs (MIPs) whose optimal solutions, which may be always found through the branch and bound method, for example, yield optimal joint policies. Computational experience on different sensor configurations shows that finding an optimal joint policy by solving the proposed MIPs is much faster than using existing algorithms for the problem.
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Alain Dutech Connect in order to contact the contributor
Submitted on : Friday, January 29, 2010 - 3:26:40 PM
Last modification on : Saturday, June 25, 2022 - 7:44:40 PM
Long-term archiving on: : Thursday, October 18, 2012 - 1:45:19 PM


Files produced by the author(s)


  • HAL Id : inria-00451638, version 1



Raghav Aras, Alain Dutech, François Charpillet. Quadratic Programming for Multi-Target Tracking. AAMAS Worshop : Multi-agent Sequential Decision-Making in Uncertain Domains, May 2009, Budapest, Hungary. pp.4-10. ⟨inria-00451638⟩



Record views


Files downloads