best_first_search.h
Go to the documentation of this file.
00001 #ifndef BEST_FIRST_SEARCH_H
00002 #define BEST_FIRST_SEARCH_H
00003 
00004 #include <vector>
00005 #include <queue>
00006 #include "closed_list.h"
00007 #include "search_engine.h"
00008 #include "state.h"
00009 #include "operator.h"
00010 #include <tr1/tuple>
00011 #include "search_statistics.h"
00012 
00013 class Heuristic;
00014 
00015 typedef std::tr1::tuple<const TimeStampedState *, const Operator *, double> OpenListEntry;
00016 
00017 class OpenListEntryCompare
00018 {
00019     public:
00020         bool operator()(const OpenListEntry left_entry, const OpenListEntry right_entry) const
00021         {
00022             return std::tr1::get<2>(right_entry) < std::tr1::get<2>(left_entry);
00023         }
00024 };
00025 
00026 typedef priority_queue<OpenListEntry, std::vector<OpenListEntry>,OpenListEntryCompare> OpenList;
00027 
00028 struct OpenListInfo
00029 {
00030     OpenListInfo(Heuristic *heur, bool only_pref);
00031     Heuristic *heuristic;
00032     bool only_preferred_operators;
00033     //    OpenList<OpenListEntry> open;
00034     OpenList open;
00035     int priority; // low value indicates high priority
00036 };
00037 
00039 typedef std::map<std::vector<double>, double> LogicalStateClosedList;
00040 bool knownByLogicalStateOnly(LogicalStateClosedList& scl,
00041         const TimedSymbolicStates& timedSymbolicStates);
00042 
00043 class BestFirstSearchEngine : public SearchEngine
00044 {
00045     private:
00046         std::vector<Heuristic *> heuristics;
00047         std::vector<Heuristic *> preferred_operator_heuristics;
00048         std::vector<OpenListInfo> open_lists;
00049         ClosedList closed_list;
00050 
00051         LogicalStateClosedList logical_state_closed_list;
00052 
00053         std::vector<double> best_heuristic_values;
00054         std::vector<const TimeStampedState*> best_states;
00055 
00056         TimeStampedState current_state;
00057         const TimeStampedState *current_predecessor;
00058         const Operator *current_operator;
00059 
00060         time_t start_time;
00061         int currentQueueIndex;
00062 
00063         SearchStatistics search_statistics;
00064 
00065     private:
00066         bool is_dead_end();
00067         bool check_goal();
00068         bool check_progress(const TimeStampedState* state);
00069         void report_progress();
00070         void reward_progress();
00071         void generate_successors(const TimeStampedState *parent_ptr);
00072         void dump_transition() const;
00074         void dump_everything() const;
00075         OpenListInfo *select_open_queue();
00076 
00077         void dump_plan_prefix_for_current_state() const;
00078         void dump_plan_prefix_for__state(const TimeStampedState &state) const;
00079 
00081         double getG(const TimeStampedState* state_ptr, const TimeStampedState* closed_ptr, const Operator* op) const;
00082         double getGc(const TimeStampedState *parent_ptr) const;
00083         double getGc(const TimeStampedState *parent_ptr, const Operator *op) const;
00084         double getGm(const TimeStampedState *parent_ptr) const;
00085         double getGt(const TimeStampedState *parent_ptr) const;
00086 
00087     protected:
00088         virtual SearchEngine::status step();
00089 
00090     public:
00091         enum QueueManagementMode
00092         {
00093             ROUND_ROBIN, PRIORITY_BASED
00094         } mode;
00095 
00096         BestFirstSearchEngine(QueueManagementMode _mode);
00097         ~BestFirstSearchEngine();
00098         void add_heuristic(Heuristic *heuristic, bool use_estimates,
00099                 bool use_preferred_operators);
00100         virtual void statistics(time_t & current_time);
00101         virtual void initialize();
00102         SearchEngine::status fetch_next_state();
00103 
00104     public:
00105         double bestMakespan;
00106         double bestSumOfGoals;
00107 };
00108 
00109 #endif


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