Robots in the huddle: Upfront computation to reduce global communication at run-time in multi-robot task allocation

Robots in the huddle: Upfront computation to reduce global communication at run-time in multi-robot task allocation
남창주Dylan A. Shell
Multi-robot coordination; Networked robots; Task planning and scheduling
Issue Date
IEEE transactions on robotics
VOL 36, NO 1-141
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.
Appears in Collections:
KIST Publication > Article
Files in This Item:
There are no files associated with this item.
RIS (EndNote)
XLS (Excel)


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.