Task allocation is an important problem for robot swarms to solve, allowing agents to reduce task completion time by performing tasks in a distributed fashion. Existing task allocation algorithms often assume prior knowledge of task location and demand or fail to consider the effects of the geometric distribution of tasks on the completion time and communication cost of the algorithms. In this paper, we examine an environment where agents must explore and discover tasks with positive demand and successfully assign themselves to complete all such tasks. We propose two new task allocation algorithms for initially unknown environments -- one based on N-site selection and the other on virtual pheromones. We analyze each algorithm separately and also evaluate the effectiveness of the two algorithms in dense vs. sparse task distributions. Compared to the Levy walk, which has been theorized to be optimal for foraging, our virtual pheromone inspired algorithm is much faster in sparse to medium task densities but is communication and agent intensive. Our site selection inspired algorithm also outperforms Levy walk in sparse task densities and is a less resource-intensive option than our virtual pheromone algorithm for this case. Because the performance of both algorithms relative to random walk is dependent on task density, our results shed light on how task density is important in choosing a task allocation algorithm in initially unknown environments.
翻译:任务分配是机器人群要解决的一个重要问题, 使代理商能够通过以分布式方式执行任务来减少任务完成时间。 现有的任务分配算法通常会事先掌握任务位置和需求的知识, 或者没有考虑任务几何分布对任务完成时间和运算法通信成本的影响。 在本文中, 我们检查一个代理商必须探索和发现任务并具有积极需求并成功指定自己完成所有这些任务的环境。 我们为最初未知的环境建议了两种新的任务分配算法 -- -- 一种基于N站点选择,另一种基于虚拟花生素。 我们分别分析每一种算法, 并且还评估两种计算法在密集度和稀少任务分布中的有效性。 与Levy 行走法相比, 我们的虚拟花生运算法在最初的密度上是如何选择一个未知的随机任务分配结果的。 在不为人所了解的行情密度上, 我们的行进算法工作在初始的进度上是如何选择一个不为常态的飞行环境的。