Re: Prolog and AION

rupertlssmith@xxxxxxxxxxxxxx wrote:
On May 17, 10:28 pm, Philip.Yu...@xxxxxxxxx wrote:
I'd like to know if there are things that AION can do that Prolog
cannot.

Thanks.

Hard to say, given that you cannot download and try AION for free. I'm
interested to see a language that has both forward and backward
chaining modes of operation; is that production rules and goal
seeking? If you have any code examples of AION that demonstrate how
the language works it'd be nice to see them...


I do not know AION, but I could make an educated guess. I had this discussion many times with production rules adepts, but in my opinion, even though it can be used to encode a form of goal-directed reasoning, what they call "backward chaining", is not really backward chaining. I have attached the best article I know of explaining production rules backward chaining, so that you can make up your own minds.

Cheers,
Peter


Forward and Backward Chaining

By Charles Forgy, PhD



I will discuss the most fundamental issue in rules: The difference between forward and backward chaining. In the rules literature, there are many articles that discuss the difference between forward and backward chaining. Some of these articles tell only a part of the story, and as a result, while they may be technically correct, they can be misleading. I hope to give a more complete explanation. This is a three-part column. The first part gives a detailed description of forward and backward chaining. Next part will explore why forward and backward chaining are more alike than it may appear at first.

An Example

Before describing the two kinds of chaining, let's define a few simple rules that we can use to show what the two systems would do. The following rules might be found in an order processing system. The rules operate on the following variables:

* last-years-orders: The total amount spent by the customer in the last twelve months.
* current-order: The dollar amount of the current order.
* discount-level: An indication of how good a customer this one is; the possible values are Platinum, Gold, Silver, and Default.
* eligible-for-discount: A logical variable; it is true if the current-order is large enough to be discounted.
* discount-amount: How much to discount the current order.

The rules are:

R1: If last-years-orders are >= $10,000
Then discount-level is Platinum.

R2: If last-years-orders are < $10,000
And last-years-orders are >= $5,000
Then discount-level is Gold.

R3: If last-years-orders are < $5,000
And last-years-orders are >= $2,000
Then discount-level is Silver.

R4: If last-years-orders are < $2,000
Then discount-level is Default.

R5: If current-order is >= $100
Then eligible-for-discount is true.

R6: If current-order is < $100
Then eligible-for-discount is false.

R7: If discount-level is Platinum
And eligible-for-discount is true
Then discount-amount is 10%.

R8: If discount-level is Gold
And eligible-for-discount is true
Then discount-amount is 7%.

R9: If discount-level is Silver
And eligible-for-discount is true
Then discount-amount is 5%.

R10: If discount-level is Default
Then discount-amount is 0%.

R11: If eligible-for-discount is false
Then discount-amount is 0%.


Forward Chaining
A forward-chaining rule based system contains two basic components:

1. A collection of rules.
2. A collection of facts or assumptions that the rules operate on. (This is sometimes called the rules Working Memory.)

The standard definition of a forward-chaining system is that the system operates by repeating the following sequence of operations:

1. Examine the rules to find one whose If part is satisfied by the current contents of Working memory.
2. Fire the rule by adding to Working Memory the facts that are specified in the rule's Then part. (The Then part may perform other actions as well, but we can ignore that for now.)

This control cycle continues until no rules have satisfied If parts.

For an example of how this works, suppose we were executing the rules above, and suppose the system starts with the two following facts in Working Memory:

last-years-orders = $6300
current-order = $260

With those facts, two rules, R2 and R5 can fire. If R2 fires first, it will add the fact

discount-level = Gold

Then rule R5 will fire and add the fact

eligible-for-discount = true

After these two new facts have been added, rule R8 will be satisfied. It will fire and add the fact

discount-level = 7%

At this point, no other rules will have satisfied If parts, so execution will terminate.


Backward Chaining
A backward-chaining rule based system contains three basic components:

