translate.py
Go to the documentation of this file.
00001 #! /usr/bin/env python
00002 # -*- coding: latin-1 -*-
00003 import sys
00004 
00005 import axiom_rules
00006 import fact_groups
00007 import instantiate
00008 import numeric_axiom_rules
00009 import pddl
00010 import sas_tasks
00011 import simplify
00012 import itertools
00013 import copy
00014 
00015 # TODO: The translator may generate trivial derived variables which are always true,
00016 # for example if there ia a derived predicate in the input that only depends on
00017 # (non-derived) variables which are detected as always true.
00018 # Such a situation was encountered in the PSR-STRIPS-DerivedPredicates domain.
00019 # Such "always-true" variables should best be compiled away, but it is
00020 # not clear what the best place to do this should be. Similar
00021 # simplifications might be possible elsewhere, for example if a
00022 # derived variable is synonymous with another variable (derived or
00023 # non-derived).
00024 # The first part is now handled in axioms.py calculating true_atoms and false_atoms
00025 
00026 ALLOW_CONFLICTING_EFFECTS = False
00027 USE_PARTIAL_ENCODING = True
00028 WRITE_ALL_MUTEXES = True
00029 USE_SAFE_INVARIANT_SYNTHESIS = True
00030 
00031 def strips_to_sas_dictionary(groups, num_axioms, num_axiom_map, num_fluents, modules):
00032     dictionary = {}
00033     mod_effects_dict = {}
00034 
00035     # sort groups to get a deterministic output
00036     map(lambda g: g.sort(lambda x, y: cmp(str(x),str(y))),groups)
00037     groups.sort(lambda x, y: cmp((-len(x),str(x[0])),(-len(y),str(y[0]))))
00038  
00039     for var_no, group in enumerate(groups):
00040         for val_no, atom in enumerate(group):
00041             dictionary.setdefault(atom, []).append((var_no, val_no))
00042     if USE_PARTIAL_ENCODING:
00043         assert all(len(sas_pairs) == 1
00044                    for sas_pairs in dictionary.itervalues())
00045 
00046     redundant_axioms = []
00047     num_ax_count = 0
00048     for axiom in num_axioms:
00049         if axiom.effect in num_axiom_map:
00050             redundant_axioms.append(axiom.effect)
00051         else:
00052             dictionary.setdefault(axiom.effect,[]).append((num_ax_count + len(groups), -2))
00053             num_ax_count += 1
00054     for axiom_effect in redundant_axioms:
00055             dictionary[axiom_effect] = dictionary[num_axiom_map[axiom_effect].effect]
00056 
00057     ranges = [len(group) + 1 for group in groups] + [-1]*num_ax_count
00058 
00059     var_no = len(groups) + num_ax_count
00060     fluent_list = list(num_fluents)
00061     fluent_list.sort(lambda x,y: cmp(str(x), str(y)))
00062     for fluent in fluent_list: # are partially contained in num_axiom
00063         if fluent not in dictionary:
00064             dictionary.setdefault(fluent,[]).append((var_no, -2))
00065             var_no += 1
00066             ranges.append(-1)
00067     
00068     module_list = list(modules)
00069     module_list.sort(lambda x,y: cmp(str(x), str(y)))
00070     mod_eff_no = 0
00071     for module in module_list:
00072       moduleCall = module.toModuleCall()
00073       if module.type == "effect":
00074         if moduleCall not in mod_effects_dict:
00075           mod_effects_dict.setdefault(moduleCall, []).append(mod_eff_no)
00076           # might be enough just to set that to mod_eff_no
00077           mod_eff_no += 1
00078       else:
00079         if moduleCall not in dictionary:
00080           # hm, if we use 1 here, we could even handle negated effects
00081           # see if this happens, when effects are not at toplevel in a condition
00082           dictionary.setdefault(moduleCall, []).append((var_no, 0))
00083           var_no += 1
00084           if module.type == "conditionchecker":
00085             ranges.append(-2)
00086           elif module.type == "cost":
00087             ranges.append(-3)
00088           else:
00089             assert False, "Unknown module type in dictionary"
00090         
00091     return ranges, dictionary, mod_effects_dict
00092 
00093 def translate_strips_conditions(conditions, dictionary, ranges, comp_axioms, 
00094                                 temporal=False, true_atoms=(), false_atoms=()):
00095     """ Translate (possibly temporal) strips conditions to a list of conditions.
00096     
00097     If temporal, conditions is a list of (3) condition (lists).
00098 
00099     """
00100     if temporal:
00101         condition = [translate_strips_conditions_aux(conds, dictionary, ranges,
00102                                                      comp_axioms, true_atoms,
00103                                                      false_atoms) 
00104                      for conds in conditions]
00105         if None in condition:
00106             return None
00107         else:
00108             return condition
00109     else:
00110         return translate_strips_conditions_aux(conditions, dictionary, ranges,
00111                                                comp_axioms, true_atoms,
00112                                                false_atoms)
00113 
00114 
00115 def translate_strips_conditions_aux(conditions, dictionary, ranges, comparison_axioms,
00116                                     true_atoms, false_atoms):
00117     """ Translate a strips condition.
00118 
00119     Translates the condition for a certain time point/period (at start, over
00120     all or at end), not a full temporal condition. So conditions must
00121     represent a conjunction of facts.
00122 
00123     Returns a list of conditions - commonly just 1 entry, but negated
00124     effects might result in a disjunction (represented as list) of multiple
00125     conditions. 
00126 
00127     """
00128     if not conditions:
00129         return [{}] # Quick exit for common case.
00130 
00131     condition = {}
00132     comp_axiom_dict = comparison_axioms[0]
00133     sas_comp_axioms = comparison_axioms[1]
00134     negated_facts = []
00135 
00136     for fact in conditions:
00137         if (isinstance(fact,pddl.FunctionComparison) or 
00138             isinstance(fact,pddl.NegatedFunctionComparison)):
00139             if fact not in dictionary:
00140                 parts = [dictionary[part][0][0] for part in fact.parts]
00141                 key = (fact.comparator, tuple(parts))
00142                 negated = fact.negated
00143                 if key in comp_axiom_dict:
00144                     fact = comp_axiom_dict[key]
00145                     if negated:
00146                         fact = fact.negate()
00147                 else:
00148                     axiom = sas_tasks.SASCompareAxiom(fact.comparator, 
00149                                                       parts, len(ranges)) 
00150                     sas_comp_axioms.append(axiom)
00151                     if negated:
00152                         negfact = fact
00153                         posfact = fact.negate()
00154                     else:
00155                         posfact = fact
00156                         negfact = fact.negate()
00157                     comp_axiom_dict[key] = posfact
00158                     dictionary.setdefault(posfact,[]).append((len(ranges), 0))
00159                     dictionary.setdefault(negfact,[]).append((len(ranges), 1))
00160                     ranges.append(3)
00161             var, val = dictionary[fact][0]
00162             if (var in condition and val not in condition[var]):
00163                 # Conflicting conditions on this variable: Operator invalid.
00164                 return None
00165             condition[var] = set([val]) 
00166         elif isinstance(fact, pddl.ModuleCall):
00167             assert fact in dictionary
00168             for var, val in dictionary[fact]:
00169                 if (var in condition and val not in condition[var]):
00170                     # Conflicting conditions on this variable: Operator invalid.
00171                     return None
00172                 # Warum koennen das mehr als 1 eintrag sein?
00173                 condition[var] = set([val])
00174         else:
00175             # check atoms from constant axioms
00176             atom = pddl.Atom(fact.predicate, fact.args) # force positive
00177             if fact.negated:
00178                 if atom in false_atoms:
00179                     continue
00180                 if atom in true_atoms:
00181                     return None
00182             else:
00183                 if atom in true_atoms:
00184                     continue
00185                 if atom in false_atoms:
00186                     return None
00187             if fact.negated:
00188                 negated_facts.append(fact)
00189                 # we handle negative conditions later, because then we
00190                 # can recognize when the negative condition is already
00191                 # ensured by a positive condition
00192                 continue
00193             try:
00194                 for var, val in dictionary[fact]:
00195                     if var in condition and val not in condition[var]:
00196                         # Conflicting conditions on this variable: 
00197                         # Operator invalid.
00198                         return None
00199                     condition[var] = set([val])
00200             except KeyError as e:
00201                 print "Atom not in dictionary: ", fact.dump()
00202                 raise
00203 
00204     # Now deal with the negated conditions
00205     for fact in negated_facts:
00206         ## Note  Here we use a different solution than in Sec. 10.6.4
00207         ##       of the thesis. Compare the last sentences of the third
00208         ##       paragraph of the section.
00209         ##       We could do what is written there. As a test case,
00210         ##       consider Airport ADL tasks with only one airport, where
00211         ##       (occupied ?x) variables are encoded in a single variable,
00212         ##       and conditions like (not (occupied ?x)) do occur in
00213         ##       preconditions.
00214         ##       However, here we avoid introducing new derived predicates
00215         ##       by treat the negative precondition as a disjunctive precondition
00216         ##       and expanding it by "multiplying out" the possibilities.
00217         ##       This can lead to an exponential blow-up so it would be nice
00218         ##       to choose the behaviour as an option.
00219         done = False
00220         new_condition = {}
00221         atom = pddl.Atom(fact.predicate, fact.args) # force positive
00222         for var, val in dictionary.get(atom, ()):
00223             # see comment (**) above
00224             poss_vals = set(range(ranges[var]))
00225             poss_vals.remove(val)
00226 
00227             if condition.get(var) is None:
00228                 assert new_condition.get(var) is None
00229                 new_condition[var] = poss_vals
00230             else:
00231                 # constrain existing condition on var
00232                 prev_possible_vals = condition.get(var)
00233                 done = True
00234                 prev_possible_vals.intersection_update(poss_vals)
00235                 if len(prev_possible_vals) == 0:
00236                     # Conflicting conditions on this variable:
00237                     # Operator invalid.
00238                     return None
00239 
00240         if not done and new_condition:
00241             # we did not enforce the negative condition by constraining
00242             # an existing condition on one of the variables representing
00243             # this atom. So we need to introduce a new condition:
00244             # We can select any from new_condition and currently prefer the
00245             # smalles one.
00246             candidates = sorted(new_condition.items(),
00247                                 lambda x,y: cmp(len(x[1]),len(y[1])))
00248             var, vals = candidates[0]
00249             condition[var] = vals
00250 
00251     def multiply_out(condition): # destroys the input
00252         sorted_conds = sorted(condition.items(),
00253                               lambda x,y: cmp(len(x[1]),len(y[1])))
00254         flat_conds = [{}]
00255         for var, vals in sorted_conds:
00256             if len(vals) == 1:
00257                 for cond in flat_conds:
00258                     cond[var] = vals.pop() # destroys the input here
00259             else:
00260                 new_conds = []
00261                 for cond in flat_conds:
00262                     for val in vals:
00263                         new_cond = copy.deepcopy(cond)
00264                         new_cond[var] = val
00265                         new_conds.append(new_cond)
00266                 flat_conds = new_conds
00267         return flat_conds
00268 
00269     return multiply_out(condition)
00270 
00271 
00272 def translate_operator_duration(duration, dictionary):
00273     sas_durations = []
00274     for timed_duration in duration:
00275         timed_sas_durations = []
00276         for dur in timed_duration:
00277             var, val = dictionary.get(dur[1])[0]
00278             timed_sas_durations.append(sas_tasks.SASDuration(dur[0],var))
00279         sas_durations.append(timed_sas_durations)
00280     return sas_durations
00281 
00282 def mutex_conditions(cond_dict, condition, temporal):
00283     # return value True means that the conditions are mutex
00284     # return value False means that we don't know whether they are mutex
00285     if temporal:
00286         for time in range(3):
00287             for var,val in condition[time]:
00288                 if var in cond_dict[time]:
00289                     if cond_dict[time][var] != val:
00290                         return True
00291     else:
00292         for var,val in condition:
00293             if var in cond_dict:
00294                 if cond_dict[var] != val:
00295                     return True
00296     return False
00297 
00298 def implies(condition, condition_list, global_cond, temporal):
00299     # True: whenever condition is true also at least one condition 
00300     # from condition_list is true (given global_cond)
00301     if temporal:
00302         if [[],[],[]] in condition_list:
00303             return True
00304         for cond in condition_list:
00305             triggers = True
00306             for time in range(3):
00307                 for (var,val) in cond[time]:
00308                     if (var,val) not in condition[time] and global_cond[time].get(var)!=val:
00309                         triggers=False
00310                         break
00311                 if not triggers:
00312                     break
00313             if triggers:
00314                 return True
00315     else:
00316         if [] in condition_list:
00317             return True
00318         for cond in condition_list:
00319             triggers = True
00320             for (var,val) in cond:
00321                 if (var,val) not in condition and global_cond.get(var)!=val:
00322                     triggers=False
00323                     break
00324             if triggers:
00325                 return True
00326     return False
00327 
00328 def translate_add_effects(add_effects, dictionary, mod_effects_dict, ranges, comp_axioms,
00329                           temporal, true_atoms, false_atoms):
00330     assert temporal
00331     effect = {}
00332     mod_effect = {}
00333     possible_add_conflict = False
00334 
00335     for conditions, fact in add_effects:
00336         eff_condition_dict_list = translate_strips_conditions(conditions, dictionary, 
00337                                          ranges, comp_axioms, temporal, true_atoms,
00338                                          false_atoms)
00339         if eff_condition_dict_list is None: # Impossible condition for this effect.
00340             continue
00341         eff_condition_temporal_dicts = cartesian_product_temporal_conditions(eff_condition_dict_list)
00342         # now eff_condition_temporal_dicts is a list of temporal conditions        
00343 
00344         if temporal:
00345             eff_conditions = [[eff_dict.items() for eff_dict in eff_cond] 
00346                                 for eff_cond in eff_condition_temporal_dicts]
00347         else:
00348             eff_conditions = [eff_dict.items() 
00349                                 for eff_dict in eff_condition_temporal_dicts]
00350 
00351         if isinstance(fact, pddl.ModuleCall):
00352           for eff_num in mod_effects_dict[fact]:
00353             assert eff_num not in mod_effect
00354             mod_effect.setdefault(eff_num, eff_conditions)
00355         # wie geht hier das: 3 1 2 (3 von 1 auf 2), da unten steht ja nur die eff_con
00356         # die ist doch fuer den ganzen, oder?!?
00357         # PRE_POST gebastel eins drueber ansehen
00358         else:
00359           for var, val in dictionary[fact]:
00360             hitherto_effect = effect.setdefault(var, {})
00361             for other_val in hitherto_effect:
00362                 if other_val != val:
00363                     for other_cond in hitherto_effect[other_val]:
00364                         for eff_cond in eff_conditions:
00365                             #redictify
00366                             eff_cond_as_dict = [dict(eff_pairs)
00367                                                 for eff_pairs in eff_cond]
00368                             if not mutex_conditions(eff_cond_as_dict, 
00369                                                 other_cond, temporal):
00370                                 possible_add_conflict = True
00371             hitherto_effect.setdefault(val,[]).extend(eff_conditions)
00372     return effect, possible_add_conflict, mod_effect
00373 
00374 def translate_del_effects(del_effects,dictionary,ranges,effect,condition,
00375                           comp_axioms, temporal, time, true_atoms, false_atoms):
00376     assert temporal
00377     if temporal:
00378         assert time is not None
00379         cond_time = time*2 # start -> start condition, end -> end_condition
00380 
00381     for conditions, fact in del_effects:
00382         eff_condition_dict_list = translate_strips_conditions(conditions, dictionary,
00383                                                   ranges, comp_axioms, temporal,
00384                                                   true_atoms, false_atoms)
00385         if eff_condition_dict_list is None:
00386             continue
00387         eff_condition_temporal_dicts = cartesian_product_temporal_conditions(eff_condition_dict_list)
00388         # now eff_condition_temporal_dicts is a list of temporal conditions        
00389 
00390         if temporal:
00391             eff_conditions = [[eff_dict.items() for eff_dict in eff_cond] 
00392                               for eff_cond in eff_condition_temporal_dicts]
00393         else:
00394             eff_conditions = [eff_dict.items() 
00395                               for eff_dict in eff_condition_temporal_dicts]
00396 
00397         for var, val in dictionary[fact]:
00398             none_of_those = ranges[var] - 1
00399             hitherto_effects = effect.setdefault(var,{})
00400             
00401             for eff_condition in eff_conditions:
00402                 eff_cond_as_dict = [dict(eff_pairs) for eff_pairs in eff_condition]
00403                 # Look for matching add effect; ignore this del effect if found
00404                 found_matching_add_effect = False
00405                 uncertain_conflict = False
00406     
00407                 for other_val, other_eff_conditions in hitherto_effects.items():
00408                     if other_val != none_of_those:
00409                         if implies(eff_condition, other_eff_conditions, condition, temporal):
00410                             found_matching_add_effect = True
00411                             break
00412                         for cond in other_eff_conditions:
00413                             if not mutex_conditions(eff_cond_as_dict, 
00414                                                     cond, temporal): 
00415                                 uncertain_conflict = True
00416                 # del-effect can be ignored if some other value is added
00417                 # or the variable already has the value none-of-those
00418                 already_undefined = (condition[cond_time].get(var) == none_of_those or 
00419                                      eff_cond_as_dict[cond_time].get(var) == none_of_those)
00420                 if found_matching_add_effect or already_undefined:
00421                     continue
00422                 else:
00423                     assert not uncertain_conflict, "Uncertain conflict"
00424                     if (condition[cond_time].get(var) != val and 
00425                         eff_cond_as_dict[cond_time].get(var) != val):
00426                         # if the variable must have a different value whenever
00427                         # the operator is applied, we can ignore the delete
00428                         # effect
00429                         if (var in condition[cond_time] or
00430                             (cond_time == 2 and var in condition[1] and
00431                              condition[1][var] != val)):
00432                             continue
00433                         # Need a guard for this delete effect.
00434                         assert (var not in eff_condition[cond_time]), "Oops?"
00435                         eff_condition[cond_time].append((var, val))
00436     
00437                     del_eff_conditions = hitherto_effects.setdefault(none_of_those,[])
00438                     del_eff_conditions.append(eff_condition)
00439 
00440 def translate_assignment_effects(assign_effects, dictionary, ranges, comp_axioms, 
00441                                  temporal, true_atoms, false_atoms):
00442     assert temporal
00443     effect = {}
00444     possible_assign_conflict = False
00445 
00446     for conditions, assignment in assign_effects:
00447         eff_condition_dict_list = translate_strips_conditions(conditions, dictionary, 
00448                                          ranges, comp_axioms, temporal, true_atoms,
00449                                          false_atoms)
00450         if eff_condition_dict_list is None: # Impossible condition for this effect.
00451             continue
00452         eff_condition_temporal_dicts = cartesian_product_temporal_conditions(eff_condition_dict_list)
00453         # now eff_condition_temporal_dicts is a list of temporal conditions        
00454 
00455         if temporal:
00456             eff_conditions = [[eff_dict.items() for eff_dict in eff_cond]
00457                               for eff_cond in eff_condition_temporal_dicts]
00458         else:
00459             eff_conditions = [eff_dict.items() 
00460                               for eff_dict in eff_condition_temporal_dicts]
00461         for var, _ in dictionary[assignment.fluent]:
00462             for expvar, _ in dictionary[assignment.expression]:
00463                 val = (assignment.symbol, expvar)
00464                 hitherto_effect = effect.setdefault(var,{})
00465                 for other_val in hitherto_effect:
00466                     if other_val != val:
00467                         for other_cond in hitherto_effect[other_val]:
00468                             for eff_cond in eff_conditions:
00469                                 # redictify
00470                                 eff_cond_as_dict = [dict(eff_pairs) 
00471                                                     for eff_pairs in eff_cond]
00472                                 if not mutex_conditions(eff_cond_as_dict,
00473                                                         other_cond, temporal):
00474                                     possible_assign_conflict = True
00475                 hitherto_effect.setdefault(val,[]).extend(eff_conditions)
00476     return effect, possible_assign_conflict
00477 
00478 def translate_strips_operator(operator, dictionary, mod_effects_dict, ranges, comp_axioms):
00479     # NOTE: This function does not really deal with the intricacies of properly
00480     # encoding delete effects for grouped propositions in the presence of
00481     # conditional effects. It should work ok but will bail out in more
00482     # complicated cases even though a conflict does not necessarily exist.
00483 
00484     assert False, "Actions not supported, use durative actions"
00485     condition = translate_strips_conditions(operator.condition, dictionary, ranges, comp_axioms)
00486     if condition is None:
00487         return None
00488 
00489     effect, possible_add_conflict, mod_eff = translate_add_effects(operator.add_effects, 
00490                                                           dictionary, mod_effects_dict, ranges, comp_axioms, False)
00491     translate_del_effects(operator.del_effects, dictionary, ranges, effect,
00492                           condition, comp_axioms, False, None)
00493 
00494     if possible_add_conflict:
00495         print operator.name
00496     assert not possible_add_conflict, "Conflicting add effects?"
00497 
00498     assign_effect, possible_assign_conflict = \
00499         translate_assignment_effects(operator.assign_effects, dictionary, ranges, comp_axioms, False)
00500     
00501     if possible_assign_conflict:
00502         print operator.name
00503     assert not possible_assign_conflict, "Conflicting assign effects?"
00504 
00505     pre_post = []
00506     for var in effect:
00507         for (post, eff_condition_lists) in effect[var].iteritems():
00508             pre = condition.get(var, -1)
00509             if pre != -1:
00510                 del condition[var]
00511             for eff_condition in eff_condition_lists:
00512                 pre_post.append((var, pre, post, eff_condition))
00513     prevail = condition.items()
00514 
00515     assign_effects = []
00516     for var in assign_effect:
00517         for ((op, valvar), eff_condition_lists) in assign_effect[var].iteritems():
00518             for eff_condition in eff_condition_lists:
00519                 sas_effect = sas_tasks.SASAssignmentEffect(var, op, valvar, 
00520                                                        eff_condition)
00521                 assign_effects.append(sas_effect)
00522 
00523     return sas_tasks.SASOperator(operator.name, prevail, pre_post, assign_effects)
00524 
00525 def cartesian_product_temporal_conditions(conds):
00526     """ Expands disjunctive temporal conditions.
00527 
00528         Forms a disjunction as a list of temporal conditions (length 3 list)
00529         from a temporal condition where each entry is a disjunction as a list of
00530         conditions by applying the cartesian product.
00531         
00532     """
00533     assert len(conds) == 3, "Unexpected length for temporal condition"
00534     return [list(cond) for cond in itertools.product(*conds)]
00535 
00536 
00537 def translate_temporal_strips_operator_aux(operator, dictionary, mod_effects_dict, ranges,
00538                                            comp_axioms, condition, true_atoms,
00539                                            false_atoms):
00540     # NOTE: This function does not really deal with the intricacies of properly
00541     # encoding delete effects for grouped propositions in the presence of
00542     # conditional effects. It should work ok but will bail out in more
00543     # complicated cases even though a conflict does not necessarily exist.
00544 
00545     duration = translate_operator_duration(operator.duration, dictionary)
00546 
00547     if condition is None:
00548         print "operator condition is None (invalid)"
00549         return None
00550 
00551     effect = []
00552     mod_effects = []
00553     possible_add_conflict = False
00554     for time in range(2):
00555         eff, poss_conflict, mod_eff = translate_add_effects(operator.add_effects[time], 
00556                                                    dictionary, mod_effects_dict, ranges,
00557                                                    comp_axioms, True,
00558                                                    true_atoms, false_atoms)
00559         translate_del_effects(operator.del_effects[time], dictionary, ranges, 
00560                               eff, condition, comp_axioms, True, time,
00561                               true_atoms, false_atoms)
00562         effect.append(eff)
00563         mod_effects.append(mod_eff)
00564         possible_add_conflict |= poss_conflict
00565 
00566     if possible_add_conflict:
00567         print operator.name
00568     assert not possible_add_conflict
00569 
00570     assign_effect = []
00571     possible_assign_conflict = False
00572     for time in range(2):
00573         eff, conflict = translate_assignment_effects(operator.assign_effects[time], 
00574                                                      dictionary, ranges,
00575                                                      comp_axioms, True,
00576                                                      true_atoms, false_atoms)
00577         assign_effect.append(eff)
00578         possible_assign_conflict |= conflict
00579 
00580     if possible_assign_conflict:
00581         print operator.name
00582     assert not possible_assign_conflict
00583 
00584     pre_post = [[],[]]
00585     for time in range(2):
00586         cond_time = time*2 # start -> start condition, end -> end_condition
00587         for var in effect[time]:
00588             for (post, eff_condition_lists) in effect[time][var].iteritems():
00589                 pre = condition[cond_time].get(var, -1)
00590                 if pre != -1:
00591                     del condition[cond_time][var]
00592 
00593                 # substitute normal effect for conditional effects if it has only
00594                 # one at-start condition on a binary variable which is equivalent
00595                 # to the effect variable
00596                 # example: temporal effect 1 6 0 0 0 6 -1 1
00597                 #          becomes 0 0 0 6 0 1 
00598                 # NOTE: this changes the applicability of the action, because we 
00599                 # introduce a "write operation" on the variable in the case, where 
00600                 # the original conditional effect does not trigger (hence not 
00601                 # affecting the variable)
00602                 if len(eff_condition_lists) == 1: # only one conditon
00603                     eff_condition = eff_condition_lists[0]
00604                     if (eff_condition[1] == [] and eff_condition[2] == [] and
00605                         len(eff_condition[0]) == 1):
00606                         ecvar, ecval = eff_condition[0][0]
00607                         if ecvar == var and ranges[var] == 2:
00608                             eff_condition[0] = []
00609                 for eff_condition in eff_condition_lists:
00610                     pre_post[time].append((var, pre, post, eff_condition))
00611     prevail = [cond.items() for cond in condition]
00612 
00613     assign_effects = [[],[]]
00614     for time in range(2):
00615         for var in assign_effect[time]:
00616             for ((op, valvar), eff_condition_lists) \
00617                 in assign_effect[time][var].iteritems():
00618                 for eff_condition in eff_condition_lists:
00619                     sas_effect = sas_tasks.SASAssignmentEffect(var, op, valvar, 
00620                                                            eff_condition, True)
00621                     assign_effects[time].append(sas_effect)
00622 
00623     return sas_tasks.SASTemporalOperator(operator.name, duration, 
00624                 prevail, pre_post, assign_effects, mod_effects)
00625 
00626 def translate_temporal_strips_operator(operator, dictionary, mod_effects_dict, ranges,
00627                                        comp_axioms, true_atoms, false_atoms):
00628     condition = translate_strips_conditions(operator.conditions, dictionary,
00629                                             ranges, comp_axioms, True,
00630                                             true_atoms, false_atoms)
00631     if condition is None:
00632         return None
00633     # condition now is a list for at start/over all/at end where each entry is a
00634     # list of conditions forming a disjunction We handle the disjunctions by
00635     # forming one operator per disjunction. As we have three disjunctions for
00636     # the temporal operator, we need to combine them using the cartesian product
00637     # forming the resulting operators
00638     temp_conds = cartesian_product_temporal_conditions(condition)
00639     ops = []
00640     for temp_cond in temp_conds:
00641         op = translate_temporal_strips_operator_aux(operator, dictionary, mod_effects_dict, 
00642                                                     ranges, comp_axioms,
00643                                                     temp_cond, true_atoms,
00644                                                     false_atoms)
00645         if op is not None:
00646             ops.append(op)
00647     return ops
00648 
00649 def translate_strips_axiom(axiom, dictionary, ranges, comp_axioms):
00650     # returns a list of axioms as condition might give a disjunction
00651     conditions = translate_strips_conditions(axiom.condition, dictionary, ranges, comp_axioms)
00652     if conditions is None:
00653         return []
00654     if axiom.effect.negated:
00655         [(var, _)] = dictionary[axiom.effect.positive()]
00656         effect = (var, ranges[var] - 1)
00657     else:
00658         [effect] = dictionary[axiom.effect]
00659     axioms = []
00660     for condition in conditions:
00661         axioms.append(sas_tasks.SASAxiom(condition.items(), effect))
00662     return axioms
00663 
00664 def translate_numeric_axiom(axiom, dictionary):
00665     effect = dictionary.get(axiom.effect)[0][0]
00666     op = axiom.op
00667     parts = []
00668     for part in axiom.parts:
00669         if isinstance(part, pddl.PrimitiveNumericExpression):
00670             parts.append(dictionary.get(part)[0][0])
00671         else: # part is PropositionalNumericAxiom
00672             parts.append(dictionary.get(part.effect)[0][0])
00673     return sas_tasks.SASNumericAxiom(op, parts, effect)
00674 
00675 def translate_strips_operators(actions, strips_to_sas, module_effects_to_sas, ranges, comp_axioms):
00676     result = []
00677     actions.sort(lambda x,y: cmp(x.name,y.name))
00678     for action in actions:
00679         sas_op = translate_strips_operator(action, strips_to_sas, module_effects_to_sas, ranges, comp_axioms)
00680         if sas_op:
00681             result.append(sas_op)
00682     return result
00683 
00684 def translate_temporal_strips_operators(actions, strips_to_sas, module_effects_to_sas, ranges, comp_axioms,
00685         true_atoms, false_atoms):
00686     result = []
00687     actions.sort(lambda x,y: cmp(x.name,y.name))
00688     for action in actions:
00689         sas_ops = translate_temporal_strips_operator(action, strips_to_sas, module_effects_to_sas,
00690                                                      ranges, comp_axioms, 
00691                                                      true_atoms, false_atoms)
00692         if sas_ops:
00693             result.extend(sas_ops)
00694     return result
00695 
00696 def translate_strips_axioms(axioms, strips_to_sas, ranges, comp_axioms):
00697     result = []
00698     axioms.sort(lambda x,y: cmp(x.name,y.name))
00699     for axiom in axioms:
00700         sas_axioms = translate_strips_axiom(axiom, strips_to_sas, ranges, comp_axioms)
00701         if sas_axioms:
00702             result.extend(sas_axioms)
00703     return result
00704 
00705 def translate_task(strips_to_sas, module_effects_to_sas, ranges, init, goals, actions, 
00706                    durative_actions, axioms, num_axioms, num_axioms_by_layer, 
00707                    max_num_layer, num_axiom_map, const_num_axioms, oplinit, objects,
00708                    modules, module_inits, subplan_generators, init_constant_predicates, init_constant_numerics):
00709 
00710     axioms, axiom_init, axiom_layer_dict, true_atoms, false_atoms = axiom_rules.handle_axioms(
00711       actions, durative_actions, axioms, goals)
00712 
00713     init = init + axiom_init
00714 
00715     # filter trivial true_atoms from goal
00716     goals = [g for g in goals if g not in true_atoms]   # FIXME: empty goal would be handled nicely by search
00717     # if any atom in goal is false, the task is unsolvable
00718     for fa in false_atoms:
00719         if fa in goals:
00720             print "False atom in goal:"
00721             fa.dump()
00722             return unsolvable_sas_task("False atom in goal")
00723 
00724     comp_axioms = [{},[]]
00725     goal_dict_list = translate_strips_conditions(goals, strips_to_sas, ranges, comp_axioms)
00726     assert len(goal_dict_list) == 1, "Negative goal not supported"
00727     ## we could substitute the negative goal literal in
00728     ## normalize.substitute_complicated_goal, using an axiom. We currently
00729     ## don't do this, because we don't run into this assertion, if the
00730     ## negative goal is part of finite domain variable with only two
00731     ## values, which is most of the time the case, and hence refrain from
00732     ## introducing axioms (that are not supported by all heuristics)
00733     goal_pairs = goal_dict_list[0].items()
00734     goal = sas_tasks.SASGoal(goal_pairs)
00735 
00736     # FIXME: remove this, defunct anyways
00737     operators = translate_strips_operators(actions,
00738                                         strips_to_sas, module_effects_to_sas, ranges, comp_axioms)
00739     temp_operators = translate_temporal_strips_operators(durative_actions, 
00740                                         strips_to_sas, module_effects_to_sas, ranges, comp_axioms,
00741                                         true_atoms, false_atoms)
00742     
00743     axioms = translate_strips_axioms(axioms, strips_to_sas, ranges, comp_axioms)
00744     sas_num_axioms = [translate_numeric_axiom(axiom,strips_to_sas) for axiom in num_axioms 
00745                       if axiom not in const_num_axioms and
00746                       axiom.effect not in num_axiom_map]
00747 
00748 
00749     axiom_layers = [-1] * len(ranges)
00750     
00751     ## each numeric axiom gets its own layer (a wish of a colleague for 
00752     ## knowledge compilation or search. If you use only the translator,
00753     ## you can change this)
00754     num_axiom_layer = 0
00755     for layer in num_axioms_by_layer:
00756         num_axioms_by_layer[layer].sort(lambda x,y: cmp(x.name,y.name))
00757         for axiom in num_axioms_by_layer[layer]:
00758             if axiom.effect not in num_axiom_map:
00759                 [(var,val)] = strips_to_sas[axiom.effect]
00760                 if layer == -1:
00761                     axiom_layers[var] = -1
00762                 else:
00763                     axiom_layers[var] = num_axiom_layer
00764                     num_axiom_layer += 1
00765     for axiom in comp_axioms[1]:
00766         axiom_layers[axiom.effect] = num_axiom_layer
00767     for atom, layer in axiom_layer_dict.iteritems():
00768         assert layer >= 0
00769         [(var, val)] = strips_to_sas[atom]
00770         axiom_layers[var] = layer + num_axiom_layer + 1
00771     variables = sas_tasks.SASVariables(ranges, axiom_layers)
00772 
00773     init_values = [rang - 1 for rang in ranges]
00774     # Closed World Assumption: Initialize to "range - 1" == Nothing.
00775     for fact in init:
00776         if isinstance(fact,pddl.Atom):
00777             pairs = strips_to_sas.get(fact, [])  # empty for static init facts
00778             for var, val in pairs:
00779                 assert init_values[var] == ranges[var] - 1, "Inconsistent init facts!"
00780                 init_values[var] = val
00781         else: # isinstance(fact,pddl.FunctionAssignment)
00782             pairs = strips_to_sas.get(fact.fluent,[]) #empty for constant functions 
00783             for (var, _) in pairs:
00784                 val = fact.expression.value
00785                 assert init_values[var] == ranges[var] - 1, "Inconsistent init facts!"
00786                 init_values[var]=val
00787     for axiom in const_num_axioms:
00788         var = strips_to_sas.get(axiom.effect)[0][0]
00789         val = axiom.parts[0].value
00790         init_values[var]=val
00791     init = sas_tasks.SASInit(init_values)
00792 
00793     # TODO: move this block to translate_modules
00794     strips_condition_modules = [module for module in modules if module.type == "conditionchecker"]
00795     strips_effect_modules = [module for module in modules if module.type == "effect"]
00796     strips_cost_modules = [module for module in modules if module.type == "cost"]
00797     strips_condition_modules.sort(lambda x,y : cmp(str(x), str(y)))
00798     strips_effect_modules.sort(lambda x,y : cmp(str(x), str(y)))
00799     strips_cost_modules.sort(lambda x,y : cmp(str(x), str(y)))
00800     condition_modules = []
00801     effect_modules = []
00802     cost_modules = []
00803 
00804     for mod in strips_condition_modules:
00805       assert mod.parent is not None
00806       sas_params = []
00807       for (ground_param, pddl_param) in zip(mod.parameters, mod.parent.parameters):
00808         sas_params.append((pddl_param.name, ground_param.type, ground_param.name))
00809       # strips_to_sas call is very hacky
00810       assert len(strips_to_sas[mod.toModuleCall()]) == 1
00811       assert len(strips_to_sas[mod.toModuleCall()][0]) == 2
00812       mod_var = strips_to_sas[mod.toModuleCall()][0][0]
00813       condition_modules.append(sas_tasks.SASConditionModule(mod.modulecall, sas_params, mod_var))
00814     for mod in strips_effect_modules:
00815       assert mod.parent is not None
00816       sas_params = []
00817       for (ground_param, pddl_param) in zip(mod.parameters, mod.parent.parameters):
00818         sas_params.append((pddl_param.name, ground_param.type, ground_param.name))
00819       sas_effs = []
00820       for eff in mod.effects:
00821         assert len(strips_to_sas[eff]) == 1
00822         assert len(strips_to_sas[eff][0]) == 2
00823         sas_effs.append(strips_to_sas[eff][0][0])
00824       # missing eff num + eff vars
00825       effect_modules.append(sas_tasks.SASEffectModule(mod.modulecall, sas_params, module_effects_to_sas[mod.toModuleCall()][0], sas_effs))
00826     for mod in strips_cost_modules:
00827       assert mod.parent is not None # ?
00828       sas_params = []
00829       for (ground_param, pddl_param) in zip(mod.parameters, mod.parent.parameters):
00830         sas_params.append((pddl_param.name, ground_param.type, ground_param.name))
00831       # make sure strips_to_sas is not mixed badly with condition modules
00832       assert len(strips_to_sas[mod.toModuleCall()]) == 1
00833       assert len(strips_to_sas[mod.toModuleCall()][0]) == 2
00834       mod_var = strips_to_sas[mod.toModuleCall()][0][0]
00835       cost_modules.append(sas_tasks.SASConditionModule(mod.modulecall, sas_params, mod_var))
00836 
00837     return sas_tasks.SASTask(variables, init, goal, operators, 
00838                              temp_operators, axioms, sas_num_axioms, comp_axioms[1], oplinit, objects, condition_modules, effect_modules, cost_modules, sas_tasks.SASTranslation(strips_to_sas), module_inits, subplan_generators, 
00839                              init_constant_predicates, init_constant_numerics)
00840 
00841 def unsolvable_sas_task(msg):
00842     print "%s! Generating unsolvable task..." % msg
00843     variables = sas_tasks.SASVariables([2], [-1])
00844     init = sas_tasks.SASInit([0])
00845     goal = sas_tasks.SASGoal([(0, 1)])
00846     operators = []
00847     temp_operators = []
00848     axioms = []
00849     num_axioms = []
00850     comp_axioms = []
00851     objects = []
00852     oplinit = []
00853     condition_modules = []
00854     effect_modules = []
00855     cost_modules = []
00856     strips_to_sas = {}
00857     module_inits = []
00858     subplan_generators = []
00859     init_cons_pred = []
00860     init_cons_numer = []
00861     return sas_tasks.SASTask(variables, init, goal, operators,
00862             temp_operators, axioms, num_axioms, comp_axioms, oplinit, objects, condition_modules, effect_modules, cost_modules, sas_tasks.SASTranslation(strips_to_sas), module_inits, subplan_generators,
00863             init_cons_pred, init_cons_numer)
00864 
00865 def pddl_to_sas(task):
00866     print "Instantiating..."
00867     (relaxed_reachable, atoms, num_fluents, actions, 
00868         durative_actions, axioms, num_axioms, modules, 
00869         init_constant_predicates, init_constant_numerics,
00870         reachable_action_params) = instantiate.explore(task)
00871 
00872     if not relaxed_reachable:
00873         return unsolvable_sas_task("No relaxed solution")
00874 
00875     num_axioms = list(num_axioms)
00876     num_axioms.sort(lambda x,y: cmp(x.name,y.name))
00877 
00878     # HACK! Goals should be treated differently.
00879     # Update: This is now done during normalization. The assertions
00880     # are only left here to be on the safe side. Can be removed eventually
00881     if isinstance(task.goal, pddl.Conjunction):
00882         goal_list = task.goal.parts
00883     else:
00884         goal_list = [task.goal]
00885     for item in goal_list:
00886         assert isinstance(item, pddl.Literal)
00887 
00888     groups, mutex_groups, translation_key = fact_groups.compute_groups(
00889         task, atoms, reachable_action_params,
00890         return_mutex_groups=WRITE_ALL_MUTEXES,
00891         partial_encoding=USE_PARTIAL_ENCODING,
00892         safe=USE_SAFE_INVARIANT_SYNTHESIS)
00893 
00894     num_axioms_by_layer, max_num_layer, num_axiom_map, const_num_axioms = \
00895         numeric_axiom_rules.handle_axioms(num_axioms)
00896 
00897     print "Building STRIPS to SAS dictionary..."
00898     ranges, strips_to_sas, module_effects_to_sas = strips_to_sas_dictionary(groups, num_axioms, num_axiom_map, num_fluents, modules)
00899     print "Translating task..."
00900     assert not actions, "There shouldn't be any actions - just temporal actions"
00901     sas_task = translate_task(strips_to_sas, module_effects_to_sas, ranges, task.init, goal_list,
00902                               actions, durative_actions, axioms, num_axioms,
00903                               num_axioms_by_layer, max_num_layer, num_axiom_map,
00904                               const_num_axioms, task.oplinit, task.objects, modules, task.module_inits, task.subplan_generators, init_constant_predicates, init_constant_numerics)
00905 
00906     simplify.constrain_end_effect_conditions(sas_task)
00907     mutex_key = build_mutex_key(strips_to_sas, mutex_groups)
00908 
00909 #    try:
00910 #        simplify.filter_unreachable_propositions(
00911 #            sas_task, mutex_key, translation_key)
00912 #    except simplify.Impossible:
00913 #        return unsolvable_sas_task("Simplified to trivially false goal")
00914 
00915     write_translation_key(strips_to_sas)
00916     if WRITE_ALL_MUTEXES:
00917         write_mutex_key(mutex_key)
00918     return sas_task
00919 
00920 def build_mutex_key(strips_to_sas, groups):
00921     group_keys = []
00922     for group in groups:
00923         group_key = []
00924         for fact in group:
00925             if strips_to_sas.get(fact):
00926                 for var, val in strips_to_sas[fact]:
00927                     group_key.append((var, val, str(fact)))
00928             else:
00929                 print "not in strips_to_sas, left out:", fact
00930         group_keys.append(group_key)
00931     return group_keys
00932 
00933 def write_translation_key(strips_to_sas):
00934     var_file = file("variables.groups", "w")
00935     vars = dict()
00936     for exp,[(var, val)] in strips_to_sas.iteritems():
00937         vars.setdefault(var, []).append((val, exp))
00938     for var in range(len(vars)):
00939         print >> var_file, "var%d" % var
00940         vals = sorted(vars[var]) 
00941         for (val, exp) in vals:
00942             print >> var_file, "   %d: %s" % (val, exp)
00943         if val != -2:
00944             print >> var_file, "   %d: <none of those>" % (val + 1)
00945 
00946 def write_mutex_key(mutex_key):
00947     invariants_file = file("all.groups", "w")
00948     print >> invariants_file, "begin_groups"
00949     print >> invariants_file, len(mutex_key)
00950     for group in mutex_key:
00951         #print map(str, group)
00952         no_facts = len(group)
00953         print >> invariants_file, "group"
00954         print >> invariants_file, no_facts
00955         for var, val, fact in group:
00956             #print fact
00957             assert str(fact).startswith("Atom ")
00958             predicate = str(fact)[5:].split("(")[0]
00959             #print predicate
00960             rest = str(fact).split("(")[1]
00961             rest = rest.strip(")").strip()
00962             if not rest == "":
00963                 #print "there are args" , rest
00964                 args = rest.split(",")
00965             else:
00966                 args = []
00967             print_line = "%d %d %s %d " % (var, val, predicate, len(args))
00968             for arg in args:
00969                 print_line += str(arg).strip() + " "
00970             #print fact
00971             #print print_line
00972             print >> invariants_file, print_line
00973     print >> invariants_file, "end_groups"
00974     invariants_file.close()
00975 
00976 
00977 if __name__ == "__main__":
00978     import pddl
00979     sys.stdout = sys.__stderr__
00980     print "Parsing..."
00981     task = pddl.open()
00982     if task.domain_name in ["protocol", "rover"]:
00983         # This is, of course, a HACK HACK HACK!
00984         # The real issue is that ALLOW_CONFLICTING_EFFECTS = True
00985         # is actually the correct semantics, but then we don't get to filter
00986         # out operators that are impossible to apply due to mutexes between
00987         # different SAS+ variables. For example,
00988         # ALLOW_CONFLICTING_EFFECTS = True does not filter on(a,a) in
00989         # blocksworld/4-0.
00990         ALLOW_CONFLICTING_EFFECTS = True
00991 
00992     # EXPERIMENTAL!
00993     # import psyco
00994     # psyco.full()
00995 
00996     sas_task = pddl_to_sas(task)
00997     print "Writing output..."
00998     #sas_task.output(file("output.sas", "w"))
00999     sas_task.output(sys.__stdout__)
01000     print "Done!"


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