planning_partial_order_planner.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PARTIAL ORDER  PLANNER\n",
    "A partial-order planning algorithm is significantly different from a total-order planner.\n",
    "The way a partial-order plan works enables it to take advantage of _problem decomposition_ and work on each subproblem separately.\n",
    "It works on several subgoals independently, solves them with several subplans, and then combines the plan.\n",
    "<br>\n",
    "A partial-order planner also follows the **least commitment** strategy, where it delays making choices for as long as possible.\n",
    "Variables are not bound unless it is absolutely necessary and new actions are chosen only if the existing actions cannot fulfil the required precondition.\n",
    "<br>\n",
    "Any planning algorithm that can place two actions into a plan without specifying which comes first is called a **partial-order planner**.\n",
    "A partial-order planner searches through the space of plans rather than the space of states, which makes it perform better for certain problems.\n",
    "<br>\n",
    "<br>\n",
    "Let's have a look at the `PartialOrderPlanner` class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from planning import *\n",
    "from notebook import psource"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
       "span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
       "pre { line-height: 125%; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body  { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">PartialOrderPlanner</span><span class=\"p\">:</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">planningproblem</span><span class=\"p\">):</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span> <span class=\"o\">=</span> <span class=\"n\">planningproblem</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">initialize</span><span class=\"p\">()</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">initialize</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Initialize all variables&quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span> <span class=\"o\">=</span> <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"s1\">&#39;Start&#39;</span><span class=\"p\">,</span> <span class=\"p\">[],</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">)</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span> <span class=\"o\">=</span> <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"s1\">&#39;Finish&#39;</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"o\">.</span><span class=\"n\">goals</span><span class=\"p\">,</span> <span class=\"p\">[])</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">)</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"p\">)</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"p\">))</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">precond</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"p\">))</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expand_actions</span><span class=\"p\">()</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">expand_actions</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">name</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Generate all possible actions with variable bindings for precondition selection heuristic&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">objects</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">arg</span> <span class=\"k\">for</span> <span class=\"n\">clause</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"o\">.</span><span class=\"n\">init</span> <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">expansions</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "        <span class=\"n\">action_list</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">name</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">if</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">name</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">action_list</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">action_list</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"o\">.</span><span class=\"n\">actions</span>\n",
       "\n",
       "        <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"n\">action_list</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">permutation</span> <span class=\"ow\">in</span> <span class=\"n\">itertools</span><span class=\"o\">.</span><span class=\"n\">permutations</span><span class=\"p\">(</span><span class=\"n\">objects</span><span class=\"p\">,</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">)):</span>\n",
       "                <span class=\"n\">bindings</span> <span class=\"o\">=</span> <span class=\"n\">unify</span><span class=\"p\">(</span><span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"o\">*</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">),</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"o\">*</span><span class=\"n\">permutation</span><span class=\"p\">))</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">bindings</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">new_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "                    <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
       "                        <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
       "                            <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
       "                        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                            <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
       "                    <span class=\"n\">new_expr</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_args</span><span class=\"p\">)</span>\n",
       "                    <span class=\"n\">new_preconds</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "                    <span class=\"k\">for</span> <span class=\"n\">precond</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
       "                        <span class=\"n\">new_precond_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "                        <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">precond</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
       "                            <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
       "                                <span class=\"n\">new_precond_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
       "                            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                                <span class=\"n\">new_precond_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
       "                        <span class=\"n\">new_precond</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">precond</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_precond_args</span><span class=\"p\">)</span>\n",
       "                        <span class=\"n\">new_preconds</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_precond</span><span class=\"p\">)</span>\n",
       "                    <span class=\"n\">new_effects</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "                    <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
       "                        <span class=\"n\">new_effect_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "                        <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
       "                            <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
       "                                <span class=\"n\">new_effect_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
       "                            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                                <span class=\"n\">new_effect_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
       "                        <span class=\"n\">new_effect</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_effect_args</span><span class=\"p\">)</span>\n",
       "                        <span class=\"n\">new_effects</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_effect</span><span class=\"p\">)</span>\n",
       "                    <span class=\"n\">expansions</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"n\">new_expr</span><span class=\"p\">,</span> <span class=\"n\">new_preconds</span><span class=\"p\">,</span> <span class=\"n\">new_effects</span><span class=\"p\">))</span>\n",
       "\n",
       "        <span class=\"k\">return</span> <span class=\"n\">expansions</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">find_open_precondition</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Find open precondition with the least number of possible actions&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">number_of_ways</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
       "        <span class=\"n\">actions_for_precondition</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">open_precondition</span> <span class=\"o\">=</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
       "            <span class=\"n\">possible_actions</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">)</span> <span class=\"o\">+</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"n\">possible_actions</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
       "                    <span class=\"k\">if</span> <span class=\"n\">effect</span> <span class=\"o\">==</span> <span class=\"n\">open_precondition</span><span class=\"p\">:</span>\n",
       "                        <span class=\"k\">if</span> <span class=\"n\">open_precondition</span> <span class=\"ow\">in</span> <span class=\"n\">number_of_ways</span><span class=\"p\">:</span>\n",
       "                            <span class=\"n\">number_of_ways</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"mi\">1</span>\n",
       "                            <span class=\"n\">actions_for_precondition</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
       "                        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                            <span class=\"n\">number_of_ways</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
       "                            <span class=\"n\">actions_for_precondition</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">action</span><span class=\"p\">]</span>\n",
       "\n",
       "        <span class=\"n\">number</span> <span class=\"o\">=</span> <span class=\"nb\">sorted</span><span class=\"p\">(</span><span class=\"n\">number_of_ways</span><span class=\"p\">,</span> <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"n\">number_of_ways</span><span class=\"o\">.</span><span class=\"fm\">__getitem__</span><span class=\"p\">)</span>\n",
       "        \n",
       "        <span class=\"k\">for</span> <span class=\"n\">k</span><span class=\"p\">,</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">number_of_ways</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">v</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">return</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"bp\">None</span>\n",
       "\n",
       "        <span class=\"n\">act1</span> <span class=\"o\">=</span> <span class=\"bp\">None</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]:</span>\n",
       "                <span class=\"n\">act1</span> <span class=\"o\">=</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]</span>\n",
       "                <span class=\"k\">break</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span><span class=\"o\">.</span><span class=\"n\">remove</span><span class=\"p\">(</span><span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">])</span>\n",
       "\n",
       "        <span class=\"k\">return</span> <span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">],</span> <span class=\"n\">act1</span><span class=\"p\">,</span> <span class=\"n\">actions_for_precondition</span><span class=\"p\">[</span><span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">find_action_for_precondition</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">oprec</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Find action for a given precondition&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"c1\"># either</span>\n",
       "        <span class=\"c1\">#   choose act0 E Actions such that act0 achieves G</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">effect</span> <span class=\"o\">==</span> <span class=\"n\">oprec</span><span class=\"p\">:</span>\n",
       "                    <span class=\"k\">return</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"mi\">0</span>\n",
       "\n",
       "        <span class=\"c1\"># or</span>\n",
       "        <span class=\"c1\">#   choose act0 E Actions such that act0 achieves G</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span> <span class=\"o\">==</span> <span class=\"n\">oprec</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">bindings</span> <span class=\"o\">=</span> <span class=\"n\">unify</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"p\">,</span> <span class=\"n\">oprec</span><span class=\"p\">)</span>\n",
       "                    <span class=\"k\">if</span> <span class=\"n\">bindings</span> <span class=\"ow\">is</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
       "                        <span class=\"k\">break</span>\n",
       "                    <span class=\"k\">return</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">bindings</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">generate_expr</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">clause</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Generate atomic expression from generic expression given variable bindings&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">new_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"k\">try</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_args</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">except</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_args</span><span class=\"p\">)</span>\n",
       "        \n",
       "    <span class=\"k\">def</span> <span class=\"nf\">generate_action_object</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Generate action object given a generic action andvariable bindings&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"c1\"># if bindings is 0, it means the action already exists in self.actions</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">bindings</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">action</span>\n",
       "\n",
       "        <span class=\"c1\"># bindings cannot be None</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">new_expr</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">generate_expr</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">new_preconds</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">precond</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">new_precond</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">generate_expr</span><span class=\"p\">(</span><span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">)</span>\n",
       "                <span class=\"n\">new_preconds</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_precond</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">new_effects</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">new_effect</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">generate_expr</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">)</span>\n",
       "                <span class=\"n\">new_effects</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_effect</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"n\">new_expr</span><span class=\"p\">,</span> <span class=\"n\">new_preconds</span><span class=\"p\">,</span> <span class=\"n\">new_effects</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">cyclic</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Check cyclicity of a directed graph&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">new_graph</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">in</span> <span class=\"n\">new_graph</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">new_graph</span><span class=\"p\">[</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">])</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">new_graph</span><span class=\"p\">[</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]]</span>\n",
       "\n",
       "        <span class=\"n\">path</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
       "\n",
       "        <span class=\"k\">def</span> <span class=\"nf\">visit</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">):</span>\n",
       "            <span class=\"n\">path</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">neighbor</span> <span class=\"ow\">in</span> <span class=\"n\">new_graph</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">,</span> <span class=\"p\">()):</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">neighbor</span> <span class=\"ow\">in</span> <span class=\"n\">path</span> <span class=\"ow\">or</span> <span class=\"n\">visit</span><span class=\"p\">(</span><span class=\"n\">neighbor</span><span class=\"p\">):</span>\n",
       "                    <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
       "            <span class=\"n\">path</span><span class=\"o\">.</span><span class=\"n\">remove</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
       "\n",
       "        <span class=\"n\">value</span> <span class=\"o\">=</span> <span class=\"nb\">any</span><span class=\"p\">(</span><span class=\"n\">visit</span><span class=\"p\">(</span><span class=\"n\">v</span><span class=\"p\">)</span> <span class=\"k\">for</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">new_graph</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">value</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">add_const</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">constraint</span><span class=\"p\">,</span> <span class=\"n\">constraints</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Add the constraint to constraints if the resulting graph is acyclic&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span> <span class=\"ow\">or</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">constraints</span>\n",
       "\n",
       "        <span class=\"n\">new_constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">new_constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">cyclic</span><span class=\"p\">(</span><span class=\"n\">new_constraints</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">constraints</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">new_constraints</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">is_a_threat</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">precondition</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Check if effect is a threat to precondition&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"s1\">&#39;Not&#39;</span> <span class=\"o\">+</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">precondition</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">))</span> <span class=\"ow\">or</span> <span class=\"p\">(</span><span class=\"s1\">&#39;Not&#39;</span> <span class=\"o\">+</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">precondition</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">)):</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">args</span> <span class=\"o\">==</span> <span class=\"n\">precondition</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
       "        <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">protect</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">constraints</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Check and resolve threats by promotion or demotion&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">threat</span> <span class=\"o\">=</span> <span class=\"bp\">False</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">is_a_threat</span><span class=\"p\">(</span><span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">],</span> <span class=\"n\">effect</span><span class=\"p\">):</span>\n",
       "                <span class=\"n\">threat</span> <span class=\"o\">=</span> <span class=\"bp\">True</span>\n",
       "                <span class=\"k\">break</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"n\">action</span> <span class=\"o\">!=</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">and</span> <span class=\"n\">action</span> <span class=\"o\">!=</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">2</span><span class=\"p\">]</span> <span class=\"ow\">and</span> <span class=\"n\">threat</span><span class=\"p\">:</span>\n",
       "            <span class=\"c1\"># try promotion</span>\n",
       "            <span class=\"n\">new_constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">new_constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]))</span>\n",
       "            <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">cyclic</span><span class=\"p\">(</span><span class=\"n\">new_constraints</span><span class=\"p\">):</span>\n",
       "                <span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]),</span> <span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                <span class=\"c1\"># try demotion</span>\n",
       "                <span class=\"n\">new_constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "                <span class=\"n\">new_constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">2</span><span class=\"p\">],</span> <span class=\"n\">action</span><span class=\"p\">))</span>\n",
       "                <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">cyclic</span><span class=\"p\">(</span><span class=\"n\">new_constraints</span><span class=\"p\">):</span>\n",
       "                    <span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">2</span><span class=\"p\">],</span> <span class=\"n\">action</span><span class=\"p\">),</span> <span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "                <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                    <span class=\"c1\"># both promotion and demotion fail</span>\n",
       "                    <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;Unable to resolve a threat caused by&#39;</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"s1\">&#39;onto&#39;</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">)</span>\n",
       "                    <span class=\"k\">return</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">constraints</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">convert</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">constraints</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Convert constraints into a dict of Action to set orderings&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">constraint</span> <span class=\"ow\">in</span> <span class=\"n\">constraints</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">graph</span><span class=\"p\">[</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">])</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">graph</span><span class=\"p\">[</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
       "                <span class=\"n\">graph</span><span class=\"p\">[</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">])</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">graph</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">toposort</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Generate topological ordering of constraints&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">graph</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span>\n",
       "\n",
       "        <span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">copy</span><span class=\"p\">()</span>\n",
       "\n",
       "        <span class=\"k\">for</span> <span class=\"n\">k</span><span class=\"p\">,</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
       "            <span class=\"n\">v</span><span class=\"o\">.</span><span class=\"n\">discard</span><span class=\"p\">(</span><span class=\"n\">k</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"n\">extra_elements_in_dependencies</span> <span class=\"o\">=</span> <span class=\"n\">_reduce</span><span class=\"p\">(</span><span class=\"nb\">set</span><span class=\"o\">.</span><span class=\"n\">union</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">())</span> <span class=\"o\">-</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">keys</span><span class=\"p\">())</span>\n",
       "\n",
       "        <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">update</span><span class=\"p\">({</span><span class=\"n\">element</span><span class=\"p\">:</span><span class=\"nb\">set</span><span class=\"p\">()</span> <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"n\">extra_elements_in_dependencies</span><span class=\"p\">})</span>\n",
       "        <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">ordered</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">element</span> <span class=\"k\">for</span> <span class=\"n\">element</span><span class=\"p\">,</span> <span class=\"n\">dependency</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">()</span> <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">dependency</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">ordered</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">break</span>\n",
       "            <span class=\"k\">yield</span> <span class=\"n\">ordered</span>\n",
       "            <span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"p\">{</span><span class=\"n\">element</span><span class=\"p\">:</span> <span class=\"p\">(</span><span class=\"n\">dependency</span> <span class=\"o\">-</span> <span class=\"n\">ordered</span><span class=\"p\">)</span> <span class=\"k\">for</span> <span class=\"n\">element</span><span class=\"p\">,</span> <span class=\"n\">dependency</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">()</span> <span class=\"k\">if</span> <span class=\"n\">element</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"n\">ordered</span><span class=\"p\">}</span>\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">graph</span><span class=\"p\">)</span> <span class=\"o\">!=</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">raise</span> <span class=\"ne\">ValueError</span><span class=\"p\">(</span><span class=\"s1\">&#39;The graph is not acyclic and cannot be linearly ordered&#39;</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">display_plan</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Display causal links, constraints and the plan&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;Causal Links&#39;</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">causal_link</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">causal_link</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;</span><span class=\"se\">\\n</span><span class=\"s1\">Constraints&#39;</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">constraint</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">],</span> <span class=\"s1\">&#39;&lt;&#39;</span><span class=\"p\">,</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">])</span>\n",
       "\n",
       "        <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;</span><span class=\"se\">\\n</span><span class=\"s1\">Partial Order Plan&#39;</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">reversed</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">toposort</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">convert</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">))))))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">execute</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">display</span><span class=\"o\">=</span><span class=\"bp\">True</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Execute the algorithm&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">step</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">tries</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
       "        <span class=\"k\">while</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"p\">)</span> <span class=\"o\">&gt;</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">step</span> <span class=\"o\">+=</span> <span class=\"mi\">1</span>\n",
       "            <span class=\"c1\"># select &lt;G, act1&gt; from Agenda</span>\n",
       "            <span class=\"k\">try</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">,</span> <span class=\"n\">possible_actions</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">find_open_precondition</span><span class=\"p\">()</span>\n",
       "            <span class=\"k\">except</span> <span class=\"ne\">IndexError</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;Probably Wrong&#39;</span><span class=\"p\">)</span>\n",
       "                <span class=\"k\">break</span>\n",
       "\n",
       "            <span class=\"n\">act0</span> <span class=\"o\">=</span> <span class=\"n\">possible_actions</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
       "            <span class=\"c1\"># remove &lt;G, act1&gt; from Agenda</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"o\">.</span><span class=\"n\">remove</span><span class=\"p\">((</span><span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">))</span>\n",
       "\n",
       "            <span class=\"c1\"># For actions with variable number of arguments, use least commitment principle</span>\n",
       "            <span class=\"c1\"># act0_temp, bindings = self.find_action_for_precondition(G)</span>\n",
       "            <span class=\"c1\"># act0 = self.generate_action_object(act0_temp, bindings)</span>\n",
       "\n",
       "            <span class=\"c1\"># Actions = Actions U {act0}</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">act0</span><span class=\"p\">)</span>\n",
       "\n",
       "            <span class=\"c1\"># Constraints = add_const(start &lt; act0, Constraints)</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">,</span> <span class=\"n\">act0</span><span class=\"p\">),</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "\n",
       "            <span class=\"c1\"># for each CL E CausalLinks do</span>\n",
       "            <span class=\"c1\">#   Constraints = protect(CL, act0, Constraints)</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">causal_link</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"p\">:</span>\n",
       "                <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">protect</span><span class=\"p\">(</span><span class=\"n\">causal_link</span><span class=\"p\">,</span> <span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "\n",
       "            <span class=\"c1\"># Agenda = Agenda U {&lt;P, act0&gt;: P is a precondition of act0}</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">precondition</span> <span class=\"ow\">in</span> <span class=\"n\">act0</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
       "                <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">precondition</span><span class=\"p\">,</span> <span class=\"n\">act0</span><span class=\"p\">))</span>\n",
       "\n",
       "            <span class=\"c1\"># Constraints = add_const(act0 &lt; act1, Constraints)</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">),</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "\n",
       "            <span class=\"c1\"># CausalLinks U {&lt;act0, G, act1&gt;}</span>\n",
       "            <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">)</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"p\">:</span>\n",
       "                <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">((</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">))</span>\n",
       "\n",
       "            <span class=\"c1\"># for each A E Actions do</span>\n",
       "            <span class=\"c1\">#   Constraints = protect(&lt;act0, G, act1&gt;, A, Constraints)</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
       "                <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">protect</span><span class=\"p\">((</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">),</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
       "\n",
       "            <span class=\"k\">if</span> <span class=\"n\">step</span> <span class=\"o\">&gt;</span> <span class=\"mi\">200</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;Couldn</span><span class=\"se\">\\&#39;</span><span class=\"s1\">t find a solution&#39;</span><span class=\"p\">)</span>\n",
       "                <span class=\"k\">return</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"bp\">None</span>\n",
       "\n",
       "        <span class=\"k\">if</span> <span class=\"n\">display</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">display_plan</span><span class=\"p\">()</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span>                \n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(PartialOrderPlanner)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will first describe the data-structures and helper methods used, followed by the algorithm used to find a partial-order plan."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each plan has the following four components:\n",
    "\n",
    "1. **`actions`**: a set of actions that make up the steps of the plan.\n",
    "`actions` is always a subset of `pddl.actions` the set of possible actions for the given planning problem. \n",
    "The `start` and `finish` actions are dummy actions defined to bring uniformity to the problem. The `start` action has no preconditions and its effects constitute the initial state of the planning problem. \n",
    "The `finish` action has no effects and its preconditions constitute the goal state of the planning problem.\n",
    "The empty plan consists of just these two dummy actions.\n",
    "2. **`constraints`**: a set of temporal constraints that define the order of performing the actions relative to each other.\n",
    "`constraints` does not define a linear ordering, rather it usually represents a directed graph which is also acyclic if the plan is consistent.\n",
    "Each ordering is of the form A &lt; B, which reads as \"A before B\" and means that action A _must_ be executed sometime before action B, but not necessarily immediately before.\n",
    "`constraints` stores these as a set of tuples `(Action(A), Action(B))` which is interpreted as given above.\n",
    "A constraint cannot be added to `constraints` if it breaks the acyclicity of the existing graph.\n",
    "3. **`causal_links`**: a set of causal-links. \n",
    "A causal link between two actions _A_ and _B_ in the plan is written as _A_ --_p_--> _B_ and is read as \"A achieves p for B\".\n",
    "This imples that _p_ is an effect of _A_ and a precondition of _B_.\n",
    "It also asserts that _p_ must remain true from the time of action _A_ to the time of action _B_.\n",
    "Any violation of this rule is called a threat and must be resolved immediately by adding suitable ordering constraints.\n",
    "`causal_links` stores this information as tuples `(Action(A), precondition(p), Action(B))` which is interpreted as given above.\n",
    "Causal-links can also be called **protection-intervals**, because the link _A_ --_p_--> _B_ protects _p_ from being negated over the interval from _A_ to _B_.\n",
    "4. **`agenda`**: a set of open-preconditions.\n",
    "A precondition is open if it is not achieved by some action in the plan.\n",
    "Planners will work to reduce the set of open preconditions to the empty set, without introducing a contradiction.\n",
    "`agenda` stored this information as tuples `(precondition(p), Action(A))` where p is a precondition of the action A.\n",
    "\n",
    "A **consistent plan** is a plan in which there are no cycles in the ordering constraints and no conflicts with the causal-links.\n",
    "A consistent plan with no open preconditions is a **solution**.\n",
    "<br>\n",
    "<br>\n",
    "Let's briefly glance over the helper functions before going into the actual algorithm.\n",
    "<br>\n",
    "**`expand_actions`**: generates all possible actions with variable bindings for use as a heuristic of selection of an open precondition.\n",
    "<br>\n",
    "**`find_open_precondition`**: finds a precondition from the agenda with the least number of actions that fulfil that precondition.\n",
    "This heuristic helps form mandatory ordering constraints and causal-links to further simplify the problem and reduce the probability of encountering a threat.\n",
    "<br>\n",
    "**`find_action_for_precondition`**: finds an action that fulfils the given precondition along with the absolutely necessary variable bindings in accordance with the principle of _least commitment_.\n",
    "In case of multiple possible actions, the action with the least number of effects is chosen to minimize the chances of encountering a threat.\n",
    "<br>\n",
    "**`cyclic`**: checks if a directed graph is cyclic.\n",
    "<br>\n",
    "**`add_const`**: adds `constraint` to `constraints` if the newly formed graph is acyclic and returns `constraints` otherwise.\n",
    "<br>\n",
    "**`is_a_threat`**: checks if the given `effect` negates the given `precondition`.\n",
    "<br>\n",
    "**`protect`**: checks if the given `action` poses a threat to the given `causal_link`.\n",
    "If so, the threat is resolved by either promotion or demotion, whichever generates acyclic temporal constraints.\n",
    "If neither promotion or demotion work, the chosen action is not the correct fit or the planning problem cannot be solved altogether.\n",
    "<br>\n",
    "**`convert`**: converts a graph from a list of edges to an `Action` : `set` mapping, for use in topological sorting.\n",
    "<br>\n",
    "**`toposort`**: a generator function that generates a topological ordering of a given graph as a list of sets.\n",
    "Each set contains an action or several actions.\n",
    "If a set has more that one action in it, it means that permutations between those actions also produce a valid plan.\n",
    "<br>\n",
    "**`display_plan`**: displays the `causal_links`, `constraints` and the partial order plan generated from `toposort`.\n",
    "<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **`execute`** method executes the algorithm, which is summarized below:\n",
    "<br>\n",
    "1. An open precondition is selected (a sub-goal that we want to achieve).\n",
    "2. An action that fulfils the open precondition is chosen.\n",
    "3. Temporal constraints are updated.\n",
    "4. Existing causal links are protected. Protection is a method that checks if the causal links conflict\n",
    "   and if they do, temporal constraints are added to fix the threats.\n",
    "5. The set of open preconditions is updated.\n",
    "6. Temporal constraints of the selected action and the next action are established.\n",
    "7. A new causal link is added between the selected action and the owner of the open precondition.\n",
    "8. The set of new causal links is checked for threats and if found, the threat is removed by either promotion or demotion.\n",
    "   If promotion or demotion is unable to solve the problem, the planning problem cannot be solved with the current sequence of actions\n",
    "   or it may not be solvable at all.\n",
    "9. These steps are repeated until the set of open preconditions is empty."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A partial-order plan can be used to generate different valid total-order plans.\n",
    "This step is called **linearization** of the partial-order plan.\n",
    "All possible linearizations of a partial-order plan for `socks_and_shoes` looks like this.\n",
    "<br>\n",
    "![title](images/pop.jpg)\n",
    "<br>\n",
    "Linearization can be carried out in many ways, but the most efficient way is to represent the set of temporal constraints as a directed graph.\n",
    "We can easily realize that the graph should also be acyclic as cycles in constraints means that the constraints are inconsistent.\n",
    "This acyclicity is enforced by the `add_const` method, which adds a new constraint only if the acyclicity of the existing graph is not violated.\n",
    "The `protect` method also checks for acyclicity of the newly-added temporal constraints to make a decision between promotion and demotion in case of a threat.\n",
    "This property of a graph created from the temporal constraints of a valid partial-order plan allows us to use topological sort to order the constraints linearly.\n",
    "A topological sort may produce several different valid solutions for a given directed acyclic graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we know how `PartialOrderPlanner` works, let's solve a few problems using it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Causal Links\n",
      "(Action(PutOn(Spare, Axle)), At(Spare, Axle), Action(Finish))\n",
      "(Action(Start), Tire(Spare), Action(PutOn(Spare, Axle)))\n",
      "(Action(Remove(Flat, Axle)), NotAt(Flat, Axle), Action(PutOn(Spare, Axle)))\n",
      "(Action(Start), At(Flat, Axle), Action(Remove(Flat, Axle)))\n",
      "(Action(Remove(Spare, Trunk)), At(Spare, Ground), Action(PutOn(Spare, Axle)))\n",
      "(Action(Start), At(Spare, Trunk), Action(Remove(Spare, Trunk)))\n",
      "(Action(Remove(Flat, Axle)), At(Flat, Ground), Action(Finish))\n",
      "\n",
      "Constraints\n",
      "Action(Remove(Flat, Axle)) < Action(PutOn(Spare, Axle))\n",
      "Action(Start) < Action(Finish)\n",
      "Action(Remove(Spare, Trunk)) < Action(PutOn(Spare, Axle))\n",
      "Action(Start) < Action(Remove(Spare, Trunk))\n",
      "Action(Start) < Action(Remove(Flat, Axle))\n",
      "Action(Remove(Flat, Axle)) < Action(Finish)\n",
      "Action(PutOn(Spare, Axle)) < Action(Finish)\n",
      "Action(Start) < Action(PutOn(Spare, Axle))\n",
      "\n",
      "Partial Order Plan\n",
      "[{Action(Start)}, {Action(Remove(Flat, Axle)), Action(Remove(Spare, Trunk))}, {Action(PutOn(Spare, Axle))}, {Action(Finish)}]\n"
     ]
    }
   ],
   "source": [
    "st = spare_tire()\n",
    "pop = PartialOrderPlanner(st)\n",
    "pop.execute()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We observe that in the given partial order plan, Remove(Flat, Axle) and Remove(Spare, Trunk) are in the same set.\n",
    "This means that the order of performing these actions does not affect the final outcome.\n",
    "That aside, we also see that the PutOn(Spare, Axle) action has to be performed after both the Remove actions are complete, which seems logically consistent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Causal Links\n",
      "(Action(FromTable(C, B)), On(C, B), Action(Finish))\n",
      "(Action(FromTable(B, A)), On(B, A), Action(Finish))\n",
      "(Action(Start), OnTable(B), Action(FromTable(B, A)))\n",
      "(Action(Start), OnTable(C), Action(FromTable(C, B)))\n",
      "(Action(Start), Clear(C), Action(FromTable(C, B)))\n",
      "(Action(Start), Clear(A), Action(FromTable(B, A)))\n",
      "(Action(ToTable(A, B)), Clear(B), Action(FromTable(C, B)))\n",
      "(Action(Start), On(A, B), Action(ToTable(A, B)))\n",
      "(Action(ToTable(A, B)), Clear(B), Action(FromTable(B, A)))\n",
      "(Action(Start), Clear(A), Action(ToTable(A, B)))\n",
      "\n",
      "Constraints\n",
      "Action(Start) < Action(FromTable(C, B))\n",
      "Action(FromTable(B, A)) < Action(FromTable(C, B))\n",
      "Action(Start) < Action(FromTable(B, A))\n",
      "Action(Start) < Action(ToTable(A, B))\n",
      "Action(Start) < Action(Finish)\n",
      "Action(FromTable(B, A)) < Action(Finish)\n",
      "Action(FromTable(C, B)) < Action(Finish)\n",
      "Action(ToTable(A, B)) < Action(FromTable(B, A))\n",
      "Action(ToTable(A, B)) < Action(FromTable(C, B))\n",
      "\n",
      "Partial Order Plan\n",
      "[{Action(Start)}, {Action(ToTable(A, B))}, {Action(FromTable(B, A))}, {Action(FromTable(C, B))}, {Action(Finish)}]\n"
     ]
    }
   ],
   "source": [
    "sbw = simple_blocks_world()\n",
    "pop = PartialOrderPlanner(sbw)\n",
    "pop.execute()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We see that this plan does not have flexibility in selecting actions, ie, actions should be performed in this order and this order only, to successfully reach the goal state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Causal Links\n",
      "(Action(RightShoe), RightShoeOn, Action(Finish))\n",
      "(Action(LeftShoe), LeftShoeOn, Action(Finish))\n",
      "(Action(LeftSock), LeftSockOn, Action(LeftShoe))\n",
      "(Action(RightSock), RightSockOn, Action(RightShoe))\n",
      "\n",
      "Constraints\n",
      "Action(LeftSock) < Action(LeftShoe)\n",
      "Action(RightSock) < Action(RightShoe)\n",
      "Action(Start) < Action(RightShoe)\n",
      "Action(Start) < Action(Finish)\n",
      "Action(LeftShoe) < Action(Finish)\n",
      "Action(Start) < Action(RightSock)\n",
      "Action(Start) < Action(LeftShoe)\n",
      "Action(Start) < Action(LeftSock)\n",
      "Action(RightShoe) < Action(Finish)\n",
      "\n",
      "Partial Order Plan\n",
      "[{Action(Start)}, {Action(LeftSock), Action(RightSock)}, {Action(LeftShoe), Action(RightShoe)}, {Action(Finish)}]\n"
     ]
    }
   ],
   "source": [
    "ss = socks_and_shoes()\n",
    "pop = PartialOrderPlanner(ss)\n",
    "pop.execute()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "This plan again doesn't have constraints in selecting socks or shoes.\n",
    "As long as both socks are worn before both shoes, we are fine.\n",
    "Notice however, there is one valid solution,\n",
    "<br>\n",
    "LeftSock -> LeftShoe -> RightSock -> RightShoe\n",
    "<br>\n",
    "that the algorithm could not find as it cannot be represented as a general partially-ordered plan but is a specific total-order solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Runtime differences\n",
    "Let's briefly take a look at the running time of all the three algorithms on the `socks_and_shoes` problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "ss = socks_and_shoes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "198 µs ± 3.53 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "GraphPlan(ss).execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "844 µs ± 23.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "Linearize(ss).execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "258 µs ± 4.03 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "PartialOrderPlanner(ss).execute(display=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We observe that `GraphPlan` is about 4 times faster than `Linearize` because `Linearize` essentially runs a `GraphPlan` subroutine under the hood and then carries out some transformations on the solved planning-graph.\n",
    "<br>\n",
    "We also find that `GraphPlan` is slightly faster than `PartialOrderPlanner`, but this is mainly due to the `expand_actions` method in `PartialOrderPlanner` that slows it down as it generates all possible permutations of actions and variable bindings.\n",
    "<br>\n",
    "Without heuristic functions, `PartialOrderPlanner` will be atleast as fast as `GraphPlan`, if not faster, but will have a higher tendency to encounter threats and conflicts which might take additional time to resolve.\n",
    "<br>\n",
    "Different planning algorithms work differently for different problems."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}