Title: Chance Constrained Simultaneous Task Allocation and Path Planning for Multi-Robot Systems
Speaker: Nilanjan Chakraborty - Stony Brook University
Date/Time: Friday, Apr 02 2021 - 10:00 am (GMT + 7)
Video recording: https://youtu.be/5G1c-q1QW0k
Nilanjan Chakraborty is an Assistant Professor in the Department of Mechanical Engineering at Stony Brook University (SBU). Prior to joining SBU he was a Project Scientist as well as a postdoctoral researcher at The Robotics Institute, Carnegie Mellon University. He has a PhD in Computer Science from Rensselaer Polytechnic Institute. He serves as an Associate Editor for IEEE Robotics and Automation Letters. His research interests are in multi-robot coordination, robot motion planning and manipulation planning, multi-body dynamics, and human-robot interaction. He was a recipient of the Best Paper Award (Computer Systems Technical Group) at the Annual Meeting of the Human Factors and Ergonomics Society in 2013 and the Best Student Paper Award at Robotics: Science and Systems Conference in 2007.
In many application scenarios of multi-robot systems including parts transfer, mobility-on-demand, and search and rescue, to execute a task, robots have to move to spatially distributed target destinations in an open environment, i.e., in the presence of uncontrolled mobile agents. In such problems, each robot has to be assigned to a task, as well as a collision-free path has to be planned for each robot for moving to the target destination, so that a team performance objective is optimized. Furthermore, the cost (or value) of performing a task is stochastic, which makes the team performance stochastic. In this talk, I will present an algorithmic approach for solving such simultaneous task allocation and path planning (STAPP) problems with probabilistic performance certificates on the team performance. Technically, the STAPP problems can be formulated as a chance-constrained combinatorial optimization problem, which are hard to solve in general. I will show a two-dimensional geometric interpretation of the problem, which allows us to develop a methodical one-parameter search algorithm for computing the optimal solution. I will show computational experiments demonstrating the scalability of our approach with the number of robots and tasks.