Chance Constrained Simultaneous Task Allocation and Path Planning for Multi-Robot Systems


Nilanjan Chakraborty

Stony Brook University
Fri, Apr 2 2021 - 10:00 am (GMT + 7)
About Speaker

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.

Related seminars

Anh Nguyen

Microsoft GenAI

The Revolution of Small Language Models
Fri, Mar 8 2024 - 02:30 pm (GMT + 7)

Thang D. Bui

Australian National University (ANU)

Recent Progress on Grokking and Probabilistic Federated Learning
Fri, Jan 26 2024 - 10:00 am (GMT + 7)

Tim Baldwin

MBZUAI, The University of Melbourne

Tue, Jan 9 2024 - 10:30 am (GMT + 7)

Quan Vuong

Google DeepMind

Scaling Robot Learning
Wed, Dec 27 2023 - 10:00 am (GMT + 7)