UC Santa Barbara

Consider an equal number of mobile robotic agents and distinct target locations dispersed in an environment. Each agent has a limited communication range and either: 1) knowledge of every target position or 2) a finite-range sensor capable of acquiring target positions and no a priori knowledge of target positions. In this paper we study the following target assignment problem: design a distributed algorithm with which the agents divide the targets among themselves and, simultaneously, move to their unique target. We evaluate an algorithm's performance by characterizing its worst-case asymptotic time to complete the target assignment; that is the task completion time as the number of agents (and targets) increases, and the size of the environment scales to accommodate them. We introduce the intuitive class of monotonic algorithms, and give a lower bound on its worst-case completion time. We design and analyze two algorithms within this class: the ETSP Assgmt algorithm which works under assumption 1), and the Grid Assgmt algorithm which works under either assumption 1) or 2). In “sparse environments,” where communication is infrequent, the ETSP Assgmt algorithm is within a constant factor of the optimal monotonic algorithm for worst-case initial conditions. In “dense environments,” where communication is more prevalent, the Grid Assgmt algorithm is within a constant factor of the optimal monotonic algorithm for worst-case initial conditions. In addition we characterize the performance of the Grid Assgmt algorithm for uniformly distributed targets and agents, and for the case when there are more agents than targets.