partial_order_lifter.h
Go to the documentation of this file.
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  */


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