* A collection of rules.
* A collection of facts or assumptions for the rules to operate on. (The Working Memory.)
* A stack of goals, where a goal is simply a statement of something that the rules need to determine.

The control flow of a backward-chaining system is more complex than that of a forward-chaining system. Backward-chaining systems try to satisfy the goals in the goal stack. They do this by finding rules that can conclude the information needed by the goal, and trying to make the If parts of those rules satisfied. In more detail, the standard backward-chaining control cycle is:

1. Check the conclusions of the rules to find all rules that can satisfy the top goal on the stack.

2. Process these rules one at a time:

a. Evaluate the conditions in the rule's If part one at a time:

i. If the condition is currently unknown (that is, if there is not enough information currently known to determine whether the condition is satisfied) push a goal to make that condition known, and recursively invoke the system.

ii. If the condition is known to be unsatisfied, continue with the loop at Step 2.

iii. If it was not possible to determine whether the condition was satisfied, continue with the loop at Step 2.

b. If all the conditions in the selected rule are satisfied, add to Working Memory the facts specified in the Then part of the rule, pop the goal off the stack, and return from this invocation of the system.

The system terminates with success when the goal stack is empty. It terminates with failure if the system runs out of rules to try in Step 2.

Using our same example, we will again suppose the system starts with the two following facts:

last-years-orders = $6300

current-order = $260

In a backward-chaining system, we also need an initial goal. Let us assume the stack contains one goal:

G1: Determine the value of discount-amount

When the system begins evaluating goal G1, it will find that R7, R8, R9, R10, and R11 might satisfy this goal. If it starts with R7, it will determine that to satisfy R7's If part, it need the value of discount-level, so it will assert the goal

G2: Determine the value of discount-level

It will determine that rules R1, R2, R3, and R4 could satisfy this goal. If it tries R1 first, it will determine that it has all the information that it needs (since it already has the value of last-years-orders), but that R1's If part is not satisfied. If it tries R2 next, it will determine that R2's If part is satisfied, and conclude

discount-level = Gold

When it adds this fact to Working Memory, it will pop goal G2 from the stack, and return to G1 and R7 (where it was when it pushed G2). It will determine that R7's If part cannot be satisfied. If it selects R8 next, it will determine that the first condition in R8 is satisfied, but that it does not have the necessary information for the second condition. It will push the goal

G3: Determine the value of eligible-for-discount

It will find that rules R5 and R6 can determine this value. If it tries R5 first, it will find that R5's single condition is satisfied (because last-years-orders are $6300). It will conclude

eligible-for-discount = true

It will pop G3, and return to G1 and R8. It will determine that both of R8's conditions are satisfied. It will conclude

discount-amount = 7%

It will pop goal G1, and terminate with success.

The backward-chaining system, then, concludes the same value for discount-amount as the forward-chaining system, though it follows a completely different path to the conclusion.

Conclusion
The standard brief explanation of the difference between forward and backward chaining usually focuses on two points:

* Forward-chaining systems simply fire rules whenever the rules' If parts are satisfied. Backward-chaining systems attempt to fire rules only when those rules can potentially satisfy a goal.
* Backward-chaining systems automatically create new subgoals when more information is needed to determine whether a given rule is satisfied. Forward-chaining systems do not automatically create subgoals.

This is correct as far as it goes, but it does not give an accurate picture of how rules are used in practice. Next part will attempt to show how rules are actually used. It will also discuss the RulesPower system's use of forward and backward chaining for business process automation.

In the last column we looked at the basic difference between forward and backward chaining rule systems. In this column we will continue to look at chaining. First we will look at forward chaining in more detail, and we will see that forward and backward chaining rules are not as different as they may first appear. Then we will look at how forward and backward chaining are integrated in modern systems.

As we discussed, the difference between forward and backward chaining boils down to just two points:

