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

[Geoffrey De Smet]

If your problem is A* search efficient, you should use A* search. It's 
better and simpler than any metaheuristic.
Problem is, most real-life problems are NP complete and A* search 
doesn't work efficiently on those.

Some examples:
- Quickest route between 2 cities: Use A* search
- Quickest route to visit 4+ cities (TSP): Use metaheuristic (or LP)
- Bin packing: Use metaheuristic

The easiest way to make this decision, is to take a look if you find 
your problem on this list:
    http://en.wikipedia.org/wiki/List_of_NP-complete_problems
(which is a long list of Karp's list: 
http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems )
If your problem or a subproblem of it is on that list, use Planner, 
because A* search will take a few billion years too long.
Otherwise go for A* search.

Op 17-06-12 21:57, Davide Sottara schreef:
> 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.
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>

-- 
With kind regards,
Geoffrey De Smet