Algorithmic motion planning
Algorithmic motion planning
复制标题
算法运动规划
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
M. Sharir
运动规划是机器人技术中的一个基本问题。它有多种形式，但最简单的版本如下。给定一个机器人系统B，它可能由通过各种关节、铰链和连杆相互连接的几个刚性物体组成，或者独立运动，以及一个充满障碍物的二维或三维环境V。我们假设规划系统已知障碍物的形状和位置以及B的形状。给定B的初始放置位置Z1和最终放置位置Z2，我们希望确定是否存在B从Z1到Z2的避碰运动，如果存在，则规划这样的运动。在这个简化的纯几何设定中，我们忽略诸如不完全信息、非完整约束、与传感和运动不精确性相关的控制问题、非静止障碍物、规划运动的最优性等问题。自20世纪80年代初以来，运动规划一直是机器人技术和计算几何领域的一个重点研究方向。在本章中，我们将重点关注算法运动规划，强调对该问题的理论算法分析并寻求最坏情况的渐近界，并且仅简要提及解决该问题的实用启发式方法。本章的大部分内容致力于上述运动规划的简化版本。第51.1节介绍了一般技术和下界。第51.1节考虑了对具有少量自由度的各种特定运动系统的有效解决方案。这些有效解决方案利用了与曲线和曲面排列相关的计算几何和组合几何中的各种复杂方法（第30章）。第51.3节然后简要讨论了运动规划问题的各种扩展，例如根据各种质量度量计算最优路径、计算系绳机器人的路径、纳入不确定性、移动障碍物等等。
Motion planning is a fundamental problem in robotics. It comes in a variety of forms, but the simplest version is as follows. We are given a robot system B, which may consist of several rigid objects attached to each other through various joints, hinges, and links, or moving independently, and a 2D or 3D environment V cluttered with obstacles. We assume that the shape and location of the obstacles and the shape of B are known to the planning system. Given an initial placement Z1 and a final placement Z2 of B, we wish to determine whether there exists a collisionavoiding motion of B from Z1 to Z2, and, if so, to plan such a motion. In this simplified and purely geometric setup, we ignore issues such as incomplete information, nonholonomic constraints, control issues related to inaccuracies in sensing and motion, nonstationary obstacles, optimality of the planned motion, and so on. Since the early 1980s, motion planning has been an intensive area of study in robotics and computational geometry. In this chapter we will focus on algorithmic motion planning, emphasizing theoretical algorithmic analysis of the problem and seeking worst-case asymptotic bounds, and only mention briefly practical heuristic approaches to the problem. The majority of this chapter is devoted to the simplified version of motion planning, as stated above. Section 51.1 presents general techniques and lower bounds. Section 51.2 considers efficient solutions to a variety of specific moving systems with a small number of degrees of freedom. These efficient solutions exploit various sophisticated methods in computational and combinatorial geometry related to arrangements of curves and surfaces (Chapter 30). Section 51.3 then briefly discusses various extensions of the motion planning problem such as computing optimal paths with respect to various quality measures, computing the path of a tethered robot, incorporating uncertainty, moving obstacles, and more.