planning_angelic_search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Angelic Search \n",
    "\n",
    "Search using angelic semantics (is a hierarchical search), where the agent chooses the implementation of the HLA's. <br>\n",
    "The algorithms input is: problem, hierarchy and initialPlan\n",
    "-  problem is of type Problem \n",
    "-  hierarchy is a dictionary consisting of all the actions. \n",
    "-  initialPlan is an approximate description(optimistic and pessimistic) of the agents choices for the implementation. <br>\n",
    "   initialPlan contains a sequence of HLA's with angelic semantics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from planning import * \n",
    "from notebook import psource"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Angelic search algorithm consists of three parts. \n",
    "-  Search using angelic semantics\n",
    "-  Decompose\n",
    "-  a search in the space of refinements, in a similar way with hierarchical search\n",
    "\n",
    "### Searching using angelic semantics\n",
    "-  Find the reachable set (optimistic and pessimistic) of the sequence of angelic HLA in initialPlan\n",
    "  -    If the optimistic reachable set doesn't intersect the goal, then there is no solution\n",
    "  -    If the pessimistic reachable set intersects the goal, then we call decompose, in order to find the sequence of actions that lead us to the goal. \n",
    "  -    If the optimistic reachable set intersects the goal, but the pessimistic doesn't we do some further refinements, in order to see if there is a sequence of actions that achieves the goal. \n",
    "  \n",
    "### Search in space of refinements\n",
    "-  Create a search tree, that has root the action and children it's refinements\n",
    "-  Extend frontier by adding each refinement, so that we keep looping till we find all primitive actions\n",
    "-  If we achieve that we return the path of the solution (search tree), else there is no solution and we return None.\n",
    "\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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\">angelic_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"n\">initialPlan</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">\t[Figure 11.8] A hierarchical planning algorithm that uses angelic semantics to identify and</span>\n",
       "<span class=\"sd\">\tcommit to high-level plans that work while avoiding high-level plans that don’t. </span>\n",
       "<span class=\"sd\">\tThe predicate MAKING-PROGRESS checks to make sure that we aren’t stuck in an infinite regression</span>\n",
       "<span class=\"sd\">\tof refinements. </span>\n",
       "<span class=\"sd\">\tAt top level, call ANGELIC -SEARCH with [Act ] as the initialPlan .</span>\n",
       "\n",
       "<span class=\"sd\">        initialPlan contains a sequence of HLA&#39;s with angelic semantics </span>\n",
       "\n",
       "<span class=\"sd\">        The possible effects of an angelic HLA in initialPlan are : </span>\n",
       "<span class=\"sd\">        ~ : effect remove</span>\n",
       "<span class=\"sd\">        $+: effect possibly add</span>\n",
       "<span class=\"sd\">        $-: effect possibly remove</span>\n",
       "<span class=\"sd\">        $$: possibly add or remove</span>\n",
       "<span class=\"sd\">\t&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">frontier</span> <span class=\"o\">=</span> <span class=\"n\">deque</span><span class=\"p\">(</span><span class=\"n\">initialPlan</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> <span class=\"c1\"># sequence of HLA/Angelic HLA&#39;s </span>\n",
       "            <span class=\"n\">opt_reachable_set</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">reach_opt</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\">plan</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">pes_reachable_set</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">reach_pes</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\">plan</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">intersects_goal</span><span class=\"p\">(</span><span class=\"n\">opt_reachable_set</span><span class=\"p\">):</span> \n",
       "                <span class=\"k\">if</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">is_primitive</span><span class=\"p\">(</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span> <span class=\"p\">):</span> \n",
       "                    <span class=\"k\">return</span> <span class=\"p\">([</span><span class=\"n\">x</span> <span class=\"k\">for</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">])</span>\n",
       "                <span class=\"n\">guaranteed</span> <span class=\"o\">=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">intersects_goal</span><span class=\"p\">(</span><span class=\"n\">pes_reachable_set</span><span class=\"p\">)</span> \n",
       "                <span class=\"k\">if</span> <span class=\"n\">guaranteed</span> <span class=\"ow\">and</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">making_progress</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">initialPlan</span><span class=\"p\">):</span>\n",
       "                    <span class=\"n\">final_state</span> <span class=\"o\">=</span> <span class=\"n\">guaranteed</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"c1\"># any element of guaranteed </span>\n",
       "                    <span class=\"c1\">#print(&#39;decompose&#39;)</span>\n",
       "                    <span class=\"k\">return</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">decompose</span><span class=\"p\">(</span><span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">final_state</span><span class=\"p\">,</span> <span class=\"n\">pes_reachable_set</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\"># there should be at least one HLA/Angelic_HLA, otherwise plan would be primitive.</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\">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=\"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=\"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\">Angelic_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> <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.angelic_search)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Decompose \n",
    "-  Finds recursively the sequence of states and actions that lead us from initial state to goal.\n",
    "-  For each of the above actions we find their refinements,if they are not primitive, by calling the angelic_search function. \n",
    "   If there are not refinements return None\n",
    "   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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\">decompose</span><span class=\"p\">(</span><span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"n\">s_0</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">s_f</span><span class=\"p\">,</span> <span class=\"n\">reachable_set</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">solution</span> <span class=\"o\">=</span> <span class=\"p\">[]</span> \n",
       "        <span class=\"n\">i</span> <span class=\"o\">=</span> <span class=\"nb\">max</span><span class=\"p\">(</span><span class=\"n\">reachable_set</span><span class=\"o\">.</span><span class=\"n\">keys</span><span class=\"p\">())</span>\n",
       "        <span class=\"k\">while</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action_pes</span><span class=\"p\">:</span> \n",
       "            <span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action_pes</span><span class=\"o\">.</span><span class=\"n\">pop</span><span class=\"p\">()</span>\n",
       "            <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"n\">i</span><span class=\"o\">==</span><span class=\"mi\">0</span><span class=\"p\">):</span> \n",
       "                <span class=\"k\">return</span> <span class=\"n\">solution</span>\n",
       "            <span class=\"n\">s_i</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">find_previous_state</span><span class=\"p\">(</span><span class=\"n\">s_f</span><span class=\"p\">,</span> <span class=\"n\">reachable_set</span><span class=\"p\">,</span><span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">)</span> \n",
       "            <span class=\"n\">problem</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"p\">(</span><span class=\"n\">s_i</span><span class=\"p\">,</span> <span class=\"n\">s_f</span> <span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">angelic_call</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">angelic_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"p\">[</span><span class=\"n\">Angelic_Node</span><span class=\"p\">(</span><span class=\"n\">s_i</span><span class=\"p\">,</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"bp\">None</span><span class=\"p\">),</span> <span class=\"p\">[</span><span class=\"n\">action</span><span class=\"p\">],[</span><span class=\"n\">action</span><span class=\"p\">])])</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">angelic_call</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">for</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"n\">angelic_call</span><span class=\"p\">:</span> \n",
       "                    <span class=\"n\">solution</span><span class=\"o\">.</span><span class=\"n\">insert</span><span class=\"p\">(</span><span class=\"mi\">0</span><span class=\"p\">,</span><span class=\"n\">x</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span> \n",
       "                <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",
       "            <span class=\"n\">s_f</span> <span class=\"o\">=</span> <span class=\"n\">s_i</span>\n",
       "            <span class=\"n\">i</span><span class=\"o\">-=</span><span class=\"mi\">1</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">solution</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(Problem.decompose)"
   ]
  },
  {
   "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": 4,
   "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": 5,
   "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": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "prob = Problem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO, taxi_SFO, drive_SFOLongTermParking,shuttle_SFO])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An agent gives us some approximate information about the plan we will follow: <br>\n",
    "(initialPlan is an Angelic Node, where: \n",
    "-    state is the initial state of the problem, \n",
    "-    parent is None \n",
    "-    action: is a list of actions (Angelic HLA's) with the optimistic estimators of effects and \n",
    "-    action_pes: is a list of actions (Angelic HLA's) with the pessimistic approximations of the effects\n",
    "##### InitialPlan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "angelic_opt_description = Angelic_HLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & $-At(Home)' ) \n",
    "angelic_pes_description = Angelic_HLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & ~At(Home)' )\n",
    "\n",
    "initialPlan = [Angelic_Node(prob.init, None, [angelic_opt_description], [angelic_pes_description])] \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to find the optimistic and pessimistic reachable set of initialPlan when applied to the problem:\n",
    "##### Optimistic/Pessimistic reachable set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[At(Home), Have(Cash), Have(Car)], [Have(Cash), Have(Car), At(SFO), NotAt(Home)], [Have(Cash), Have(Car), NotAt(Home)], [At(Home), Have(Cash), Have(Car), At(SFO)], [At(Home), Have(Cash), Have(Car)]] \n",
      "\n",
      "[[At(Home), Have(Cash), Have(Car)], [Have(Cash), Have(Car), At(SFO), NotAt(Home)], [Have(Cash), Have(Car), NotAt(Home)]]\n"
     ]
    }
   ],
   "source": [
    "opt_reachable_set = Problem.reach_opt(prob.init, initialPlan[0])\n",
    "pes_reachable_set = Problem.reach_pes(prob.init, initialPlan[0])\n",
    "print([x for y in opt_reachable_set.keys() for x in opt_reachable_set[y]], '\\n')\n",
    "print([x for y in pes_reachable_set.keys() for x in pes_reachable_set[y]])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Refinements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))]\n",
      "[{'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'args': (Home, SFOLongTermParking), 'uses': {}, 'consumes': {}, 'name': 'Drive', 'completed': False, 'precond': [At(Home), Have(Car)]}, {'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'args': (SFOLongTermParking, SFO), 'uses': {}, 'consumes': {}, 'name': 'Shuttle', 'completed': False, 'precond': [At(SFOLongTermParking)]}] \n",
      "\n",
      "[HLA(Taxi(Home, SFO))]\n",
      "[{'duration': 0, 'effect': [At(SFO), NotAt(Home), NotHave(Cash)], 'args': (Home, SFO), 'uses': {}, 'consumes': {}, 'name': 'Taxi', 'completed': False, '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 angelic search\n",
    "##### Top level call"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))] \n",
      "\n",
      "[{'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'args': (Home, SFOLongTermParking), 'uses': {}, 'consumes': {}, 'name': 'Drive', 'completed': False, 'precond': [At(Home), Have(Car)]}, {'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'args': (SFOLongTermParking, SFO), 'uses': {}, 'consumes': {}, 'name': 'Shuttle', 'completed': False, 'precond': [At(SFOLongTermParking)]}]\n"
     ]
    }
   ],
   "source": [
    "plan= Problem.angelic_search(prob, library, initialPlan)\n",
    "print (plan, '\\n')\n",
    "print ([x.__dict__ for x in plan])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Bus(Home, MetroStop)), HLA(Metro1(MetroStop, SFO))] \n",
      "\n",
      "[{'duration': 0, 'effect': [At(MetroStop), NotAt(Home)], 'args': (Home, MetroStop), 'uses': {}, 'consumes': {}, 'name': 'Bus', 'completed': False, 'precond': [At(Home)]}, {'duration': 0, 'effect': [At(SFO), NotAt(MetroStop)], 'args': (MetroStop, SFO), 'uses': {}, 'consumes': {}, 'name': 'Metro1', 'completed': False, 'precond': [At(MetroStop)]}]\n"
     ]
    }
   ],
   "source": [
    "plan_2 = Problem.angelic_search(prob, library_2, initialPlan)\n",
    "print(plan_2, '\\n')\n",
    "print([x.__dict__ for x in plan_2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 3 \n",
    "\n",
    "Sometimes there is no plan that achieves the goal!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "library_3 = {\n",
    "        'HLA': ['Shuttle(SFOLongTermParking, SFO)', 'Go(Home, SFOLongTermParking)', 'Taxi(Home, SFOLongTermParking)', 'Drive(Home, SFOLongTermParking)', 'Drive(SFOLongTermParking, Home)', 'Get(Cash)', 'Go(Home, ATM)'],\n",
    "        'steps': [['Get(Cash)', 'Go(Home, SFOLongTermParking)'], ['Taxi(Home, SFOLongTermParking)'], [], [], [], ['Drive(SFOLongTermParking, Home)', 'Go(Home, ATM)'], []],\n",
    "        'precond': [['At(SFOLongTermParking)'], ['At(Home)'], ['At(Home) & Have(Cash)'], ['At(Home)'],  ['At(SFOLongTermParking)'], ['At(SFOLongTermParking)'], ['At(Home)']],\n",
    "        'effect': [['At(SFO)'], ['At(SFO)'], ['At(SFOLongTermParking) & ~Have(Cash)'], ['At(SFOLongTermParking)'] ,['At(Home) & ~At(SFOLongTermParking)'], ['At(Home) & Have(Cash)'], ['Have(Cash)'] ]\n",
    "        }\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "shuttle_SFO = HLA('Shuttle(SFOLongTermParking, SFO)', 'Have(Cash) & At(SFOLongTermParking)', 'At(SFO)')\n",
    "prob_3 = Problem('At(SFOLongTermParking) & Have(Cash)', 'At(SFO) & Have(Cash)', [shuttle_SFO])\n",
    "# optimistic/pessimistic descriptions\n",
    "angelic_opt_description = Angelic_HLA('Shuttle(SFOLongTermParking, SFO)', precond = 'At(SFOLongTermParking)', effect ='$+At(SFO) & $-At(SFOLongTermParking)' ) \n",
    "angelic_pes_description = Angelic_HLA('Shuttle(SFOLongTermParking, SFO)', precond = 'At(SFOLongTermParking)', effect ='$+At(SFO) & ~At(SFOLongTermParking)' ) \n",
    "# initial Plan\n",
    "initialPlan_3 = [Angelic_Node(prob.init, None, [angelic_opt_description], [angelic_pes_description])] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "plan_3 = prob_3.angelic_search(library_3, initialPlan_3)\n",
    "print(plan_3)"
   ]
  }
 ],
 "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
}