1. Forward-chaining systems fire rules whenever the rules' If parts are satisfied. Backward-chaining systems attempt to fire rules only when those rules can potentially satisfy a goal.
2. Backward-chaining systems automatically create new subgoals when more information is needed to determine whether a given rule is satisfied. Forward-chaining systems do not automatically create subgoals.

Some discussions of forward chaining systems go beyond these two points to give a very misleading characterization of forward chaining systems. The usual statement is something like, "Forward chaining systems start with the facts about the situation and proceed to compute every conclusion that can be made based on those facts." I have to say I have never seen a system of any size that operates that way. Just as backward chaining systems do, forward chaining systems use goals to control which rules may fire at a given time. The only difference is that the goals are created explicitly by the rules in a forward chaining system.

Working with goals in a forward chaining system is actually quite simple. As was explained in the last column, forward chaining rules operate on an in-core data base of objects usually called the system's working memory. This working memory can contain not only facts about the problem situation, but goals as well. For instance, the data base can contain not only facts such as
Chest C1 is locked.
But also goals such as Goal:
Unlock Chest C1.
The If parts of the rules in a forward chaining system generally specify both a goal that they can satisfy (or help to satisfy) and the facts about the problem that the rule needs. For instance, there might be a rule in a system that says

In this article we are going to use a very abstract representation for working memory objects as well as the rules that operate on them. In later articles we can get objects and rules in actual systems look like.

IF
The current goal is Open Chest x, and Chest x is locked THEN
Create Goal: Unlock Chest x.

In general, most of the rules in a system that is organized this way will take one of two formats. The first is rules to create subgoals, like the one we just saw:

IF
The current goal is Goal1, and
Fact1, and
Fact2, and
. . .
FactN THEN
Create the goal Goal2.

