Given a collection of red and blue mobile agents located on two grid rows, we seek to move all the blue agents to the far left side and all the red agents to the far right side, thus \textit{physically sorting} them according to color. The agents all start on the bottom row. They move simultaneously at discrete time steps and must not collide. Our goal is to design a centralized algorithm that controls the agents so as to sort them in the least number of time steps. We derive an \textbf{exact} lower bound on the amount of time any algorithm requires to sort a given initial configuration of agents. We find an instance optimal algorithm that provably matches this lower bound, attaining the best possible sorting time for any initial configuration. Surprisingly, we find that whenever the leftmost agent is red and the rightmost agent is blue, a straightforward decentralized and local sensing-based algorithm is at most $1$ time step slower than the centralized instance-optimal algorithm.
翻译:根据位于两个网格行上的红色和蓝色移动剂集,我们试图将所有蓝色剂和所有红色剂都移到最左边的左边,从而根据颜色进行物理排序。 试剂都从底线开始。 它们同时在离散的时间步骤上移动, 并且不能相撞。 我们的目标是设计一个集中的算法, 控制这些剂, 以便以最少的时间步骤来排序它们。 我们得出一个在任何算法排序给定的初始代理器配置所需的时间长度上下限 。 我们找到一种最理想的算法, 可以匹配这个更低的绑定, 达到任何初始配置的最佳排序时间。 令人惊讶的是, 我们发现, 当最左边的试剂是红色, 最右边的试剂是蓝色的, 一个直接分散的和基于本地感测的算法, 比中央试样最优的算法速度要慢一美元。