Multiple Robot Point Set Coverage under Geometric Constraints
We focus on the assignment of discrete points among K
robots and determining the order in which the points should be
processed by the robots, in the presence of geometric and kinematic
constraints between the robots. This is a path planning problem that arises
as a subproblem in the decoupled approach to solving the motion planning problem
of covering a point set by a multiple robot system in minimum time.
More concretely, our work is motivated by an industrial microelectronics
manufacturing system with two robots, with square footprints, that are
constrained to translate along a line while satisfying proximity and
collision avoidance constraints (see the figure on right). The N points lie on a planar base
plate that can translate along the plane normal to the direction of
motion of the robots. The geometric constraints on the motions of the
two robots lead to constraints on points that can be processed
simultaneously. We use a two step approach to solve the path planning problem: (1) Splitting Problem: Assign the points to the K robots subject to geometric constraints, such that the total processing time is minimized. (2) Ordering Problem: Find an order of processing the split points by formulating and solving a multi-dimensional Traveling Salesman Problem (TSP) in the K-tuple space with an appropriately defined metric to minimize the total travel cost. We show that for K = 2, the splitting problem can be converted to a maximum cardinality matching problem on a graph and solved optimally in polynomial time. The matching algorithm takes O(N^3) time in general and is too slow for large datasets. Therefore, we also provide a greedy algorithm for the splitting problem that takes O(N log(N)) time. We provide computational results comparing the two approaches and show that the greedy algorithm is very close to the optimal solution for typical industrial datasets. We also provide computational results for the ordering problem and propose local search based heuristics to improve the TSP tour. Further, we give computational results showing the overall performance gain obtained (over a single robot system) by using our algorithm. Finally, we extend our approach to a K-robot system and give computational results for K = 4.
-
N.Chakraborty, S. Akella, and J.T. Wen, ``Coverage of a Planar Point Set
with Multiple Robots subject to Geometric Constraints,'' Conditionally accepted (March 2008), IEEE
Transactions on Automation Sciences and Engineering.
-
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.
- N. Chakraborty, S. Akella, and J. T. Wen,
``
Coverage of a Planar Point Set with Multiple Constrained Robots,''
IEEE Conference on Automation Science and Engineering , pp 899-904, Scottsdale, AZ, September
2007.
Multi-robot task allocation for grouped tasks
-
L. Luo, N. Chakraborty, and K. Sycara, `` A Distributed Algorithm for Constrained Multi-Robot Task Assignment
for Grouped Tasks '', Under Submission.
- L. Luo, N.Chakraborty, and K. Sycara, `` A Distributed Algorithm Design for Multi-Robot Task Assignment with Deadlines for Tasks '', 2013 IEEE International Conference on Robotics and Automation (IEEE ICRA 2013) , Karlsruhe, Germany, May 2013.
-
L. Luo, N. Chakraborty, and K. Sycara, `` Multi-robot Assignment Algorithms for Tasks with Set Precedence Constraints'', 2011 IEEE International
Conference on Robotics and Automation , Shanghai, China, May 2011.
In this paper, we present provably-good distributed task allocation (assignment) algorithms for a heterogeneous multi-robot system where the tasks form disjoint groups and there are constraints on the number of tasks a robot can do (both within the overall mission and within each task group). Our problem is motivated by applications where multiple robots with heterogeneous capabilities have to work together to accomplish tasks. Thus, for our purposes, a task group is a {\em compound task} composed of more than one atomic tasks where one robot is required for each atomic task. Since robots have limited battery life, we assume that the number of (atomic) tasks that a robot can do within a mission has an upper bound. Futhermore, each robot has a constraint on the number of tasks it can do from each group (this models the fact that multiple robots may be needed to simultaneously perform the atomic tasks that make up the compound task). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize the total payoff (or minimize the total cost) of all the robots. In general, existing (centralized or distributed) algorithms for task allocation either assume that (atomic) tasks are independent, or do not provide performance guarantee for the situation where task constraints exist. We show that our problem can be solved in polynomial time by a centralized algorithm by reducing it to a minimum cost network flow problem. We then present a decentralized algorithm (that extends the auction algorithm of Bertsekas for linear assignment problems~\cite{Bertsekas88}) to provide an almost optimal solution. We prove that our solution is within a factor of $O(n_t\epsilon)$ of the optimal solution, where $n_t$ is the total number of tasks and $\epsilon$ is a parameter that we choose (the guarantees are the same as that of the original auction algorithm for unconstrained tasks). The decentralized algorithm assumes a shared memory model of computation that may be unrealistic for many multi-robot deployments. Therefore, we show that by using a maximum consensus algorithm along with our algorithm, we can design a totally distributed algorithm for task allocation with group constraints. The key aspect of our distributed algorithm is that the overall objective is (nearly) maximized by {\em each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task)}. Our algorithm is polynomial in the number of tasks as well as the number of robots.
Online multi-robot task allocation
-
We study an online task assignment problem for multi-robot systems
where robots can do multiple tasks during their mission and the tasks
arrive dynamically in groups. Each robot can do at most one task from
a group and the total number of tasks a robot can do is bounded by its
limited battery life. There is a payoff for assigning each robot to a
task and the objective is to maximize the total payoff. A special
case, where each group has one task and each robot can do one task is
the online maximum weighted bipartite matching problem (MWBMP). For
online MWBMP, it is known that, under some assumptions on the payoffs, a
greedy algorithm has a {\em competitive ratio} of $\frac{1}{3}$. Our key result
is to prove that for the general problem, under the same assumptions
on the payoff as in MWBMP and an assumption on the number of tasks
arising in each group, a repeated auction algorithm, where each group
of tasks is (near) optimally allocated to the available group of
robots has a guaranteed competitive ratio. We also prove that (a) without
the assumptions on the payoffs, it is impossible to design an
algorithm with any performance guarantee and (b) without the
assumption on the task profile, the algorithms that can guarantee a
feasible allocation (if one exists) have arbitrarily bad performance in
the worst case. Additionally, we present simulation results depicting
the average case performance of the repeated greedy auction algorithm.
-
L. Luo, N.Chakraborty, and K. Sycara, `` Distributed Algorithm Design for Multi-Robot Task Assignment
with Deadlines for Tasks '', 2013 IEEE International Conference on Robotics
and Automation (IEEE ICRA 2013) , Karlsruhe, Germany, May 2013.
Back to top.
Back to Nilanjan's research interests