Date/Time
Date(s) - September 09, 2022
10:45 am - 12:35 pm
Categories No Categories
Rakesh Nagi
Date : Friday, September 9, 2022
Mode : Virtual
Affiliation: UIUC
Bio: Visit Page
Title: A 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 creative 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 e ciently 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.
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 a liate 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 Engineering at the University at Bu alo (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 Achievement Award? in recognition of outstanding achievements in scholarly activity (2009), Business First of Bu alo?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 scienti c 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.