Geek Answers Handbook

VS Rete backtracking

In my class, I was taught the Prolog backtracking algorithm and the Retre forprop algorithm, but I was also told that Rete can be used for backprop.

How it works? How is it similar / different from Prolog reverse tracking?

For example, this is one of the exercises that they gave me:

(R1) 24fingers and antennas => origin(mars) (R2) shy and 5feet => origin(mars) (R3) shy and 4arms => origin(venus) (R4) looksDownWhenTalking => shy (R5) fleesWhenSeen => shy

The purpose of the following facts is given: to find the origin of an alien:

 (F1) fleesWhenSeen (F2) 4arms

In Prolog, we would solve it by a pattern matching the origin(X) target with the RHS rules. The rule matches R1, R2, and R3, so the first R1 will be launched, and we will try to resolve the 24fingers and antennas subtitles that fail.

Then we will go back to the beginning and run R2, which will eventually fail and finally step back and run R3, which will succeed.

So, X ends with binding to venus in a successful request, and the algorithm ends.

Now, how would we solve the same exercise using the backtep rete algorithm?

I naively assume that we will use a list of subgoals starting with origin(X) to trigger trigger rules whose RHS matches subgoals.

But I don’t understand how the Rete algorithm will take care of returning back when some subgoals fail, or how he will find out that he succeeded as soon as he resolves a certain subset of the goals.

+7
prolog backtracking rule-engine rete
source share
2 answers

There is no standard implementation to support reverse chaining in a direct connection system. Hybrid tools have implemented this functionality using various methods. One method associated with reverse link data is described here: http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/ . Some additional information: JESS vs DROOLS: reverse chain and http://herzberg.ca.sandia.gov/docs/70/rules.html .

+2
source share

Here's a description of the Rete algorithm: http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218 .

Prolog uses the unificaton algorithm, which unlike template matching has templates on both sides (target / rule head).

Edit

Here is a lot of information about Rete and Prolog.

Creation of expert systems in Prolog

http://www.amzi.com/distribution/files/xsip_book.pdf

http://www.oopweb.com/Prolog/Documents/XSIP/Volume/08performance.htm

THEORETICAL FRAME AND ALSO IMPLEMENTATION OF THE PROLOG INTERPRETER

http://staff.um.edu.mt/mcam1/Files/Dissertation.pdf

+2
source share

More articles:


All Articles