Nam, Changjoo Shell, Dylan A. 2024-01-19T18:04:53Z 2024-01-19T18:04:53Z 2021-09-04 2020-02 1552-3098 https://pubs.kist.re.kr/handle/201004/119038 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. English IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC SENSITIVITY-ANALYSIS ASSIGNMENT ALGORITHM Robots in the Huddle: Upfront Computation to Reduce Global Communication at Run Time in Multirobot Task Allocation Article 10.1109/TRO.2019.2937468 1 IEEE TRANSACTIONS ON ROBOTICS, v.36, no.1, pp.125 - 141 IEEE TRANSACTIONS ON ROBOTICS 36 1 125 141 scie scopus 000526526500009 2-s2.0-85072739379 Robotics Robotics Article SENSITIVITY-ANALYSIS ASSIGNMENT ALGORITHM Task analysis Robot kinematics Uncertainty Heuristic algorithms Computational modeling Global communication Multirobot coordination networked robots task planning and scheduling