Putting it together: the computational complexity of designing robot controllers and environments for distributed construction
Putting it together: the computational complexity of designing robot controllers and environments for distributed construction
复制标题
放在一起：设计机器人控制器和分布式构建环境的计算复杂性
DOI：
10.1007/s11721-017-0152-7
复制
发表时间：
2017
影响因子：
2.6
通讯作者：
A. Vardy
中科院分区：
文献类型：
--
作者：
T. Wareham;A. Vardy
通过自主机器人团队的协调努力创建目标结构（可能由其环境中的特定功能辅助）是分布式机器人中非常重要的问题。分布式机器人施工团队的许多特定实例都是手动开发的。一个重要的问题是，自动化控制器设计算法是否既可以快速生成机器人控制器，又可以保证使用这些控制器的团队能够正确地构建任意请求的目标结构;这项任务还可能涉及指定环境中可以帮助构建过程的功能。在本文中，我们给出了第一个计算和参数化的复杂性分析与机器人控制器的设计和环境创建目标结构的几个问题。这些问题使用一个简单的有限状态的机器人控制器模型，在一个基于网格的环境中，以非连续的确定性的方式移动。我们的目标是建立是否存在算法，都是快速和正确的所有输入，如果没有，在哪些限制下，这样的算法是可能的。我们证明，这些问题都是有效地解决一般，并保持这样的控制器，环境和目标结构的一些合理的限制。我们还给出了第一个限制相对于这些问题是有效解决的，并讨论了理论上的可解性和不可解性的结果，相对于这里研究的问题意味着现实世界的建设使用机器人团队。
Creating target structures through the coordinated efforts of teams of autonomous robots (possibly aided by specific features in their environments) is a very important problem in distributed robotics. Many specific instances of distributed robotic construction teams have been developed manually. An important issue is whether automated controller design algorithms can both quickly produce robot controllers and guarantee that teams using these controllers will build arbitrary requested target structures correctly; this task may also involve specifying features in the environment that can aid the construction process. In this paper, we give the first computational and parameterized complexity analyses of several problems associated with the design of robot controllers and environments for creating target structures. These problems use a simple finite-state robot controller model that moves in a non-continuous deterministic manner in a grid-based environment. Our goal is to establish whether algorithms exist that are both fast and correct for all inputs and if not, under which restrictions such algorithms are possible. We prove that none of these problems are efficiently solvable in general and remain so under a number of plausible restrictions on controllers, environments, and target structures. We also give the first restrictions relative to which these problems are efficiently solvable and discuss what theoretical solvability and unsolvability results derived relative to the problems examined here mean for real-world construction using robot teams.