{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### PARTIAL ORDER PLANNER\n", "A partial-order planning algorithm is significantly different from a total-order planner.\n", "The way a partial-order plan works enables it to take advantage of _problem decomposition_ and work on each subproblem separately.\n", "It works on several subgoals independently, solves them with several subplans, and then combines the plan.\n", "
\n", "A partial-order planner also follows the **least commitment** strategy, where it delays making choices for as long as possible.\n", "Variables are not bound unless it is absolutely necessary and new actions are chosen only if the existing actions cannot fulfil the required precondition.\n", "
\n", "Any planning algorithm that can place two actions into a plan without specifying which comes first is called a **partial-order planner**.\n", "A partial-order planner searches through the space of plans rather than the space of states, which makes it perform better for certain problems.\n", "
\n", "
\n", "Let's have a look at the `PartialOrderPlanner` class." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "from planning import *\n", "from notebook import psource" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "

\n", "\n", "
class PartialOrderPlanner:\n",
       "\n",
       "    def __init__(self, planningproblem):\n",
       "        self.planningproblem = planningproblem\n",
       "        self.initialize()\n",
       "\n",
       "    def initialize(self):\n",
       "        """Initialize all variables"""\n",
       "        self.causal_links = []\n",
       "        self.start = Action('Start', [], self.planningproblem.init)\n",
       "        self.finish = Action('Finish', self.planningproblem.goals, [])\n",
       "        self.actions = set()\n",
       "        self.actions.add(self.start)\n",
       "        self.actions.add(self.finish)\n",
       "        self.constraints = set()\n",
       "        self.constraints.add((self.start, self.finish))\n",
       "        self.agenda = set()\n",
       "        for precond in self.finish.precond:\n",
       "            self.agenda.add((precond, self.finish))\n",
       "        self.expanded_actions = self.expand_actions()\n",
       "\n",
       "    def expand_actions(self, name=None):\n",
       "        """Generate all possible actions with variable bindings for precondition selection heuristic"""\n",
       "\n",
       "        objects = set(arg for clause in self.planningproblem.init for arg in clause.args)\n",
       "        expansions = []\n",
       "        action_list = []\n",
       "        if name is not None:\n",
       "            for action in self.planningproblem.actions:\n",
       "                if str(action.name) == name:\n",
       "                    action_list.append(action)\n",
       "        else:\n",
       "            action_list = self.planningproblem.actions\n",
       "\n",
       "        for action in action_list:\n",
       "            for permutation in itertools.permutations(objects, len(action.args)):\n",
       "                bindings = unify(Expr(action.name, *action.args), Expr(action.name, *permutation))\n",
       "                if bindings is not None:\n",
       "                    new_args = []\n",
       "                    for arg in action.args:\n",
       "                        if arg in bindings:\n",
       "                            new_args.append(bindings[arg])\n",
       "                        else:\n",
       "                            new_args.append(arg)\n",
       "                    new_expr = Expr(str(action.name), *new_args)\n",
       "                    new_preconds = []\n",
       "                    for precond in action.precond:\n",
       "                        new_precond_args = []\n",
       "                        for arg in precond.args:\n",
       "                            if arg in bindings:\n",
       "                                new_precond_args.append(bindings[arg])\n",
       "                            else:\n",
       "                                new_precond_args.append(arg)\n",
       "                        new_precond = Expr(str(precond.op), *new_precond_args)\n",
       "                        new_preconds.append(new_precond)\n",
       "                    new_effects = []\n",
       "                    for effect in action.effect:\n",
       "                        new_effect_args = []\n",
       "                        for arg in effect.args:\n",
       "                            if arg in bindings:\n",
       "                                new_effect_args.append(bindings[arg])\n",
       "                            else:\n",
       "                                new_effect_args.append(arg)\n",
       "                        new_effect = Expr(str(effect.op), *new_effect_args)\n",
       "                        new_effects.append(new_effect)\n",
       "                    expansions.append(Action(new_expr, new_preconds, new_effects))\n",
       "\n",
       "        return expansions\n",
       "\n",
       "    def find_open_precondition(self):\n",
       "        """Find open precondition with the least number of possible actions"""\n",
       "\n",
       "        number_of_ways = dict()\n",
       "        actions_for_precondition = dict()\n",
       "        for element in self.agenda:\n",
       "            open_precondition = element[0]\n",
       "            possible_actions = list(self.actions) + self.expanded_actions\n",
       "            for action in possible_actions:\n",
       "                for effect in action.effect:\n",
       "                    if effect == open_precondition:\n",
       "                        if open_precondition in number_of_ways:\n",
       "                            number_of_ways[open_precondition] += 1\n",
       "                            actions_for_precondition[open_precondition].append(action)\n",
       "                        else:\n",
       "                            number_of_ways[open_precondition] = 1\n",
       "                            actions_for_precondition[open_precondition] = [action]\n",
       "\n",
       "        number = sorted(number_of_ways, key=number_of_ways.__getitem__)\n",
       "        \n",
       "        for k, v in number_of_ways.items():\n",
       "            if v == 0:\n",
       "                return None, None, None\n",
       "\n",
       "        act1 = None\n",
       "        for element in self.agenda:\n",
       "            if element[0] == number[0]:\n",
       "                act1 = element[1]\n",
       "                break\n",
       "\n",
       "        if number[0] in self.expanded_actions:\n",
       "            self.expanded_actions.remove(number[0])\n",
       "\n",
       "        return number[0], act1, actions_for_precondition[number[0]]\n",
       "\n",
       "    def find_action_for_precondition(self, oprec):\n",
       "        """Find action for a given precondition"""\n",
       "\n",
       "        # either\n",
       "        #   choose act0 E Actions such that act0 achieves G\n",
       "        for action in self.actions:\n",
       "            for effect in action.effect:\n",
       "                if effect == oprec:\n",
       "                    return action, 0\n",
       "\n",
       "        # or\n",
       "        #   choose act0 E Actions such that act0 achieves G\n",
       "        for action in self.planningproblem.actions:\n",
       "            for effect in action.effect:\n",
       "                if effect.op == oprec.op:\n",
       "                    bindings = unify(effect, oprec)\n",
       "                    if bindings is None:\n",
       "                        break\n",
       "                    return action, bindings\n",
       "\n",
       "    def generate_expr(self, clause, bindings):\n",
       "        """Generate atomic expression from generic expression given variable bindings"""\n",
       "\n",
       "        new_args = []\n",
       "        for arg in clause.args:\n",
       "            if arg in bindings:\n",
       "                new_args.append(bindings[arg])\n",
       "            else:\n",
       "                new_args.append(arg)\n",
       "\n",
       "        try:\n",
       "            return Expr(str(clause.name), *new_args)\n",
       "        except:\n",
       "            return Expr(str(clause.op), *new_args)\n",
       "        \n",
       "    def generate_action_object(self, action, bindings):\n",
       "        """Generate action object given a generic action andvariable bindings"""\n",
       "\n",
       "        # if bindings is 0, it means the action already exists in self.actions\n",
       "        if bindings == 0:\n",
       "            return action\n",
       "\n",
       "        # bindings cannot be None\n",
       "        else:\n",
       "            new_expr = self.generate_expr(action, bindings)\n",
       "            new_preconds = []\n",
       "            for precond in action.precond:\n",
       "                new_precond = self.generate_expr(precond, bindings)\n",
       "                new_preconds.append(new_precond)\n",
       "            new_effects = []\n",
       "            for effect in action.effect:\n",
       "                new_effect = self.generate_expr(effect, bindings)\n",
       "                new_effects.append(new_effect)\n",
       "            return Action(new_expr, new_preconds, new_effects)\n",
       "\n",
       "    def cyclic(self, graph):\n",
       "        """Check cyclicity of a directed graph"""\n",
       "\n",
       "        new_graph = dict()\n",
       "        for element in graph:\n",
       "            if element[0] in new_graph:\n",
       "                new_graph[element[0]].append(element[1])\n",
       "            else:\n",
       "                new_graph[element[0]] = [element[1]]\n",
       "\n",
       "        path = set()\n",
       "\n",
       "        def visit(vertex):\n",
       "            path.add(vertex)\n",
       "            for neighbor in new_graph.get(vertex, ()):\n",
       "                if neighbor in path or visit(neighbor):\n",
       "                    return True\n",
       "            path.remove(vertex)\n",
       "            return False\n",
       "\n",
       "        value = any(visit(v) for v in new_graph)\n",
       "        return value\n",
       "\n",
       "    def add_const(self, constraint, constraints):\n",
       "        """Add the constraint to constraints if the resulting graph is acyclic"""\n",
       "\n",
       "        if constraint[0] == self.finish or constraint[1] == self.start:\n",
       "            return constraints\n",
       "\n",
       "        new_constraints = set(constraints)\n",
       "        new_constraints.add(constraint)\n",
       "\n",
       "        if self.cyclic(new_constraints):\n",
       "            return constraints\n",
       "        return new_constraints\n",
       "\n",
       "    def is_a_threat(self, precondition, effect):\n",
       "        """Check if effect is a threat to precondition"""\n",
       "\n",
       "        if (str(effect.op) == 'Not' + str(precondition.op)) or ('Not' + str(effect.op) == str(precondition.op)):\n",
       "            if effect.args == precondition.args:\n",
       "                return True\n",
       "        return False\n",
       "\n",
       "    def protect(self, causal_link, action, constraints):\n",
       "        """Check and resolve threats by promotion or demotion"""\n",
       "\n",
       "        threat = False\n",
       "        for effect in action.effect:\n",
       "            if self.is_a_threat(causal_link[1], effect):\n",
       "                threat = True\n",
       "                break\n",
       "\n",
       "        if action != causal_link[0] and action != causal_link[2] and threat:\n",
       "            # try promotion\n",
       "            new_constraints = set(constraints)\n",
       "            new_constraints.add((action, causal_link[0]))\n",
       "            if not self.cyclic(new_constraints):\n",
       "                constraints = self.add_const((action, causal_link[0]), constraints)\n",
       "            else:\n",
       "                # try demotion\n",
       "                new_constraints = set(constraints)\n",
       "                new_constraints.add((causal_link[2], action))\n",
       "                if not self.cyclic(new_constraints):\n",
       "                    constraints = self.add_const((causal_link[2], action), constraints)\n",
       "                else:\n",
       "                    # both promotion and demotion fail\n",
       "                    print('Unable to resolve a threat caused by', action, 'onto', causal_link)\n",
       "                    return\n",
       "        return constraints\n",
       "\n",
       "    def convert(self, constraints):\n",
       "        """Convert constraints into a dict of Action to set orderings"""\n",
       "\n",
       "        graph = dict()\n",
       "        for constraint in constraints:\n",
       "            if constraint[0] in graph:\n",
       "                graph[constraint[0]].add(constraint[1])\n",
       "            else:\n",
       "                graph[constraint[0]] = set()\n",
       "                graph[constraint[0]].add(constraint[1])\n",
       "        return graph\n",
       "\n",
       "    def toposort(self, graph):\n",
       "        """Generate topological ordering of constraints"""\n",
       "\n",
       "        if len(graph) == 0:\n",
       "            return\n",
       "\n",
       "        graph = graph.copy()\n",
       "\n",
       "        for k, v in graph.items():\n",
       "            v.discard(k)\n",
       "\n",
       "        extra_elements_in_dependencies = _reduce(set.union, graph.values()) - set(graph.keys())\n",
       "\n",
       "        graph.update({element:set() for element in extra_elements_in_dependencies})\n",
       "        while True:\n",
       "            ordered = set(element for element, dependency in graph.items() if len(dependency) == 0)\n",
       "            if not ordered:\n",
       "                break\n",
       "            yield ordered\n",
       "            graph = {element: (dependency - ordered) for element, dependency in graph.items() if element not in ordered}\n",
       "        if len(graph) != 0:\n",
       "            raise ValueError('The graph is not acyclic and cannot be linearly ordered')\n",
       "\n",
       "    def display_plan(self):\n",
       "        """Display causal links, constraints and the plan"""\n",
       "\n",
       "        print('Causal Links')\n",
       "        for causal_link in self.causal_links:\n",
       "            print(causal_link)\n",
       "\n",
       "        print('\\nConstraints')\n",
       "        for constraint in self.constraints:\n",
       "            print(constraint[0], '<', constraint[1])\n",
       "\n",
       "        print('\\nPartial Order Plan')\n",
       "        print(list(reversed(list(self.toposort(self.convert(self.constraints))))))\n",
       "\n",
       "    def execute(self, display=True):\n",
       "        """Execute the algorithm"""\n",
       "\n",
       "        step = 1\n",
       "        self.tries = 1\n",
       "        while len(self.agenda) > 0:\n",
       "            step += 1\n",
       "            # select <G, act1> from Agenda\n",
       "            try:\n",
       "                G, act1, possible_actions = self.find_open_precondition()\n",
       "            except IndexError:\n",
       "                print('Probably Wrong')\n",
       "                break\n",
       "\n",
       "            act0 = possible_actions[0]\n",
       "            # remove <G, act1> from Agenda\n",
       "            self.agenda.remove((G, act1))\n",
       "\n",
       "            # For actions with variable number of arguments, use least commitment principle\n",
       "            # act0_temp, bindings = self.find_action_for_precondition(G)\n",
       "            # act0 = self.generate_action_object(act0_temp, bindings)\n",
       "\n",
       "            # Actions = Actions U {act0}\n",
       "            self.actions.add(act0)\n",
       "\n",
       "            # Constraints = add_const(start < act0, Constraints)\n",
       "            self.constraints = self.add_const((self.start, act0), self.constraints)\n",
       "\n",
       "            # for each CL E CausalLinks do\n",
       "            #   Constraints = protect(CL, act0, Constraints)\n",
       "            for causal_link in self.causal_links:\n",
       "                self.constraints = self.protect(causal_link, act0, self.constraints)\n",
       "\n",
       "            # Agenda = Agenda U {<P, act0>: P is a precondition of act0}\n",
       "            for precondition in act0.precond:\n",
       "                self.agenda.add((precondition, act0))\n",
       "\n",
       "            # Constraints = add_const(act0 < act1, Constraints)\n",
       "            self.constraints = self.add_const((act0, act1), self.constraints)\n",
       "\n",
       "            # CausalLinks U {<act0, G, act1>}\n",
       "            if (act0, G, act1) not in self.causal_links:\n",
       "                self.causal_links.append((act0, G, act1))\n",
       "\n",
       "            # for each A E Actions do\n",
       "            #   Constraints = protect(<act0, G, act1>, A, Constraints)\n",
       "            for action in self.actions:\n",
       "                self.constraints = self.protect((act0, G, act1), action, self.constraints)\n",
       "\n",
       "            if step > 200:\n",
       "                print('Couldn\\'t find a solution')\n",
       "                return None, None\n",
       "\n",
       "        if display:\n",
       "            self.display_plan()\n",
       "        else:\n",
       "            return self.constraints, self.causal_links                \n",
       "
\n", "\n", "\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "psource(PartialOrderPlanner)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will first describe the data-structures and helper methods used, followed by the algorithm used to find a partial-order plan." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each plan has the following four components:\n", "\n", "1. **`actions`**: a set of actions that make up the steps of the plan.\n", "`actions` is always a subset of `pddl.actions` the set of possible actions for the given planning problem. \n", "The `start` and `finish` actions are dummy actions defined to bring uniformity to the problem. The `start` action has no preconditions and its effects constitute the initial state of the planning problem. \n", "The `finish` action has no effects and its preconditions constitute the goal state of the planning problem.\n", "The empty plan consists of just these two dummy actions.\n", "2. **`constraints`**: a set of temporal constraints that define the order of performing the actions relative to each other.\n", "`constraints` does not define a linear ordering, rather it usually represents a directed graph which is also acyclic if the plan is consistent.\n", "Each ordering is of the form A < B, which reads as \"A before B\" and means that action A _must_ be executed sometime before action B, but not necessarily immediately before.\n", "`constraints` stores these as a set of tuples `(Action(A), Action(B))` which is interpreted as given above.\n", "A constraint cannot be added to `constraints` if it breaks the acyclicity of the existing graph.\n", "3. **`causal_links`**: a set of causal-links. \n", "A causal link between two actions _A_ and _B_ in the plan is written as _A_ --_p_--> _B_ and is read as \"A achieves p for B\".\n", "This imples that _p_ is an effect of _A_ and a precondition of _B_.\n", "It also asserts that _p_ must remain true from the time of action _A_ to the time of action _B_.\n", "Any violation of this rule is called a threat and must be resolved immediately by adding suitable ordering constraints.\n", "`causal_links` stores this information as tuples `(Action(A), precondition(p), Action(B))` which is interpreted as given above.\n", "Causal-links can also be called **protection-intervals**, because the link _A_ --_p_--> _B_ protects _p_ from being negated over the interval from _A_ to _B_.\n", "4. **`agenda`**: a set of open-preconditions.\n", "A precondition is open if it is not achieved by some action in the plan.\n", "Planners will work to reduce the set of open preconditions to the empty set, without introducing a contradiction.\n", "`agenda` stored this information as tuples `(precondition(p), Action(A))` where p is a precondition of the action A.\n", "\n", "A **consistent plan** is a plan in which there are no cycles in the ordering constraints and no conflicts with the causal-links.\n", "A consistent plan with no open preconditions is a **solution**.\n", "
\n", "
\n", "Let's briefly glance over the helper functions before going into the actual algorithm.\n", "
\n", "**`expand_actions`**: generates all possible actions with variable bindings for use as a heuristic of selection of an open precondition.\n", "
\n", "**`find_open_precondition`**: finds a precondition from the agenda with the least number of actions that fulfil that precondition.\n", "This heuristic helps form mandatory ordering constraints and causal-links to further simplify the problem and reduce the probability of encountering a threat.\n", "
\n", "**`find_action_for_precondition`**: finds an action that fulfils the given precondition along with the absolutely necessary variable bindings in accordance with the principle of _least commitment_.\n", "In case of multiple possible actions, the action with the least number of effects is chosen to minimize the chances of encountering a threat.\n", "
\n", "**`cyclic`**: checks if a directed graph is cyclic.\n", "
\n", "**`add_const`**: adds `constraint` to `constraints` if the newly formed graph is acyclic and returns `constraints` otherwise.\n", "
\n", "**`is_a_threat`**: checks if the given `effect` negates the given `precondition`.\n", "
\n", "**`protect`**: checks if the given `action` poses a threat to the given `causal_link`.\n", "If so, the threat is resolved by either promotion or demotion, whichever generates acyclic temporal constraints.\n", "If neither promotion or demotion work, the chosen action is not the correct fit or the planning problem cannot be solved altogether.\n", "
\n", "**`convert`**: converts a graph from a list of edges to an `Action` : `set` mapping, for use in topological sorting.\n", "
\n", "**`toposort`**: a generator function that generates a topological ordering of a given graph as a list of sets.\n", "Each set contains an action or several actions.\n", "If a set has more that one action in it, it means that permutations between those actions also produce a valid plan.\n", "
\n", "**`display_plan`**: displays the `causal_links`, `constraints` and the partial order plan generated from `toposort`.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The **`execute`** method executes the algorithm, which is summarized below:\n", "
\n", "1. An open precondition is selected (a sub-goal that we want to achieve).\n", "2. An action that fulfils the open precondition is chosen.\n", "3. Temporal constraints are updated.\n", "4. Existing causal links are protected. Protection is a method that checks if the causal links conflict\n", " and if they do, temporal constraints are added to fix the threats.\n", "5. The set of open preconditions is updated.\n", "6. Temporal constraints of the selected action and the next action are established.\n", "7. A new causal link is added between the selected action and the owner of the open precondition.\n", "8. The set of new causal links is checked for threats and if found, the threat is removed by either promotion or demotion.\n", " If promotion or demotion is unable to solve the problem, the planning problem cannot be solved with the current sequence of actions\n", " or it may not be solvable at all.\n", "9. These steps are repeated until the set of open preconditions is empty." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A partial-order plan can be used to generate different valid total-order plans.\n", "This step is called **linearization** of the partial-order plan.\n", "All possible linearizations of a partial-order plan for `socks_and_shoes` looks like this.\n", "
\n", "![title](images/pop.jpg)\n", "
\n", "Linearization can be carried out in many ways, but the most efficient way is to represent the set of temporal constraints as a directed graph.\n", "We can easily realize that the graph should also be acyclic as cycles in constraints means that the constraints are inconsistent.\n", "This acyclicity is enforced by the `add_const` method, which adds a new constraint only if the acyclicity of the existing graph is not violated.\n", "The `protect` method also checks for acyclicity of the newly-added temporal constraints to make a decision between promotion and demotion in case of a threat.\n", "This property of a graph created from the temporal constraints of a valid partial-order plan allows us to use topological sort to order the constraints linearly.\n", "A topological sort may produce several different valid solutions for a given directed acyclic graph." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we know how `PartialOrderPlanner` works, let's solve a few problems using it." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Causal Links\n", "(Action(PutOn(Spare, Axle)), At(Spare, Axle), Action(Finish))\n", "(Action(Start), Tire(Spare), Action(PutOn(Spare, Axle)))\n", "(Action(Remove(Flat, Axle)), NotAt(Flat, Axle), Action(PutOn(Spare, Axle)))\n", "(Action(Start), At(Flat, Axle), Action(Remove(Flat, Axle)))\n", "(Action(Remove(Spare, Trunk)), At(Spare, Ground), Action(PutOn(Spare, Axle)))\n", "(Action(Start), At(Spare, Trunk), Action(Remove(Spare, Trunk)))\n", "(Action(Remove(Flat, Axle)), At(Flat, Ground), Action(Finish))\n", "\n", "Constraints\n", "Action(Remove(Flat, Axle)) < Action(PutOn(Spare, Axle))\n", "Action(Start) < Action(Finish)\n", "Action(Remove(Spare, Trunk)) < Action(PutOn(Spare, Axle))\n", "Action(Start) < Action(Remove(Spare, Trunk))\n", "Action(Start) < Action(Remove(Flat, Axle))\n", "Action(Remove(Flat, Axle)) < Action(Finish)\n", "Action(PutOn(Spare, Axle)) < Action(Finish)\n", "Action(Start) < Action(PutOn(Spare, Axle))\n", "\n", "Partial Order Plan\n", "[{Action(Start)}, {Action(Remove(Flat, Axle)), Action(Remove(Spare, Trunk))}, {Action(PutOn(Spare, Axle))}, {Action(Finish)}]\n" ] } ], "source": [ "st = spare_tire()\n", "pop = PartialOrderPlanner(st)\n", "pop.execute()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We observe that in the given partial order plan, Remove(Flat, Axle) and Remove(Spare, Trunk) are in the same set.\n", "This means that the order of performing these actions does not affect the final outcome.\n", "That aside, we also see that the PutOn(Spare, Axle) action has to be performed after both the Remove actions are complete, which seems logically consistent." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Causal Links\n", "(Action(FromTable(C, B)), On(C, B), Action(Finish))\n", "(Action(FromTable(B, A)), On(B, A), Action(Finish))\n", "(Action(Start), OnTable(B), Action(FromTable(B, A)))\n", "(Action(Start), OnTable(C), Action(FromTable(C, B)))\n", "(Action(Start), Clear(C), Action(FromTable(C, B)))\n", "(Action(Start), Clear(A), Action(FromTable(B, A)))\n", "(Action(ToTable(A, B)), Clear(B), Action(FromTable(C, B)))\n", "(Action(Start), On(A, B), Action(ToTable(A, B)))\n", "(Action(ToTable(A, B)), Clear(B), Action(FromTable(B, A)))\n", "(Action(Start), Clear(A), Action(ToTable(A, B)))\n", "\n", "Constraints\n", "Action(Start) < Action(FromTable(C, B))\n", "Action(FromTable(B, A)) < Action(FromTable(C, B))\n", "Action(Start) < Action(FromTable(B, A))\n", "Action(Start) < Action(ToTable(A, B))\n", "Action(Start) < Action(Finish)\n", "Action(FromTable(B, A)) < Action(Finish)\n", "Action(FromTable(C, B)) < Action(Finish)\n", "Action(ToTable(A, B)) < Action(FromTable(B, A))\n", "Action(ToTable(A, B)) < Action(FromTable(C, B))\n", "\n", "Partial Order Plan\n", "[{Action(Start)}, {Action(ToTable(A, B))}, {Action(FromTable(B, A))}, {Action(FromTable(C, B))}, {Action(Finish)}]\n" ] } ], "source": [ "sbw = simple_blocks_world()\n", "pop = PartialOrderPlanner(sbw)\n", "pop.execute()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "We see that this plan does not have flexibility in selecting actions, ie, actions should be performed in this order and this order only, to successfully reach the goal state." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Causal Links\n", "(Action(RightShoe), RightShoeOn, Action(Finish))\n", "(Action(LeftShoe), LeftShoeOn, Action(Finish))\n", "(Action(LeftSock), LeftSockOn, Action(LeftShoe))\n", "(Action(RightSock), RightSockOn, Action(RightShoe))\n", "\n", "Constraints\n", "Action(LeftSock) < Action(LeftShoe)\n", "Action(RightSock) < Action(RightShoe)\n", "Action(Start) < Action(RightShoe)\n", "Action(Start) < Action(Finish)\n", "Action(LeftShoe) < Action(Finish)\n", "Action(Start) < Action(RightSock)\n", "Action(Start) < Action(LeftShoe)\n", "Action(Start) < Action(LeftSock)\n", "Action(RightShoe) < Action(Finish)\n", "\n", "Partial Order Plan\n", "[{Action(Start)}, {Action(LeftSock), Action(RightSock)}, {Action(LeftShoe), Action(RightShoe)}, {Action(Finish)}]\n" ] } ], "source": [ "ss = socks_and_shoes()\n", "pop = PartialOrderPlanner(ss)\n", "pop.execute()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "This plan again doesn't have constraints in selecting socks or shoes.\n", "As long as both socks are worn before both shoes, we are fine.\n", "Notice however, there is one valid solution,\n", "
\n", "LeftSock -> LeftShoe -> RightSock -> RightShoe\n", "
\n", "that the algorithm could not find as it cannot be represented as a general partially-ordered plan but is a specific total-order solution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Runtime differences\n", "Let's briefly take a look at the running time of all the three algorithms on the `socks_and_shoes` problem." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "ss = socks_and_shoes()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "198 µs ± 3.53 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n" ] } ], "source": [ "%%timeit\n", "GraphPlan(ss).execute()" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "844 µs ± 23.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n" ] } ], "source": [ "%%timeit\n", "Linearize(ss).execute()" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "258 µs ± 4.03 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n" ] } ], "source": [ "%%timeit\n", "PartialOrderPlanner(ss).execute(display=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We observe that `GraphPlan` is about 4 times faster than `Linearize` because `Linearize` essentially runs a `GraphPlan` subroutine under the hood and then carries out some transformations on the solved planning-graph.\n", "
\n", "We also find that `GraphPlan` is slightly faster than `PartialOrderPlanner`, but this is mainly due to the `expand_actions` method in `PartialOrderPlanner` that slows it down as it generates all possible permutations of actions and variable bindings.\n", "
\n", "Without heuristic functions, `PartialOrderPlanner` will be atleast as fast as `GraphPlan`, if not faster, but will have a higher tendency to encounter threats and conflicts which might take additional time to resolve.\n", "
\n", "Different planning algorithms work differently for different problems." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.3" } }, "nbformat": 4, "nbformat_minor": 1 }