[rules-users] How to write a Heuristic Knowledge in Drools Expert?

[Davide Sottara]

Are you familiar with the A* algorithm? A heuristic function is typically
used in (state-)space search problems: at a given point, you may have
alternative "paths" you can choose and the heuristic will help you
estimate/predict how "successful" exploring that branch would be by giving a
score. The function usually involves reviewing your path so far and trying
to look ahead before making another step.
More generally, heuristic decision making is a process where you choose an
action (the "path") according to your current knowledge (your state) and
some prediction criteria which is not necessarily the best, but the most
promising. 

A heuristic search rule could look like this:

rule "Example"
when
  // you have a current state, given by one or more patterns
  $here : CurrentState( $history : path )
  // then you query for / generate a list of possible follow-up alternatives 
  ?possiblePath( $here, $nextFromHere )
  // optionally, you filter those which make sense qualitatively
  Filter( ... ) from $nextFromHere           // notice: $nextFromHere might
not be in the WM
  // optionally, and/or you apply some heuristic scoring function, filtering
quantitatively 
  // notice that it might use the history, the current position or the next
tentative step
  $score : Double( this > THRESHOLD ) from heur( $path, $here, $nextFromHere
)  
  
  // any additional logic, e.g. accumulate scores?
  ....
then
  // make your choice
  insert ( new Step( $nextFromHere ) );
  // the step will later modify the currentState
end

Notice that the following MUCH simplified version - a rule - is doing the
same thing... Simply, there is only one promising and meaningful path - e.g.
administering an aspiring - which is automatically chosen given the current
state (of Fever).

rule "a more traditional rule"
when
  $path : MedicalHistory( ... )
  $here : FeverDiagnosis( temp < 38 )
  // ?possiblePath( $here, $nextFromHere )  --> let's say aspirin, strong
antibiotics and bone marrow transplant
  // but you can already figure out the scores a realistic function would
give to the alternatives...
  // (ok, allergies from $path would make it different, but ignore...)
  // $score : Double( this > THRESHOLD ) from heur( $path, $here,
$nextFromHere )  
then
  // so you hardcode your choice!
  insert( new AspirinAdministration() );
end


Drools Planner is slightly different: you might indeed use it to define a
plan - i.e. a sequence of actions to reach a goal - ***provided*** that you
can reliably estimate the consequences of any action (move) you allow.
Planner, however, already implements its own search strategies. What you
provide there is a "score" for the current state (aka candidate "solution"),
expressed in terms of hard and soft constraints, that planner algorithms
will consume. You still have to provide the alternative moves and their
effects, but the main difference between the scoring (the constraints) and
heuristic function is that the former usually just look at the current
state. So, in planner 1) you tentatively make a step and evaluate the
results, 2) then backtrack and repeat until you have seen all possible
paths, 3) you choose the best one according to the strategy (it's called
meta-heuristic)

With a heuristic function, you evaluate your possible future outcome (not
just one step ahead) before you do make the step, so that's "predictive". 

Now, coming back to your question : how do you implement a heuristic
function?
The answer is: first you have to define it, given your problem :) 
Only then you can think of an implementation, but functions(), queries and
rules with optional accumulates seem good candidates!

Best
Davide

--
View this message in context: http://drools.46999.n3.nabble.com/How-to-write-a-Heuristic-Knowledge-in-Drools-Expert-tp4018012p4018015.html
Sent from the Drools: User forum mailing list archive at Nabble.com.