作者 | Debby Nirwan

編譯 | VK
來源 | Towards Data Science

利用一個新的搜索空間，規(guī)劃圖可以提高經(jīng)典的規(guī)劃方法的表達(dá)能力和復(fù)雜性的問題。

介紹

人工智能規(guī)劃的經(jīng)典方法是利用狀態(tài)空間和規(guī)劃空間來尋找解決規(guī)劃問題的方案。

在狀態(tài)空間搜索中，初始世界狀態(tài)通過應(yīng)用適當(dāng)?shù)牟僮鬟M(jìn)行多次轉(zhuǎn)換，直到找到一個解決方案以達(dá)到目標(biāo)或搜索算法終止并返回失敗。我們可以使用諸如BFS、DFS、Dijkstra、A*等搜索算法。

得到的解決方案是一系列操作(action)，當(dāng)應(yīng)用這些操作時，會在一個或多個步驟中將初始世界狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)。

另一個搜索空間是規(guī)劃空間，我們將規(guī)劃作為我們的節(jié)點(diǎn)，試圖解決開放（未解決）目標(biāo)和缺陷。

這種方法本身就相當(dāng)復(fù)雜，我們這里不討論細(xì)節(jié)，如果你有興趣了解更多，可以閱讀以下文章：

https://medium.com/swlh/plan-space-search-2d877b4ab231

改善空間大小

在《Automated Planning: Theory and Practice》一書中，Malik、Dana和Paolo提到，由于表現(xiàn)力和復(fù)雜性的原因，經(jīng)典方法的研究停滯不前，規(guī)劃圖-一個新的搜索空間，允許改進(jìn)搜索空間的大小，從而為解決更復(fù)雜的規(guī)劃問題開辟了一條途徑。

我們將在下面的小節(jié)中詳細(xì)介紹，以了解它是如何改進(jìn)經(jīng)典規(guī)劃方法中發(fā)現(xiàn)的問題的。

碼頭工人機(jī)器人規(guī)劃領(lǐng)域

對于我們的示例，我們將使用簡化的Dock Worker Robots（DWR）域和問題，這在AI規(guī)劃教程中經(jīng)常使用。

在這個領(lǐng)域，我們有兩個機(jī)器人，robr和robq，兩個容器conta和contb，以及兩個位置loc1和loc2。

有三種可能的操作：

• load(location, container, robot)：將容器裝載到機(jī)器人上

• move(location, location)：從一個位置移動到另一個位置

• unload(location, container, robot)：從機(jī)器人上卸載容器

操作的前提條件和效果的詳細(xì)信息可以在下面的pddl文件中看到。

我們還有五個謂詞來表示狀態(tài)：

• adjacent(loc1, loc2)-這是關(guān)于位置的靜態(tài)信息

• atl(robot, location)）-描述機(jī)器人的位置

• loaded(robot, container)-機(jī)器人是否裝載以及機(jī)器人上的容器

• unloaded(robot)-機(jī)器人已卸載

• iin(container, location)-描述容器的位置

我們使用PDDL（planningdomaindefinitionlanguage）來表示我們的規(guī)劃域和規(guī)劃問題。下面是我們感興趣的領(lǐng)域的pddl文件。

;;?Specification?in?PDDL1?of?the?DWR?domain(define?(domain?dock-worker-robot-simple)(:requirements?:strips?:typing?)(:typeslocation??????;?there?are?several?connected?locations?in?the?harborrobot?????????;?holds?at?most?1?container,?only?1?robot?per?locationcontainer)(: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))?))?)

現(xiàn)在讓我們開始深入研究規(guī)劃圖及其規(guī)劃器。

規(guī)劃圖

規(guī)劃圖是基于可達(dá)性分析的思想，即從一組初始狀態(tài)計(jì)算一組狀態(tài)是否可達(dá)的過程。

讓我們一步一步地通過一個例子來理解這個概念。首先，這是我們的初始狀態(tài)：

我們使用謂詞來表示我們的世界狀態(tài)（為了簡單起見，我們省略了相鄰的謂詞）：

• in(conta, loc1)

• in(contb, loc2)

• atl(robr, loc1)

• atl(robq, loc2)

• unloaded(robr)

• unloaded(robq)

我們想知道這個狀態(tài)是否可以到達(dá)：

我們沒有展示圖片中的機(jī)器人，因?yàn)槲覀儾魂P(guān)心它們的位置，我們只對容器的位置感興趣。我們是這樣表示的：

• in(contb, loc1)

• in(conta, loc2)

可達(dá)樹

現(xiàn)在，最簡單的方法是使用可達(dá)性樹。我們從初始狀態(tài)（根節(jié)點(diǎn)）開始，搜索狀態(tài)的適用操作（邊），然后生成預(yù)測狀態(tài)（子節(jié)點(diǎn)），并對所有子節(jié)點(diǎn)重復(fù)該過程，直到達(dá)到指定的深度。

這是深度為1的可達(dá)樹。

這是深度為2的可達(dá)樹。

我們可以看到，這并不能很好地?cái)U(kuò)展，當(dāng)我們增加深度時，節(jié)點(diǎn)的數(shù)量會爆炸。而且，我們還沒有找到這個深度的目標(biāo)，我們需要進(jìn)一步擴(kuò)大它。

可達(dá)圖

我相信你會認(rèn)為，我們可以用一個圖來改進(jìn)它，因?yàn)橛行┕?jié)點(diǎn)確實(shí)是重復(fù)的。這是depth=2的圖形版本。

雖然略有改進(jìn)，但要達(dá)到我們的目標(biāo)（紅色節(jié)點(diǎn)），我們需要depth=6，如下所示：

