作者 | Debby Nirwan

編譯 | VK
來源 | Towards Data Science

這篇文章涉及規劃圖技術分步算法實現：從偽代碼和方程到Python代碼。在本文中，我們將用Python實現規劃圖（Planning Graph）及其規劃器GraphPlanner，以及AI規劃的數據結構和搜索算法。

介紹

規劃圖是為了解決經典人工智能規劃方法(又稱STRIPS規劃器)的復雜性問題而發展起來的。我們需要實施兩個主要部分：

• 規劃圖：數據結構

• 圖規劃：搜索算法，為我們找到解決方案

如果你不熟悉規劃圖，想了解更多，請查看我的以下帖子：

https://towardsdatascience.com/improving-classical-ai-planning-complexity-with-planning-graph-c63d47f87018

領域和問題表示

在我們開始實現之前，我們需要知道我們將如何表示規劃域和規劃問題。

規劃圖及其規劃器與許多STRIPS規劃器有相同的表示，因此我們將使用PDDL(規劃域定義語言)來表示它們。下面是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))?))?)

我們可以將PDDL看作JSON或XML之類的東西，這意味著我們需要一個解析器來反序列化用它編寫的表示。當我在Github上搜索時，其中有幾個出現了，但是有一個似乎很適合我們的項目pddlpy。

https://github.com/hfoffani/pddl-lib

但是，它在開發中不再活躍，我發現了一個bug和一些問題。因此，我決定使用它并編寫一個適配器/包裝器，這是一個薄層，我們添加它來修復錯誤并解決其他問題。

PDDL適配器

我們需要的代表如下：

• 世界的初始狀態：數據類型為set

• 目標狀態：數據類型為set

• 運算符(也稱為操作)的列表，這些運算符已用實變量實例化：數據類型為List[Operator]

我們將只使用pddlpy庫中的一個接口，DomainProblem()類構造函數。

我們需要提供上面列出的三個接口：初始狀態、目標狀態和運算符列表。

我們創建了一個名為PlanningProblem的類：

class?PlanningProblem(object):def?__init__(self,?dom_file:?str,?problem_file:?str):self._domain_file?=?dom_fileself._problem_file?=?problem_fileself._domain_problem?=?DomainProblem(self._domain_file,self._problem_file)self._initial_state?=?self._to_set_of_tuples(self._domain_problem.initialstate())self._goal_state?=?self._to_set_of_tuples(self._domain_problem.goals())self._actions?=?self._get_ground_operators()

庫提供的狀態不是我們想要的正確數據類型，因此需要將它們轉換為一組元組。

我們使用set()數據類型，以便以后實現數據結構和算法。因為在經典的人工智能規劃中，我們大量使用集合論，我們應該使用set()數據類型來利用內置函數來加速我們的實現。我們將在下一節看到更多內容。

我們還必須創建一個運算符列表，我們稱之為操作。下面是適配器的最終代碼。

class?PlanningProblem(object):def?__init__(self,?dom_file:?str,?problem_file:?str):self._domain_file?=?dom_fileself._problem_file?=?problem_fileself._domain_problem?=?DomainProblem(self._domain_file,self._problem_file)self._initial_state?=?self._to_set_of_tuples(self._domain_problem.initialstate())self._goal_state?=?self._to_set_of_tuples(self._domain_problem.goals())self._actions?=?self._get_ground_operators()@staticmethoddef?_type_symbols(variable_type,?world_objects:?dict):#?如果變量類型是在world對象中找到的，#?返回對象名稱列表，如robr,?robqreturn?(k?for?k,?v?in?world_objects.items()?if?v?==?variable_type)def?_instantiate(self,?variables,?world_objects:?dict):variable_ground_space?=?[]for?variable_name,?variable_type?in?variables:c?=?[]for?symbol?in?self._type_symbols(variable_type,?world_objects):c.append((variable_name,?symbol))variable_ground_space.append(c)return?itertools.product(*variable_ground_space)def?_get_ground_operators(self)?->?List[Operator]:ground_operators?=?[]for?operator?in?self._domain_problem.operators():op?=?self._domain_problem.domain.operators[operator]for?ground?in?self._instantiate(op.variable_list.items(),self._domain_problem.worldobjects()):st?=?dict(ground)gop?=?Operator(operator)gop.variable_list?=?stgop.precondition_pos?=?set([a.ground(st)?for?a?in?op.precondition_pos])gop.precondition_neg?=?set([a.ground(st)?for?a?in?op.precondition_neg])gop.effect_pos?=?set([a.ground(st)?for?a?in?op.effect_pos])gop.effect_neg?=?set([a.ground(st)?for?a?in?op.effect_neg])ground_operators.append(gop)return?ground_operators@staticmethoddef?_to_set_of_tuples(state:?Set[Atom])?->?Set[Tuple]:set_of_tuples?=?set()for?atom?in?state:tup?=?tuple(atom.predicate)set_of_tuples.add(tup)return?set_of_tuples@propertydef?initial_state(self):return?self._initial_state@propertydef?goal_state(self):return?self._goal_state@propertydef?actions(self):return?self._actions

