论文标题
机器人团队的环境传感选项：计算复杂性的观点
Environmental Sensing Options for Robot Teams: A Computational Complexity Perspective
论文作者
论文摘要
视觉和标量场（例如化学）传感是机器人团队在执行任务时可以使用的两个选项。我们对视觉和标量场传感的计算特征进行了首次比较，这是根据验证和设计机器人的计算复杂性来有效，可靠地执行分布式施工任务的方法。这是相对模型完成的，其中具有确定性有限状态控制器的机器人团队在基于2D网格的环境中以同步错误方式运行。我们的结果表明，对于两种类型的感应，我们的所有问题通常都是多项式时间难治性，并且在表征机器人控制器，团队和环境的参数的各种限制下仍然棘手。话虽如此，这些结果还包括我们每个问题的限制情况，在这些问题中，这些问题有效地是多项式时间可进行的。尽管存在一些差异，但我们的结果表明（至少在我们调查的这一阶段）相对于视觉和标量场传感的验证和设计问题具有大致相同的模式和类型的障碍性和类型。
Visual and scalar-field (e.g., chemical) sensing are two of the options robot teams can use to perceive their environments when performing tasks. We give the first comparison of the computational characteristic of visual and scalar-field sensing, phrased in terms of the computational complexities of verifying and designing teams of robots to efficiently and robustly perform distributed construction tasks. This is done relative a basic model in which teams of robots with deterministic finite-state controllers operate in a synchronous error-free manner in 2D grid-based environments. Our results show that for both types of sensing, all of our problems are polynomial-time intractable in general and remain intractable under a variety of restrictions on parameters characterizing robot controllers, teams, and environments. That being said, these results also include restricted situations for each of our problems in which those problems are effectively polynomial-time tractable. Though there are some differences, our results suggest that (at least in this stage of our investigation) verification and design problems relative to visual and scalar-field sensing have roughly the same patterns and types of tractability and intractability results.
