ISE Fall Seminar – Rakesh Nagi

Details

Presented By: Dr Rakesh Nagi with UIUC

Location: Virtual – Zoom – https://ufl.zoom.us/j/98518592687?pwd=L2NPRkVKMDAvNVhzUGlSdWZRNitQUT09

Title: GPU Accelerated Dual-Ascent Algorithm for the Multi-dimensional
Assignment Problem in a Multi-Target Tracking Application*

Abstract: We develop a Graphics Processing Unit (GPU) accelerated algorithm for the NP-Hard Multi-
dimensional Assignment Problem (MAP), which is suitable for target tracking applications.
First, the MAP formulation with a quadratic objective function is reformulated using a cre-
ative linearization technique. This formulation lends itself well to Lagrangian Relaxation,
which decomposes into pairwise Linear Assignment Problems (LAPs). These LAPs can be
solved in parallel and are each solved using the GPU accelerated method of Date and Nagi
(2016, 2017). Next, we propose a dual-ascent scheme for the Lagrange multiplier updates.
The advantage of this scheme is that it results in monotonically increasing lower bounds
and converges in a fraction of the iterations typically needed for a subgradient method. The
dual-ascent scheme is also parallelized for the GPU. Finally we develop a creative gap closure
scheme with M-best LAP solutions for each dimension and shortest path in the resulting
staged graph. The algorithm is applied to the Multi-Target Tracking problem and tested
on the datasets for maneuverable targets. Scaling studies are also performed and note that
the processing time goes down approximately linearly in the number of GPU devices. The
algorithm is able to eciently solve up to a problem size of 400 targets in a 400 time-frames
with high accuracy. Some results on missed detections and false alarms will also be shared.
Keywords: Multi-dimensional Assignment Problem; Linear Assignment Problem; Dual-
Ascent; Data Association; Multi-Target Tracking; Parallel Algorithms; Graphics Processing
Unit (GPU); CUDA.

*Joint work with Samhita Vadrevi, PhD student, ISE@UIUC
1

Bio
Rakesh Nagi is Donald Biggar Willett Professor of Engineering at the University of Illinois,
Urbana-Champaign. He served as the Department Head of Industrial and Enterprise Systems
Engineering (2013-2019). He also served as the Interim Director of the Illinois Applied Research
Institute (2016-2018). He is an aliate faculty in Computer Science, Electrical and Computer
Engineering, Coordinated Science Laboratory, and Computational Science and Engineering.
Previously he served as the Chair (2006-2012) and Professor of Industrial and Systems Engineer-
ing at the University at Bualo (SUNY) (1993-2013). He received his Ph.D. (1991) and M.S.
(1989) degrees in Mechanical Engineering from the University of Maryland at College Park,
while he worked at the Institute for Systems Research and INRIA, France, and B.E. (1987)
degree in Mechanical Engineering from University of Roorkee (now IIT-R), India.
He is a recipient of IISE David F. Baker Distinguished Research Award (2022), INFORMS
Koopman Award from Military Application Society (2021, 2018), DARPA Graph Challenge,
Champion (2020), Honorable Mention (2017, 2019), Finalist (2018), Innovation Award (2018,
2019), IIE Transactions on Design and Manufacturing, Best paper award from journal issues
from July 2011 through June 2012 (2013), IIE Fellow Award (2010), UB?s ?Sustained Achieve-
ment Award? in recognition of outstanding achievements in scholarly activity (2009), Business
First of Bualo?s ?40 under Forty? award (2004), SME’s Milton C. Shaw Outstanding Young
Manufacturing Engineer Award (1999), IIE’s Outstanding Young Industrial Engineer Award in
Academia (1999), and National Science Foundation’s CAREER Award (1996). He has over 200
papers in peer-reviewed scientic journals and conferences. Dr. Nagi’s major research thrust is
in the area of applied/military operations research and manufacturing/production systems. His
recent research interests are in Location theoretic approaches to Facilities Design, Information
Fusion, Intelligence Applications, Social Networks and Military Operations Research.

Please contact Barbara Martin in ISE with any questions or information needed for the seminar: bflorence@ufl.edu