{ "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 ≤ if the following statements hold for all *a*, *b* and *c* in *X*:\n", "
\n", "If *a* ≤ *b* and *b* ≤ *a*, then *a* = *b* (antisymmetry).\n", "
\n", "If *a* ≤ *b* and *b* ≤ *c*, then *a* ≤ *c* (transitivity).\n", "
\n", "*a* ≤ *b* or *b* ≤ *a* (connex relation).\n", "\n", "
\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", "
\n", "
\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": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
class Linearize:\n",
       "\n",
       "    def __init__(self, planningproblem):\n",
       "        self.planningproblem = planningproblem\n",
       "\n",
       "    def filter(self, solution):\n",
       "        """Filter out persistence actions from a solution"""\n",
       "\n",
       "        new_solution = []\n",
       "        for section in solution[0]:\n",
       "            new_section = []\n",
       "            for operation in section:\n",
       "                if not (operation.op[0] == 'P' and operation.op[1].isupper()):\n",
       "                    new_section.append(operation)\n",
       "            new_solution.append(new_section)\n",
       "        return new_solution\n",
       "\n",
       "    def orderlevel(self, level, planningproblem):\n",
       "        """Return valid linear order of actions for a given level"""\n",
       "\n",
       "        for permutation in itertools.permutations(level):\n",
       "            temp = copy.deepcopy(planningproblem)\n",
       "            count = 0\n",
       "            for action in permutation:\n",
       "                try:\n",
       "                    temp.act(action)\n",
       "                    count += 1\n",
       "                except:\n",
       "                    count = 0\n",
       "                    temp = copy.deepcopy(planningproblem)\n",
       "                    break\n",
       "            if count == len(permutation):\n",
       "                return list(permutation), temp\n",
       "        return None\n",
       "\n",
       "    def execute(self):\n",
       "        """Finds total-order solution for a planning graph"""\n",
       "\n",
       "        graphplan_solution = GraphPlan(self.planningproblem).execute()\n",
       "        filtered_solution = self.filter(graphplan_solution)\n",
       "        ordered_solution = []\n",
       "        planningproblem = self.planningproblem\n",
       "        for level in filtered_solution:\n",
       "            level_solution, planningproblem = self.orderlevel(level, planningproblem)\n",
       "            for element in level_solution:\n",
       "                ordered_solution.append(element)\n",
       "\n",
       "        return ordered_solution\n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "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", "
\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", "
\n", "The `execute` method sequentially calls `orderlevel` for all the levels in the planning-graph and returns the final total-order solution.\n", "
\n", "
\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 }