Navigation among movable obstacles: real-time reasoning in complex environments
Navigation among movable obstacles: real-time reasoning in complex environments
复制标题
可移动障碍物之间的导航：复杂环境中的实时推理
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Kuffner
中科院分区：
文献类型：
--
作者：
Mike Stilman;J. Kuffner
在本文中，我们解决了可移动障碍物之间的导航问题（NAMO）：针对人形生物和其他灵活移动机器人导航的实际扩展。允许机器人通过移动障碍并清除路径的可用空间来重新配置环境。简单的问题已证明是p空间的。对于具有大量可移动障碍的现实情况，完整的运动计划技术在很大程度上是棘手的。本文为NAMO问题的子类提出了一个完整的计划者。我们的计划者通过州空间分解和启发式搜索利用导航结构。计划的复杂性降低为特定导航任务的难度，而不是多对象域的维度。我们展示了包含大量可移动障碍的空间的实时结果。我们还提出了一个实用框架，用于单格搜索，该框架可用于有关该领域的算法推理。
In this paper, we address the problem of navigation among movable obstacles (NAMO): a practical extension to navigation for humanoids and other dexterous mobile robots. The robot is permitted to reconfigure the environment by moving obstacles and clearing free space for a path. Simpler problems have been shown to be P-SPACE hard. For real-world scenarios with large numbers of movable obstacles, complete motion planning techniques are largely intractable. This paper presents a resolution complete planner for a subclass of NAMO problems. Our planner takes advantage of the navigational structure through state-space decomposition and heuristic search. The planning complexity is reduced to the difficulty of the specific navigation task, rather than the dimensionality of the multi-object domain. We demonstrate real-time results for spaces that contain large numbers of movable obstacles. We also present a practical framework for single-agent search that can be used in algorithmic reasoning about this domain.
DOI：
10.1115/1.1531112
发表时间：
2003-02-01
影响因子：
1.7
作者：
Thelen, DG
通讯作者：
Thelen, DG