利用一個新的搜尋空間，規劃圖可以提高經典的規劃方法的表達能力和複雜性的問題。
介紹
人工智慧規劃的經典方法是利用狀態空間和規劃空間來尋找解決規劃問題的方案。
在狀態空間搜尋中，初始世界狀態透過應用適當的操作進行多次轉換，直到找到一個解決方案以達到目標或搜尋演算法終止並返回失敗。我們可以使用諸如BFS、DFS、Dijkstra、A*等搜尋演算法。
得到的解決方案是一系列操作（action），當應用這些操作時，會在一個或多個步驟中將初始世界狀態轉換為目標狀態。
另一個搜尋空間是規劃空間，我們將規劃作為節點，試圖解決開放（未解決）目標和缺陷。
這種方法本身就相當複雜，我們這裡不討論細節，如果你有興趣瞭解更多，可以閱讀以下文章：
https：//medium。com/swlh/plan-space-search-2d877b4ab231
改善空間大小
在《
Automated Planning： Theory and Practice
》一書中，Malik、Dana和Paolo提到，由於表現力和複雜性的原因，經典方法的研究停滯不前，規劃圖-一個新的搜尋空間，允許改進搜尋空間的大小，從而為解決更復雜的規劃問題開闢了一條途徑。
我們將在下面的小節中詳細介紹，以瞭解它是如何改進經典規劃方法中發現的問題的。
碼頭工人機器人規劃領域
對於我們的示例，我們將使用簡化的Dock Worker Robots（DWR）域和問題，這在AI規劃教程中經常使用。
在這個領域有兩個機器人，robr和robq，兩個容器conta和contb，以及兩個位置loc1和loc2。
有三種可能的操作：
load(location, container, robot)
：將容器裝載到機器人上
move(location, location)
：從一個位置移動到另一個位置
unload(location, container, robot)
：從機器人上解除安裝容器
操作的前提條件和效果的詳細資訊可以在下面的pddl檔案中看到。
我們還有五個謂詞來表示狀態：
adjacent(loc1, loc2)
-這是關於位置的靜態資訊
atl(robot, location)
）-描述機器人的位置
loaded(robot, container)
-機器人是否裝載以及機器人上的容器
unloaded(robot)
-機器人已解除安裝
in(container, location)
-描述容器的位置
我們使用PDDL（planningdomaindefinitionlanguage）來表示規劃域和規劃問題。下面是我們感興趣的領域的pddl檔案。
；； Specification in PDDL1 of the DWR domain（define （domain dock-worker-robot-simple） （：requirements ：strips ：typing ） （：types location ； there are several connected locations in the harbor robot ； holds at most 1 container， only 1 robot per location container） （：predicates （adjacent ？l1 ？l2 - location） ； location ？l1 is adjacent ot ？l2 （atl ？r - robot ？l - location） ； robot ？r is at location ？l （loaded ？r - robot ？c - container ） ； robot ？r is loaded with container ？c （unloaded ？r - robot） ； robot ？r is empty （in ？c - container ？l - location） ； container ？c is within location ？l ）；； there are 3 operators in this domain：；； moves a robot between two adjacent locations （：action move ：parameters （？r - robot ？from ？to - location） ：precondition （and （adjacent ？from ？to） （atl ？r ？from） ） ：effect （and （atl ？r ？to） （not （atl ？r ？from）） ））；； loads an empty robot with a container held by a nearby crane （：action load ：parameters （？l - location ？c - container ？r - robot） ：precondition （and （atl ？r ？l） （in ？c ？l） （unloaded ？r）） ：effect （and （loaded ？r ？c） （not （in ？c ？l）） （not （unloaded ？r）） ））；； unloads a robot holding a container with a nearby crane （：action unload ：parameters （？l - location ？c - container ？r - robot） ：precondition （and （atl ？r ？l） （loaded ？r ？c） ） ：effect （and （unloaded ？r） （in ？c ？l） （not （loaded ？r ？c）） ）） ）
現在開始深入研究規劃圖及其規劃器。
規劃圖
規劃圖是基於可達性分析的思想，即從一組初始狀態計算一組狀態是否可達的過程。
我們一步一步地透過一個例子來理解這個概念。首先，這是初始狀態：
我們使用謂詞來表示世界狀態（為了簡單起見，省略了相鄰的謂詞）：
in（conta， loc1）
in（contb， loc2）
atl（robr， loc1）
atl（robq， loc2）
unloaded（robr）
unloaded（robq）
我們想知道這個狀態是否可以到達：
我們沒有展示圖片中的機器人，因為不關心它們的位置，我們只對容器的位置感興趣。是這樣表示的：
in（contb， loc1）
in（conta， loc2）
可達樹
現在，最簡單的方法是使用可達性樹。我們從初始狀態（根節點）開始，搜尋狀態的適用操作（邊），然後生成預測狀態（子節點），並對所有子節點重複該過程，直到達到指定的深度。
這是深度為1的可達樹。
這是深度為2的可達樹。
可以看到這並不能很好地擴充套件，當我們增加深度時，節點的數量會爆炸。而且我們還沒有找到這個深度的目標，需要進一步擴大它。
可達圖
我相信你會認為，我們可以用一個圖來改進它，因為有些節點確實是重複的。這是depth=2的圖形版本。
雖然略有改進，但要達到目標（紅色節點），需要depth=6，如下所示：
很可怕，不是嗎？它的規模確實很大，因為當我們增加深度時，複雜程度會增加，如果我們想解決更復雜的問題，這在某些時候變得不切實際。
規劃圖的可達性
規劃圖的思想是帶鬆弛的可達圖。在每一個深度（或者稱為層次）它不使用單個狀態，而是使用狀態的並集，因此我們可以認為每個層次只有一個節點。
與可達圖不同，在可達圖中，我們透過應用可應用的操作來生成節點，所有的操作都用於生成狀態的並集。
另一個區別是在可達圖中，狀態是一組一致的命題，而在規劃圖中，狀態不是。例如，在圖中的前提條件1中，robr的位置可以同時在loc1和loc2中。
同樣，這些操作並不總是相容的，它們可能會抵消彼此的效果。
在規劃圖中，為了跟蹤這些命題的不一致性和不相容的操作，我們使用了所謂的互斥（mutex）。在每個層面上，我們都有：
一組命題互斥
一組操作互斥
建立規劃圖
現在，讓我們看看如何一步一步地構建規劃圖。最初，我們有級別0，其中只有前提條件0，它等於初始狀態。
接下來，我們構建下一個級別，級別1。從一組操作開始：
這個等式的意思是A1是一組操作，即：
當前狀態滿足前提條件
在命題互斥物件中沒有前提條件
下一步是構建一組命題：
我們採用先前構建的A1，並將所有操作的積極影響結合起來。
接下來的兩個步驟是構建互斥體，從A1的互斥體開始：
A1中的兩個操作是互斥物件，如果它們是相互依賴的（它們會抵消彼此的影響），或者它們的前置條件在P0的互斥物件中。如果有一個負面影響會抵消一個正面影響的前提條件，那麼這兩個行為是相互依賴的：
最後一步是為P1構建互斥：
P1中的一對命題是互斥的，如果：
A1中所有具有積極效果的一對操作中，這對操作是互斥的
A1中沒有一個操作可以同時產生這兩種效果
現在，這是相當複雜的，但是這個步驟可以簡單地重複到下一個級別。這是深度為3的規劃圖的結果。
此時，我們可以看到，與可達樹和可達圖相比，規劃圖的構建要複雜得多，但正如你所看到的，它將在搜尋時間上更快，並且在大小上更小，更重要的是更易於我們分析或除錯。
在構建規劃圖時，另一個重要的一點是，經過一些深度之後，它將是固定的，這意味著操作集和命題集不會再發生任何變化。
我們的目標達到了3級，我們可以看到兩個命題：
in（contb， loc1）
in（conta， loc2）
在P3（見上圖）。
搜尋規劃圖
現在我們有了規劃圖-資料結構，我們可以使用搜索演算法來找到規劃問題的解決方案。
這種方法中的規劃不是一系列操作，而是操作集合。一個級別的集合中的所有操作都可以獨立執行，這意味著它們之間沒有順序約束。
在本例中，搜尋從P3向後執行到P0，遞迴地求解目標中的所有命題。在解決它們之後，我們遞迴地使用操作的前提條件作為子目標，直到達到P0。
我們跳過的一件重要的事情是，在每一個級別上，我們都有不做任何事情的虛擬操作—它們的前提條件和效果是相同的。這使得演算法能夠順利地處理那些在較低層次上已經滿足的命題。
例如，我們的解決方案規劃是：
Level 1： {load（loc2， contb， robq）， load（loc1， conta， robr）}
Level 2： {move（robq， loc2， loc1）， move（robr， loc1， loc2）}
Level 3： {unload（loc1， contb， robq）， unload（loc2， conta， robr）}
結論
我們希望現在能夠理解如何透過使用規劃圖方法來提高經典規劃方法的複雜性。與可達樹和可達圖相比，規劃圖的構建更加複雜，但是它節省了我們搜尋解決方案的大小和時間，如分步示例所示。
感謝閱讀！
