simplify.py
Go to the documentation of this file.
00001 # -*- coding: utf-8 -*-
00002 
00003 from collections import defaultdict
00004 from itertools import count
00005 import sys
00006 
00007 DEBUG = True
00008 
00009 # TODO:
00010 # This is all quite hackish and would be easier if the translator were
00011 # restructured so that more information is immediately available for
00012 # the propositions, and if propositions had more structure. Directly
00013 # working with int pairs is awkward.
00014 
00015 
00016 class DomainTransitionGraph(object):
00017     def __init__(self, init, size):
00018         self.init = init
00019         self.size = size
00020         self.arcs = defaultdict(set)
00021 
00022     def add_arc(self, u, v):
00023         self.arcs[u].add(v)
00024 
00025     def reachable(self):
00026         queue = [self.init]
00027         reachable = set(queue)
00028         while queue:
00029             node = queue.pop()
00030             new_neighbors = self.arcs.get(node, set()) - reachable
00031             reachable |= new_neighbors
00032             queue.extend(new_neighbors)
00033         return reachable
00034         
00035     def dump(self):
00036         print "SIZE", self.size
00037         print "INIT", self.init
00038         print "ARCS:"
00039         for source, destinations in sorted(self.arcs.items()):
00040             for destination in sorted(destinations):
00041                 print "  %d => %d" % (source, destination)
00042 
00043 
00044 def build_dtgs(task):
00045     init_vals = task.init.values
00046     sizes = task.variables.ranges
00047     dtgs = [DomainTransitionGraph(init, size)
00048             for (init, size) in zip(init_vals, sizes)]
00049 
00050     def add_arc(var_no, pre_spec, post):
00051         if pre_spec == -1:
00052             pre_values = set(range(sizes[var_no])).difference([post])
00053         else:
00054             pre_values = [pre_spec]
00055         for pre in pre_values:
00056             dtgs[var_no].add_arc(pre, post)
00057 
00058     for op in task.operators:
00059         for var_no, pre_spec, post, cond in op.pre_post:
00060             add_arc(var_no, pre_spec, post)
00061     for axiom in task.axioms:
00062         var_no, val = axiom.effect
00063         add_arc(var_no, -1, val)
00064 
00065     return dtgs
00066 
00067 
00068 always_false = object()
00069 always_true = object()
00070 
00071 class Impossible(Exception):
00072     pass
00073 
00074 class DoesNothing(Exception):
00075     pass
00076 
00077 class VarValueRenaming(object):
00078     def __init__(self):
00079         self.new_var_nos = []   # indexed by old var_no
00080         self.new_values = []    # indexed by old var_no and old value
00081         self.new_sizes = []     # indexed by new var_no
00082         self.new_var_count = 0
00083         self.num_removed_values = 0
00084 
00085     def register_variable(self, old_domain_size, init_value, new_domain):
00086         assert 1 <= len(new_domain) <= old_domain_size
00087         assert init_value in new_domain
00088         if len(new_domain) == 1:
00089             # Remove this variable completely.
00090             new_values_for_var = [always_false] * old_domain_size
00091             new_values_for_var[init_value] = always_true
00092             self.new_var_nos.append(None)
00093             self.new_values.append(new_values_for_var)
00094             self.num_removed_values += old_domain_size
00095         else:
00096             new_value_counter = count()
00097             new_values_for_var = []
00098             for value in range(old_domain_size):
00099                 if value in new_domain:
00100                     new_values_for_var.append(new_value_counter.next())
00101                 else:
00102                     self.num_removed_values += 1
00103                     new_values_for_var.append(always_false)
00104             new_size = new_value_counter.next()
00105             assert new_size == len(new_domain)
00106 
00107             self.new_var_nos.append(self.new_var_count)
00108             self.new_values.append(new_values_for_var)
00109             self.new_sizes.append(new_size)
00110             self.new_var_count += 1
00111 
00112     def apply_to_task(self, task):
00113         self.apply_to_variables(task.variables)
00114         self.apply_to_init(task.init)
00115         self.apply_to_goals(task.goal.pairs)
00116         self.apply_to_operators(task.operators)
00117         self.apply_to_axioms(task.axioms)
00118 
00119     def apply_to_variables(self, variables):
00120         variables.ranges = self.new_sizes
00121         new_axiom_layers = [None] * self.new_var_count
00122         for old_no, new_no in enumerate(self.new_var_nos):
00123             if new_no is not None:
00124                 new_axiom_layers[new_no] = variables.axiom_layers[old_no]
00125         assert None not in new_axiom_layers
00126         variables.axiom_layers = new_axiom_layers
00127 
00128     def apply_to_init(self, init):
00129         init_pairs = list(enumerate(init.values))
00130         try:
00131             self.translate_pairs_in_place(init_pairs)
00132         except Impossible:
00133             assert False, "Initial state impossible? Inconceivable!"
00134         new_values = [None] * self.new_var_count
00135         for new_var_no, new_value in init_pairs:
00136             new_values[new_var_no] = new_value
00137         assert None not in new_values
00138         init.values = new_values
00139 
00140     def apply_to_goals(self, goals):
00141         # This may propagate Impossible up.
00142         self.translate_pairs_in_place(goals)
00143 
00144     def apply_to_operators(self, operators):
00145         new_operators = []
00146         for op in operators:
00147             try:
00148                 self.apply_to_operator(op)
00149                 new_operators.append(op)
00150             except (Impossible, DoesNothing):
00151                 if DEBUG:
00152                     print "Removed operator: %s" % op.name
00153         operators[:] = new_operators
00154 
00155     def apply_to_axioms(self, axioms):
00156         print axioms
00157         new_axioms = []
00158         for axiom in axioms:
00159             try:
00160                 self.apply_to_axiom(axiom)
00161                 new_axioms.append(axiom)
00162             except (Impossible, DoesNothing):
00163                 if DEBUG:
00164                     print "Removed axiom:"
00165                     axiom.dump()
00166         axioms[:] = new_axioms
00167 
00168     def apply_to_operator(self, op):
00169         # The prevail translation may generate an Impossible exception,
00170         # which is propagated up.
00171         self.translate_pairs_in_place(op.prevail)
00172         new_pre_post = []
00173         for entry in op.pre_post:
00174             try:
00175                 new_pre_post.append(self.translate_pre_post(entry))
00176                 # This may raise Impossible if "pre" is always false.
00177                 # This is then propagated up.
00178             except DoesNothing:
00179                 # Conditional effect that is impossible to trigger, or
00180                 # effect that sets an always true value. Swallow this.
00181                 pass
00182         op.pre_post = new_pre_post
00183         if not new_pre_post:
00184             raise DoesNothing
00185 
00186     def apply_to_axiom(self, axiom):
00187         # The following line may generate an Impossible exception,
00188         # which is propagated up.
00189         self.translate_pairs_in_place(axiom.condition)
00190         new_var, new_value = self.translate_pair(axiom.effect)
00191         # If the new_value is always false, then the condition must
00192         # have been impossible.
00193         assert not new_value is always_false
00194         if new_value is always_true:
00195             raise DoesNothing
00196         axiom.effect = new_var, new_value
00197 
00198     def translate_pre_post(self, (var_no, pre, post, cond)):
00199         new_var_no, new_post = self.translate_pair((var_no, post))
00200         if pre == -1:
00201             new_pre = -1
00202         else:
00203             _, new_pre = self.translate_pair((var_no, pre))
00204         if new_pre is always_false:
00205             raise Impossible
00206         try:
00207             self.translate_pairs_in_place(cond)
00208         except Impossible:
00209             raise DoesNothing
00210         assert new_post is not always_false
00211         if new_pre is always_true:
00212             assert new_post is always_true
00213             raise DoesNothing
00214         elif new_post is always_true:
00215             assert new_pre == -1
00216             raise DoesNothing
00217         return new_var_no, new_pre, new_post, cond
00218 
00219     def translate_pair(self, (var_no, value)):
00220         new_var_no = self.new_var_nos[var_no]
00221         new_value = self.new_values[var_no][value]
00222         return new_var_no, new_value
00223 
00224     def translate_pairs_in_place(self, pairs):
00225         new_pairs = []
00226         for pair in pairs:
00227             new_var_no, new_value = self.translate_pair(pair)
00228             if new_value is always_false:
00229                 raise Impossible
00230             elif new_value is not always_true:
00231                 assert new_var_no is not None
00232                 new_pairs.append((new_var_no, new_value))
00233         pairs[:] = new_pairs
00234 
00235     def apply_to_translation_key(self, translation_key):
00236         new_key = [[None] * size for size in self.new_sizes]
00237         for var_no, value_names in enumerate(translation_key):
00238             for value, value_name in enumerate(value_names):
00239                 new_var_no, new_value = self.translate_pair((var_no, value))
00240                 if new_value is always_true:
00241                     if DEBUG:
00242                         print "Removed true proposition: %s" % value_name
00243                 elif new_value is always_false:
00244                     if DEBUG:
00245                         print "Removed false proposition: %s" % value_name
00246                 else:
00247                     new_key[new_var_no][new_value] = value_name
00248         assert all((None not in value_names) for value_names in new_key)
00249         translation_key[:] = new_key
00250 
00251     def apply_to_mutex_key(self, mutex_key):
00252         new_key = []
00253         for group in mutex_key:
00254             new_group = []
00255             for var, val, name in group:
00256                 new_var_no, new_value = self.translate_pair((var, val))
00257                 if (new_value is not always_true and
00258                     new_value is not always_false):
00259                     new_group.append((new_var_no, new_value, name))
00260             if len(new_group) > 0:
00261                 new_key.append(new_group)
00262         mutex_key[:] = new_key
00263         
00264 
00265 def build_renaming(dtgs):
00266     renaming = VarValueRenaming()
00267     for dtg in dtgs:
00268         renaming.register_variable(dtg.size, dtg.init, dtg.reachable())
00269     return renaming
00270 
00271 
00272 def dump_translation_key(translation_key):
00273     for var_no, values in enumerate(translation_key):
00274         print "var %d:" % var_no
00275         for value_no, value in enumerate(values):
00276             print "%2d: %s" % (value_no, value)
00277 
00278 def filter_unreachable_propositions(sas_task, mutex_key, translation_key):
00279     print "**sas_task"
00280     sas_task.output(sys.stdout)
00281     print "Detecting unreachable propositions...",
00282     sys.stdout.flush()
00283     if DEBUG:
00284         print
00285 
00286     # This procedure is a bit of an afterthought, and doesn't fit the
00287     # overall architecture of the translator too well. We filter away
00288     # unreachable propositions here, and then prune away variables
00289     # with only one value left.
00290     # 
00291     # Examples of things that are filtered away:
00292     # - Constant propositions that are not detected in instantiate.py
00293     #   because it only reasons at the predicate level, and some
00294     #   predicates such as "at" in Depot is constant for some objects
00295     #   (hoists), but not others (trucks).
00296     #   Example: "at(hoist1, distributor0)" and the associated
00297     #            variable in depots-01.
00298     # - "none of those" values that are unreachable.
00299     #   Example: at(truck1, ?x) = <none of those> in depots-01.
00300     # - Certain values that are relaxed reachable but detected as
00301     #   unreachable after SAS instantiation because the only operators
00302     #   that set them have inconsistent preconditions.
00303     #   Example: on(crate0, crate0) in depots-01.
00304 
00305     # dump_translation_key(translation_key)
00306     dtgs = build_dtgs(sas_task)
00307     renaming = build_renaming(dtgs)
00308     # apply_to_task may propagate up Impossible if the goal is simplified
00309     # to False.
00310     renaming.apply_to_task(sas_task)
00311     renaming.apply_to_translation_key(translation_key)
00312     renaming.apply_to_mutex_key(mutex_key)
00313     print "%d propositions removed." % renaming.num_removed_values
00314 
00315 def constrain_end_effect_conditions(sas_task):
00316     pre_by_operator_and_var = dict(); 
00317     start_eff_by_operator_and_var = dict(); 
00318     var_to_influencing_ops = dict();
00319     interesting = dict(); ## var->list<op> operators for which the effect
00320                           ## condition could possibly be constrained
00321     for op in sas_task.temp_operators:
00322          start_prevail = op.prevail[0]
00323          for var, val in start_prevail:
00324              pre_by_operator_and_var[(op,var)] = val 
00325          pre_post = op.pre_post
00326          start_eff = dict()
00327          for var, pre, post, cond in pre_post[0]:
00328             pre_by_operator_and_var[(op,var)] = pre
00329             if cond == [[],[],[]]:
00330                 start_eff[var] = post
00331                 start_eff_by_operator_and_var[(op,var)] = post 
00332             var_to_influencing_ops.setdefault(var,set()).add(op)
00333          for var, pre, post, cond in pre_post[1]:
00334             var_to_influencing_ops.setdefault(var,set()).add(op)
00335             if pre == -1:
00336                start_val = start_eff.get(var, None)
00337                if start_val is not None:
00338                   interesting.setdefault(var,[]).append(op)
00339 
00340     variables_to_change = dict()
00341     for var in interesting.iterkeys():
00342         influencing = var_to_influencing_ops[var]
00343         var_is_candidate = True
00344         for op1 in influencing:
00345             if not var_is_candidate:
00346                 break
00347             for op2 in influencing: ## check that op2 cannot be started while 
00348                                     ## op1 is running
00349                 cond2 = pre_by_operator_and_var.get((op2,var), None)
00350                 start_eff1 = start_eff_by_operator_and_var.get((op1,var), None)
00351                 if None in (cond2, start_eff1) or start_eff1 == cond2:
00352                     var_is_candidate = False
00353                     break
00354         if var_is_candidate:
00355             for op in interesting[var]:
00356                 variables_to_change.setdefault(op,set()).add(var)
00357 
00358     nr_changed = 0
00359     for op, vars in variables_to_change.iteritems():
00360         for index, (var, pre, post, cond) in enumerate(op.pre_post[1]):
00361             if var in vars and pre == -1:
00362                 new_pre = start_eff_by_operator_and_var[(op,var)]
00363                 op.pre_post[1][index] = (var, new_pre , post, cond)
00364                 nr_changed += 1
00365 
00366     print "constrained %s conditions" % nr_changed


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06