让机器人在无标识图中按颜色分布,实现精准定位的协同部署新方法。
Location-Aware Dispersion on Anonymous Graphs
- 基于颜色约束设计分布式算法,确保同色节点仅分配一个机器人。
- 提出确定性算法,时间与内存消耗均有理论保证,适用于任意规模网络。
- 揭示该问题比经典分散问题更难,首次给出不可行性结论与下界证明。
经典的分散问题(DISPERSION)是分布式机器人中的基础协调问题:一组移动机器人需重新部署,使每个机器人占据图中唯一节点。本文提出位置感知分散(LOCATION-AWARE DISPERSION),其要求机器人只能部署在与其自身颜色相同的节点上,且每类颜色的节点至多被一个机器人占据。给定一个包含 $n = |V|$ 个节点的匿名、连通、无向图 $G = (V, E)$,节点用 $t eq n$ 种颜色标记,共有 $k eq n$ 个机器人,每个机器人具有对应颜色。初始位置任意,目标是使每个机器人占据一个同色且唯一的节点。当 $|C|=1$ 时,问题退化为经典分散问题。本文设计了多个确定性算法,在不预先知道 $k,n$ 情况下仍能保证时间和内存开销的上界。同时,给出了该问题的不可行性结果与确定性算法的下界,表明其相比传统分散更具挑战性。这些成果首次系统确立了在匿名网络中求解该问题的可行性,并揭示了效率瓶颈。
原文摘要 · Abstract (English)
The well-studied DISPERSION problem is a fundamental coordination problem in distributed robotics, where a set of mobile robots must relocate so that each occupies a distinct node of a network. DISPERSION assumes that a robot can settle at any node as long as no other robot settles on that node. In this work, we introduce LOCATION-AWARE DISPERSION, a novel generalization of DISPERSION that incorporates location awareness: Let $G = (V, E)$ be an anonymous, connected, undirected graph with $n = |V|$ nodes, each labeled with a color $\sf{col}(v) \in C = \{c_1, \dots, c_t\}, t\leq n$. A set $R = \{r_1, \dots, r_k\}$ of $k \leq n$ mobile robots is given, where each robot $r_i$ has an associated color $\mathsf{col}(r_i) \in C$. Initially placed arbitrarily on the graph, the goal is to relocate the robots so that each occupies a distinct node of the same color. When $|C|=1$, LOCATION-AWARE DISPERSION reduces to DISPERSION. There is a solution to DISPERSION in graphs with any $k\leq n$ without knowing $k,n$. Like DISPERSION, the goal is to solve LOCATION-AWARE DISPERSION minimizing both time and memory requirement at each agent. We develop several deterministic algorithms with guaranteed bounds on both time and memory requirement. We also give an impossibility and a lower bound for any deterministic algorithm for LOCATION-AWARE DISPERSION. To the best of our knowledge, the presented results collectively establish the algorithmic feasibility of LOCATION-AWARE DISPERSION in anonymous networks and also highlight the challenges on getting an efficient solution compared to the solutions for DISPERSION.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。