The second format is for the rules that "really" do something (i.e., rules that don't just create goals for other rules):

IF
The current goal is Goal3, and
Fact1, and
Fact2, and
. . .
FactN THEN
Change fact Factw, and
Change fact Factx, and
. . .
Delete goal Goal3.

We might call the second form of rules, "action" rules and the first form of rules "subgoaling" rules. In short, action rules make the changes to the state of the world that are required to solve the problem, while subgoaling rules insure that all the facts required by the action rules are available.

You might ask why you would want to use a forward chaining system if you have to write rules to manage subgoals. After all, backward chaining systems automatically manage the subgoals. There answer is very simple: Backward chaining systems are more limited than forward chaining systems. There are many kinds of tasks that can be handled easily with a forward chaining system that are either difficult or impossible with a backward chaining system. Backward chaining systems are good for diagnostic and classification tasks, but they are not good for planning, design, process monitoring, and quite a few other tasks. Forward chaining systems can handle all these tasks.

But the fact remains that when backward chaining is applicable, it is certainly easier to use. The ideal would be to use backward chaining where it could be used, and forward chaining elsewhere. For instance, a medical system might use backward chaining to diagnose an illness, and then use forward chaining to design a course of treatment. Modern rule based systems provide both forward and backward chaining capabilities in a single system. The RulesPower system, for instance, is primarily a forward chaining system, but it can invoke automatic backward chaining to create the preconditions needed by the forward chaining rules. That is, you can avoid writing many (perhaps all) of the subgoaling rules needed by a strictly forward chaining system.

The way automatic backward chaining works is quite simple. Consider again the action rule from above:

IF
The current goal is Goal3, and
Fact1, and
Fact2, and
. . .
FactN THEN
Change fact Factw, and
Change fact Factx, and
. . .
Delete goal Goal3.

All the developer needs to do is to indicate which conditions in the rule should be handled by automatic back chaining. For example, in this rule, if all the facts are to be handled by back chaining, the developer might write something like

IF
The current goal is Goal3, and
Can establish Fact1, and
Can establish Fact2, and
. . .
Can establish FactN THEN
Change fact Factw, and
Change fact Factx, and
. . .
Delete goal Goal3.

When the rule interpRETEr processes this If part, if it finds that a certain fact is not available, it automatically creates a goal object and puts it into working memory. For instance, if Fact1 was available and Fact2 was not, the system would behave as if the following rule was in the system:

IF
The current goal is Goal3, and
Fact1, and
NOT Fact2, and THEN
Create Goal: Achieve Fact2.

In short, the system behaves as if there were subgoaling rules for each of the facts. (Though the rules are not actually present in the system, which makes the system smaller and more efficient.)

In conclusion, forward and backward chaining systems both use subgoals to control the operation of a rule base. Pure forward chaining systems are more powerful than pure backward chaining systems, but pure forward chaining systems require the developer to write all the subgoaling rules. Modern forward chaining systems such as the RulesPower system integrate automatic backward chaining with forward chaining. These systems combine the best features of both forward and backward chaining.

This column looks in detail at the topic we discussed in general in the last column: How primarily forward-chaining production systems can provide support for backward chaining. We are going to look at two real systems: JESS and OPSJ. It is interesting to compare these systems because they provide essentially the same functionality, but they do so using rather different designs.

Here is the problem we are going to consider: Suppose we are implementing an on-line order processing system, and that we are writing the rules to determine how much of a discount, if any, to give each customer based on these business rules:

R1. If the total price is >= $100.00 and < $1000.00, give a discount based on the following schedule:

Gold customers: 5%.

Silver customers: 3%.

All other customers: 0%.



R2. If the total price is >= $1000.00, give a discount based on the following schedule:

Gold customers: 7%.

Silver customers: 5%.

Bronze customers: 3%.

All other customers: 0%.



Suppose we will not know whether the customer is Gold, Silver, etc. unless we execute a time-consuming database access.

In a pure forward chaining system, we have two choices about how to implement these rules:

1. We can always determine the customer's class before deciding how big a discount to give.
2. We can check the total price first, and only determine the customer's class if the total price is at least $100.00.

Neither of these options is too attractive. The first will cause the system to perform unnecessary database accesses on many orders. The second will avoid the unnecessary database accesses, but it will complicate the rules and make the mapping between the business rules and the implementation rules less clear than it might be.

As will be illustrated below, backward chaining will enable the system to avoid the unnecessary database accesses while keeping a natural mapping between the business rules and the implementation rules.

Representing Attributes of Objects

Before describing how the systems implement backward chaining, we need to spend a few minutes on the more basic topic of how attributes of objects are represented in rule based systems. Two basic methods are used: The first is to use objects like those that would be used in Java or any other object-oriented programming language. For example, a Customer might be represented as an instance of a class like this:

public class Customer

{

public int mIdNumber;

public String mName;

public String mClass;

. . .

}



The other basic method for representing attributes is to put each attribute and value into a separate fact object. For instance, if the customer with IdNumber 1009 was named "John Smith" and had class "Bronze" the facts representing the customer might be

(isa 1009 Customer)

(name 1009 "John Smith")

(class 1009 "Bronze")

.. . .



It should be noted that it is possible to combine these two representations to put some information into a class like Customer, and other information into separate fact objects.

Backward Chaining in Jess

In JESS, backward chaining is performed on facts representing individual attributes, so rule R2 from above might be implemented as:

(defrule R2JESS

;; If the current task is to compute the discount

;; for order number ?ord and customer ?cust

(Task (name ComputeDiscount)

(order ?ord)

(customer ?cust))

;; And order ?ord is for at least $1000.00

(Order (number ?ord)

(amount ?amt & :(>= ?amt 1000.0)))

;; And the class of the customer is known

;; (Backward chain if necessary)

(class ?cust ?cls)

=>

;; Then apply the appropriate discount . . .

)



When JESS processes the above rule, if the class of the customer is known, the rule is executed as a standard forward chaining rule. However, if JESS determines that there is no object in working memory that matches the class condition it will automatically generate a goal to determine the class. The goal object looks like the object that this condition would match except that "class" is replaced with "need-class." If this is customer 1009, the created goal is

(need-class 1009 nil)



Of course JESS does not backward chain on every condition that fails. So, how did it know that it was supposed to backward chain on the "class" condition? The answer is that a declaration has to be made before the rule is entered. The definition in this case is

(do-backward-chaining class)



This says that all class conditions are to be considered by default subject to backward chaining. It may happen that in some rules backward chaining is inappropriate. In those rules backward chaining can be turned off by using the keyword explicit. That is, the condition

(explicit (class ?cust ?cls))



will not result in backward chaining, while the condition in R2JESS will.

Backward Chaining in OPSJ

In OPSJ, backward chaining is performed on specific attributes of regular objects. So, instead of using a separate fact like

(class 1009 "Bronze")



in an OPSJ program the class value would be held in a member field of the Customer object. Rule R2 could be written in OPSJ like this:

rule R2OPSJ

if {

// The current task is to compute a discount

t: Task (t.mName == "ComputeDiscount");

// And the order is for at least $1000.00

ord: Order (ord.mNumber == t.mOrder,

ord.mAmount >= 1000.0);

// And the class of the customer is known

// (Backward chain if necessary)

c: Customer(c.mIdNumber == t.mCustomer);

need (c.mClass != null);

} do {

// Apply the appropriate discount . . .

}



In OPSJ, conditions where backward chaining may be needed are marked with the keyword "need." The above rule says to use backward chaining on the mClass member of Customer c if its value is not currently known (or more specifically, if it has not been changed from its default value of null). So, when this rule is processed, if mClass is known, the rule behaves as a standard forward chaining rule. If mClass is not known, OPSJ causes a goal to be created to determine mClass.
Discussion

Both JESS and OPSJ allow us to do what we needed to do: To implement the business rules directly and yet insure that the database accesses are not performed unnecessarily. However, there are some interesting differences between the two languages:

* JESS performs backward chaining on attributes represented as separate facts. OPSJ performs backward chaining on member attributes of standard objects.
* In JESS a particular attribute can be declared to be backward chained, and the system will always backward chain on that attribute unless the keyword "explicit" is used to locally disable backward chaining. In OPSJ there are no global backward chaining declarations, and the system performs backward chaining only when the keyword "need" is used to locally enable backward chaining.

begin:vcard
fn:Peter Van Weert
n:Van Weert;Peter
org:K.U.Leuven;Computer Science
adr:room 01.08;;Celestijnenlaan 200A;Heverlee;;3001;Belgium
email;internet:Peter.VanWeert@xxxxxxxxxxxxxx
title:DTAI (Declarative Languages and Artificial Intelligence)
tel;work:+ 32 16 327064
x-mozilla-html:TRUE
url:http://www.cs.kuleuven.be/~petervw/
version:2.1
end:vcard

Relevant Pages

  • Re: Damn you, FEDEX! or Nikon D40 lost in Springfield, MO blackhole.
    ... the 2 mp Mavica he had been using with a Nikon D40. ... After shopping around, he got me to order one for him. ... The shipper had it insured, but from what I have read it could take weeks to sort this crap out. ... You may get your insurance from FedEx and a couple weeks later they find it and deliver it. ...
    (alt.photography)
  • Re: A Cars velocity
    ... If by instantaneously you mean Zero, infinite acceleration is required ... How much money do you have for the speedometer design phase? ...
    (sci.physics)
  • simple expert system
    ... Does anybody know where I can find a few code-examples for a simple expert ... system (written in Prolog), which uses forward and backward chaining... ...
    (comp.lang.prolog)
  • Re: The Sci-Fi Rejection Letter That Time Forgot
    ... nations have stockpiled arsenals of these incredible bombs and the time the story is set. ...
    (rec.arts.sf.written)
  • RE: copied music cds have a skip in last 18 seconds
    ... If installing all missing Windows Updates doesn't fix your problem ... xiowan.......in tucson ...
    (microsoft.public.windows.mediacenter)