通信範囲が限られたロボット群のためのタスク割り当て
Target assignment for robots constrained by limited communication range
通信範囲に制約のある分散ロボット群が複数の目標地点を最短時間で巡回するため、集合地点を介した集中型アルゴリズムと単一巡回セールスマン巡回路に基づく分散型アルゴリズムを提案し、性能を比較評価した。
著者: Xiaoshan Bai, Weisheng Yan, Ming Cao, Jie Huang
分類: math.OC, cs.MA, cs.RO, math.PR
原文アブストラクト
This paper investigates the task assignment problem for multiple dispersed robots constrained by limited communication range. The robots are initially randomly distributed and need to visit several target locations while minimizing the total travel time. A centralized rendezvous-based algorithm is proposed, under which all the robots first move towards a rendezvous position until communication paths are established between every pair of robots either directly or through intermediate peers, and then one robot is chosen as the leader to make a centralized task assignment for the other robots. Furthermore, we propose a decentralized algorithm based on a single-traveling-salesman tour, which does not require all the robots to be connected through communication. We investigate the variation of the quality of the assignment solutions as the level of information sharing increases and as the communication range grows, respectively. The proposed algorithms are compared with a centralized algorithm with shared global information and a decentralized greedy algorithm respectively. Monte Carlo simulation results show the satisfying performance of the proposed algorithms.