很可怕，不是嗎？它的規(guī)模確實(shí)很大，因?yàn)楫?dāng)我們增加深度時，復(fù)雜程度會增加，如果我們想解決更復(fù)雜的問題，這在某些時候變得不切實(shí)際。

規(guī)劃圖的可達(dá)性

規(guī)劃圖的思想是帶松弛的可達(dá)圖。在每一個深度（或者稱為層次）它不使用單個狀態(tài)，而是使用狀態(tài)的并集，因此我們可以認(rèn)為每個層次只有一個節(jié)點(diǎn)。

與可達(dá)圖不同，在可達(dá)圖中，我們通過應(yīng)用可應(yīng)用的操作來生成節(jié)點(diǎn)，所有的操作都用于生成狀態(tài)的并集。

另一個區(qū)別是在可達(dá)圖中，狀態(tài)是一組一致的命題，而在規(guī)劃圖中，狀態(tài)不是。例如，在圖中的前提條件1中，robr的位置可以同時在loc1和loc2中。

同樣，這些操作并不總是兼容的，它們可能會抵消彼此的效果。

在規(guī)劃圖中，為了跟蹤這些命題的不一致性和不兼容的操作，我們使用了所謂的互斥（mutex）。在每個層面上，我們都有：

• 一組命題互斥

• 一組操作互斥

創(chuàng)建規(guī)劃圖

現(xiàn)在，讓我們看看如何一步一步地構(gòu)建規(guī)劃圖。最初，我們有級別0，其中只有前提條件0，它等于初始狀態(tài)。

接下來，我們構(gòu)建下一個級別，級別1。從一組操作開始：

這個等式的意思是A1是一組操作，其：

• 當(dāng)前狀態(tài)滿足前提條件

• 在命題互斥對象中沒有前提條件

下一步是構(gòu)建一組命題：

我們采用先前構(gòu)建的A1，并將所有操作的積極影響結(jié)合起來。

接下來的兩個步驟是構(gòu)建互斥體，從A1的互斥體開始：

A1中的兩個操作是互斥對象，如果它們是相互依賴的(它們會抵消彼此的影響)，或者它們的前置條件在P0的互斥對象中。如果有一個負(fù)面影響會抵消一個正面影響的前提條件，那么這兩個行為是相互依賴的:

最后一步是為P1構(gòu)建互斥：

P1中的一對命題是互斥的，如果：

• A1中所有具有積極效果的一對操作中，這對操作是互斥的

• A1中沒有一個操作可以同時產(chǎn)生這兩種效果

現(xiàn)在，這是相當(dāng)復(fù)雜的，但是這個步驟可以簡單地重復(fù)到下一個級別。這是深度為3的規(guī)劃圖的結(jié)果。

此時，我們可以看到，與可達(dá)樹和可達(dá)圖相比，規(guī)劃圖的構(gòu)建要復(fù)雜得多，但正如你所看到的，它將在搜索時間上更快，并且在大小上更小，更重要的是更易于我們分析或調(diào)試。

在構(gòu)建規(guī)劃圖時，另一個重要的一點(diǎn)是，經(jīng)過一些深度之后，它將是固定的，這意味著操作集和命題集不會再發(fā)生任何變化。

我們的目標(biāo)達(dá)到了3級，我們可以看到兩個命題：

• in(contb, loc1)

• in(conta, loc2)

在P3（見上圖）。

搜索規(guī)劃圖

現(xiàn)在我們有了規(guī)劃圖-數(shù)據(jù)結(jié)構(gòu)，我們可以使用搜索算法來找到規(guī)劃問題的解決方案。

這種方法中的規(guī)劃不是一系列操作，而是操作集合。一個級別的集合中的所有操作都可以獨(dú)立執(zhí)行，這意味著它們之間沒有順序約束。

在我們的例子中，搜索從P3向后執(zhí)行到P0，遞歸地求解目標(biāo)中的所有命題。在我們解決它們之后，我們遞歸地使用操作的前提條件作為子目標(biāo)，直到我們達(dá)到P0。

我們跳過的一件重要的事情是，在每一個級別上，我們都有不做任何事情的虛擬操作—它們的前提條件和效果是相同的。這使得算法能夠順利地處理那些在較低層次上已經(jīng)滿足的命題。

例如，我們的解決方案規(guī)劃是：

• 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)}

結(jié)論

我們希望現(xiàn)在能夠理解如何通過使用規(guī)劃圖方法來提高經(jīng)典規(guī)劃方法的復(fù)雜性。與可達(dá)樹和可達(dá)圖相比，規(guī)劃圖的構(gòu)建更加復(fù)雜，但是它節(jié)省了我們搜索解決方案的大小和時間，如分步示例所示。

我希望你理解這個概念，在下一篇文章中，我們將用Python實(shí)現(xiàn)這個方法，以證明它是有效的，并幫助我們進(jìn)一步理解它。

js可視化庫D3

2021-06-16

手把手教你使用Python打造絢麗的詞云圖

2021-06-14

利用python進(jìn)行數(shù)據(jù)清理

2021-06-15

?------------------------------------------------

看到這里，說明你喜歡這篇文章，請點(diǎn)擊「在看」或順手「轉(zhuǎn)發(fā)」「點(diǎn)贊」。

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊深度學(xué)習(xí)筆記專輯《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)專輯溫州大學(xué)《機(jī)器學(xué)習(xí)課程》視頻 本站qq群851320808，加入微信群請掃碼：

總結(jié)

以上是生活随笔為你收集整理的利用规划图提高经典人工智能规划复杂度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。