我們現在可以使用這個類來解決規劃領域和規劃問題，并將重點放在數據結構和算法實現上。

規劃圖：數據結構

在這里我們將只看偽代碼和方程，然后接下來的重點是將它們翻譯成代碼

以下是我們如何構建規劃圖的偽代碼：

有四個步驟，我們一個接一個地講。

計算動作

這是指以下步驟：

其中包括兩部分：

• 對于PDDL適配器提供的所有操作，我們在當前狀態下搜索可用的操作

• 我們確保那些可應用的操作的前提條件不在前提條件的互斥體中

class?PlanningGraph(object):def?__init__(self,?dom_file:?str,?problem_file:?str):self._planning_problem?=?PlanningProblem(dom_file,?problem_file)self._graph:?Graph?=?Graph(visualize)def?compute_actions(self,?gr:?Graph):graph_result?=?grlevel?=?gr.num_of_levels#?計算?Aiaction_list?=?[]for?action?in?self._planning_problem.actions:if?self._applicable(action,?graph_result.prop[level?-?1],graph_result.prop_mutexes[level?-?1]):action_list.append(action)graph_result.act[level]?=?action_list@staticmethoddef?_applicable(action,?state,?preconditions_mutex)?->?bool:if?action.precondition_pos.issubset(state)?and?\action.precondition_neg.isdisjoint(state):applicable?=?Trueif?preconditions_mutex?is?not?None:for?precondition?in?list(permutations(action.precondition_pos,?2)):if?precondition?in?preconditions_mutex:applicable?=?Falsebreakelse:applicable?=?Falsereturn?applicable)

計算前提條件

下一步是計算前提條件，也就是這一步：

這一步非常簡單：

class?PlanningGraph(object):def?__init__(self,?dom_file:?str,?problem_file:?str):self._planning_problem?=?PlanningProblem(dom_file,?problem_file)self._graph:?Graph?=?Graph(visualize)def?compute_preconditions(self,?gr:?Graph):graph_result?=?grlevel?=?gr.num_of_levelsproposition_list?=?set()for?action?in?action_list:for?effect?in?action.effect_pos:proposition_list.add(effect)graph_result.prop[level]?=?proposition_list

我們只存儲計算出的動作效果。

計算操作互斥

該算法的下一步是計算Actions Mutex（操作互斥），這是一組相互抵消效果的操作。

在這個等式中有三個部分，對于動作中所有可能的排列，我們希望在我們的列表中包括以下內容：

• 行動的消極影響會干擾另一方的積極影響或先決條件

• 第二部分是相同的，只是在另一個方向(b到a)

• 第三部分是它們的前提條件是互斥

class?PlanningGraph(object):def?__init__(self,?dom_file:?str,?problem_file:?str):self._planning_problem?=?PlanningProblem(dom_file,?problem_file)self._graph:?Graph?=?Graph(visualize)def?compute_actions_mutex(self,?gr:?Graph):graph_result?=?grlevel?=?gr.num_of_levelsaction_mutex_list?=?[]for?action_pair?in?list(permutations(action_list,?2)):if?self.compute_action_mutex(action_pair,graph_result.prop_mutexes[level?-?1]):action_mutex_list.append(action_pair)graph_result.act_mutexes[level]?=?action_mutex_list@staticmethoddef?compute_action_mutex(pair,?preconds_mutex)?->?bool:a?=?pair[0]b?=?pair[1]#?兩個動作是相互依存的if?a.effect_neg.interp(b.precondition_pos.union(b.effect_pos))?\!=?set():return?Trueif?b.effect_neg.interp(a.precondition_pos.union(a.effect_pos))?\!=?set():return?True#?它們的先決條件互斥if?preconds_mutex?is?not?None:for?mutex?in?preconds_mutex:#?(p,?q)p?=?mutex[0]q?=?mutex[1]if?p?in?a.precondition_pos?and?q?in?b.precondition_pos:return?Truereturn?False

計算互斥的前提條件

建立規劃圖的算法的最后一步是計算預條件互斥

這意味著我們要尋找一對互斥的前提條件。它們是互斥的當且僅當：

• 對于同時產生p和q的所有操作對，它們都在actions Mutex列表中

• 沒有同時產生p和q的單一操作

