Motion planning in the presence of movable obstacles
Motion planning in the presence of movable obstacles
复制标题
存在可移动障碍物时的运动规划
DOI：
10.1007/bf01530890
复制
发表时间：
1988
影响因子：
1.2
通讯作者：
G. Wilfong
中科院分区：
文献类型：
--
作者：
G. Wilfong
大多数运动规划算法已经处理了静态工作空间中的运动，或者最近处理了以已知方式改变的工作空间中的运动。我们考虑在可变工作空间中寻找无碰撞运动的问题。也就是说，我们希望找到一个物体的运动，允许该物体移动一些障碍物。在这样的工作空间中，可移动障碍物的最终位置可以是或可以不是目标的一部分。在障碍物的最终位置被指定的情况下，一般的问题被证明是PSPACE硬。在障碍物的最终位置未指定的情况下，运动规划问题被证明是NP难的。算法运行在O（n3）时间的情况下，只有一个可移动的障碍物在多边形环境中的n个角落和物体被移动和障碍物是凸多边形的常数复杂度。
Most motion planning algorithms have dealt with motion in a static workspace, or more recently, with motion in a workspace that changes in a known manner. We consider the problem of finding collision-free motions in a changeable workspace. That is, we wish to find a motion for an object where the object is permitted to move some of the obstacles. In such a workspace, the final positions of the movable obstacles may or may not be part of the goal. In the case where the final positions of the obstacles are specified, the general problem is shown to be PSPACE-hard. In the case where the final positions of the obstacles are unspecified, the motion planning problem is shown to be NP-hard. Algorithms that run inO(n3) time are presented for the case where there is only one movable obstacle in a polygonal environment withn corners and the object to be moved and the obstacle are convex polygons of constant complexity.