00001
00002
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
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
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