解决有距离与移动限制的多机器人图覆盖问题，找最优路径。
Heterogeneous Multi-Robot Graph Coverage with Proximity and Movement Constraints
- 建模机器人间距离和移动约束下的图覆盖问题
- 提出固定参数可解算法，树结构下有近似多项式时间解法
- 适用于搜救、巡检等需协同作业的真实场景
多机器人覆盖问题是机器人学、规划与多智能体系统中的经典问题。本文研究在存在邻近约束（如机器人间最大距离、蓝机必须紧邻红机）和运动约束（如地形通行性、载重能力）下的覆盖问题。此类约束在搜救与维护任务中常见。目标是在满足约束的前提下，以最少步数完成图覆盖遍历。本文贡献包括：(i) 问题的严格形式化；(ii) 一个关于机器人构型集合F、最大节点度d与图树宽tw的固定参数可解精确算法；(iii) 当图为树时，给出一个参数为ε的多项式时间近似方案（PTAS），其误差为ε·||F||, d)，运行时间为poly(n)·h(1/ε, ||F||)；(iv) 当图是树、机器人数k=3且所有机器人需保持连通时，提出一个乘法近似误差为1+O(ε)的PTAS，误差与最大度d无关。
原文摘要 · Abstract (English)
Multi-Robot Coverage problems have been extensively studied in robotics, planning and multi-agent systems. In this work, we consider the coverage problem when there are constraints on the proximity (e.g., maximum distance between the agents, or a blue agent must be adjacent to a red agent) and the movement (e.g., terrain traversability and material load capacity) of the robots. Such constraints naturally arise in many real-world applications, e.g. in search-and-rescue and maintenance operations. Given such a setting, the goal is to compute a covering tour of the graph with a minimum number of steps, and that adheres to the proximity and movement constraints. For this problem, our contributions are four: (i) a formal formulation of the problem, (ii) an exact algorithm that is FPT in F, d and tw, the set of robot formations that encode the proximity constraints, the maximum nodes degree, and the tree-width of the graph, respectively, (iii) for the case that the graph is a tree: a PTAS approximation scheme, that given an approximation parameter epsilon, produces a tour that is within a epsilon times error(||F||, d) of the optimal one, and the computation runs in time poly(n) times h(1/epsilon,||F||). (iv) for the case that the graph is a tree, with $k=3$ robots, and the constraint is that all agents are connected: a PTAS scheme with multiplicative approximation error of 1+O(epsilon), independent of the maximal degree d.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。