axiom_rules.py
Go to the documentation of this file.
00001 import pddl
00002 import sas_tasks
00003 
00004 from collections import defaultdict
00005 
00006 def handle_axioms(operators, durative_operators, axioms, goals):
00007     print "Processing axioms..."
00008 
00009     axioms_by_atom = get_axioms_by_atom(axioms)
00010 
00011     axiom_literals = compute_necessary_axiom_literals(axioms_by_atom, operators, 
00012                                                       durative_operators, goals)
00013     axiom_init = get_axiom_init(axioms_by_atom, axiom_literals)
00014     axioms = simplify_axioms(axioms_by_atom, axiom_literals)
00015 
00016     axioms, true_atoms, false_atoms = compute_constant_axioms(axioms)
00017     # we moved some axioms (actually their heads) to true_atoms and false_atoms
00018     # (i.e. they are not axioms any more). now repair axioms_by_atom by
00019     # rebuilding it
00020     axioms_by_atom = get_axioms_by_atom(axioms)
00021     # the axiom_literals are only used to know which ones need to be negated, so
00022     # we remove the constant heads from those
00023     axiom_literals = [a for a in axiom_literals
00024                       if a.positive() not in true_atoms and
00025                          a.positive() not in false_atoms]
00026     # The same goes for init. The true_atoms and false_atoms should be handled
00027     # in the translation
00028     axiom_init = [a for a in axiom_init
00029                   if a.positive() not in true_atoms and
00030                      a.positive() not in false_atoms]
00031 
00032     axioms = compute_negative_axioms(axioms_by_atom, axiom_literals)
00033     # NOTE: compute_negative_axioms more or less invalidates axioms_by_atom.
00034     #       Careful with that axe, Eugene!
00035     axiom_layers = compute_axiom_layers(axioms, axiom_init)
00036     print "Found", len(true_atoms), "axioms that are always true and", len(false_atoms), "that are always false"
00037     return axioms, list(axiom_init), axiom_layers, true_atoms, false_atoms
00038 
00039 def get_axioms_by_atom(axioms):
00040     axioms_by_atom = {}
00041     for axiom in axioms:
00042         axioms_by_atom.setdefault(axiom.effect, []).append(axiom)
00043     return axioms_by_atom
00044 
00045 def compute_axiom_layers(axioms, axiom_init):
00046     NO_AXIOM = -1
00047     UNKNOWN_LAYER = -2
00048     FIRST_MARKER = -3
00049 
00050     depends_on = {}
00051     for axiom in axioms:
00052         effect_atom = axiom.effect.positive()
00053         effect_sign = not axiom.effect.negated
00054         effect_init_sign = effect_atom in axiom_init
00055         if effect_sign != effect_init_sign:
00056             depends_on.setdefault(effect_atom, set())
00057             for condition in axiom.condition:
00058                 condition_atom = condition.positive()
00059                 condition_sign = not condition.negated
00060                 condition_init_sign = condition_atom in axiom_init
00061                 if condition_sign == condition_init_sign:
00062                     depends_on[effect_atom].add((condition_atom, +1))
00063                 else:
00064                     depends_on[effect_atom].add((condition_atom, +0))
00065 
00066     layers = dict([(atom, UNKNOWN_LAYER) for atom in depends_on])
00067     def find_level(atom, marker):
00068         layer = layers.get(atom, NO_AXIOM)
00069         if layer == NO_AXIOM:
00070             return 0
00071 
00072         if layer == marker:
00073             # Found positive cycle: May return 0 but not set value.
00074             return 0
00075         elif layer <= FIRST_MARKER:
00076             # Found negative cycle: Error.
00077             assert False, "Cyclic dependencies in axioms; cannot stratify."
00078         if layer == UNKNOWN_LAYER:
00079             layers[atom] = marker
00080             layer = 0
00081             for (condition_atom, bonus) in depends_on[atom]:
00082                 layer = max(layer, find_level(condition_atom, marker - bonus) + bonus)
00083             layers[atom] = layer
00084         return layer
00085     for atom in depends_on:
00086         find_level(atom, FIRST_MARKER)
00087 
00088     #for atom, layer in layers.iteritems():
00089     #  print "Layer %d: %s" % (layer, atom)
00090     return layers
00091 
00092 def compute_necessary_axiom_literals(axioms_by_atom, operators, 
00093                                      durative_operators, goal):
00094     necessary_literals = set()
00095     queue = []
00096 
00097     def register_literals(literals, negated):
00098         for literal in literals:
00099             if isinstance(literal,pddl.Literal):
00100                 if literal.positive() in axioms_by_atom:   # This is an axiom literal
00101                     if negated:
00102                         literal = literal.negate()
00103                     if literal not in necessary_literals:
00104                         necessary_literals.add(literal)
00105                         queue.append(literal)
00106 
00107     # Initialize queue with axioms required for goal and operators.
00108     register_literals(goal, False)
00109     for op in operators:
00110         register_literals(op.condition, False)
00111         for (cond, _) in op.add_effects:
00112             register_literals(cond, False)
00113         for (cond, _) in op.del_effects:
00114             register_literals(cond, True)
00115 
00116     for op in durative_operators:
00117         for time in range(3):
00118             register_literals(op.conditions[time], False)
00119         for time in range(2):
00120             for (cond, _) in op.add_effects[time]:
00121                 for tt in range(3):
00122                     register_literals(cond[tt], False)
00123             for (cond, _) in op.del_effects[time]:
00124                 for tt in range(3):
00125                     register_literals(cond[tt], True)
00126 
00127     while queue:
00128         literal = queue.pop()
00129         axioms = axioms_by_atom[literal.positive()]
00130         for axiom in axioms:
00131             register_literals(axiom.condition, literal.negated)
00132     return necessary_literals
00133 
00134 def get_axiom_init(axioms_by_atom, necessary_literals):
00135     result = set()
00136     for atom in axioms_by_atom:
00137         if atom not in necessary_literals and atom.negate() in necessary_literals:
00138             # Initial value for axiom: False (which is omitted due to closed world
00139             # assumption) unless it is only needed negatively.
00140             result.add(atom)
00141     return result
00142 
00143 def simplify_axioms(axioms_by_atom, necessary_literals):
00144     necessary_atoms = set([literal.positive() for literal in necessary_literals])
00145     new_axioms = []
00146     for atom in necessary_atoms:
00147         axioms = simplify(axioms_by_atom[atom])
00148         axioms_by_atom[atom] = axioms
00149         new_axioms += axioms
00150     return new_axioms
00151 
00152 def remove_duplicates(alist):
00153     next_elem = 1
00154     for i in xrange(1, len(alist)):
00155         if alist[i] != alist[i - 1]:
00156             alist[next_elem] = alist[i]
00157             next_elem += 1
00158     alist[next_elem:] = []
00159 
00160 def simplify(axioms):
00161     """Remove duplicate axioms, duplicates within axioms, and dominated axioms."""
00162 
00163     # Remove duplicates from axiom conditions.
00164     for axiom in axioms:
00165         axiom.condition.sort()
00166         remove_duplicates(axiom.condition)
00167 
00168     # Remove dominated axioms.
00169     axioms_by_literal = {}
00170     for axiom in axioms:
00171         for literal in axiom.condition:
00172             axioms_by_literal.setdefault(literal, set()).add(id(axiom))
00173 
00174     axioms_to_skip = set()
00175     for axiom in axioms:
00176         if id(axiom) in axioms_to_skip:
00177             continue   # Required to keep one of multiple identical axioms.
00178         if not axiom.condition: # empty condition: dominates everything
00179             return [axiom]
00180         literals = iter(axiom.condition)
00181         dominated_axioms = axioms_by_literal[literals.next()]
00182         for literal in literals:
00183             dominated_axioms &= axioms_by_literal[literal]
00184         for dominated_axiom in dominated_axioms:
00185             if dominated_axiom != id(axiom):
00186                 axioms_to_skip.add(dominated_axiom)
00187     return [axiom for axiom in axioms if id(axiom) not in axioms_to_skip]
00188 
00189 
00190 def compute_constant_axioms(axioms):
00191     """ Computes which axioms always evaluate to the same constant values """
00192     true_atoms = set()
00193     false_atoms = set()
00194     new_axioms = set(axioms)
00195     # this will be a subset of axioms, where some axioms have simpler conditions
00196     # the removed axiom's heads should appear in true_atoms or false_atoms
00197 
00198     axioms_by_condition = defaultdict(set)
00199     axioms_by_negated_condition = defaultdict(set)
00200 
00201     queue = [] # true literals that have not been processed, yet
00202     condition_counter = dict() 
00203     # number of unsatisfied conditions for each axiom
00204     axiom_counter = defaultdict(int) # number of axioms for each effect
00205 
00206     # initialize counters and queue
00207     for axiom in new_axioms:
00208         assert not axiom.effect.negated
00209         axiom_counter[axiom.effect] += 1
00210         if not axiom.condition:
00211             if axiom.effect not in true_atoms:
00212                 true_atoms.add(axiom.effect)
00213                 queue.append(axiom.effect)
00214         else:
00215             for cond in axiom.condition:
00216                 axioms_by_condition[cond].add(axiom)
00217                 axioms_by_negated_condition[cond.negate()].add(axiom)
00218             condition_counter[axiom] = len(set(axiom.condition))
00219 
00220     while queue:
00221         literal = queue.pop()
00222         for axiom in axioms_by_condition[literal]:
00223             condition_counter[axiom] -= 1
00224             if not condition_counter[axiom]:
00225                 if axiom.effect not in true_atoms:
00226                     true_atoms.add(axiom.effect)
00227                     queue.append(axiom.effect)
00228         for axiom in axioms_by_negated_condition[literal]:
00229             # axiom can never trigger, so we remove it
00230             if axiom in new_axioms:
00231                 new_axioms.remove(axiom)
00232                 axiom_counter[axiom.effect] -= 1
00233                 if not axiom_counter[axiom.effect]:
00234                     # axiom head can never become true
00235                     assert axiom.effect not in false_atoms
00236                     false_atoms.add(axiom.effect)
00237                     queue.append(axiom.effect.negate())
00238 
00239     # filter all axioms from new_atoms that have a constantly true
00240     # effect and simplify all other axiom conditions
00241     for axiom in list(new_axioms):
00242         assert not axiom.effect in false_atoms # should already be removed
00243         if axiom.effect in true_atoms:
00244             new_axioms.remove(axiom)
00245         else:
00246             axiom.condition = list(set(axiom.condition) - true_atoms)
00247     return list(new_axioms), list(true_atoms), list(false_atoms)
00248 
00249 
00250 def compute_negative_axioms(axioms_by_atom, necessary_literals):
00251     new_axioms = []
00252     for literal in necessary_literals:
00253         if literal.negated:
00254             new_axioms += negate(axioms_by_atom[literal.positive()])
00255         else:
00256             new_axioms += axioms_by_atom[literal]
00257     return new_axioms
00258 
00259 def negate(axioms):
00260     assert axioms
00261     result = [pddl.PropositionalAxiom(axioms[0].name, [], axioms[0].effect.negate())]
00262     for axiom in axioms:
00263         condition = axiom.condition
00264         assert len(condition) > 0, "Negated axiom impossible; cannot deal with that"
00265         if len(condition) == 1: # Handle easy special case quickly.
00266             new_literal = condition[0].negate()
00267             for result_axiom in result:
00268                 result_axiom.condition.append(new_literal)
00269         else:
00270             new_result = []
00271             for literal in condition:
00272                 literal = literal.negate()
00273                 for result_axiom in result:
00274                     new_axiom = result_axiom.clone()
00275                     new_axiom.condition.append(literal)
00276                     new_result.append(new_axiom)
00277             result = new_result
00278     result = simplify(result)
00279     return result


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