Title: Solving an escape interdiction game on transportation networks
Speaker: Dr. Sukanya Samanta, Post-doctoral researcher, Kyushu University, Japan.
Day, Date and Time: Monday, July 24, 2023, 11 AM to 12 AM IST (Online mode)
Abstract: Containment of dynamic crimes such as kidnapping, bank robbery, hit-and-run, etc., is a challenging issue for law enforcement agencies as the criminal changes his location with time. This type of scenario is generally modeled as an escape interdiction game. We consider two types of players, namely multiple defenders and a single attacker. The defenders choose a sequence of junctions to protect, while the attacker chooses an escape path and the travel time on distinct edges along the path. Hence, both the defender strategy space and the continuous attacker strategy space suffer exponential growth. This leads to major challenges in the computation of the optimal solution with respect to each player. We develop a double oracle Variable Neighborhood Search (VNS) based meta-heuristic algorithm for finding near-optimal defender and attacker strategies in a time efficient manner. We test the efficiency of this approach against an established exact algorithm named Escape Interdiction Game Solver (EIGS). We use EIGS to generate the benchmark results to check the performance of our heuristic. We also show that the performance of our approach is reasonably good under strict time limitations, as observed in practice.
Speaker Bio: She is a postdoctoral researcher at the multi-agent laboratory in the Department of ISEE (Information Science and Electrical Engineering), Kyushu University, Japan. Prior to joining Kyushu University, She was a Ph.D. candidate in the Advanced Technology Development Centre (Industrial & Systems Engineering (ISE) and Computer Science & Engineering (CSE)) at the Indian Institute of Technology (IIT) Kharagpur, India. She completed Master of Technology (M.Tech) in Computer Science and Information Security from the National Institute of Technology Warangal and Bachelor of Technology (B.Tech) in Computer Science and Engineering from Government College of Engineering & Textile Technology Berhampore under the West Bengal University of Technology. She also qualified the GATE exam (Computer Science) in 2014 (AIR 944 out of 1,55,190 students) and received the Institute Silver Medal for Department Rank 1 in Graduation. Her research interests include security games and the application of meta-heuristic techniques to solve large-scale optimization problems.