00001 #ifndef NDEBUG
00002 #include <ext/algorithm>
00003 #endif
00004 #include <iostream>
00005 #include <map>
00006 #include <cassert>
00007 using namespace std;
00008 using namespace __gnu_cxx;
00009
00010 #include "domain_transition_graph.h"
00011 #include "globals.h"
00012
00013 void DomainTransitionGraph::read_all(istream &in)
00014 {
00015 int var_count = g_variable_domain.size();
00016
00017
00018 g_transition_graphs.reserve(var_count);
00019 for(int var = 0; var < var_count; var++) {
00020 switch (g_variable_types[var]) {
00021 case module:
00022 case costmodule:
00023 {
00024 DomainTransitionGraphModule *dtg =
00025 new DomainTransitionGraphModule(var);
00026 g_transition_graphs.push_back(dtg);
00027 break;
00028 }
00029 case logical:
00030 {
00031 int range = g_variable_domain[var];
00032 assert(range> 0);
00033 DomainTransitionGraphSymb *dtg = new DomainTransitionGraphSymb(var, range);
00034 g_transition_graphs.push_back(dtg);
00035 break;
00036 }
00037 case primitive_functional:
00038 {
00039 DomainTransitionGraphFunc *dtg = new DomainTransitionGraphFunc(var);
00040 g_transition_graphs.push_back(dtg);
00041 break;
00042 }
00043 case subterm_functional:
00044 {
00045 DomainTransitionGraphSubterm *dtg =
00046 new DomainTransitionGraphSubterm(var);
00047 g_transition_graphs.push_back(dtg);
00048 break;
00049 }
00050 case comparison:
00051 {
00052 DomainTransitionGraphComp *dtg = new DomainTransitionGraphComp(var);
00053 g_transition_graphs.push_back(dtg);
00054 break;
00055 }
00056 default:
00057 assert(false);
00058 break;
00059 }
00060 }
00061
00062
00063 for(int var = 0; var < var_count; var++) {
00064 g_transition_graphs[var]->read_data(in);
00065 }
00066
00067
00068
00069
00070
00071 for(int var = 0; var < var_count; var++) {
00072 if(g_variable_types[var] == comparison) {
00073 map<int, int> global_to_ccg_parent;
00074 DomainTransitionGraph::compute_causal_graph_parents_comp(var,
00075 global_to_ccg_parent);
00076 DomainTransitionGraph::collect_func_transitions(var,
00077 global_to_ccg_parent);
00078 }
00079 }
00080 }
00081
00082 void DomainTransitionGraph::compute_causal_graph_parents_comp(int var, map<int, int> &global_to_ccg_parent)
00083 {
00084 DomainTransitionGraph *dtg = g_transition_graphs[var];
00085 DomainTransitionGraphComp *cdtg =
00086 dynamic_cast<DomainTransitionGraphComp*>(dtg);
00087 assert(cdtg);
00088 cdtg->compute_recursively_parents(cdtg->nodes.first.left_var,
00089 global_to_ccg_parent);
00090 cdtg->compute_recursively_parents(cdtg->nodes.first.right_var,
00091 global_to_ccg_parent);
00092 }
00093
00094 void DomainTransitionGraph::collect_func_transitions(int var, map<int, int> &global_to_ccg_parent)
00095 {
00096 DomainTransitionGraph *dtg = g_transition_graphs[var];
00097 DomainTransitionGraphComp *cdtg =
00098 dynamic_cast<DomainTransitionGraphComp*>(dtg);
00099 assert(cdtg);
00100 cdtg->collect_recursively_func_transitions(cdtg->nodes.first.left_var,
00101 global_to_ccg_parent);
00102 cdtg->collect_recursively_func_transitions(cdtg->nodes.first.right_var,
00103 global_to_ccg_parent);
00104 }
00105
00106 DomainTransitionGraphSymb::DomainTransitionGraphSymb(int var_index, int node_count)
00107 {
00108 is_axiom = g_axiom_layers[var_index] != -1;
00109 var = var_index;
00110 nodes.reserve(node_count);
00111 for(int value = 0; value < node_count; value++)
00112 nodes.push_back(ValueNode(this, value));
00113 }
00114
00115 void DomainTransitionGraphSymb::read_data(istream &in)
00116 {
00117 check_magic(in, "begin_DTG");
00118
00119 map<int, int> global_to_ccg_parent;
00120 map<pair<int, int>, int> transition_index;
00121
00122
00123
00124
00125 for(int origin = 0; origin < nodes.size(); origin++) {
00126 int trans_count;
00127 in >> trans_count;
00128 for(int i = 0; i < trans_count; i++) {
00129 trans_type tt;
00130 int target, operator_index;
00131 in >> target;
00132 in >> operator_index;
00133 in >> tt;
00134
00135 pair<int, int> arc = make_pair(origin, target);
00136 if(!transition_index.count(arc)) {
00137 transition_index[arc] = nodes[origin].transitions.size();
00138 nodes[origin].transitions.push_back(ValueTransition(&nodes[target]));
00139
00140 assert(double_equals(
00141 target,
00142 nodes[origin].transitions[transition_index[arc]].target->value));
00143 }
00144
00145 assert(transition_index.count(arc));
00146 ValueTransition *transition =
00147 &nodes[origin].transitions[transition_index[arc]];
00148
00149 binary_op op;
00150 int duration_variable;
00151
00152 if(tt == start || tt == end || tt == compressed)
00153 in >> op >> duration_variable;
00154 else {
00155
00156 op = eq;
00157 duration_variable = -1;
00158 }
00159
00160 if(duration_variable != -1) {
00161 if(!global_to_ccg_parent.count(duration_variable)) {
00162 int duration_variable_local = ccg_parents.size();
00163 global_to_ccg_parent[duration_variable] = ccg_parents.size();
00164 ccg_parents.push_back(duration_variable);
00165 global_to_local_ccg_parents.insert(ValuePair(duration_variable,
00166 duration_variable_local));
00167 }
00168 }
00169
00170 if(op != eq) {
00171 cout << "Error: The duration constraint must be of the form\n";
00172 cout << " (= ?duration (arithmetic_term))" << endl;
00173 exit(1);
00174 }
00175
00176 vector<LocalAssignment> all_prevails;
00177 vector<LocalAssignment> cyclic_effect;
00178 int prevail_count;
00179 in >> prevail_count;
00180
00181 vector<pair<int, int> > precond_pairs;
00182 for(int j = 0; j < prevail_count; j++) {
00183 int global_var, val;
00184 condition_type cond_type;
00185 in >> global_var >> val >> cond_type;
00186 precond_pairs.push_back(make_pair(global_var, val));
00187
00188
00189 translate_global_to_local(global_to_ccg_parent, global_var);
00190 int ccg_parent = global_to_ccg_parent[global_var];
00191 DomainTransitionGraph *prev_dtg =
00192 g_transition_graphs[global_var];
00193 all_prevails.push_back(LocalAssignment(prev_dtg, ccg_parent,
00194 val, cond_type));
00195 }
00196 Operator *the_operator = NULL;
00197
00198
00199
00200
00201 if(is_axiom) {
00202
00203
00204 } else {
00205 assert(operator_index >= 0 && operator_index
00206 < g_operators.size());
00207 the_operator = &g_operators[operator_index];
00208 }
00209
00210
00211
00212
00213 if(the_operator) {
00214
00215
00216 vector<PrePost> pre_post;
00217 compress_effects(the_operator, pre_post);
00218
00219 sort(precond_pairs.begin(), precond_pairs.end());
00220
00221 for(int j = 0; j < pre_post.size(); j++) {
00222 int var_no = pre_post[j].var;
00223 if(var_no != var) {
00224 bool already_contained_in_global = global_to_ccg_parent.count(var_no);
00225 bool var_influences_important_comp_var = false;
00226 if(!already_contained_in_global &&
00227 g_variable_types[var_no] == primitive_functional) {
00228 var_influences_important_comp_var =
00229 add_relevant_functional_vars_to_context(var_no, global_to_ccg_parent);
00230 }
00231 if(already_contained_in_global || var_influences_important_comp_var) {
00232 extend_cyclic_effect(pre_post[j], cyclic_effect, global_to_ccg_parent,
00233 precond_pairs);
00234 }
00235 }
00236 }
00237 }
00238
00239 transition->ccg_labels.push_back(new ValueTransitionLabel(
00240 duration_variable, all_prevails, tt, cyclic_effect,
00241 the_operator));
00242 }
00243 }
00244 check_magic(in, "end_DTG");
00245 }
00246
00247 void DomainTransitionGraphSymb::extend_cyclic_effect(const PrePost& pre_post, vector<LocalAssignment>& cyclic_effect,
00248 map<int, int> &global_to_ccg_parent, const vector<pair<int, int> >& precond_pairs)
00249 {
00250 int var_no = pre_post.var;
00251 double pre = pre_post.pre;
00252 double post = pre_post.post;
00253 int var_post = pre_post.var_post;
00254 assignment_op fop = pre_post.fop;
00255
00256 vector<pair<int, int> > triggercond_pairs;
00257 if(pre != -1)
00258 triggercond_pairs.push_back(make_pair(var_no, static_cast<int>(pre)));
00259
00260 vector<Prevail> cond;
00261 for(int f = 0; f < pre_post.cond_start.size(); ++f) {
00262 cond.push_back(pre_post.cond_start[f]);
00263 }
00264 for(int f = 0; f < pre_post.cond_end.size(); ++f) {
00265 cond.push_back(pre_post.cond_end[f]);
00266 }
00267 for(int k = 0; k < cond.size(); k++)
00268 triggercond_pairs.push_back(make_pair(cond[k].var,
00269 static_cast<int>(cond[k].prev)));
00270 sort(triggercond_pairs.begin(), triggercond_pairs.end());
00271
00272
00273 if(includes(precond_pairs.begin(), precond_pairs.end(),
00274 triggercond_pairs.begin(), triggercond_pairs.end())) {
00275
00276
00277
00278 assert(global_to_ccg_parent.count(var_no));
00279 int ccg_parent = global_to_ccg_parent[var_no];
00280 assert(g_variable_types[var_no] == primitive_functional || g_variable_types[var_no] == logical);
00281 if(g_variable_types[var_no] == logical) {
00282 if(!double_equals(pre, post)) {
00283
00284 cyclic_effect.push_back(LocalAssignment(
00285 g_transition_graphs[var_no], ccg_parent,
00286 post, end_cond));
00287 }
00288 } else {
00289 assert(g_variable_types[var_no] == primitive_functional);
00290 translate_global_to_local(global_to_ccg_parent, var_post);
00291
00292 cyclic_effect.push_back(LocalAssignment(
00293 g_transition_graphs[var_no], ccg_parent,
00294 global_to_ccg_parent[var_post], fop, end_cond));
00295 }
00296 }
00297 }
00298
00299 bool DomainTransitionGraphSymb::add_relevant_functional_vars_to_context(int var_no,
00300 map<int, int> &global_to_ccg_parent)
00301 {
00302
00303
00304 vector<int> comp_vars;
00305 g_causal_graph->get_comp_vars_for_func_var(var_no, comp_vars);
00306 bool var_influences_important_comp_var = false;
00307 for(int s = 0; s < comp_vars.size(); ++s) {
00308 if(global_to_ccg_parent.count(comp_vars[s])) {
00309 var_influences_important_comp_var = true;
00310 set<int> intermediate_vars;
00311 g_causal_graph->get_functional_vars_in_unrolled_term(comp_vars[s], intermediate_vars);
00312 set<int>::iterator it;
00313 for(it = intermediate_vars.begin(); it != intermediate_vars.end(); ++it) {
00314 translate_global_to_local(global_to_ccg_parent, *it);
00315 }
00316 }
00317 }
00318 return var_influences_important_comp_var;
00319 }
00320
00321 void DomainTransitionGraphSymb::compress_effects(const Operator* op, vector<PrePost>& pre_post)
00322 {
00323 const vector<PrePost> &pre_post_start = op->get_pre_post_start();
00324 const vector<PrePost> &pre_post_end = op->get_pre_post_end();
00325 for(int k = 0; k < pre_post_start.size(); ++k) {
00326 pre_post.push_back(pre_post_start[k]);
00327 }
00328 bool pre_post_overwritten = false;
00329 for(int k = 0; k < pre_post_end.size(); ++k) {
00330 for(int l = 0; l < pre_post.size(); l++) {
00331 if(pre_post_end[k].var == pre_post[l].var) {
00332 pre_post_overwritten = true;
00333 pre_post[l].post = pre_post_end[k].post;
00334 pre_post[l].var_post = pre_post_end[k].var_post;
00335 break;
00336 }
00337 }
00338 if(!pre_post_overwritten) {
00339 pre_post.push_back(pre_post_end[k]);
00340 }
00341 pre_post_overwritten = false;
00342 }
00343 }
00344
00345 void DomainTransitionGraphSymb::dump() const
00346 {
00347 cout << " (logical)" << endl;
00348 for(int i = 0; i < nodes.size(); i++) {
00349 cout << nodes[i].value << endl;
00350 vector<ValueTransition> transitions = nodes[i].transitions;
00351 for(int j = 0; j < transitions.size(); j++) {
00352 cout << " " << transitions[j].target->value << endl;
00353 vector<ValueTransitionLabel*> labels = transitions[j].ccg_labels;
00354 for(int k = 0; k < labels.size(); k++) {
00355 cout << " at-start-durations:" << endl;
00356 cout << " " << labels[k]->duration_variable << endl;
00357 cout << " prevails:" << endl;
00358 vector<LocalAssignment> prevail = labels[k]->precond;
00359 for(int l = 0; l < prevail.size(); l++) {
00360 cout << " " << prevail[l].local_var << ":"
00361 << prevail[l].value << endl;
00362 }
00363 }
00364 }
00365 cout << " global parents:" << endl;
00366 for(int i = 0; i < ccg_parents.size(); i++)
00367 cout << ccg_parents[i] << endl;
00368 }
00369 }
00370
00371 void DomainTransitionGraphSymb::get_successors(int value, vector<int> &result) const
00372 {
00373 assert(result.empty());
00374 assert(value >= 0 && value < nodes.size());
00375 const vector<ValueTransition> &transitions = nodes[value].transitions;
00376 result.reserve(transitions.size());
00377 for(int i = 0; i < transitions.size(); i++)
00378 result.push_back(transitions[i].target->value);
00379 }
00380
00381 DomainTransitionGraphSubterm::DomainTransitionGraphSubterm(int var_index)
00382 {
00383 is_axiom = g_axiom_layers[var_index] != -1;
00384 var = var_index;
00385 }
00386
00387 void DomainTransitionGraphSubterm::read_data(istream &in)
00388 {
00389 check_magic(in, "begin_DTG");
00390 in >> left_var >> op >> right_var;
00391 check_magic(in, "end_DTG");
00392 }
00393
00394 void DomainTransitionGraphSubterm::dump() const
00395 {
00396 cout << " (subterm)" << endl;
00397 cout << left_var << " " << op << " " << right_var << endl;
00398 }
00399
00400 DomainTransitionGraphFunc::DomainTransitionGraphFunc(int var_index)
00401 {
00402 is_axiom = g_axiom_layers[var_index] != -1;
00403 var = var_index;
00404 }
00405
00406 void DomainTransitionGraphFunc::read_data(istream &in)
00407 {
00408 check_magic(in, "begin_DTG");
00409 int number_of_transitions;
00410 in >> number_of_transitions;
00411 for(int i = 0; i < number_of_transitions; i++) {
00412 int op_index;
00413 in >> op_index;
00414 Operator *op = &g_operators[op_index];
00415
00416 trans_type tt;
00417 in >> tt;
00418
00419 assignment_op a_op;
00420 int influencing_variable;
00421 in >> a_op >> influencing_variable;
00422 int duration_variable;
00423 vector<LocalAssignment> prevails;
00424 vector<LocalAssignment> effects;
00425
00426 binary_op bop;
00427 in >> bop >> duration_variable;
00428
00429 if(bop != eq) {
00430 cout << "Error: The duration constraint must be of the form\n";
00431 cout << " (= ?duration (arithmetic_term))" << endl;
00432 exit(1);
00433 }
00434
00435 int count;
00436
00437 in >> count;
00438 for(int i = 0; i < count; i++) {
00439 LocalAssignment prev_cond = LocalAssignment(in);
00440 prev_cond.prev_dtg = g_transition_graphs[prev_cond.local_var];
00441 prevails.push_back(prev_cond);
00442 }
00443 transitions.push_back(FuncTransitionLabel(var, prevails, effects, a_op,
00444 influencing_variable, duration_variable, tt, op));
00445 }
00446
00447 check_magic(in, "end_DTG");
00448 }
00449
00450 LocalAssignment::LocalAssignment(istream &in)
00451 {
00452 in >> local_var >> value >> cond_type;
00453 }
00454
00455 void LocalAssignment::dump() const
00456 {
00457 cout << local_var << ": " << value;
00458 }
00459
00460 void DomainTransitionGraphFunc::dump() const
00461 {
00462 cout << " (functional)" << endl;
00463 for(int i = 0; i < transitions.size(); i++) {
00464 cout << " durations_at_start:" << endl;
00465 cout << " " << transitions[i].duration_variable << endl;
00466 cout << " conds:" << endl;
00467 for(int j = 0; j < transitions[i].precond.size(); j++) {
00468 cout << " ";
00469 transitions[i].precond[j].dump();
00470 }
00471 cout << endl;
00472 cout << " effect: ";
00473 cout << transitions[i].a_op << " "
00474 << transitions[i].influencing_variable << endl;
00475 }
00476 }
00477
00478 DomainTransitionGraphComp::DomainTransitionGraphComp(int var_index)
00479 {
00480 is_axiom = g_axiom_layers[var_index] != -1;
00481 var = var_index;
00482 }
00483
00484 void DomainTransitionGraphComp::read_data(istream &in)
00485 {
00486 check_magic(in, "begin_DTG");
00487 check_magic(in, "1");
00488 in >> nodes.second.left_var >> nodes.second.op >> nodes.second.right_var;
00489 check_magic(in, "0");
00490 in >> nodes.first.left_var >> nodes.first.op >> nodes.first.right_var;
00491 check_magic(in, "end_DTG");
00492 assert(nodes.first.op != nodes.second.op || nodes.first.op == eq);
00493 }
00494
00495 void DomainTransitionGraphComp::compute_recursively_parents(int var,
00496 map<int, int> &global_to_ccg_parent)
00497 {
00498 if(g_variable_types[var] == primitive_functional) {
00499
00500 translate_global_to_local(global_to_ccg_parent, var);
00501 return;
00502 }
00503 if(g_variable_types[var] == subterm_functional) {
00504 translate_global_to_local(global_to_ccg_parent, var);
00505 DomainTransitionGraph* dtg = g_transition_graphs[var];
00506 DomainTransitionGraphSubterm* sdtg =
00507 dynamic_cast<DomainTransitionGraphSubterm*>(dtg);
00508 assert(sdtg);
00509 compute_recursively_parents(sdtg->left_var, global_to_ccg_parent);
00510 compute_recursively_parents(sdtg->right_var, global_to_ccg_parent);
00511 return;
00512 }
00513 assert(false);
00514 }
00515
00516 int DomainTransitionGraph::translate_global_to_local(map<int, int> &global_to_ccg_parent, int global_var)
00517 {
00518 int local_var;
00519 if(!global_to_ccg_parent.count(global_var)) {
00520 local_var = ccg_parents.size();
00521 global_to_ccg_parent[global_var] = local_var;
00522 ccg_parents.push_back(global_var);
00523 global_to_local_ccg_parents.insert(ValuePair(global_var, local_var));
00524 } else {
00525 local_var = global_to_ccg_parent[global_var];
00526 }
00527 return local_var;
00528 }
00529
00530 void DomainTransitionGraphComp::collect_recursively_func_transitions(int var,
00531 map<int, int> &global_to_ccg_parent)
00532 {
00533 DomainTransitionGraph* dtg = g_transition_graphs[var];
00534 if(g_variable_types[var] == primitive_functional) {
00535 DomainTransitionGraphFunc* fdtg =
00536 dynamic_cast<DomainTransitionGraphFunc*>(dtg);
00537 assert(fdtg);
00538 for(int i = 0; i < fdtg->transitions.size(); i++) {
00539 transitions.push_back(fdtg->transitions[i]);
00540 FuncTransitionLabel &trans = transitions.back();
00541 int starting_variable_global =
00542 trans.starting_variable;
00543 int starting_variable_local =
00544 translate_global_to_local(global_to_ccg_parent, starting_variable_global);
00545 trans.starting_variable = starting_variable_local;
00546
00547 int influencing_variable_global =
00548 trans.influencing_variable;
00549 int influencing_variable_local =
00550 translate_global_to_local(global_to_ccg_parent, influencing_variable_global);
00551 trans.influencing_variable = influencing_variable_local;
00552
00553 if(trans.duration_variable != -1) {
00554 int duration_variable_global = trans.duration_variable;
00555 int duration_variable_local = translate_global_to_local(
00556 global_to_ccg_parent, duration_variable_global);
00557 trans.duration_variable = duration_variable_local;
00558 }
00559 vector<LocalAssignment> *prevails = &(trans.precond);
00560 for(int k = 0; k < prevails->size(); k++) {
00561 int global_var = (*prevails)[k].local_var;
00562 int local_var = translate_global_to_local(global_to_ccg_parent, global_var);
00563 (*prevails)[k].local_var = local_var;
00564 }
00565 }
00566 return;
00567 }
00568 if(g_variable_types[var] == subterm_functional) {
00569 DomainTransitionGraphSubterm* sdtg =
00570 dynamic_cast<DomainTransitionGraphSubterm*>(dtg);
00571 assert(sdtg);
00572 collect_recursively_func_transitions(sdtg->left_var,
00573 global_to_ccg_parent);
00574 collect_recursively_func_transitions(sdtg->right_var,
00575 global_to_ccg_parent);
00576 return;
00577 }
00578 }
00579
00580 void DomainTransitionGraphComp::dump() const
00581 {
00582 cout << " (comparison)" << endl;
00583 cout << "1: " << nodes.first.left_var << " " << nodes.first.op << " "
00584 << nodes.first.right_var << endl;
00585 cout << "0: " << nodes.second.left_var << " " << nodes.second.op << " "
00586 << nodes.second.right_var << endl;
00587 cout << "transitions: " << endl;
00588 for(int i = 0; i < transitions.size(); i++) {
00589 cout << " duration variable: ";
00590 cout << " " << transitions[i].duration_variable;
00591 cout << endl;
00592 cout << " conds:" << endl;
00593 for(int j = 0; j < transitions[i].precond.size(); j++) {
00594 cout << " ";
00595 transitions[i].precond[j].dump();
00596 }
00597 cout << endl;
00598 cout << " effect: ";
00599 cout << transitions[i].a_op << " "
00600 << transitions[i].influencing_variable << endl;
00601 }
00602 cout << "Context: ";
00603 for(int i = 0; i < ccg_parents.size(); i++) {
00604 cout << ccg_parents[i] << " ";
00605 }
00606 cout << endl;
00607 }
00608
00609 class hash_pair_vector
00610 {
00611 public:
00612 size_t operator()(const vector<pair<int, int> > &vec) const
00613 {
00614 unsigned long hash_value = 0;
00615 for(int i = 0; i < vec.size(); i++) {
00616 hash_value = 17 * hash_value + vec[i].first;
00617 hash_value = 17 * hash_value + vec[i].second;
00618 }
00619 return size_t(hash_value);
00620 }
00621 };
00622