best_first_search.cpp
Go to the documentation of this file.
00001 #include "best_first_search.h"
00002 
00003 #include "globals.h"
00004 #include "heuristic.h"
00005 #include "successor_generator.h"
00006 #include "plannerParameters.h"
00007 #include <time.h>
00008 #include <iomanip>
00009 #include "ros_printouts.h"
00010 
00011 #include <cassert>
00012 #include <cmath>
00013 
00014 using namespace std;
00015 
00016 OpenListInfo::OpenListInfo(Heuristic *heur, bool only_pref)
00017 {
00018     heuristic = heur;
00019     only_preferred_operators = only_pref;
00020     priority = 0;
00021 }
00022 
00023 BestFirstSearchEngine::BestFirstSearchEngine(QueueManagementMode _mode) :
00024     current_state(*g_initial_state), currentQueueIndex(-1), mode(_mode)
00025 {
00026     current_predecessor = 0;
00027     current_operator = 0;
00028     start_time = time(NULL);
00029     bestMakespan = HUGE_VAL;
00030     bestSumOfGoals = HUGE_VAL;
00031 }
00032 
00033 BestFirstSearchEngine::~BestFirstSearchEngine()
00034 {
00035 }
00036 
00037 void BestFirstSearchEngine::add_heuristic(Heuristic *heuristic,
00038         bool use_estimates, bool use_preferred_operators)
00039 {
00040     assert(use_estimates || use_preferred_operators);
00041     heuristics.push_back(heuristic);
00042     best_heuristic_values.push_back(-1);
00043     best_states.push_back(NULL);
00044     if(use_estimates) {
00045         open_lists.push_back(OpenListInfo(heuristic, false));
00046     }
00047     if(use_preferred_operators) {
00048         preferred_operator_heuristics.push_back(heuristic);
00049         open_lists.push_back(OpenListInfo(heuristic, true));
00050     }
00051 }
00052 
00053 void BestFirstSearchEngine::initialize()
00054 {
00055     assert(!open_lists.empty());
00056 }
00057 
00058 void BestFirstSearchEngine::statistics(time_t & current_time)
00059 {
00060     cout << endl;
00061     cout << "Search Time: " << (current_time - start_time) << " sec." << endl;
00062     search_statistics.dump(closed_list.size(), current_time);
00063     cout << "OpenList sizes:";
00064     for(unsigned int i = 0; i < open_lists.size(); ++i) {
00065         cout << " " << open_lists[i].open.size();
00066     }
00067     cout << endl;
00068     cout << "Heuristic Computations (per heuristic):";
00069     unsigned long totalHeuristicComputations = 0;
00070     for(unsigned int i = 0; i < heuristics.size(); ++i) {
00071         Heuristic *heur = heuristics[i];
00072         totalHeuristicComputations += heur->get_num_computations();
00073         cout << " " << heur->get_num_computations();
00074     }
00075     cout << " Total: " << totalHeuristicComputations << endl;
00076     cout << "Best heuristic value: " << best_heuristic_values[0] << endl << endl;
00077     //    cout << "Best state:" << endl;
00078     //    const TimeStampedState &state = *best_states[0];
00079     //    if(&state) {
00080     //        dump_plan_prefix_for__state(state);
00081     //        best_states[0]->dump();
00082     //    }
00083     //    cout << endl;
00084 }
00085 
00086 void BestFirstSearchEngine::dump_transition() const
00087 {
00088     cout << endl;
00089     if(current_predecessor != 0) {
00090         cout << "DEBUG: In step(), current predecessor is: " << endl;
00091         current_predecessor->dump(g_parameters.verbose);
00092     }
00093     cout << "DEBUG: In step(), current operator is: ";
00094     if(current_operator != 0) {
00095         current_operator->dump();
00096     } else {
00097         cout << "No operator before initial state." << endl;
00098     }
00099     cout << "DEBUG: In step(), current state is: " << endl;
00100     current_state.dump(g_parameters.verbose);
00101     cout << endl;
00102 }
00103 
00104 void BestFirstSearchEngine::dump_everything() const
00105 {
00106     dump_transition();
00107     cout << endl << endl;
00108     for (std::vector<OpenListInfo>::const_iterator it = open_lists.begin(); it
00109             != open_lists.end(); it++) {
00110         cout << "DEBUG: an open list is:" << endl;
00111         // huge dangerous hack...
00112         OpenListEntry const* begin = &(it->open.top());
00113         OpenListEntry const* end = &(it->open.top()) + it->open.size();
00114         for (const OpenListEntry* it2 = begin; it2 != end; it2++) {
00115             cout << "OpenListEntry" << endl;
00116             cout << "state" << endl;
00117             std::tr1::get<0>(*it2)->dump(true);
00118             cout << "op" << endl;
00119             std::tr1::get<1>(*it2)->dump();
00120             double h = std::tr1::get<2>(*it2);
00121             cout << "Value: " << h << endl;
00122             cout << "end OpenListEntry" << endl;
00123         }
00124     }
00125 }
00126 
00127 SearchEngine::status BestFirstSearchEngine::step()
00128 {
00129     // Invariants:
00130     // - current_state is the next state for which we want to compute the heuristic.
00131     // - current_predecessor is a permanent pointer to the predecessor of that state.
00132     // - current_operator is the operator which leads to current_state from predecessor.
00133 
00134     bool discard = true;
00135 
00136     double maxTimeIncrement = 0.0;
00137     for(int k = 0; k < current_state.operators.size(); ++k) {
00138         maxTimeIncrement = max(maxTimeIncrement, current_state.operators[k].time_increment);
00139     }
00140     double makeSpan = maxTimeIncrement + current_state.timestamp;
00141 
00142     // when using subgoals we want to keep states with the same makespan as they might have better subgoals
00143     if(g_parameters.use_subgoals_to_break_makespan_ties) {
00144         if (makeSpan <= bestMakespan && !closed_list.contains(current_state)) {
00145             discard = false;
00146         }
00147     } else {
00148         if (makeSpan < bestMakespan && !closed_list.contains(current_state)) {
00149             discard = false;
00150         }
00151     }
00152 
00153     // throw away any states resulting from zero cost actions (can't handle)
00154     if(current_predecessor && current_operator && current_operator != g_let_time_pass &&
00155             current_operator->get_duration(current_predecessor) <= 0.0) {
00156         discard = true;
00157     }
00158 
00159     if(!discard) {
00160         const TimeStampedState *parent_ptr = closed_list.insert(current_state,
00161                 current_predecessor, current_operator);
00162         assert(&current_state != current_predecessor);
00163 
00164         // evaluate the current/parent state
00165         // also do this for non/lazy-evaluation as the heuristics
00166         // provide preferred operators!
00167         for(int i = 0; i < heuristics.size(); i++) {
00168             heuristics[i]->evaluate(current_state);
00169         }
00170         if(!is_dead_end()) {
00171             if(check_progress(parent_ptr)) {
00172                 // current_state.dump();
00173                 report_progress();
00174                 reward_progress();
00175             }
00176             if(check_goal())
00177                 return SOLVED;
00178             generate_successors(parent_ptr);
00179         }
00180     } else if ((current_operator == g_let_time_pass) &&
00181             current_state.operators.empty() &&
00182             makeSpan < bestMakespan) {
00183         // arrived at same state by letting time pass
00184         // e.g. when having an action with duration and only start effect
00185         // the result would be discarded, check if we are at goal    
00186         for(int i = 0; i < heuristics.size(); i++) {
00187             heuristics[i]->evaluate(current_state);
00188         }
00189         if(!is_dead_end()) {
00190             if(check_goal())
00191                 return SOLVED;
00192         }
00193     }
00194 
00195     time_t current_time = time(NULL);
00196     static time_t last_stat_time = current_time;
00197     if(g_parameters.verbose && current_time - last_stat_time >= 10) {
00198         statistics(current_time);
00199         last_stat_time = current_time;
00200     }
00201 
00202     // use different timeouts depending if we found a plan or not.
00203     if(found_solution()) {
00204         static time_t first_solution_time = current_time;
00205         // first check: timeout if plan found
00206         if(g_parameters.timeout_if_plan_found > 0 
00207                 && current_time - start_time > g_parameters.timeout_if_plan_found) {
00208             // second check: timeout from first plan found to min_search_time_after_plan_found
00209             // only do this, if the extra time is request, otherwise we ran into the timeout
00210             if(g_parameters.min_search_time_after_plan_found <= 0
00211                     && g_parameters.min_search_time_factor_after_plan_found <= 0) {
00212                 ROS_INFO("Ran into timeout_if_plan_found");
00213                 if(g_parameters.verbose)
00214                     statistics(current_time);
00215                 return SOLVED_TIMEOUT;
00216             } else {
00217                 int extra_timeout = g_parameters.min_search_time_after_plan_found;
00218                 int proportion_extra =
00219                     int(g_parameters.min_search_time_factor_after_plan_found
00220                             * double(first_solution_time - start_time));
00221                 if(proportion_extra > extra_timeout)
00222                     extra_timeout = proportion_extra;
00223 
00224                 if(current_time - first_solution_time > extra_timeout) {
00225                     ROS_INFO("Ran into min_search_time_(factor_)after_plan_found");
00226                     if(g_parameters.verbose)
00227                         statistics(current_time);
00228                     return SOLVED_TIMEOUT;
00229                 }
00230             }
00231         }
00232     } else {
00233         if (g_parameters.timeout_while_no_plan_found > 0 
00234                 && current_time - start_time > g_parameters.timeout_while_no_plan_found) {
00235             if(g_parameters.verbose)
00236                 statistics(current_time);
00237             return FAILED_TIMEOUT;
00238         }
00239     }
00240 
00241     return fetch_next_state();
00242 }
00243 
00244 bool BestFirstSearchEngine::is_dead_end()
00245 {
00246     // If a reliable heuristic reports a dead end, we trust it.
00247     // Otherwise, all heuristics must agree on dead-end-ness.
00248     int dead_end_counter = 0;
00249     for(int i = 0; i < heuristics.size(); i++) {
00250         if(heuristics[i]->is_dead_end()) {
00251             if(heuristics[i]->dead_ends_are_reliable())
00252                 return true;
00253             else
00254                 dead_end_counter++;
00255         }
00256     }
00257     return dead_end_counter == heuristics.size();
00258 }
00259 
00260 bool BestFirstSearchEngine::check_goal()
00261 {
00262     // Any heuristic reports 0 iff this is a goal state, so we can
00263     // pick an arbitrary one. Heuristics are assumed to not miss a goal
00264     // state and especially not to report a goal as dead end.
00265     Heuristic *heur = open_lists[0].heuristic;
00266  
00267     // We actually need this silly !heur->is_dead_end() check because
00268     // this state *might* be considered a non-dead end by the
00269     // overall search even though heur considers it a dead end
00270     // (e.g. if heur is the CG heuristic, but the FF heuristic is
00271     // also computed and doesn't consider this state a dead end.
00272     // If heur considers the state a dead end, it cannot be a goal
00273     // state (heur will not be *that* stupid). We may not call
00274     // get_heuristic() in such cases because it will barf.
00275     if(!heur->is_dead_end() && heur->get_heuristic() == 0) {
00276         if(current_state.operators.size() > 0) {
00277             return false;
00278         }
00279         // found goal
00280 
00281         if(!current_state.satisfies(g_goal)) {  // will assert...
00282             dump_everything();
00283         }
00284         assert(current_state.operators.empty() && current_state.satisfies(g_goal));
00285 
00286         Plan plan;
00287         PlanTrace path;
00288         closed_list.trace_path(current_state, plan, path);
00289         set_plan(plan);
00290         set_path(path);
00291         return true;
00292     } else {
00293         return false;
00294     }
00295 }
00296 
00297 void BestFirstSearchEngine::dump_plan_prefix_for_current_state() const
00298 {
00299     dump_plan_prefix_for__state(current_state);
00300 }
00301 
00302 void BestFirstSearchEngine::dump_plan_prefix_for__state(const TimeStampedState &state) const
00303 {
00304     Plan plan;
00305     PlanTrace path;
00306     closed_list.trace_path(state, plan, path);
00307     for(int i = 0; i < plan.size(); i++) {
00308         const PlanStep& step = plan[i];
00309         cout << step.start_time << ": " << "(" << step.op->get_name() << ")"
00310             << " [" << step.duration << "]" << endl;
00311     }
00312 }
00313 
00314 bool BestFirstSearchEngine::check_progress(const TimeStampedState* state)
00315 {
00316     bool progress = false;
00317     for(int i = 0; i < heuristics.size(); i++) {
00318         if(heuristics[i]->is_dead_end())
00319             continue;
00320         double h = heuristics[i]->get_heuristic();
00321         double &best_h = best_heuristic_values[i];
00322         if(best_h == -1 || h < best_h) {
00323             best_h = h;
00324             best_states[i] = state;
00325             progress = true;
00326         }
00327     }
00328     return progress;
00329 }
00330 
00331 void BestFirstSearchEngine::report_progress()
00332 {
00333     cout << "Best heuristic value: ";
00334     for(int i = 0; i < heuristics.size(); i++) {
00335         cout << best_heuristic_values[i];
00336         if(i != heuristics.size() - 1)
00337             cout << "/";
00338     }
00339     cout << " [expanded " << closed_list.size() << " state(s)]" << endl;
00340 }
00341 
00342 void BestFirstSearchEngine::reward_progress()
00343 {
00344     // Boost the "preferred operator" open lists somewhat whenever
00345     // progress is made. This used to be used in multi-heuristic mode
00346     // only, but it is also useful in single-heuristic mode, at least
00347     // in Schedule.
00348     //
00349     // Future Work: Test the impact of this, and find a better way of rewarding
00350     // successful exploration. For example, reward only the open queue
00351     // from which the good state was extracted and/or the open queues
00352     // for the heuristic for which a new best value was found.
00353 
00354     for(int i = 0; i < open_lists.size(); i++)
00355         if(open_lists[i].only_preferred_operators)
00356             open_lists[i].priority -= 1000;
00357 }
00358 
00359 bool knownByLogicalStateOnly(LogicalStateClosedList& scl, const TimedSymbolicStates& timedSymbolicStates)
00360 {
00361     // feature disabled -> return false = state unkown -> insert
00362     if(!g_parameters.use_known_by_logical_state_only)
00363        return false;
00364     assert(timedSymbolicStates.size() > 0);
00365     bool ret = true;
00366     for (int i = 0; i < timedSymbolicStates.size(); ++i) {
00367         if (scl.count(timedSymbolicStates[i].first) > 0) {
00368             double currentBestMakespan = scl[timedSymbolicStates[i].first];
00369             if (timedSymbolicStates[i].second + EPSILON < currentBestMakespan) {
00370                 ret = false;
00371                 scl[timedSymbolicStates[i].first] = timedSymbolicStates[i].second;
00372             }
00373         } else {
00374             ret = false;
00375             scl[timedSymbolicStates[i].first] = timedSymbolicStates[i].second;
00376         }
00377     }
00378     return ret;
00379 }
00380 
00381 void BestFirstSearchEngine::generate_successors(const TimeStampedState *parent_ptr)
00382 {
00383     vector<const Operator *> all_operators;
00384     g_successor_generator->generate_applicable_ops(*parent_ptr, all_operators);
00385     // Filter ops that cannot be applicable just from the preprocess data (doesn't guarantee full applicability)
00386 
00387     vector<const Operator *> preferred_operators;
00388     for(int i = 0; i < preferred_operator_heuristics.size(); i++) {
00389         Heuristic *heur = preferred_operator_heuristics[i];
00390         if(!heur->is_dead_end()) {
00391             heur->get_preferred_operators(preferred_operators);
00392         }
00393     }
00394 
00395     vector<const Operator *> preferred_applicable_operators;
00396     // all_operators contains a superset of applicable operators based on preprocess data
00397     // this in not necessarily all operators in the task, but also doesn't guarantee applicablity, yet.
00398     // Here we split this superset of operators in two:
00399     // - preferred_applicable_operators will be those operators from all_operators that are preferred_operators
00400     // - all_operators will be the rest (i.e. the non-preferred operators)
00401     // preferred_applicable_operators thus contains all operators that are preferred and might be applicable,
00402     // i.e. a subset of preferred_operators
00403     // The preferred_operators to be used will thus be only the preferred_applicable_operators
00404     for(int k = 0; k < preferred_operators.size(); ++k) {
00405         for(int l = 0; l < all_operators.size(); ++l) {
00406             if(all_operators[l] == preferred_operators[k]) {
00407                 all_operators[l] = all_operators[all_operators.size() - 1];
00408                 all_operators.pop_back();
00409                 preferred_applicable_operators.push_back(preferred_operators[k]);
00410                 break;
00411             }
00412         }
00413     }
00414     preferred_operators = preferred_applicable_operators;
00415 
00416     for(int i = 0; i < open_lists.size(); i++) {
00417         Heuristic *heur = open_lists[i].heuristic;
00418 
00419         double priority = -1;   // invalid
00420         // lazy eval = compute priority by parent
00421         if(g_parameters.lazy_evaluation) {
00422             double parentG = getG(parent_ptr, parent_ptr, NULL);
00423             double parentH = heur->get_heuristic();
00424             assert(!heur->is_dead_end());
00425             double parentF = parentG + parentH;
00426             if(g_parameters.greedy)
00427                 priority = parentH;
00428             else
00429                 priority = parentF;
00430         }
00431 
00432         OpenList &open = open_lists[i].open;
00433         vector<const Operator *> & ops =
00434             open_lists[i].only_preferred_operators ? preferred_operators : all_operators;
00435 
00436         // push successors from applicable ops
00437         for(int j = 0; j < ops.size(); j++) {
00438             assert(ops[j]->get_name().compare("wait") != 0);
00439 
00440             bool lazy_state_module_eval = g_parameters.lazy_state_module_evaluation > 0;
00441 
00442             // compute expected min makespan of this op
00443             double maxTimeIncrement = 0.0;
00444             for(int k = 0; k < parent_ptr->operators.size(); ++k) {
00445                 maxTimeIncrement = max(maxTimeIncrement, parent_ptr->operators[k].time_increment);
00446             }
00447             double duration = ops[j]->get_duration(parent_ptr, lazy_state_module_eval);
00448             maxTimeIncrement = max(maxTimeIncrement, duration);
00449             double makespan = maxTimeIncrement + parent_ptr->timestamp;
00450             bool betterMakespan = makespan < bestMakespan;
00451             if(g_parameters.use_subgoals_to_break_makespan_ties && makespan == bestMakespan)
00452                 betterMakespan = true;
00453 
00454             // Generate a child/Use an operator if
00455             // - it is applicable
00456             // - its minimum makespan is better than the best we had so far
00457             // - if knownByLogicalStateOnly hasn't closed this state (when feature enabled)
00458 
00459             // only compute tss if needed
00460             TimedSymbolicStates timedSymbolicStates;
00461             TimedSymbolicStates* tssPtr = NULL;
00462             if(g_parameters.use_known_by_logical_state_only)
00463                 tssPtr = &timedSymbolicStates;
00464             if(betterMakespan && ops[j]->is_applicable(*parent_ptr, lazy_state_module_eval, tssPtr) &&
00465                     (!knownByLogicalStateOnly(logical_state_closed_list, timedSymbolicStates))) {
00466                 // non lazy eval = compute priority by child
00467                 if(!g_parameters.lazy_evaluation) {
00468                     // need to compute the child to evaluate it
00469                     TimeStampedState tss = TimeStampedState(*parent_ptr, *ops[j]);
00470                     double childG = getG(&tss, parent_ptr, ops[j]);
00471                     double childH = heur->evaluate(tss);
00472                     if(heur->is_dead_end())
00473                         continue;
00474                     double childF = childG + childH;
00475                     if(g_parameters.greedy)
00476                         priority = childH;
00477                     else
00478                         priority = childF;
00479                 }
00480 
00481                 open.push(std::tr1::make_tuple(parent_ptr, ops[j], priority));
00482                 search_statistics.countChild(i);
00483             }
00484         }
00485 
00486         // Inserted all children, now insert one more child by letting time pass
00487         // only allow let_time_pass if there are running operators (i.e. there is time to pass)
00488         if(!g_parameters.insert_let_time_pass_only_when_running_operators_not_empty || !parent_ptr->operators.empty()) {
00489             // non lazy eval = compute priority by child
00490             if(!g_parameters.lazy_evaluation) {
00491                 // compute child
00492                 TimeStampedState tss = parent_ptr->let_time_pass(false, true);
00493                 double childG = getG(&tss, parent_ptr, NULL);
00494                 double childH = heur->evaluate(tss);
00495                 if(heur->is_dead_end()) {
00496                     continue;
00497                 }
00498 
00499                 double childF = childH + childG;
00500                 if(g_parameters.greedy)
00501                     priority = childH;
00502                 else
00503                     priority = childF;
00504             }
00505             open.push(std::tr1::make_tuple(parent_ptr, g_let_time_pass, priority));
00506             search_statistics.countChild(i);
00507         }
00508     }
00509     search_statistics.finishExpansion();
00510 }
00511 
00512 enum SearchEngine::status BestFirstSearchEngine::fetch_next_state()
00513 {
00514     OpenListInfo *open_info = select_open_queue();
00515     if(!open_info) {
00516         if(found_at_least_one_solution()) {
00517             cout << "Completely explored state space -- best plan found!" << endl;
00518             return SOLVED_COMPLETE;
00519         }
00520         
00521         if(g_parameters.verbose) {
00522             time_t current_time = time(NULL);
00523             statistics(current_time);
00524         }
00525         cout << "Completely explored state space -- no solution!" << endl;
00526         return FAILED;
00527     }
00528 
00529     std::tr1::tuple<const TimeStampedState *, const Operator *, double> next =
00530         open_info->open.top();
00531     open_info->open.pop();
00532     open_info->priority++;
00533 
00534     if(g_parameters.lazy_state_module_evaluation > 0) {
00535         // tentative new current_predecessor and current_operator
00536         // We need to recheck operator applicability in case a lazy evaluated op (relaxed module calls)
00537         // was inserted in the open queue
00538         const TimeStampedState* state = std::tr1::get<0>(next);
00539         const Operator* op = std::tr1::get<1>(next);
00540 
00541         if (op != g_let_time_pass && !op->is_applicable(*state, false)) {
00542             return fetch_next_state();
00543         }
00544     }
00545 
00546     current_predecessor = std::tr1::get<0>(next);
00547     current_operator = std::tr1::get<1>(next);
00548 
00549     if(current_operator == g_let_time_pass) {
00550         // do not apply an operator but rather let some time pass until
00551         // next scheduled happening
00552         current_state = current_predecessor->let_time_pass(false, true);
00553     } else {
00554         assert(current_operator->get_name().compare("wait") != 0);
00555         current_state = TimeStampedState(*current_predecessor, *current_operator);
00556     }
00557     assert(&current_state != current_predecessor);
00558     return IN_PROGRESS;
00559 }
00560 
00561 OpenListInfo *BestFirstSearchEngine::select_open_queue()
00562 {
00563     OpenListInfo *best = 0;
00564 
00565     switch(mode) {
00566         case PRIORITY_BASED:
00567             for(int i = 0; i < open_lists.size(); i++) {
00568                 if(!open_lists[i].open.empty() && (best == 0 || open_lists[i].priority < best->priority))
00569                     best = &open_lists[i];
00570             }
00571             break;
00572         case ROUND_ROBIN:
00573             for(int i = 0; i < open_lists.size(); i++) {
00574                 currentQueueIndex = (currentQueueIndex + 1) % open_lists.size();
00575                 if(!open_lists[currentQueueIndex].open.empty()) {
00576                     best = &open_lists[currentQueueIndex];
00577                     break;
00578                 }
00579             }
00580             break;
00581     }
00582 
00583     return best;
00584 }
00585 
00586 double BestFirstSearchEngine::getGc(const TimeStampedState *state) const
00587 {
00588     return closed_list.getCostOfPath(*state);
00589 }
00590 
00591 double BestFirstSearchEngine::getGc(const TimeStampedState *state,
00592         const Operator *op) const
00593 {
00594     double opCost = 0.0;
00595     if (op && op != g_let_time_pass) {
00596         opCost += op->get_duration(state);
00597     }
00598     return getGc(state) + opCost;
00599 }
00600 
00601 double BestFirstSearchEngine::getGm(const TimeStampedState *state) const
00602 {
00603     double longestActionDuration = 0.0;
00604     for (int i = 0; i < state->operators.size(); ++i) {
00605         const ScheduledOperator* op = &state->operators[i];
00606         double duration = 0.0;
00607         if (op && op != g_let_time_pass) {
00608             duration = op->get_duration(state);
00609         }
00610         if (duration > longestActionDuration) {
00611             longestActionDuration = duration;
00612         }
00613     }
00614     return state->timestamp + longestActionDuration;
00615 }
00616 
00617 double BestFirstSearchEngine::getGt(const TimeStampedState *state) const
00618 {
00619     return state->timestamp;
00620 }
00621 
00628 double BestFirstSearchEngine::getG(const TimeStampedState* state_ptr, 
00629         const TimeStampedState* closed_ptr, const Operator* op) const
00630 {
00631     double g = HUGE_VAL;
00632     switch(g_parameters.g_values) {
00633         case PlannerParameters::GTimestamp:
00634             g = getGt(state_ptr);
00635             break;
00636         case PlannerParameters::GCost:
00637             if(op == NULL)
00638                 g = getGc(closed_ptr);
00639             else
00640                 g = getGc(closed_ptr, op);
00641             break;
00642         case PlannerParameters::GMakespan:
00643             g = getGm(state_ptr);
00644             break;
00645         case PlannerParameters::GWeighted:
00646             if(op == NULL)
00647                 g = g_parameters.g_weight * getGm(state_ptr) 
00648                     + (1.0 - g_parameters.g_weight) * getGc(closed_ptr);
00649             else
00650                 g = g_parameters.g_weight * getGm(state_ptr) 
00651                     + (1.0 - g_parameters.g_weight) * getGc(closed_ptr, op);
00652             break;
00653         default:
00654             assert(false);
00655     }
00656     return g;
00657 }
00658 


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