Prolog backtracking VS Rete backtracking

Question

In my class I have been taught the Prolog backtracking algorithm and the Rete forprop algorithm, but I have also been told that Rete can be used to do backprop.

How does that work? In which ways is it similar / different to Prolog backtracking?

---

For example, this is one of the exercises I have been given:

(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 goal is given the following facts find the origin of the alien:

(F1) fleesWhenSeen
(F2) 4arms

In Prolog, we would solve it by pattern matching the goal origin(X) against the RHS of the rules. The rule matches against R1, R2 and R3, so first R1 will be triggered, and we would try to resolve the subgoals 24fingers and antennas which would fail.

Then we would go backtrack to the beginning and trigger R2, which eventually will fail, and finally backtrack and trigger R3, which succeeds.

So X ends up binded to venus in a successful query, and the algorithm ends.

---

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

I naively assume that we would use a list of subgoals, starting with origin(X), to start triggering rules whose RHS matches the subgoals.

But it isn't clear to me how the Rete algorithm would take care of backtracking when some subgoals fail, or how would it know that it has succeed once it resolves a certain subset of goals.

Answer 1

There is no standard implementation for supporting backward chaining in a forward chaining system. Hybrid tools have implemented this functionality using different techniques. One technique, data-driven backward chaining, is described here: http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/. Some additional information: JESS vs DROOLS : Backward chaining and http://herzberg.ca.sandia.gov/docs/70/rules.html.

Answer 2

Explanation of the Rete algorithm is provided here: http://www.drdobbs.com/architecture-and-design/the-rete-matching-algorithm/184405218 .

In Prolog the unificaton algorithm is used that unlike of pattern-matching has patterns on both sides (goal / rule head).

Edit

here is a lots of info about Rete and Prolog.

Building Expert Systems in Prolog

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

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

THE THEORETICAL FRAMEWORK AND IMPLEMENTATION OF A PROLOG INTERPRETER

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