2.6.1　完整性問題——規劃是NP-hard

機器人的任務通常包含移動，在合理的時間內移動到指定的位置，同時盡量減少努力和麻煩。這類問題經常會用到運動規劃和軌跡生成。許多其他復雜的任務都是移動的擴展，因此導航和路徑規劃既被視為基本的行為，也被視為設計的工具。

研究表明，規劃空間的維度越高，規劃過程越復雜，即xy平面上的二維導航比xyz空間中的三維導航要更容易設計和編程。路徑規劃的復雜性隨維度和障礙數的增加呈指數增長。然而，以規劃為核心的簡單工作，例如，去往目標點、搜尋、跟蹤、繪圖等，從理論上來說也可能會花費無限的時間和/或變得非常復雜以至于不切實際。這類問題被稱為NP-hard（非確定性多項式時間困難）問題。對于這類問題，很容易對給定的解進行驗證，但沒有一種分析方法可以在有限的、合理的時間內找到給定問題的解。這會使得規劃不能完整，因而并不總是能產生一個結果。現實世界問題至少需要從三個維度進行規劃，移動障礙物的存在使問題從理論上來說是困難的和棘手的。

舉個例子，設想一個機器人的工作是穿過一條繁忙的街道。解決方案是注意車輛和其他行人，在交通流量較小的時候，小心地走到街道的另一邊。我們大部分人親歷過這個情況，盡管看起來很簡單，但是編程給機器人卻不是一件容易的事情，因為幾乎不存在沒有交通流量的場景。簡單的程序（如注意左方、注意右方并且在沒有交通流量時去到街道的另一邊）會直接失敗，或者被卡在無限次地去嘗試執行這個工作上。在這種場景下，機器人通常會持續進行編程循環，嘗試找到期望的移動終點，并且持續失敗直到耗盡燃料。因此，程序員會把“異常處理”這個條件放入程序來避免無限循環，即機器人會在幾次嘗試后停止，并報告工作無法完成。

一個好的算法應該保證能夠在有解決方案的時候找到解決方案，如果沒有則報告，但是完整性問題永遠無法被“解決”。盡管它們可以被適當避免，或者減小到最低程度。窮舉搜索是一個很明顯的解決方案，但是在時間上要妥協。其他方法還有預先對空間進行切片造粒或者運用子目標和混合方法，以及當第一個路徑規劃器冗余時應用第二個。這些技術都是以導航為核心的，我們會在第4章討論。

完整性也是機器人設計可能遇到的一個問題，但是這個問題是無所不在的，并且也是人類認知的標記，很多時候，我們人類也可能無法理解一個理論上確實存在的解決方案，或者當解決方案不存在時陷入邏輯難題。