论文标题
动态分布式任务分配的下限
Lower Bounds for Dynamic Distributed Task Allocation
论文作者
论文摘要
我们研究多代理系统中分布式任务分配的问题。假设有一系列代理，一系列任务和需求向量，它指定执行每个任务所需的代理数量。代理商的目标是合作地分配给任务以满足需求向量。我们研究了需求向量随时间变化的问题的动态版本。在这里，目标是最大程度地降低切换成本，这是根据需求向量变化而更改任务的代理数量。切换成本是一个重要的指标，因为改变任务可能会产生大量的开销。 我们研究了SU，Su，Dornhaus和Lynch引入的上述问题的数学形式化，可以将其重新构成，以发现从对称差异到锤距距离的较低失真嵌入的问题。在此模型中，证明开关成本至少为2是很琐碎的。我们通过为参数的不同范围提供了3和4的第一个非平凡的下限。
We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task. The goal of the agents is to cooperatively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes over time. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead. We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch, which can be reformulated as a question of finding a low distortion embedding from symmetric difference to Hamming distance. In this model it is trivial to prove that the switching cost is at least 2. We present the first non-trivial lower bounds for the switching cost, by giving lower bounds of 3 and 4 for different ranges of the parameters.
