00001 #ifndef PARTIAL_ORDER_LIFTER_H 00002 #define PARTIAL_ORDER_LIFTER_H 00003 00004 #include "state.h" 00005 #include "operator.h" 00006 #include "scheduler.h" 00007 #include <list> 00008 00009 enum ActionType 00010 { 00011 start_action = 0, 00012 end_action = 1, 00013 dummy_start_action = 2, 00014 dummy_end_action = 3 00015 }; 00016 00017 struct InstantPlanStep 00018 { 00019 00020 ActionType type; 00021 int endAction; 00022 int actionFinishingImmeadatlyAfterThis; 00023 double timepoint; 00024 double duration; 00025 const Operator* op; 00026 string name; 00027 00028 int correspondingPlanStep; 00029 00030 std::set<int> precondition_vars; 00031 std::set<int> effect_vars; 00032 00033 std::vector<Prevail> preconditions; 00034 std::set<int> effect_cond_vars; 00035 std::vector<PrePost> effects; 00036 std::vector<Prevail> overall_conds; 00037 00038 // void addCondVars(std::set<int>& effect_cond_vars, 00039 // const std::vector<Prevail>& conds) { 00040 // for(int i = 0; i < conds.size(); ++i) { 00041 // effect_cond_vars.insert(conds[i].var); 00042 // } 00043 // } 00044 // 00045 // void initializePreconditionVars(const std::vector<Prevail> &prevails, 00046 // const std::vector<PrePost> &pre_posts) { 00047 // for(size_t i = 0; i < prevails.size(); i++) { 00048 // precondition_vars.insert(prevails[i].var); 00049 // preconditions.push_back(prevails[i]); 00050 // } 00051 // for(int i = 0; i < pre_posts.size(); ++i) { 00052 // if(g_variable_types[pre_posts[i].var] == logical && pre_posts[i].pre != -1) { 00053 // precondition_vars.insert(pre_posts[i].var); 00054 // preconditions.push_back(Prevail(pre_posts[i].var,pre_posts[i].post)); 00055 // } 00056 // } 00057 // for(size_t i = 0; i < pre_posts.size(); i++) { 00058 // effect_vars.insert(pre_posts[i].var); 00059 // addCondVars(effect_cond_vars,pre_posts[i].cond_start); 00060 // addCondVars(effect_cond_vars,pre_posts[i].cond_overall); 00061 // addCondVars(effect_cond_vars,pre_posts[i].cond_end); 00062 // } 00063 // 00064 // // todo(); 00065 // } 00066 00067 00068 // void initializePreconditionVars() { 00069 // if(type == start_action) { 00070 // initializePreconditionVars(op->get_prevail_start(), 00071 // op->get_pre_post_start()); 00072 // } else { 00073 // initializePreconditionVars(op->get_prevail_end(), 00074 // op->get_pre_post_end()); 00075 // } 00076 // } 00077 // 00078 // void initializeEffectVars(const std::vector<PrePost> &pre_posts) { 00079 // // todo(); 00080 // } 00081 // 00082 // void initializeEffectVars() { 00083 // if(type == start_action) { 00084 // initializeEffectVars(op->get_pre_post_start()); 00085 // } else { 00086 // initializeEffectVars(op->get_pre_post_end()); 00087 // } 00088 // } 00089 // 00090 // void initializeRelevantPreconditions(const PlanTrace &trace) { 00091 // // todo(); 00092 // } 00093 // 00094 // void initializeTriggeredEffects(const PlanTrace &trace) { 00095 // // todo(); 00096 // } 00097 // 00098 // void initialize(const PlanTrace &trace) { 00099 // initializePreconditionVars(); 00100 // initializeEffectVars(); 00101 // initializeRelevantPreconditions(trace); 00102 // initializeTriggeredEffects(trace); 00103 // } 00104 00105 InstantPlanStep(ActionType _type, double _timepoint, double _duration, 00106 const Operator* _op) : 00107 type(_type), timepoint(_timepoint), duration(_duration), op(_op) 00108 { 00109 endAction = -1; 00110 actionFinishingImmeadatlyAfterThis = -1; 00111 name = type + "." + op->get_name(); 00112 // cout << "NAME: " << name << endl; 00113 // initialize(trace); 00114 } 00115 00116 bool operator<(const InstantPlanStep &other) const 00117 { 00118 return timepoint < other.timepoint; 00119 } 00120 00121 void dump(); 00122 void print_name(); 00123 00124 }; 00125 00126 typedef std::vector<InstantPlanStep> InstantPlan; 00127 00128 /* 00129 vector<Prevail> prevail_start; // var, val 00130 vector<Prevail> prevail_overall; // var, val 00131 vector<Prevail> prevail_end; // var, val 00132 vector<PrePost> pre_post_start; // var, old-val, new-val 00133 vector<PrePost> pre_post_end; // var, old-val, new-val 00134 */ 00135 00136 typedef std::pair<int, int> Ordering; 00137 00138 class PartialOrderLifter 00139 { 00140 struct doubleEquComp 00141 { 00142 bool operator()(const double& lhs, const double& rhs) const 00143 { 00144 return lhs + EPSILON < rhs; 00145 } 00146 }; 00147 private: 00148 Plan plan; 00149 const PlanTrace trace; 00150 00151 InstantPlan instant_plan; 00152 std::set<Ordering> partial_order; 00153 00154 void findTriggeringEffects( 00155 const TimeStampedState* stateBeforeHappening, 00156 const TimeStampedState* stateAfterHappening, 00157 vector<PrePost>& las); 00158 void findTriggeringEffectsForInitialState( 00159 const TimeStampedState* tsstate, vector<PrePost>& effects); 00160 void findAllEffectCondVars(const ScheduledOperator& new_op, 00161 set<int>& effect_cond_vars, ActionType type); 00162 void findPreconditions(const ScheduledOperator& new_op, 00163 vector<Prevail>& preconditions, ActionType type); 00164 // todo(); 00165 00166 int getIndexOfPlanStep(const ScheduledOperator& op, double timestamp); 00167 void buildInstantPlan(); 00168 void dumpInstantPlan(); 00169 void dumpOrdering(); 00170 void buildTrace(); 00171 void buildPartialOrder(); 00172 void sortPlan(Plan& plan); 00173 Plan createAndSolveSTN(); 00174 00175 public: 00176 PartialOrderLifter(const Plan &_plan, const PlanTrace &_trace) : 00177 plan(_plan), trace(_trace) 00178 { 00179 instant_plan.reserve(sizeof(InstantPlanStep) 00180 * (plan.size() * 2 + 2)); 00181 } 00182 00183 Plan lift(); 00184 }; 00185 00186 #endif 00187 00188 /* 00189 PSEUDOCODE: 00190 =========== 00191 00192 zusätzlich: 00193 constraints, die dafür sorgen, dass die duration variable passt + constraints 00194 die dafür sorgen, dass numerische effekte passen (aufeinander aufbauen). 00195 00196 Alle constraints, die es auch bei crikey gibt, plus constraints, die 00197 erzwingen, dass instant actions in derselben Reihenfolge bleiben, 00198 falls sie bzgl. bedingter effekte interferieren, d.h. wenn die eine 00199 aktion eine variable im effekt hat, die bei der anderen in einer 00200 effektvorbedingung oder der bedingung vorkommt. Wenn wir alle diese 00201 Constraints haben, dann ist garantiert, dass alle Aktionen genau die 00202 Effekte haben, die sie auch im urspruenglichen Plan besitzen. Dann 00203 dürfen wir aber die instant actions so zu unbedingten Aktionen 00204 umschreiben, dass sie (unbedingt) eben genau die effekte haben, die 00205 sie in dem gegebenen konkreten Plan haben. Auf diesen Aktionen kann 00206 man dann den Partial-Order-Lifting-Algorithmus von Crikey anwenden. 00207 00208 00209 Schritt 1) Instant-Actions erstellen, die Start- und End-Aktionen 00210 entsprechen, noch mit bedingten Effekten. Dummy-Aktionen 00211 für Init und Goal hinzufuegen. 00212 00213 Schritt 2) Fuer jede Aktion a sei pre_var(a) die Menge aller 00214 Variablen, die in der Vorbedingung von a oder der Bedingung 00215 eines bedingten Effekts von a erwähnt werden. Ferner sei 00216 eff_var(a) die Menge aller Variablen, die in irgendeinem 00217 (bedingten oder unbedingten) Effekt von a manipuliert 00218 werden können. Füge nun ein ordering a_i < a_j hinzu für 00219 alle i < j so dass (pre_var(a_j) \intersect eff_var(a_i)) 00220 \union (pre_var(a_i) \intersect eff_var(a_j)) != empty 00221 (d.h. ordering bleibt erhalten, wenn die Aktionen 00222 *irgendwie* interferieren könnten). 00223 00224 Schritt 3) Für jede Nicht-Instant-Aktion a sei overall_cond_var(a) die 00225 Menge aller Variablen, die in der Overall-Bedingung von a 00226 erwähnt werden. Für jede solche Aktion a und alle 00227 Instant-Aktionen a', die im Originalplan NICHT zwischen den 00228 Anfangs- und End-Instant-Aktionen von a auftreten, füge den 00229 Constraint a' < start_instant_action(a) 00230 bzw. end_instant_action(a) < a' zu den gesammelten 00231 Constraints hinzu, je nachdem, wie die Reihenfolge in dem 00232 Orignalplan ist. 00233 00234 Schritt 4) Schreibe alle Aktionen so um, dass sie nur noch bedingte 00235 Effekte haben, und zwar genau die, die sie in der 00236 Planausführung tatsächlich haben. Die Vorbedingungen seien 00237 genau die ursprünglichen Aktionsvorbedingungen plus die 00238 effektvorbedingungen der Effekte, die tatsächlich 00239 triggern. Ab jetzt sei (abuse of notation) a immer eine so 00240 umgeschriebene Aktion a. 00241 00242 Schritt 5) Führe auf dieser Aktionsmenge den 00243 Partial-Order-Lifting-Algorithmus von Crikey durch und wirf 00244 die dabei ermittelten orederings mit denen von oben 00245 (Schritt 1) zusammen. 00246 00247 Schritt 6) Erzeuge entsprechendes STN (am besten gleich mit 00248 epsilon-Abständen drin) und löse das STN mit entsprechendem 00249 Scheduler. 00250 00251 Schritt 7) Übersetzte Scheduling-Ergebnis in Plan zurück. 00252 00253 00254 + ABGELEITETE PRAEDIKATE!!! 00255 */