Planning High-quality Paths and Corridors Amidst Obstacles
Planning High-quality Paths and Corridors Amidst Obstacles
复制标题
DOI：
10.1177/0278364908097213
复制
发表时间：
2008-11
期刊：
影响因子：
--
通讯作者：
R. Wein;J. V. D. Berg;D. Halperin
中科院分区：
文献类型：
--
作者：
R. Wein;J. V. D. Berg;D. Halperin
运动规划问题是机器人和游戏设计等领域的核心问题，涉及到在障碍物中移动实体的无碰撞路径的计算。本文主要研究高质量路径的规划问题。高质量的路径应该具有一些理想的属性：它应该是短的，避免长弯路，同时它应该与障碍物保持安全距离，即它应该有间隙。我们提出了一种路径质量度量，它在最小化路径长度和最大化路径间隙的上述标准之间取得平衡。根据测量结果分析了最优路径的性质，并设计了一种逼近算法来计算平面上多边形障碍物中的近最优路径。我们还将我们的质量措施应用于走廊。与其为移动的实体规划一维的运动路径，不如让实体在走廊中移动更方便，在走廊中，精确的运动路径由局部规划器确定。我们证明了规划一个最优走廊等同于规划一个有界间隙的最优路径。
The motion-planning problem, involving the computation of a collision-free path for a moving entity amidst obstacles, is a central problem in fields such robotics and game design. In this paper we study the problem of planning high-quality paths. A high-quality path should have some desirable properties: it should be short, avoiding long detours, and at the same time it should stay at a safe distance from the obstacles, namely it should have clearance. We suggest a quality measure for paths, which balances between the above criteria of minimizing the path length while maximizing its clearance. We analyze the properties of optimal paths according to our measure, and devise an approximation algorithm to compute near-optimal paths amidst polygonal obstacles in the plane. We also apply our quality measure to corridors. Instead of planning a one-dimensional motion path for a moving entity, it is often more convenient to let the entity move in a corridor, where the exact motion path is determined by a local planner. We show that planning an optimal corridor is equivalent to planning an optimal path with bounded clearance.