Multi-robot Coordination Under Constraints and Uncertainty

The goal of this research is to design centralized and distributed algorithms for multi-robot task and resource allocation problems with realistic physical, sensing, communication, and information models. Roughly speaking, multi-robot task allocation problems are of the following form: Given a mission consisting of a set of atomic tasks and a payoff (or cost) for each task, compute which robots should do which tasks and/or the sequence/schedule in which the tasks should be done such that a team performance objective is optimized, while ensuring that any task constraints or robot resource constraints are satisfied. In practice, there may be uncertainties associated with the payoff or resource consumption parameters. Furthermore, there may be constraints arising from the capability of the robot, task structure, and the environment in which the robot is operating. We develop algorithms that can deal with uncertainty as well as the physical robot-dependent and task-dependent constraints. Please see below for more details about the problems that we study and our technical approaches.

Simultaneous path planning and task allocation under uncertainty


Multi-robot task allocation under uncertainty


Multi-robot task allocation under constraints


Reinforcement learning for task allocation


Related Publications

  1. F. Yang and N. Chakraborty, ``Chance Constrained Simultaneous Path Planning and Task Assignment with Bottleneck Objective", IEEE International Conference on Robotics and Automation (ICRA), Xi'an, China, June, 2021.

  2. X. Ou, Q. Chang, and N.Chakraborty, ``A Method Integrating Q-Learning With Approximate Dynamic Programming for Gantry Work Cell Scheduling", IEEE Transactions on Automation Sciences and Engineering, Vol. 18, No. 1, pp. 85-93, January 2021.

  3. F. Yang and N. Chakraborty, ``Chance Constrained Simultaneous Path Planning and Task Assignment for Multiple Robots with Stochastic Path Costs'', IEEE International Conference on Robotics and Automation (ICRA), Paris, France, June, 2020.

  4. F. Yang and N. Chakraborty, ``Algorithm for Multi-robot Chance Constrained Generalized Assignment Problem with Stochastic Resource Consumption'', IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, USA, October, 2020.

  5. J. Huang, Q. Chang and N. Chakraborty, "Machine Preventive Replacement Policy for Serial Production Lines Based on Reinforcement Learning," 15th IEEE International Conference on Automation Science and Engineering (CASE), pp. 523-528, August 2019.

  6. X. Ou, Q. Chang, and N.Chakraborty, ``Simulation study on reward function of reinforcement learning in gantry work cell scheduling", Journal of Manufacturing Systems, Vol. 50, pp 1-8, January 2019.

  7. F. Yang and N. Chakraborty, ``Algorithm for Optimal Chance Constrained Knapsack Problem with Applications to Multi-Robot Teaming'', IEEE International Conference on Robotics and Automation (ICRA), pp. 1043 - 1049 Brisbane, May, 2018.

  8. F. Yang and N. Chakraborty, ``Algorithm for Optimal Chance Constrained Linear Assignment'', IEEE International Conference on Robotics and Automation (ICRA), Singapore, May, 2017.

  9. X. Ou, Q. Chang, N.Chakraborty, and J. Wang, ``Gantry Scheduling for Multi-Gantry Production System by Online Task Allocation Method", IEEE Robotics and Automation Letters, Vol. 2, No. 4, pp. 1848 – 1855, October 2017. (Also appears in IEEE Conference on Automation Science and Engineering, 2017)

  10. D. Mitchell, N. Chakraborty, K. Sycara, and N. Michael, ``Multi-robot Persistent Coverage with Stochastic Task Costs'', International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany, September, 2015.

  11. L. Luo, N. Chakraborty, and K. Sycara, ``Distributed Algorithms for Multi-Robot Task Assignment with Task Deadline Constraints'', IEEE Transactions on Automation Sciences and Engineering, Vol. 12, No. 3, pp. 876 - 888, July 2015.

  12. D. Mitchell, M. Corah, N. Chakraborty, K. Sycara, and N. Michael, ``Multi-robot Long-term Persistent Coverage with Fuel Constrained Robots'', IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA, May, 2015.

  13. L. Luo, N. Chakraborty, and K. Sycara, ``Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks'', IEEE Transactions on Robotics, Vol. 34, No. 1, pp. 19-30, February 2015.

  14. L. Luo, N. Chakraborty, and K. Sycara, ``Distributed Algorithm Design for Multi-Robot Generalized Task Assignment'', IEEE International Conference on Intelligent Robots and Systems, Tokyo, Japan, November, 2013.

  15. L. Luo, N. Chakraborty, and K. Sycara, ``Competitive Analysis of Repeated Greedy Auction Algorithm for Online Multi-Robot Task Assignment'', 2012 IEEE International Conference on Robotics and Automation , Minneapolis, Minnesota, May 2012.

  16. N.Chakraborty, S. Akella, and J.T. Wen, ``Coverage of a Planar Point Set with Multiple Robots subject to Geometric Constraints'', IEEE Transactions on Automation Sciences and Engineering, Vol. 7, No. 1, pp. 111-122, January 2010.

  17. N. Chakraborty, S. Akella, and J. T. Wen, ``Minimum Time Point Assignment for Coverage by Two Constrained Robots'', 2008 IEEE International Conference on Robotics and Automation, Pasadena, CA, May 2008.