build_model.py
Go to the documentation of this file.
00001 #! /usr/bin/env python
00002 # -*- coding: latin-1 -*-
00003 
00004 import sys
00005 
00006 import pddl
00007 
00008 def convert_rules(prog):
00009   RULE_TYPES = {"join": JoinRule, "product": ProductRule, "project": ProjectRule}
00010   result = []
00011   for rule in prog.rules:
00012     RuleType = RULE_TYPES[rule.type]
00013     new_effect, new_conditions = variables_to_numbers(rule.effect, rule.conditions)
00014     rule = RuleType(new_effect, new_conditions)
00015     rule.validate()
00016     result.append(rule)
00017   return result
00018 
00019 def variables_to_numbers(effect, conditions):
00020   new_effect_args = list(effect.args)
00021   rename_map = {}
00022   for i, arg in enumerate(effect.args):
00023     if isinstance(arg,pddl.Variable):
00024       rename_map[arg] = i
00025       new_effect_args[i] = i
00026   new_effect = pddl.Atom(effect.predicate, new_effect_args)
00027 
00028   new_conditions = []
00029   for cond in conditions:
00030     new_cond_args = [rename_map.get(arg, arg) for arg in cond.args]
00031     new_conditions.append(pddl.Atom(cond.predicate, new_cond_args))
00032   return new_effect, new_conditions
00033 
00034 class BuildRule:
00035   def prepare_effect(self, new_atom, cond_index):
00036     effect_args = list(self.effect.args)
00037     cond = self.conditions[cond_index]
00038     for var_no, obj in zip(cond.args, new_atom.args):
00039       if isinstance(var_no, int):
00040         effect_args[var_no] = obj
00041     return effect_args
00042   def __str__(self):
00043     return "%s :- %s" % (self.effect, ", ".join(map(str, self.conditions)))
00044     
00045 class JoinRule(BuildRule):
00046   def __init__(self, effect, conditions):
00047     self.effect = effect
00048     self.conditions = conditions
00049     left_args = conditions[0].args
00050     right_args = conditions[1].args
00051     left_vars = set([var for var in left_args if isinstance(var, int)])
00052     right_vars = set([var for var in right_args if isinstance(var, int)])
00053     common_vars = left_vars & right_vars
00054     self.common_var_positions = [[args.index(var) for var in common_vars]
00055                                  for args in (list(left_args), list(right_args))]
00056     self.atoms_by_key = ({}, {})
00057   def validate(self):
00058     assert len(self.conditions) == 2, self
00059     left_args = self.conditions[0].args
00060     right_args = self.conditions[1].args
00061     eff_args = self.effect.args
00062     left_vars = set([v for v in left_args if isinstance(v, int) or isinstance(v,pddl.Variable)])
00063     right_vars = set([v for v in right_args if isinstance(v, int) or isinstance(v,pddl.Variable)])
00064     eff_vars = set([v for v in eff_args if isinstance(v, int) or isinstance(v,pddl.Variable)])
00065     assert left_vars & right_vars, self
00066     assert (left_vars | right_vars) == (left_vars & right_vars) | eff_vars
00067   def update_index(self, new_atom, cond_index):
00068     ordered_common_args = [new_atom.args[position]
00069                            for position in self.common_var_positions[cond_index]]
00070     key = tuple(ordered_common_args)
00071     self.atoms_by_key[cond_index].setdefault(key, []).append(new_atom)
00072   def fire(self, new_atom, cond_index, enqueue_func):
00073     effect_args = self.prepare_effect(new_atom, cond_index)
00074     ordered_common_args = [new_atom.args[position]
00075                            for position in self.common_var_positions[cond_index]]
00076     key = tuple(ordered_common_args)
00077     other_cond_index = 1 - cond_index
00078     other_cond = self.conditions[other_cond_index]
00079     for atom in self.atoms_by_key[other_cond_index].get(key, []):
00080       for var_no, obj in zip(other_cond.args, atom.args):
00081         if isinstance(var_no, int):
00082           effect_args[var_no] = obj
00083       enqueue_func(self.effect.predicate, effect_args)
00084 
00085 class ProductRule(BuildRule):
00086   def __init__(self, effect, conditions):
00087     self.effect = effect
00088     self.conditions = conditions
00089     self.atoms_by_index = [[] for c in self.conditions]
00090     self.empty_atom_list_no = len(self.conditions)
00091   def validate(self):
00092     assert len(self.conditions) >= 2, self
00093     cond_vars = [set([v for v in cond.args if isinstance(v, int) or isinstance(v,pddl.Variable)])
00094                  for cond in self.conditions]
00095     all_cond_vars = reduce(set.union, cond_vars)
00096     eff_vars = set([v for v in self.effect.args
00097                     if isinstance(v, int) or isinstance(v,pddl.Variable)])
00098     assert len(all_cond_vars) == len(eff_vars), self
00099     assert len(all_cond_vars) == sum([len(c) for c in cond_vars])
00100   def update_index(self, new_atom, cond_index):
00101     atom_list = self.atoms_by_index[cond_index]
00102     if not atom_list:
00103       self.empty_atom_list_no -= 1
00104     atom_list.append(new_atom)
00105   def fire(self, new_atom, cond_index, enqueue_func):
00106     if not self.empty_atom_list_no:
00107       effect_args = self.prepare_effect(new_atom, cond_index)
00108       self._fire(cond_index, 0, effect_args, enqueue_func)
00109   def _fire(self, ignore_pos, position, eff_args, enqueue_func):
00110     if position == len(self.conditions):
00111       enqueue_func(self.effect.predicate, eff_args)
00112     elif position == ignore_pos:
00113       self._fire(ignore_pos, position + 1, eff_args, enqueue_func)
00114     else:
00115       cond = self.conditions[position]
00116       for atom in self.atoms_by_index[position]:
00117         for var_no, obj in zip(cond.args, atom.args):
00118           if isinstance(var_no, int):
00119             eff_args[var_no] = obj
00120         self._fire(ignore_pos, position + 1, eff_args, enqueue_func)
00121 
00122 class ProjectRule(BuildRule):
00123   def __init__(self, effect, conditions):
00124     self.effect = effect
00125     self.conditions = conditions
00126   def validate(self):
00127     assert len(self.conditions) == 1
00128   def update_index(self, new_atom, cond_index):
00129     pass
00130   def fire(self, new_atom, cond_index, enqueue_func):
00131     effect_args = self.prepare_effect(new_atom, cond_index)
00132     enqueue_func(self.effect.predicate, effect_args)
00133 
00134 class Unifier:
00135   def __init__(self, rules):
00136     self.predicate_to_rule_generator = {}
00137     for rule in rules:
00138       for i, cond in enumerate(rule.conditions):
00139         self._insert_condition(rule, i)
00140   def unify(self, atom):
00141     result = []
00142     generator = self.predicate_to_rule_generator.get(atom.predicate)
00143     if generator:
00144       generator.generate(atom, result)
00145     return result
00146   def _insert_condition(self, rule, cond_index):
00147     condition = rule.conditions[cond_index]
00148     root = self.predicate_to_rule_generator.get(condition.predicate)
00149     if not root:
00150       root = LeafGenerator()
00151     constant_arguments = [(arg_index, arg)
00152                           for (arg_index, arg) in enumerate(condition.args)
00153                           if not isinstance(arg, int) and not isinstance(arg,pddl.Variable)]
00154     newroot = root._insert(constant_arguments, (rule, cond_index))
00155     self.predicate_to_rule_generator[condition.predicate] = newroot
00156   def dump(self): 
00157     predicates = self.predicate_to_rule_generator.keys()
00158     predicates.sort()
00159     print "Unifier:"
00160     for pred in predicates:
00161       print "  %s:" % pred
00162       rule_gen = self.predicate_to_rule_generator[pred]
00163       rule_gen.dump(())
00164     
00165 class LeafGenerator:
00166   index = sys.maxint
00167   def __init__(self):
00168     self.matches = []
00169   def generate(self, atom, result):
00170     result += self.matches
00171   def _insert(self, args, value):
00172     if not args:
00173       self.matches.append(value)
00174       return self
00175     else:
00176       root = LeafGenerator()
00177       root.matches.append(value)
00178       for arg_index, arg in args[::-1]:
00179         new_root = MatchGenerator(arg_index, LeafGenerator())
00180         new_root.match_generator[arg] = root
00181         root = new_root
00182       root.matches = self.matches # can be swapped in C++
00183       return root
00184   def dump(self, conditions):
00185     spaces = "  " + "  " * len(conditions)
00186     if conditions:
00187       print "%s%s" % (spaces, ", ".join(conditions))
00188     for match in self.matches:
00189       print "%s  %s" % (spaces, match)
00190 
00191 class MatchGenerator:
00192   def __init__(self, index, next):
00193     self.index = index
00194     self.matches = []
00195     self.match_generator = {}
00196     self.next = next
00197   def generate(self, atom, result):
00198     result += self.matches
00199     generator = self.match_generator.get(atom.args[self.index])
00200     if generator:
00201       generator.generate(atom, result)
00202     self.next.generate(atom, result)
00203   def _insert(self, args, value):
00204     if not args:
00205       self.matches.append(value)
00206       return self
00207     else:
00208       arg_index, arg = args[0]
00209       if self.index < arg_index:
00210         self.next = self.next._insert(args[1:], value)
00211       elif self.index > arg_index:
00212         new_parent = MatchGenerator(arg_index, self)
00213         new_branch = LeafGenerator()._insert(args[1:], value)
00214         new_parent.match_generator[arg] = new_branch
00215         return new_parent
00216       else:
00217         branch_generator = self.match_generator.get(arg)
00218         if not branch_generator:
00219           branch_generator = LeafGenerator()
00220         self.match_generator[arg] = branch_generator._insert(args[1:], value)
00221         return self
00222   def dump(self, conditions):
00223     spaces = "  " + "  " * len(conditions)
00224     if conditions:
00225       print "%s%s" % (spaces, ", ".join(conditions))
00226     for match in self.matches:
00227       print "%s  %s" % (spaces, match)
00228     self.next.dump(conditions)
00229     keys = self.match_generator.keys()
00230     keys.sort()
00231     for key in keys:
00232       condition = "%s: %s" % (self.index, key)
00233       self.match_generator[key].dump(conditions + (condition,))
00234 
00235 class Queue:
00236   def __init__(self, atoms):
00237     self.queue = atoms
00238     self.queue_pos = 0
00239     self.enqueued = set([(atom.predicate,) + tuple(atom.args)
00240                          for atom in self.queue])
00241   def __nonzero__(self):
00242     return self.queue_pos < len(self.queue)
00243   def push(self, predicate, args):
00244     eff_tuple = (predicate,) + tuple(args)
00245     if eff_tuple not in self.enqueued:
00246       self.enqueued.add(eff_tuple)
00247       self.queue.append(pddl.Atom(predicate, list(args)))
00248   def pop(self):
00249     result = self.queue[self.queue_pos]
00250     self.queue_pos += 1
00251     return result
00252   def popped_elements(self):
00253     return queue.queue[:self.queue_pos]
00254 
00255 def compute_model(prog):
00256   rules = convert_rules(prog)
00257   unifier = Unifier(rules)
00258   # unifier.dump()
00259   queue = Queue([fact.atom for fact in prog.facts])
00260   print "Starting instantiation [%d rules]..." % len(rules)
00261   while queue:
00262     next_atom = queue.pop()
00263     matches = unifier.unify(next_atom)
00264     for rule, cond_index in matches:
00265       rule.update_index(next_atom, cond_index)
00266       rule.fire(next_atom, cond_index, queue.push)
00267   return queue.queue
00268 
00269 if __name__ == "__main__":
00270   import pddl_to_prolog
00271   print "Parsing..."
00272   task = pddl.open()
00273   print "Writing rules..."
00274   prog = pddl_to_prolog.translate(task)
00275   print "Computing model..."
00276   for atom in compute_model(prog):
00277     print atom


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