cyclic_cg_heuristic.h
Go to the documentation of this file.
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 //general classes
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         // Static attributes
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         // Dynamic attributes (modified during heuristic computation).
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 //discrete variables
00155 //*****************************************************
00156 class LocalProblemNodeDiscrete: public LocalProblemNode
00157 {
00158     public:
00159 
00160         // Static attributes (fixed upon initialization).
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 //comparison case
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             // is this necessary?
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         //nodes[0] = false, nodes[1] = true
00280         std::vector<LocalProblemNodeComp> nodes;
00281         LocalProblemNodeComp* get_node(int var_no) {
00282             return &(nodes[var_no]);
00283         }
00284 
00285         //inherited member variable start_value always has start_value 0 (true) or 1 (false)
00286 
00287         //    binary_op comp_op;
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 //CyclicCGHeuristic
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 //inline functions
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


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