planning_hierarchical_search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hierarchical Search \n",
    "\n",
    "Hierarchical search is a a planning algorithm in high level of abstraction. <br>\n",
    "Instead of actions as in classical planning (chapter 10) (primitive actions) we now use high level actions (HLAs) (see planning.ipynb) <br>\n",
    "\n",
    "## Refinements\n",
    "\n",
    "Each __HLA__ has one or more refinements into a sequence of actions, each of which may be an HLA or a primitive action (which has no refinements by definition).<br>\n",
    "For example:\n",
    "-  (a) the high level action \"Go to San Fransisco airport\" (Go(Home, SFO)), might have two possible refinements, \"Drive to San Fransisco airport\" and \"Taxi to San Fransisco airport\". \n",
    "<br>\n",
    "-  (b) A recursive refinement for navigation in the vacuum world would be: to get to a\n",
    "destination, take a step, and then go to the destination.\n",
    "<br>\n",
    "![title](images/refinement.png)\n",
    "<br>\n",
    "-  __implementation__: An HLA refinement that contains only primitive actions is called an implementation of the HLA\n",
    "-  An implementation of a high-level plan (a sequence of HLAs) is the concatenation of implementations of each HLA in the sequence\n",
    "- A high-level plan __achieves the goal__ from a given state if at least one of its implementations achieves the goal from that state\n",
    "<br>\n",
    "\n",
    "The refinements function input is: \n",
    "-  __hla__: the HLA of which we want to compute its refinements\n",
    "- __state__: the knoweledge base of the current problem (Problem.init)\n",
    "- __library__: the hierarchy of the actions in the planning problem\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from planning import * \n",
    "from notebook import psource"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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\">def</span> <span class=\"nf\">refinements</span><span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">library</span><span class=\"p\">):</span>  <span class=\"c1\"># refinements may be (multiple) HLA themselves ...</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">        state is a Problem, containing the current state kb</span>\n",
       "<span class=\"sd\">        library is a dictionary containing details for every possible refinement. eg:</span>\n",
       "<span class=\"sd\">        {</span>\n",
       "<span class=\"sd\">        &#39;HLA&#39;: [</span>\n",
       "<span class=\"sd\">            &#39;Go(Home, SFO)&#39;,</span>\n",
       "<span class=\"sd\">            &#39;Go(Home, SFO)&#39;,</span>\n",
       "<span class=\"sd\">            &#39;Drive(Home, SFOLongTermParking)&#39;,</span>\n",
       "<span class=\"sd\">            &#39;Shuttle(SFOLongTermParking, SFO)&#39;,</span>\n",
       "<span class=\"sd\">            &#39;Taxi(Home, SFO)&#39;</span>\n",
       "<span class=\"sd\">            ],</span>\n",
       "<span class=\"sd\">        &#39;steps&#39;: [</span>\n",
       "<span class=\"sd\">            [&#39;Drive(Home, SFOLongTermParking)&#39;, &#39;Shuttle(SFOLongTermParking, SFO)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;Taxi(Home, SFO)&#39;],</span>\n",
       "<span class=\"sd\">            [],</span>\n",
       "<span class=\"sd\">            [],</span>\n",
       "<span class=\"sd\">            []</span>\n",
       "<span class=\"sd\">            ],</span>\n",
       "<span class=\"sd\">        # empty refinements indicate a primitive action</span>\n",
       "<span class=\"sd\">        &#39;precond&#39;: [</span>\n",
       "<span class=\"sd\">            [&#39;At(Home) &amp; Have(Car)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(Home)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(Home) &amp; Have(Car)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(SFOLongTermParking)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(Home)&#39;]</span>\n",
       "<span class=\"sd\">            ],</span>\n",
       "<span class=\"sd\">        &#39;effect&#39;: [</span>\n",
       "<span class=\"sd\">            [&#39;At(SFO) &amp; ~At(Home)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(SFO) &amp; ~At(Home)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(SFOLongTermParking) &amp; ~At(Home)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(SFO) &amp; ~At(SFOLongTermParking)&#39;],</span>\n",
       "<span class=\"sd\">            [&#39;At(SFO) &amp; ~At(Home)&#39;]</span>\n",
       "<span class=\"sd\">            ]</span>\n",
       "<span class=\"sd\">        }</span>\n",
       "<span class=\"sd\">        &quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">e</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"n\">hla</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">indices</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">i</span> <span class=\"k\">for</span> <span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"nb\">enumerate</span><span class=\"p\">(</span><span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;HLA&#39;</span><span class=\"p\">])</span> <span class=\"k\">if</span> <span class=\"n\">expr</span><span class=\"p\">(</span><span class=\"n\">x</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">op</span> <span class=\"o\">==</span> <span class=\"n\">hla</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">]</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"n\">indices</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">actions</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">j</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;steps&#39;</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">])):</span>\n",
       "                <span class=\"c1\"># find the index of the step [j]  of the HLA </span>\n",
       "                <span class=\"n\">index_step</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">k</span> <span class=\"k\">for</span> <span class=\"n\">k</span><span class=\"p\">,</span><span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"nb\">enumerate</span><span class=\"p\">(</span><span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;HLA&#39;</span><span class=\"p\">])</span> <span class=\"k\">if</span> <span class=\"n\">x</span> <span class=\"o\">==</span> <span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;steps&#39;</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">][</span><span class=\"n\">j</span><span class=\"p\">]][</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
       "                <span class=\"n\">precond</span> <span class=\"o\">=</span> <span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;precond&#39;</span><span class=\"p\">][</span><span class=\"n\">index_step</span><span class=\"p\">][</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"c1\"># preconditions of step [j]</span>\n",
       "                <span class=\"n\">effect</span> <span class=\"o\">=</span> <span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;effect&#39;</span><span class=\"p\">][</span><span class=\"n\">index_step</span><span class=\"p\">][</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"c1\"># effect of step [j]</span>\n",
       "                <span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">&#39;steps&#39;</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">][</span><span class=\"n\">j</span><span class=\"p\">],</span> <span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"p\">))</span>\n",
       "            <span class=\"k\">yield</span> <span class=\"n\">actions</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(Problem.refinements)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hierarchical search \n",
    "\n",
    "Hierarchical search is a breadth-first implementation of hierarchical forward planning search in the space of refinements. (i.e. repeatedly choose an HLA in the current plan and replace it with one of its refinements, until the plan achieves the goal.) \n",
    "\n",
    "<br>\n",
    "The algorithms input is: problem and hierarchy\n",
    "-  __problem__: is of type Problem \n",
    "-  __hierarchy__: is a dictionary consisting of all the actions and the order in which they are performed. \n",
    "<br>\n",
    "\n",
    "In top level call, initialPlan contains [act] (i.e. is the action to be performed)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "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\">def</span> <span class=\"nf\">hierarchical_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">        [Figure 11.5] &#39;Hierarchical Search, a Breadth First Search implementation of Hierarchical</span>\n",
       "<span class=\"sd\">        Forward Planning Search&#39;</span>\n",
       "<span class=\"sd\">        The problem is a real-world problem defined by the problem class, and the hierarchy is</span>\n",
       "<span class=\"sd\">        a dictionary of HLA - refinements (see refinements generator for details)</span>\n",
       "<span class=\"sd\">        &quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">act</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"p\">[</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]])</span>\n",
       "        <span class=\"n\">frontier</span> <span class=\"o\">=</span> <span class=\"n\">deque</span><span class=\"p\">()</span>\n",
       "        <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">act</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">frontier</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",
       "            <span class=\"n\">plan</span> <span class=\"o\">=</span> <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">popleft</span><span class=\"p\">()</span>\n",
       "            <span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">index</span><span class=\"p\">)</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">find_hla</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">)</span> <span class=\"c1\"># finds the first non primitive hla in plan actions</span>\n",
       "            <span class=\"n\">prefix</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">[:</span><span class=\"n\">index</span><span class=\"p\">]</span>\n",
       "            <span class=\"n\">outcome</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"p\">(</span><span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">result</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">prefix</span><span class=\"p\">),</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">goals</span> <span class=\"p\">,</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">actions</span> <span class=\"p\">)</span>\n",
       "            <span class=\"n\">suffix</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">[</span><span class=\"n\">index</span><span class=\"o\">+</span><span class=\"mi\">1</span><span class=\"p\">:]</span>\n",
       "            <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">hla</span><span class=\"p\">:</span> <span class=\"c1\"># hla is None and plan is primitive</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">outcome</span><span class=\"o\">.</span><span class=\"n\">goal_test</span><span class=\"p\">():</span>\n",
       "                    <span class=\"k\">return</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">for</span> <span class=\"n\">sequence</span> <span class=\"ow\">in</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">refinements</span><span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">outcome</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">):</span> <span class=\"c1\"># find refinements</span>\n",
       "                    <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">outcome</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">prefix</span> <span class=\"o\">+</span> <span class=\"n\">sequence</span><span class=\"o\">+</span> <span class=\"n\">suffix</span><span class=\"p\">))</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(Problem.hierarchical_search)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "Suppose that somebody wants to get to the airport. \n",
    "The possible ways to do so is either get a taxi, or drive to the airport. <br>\n",
    "Those two actions have some preconditions and some effects. \n",
    "If you get the taxi, you need to have cash, whereas if you drive you need to have a car. <br>\n",
    "Thus we define the following hierarchy of possible actions.\n",
    "\n",
    "##### hierarchy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "library = {\n",
    "        'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)', 'Taxi(Home, SFO)'],\n",
    "        'steps': [['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)'], [], [], []],\n",
    "        'precond': [['At(Home) & Have(Car)'], ['At(Home)'], ['At(Home) & Have(Car)'], ['At(SFOLongTermParking)'], ['At(Home)']],\n",
    "        'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(SFOLongTermParking) & ~At(Home)'], ['At(SFO) & ~At(LongTermParking)'], ['At(SFO) & ~At(Home) & ~Have(Cash)']] }\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "the possible actions are the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "go_SFO = HLA('Go(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')\n",
    "taxi_SFO = HLA('Taxi(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home) & ~Have(Cash)')\n",
    "drive_SFOLongTermParking = HLA('Drive(Home, SFOLongTermParking)', 'At(Home) & Have(Car)','At(SFOLongTermParking) & ~At(Home)' )\n",
    "shuttle_SFO = HLA('Shuttle(SFOLongTermParking, SFO)', 'At(SFOLongTermParking)', 'At(SFO) & ~At(LongTermParking)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that (our preconditionds are that) we are Home and we have cash and car and  our goal is to get to SFO and maintain our cash, and our possible actions are the above. <br>\n",
    "##### Then our problem is: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "prob = Problem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Refinements\n",
    "\n",
    "The refinements of the action Go(Home, SFO), are defined as: <br>\n",
    "['Drive(Home,SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))]\n",
      "[{'completed': False, 'args': (Home, SFOLongTermParking), 'name': 'Drive', 'uses': {}, 'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'consumes': {}, 'precond': [At(Home), Have(Car)]}, {'completed': False, 'args': (SFOLongTermParking, SFO), 'name': 'Shuttle', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'consumes': {}, 'precond': [At(SFOLongTermParking)]}] \n",
      "\n",
      "[HLA(Taxi(Home, SFO))]\n",
      "[{'completed': False, 'args': (Home, SFO), 'name': 'Taxi', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(Home), NotHave(Cash)], 'consumes': {}, 'precond': [At(Home)]}] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "for sequence in Problem.refinements(go_SFO, prob, library):\n",
    "    print (sequence)\n",
    "    print([x.__dict__ for x in sequence ], '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the hierarchical search\n",
    "##### Top level call"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))] \n",
      "\n",
      "[{'completed': False, 'args': (Home, SFOLongTermParking), 'name': 'Drive', 'uses': {}, 'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'consumes': {}, 'precond': [At(Home), Have(Car)]}, {'completed': False, 'args': (SFOLongTermParking, SFO), 'name': 'Shuttle', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'consumes': {}, 'precond': [At(SFOLongTermParking)]}]\n"
     ]
    }
   ],
   "source": [
    "plan= Problem.hierarchical_search(prob, library)\n",
    "print (plan, '\\n')\n",
    "print ([x.__dict__ for x in plan])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "library_2 = {\n",
    "        'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)' , 'Metro(MetroStop, SFO)', 'Metro1(MetroStop, SFO)', 'Metro2(MetroStop, SFO)'  ,'Taxi(Home, SFO)'],\n",
    "        'steps': [['Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)'], ['Taxi(Home, SFO)'], [], ['Metro1(MetroStop, SFO)'], ['Metro2(MetroStop, SFO)'],[],[],[]],\n",
    "        'precond': [['At(Home)'], ['At(Home)'], ['At(Home)'], ['At(MetroStop)'], ['At(MetroStop)'],['At(MetroStop)'], ['At(MetroStop)'] ,['At(Home) & Have(Cash)']],\n",
    "        'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(MetroStop) & ~At(Home)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'] , ['At(SFO) & ~At(MetroStop)'] ,['At(SFO) & ~At(Home) & ~Have(Cash)']] \n",
    "        }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Bus(Home, MetroStop)), HLA(Metro1(MetroStop, SFO))] \n",
      "\n",
      "[{'completed': False, 'args': (Home, MetroStop), 'name': 'Bus', 'uses': {}, 'duration': 0, 'effect': [At(MetroStop), NotAt(Home)], 'consumes': {}, 'precond': [At(Home)]}, {'completed': False, 'args': (MetroStop, SFO), 'name': 'Metro1', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(MetroStop)], 'consumes': {}, 'precond': [At(MetroStop)]}]\n"
     ]
    }
   ],
   "source": [
    "plan_2 = Problem.hierarchical_search(prob, library_2)\n",
    "print(plan_2, '\\n')\n",
    "print([x.__dict__ for x in plan_2])"
   ]
  }
 ],
 "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
}