aiParts

Open Source Artificial Intelligence C++ Parts

Home Contact Releases Download Source Files Modules Read-Me License Your Application

The High-Hope Strategy The high-hope strategy is a technique people use to find solutions to dirty-hard problems -- highly constrained problems that can't be solved by brute force. The technique was identified by Brian Marshall while studying how people solve staff-scheduling problems. The technique is easy to implement in software, and easy to specialize to solve a particular type of problem. There is generally no worse than a linear relationship between program size and the number of problem constraints. The Technique The High-Hope Strategy... Given a dirty-hard problem, try to solve it repeatedly and remember the best solution(s). In a try, where there is a choice of which sub-problem (or decision) to address next, choose the one that is most urgent. An urgent sub-problem is one you have the urge to address next, either because it is particularly important or it is particularly safe. At each decision, pick the option with the most hope. The hope of an option is the sum of problem-domain-specific factors plus strategic factors that can be described as fear, greed and curiosity. The High-Hope strategy is a way of exploring a solution-space that is too large to search exhaustively. It's subtle. Hopes, with their fears, greeds and curiosities, control a try. The results of the try affect these factors, which then go on to affect subsequent tries. The factors interact with one another in a chaotic fashion. A variety of different solutions are tried, but each one is an attempt to do what appears best. It is the humble opinion of the researcher that people and other animals evolved the use of this technique because it is so easy to implement. It can be implemented simply in neurons or C++ or hydraulics or levers and string (given the appropriate inputs, of course). Big Problems Dirty-hard problems have so many solutions that only a vanishingly small proportion can be considered. You cannot "try each combination of the best few choices for every decision". If you have to schedule 20 employees for 7 days and you consider the best two options for each employee-day, there are more than 10 to the power of 42 combinations. The high-hope stategy can be viewed as an approach to exploring a very small proportion of a solution-tree. It is an alternative, for instance, to a depth-first or breadth-first search. Only the best When you try to put together a good staff schedule, you don't try the best two or three options at each decision. If you are trying to figure out the best way of getting to the airport, you don't try the best two or three directions at each intersection. Each time you try, you pick only the best option at each decision. A try differs from the previous one because of what you learn while trying. What appears best depends on your experience. Hope is a Summary At each decision, you pick the option which appears to be the best, the option that offers the most hope. Hope is the summary of the evaluation of all factors being considered. The hope associated with an option is the single, final quantity that can be compared to the hope of other options. The hope associated with an option combines the results of the evaluation of... static factors ("It's good for Bill to work evenings.)" dynamic factors based on decisions made up to this point ("It would be bad for Sally to work today; she has already worked five days in a row.") strategic factors based on what has been learned in previous tries ("This option worked really well last time.") Static and dynamic factors are particular to the problem domain. Implementing them in software is easy -- for each one, you write a bit of code that evaluates the factor and returns a goodness value. Such code tends to be of low complexity. If you want to add one more constraint, you add one more bit of code. The strategic factors control how the solution space is searched - the balance between trying new things and trying to improve the old ones. Fear, Greed and Curiosity The primary strategic factors in the high-hope stategy are hope are fear, greed and curiosity. These factors persist from try to try, and they change as a result of tries. Fear is the feeling that something bad may happen. Fear causes you to avoid an option that has been a problem in the past. Fear starts at Neutral and becomes more negative as an option is involved in unsuccessful tries. Greed is the feeling that you know how to make something good happen. Greed attracts you to options that have worked well in the past. Greed starts at Neutral and becomes more positive as an option is involved in successful tries. Curiosity is the feeling that an untried option might turn out well. Curiosity attracts you to options that might turn out even better than any you have already tried. Curiosity about an apparently acceptable option starts low and increases as an option is rejected during tries. Hope is a Sum A hope resolves to a goodness. Hope factors that contribute to a hope resolve to a goodnesses. They can be combined by summing, so long as goodnesses are implemented like... VeryVeryBad = -1024 VeryBad = -512 QuiteBad = -256 Bad = -64 FairlyBad = -32 SomewhatBad = -8 SlightlyBad = -2 VerySlightlyBad = -1 Neutral = 0 VerySlightlyGood = 1 SlightlyGood = 2 SomewhatGood = 3 FairlyGood = 4 Good = 5 QuiteGood = 6 VeryGood = 7 VeryVeryGood = 8 The lack of symmetry around Neutral is a reflection of the fact that the worse an aspect is, the more important it is. There may be, for example, a variety of good aspects to setting the alarm clock an hour later, but if one of the aspects is probably getting fired, it's probably a bad thing to do.