TOTAL ORDER PLANNER

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:
If a ≤ b and b ≤ a, then a = b (antisymmetry).
If a ≤ b and b ≤ c, then a ≤ c (transitivity).
a ≤ b or b ≤ a (connex relation).

In simpler terms, a total order plan is a linear ordering of actions to be taken to reach the goal state. There may be several different total-order plans for a particular goal depending on the problem.

In the module, the Linearize class solves problems using this paradigm. At its core, the Linearize uses a solved planning graph from GraphPlan and finds a valid total-order solution for it. Let's have a look at the class.



In [1]:

    
from planning import *
from notebook import psource



In [2]:

    
psource(Linearize)









    









  
  
  




class Linearize:

    def __init__(self, planningproblem):
        self.planningproblem = planningproblem

    def filter(self, solution):
        """Filter out persistence actions from a solution"""

        new_solution = []
        for section in solution[0]:
            new_section = []
            for operation in section:
                if not (operation.op[0] == 'P' and operation.op[1].isupper()):
                    new_section.append(operation)
            new_solution.append(new_section)
        return new_solution

    def orderlevel(self, level, planningproblem):
        """Return valid linear order of actions for a given level"""

        for permutation in itertools.permutations(level):
            temp = copy.deepcopy(planningproblem)
            count = 0
            for action in permutation:
                try:
                    temp.act(action)
                    count += 1
                except:
                    count = 0
                    temp = copy.deepcopy(planningproblem)
                    break
            if count == len(permutation):
                return list(permutation), temp
        return None

    def execute(self):
        """Finds total-order solution for a planning graph"""

        graphplan_solution = GraphPlan(self.planningproblem).execute()
        filtered_solution = self.filter(graphplan_solution)
        ordered_solution = []
        planningproblem = self.planningproblem
        for level in filtered_solution:
            level_solution, planningproblem = self.orderlevel(level, planningproblem)
            for element in level_solution:
                ordered_solution.append(element)

        return ordered_solution

The filter method removes the persistence actions (if any) from the planning graph representation.
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.
The execute method sequentially calls orderlevel for all the levels in the planning-graph and returns the final total-order solution.

Let's look at some examples.



In [3]:

    
# total-order solution for air_cargo problem
Linearize(air_cargo()).execute()









    Out[3]:





[Load(C1, P1, SFO),
 Fly(P1, SFO, JFK),
 Load(C2, P2, JFK),
 Fly(P2, JFK, SFO),
 Unload(C2, P2, SFO),
 Unload(C1, P1, JFK)]



In [4]:

    
# total-order solution for spare_tire problem
Linearize(spare_tire()).execute()









    Out[4]:





[Remove(Spare, Trunk), Remove(Flat, Axle), PutOn(Spare, Axle)]



In [5]:

    
# total-order solution for three_block_tower problem
Linearize(three_block_tower()).execute()









    Out[5]:





[MoveToTable(C, A), Move(B, Table, C), Move(A, Table, B)]



In [6]:

    
# total-order solution for simple_blocks_world problem
Linearize(simple_blocks_world()).execute()









    Out[6]:





[ToTable(A, B), FromTable(B, A), FromTable(C, B)]



In [7]:

    
# total-order solution for socks_and_shoes problem
Linearize(socks_and_shoes()).execute()









    Out[7]:





[RightSock, LeftSock, RightShoe, LeftShoe]