8.1 介绍
(Introduction)
蓬勃发展的机器人领域激发了人们对计算几何中一系列问题的探索，这些问题统称为"运动规划(Motion Planning)"问题，或更具体地说，"运动规划算法(algorithmic motion planning)"问题的探索。 通常，学者从现实应用中抽离出细节，从而构建出数学上更简洁的问题描述。如果抽象过程足够巧妙，那么理论探索就具有实际意义。令人欣喜的是，运动规划正是如此， 它不仅适用于传统机器人技术，还广泛应用于数控机床的刀具路径规划、芯片布线、地理信息系统(Geographic Information Systems, GIS)中的路径规划，以及计算机图形学中的虚拟导航(virtual navigation)。
8.1.1. 问题描述 (Problem Specification)
本章探讨的主要范式假设一个固定的环境，其中存在不可穿透的障碍物，通常在二维和三维空间中分别表示为多边形和多面体。 在这个环境中存在一个"机器人" \(R\)，这是一个具有预先设定的几何特征的可移动物体: 它可以是一个点、一条线段、一个凸多边形、一个铰接物体等等。 机器人位于某个初始位置 \(s\)，称之为起点。我们的任务是规划其运动轨迹，使其移动到某个指定的最终位置 \(t\)(终点)， 在整个运动过程中，要避免机器人与所有障碍物发生碰撞。当机器人上的一个点与障碍物的点重合时，就会发生碰撞。请注意，与障碍物边界的滑动接触不构成碰撞。 一条避免碰撞的路径被称为自由路径(free path)。通常，允许的运动类型会受到一些限制。
在这类一般性问题中，我们考虑三个具体问题，每个问题所需的信息都比前一个问题多:
- 判定问题: 是否存在一条从 \(s\) 到 \(t\) 的自由路径?
- 路径构造: 找到一条从 \(s\) 到 \(t\) 的自由路径。
- 最短路径: 找到一条从 \(s\) 到 \(t\) 的最短自由路径。
问题(3)的解能解决(2)，而(2)的解又能解决(1)。因此判定问题是最简单的，但在实践中通常只需要找到一条路径即可，而这实际解决了(2)。 但是，我们将在8.6 节中看到一个例子，其中判定问题比实际找到一条路径要简单得多。
路径最短的含义并不总是明确的。如果机器人是一个圆盘，那它的含义是明确的。但假设机器人是一条允许旋转的线段(8.5 节)。 那么，"最短"就有了好几种定义，选择哪一种定义，找到最短路径都极其困难。
8.1.2. 概要(Outline)
我们将仅针对最简单的情况考虑最短路径问题，即当机器人是一个点的情况(8.2 节)。 接下来，我们将探讨两个较为常见的运动规划问题: 平移凸多边形(包括部分实现)(8.4 节)和移动梯子"ladder" (一条线段)(8.5 节)。 之后，我们将研究如何移动铰接机器人"手臂"的问题(8.6 节)。 该节包含用于操作 \(n\) 连杆机械臂使末段到达指定位置的代码。 最后，我们将探讨分离互锁拼图块(separating interlocking puzzle pieces)这一引人入胜的问题(8.7 节)。