planning_total_order_planner.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TOTAL ORDER PLANNER\n",
    "\n",
    "In mathematical terminology, **total order**, **linear order** or **simple order** refers to a set *X* which is said to be totally ordered under &le; if the following statements hold for all *a*, *b* and *c* in *X*:\n",
    "<br>\n",
    "If *a* &le; *b* and *b* &le; *a*, then *a* = *b* (antisymmetry).\n",
    "<br>\n",
    "If *a* &le; *b* and *b* &le; *c*, then *a* &le; *c* (transitivity).\n",
    "<br>\n",
    "*a* &le; *b* or *b* &le; *a* (connex relation).\n",
    "\n",
    "<br>\n",
    "In simpler terms, a total order plan is a linear ordering of actions to be taken to reach the goal state.\n",
    "There may be several different total-order plans for a particular goal depending on the problem.\n",
    "<br>\n",
    "<br>\n",
    "In the module, the `Linearize` class solves problems using this paradigm.\n",
    "At its core, the `Linearize` uses a solved planning graph from `GraphPlan` and finds a valid total-order solution for it.\n",
    "Let's have a look at the class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from planning import *\n",
    "from notebook import psource"
   ]
  },
  {
   "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\">class</span> <span class=\"nc\">Linearize</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",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">filter</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">solution</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Filter out persistence actions from a solution&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">new_solution</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">section</span> <span class=\"ow\">in</span> <span class=\"n\">solution</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]:</span>\n",
       "            <span class=\"n\">new_section</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">operation</span> <span class=\"ow\">in</span> <span class=\"n\">section</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"p\">(</span><span class=\"n\">operation</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"s1\">&#39;P&#39;</span> <span class=\"ow\">and</span> <span class=\"n\">operation</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]</span><span class=\"o\">.</span><span class=\"n\">isupper</span><span class=\"p\">()):</span>\n",
       "                    <span class=\"n\">new_section</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">operation</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">new_solution</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_section</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">new_solution</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">orderlevel</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">level</span><span class=\"p\">,</span> <span class=\"n\">planningproblem</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Return valid linear order of actions for a given level&quot;&quot;&quot;</span>\n",
       "\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\">level</span><span class=\"p\">):</span>\n",
       "            <span class=\"n\">temp</span> <span class=\"o\">=</span> <span class=\"n\">copy</span><span class=\"o\">.</span><span class=\"n\">deepcopy</span><span class=\"p\">(</span><span class=\"n\">planningproblem</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">count</span> <span class=\"o\">=</span> <span class=\"mi\">0</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"n\">permutation</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">try</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">temp</span><span class=\"o\">.</span><span class=\"n\">act</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
       "                    <span class=\"n\">count</span> <span class=\"o\">+=</span> <span class=\"mi\">1</span>\n",
       "                <span class=\"k\">except</span><span class=\"p\">:</span>\n",
       "                    <span class=\"n\">count</span> <span class=\"o\">=</span> <span class=\"mi\">0</span>\n",
       "                    <span class=\"n\">temp</span> <span class=\"o\">=</span> <span class=\"n\">copy</span><span class=\"o\">.</span><span class=\"n\">deepcopy</span><span class=\"p\">(</span><span class=\"n\">planningproblem</span><span class=\"p\">)</span>\n",
       "                    <span class=\"k\">break</span>\n",
       "            <span class=\"k\">if</span> <span class=\"n\">count</span> <span class=\"o\">==</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">permutation</span><span class=\"p\">):</span>\n",
       "                <span class=\"k\">return</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"n\">permutation</span><span class=\"p\">),</span> <span class=\"n\">temp</span>\n",
       "        <span class=\"k\">return</span> <span class=\"bp\">None</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>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Finds total-order solution for a planning graph&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"n\">graphplan_solution</span> <span class=\"o\">=</span> <span class=\"n\">GraphPlan</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">execute</span><span class=\"p\">()</span>\n",
       "        <span class=\"n\">filtered_solution</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">filter</span><span class=\"p\">(</span><span class=\"n\">graphplan_solution</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">ordered_solution</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
       "        <span class=\"n\">planningproblem</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">planningproblem</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">level</span> <span class=\"ow\">in</span> <span class=\"n\">filtered_solution</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">level_solution</span><span class=\"p\">,</span> <span class=\"n\">planningproblem</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">orderlevel</span><span class=\"p\">(</span><span class=\"n\">level</span><span class=\"p\">,</span> <span class=\"n\">planningproblem</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"n\">level_solution</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">ordered_solution</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">element</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"k\">return</span> <span class=\"n\">ordered_solution</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(Linearize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `filter` method removes the persistence actions (if any) from the planning graph representation.\n",
    "<br>\n",
    "The `orderlevel` method finds a valid total-ordering of a specified level of the planning-graph, given the state of the graph after the previous level.\n",
    "<br>\n",
    "The `execute` method sequentially calls `orderlevel` for all the levels in the planning-graph and returns the final total-order solution.\n",
    "<br>\n",
    "<br>\n",
    "Let's look at some examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Load(C1, P1, SFO),\n",
       " Fly(P1, SFO, JFK),\n",
       " Load(C2, P2, JFK),\n",
       " Fly(P2, JFK, SFO),\n",
       " Unload(C2, P2, SFO),\n",
       " Unload(C1, P1, JFK)]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# total-order solution for air_cargo problem\n",
    "Linearize(air_cargo()).execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Remove(Spare, Trunk), Remove(Flat, Axle), PutOn(Spare, Axle)]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# total-order solution for spare_tire problem\n",
    "Linearize(spare_tire()).execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[MoveToTable(C, A), Move(B, Table, C), Move(A, Table, B)]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# total-order solution for three_block_tower problem\n",
    "Linearize(three_block_tower()).execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ToTable(A, B), FromTable(B, A), FromTable(C, B)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# total-order solution for simple_blocks_world problem\n",
    "Linearize(simple_blocks_world()).execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[RightSock, LeftSock, RightShoe, LeftShoe]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# total-order solution for socks_and_shoes problem\n",
    "Linearize(socks_and_shoes()).execute()"
   ]
  }
 ],
 "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
}