class?PlanningGraph(object):def?__init__(self,?dom_file:?str,?problem_file:?str):self._planning_problem?=?PlanningProblem(dom_file,?problem_file)self._graph:?Graph?=?Graph()def?compute_preconditions_mutex(self,?gr:?Graph):proposition_mutex_list?=?[]for?proposition_pair?in?list(permutations(proposition_list,?2)):if?self.compute_precondition_mutex(proposition_pair,?action_list,?action_mutex_list):if?proposition_pair?not?in?proposition_mutex_list:swapped?=?(proposition_pair[1],?proposition_pair[0])if?swapped?not?in?proposition_mutex_list:proposition_mutex_list.append(proposition_pair)graph_result.prop_mutexes[level]?=?proposition_mutex_list@staticmethoddef?compute_precondition_mutex(proposition_pair,?action_list,?action_mutex):p?=?proposition_pair[0]q?=?proposition_pair[1]for?action?in?action_list:if?p?in?action.effect_pos?and?q?in?action.effect_pos:#?(p,?q)不是互斥對象，如果它們都是由同一個動作產生的return?False#?每一個產生p的動作actions_with_p?=?set()for?action?in?action_list:if?p?in?action.effect_pos:actions_with_p.add(action)#?每一個產生q的動作actions_with_q?=?set()for?action?in?action_list:if?q?in?action.effect_pos:actions_with_q.add(action)all_mutex?=?Truefor?p_action?in?actions_with_p:for?q_action?in?actions_with_q:if?p_action?==?q_action:return?Falseif?(p_action,?q_action)?not?in?action_mutex:all_mutex?=?Falsebreakif?not?all_mutex:breakreturn?all_mutex

我們現在已經完成了構建數據結構的代碼，規劃圖。為了幫助調試，可以使用pydot擴充代碼以生成圖形可視化。下面是一個例子。

搜索算法：GraphPlanner

我們現在已經準備好了數據結構，我們可以開始實現搜索算法，為我們的計劃問題找到解決方案。

該算法是遞歸的，分為三個部分：

• 計劃

• 提取

• 搜索

提取和搜索

這兩個步驟是遞歸的，算法如下。第一部分是Extract：

下一部分是Search：

這是這兩個函數如何遞歸工作的示例：

它遞歸地調用Search()，直到所有的命題都被解析，并調用Extract()進入規劃圖的下一級。

Python編寫如下：

class?GraphPlanner(object):def?__init__(self):self._layered_plan:?LayeredPlan?=?LayeredPlan()self._mutex?=?{}def?_extract(self,?gr:?Graph,?g:?set,?index:?int):if?index?==?0:return?Plan()return?self._search(gr,?g,?Plan(),?index)def?_search(self,?gr:?Graph,?g:?set,?plan:?Plan,?index:?int):if?g?==?set():new_goals?=?set()for?action?in?plan.plan:for?proposition?in?action.precondition_pos:if?'adjacent'?not?in?proposition:new_goals.add(proposition)extracted_plan?=?self._extract(gr,?new_goals,?index-1)if?extracted_plan?is?None:return?Noneelse:self._layered_plan[index-1]?=?extracted_planself._layered_plan[index]?=?planreturn?planelse:#?選擇g中的任意pproposition?=?g.pop()#?計算解析器resolvers?=?[]for?action?in?gr.act[index]:if?proposition?in?action.effect_pos:if?plan.plan:mutex?=?Falsefor?action2?in?plan.plan:if?(action,?action2)?in?\gr.act_mutexes[index]:mutex?=?Truebreakif?not?mutex:resolvers.append(action)else:resolvers.append(action)#?沒有解析器if?not?resolvers:return?None#?選擇非確定性，如果失敗則回溯while?resolvers:resolver?=?resolvers.pop()plan.append(resolver)plan_result?=?self._search(gr,?g?-?resolver.effect_pos,plan,?index)if?plan_result?is?not?None:return?plan_resultelse:plan.remove(resolver)g.add(proposition)return?None

主程序

最后，我們到達了算法的最后一步、以下是主要步驟和入口點：

在某些情況下，我們需要計劃更多的步驟來創建解決方案計劃，我們需要展開規劃圖并重試搜索。

我們還需要添加一個額外的步驟，以確保算法在沒有可能的解決方案時終止。下面是我們的最后一段代碼：

class?GraphPlanner(object):def?__init__(self):self._layered_plan:?LayeredPlan?=?LayeredPlan()self._mutex?=?{}def?plan(self,?gr:?Graph,?g:?set):index?=?gr.num_of_levels?-?1if?not?g.issubset(gr.prop[index]):return?Noneplan?=?self._extract(gr,?g,?index)if?plan:return?self._layered_planif?gr.fixed_point:n?=?0try:props_mutex?=?self._mutex[gr.num_of_levels?-?1]except?KeyError:props_mutex?=?Noneif?props_mutex:n?=?len(props_mutex)else:n?=?0while?True:index?+=?1gr?=?PlanningGraph.expand(gr)plan?=?self._extract(gr,?g,?index)if?plan:return?self._layered_planelif?gr.fixed_point:try:props_mutex?=?self._mutex[gr.num_of_levels-1]except?KeyError:props_mutex?=?Noneif?props_mutex:if?n?==?len(props_mutex):#?這意味著它已經穩定下來return?Noneelse:n?=?len(props_mutex)

結尾

我意識到要描述實現這個算法的思想過程并不容易。但我希望至少你能對如何實現從等式、偽代碼到Python代碼的算法有一些基本的理解。

完整代碼可在我的Github上獲得，如下所示：

https://github.com/debbynirwan/planning_graph

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯溫州大學《機器學習課程》視頻 本站qq群851320808，加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的【图网络】如何用Python实现算法：规划图技术(GraphPlanner)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。