Chance Constrained Simultaneous Path Planning and Task Assignment with Bottleneck Objective

We present a novel algorithm for combined task assignment and path planning on a roadmap with stochastic costs. In this problem, the initially unassigned robots and tasks are located at known positions in a roadmap. We want to assign a unique task to each robot and compute a path for the robot to go to the task location. Given the means and variances of travel cost, our goal is to develop algorithms that guarantee that for each robot, with high probability, the total travel cost is below a minimum value in any realization of the stochastic travel costs. We prove that the solution can be obtained by solving (a) a chance-constrained shortest path problems for all robot-task pairs and (b) a linear bottleneck assignment problem in which the cost of an assignment is equal to the optimal objective value of the former problem. We propose algorithms for solving the chance-constrained shortest path problem either optimally or approximately by solving a number of deterministic shortest path problems that minimize some linear combination of means and variances of edge costs. We present simulation results on randomly generated networks and data to demonstrate that our algorithm is scalable with the number of robots (or tasks) and the size of the network.

Authors

• Fan Yang
• Nilanjan Chakraborty

Keywords

• Shortest path problem
• Costs
• Simulation
• Roads
• Conferences
• Approximation algorithms
• Path planning
• Simultaneous Tasks
• Bottleneck Objective
• High Probability
• Scalable
• Total Cost
• Shortest Path
• Network Size
• Linear Problem
• Travel Costs
• Assignment Problem
• Deterministic Problem
• Optimal Objective Value
• Linear Assignment
• Unique Task
• Estimation Algorithm
• Feasible Solution
• Nonlinear Programming
• Planning Problem
• Optimal Solution Of Problem
• Extreme Points
• Exact Algorithm
• Cost Path
• Graph Size
• Binary Decision Variables
• Size Of Map
• Theoretical Guarantees
• Team Performance