...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>The Journal of Artificial Intelligence Research >The Parameterized Complexity of Motion Planning for Snake-Like Robots
【24h】

The Parameterized Complexity of Motion Planning for Snake-Like Robots

机译：蛇形机器人的运动规划的参数化复杂性

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial position and a final position in an environment (modeled by a graph), our objective is to determine whether the robot can reach the final position from the initial position without intersecting itself. Naturally, this problem models a wide-variety of scenarios, ranging from the transportation of linked wagons towed by a locomotor at an airport or a supermarket to the movement of a group of agents that travel in an “ant-like” fashion and the construction of trains in amusement parks. Unfortunately, already on grid graphs, this problem is PSPACE-complete. Nevertheless, we prove that even on general graphs, the problem is solvable in FPT time with respect to the size of the snake. In particular, this shows that the problem is fixed-parameter tractable (FPT). Towards this, we show how to employ color-coding to sparsify the configuration graph of the problem to reduce its size significantly. We believe that our approach will find other applications in motion planning. Additionally, we show that the problem is unlikely to admit a polynomial kernel even on grid graphs, but it admits a treewidth-reduction procedure. To the best of our knowledge, the study of the parameterized complexity of motion planning problems (where the intermediate configurations of the motion are of importance) has so far been largely overlooked. Thus, our work is pioneering in this regard.
机译：我们研究了经典视频游戏蛇的变种的参数化复杂性，以模拟运动规划的真实问题。给定具有初始位置的蛇状机器人和环境中的最终位置（由图形建模），我们的目的是确定机器人是否可以从初始位置到达最终位置而不相交。当然，这个问题模拟了各种各样的情景，从机场或超市拖曳的环绕货车的运输到一群代理商，以“蚂蚁类似”时尚和建筑物的运动娱乐公园的火车。不幸的是，已经在网格图上，这个问题是PSPace完整的。尽管如此，我们证明即使在一般图表中，问题也可以在FPT时间内得到蛇的尺寸来解决。特别地，这表明问题是固定参数易易解（FPT）。为此，我们展示了如何使用颜色编码来缩小问题的配置图以显着降低其尺寸。我们认为，我们的方法将在运动规划中找到其他应用程序。此外，我们表明，即使在网格图中，问题不太可能承认多项式内核，但它承认减少树木宽度过程。据我们所知，到目前为止，迄今为止，对运动规划问题的参数化复杂性的研究（其中运动的中间配置）在很大程度上被忽略了。因此，我们的作品在这方面是开创性的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号