00001 #ifndef CYCLIC_CG_HEURISTIC_H
00002 #define CYCLIC_CG_HEURISTIC_H
00003
00004 #include <vector>
00005 #include <queue>
00006 #include <tr1/unordered_map>
00007 #include "heuristic.h"
00008 #include "state.h"
00009 #include "domain_transition_graph.h"
00010 #include <ext/slist>
00011 #include <cmath>
00012 #include <stdlib.h>
00013 #include <sstream>
00014 #include <string>
00015
00016 #include <tr1/tuple>
00017 #include "operator.h"
00018
00019 class FuncTransitionLabel;
00020 class TimeStampedState;
00021
00022 class LocalProblemDiscrete;
00023 class LocalProblemComp;
00024 class LocalProblemNodeDiscrete;
00025 class LocalProblemNodeComp;
00026 class LocalProblemNode;
00027 class CyclicCGHeuristic;
00028 class LocalProblem;
00029 class LocalTransitionComp;
00030 class LocalTransitionDiscrete;
00031 class LocalTransition;
00032 class Node_compare;
00033
00034 typedef priority_queue<LocalProblemNode*, std::vector<LocalProblemNode*>,
00035 Node_compare> node_queue;
00036
00037 typedef __gnu_cxx ::slist<std::pair<LocalTransition*, int> > waiting_list_t;
00038 typedef waiting_list_t::const_iterator const_it_waiting_list;
00039 typedef waiting_list_t::iterator it_waiting_list;
00040
00041 typedef std::tr1::unordered_map<int, int> hashmap;
00042 typedef hashmap::value_type ValuePair;
00043
00044
00045
00046
00047 class LocalTransition
00048 {
00049 public:
00050 double target_cost;
00051 int duration_var_local;
00052 const ValueTransitionLabel *label;
00053 virtual LocalProblemNode* get_source() = 0;
00054 virtual void on_condition_reached(int, double) = 0;
00055 virtual void print_description() = 0;
00056 LocalTransition(ValueTransitionLabel *the_label) :
00057 label(the_label)
00058 {
00059 }
00060 virtual ~LocalTransition()
00061 {
00062 }
00063 double get_direct_cost();
00064
00065 inline CyclicCGHeuristic* g_HACK();
00066 };
00067
00068 class LocalProblemNode
00069 {
00070 public:
00071
00072 LocalProblem *owner;
00073
00074 std::vector<double> children_state;
00075
00076 LocalTransition *reached_by;
00077
00078 LocalTransition *pred;
00079
00080 int value;
00081
00082
00083 double cost;
00084 inline double priority() const;
00085 bool expanded;
00086 double reached_by_wait_for;
00087 virtual void dump()
00088 {
00089 }
00090
00091 virtual void on_expand(const TimeStampedState &state) = 0;
00092
00093 waiting_list_t waiting_list;
00094
00095 void updatePrimitiveNumericVariable(assignment_op a_op,
00096 int primitive_var_local, int influencing_var_local,
00097 vector<double> &temp_children_state);
00098 void updateNumericVariablesRec(int var, vector<double> &temp_children_state);
00099 void updateSubtermNumericVariables(int var, binary_op op, int left_var,
00100 int right_var, vector<double> &temp_children_state);
00101 void updateComparisonVariables(int var, binary_op op, int left_var,
00102 int right_var, vector<double> &temp_children_state);
00103
00104 bool all_conds_satiesfied(const ValueTransitionLabel *label, const TimeStampedState &state);
00105 void mark_helpful_transitions(const TimeStampedState &state);
00106 virtual ~LocalProblemNode()
00107 {
00108 }
00109 LocalProblemNode(LocalProblem* owner, int children_state_size, int _value) :
00110 owner(owner), value(_value)
00111 {
00112 children_state.resize(children_state_size, 0.0);
00113 cost = -1.0;
00114 }
00115 void add_to_waiting_list(LocalTransition *transition, int start_val);
00116 virtual void print_name() = 0;
00117 inline CyclicCGHeuristic* g_HACK();
00118 };
00119
00120 typedef pair<int, int> CausalConstraint;
00121 typedef tr1::tuple<const Operator*, double, int> TimedOp;
00122
00123 class LocalProblem
00124 {
00125 public:
00126 CyclicCGHeuristic* owner;
00127 enum
00128 {
00129 QUITE_A_LOT = 10000000
00130 };
00131 double base_priority;
00132 const int var_no;
00133 std::vector<int> *causal_graph_parents;
00134 const int start_value;
00135 virtual LocalProblemNode* get_node(int var_no) = 0;
00136 hashmap *global_to_local_parents;
00137 vector<vector<int> > depending_vars;
00138 vector<vector<int> > children_in_cg;
00139 int getLocalIndexOfGlobalVariable(int global_var);
00140 void buildDependingVars(int parents_num);
00141 vector<TimedOp> generate_causal_constraints(LocalProblemNode* goalNode, set<
00142 CausalConstraint>& constraints, vector<TimedOp>& neededOps,
00143 const TimeStampedState& state, set<const Operator*>& labels);
00144 virtual ~LocalProblem() {
00145 }
00146 virtual void initialize(double base_priority, int start_value,
00147 const TimeStampedState &state) = 0;
00148 inline bool is_initialized() const;
00149 LocalProblem(CyclicCGHeuristic* _owner, int the_var_no,
00150 int the_start_value);
00151 };
00152
00153
00154
00155
00156 class LocalProblemNodeDiscrete: public LocalProblemNode
00157 {
00158 public:
00159
00160
00161 std::vector<LocalTransitionDiscrete> outgoing_transitions;
00162 std::vector<LocalTransitionDiscrete> additional_outgoing_transitions;
00163
00164 LocalProblemNodeDiscrete(LocalProblemDiscrete *owner,
00165 int children_state_size, int value);
00166 virtual void on_expand(const TimeStampedState &state);
00167 void dump();
00168 void print_name();
00169 };
00170
00171 class LocalTransitionDiscrete: public LocalTransition
00172 {
00173 public:
00174
00175 LocalProblemNodeDiscrete *source;
00176 LocalProblemNodeDiscrete *target;
00177
00178 LocalProblemNodeDiscrete* get_source()
00179 {
00180 return source;
00181 }
00182
00183 int unreached_conditions;
00184
00185 LocalTransitionDiscrete(ValueTransitionLabel *the_label,
00186 LocalProblemNodeDiscrete *the_source,
00187 LocalProblemNodeDiscrete *the_target) :
00188 LocalTransition(the_label), source(the_source), target(the_target)
00189 {
00190 }
00191
00192 void on_source_expanded(const TimeStampedState &state);
00193 virtual void on_condition_reached(int cond_no, double cost);
00194 void try_to_fire();
00195 virtual void print_description();
00196 };
00197
00198 class LocalProblemDiscrete: public LocalProblem
00199 {
00200 public:
00201
00202 std::vector<LocalProblemNodeDiscrete> nodes;
00203 virtual LocalProblemNodeDiscrete* get_node(int var_no) {
00204 return &(nodes[var_no]);
00205 }
00206
00207 void build_nodes_for_variable(int var_no);
00208 void build_nodes_for_goal();
00209 void compile_DTG_arcs_to_LTD_objects(DomainTransitionGraphSymb *dtgs);
00210 LocalProblemDiscrete(CyclicCGHeuristic* _owner, int var_no, int start_val);
00211 virtual void initialize(double base_priority, int start_value,
00212 const TimeStampedState &state);
00213 };
00214
00215
00216
00217
00218 class LocalProblemNodeComp: public LocalProblemNode
00219 {
00220 public:
00221
00222 std::vector<LocalTransitionComp> outgoing_transitions;
00223
00224 vector<vector<pair<LocalProblemNode*, int> > >
00225 nodes_where_this_subscribe;
00226
00227 binary_op op;
00228
00229 bool opened;
00230 LocalTransitionComp* bestTransition;
00231
00232 LocalProblemNodeComp(LocalProblemComp *owner_, int children_state_size,
00233 int the_value, binary_op the_binary_op);
00234 void fire(LocalTransitionComp* trans);
00235 virtual void on_expand(const TimeStampedState &state);
00236 void expand(LocalTransitionComp* trans);
00237 bool is_satiesfied(int trans_index, LocalTransitionComp* trans,
00238 const TimeStampedState &state);
00239 bool is_directly_satiesfied(const LocalAssignment &pre_cond);
00240 void subscribe_to_waiting_lists();
00241 void updateNumericVariables(LocalTransitionComp &trans,
00242 vector<double> &temp_children_state);
00243 bool check_progress_of_transition(vector<double> &temp_children_state, LocalTransitionComp *trans);
00244 void dump();
00245 void print_name();
00246 };
00247
00248 class LocalTransitionComp: public LocalTransition
00249 {
00250 public:
00251
00252 LocalProblemNodeComp* source;
00253
00254 LocalProblemNodeComp* target;
00255
00256 LocalProblemNodeComp* get_source() {
00257 return source;
00258 }
00259
00260 vector<bool> conds_satiesfied;
00261
00262 LocalTransitionComp(FuncTransitionLabel *the_label,
00263 LocalProblemNodeComp *the_source, LocalProblemNodeComp *the_target) :
00264 LocalTransition(the_label), source(the_source), target(the_target)
00265 {
00266 target_cost = 0.0;
00267
00268 conds_satiesfied.resize(label->precond.size());
00269 }
00270
00271 virtual void on_condition_reached(int cond_no, double cost);
00272 virtual void print_description();
00273 };
00274
00275 class LocalProblemComp: public LocalProblem
00276 {
00277 public:
00278
00279
00280 std::vector<LocalProblemNodeComp> nodes;
00281 LocalProblemNodeComp* get_node(int var_no) {
00282 return &(nodes[var_no]);
00283 }
00284
00285
00286
00287
00288
00289 void build_nodes_for_variable(int var_no, int the_start_value);
00290
00291 LocalProblemComp(CyclicCGHeuristic* _owner, int var_no, int start_val);
00292 virtual void initialize(double base_priority, int start_value,
00293 const TimeStampedState &state);
00294 };
00295
00296
00297
00298
00299
00300 class Node_compare
00301 {
00302 public:
00303 bool operator()(const LocalProblemNode* ln, const LocalProblemNode* rn) const
00304 {
00305 return (rn->priority() < ln->priority());
00306 }
00307 };
00308
00309 class CyclicCGHeuristic: public Heuristic
00310 {
00311 public:
00312 enum Mode
00313 {
00314 SUFFIX_MAKESPAN, REMAINING_MAKESPAN, COST, WEIGHTED, CEA
00315 } mode;
00316
00317 std::vector<LocalProblem *> local_problems;
00318 std::vector<std::vector<LocalProblem *> > local_problem_index;
00319 LocalProblemDiscrete *goal_problem;
00320 LocalProblemNodeDiscrete *goal_node;
00321
00322 node_queue open_nodes;
00323
00324 int number_of_nodes_in_queue;
00325
00326 vector<LocalProblemNodeDiscrete*> nodes_with_an_additional_transition;
00327 vector<ValueNode*> dtg_nodes_with_an_additional_transition;
00328 vector<Operator*> generated_waiting_ops;
00329 vector<ValueTransitionLabel*> generated_labels;
00330
00331 bool is_running(LocalTransition* trans, const TimeStampedState& state);
00332 double compute_costs(const TimeStampedState &state);
00333 void initialize_queue();
00334 void add_to_queue(LocalProblemNode *node);
00335 LocalProblemNode* remove_from_queue();
00336
00337 inline LocalProblem *get_local_problem(int var_no, int value);
00338
00339 virtual void initialize();
00340 virtual double compute_heuristic(const TimeStampedState &state);
00341
00342 CyclicCGHeuristic(Mode mode);
00343 ~CyclicCGHeuristic();
00344 virtual bool dead_ends_are_reliable() {
00345 return false;
00346 }
00347
00348 protected:
00349 double computeScheduledPlanMakespan(const TimeStampedState & state) const;
00350 };
00351
00352
00353
00354
00355 inline double LocalProblemNode::priority() const
00356 {
00357 return cost + owner->base_priority;
00358 }
00359
00360 inline bool LocalProblem::is_initialized() const
00361 {
00362 return base_priority != -1;
00363 }
00364
00365 inline LocalProblem *CyclicCGHeuristic::get_local_problem(int var_no, int value)
00366 {
00367 LocalProblem *result = local_problem_index[var_no][value];
00368 if(!result) {
00369 if(g_variable_types[var_no] == comparison) {
00370 result = new LocalProblemComp(this, var_no, value);
00371 } else {
00372 assert(g_variable_types[var_no] == logical);
00373 result = new LocalProblemDiscrete(this, var_no, value);
00374 }
00375 local_problem_index[var_no][value] = result;
00376 local_problems.push_back(result);
00377 }
00378 return result;
00379 }
00380
00381 #endif