Journal
IEEE TRANSACTIONS ON ROBOTICS
Volume 36, Issue 1, Pages 125-141Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TRO.2019.2937468
Keywords
Task analysis; Robot kinematics; Uncertainty; Heuristic algorithms; Computational modeling; Global communication; Multirobot coordination; networked robots; task planning; and scheduling
Categories
Funding
- National Science Foundation [IIS-1453652, ECCS-1637889]
- KIST Institutional Program [2E28670]
- National Research Council of Science & Technology (NST) grant by theKorea government (MSIP) [CRC-15-04-KIST]
Ask authors/readers for more resources
In this article, we study multirobot task allocation problems where task costs vary. The variation may be, for example, due to the revelation of new information or other dynamic circumstances. As robots update their cost estimates, typically they will update task assignments to reflect the new information using additional communication and computation. In dynamic settings, the robots are continually repairing the optimality of the system's task assignments, which can incur substantial communication and computation. We investigate how one can reduce communication and centralized computation expense during execution by using a prior model of how costs may change and performing upfront computation of possible robot-task assignments. First, we develop an algorithm that partitions a team of robots into several independent subteams that are able to maintain global optimality by communicating entirely amongst themselves. Second, we propose a method for computing the worst-case cost suboptimality if robots persist with the initial assignment and perform no further communication and computation. Finally, we introduce an algorithm to assess whether cost changes affect the optimality of the current assignment through a succession of local communication exchanges. Experimental results show that the proposed methods are helpful in reducing the degree of centralization needed by a multirobot system (e.g., the third method gave at least 45% reduction of global communication across all scenarios studied). The methods are valuable in transitioning multirobot techniques, which have met with success in structured applications (such as factories and warehouses) to the broader, wilder world.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available