2.6.1　完整性问题——规划是NP-hard

机器人的任务通常包含移动，在合理的时间内移动到指定的位置，同时尽量减少努力和麻烦。这类问题经常会用到运动规划和轨迹生成。许多其他复杂的任务都是移动的扩展，因此导航和路径规划既被视为基本的行为，也被视为设计的工具。

研究表明，规划空间的维度越高，规划过程越复杂，即xy平面上的二维导航比xyz空间中的三维导航要更容易设计和编程。路径规划的复杂性随维度和障碍数的增加呈指数增长。然而，以规划为核心的简单工作，例如，去往目标点、搜寻、跟踪、绘图等，从理论上来说也可能会花费无限的时间和/或变得非常复杂以至于不切实际。这类问题被称为NP-hard（非确定性多项式时间困难）问题。对于这类问题，很容易对给定的解进行验证，但没有一种分析方法可以在有限的、合理的时间内找到给定问题的解。这会使得规划不能完整，因而并不总是能产生一个结果。现实世界问题至少需要从三个维度进行规划，移动障碍物的存在使问题从理论上来说是困难的和棘手的。

举个例子，设想一个机器人的工作是穿过一条繁忙的街道。解决方案是注意车辆和其他行人，在交通流量较小的时候，小心地走到街道的另一边。我们大部分人亲历过这个情况，尽管看起来很简单，但是编程给机器人却不是一件容易的事情，因为几乎不存在没有交通流量的场景。简单的程序（如注意左方、注意右方并且在没有交通流量时去到街道的另一边）会直接失败，或者被卡在无限次地去尝试执行这个工作上。在这种场景下，机器人通常会持续进行编程循环，尝试找到期望的移动终点，并且持续失败直到耗尽燃料。因此，程序员会把“异常处理”这个条件放入程序来避免无限循环，即机器人会在几次尝试后停止，并报告工作无法完成。

一个好的算法应该保证能够在有解决方案的时候找到解决方案，如果没有则报告，但是完整性问题永远无法被“解决”。尽管它们可以被适当避免，或者减小到最低程度。穷举搜索是一个很明显的解决方案，但是在时间上要妥协。其他方法还有预先对空间进行切片造粒或者运用子目标和混合方法，以及当第一个路径规划器冗余时应用第二个。这些技术都是以导航为核心的，我们会在第4章讨论。

完整性也是机器人设计可能遇到的一个问题，但是这个问题是无所不在的，并且也是人类认知的标记，很多时候，我们人类也可能无法理解一个理论上确实存在的解决方案，或者当解决方案不存在时陷入逻辑难题。