aiParts |
Free Open Source Artificial Intelligence C++ Parts |
|
Home Page Open Source Contact Us Free Downloads Releases and Credits Software Status License About rrproj assigning people and/or equipment to projects High-Hope Technique History of the AI View Source Files and how they are organized Making Programs Development Notes Using aiParts Your Application Support and Services |
aiParts Source File
//**********************************************************************
// aipHighHope.h - Problem Solving using the High-Hope Technique
//
// Provides: aipHHProblem aipHHDecision aipHHOption
// aipHHImportance aipHHDecisionItr aipHHOptionItr
//
// An aipHHProblem problem is assembled with aipHHDecision and
// aipHHOption objects.
//
// Calling aipHHProblem::solve() attempts to solve the problem
// using the High-Hope technique.
//
// An aipHHProblem problem has aipHHDecision decisions and
// aipHHOption options.
//
// Copyright (c) 2005, 2008 Brian Marshall
//
// See the license at end of this file.
//
// Developers/Contributers:
// [BRM] Brian Marshall - Calgary - bmarshal@agt.net
//
//
// 08/06/16 [BRM] added decision is_decided(),
// removed decision groups, modified deciding,
// new next_decision(), added aipHHImportance,
// decisions may be decided multiple times,
// removed dcsn.m_opt_prev; small changes
// 05/11/18 [BRM] a failed try that got further than the previous
// try is, optionally, an improvement
// worst decision has extra affect on further tries
// modified constant Curiosity_Starting
// 05/11/18 [BRM] added aipHHDcsnGrp and support in decisions
// 05/11/12 [BRM] added aipHHHope and aspect classes
// moved logic from aipHHProblem to hope aspects
// added aipHHSolveStat, try_to_find_solution()
// removed redundant rand() function
// 05/11/07 [BRM] moved random_num() to class aipBase
// 05/11/01 [BRM] count tries to get to best try
// 05/10/24 [BRM] added decision, option: any_fear(), any_greed()
// added HH_Try_Is_A_Best
// 05/10/21 [BRM] added aipHHOption::dump_hope_to_ptr()
// 05/10/02 [BRM] Split out from non-HH problem, decision
// 05/09/20 [BRM] Development begins.
//
//----------------------------------------------------------------------
// The High-Hope Technique
//
// In the High-Hope technique, decisions and options have an aipHHHope
// member which models hope as fear + greed + curiosity...
// Fear: the desire to avoid known bad things
// Greed: the desire to take advantage of known good things
// Curiosity: the desire to try new things
//
// Solving a problem involves trying many times. The tries affect
// the hopes and the hopes affect the subsequent tries.
//
// The High-Hope technique:
// - for a specified number of tries...
// - attempt to find a solution:
// - while the solution is not complete...
// - pick a decision in an application-specific way
// - for the decision: choose an option:
// the one with the highest g_opt(): the sum of:
// - the sum of:
// - the option-hope-goodness
// possibly plus:
// - (normalized) constant-goodness
// - application-specific non-constant goodness
// - if this solution is the best-so-far: remember it
//
// One try differs from the next as a result of changes in the hope
// of decisions and options. (For example, once an option has been
// tried, the curiosity associated with that option goes down.)
//
// If a decision has multiple options that are the best, one is
// chosen at random. (The random-number generator will always return
// the same series of random numbers.)
//
// In a try, the next decision to decide is the one with the
// highest importance. This may be overridden by subclasses of
// aipHHProblem.
//
// Fear, Greed and Curiosity are handled differently after each try
// (for each decision and option):
// Fear
// Starts at aipNeutral; when a try fails, fear becomes
// stronger; when a solution is found, fear becomes weaker.
// Greed
// Starts at aipNeutral, and when a complete solution is found,
// it is set to one of:
// New-Best, Best, Improved, Changed, Complete.
// Curiosity
// Starts high, drops as decisions and options are tried;
//
// After a series of tries that result in the same solution, the
// hope will be raised to an identical high value for all decisions
// and options that are not in the solution.
//
// After many tries that do not result in a new-best or improved
// solution, fear is weakened and all curiosities are reset to an
// identical high value.
//
// The HighHope software does not use the hope of decisions;
// applications may use it. Applications in which an option
// determines the next decision (such as finding a path through
// a network of nodes) will presumably use decision hope.
//
//----------------------------------------------------------------------
#ifndef aipHighHope_h_guard
#define aipHighHope_h_guard
#include "aipImportance.h"
#include "aipProblem.h"
//----------------------------------------------------------------------
// Constants
static const aipG Curiosity_Starting = aipVeryGood + aipGood;
static const aipG Greed_For_New_Best = aipGood;
static const aipG Greed_For_Best = aipQuiteGood;
static const aipG Greed_For_Was_Best = aipPrettyGood;
static const aipG Greed_For_Improved = aipPrettyGood;
static const aipG Greed_For_Changed = aipFairlyGood;
static const aipG Greed_For_Complete = aipSomewhatGood;;
// Note: High-Hope technique uses: 11000 to 11999
// aipMsg typ values:
static const short HH_Starting_Solve = 11001;
static const short HH_Solve_Has_Ended = 11002;
static const short HH_Starting_New_Try = 11003;
static const short HH_Try_Has_Ended = 11004;
static const short HH_This_Is_Best_So_Far = 11005;
static const short HH_No_Recent_Improve = 11006;
static const short HH_No_Recent_Change = 11007;
static const short HH_No_Recent_Best_So_Far = 11008;
// Try-status after a try has ended
static const short HH_Try_Has_Failed = 11101;
static const short HH_Try_Is_New_Best = 11102;
static const short HH_Try_Is_A_Best = 11103;
static const short HH_Try_Is_Improved = 11104;
static const short HH_Try_Is_Changed = 11105;
static const short HH_Try_Is_Complete = 11106;
//----------------------------------------------------------------------
// Classes. Sub-classing is shown by indentation.
// class aipG is a typedef for aipGoodness
// aipHope is a compound emotion: Fear + Greed + Curiosity
// class aipBase; ( in aipBase.h )
class aipHHImportance; // Importance for choosing decisions
// class aipDemon; ( in aipPandemonium.h )
// class aipAspect; ( in aipEmotion.h)
// class aipEmotion; ( in aipEmotion.h)
// class aipCompEmotion; ( in aipEmotion.h)
// class aipHope; ( in aipEmotion.h)
class aipHHHope; // hope with High-Hope aspects
class aipHHFearAspect; // how messages affect fear in hope
class aipHHGreedAspect; // how msgs affect greed in hope
class aipHHCuriosityAspect; // msgs affect curiosity in hope
// class aipProblem; ( in aipProblem.h )
class aipHHProblem; // problem with aipDecision
// class aipDecision; ( in aipDecision.h )
class aipHHDecision; // Decision in aipHHProblem
// class aipOption; ( in aipDecision.h )
class aipHHOption; // Option in aipHHDecision
// class aipDemonItr; ( in aipPandemonium.h )
class aipHHDecisionItr; // aipHHDecision iterator
class aipHHOptionItr; // aipHHOption iterator
class aipHHSolveStat; // solve() status and statistics
// class aipMsg; ( in aipBase.h )
class aipHHMsg; // High-Hope problem-solving message
//======================================================================
// aipHHImportance - Importance for choosing decisions
class aipHHImportance : public aipImportance {
long m_been_prob; // has been a problem aspect
public:
aipHHImportance () { m_been_prob = 0; }
virtual ~aipHHImportance () {}
virtual long val () const {
return aipImportance::val() + m_been_prob;
}
virtual void take_msg (aipMsg *m);
};
//======================================================================
// aipHHHope - Hope with High-Hope aspects
class aipHHHope : public aipHope {
public:
aipHHHope ();
virtual ~aipHHHope () {}
};
//======================================================================
// aipHHFearAspect - how messages affect fear in hope
class aipHHFearAspect : public aipAspect {
protected:
aipFear * fear () const { return (aipFear *)emotion(); }
public:
aipHHFearAspect() {}
virtual ~aipHHFearAspect() {}
virtual void take_msg (aipMsg *m);
};
//======================================================================
// aipHHGreedAspect - how msgs affect greed in hope
class aipHHGreedAspect : public aipAspect {
protected:
aipGreed * greed () const { return (aipGreed *)emotion(); }
public:
aipHHGreedAspect() {}
virtual ~aipHHGreedAspect() {}
virtual void take_msg (aipMsg *m);
};
//======================================================================
// aipHHCuriosityAspect - how msgs affect curiosity in hope
class aipHHCuriosityAspect : public aipAspect {
protected:
aipCuriosity * curiosity() const { return (aipCuriosity*)emotion(); }
public:
aipHHCuriosityAspect() {}
virtual ~aipHHCuriosityAspect() {}
virtual void take_msg (aipMsg *m);
};
//======================================================================
// aipHHProblem - Problem with solve() that uses High-Hope technique.
//
// m_g_cmp_cur, m_g_cmp_prev, m_g_cmp_bsf are goodnesses
// of solutions - the sum of the goodness of each decision. These
// values are meaningful when compared to each other; they may or
// may not be meaningful when compared to standard goodness constants
// like aipQuiteGood and aipVeryBad. They may not be actual goodness
// values at all - in a shortest-path problem, they might be the
// solution-distance, in metres or kilometres, multiplied by -1.
//
// For problems in which option-goodness should affect which option
// is chosen by a decision...
// normalize_option_goodnesses() should be called before solve()
// if options do get goodnesses that are not really goodness values
// (ex: they are kilometers or dollars), and there are values
// that would be inappropriate goodness values - for example, a nice
// low cost of $1200, stored in a goodness as -1200, interpreted as
// a goodness would be very-very-bad. normalize_option_goodnesses()
// will force the values into a range of roughly -17 to +17.
//
// Subclasses that require option-goodness normalization can:
// - use normalize_option_goodnesses(), or,
// - override normalize_option_goodnesses(), or,
// - normalize the values before they are used to make options
//
// solve() tries to find a maximum; if the best solution is a minimum,
// appropriate user-meaningful goodness values must be multiplied by
// -1. If this sort of thing is going on, a subclass should override
// the virtual function bsf_goodness_for_user().
//
// bsf_goodness_for_user() returns the goodness value that is to
// be reported to the user for the best-so-far solution found.
//
// If m_dcsn_is_progress is:
// 1: each decision is a step closer to completing solution
// 0: different solutions can have different number of decisions
//
// If m_worst_is_extra_bad is true, the goodess of the worst decision
// will be added to the solution-goodness, for purposes of comparing
// to other solutions, an extra couple of times.
class aipHHProblem : public aipProblem {
long m_num_try; // times solve() will try
int m_dcsn_is_progress; // 0 = no
int m_worst_is_extra_bad; // 0 = no
int m_should_log_tries; // 0 = no
aipHHSolveStat * m_solve_stat; // status and statistics
protected:
virtual void try_to_find_solution ();
virtual aipHHDecision * next_decision ();
virtual int solution_is_complete () const;
virtual void log_this_try () {}
// threshold values used in solve()
virtual long many_tries_since_change() const {
return (5 + m_num_try/400);
}
virtual long many_tries_since_improve() const {
return (20 + m_num_try/200);
}
virtual long many_tries_since_bsf() const {
return (40 + m_num_try/50);
}
virtual aipG too_bad_to_go_on() const {
return aipForbidden; // subclasses can override
}
// used in some types of problems...
virtual void normalize_option_goodnesses(); // sample
public:
aipHHProblem ();
virtual ~aipHHProblem ();
// setting up the problem
void set_num_try (long x) { m_num_try = x; }
void set_dcsn_is_progress (int x) { m_dcsn_is_progress = x; }
void set_worst_is_extra_bad (int x) { m_worst_is_extra_bad = x; }
void add_decision (aipDecision *x) {} // use add_hh_decsion
void add_hh_decision (aipHHDecision *x);
void enable_log_tries () { m_should_log_tries = 1; }
void disable_log_tries () { m_should_log_tries = 0; }
int should_log_tries () const { return m_should_log_tries; }
// about the problem
long num_try () const { return m_num_try; }
long num_decisions() const;
int dcsn_is_progress () const { return m_dcsn_is_progress; }
int worst_is_extra_bad () const { return m_worst_is_extra_bad; }
aipHHDecisionItr hh_decision_iterator() const;
aipHHSolveStat * solve_stat () const { return m_solve_stat; }
virtual aipG g();
virtual void take_msg (aipMsg *m) { aipProblem::take_msg(m); }
virtual void note_decide (aipHHDecision *d, aipHHOption *o) {}
virtual aipG solve(); // returns goodness for user
};
//======================================================================
// aipHHDecision - Decision used in an High-Hope aipHHProblem
//
// A set of decisions may share a set of options. An option may be
// added to more than one decision, but, for destruction purposes,
// only one decision will own the option.
//
// An application may require that a decision be decided more than
// once to complete a solution - m_num_to_decide is set to more
// than one (in the constructor) and the chosen options for the
// current and best-so-far solutions for this decision are stored
// in the m_chsn_opts_xxx pandemoniums. (If the decision is only
// to be decided once, the pointers to these pandemoniums are zero.
class aipHHDecision : public aipDecision {
aipHHImportance m_importance; // importance in decision order
aipHHHope * m_hope; // how well this decision is doing
aipHHOption * m_opt_cur; // The curremt option choice
aipHHOption * m_opt_bsf; // The best-so-far option choice
long m_num_to_decide; // times to decide in a try
long m_num_decided; // times decided in this try
aipPandemonium * m_chsn_opts_cur; // opts chosen in cur try
aipPandemonium * m_chsn_opts_bsf; // opts chosen in bsf try
public:
aipHHDecision (long the_num_to_decide =1);
virtual ~aipHHDecision ();
void add_option (aipOption *x) {} // use add_hh_option
void add_hh_option (aipHHOption *x);
void dump_hope_to_ptr (char *p) const { m_hope->dump_to_ptr(p); }
aipHHProblem * hh_prob () const { return (aipHHProblem*)owner(); }
virtual void take_msg (aipMsg *m);
aipHHOptionItr hh_option_iterator () const;
aipHHOptionItr cur_opt_iterator () const; // current options
aipHHOptionItr bsf_opt_iterator () const; // best-so-far opts
aipG g_hope () const;
long num_to_decide (void) const { return m_num_to_decide; }
long num_decided (void) const { return m_num_decided; }
int is_decided () const;
virtual long imp () const { return m_importance.val(); }
long num_opt_remaining () const;
int any_fear () const {
if (!m_hope) return 0;
return (m_hope->fear()->g() < aipNeutral);
}
int any_greed () const {
if (!m_hope) return 0;
return (m_hope->greed()->g() > aipNeutral);
}
aipHHOption * opt_cur () const { return m_opt_cur; }
aipHHOption * opt_bsf () const { return m_opt_bsf; }
virtual aipHHOption * hh_decide();
};
//======================================================================
// aipHHOption - an option used in High-Hope problem-solving
//
// m_g_user_constant is a constant goodness that is meaningful
// to the user (although it may have been multiplied by -1 if the
// problem-solving is looking for a minimum).
//
// m_g_constant is m_g_user_constant that has been normalized and
// scaled into a range so that it can be meaningfully added to the
// goodness of the hope.
//
// In aipDecision::solve()...
// g_opt() is used to make decisions
// g_opt_cmp() is used to compare solutions
// g_opt_usr() is reported to the user.
//
// Generally, g_opt() is partially or completely based on the hope
// of the option, whereas g_opt_cmp() and g_opt_usr(), used in the
// calculation of goodness of a solution, are not affected by hope.
//
// g_opt_cmp() and g_opt_usr() may return the same value, or,
// if a minimum is desired, and therefore m_g_user_constant was made
// negative, g_opt_usr() may return the negative of g_opt_cmp().
class aipHHOption : public aipOption {
aipG m_g_user_constant;
aipG m_g_constant;
aipHHDecision * m_bsf_chooser;
aipHHHope * m_hope; // how well this option is doing
public:
aipHHOption(aipG g_user_const);
virtual ~aipHHOption();
// for aipHHProblem::normalize_option_goodnesses()
void set_norm_g_constant (long new_val) {
m_g_constant.set_numeric_value(new_val);
}
void dump_hope_to_ptr (char *p) const { m_hope->dump_to_ptr(p); }
aipHHDecision * hh_opt_owner () const {
return (aipHHDecision*)owner(); // all options have an owner
}
aipHHDecision * hh_opt_chooser () const {
return (aipHHDecision*)chooser(); // or, zero before decide()
}
aipHHDecision * hh_bsf_chooser () const {
return m_bsf_chooser; // best-so-far chooser of this opt
}
int is_chosen () const { return chooser() ? 1 : 0; }
virtual void take_msg (aipMsg *m);
aipG g_constant () const { return m_g_constant; }
aipG g_user_constant () const { return m_g_user_constant; }
aipG g_hope () const;
int any_fear () const {
if (!m_hope) return 0;
return (m_hope->fear()->g() < aipNeutral);
}
int any_greed () const {
if (!m_hope) return 0;
return (m_hope->greed()->g() > aipNeutral);
}
virtual aipG g_opt();
virtual aipG g_opt_cmp() { return g_user_constant(); }
virtual aipG g_opt_usr() { return g_user_constant(); }
};
//======================================================================
// aipHHDecisionItr - Iterator for aipHHDecision in a aipHHProblem
class aipHHDecisionItr : public aipDemonItr {
public:
aipHHDecisionItr () {}
aipHHDecisionItr (aipPandemonium *p) {
set_demon_itr(p,0);
}
aipHHDecisionItr (const aipHHDecisionItr& x) {
set_demon_itr (x.pandemonium(), x.current());
}
virtual ~aipHHDecisionItr () {}
aipHHDecisionItr& operator = (const aipHHDecisionItr& x) {
set_demon_itr (x.pandemonium(), x.current());
return *this;
}
aipHHDecision * first() {
return (aipHHDecision*)aipDemonItr::first();
}
aipHHDecision * next() {
return (aipHHDecision*)aipDemonItr::next();
}
};
//======================================================================
// aipHHOptionItr - Iterator for aipHHOption in an aipHHDecision
class aipHHOptionItr : public aipDemonItr {
public:
aipHHOptionItr () {}
aipHHOptionItr (aipPandemonium *p) {
set_demon_itr(p,0);
}
aipHHOptionItr (const aipHHOptionItr& x) {
set_demon_itr (x.pandemonium(), x.current());
}
virtual ~aipHHOptionItr () {}
aipHHOptionItr& operator = (const aipHHOptionItr& x) {
set_demon_itr (x.pandemonium(), x.current());
return *this;
}
aipHHOption * first() { return (aipHHOption*)aipDemonItr::first(); }
aipHHOption * next() { return (aipHHOption*)aipDemonItr::next(); }
};
//======================================================================
// aipHHSolveStat - solve() status and statistics
class aipHHSolveStat {
aipHHProblem * m_problem;
friend class aipHHProblem;
// About the solving...
int m_should_log_tries; // 0 = do not write about try in log
// sum of option.g_opt_cmp() - can be compared to each other
// (may include dollars or miles or something)
aipG m_g_cmp_cur; // Goodness of current try
aipG m_g_cmp_prev; // Goodness of previous try
aipG m_g_cmp_bsf; // Goodness of best-so-far try
// sum of option.g_opt_usr - to be reported to the user
// (may be miles or dollars or minutes or goodness, etc.)
aipG m_g_usr_cur; // Goodness (or $ or miles, etc. )
aipG m_g_usr_bsf; // Goodness of best-so-far try
// About the current try...
long m_i_try;
short m_try_result;
int m_solution_is_complete;
int m_solution_is_new_best;
long m_num_decisions_made; // in current try, in solve()
long m_num_decisions_prev; // in previous try, in solve()
long m_num_tries_to_best;
aipHHDecision * m_failed_decision; // or zero if success or quit
aipHHDecision * m_worst_decision;
aipG m_worst_decision_g_cmp;
long m_tries_since_change_count;
long m_tries_since_improve_count;
long m_tries_since_bsf_count;
int m_is_too_bad;
int m_is_many_since_new_best;
int m_is_many_since_improve;
int m_is_many_since_change;
public:
aipHHSolveStat(aipHHProblem *p);
virtual ~aipHHSolveStat() {}
// sum of option.g_opt_cmp() - can be compared to each other
aipG g_cmp_cur () const { return m_g_cmp_cur; }
aipG g_cmp_prev () const { return m_g_cmp_prev; }
aipG g_cmp_bsf () const { return m_g_cmp_bsf; }
// sum of option.g_opt_usr() - can be reported to user
aipG g_usr_cur () const { return m_g_usr_cur; }
aipG g_usr_bsf () const { return m_g_usr_bsf; }
// about the current try ...
long i_try () const { return m_i_try; }
short try_result () const { return m_try_result; }
int solution_is_complete () const { return m_solution_is_complete; }
int solution_is_new_best () const { return m_solution_is_new_best; }
long num_tries_to_best () const { return m_num_tries_to_best; }
long percent_of_tries_done() {
return ( (m_i_try * 100) / m_problem->num_try() );
}
aipHHDecision * failed_dcsn () const { return m_failed_decision; }
int is_too_bad () const { return m_is_too_bad; }
int try_is_a_success () { return (m_g_cmp_cur > aipForbidden); }
int prev_is_a_success () { return (m_g_cmp_prev > aipForbidden); }
int try_is_new_best () { return m_solution_is_new_best; }
int try_is_a_best () { return (try_is_a_success() &&
m_g_cmp_cur == m_g_cmp_bsf); }
int try_is_a_change () { return (m_g_cmp_cur != m_g_cmp_prev); }
int try_is_improvement() {
return ( (prev_is_a_success() && m_g_cmp_cur > m_g_cmp_prev) ||
(m_problem && m_problem->dcsn_is_progress() &&
m_g_cmp_bsf.is_forbidden() && !m_is_too_bad &&
m_i_try > 0 &&
m_num_decisions_made > m_num_decisions_prev) );
}
int is_many_since_new_best () const {
return m_is_many_since_new_best;
}
int is_many_since_improve () const {
return m_is_many_since_improve;
}
int is_many_since_change () const {
return m_is_many_since_change;
}
long tries_since_change_count () const {
return m_tries_since_change_count;
}
long tries_since_improve_count () const {
return m_tries_since_improve_count;
}
long tries_since_bsf_count () const {
return m_tries_since_bsf_count;
}
};
//======================================================================
// aipHHMsg - message for High-Hope problem-solving
class aipHHMsg : public aipMsg {
aipHHProblem * m_prob;
int m_is_in_cur_solution;
int m_is_the_failure;
public:
aipHHMsg (aipHHProblem *p, short typ);
~aipHHMsg() {}
aipHHProblem * prob () const { return m_prob; }
aipHHSolveStat * solve_stat () const {
return m_prob ? m_prob->solve_stat() : 0;
}
void set_is_in_cur_solution (int x) { m_is_in_cur_solution = x; }
void set_is_the_failure (int x) { m_is_the_failure = x; }
int is_in_cur_solution () const { return m_is_in_cur_solution; }
int is_the_failure () const { return m_is_the_failure; }
};
//======================================================================
#endif
//======================================================================
// License
//
// Permission is hereby granted, free of charge, to any
// person obtaining a copy of this software and associated
// documentation files (the "Software"), to deal in the Software
// without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to
// whom the Software is furnished to do so, subject to the
// following conditions:
//
// The copyright notice and this license shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//
//**********************************************************************
|