Toward Efficiently and Optimally Solving Long-Horizon Combinatorial Planning Challenges 

Abstract: To unlock the transformative potential of robotics in real-world applications, robots must do more than simply perform tasks—they must operate efficiently, scale seamlessly, and approach optimal performance. In this talk, I will present our lab’s recent advances in tackling three foundational challenges in robotics research: multi-robot path planning in grid environments, cluttered multi-object rearrangement, and non-prehensile manipulation. Although each of these problems is provably computationally intractable (NP-hard or worse, with explicit complexity proofs provided for the first two), our work demonstrates that novel, principled algorithms can efficiently/effectively compute (near-)optimal solutions.

Key publications to be discussed: 

https://arxiv.org/pdf/2408.05385 (JAIR 24) 

https://arxiv.org/pdf/2304.01764 (IJRR 23)

https://arxiv.org/pdf/2202.01426 (ICRA 22)

Bio: Jingjin Yu is an Associate Professor in the Department of Computer Science at Rutgers University, New Brunswick. He earned his B.S. from the University of Science and Technology of China, followed by an M.S. in Computer Science and a Ph.D. in Electrical and Computer Engineering from the University of Illinois, where he also served briefly as a postdoctoral researcher. Prior to joining Rutgers, he conducted postdoctoral research at the Massachusetts Institute of Technology. His research spans the field of algorithmic robotics, with a particular focus on optimality, complexity, and the design of efficient decision-making methods. Yu is a two-term IEEE RAS Distinguished Lecturer (2022–2027) and has received the NSF CAREER Award as well as an Amazon Research Award.