logicrelationshipclipsexpert-systemancestry

CLIPS(recursion) - family relations: how to implement correctly the relation of being an ancestor?


Introduction

I am trying to implement a rule in CLIPS language - the relation that a person is an ancestor of other person. The constraint is that such rule must be derived only from the following premises:

(male ?x) ("x is a male")

(female ?y) ("y is a female")

(mother-of ?x ?y) ("x is a mother of y")

(father-of ?x ?y) ("x is a father of y")

My attempt

I wrote the following code:

    (deftemplate father-of 
        (slot father)
        (slot child)
    )

    (deftemplate mother-of 
        (slot mother)
        (slot child)
    )

    (deftemplate male 
        (slot person)
    )

    (deftemplate female
         (slot person)
    )

    (deffacts family
        (father-of (father John) (child Mark))
        (father-of (father John) (child Mary))
        (mother-of (mother Alice) (child Mark))
        (mother-of (mother Alice) (child Mary))
        (male (person John))
        (male (person Mark))
        (female (person Alice))
        (female (person Mary))
    )

    (defrule ancestor
    (or 

        (mother-of (mother ?x) (child ?w))
        (father-of (father ?x) (child ?w))


        (and
            (mother-of (mother ?x) (child ?y))
            (or
                (mother-of (mother ?y) (child ?w))
                (father-of (father ?y) (child ?w))  
            )
        )

        (and
            (father-of (father ?x) (child ?y))
            (or
                (mother-of (mother ?y) (child ?w))
                (father-of (father ?y) (child ?w))  
            )
        )
    )
    =>
    (printout t ?x " is an ancestor of " ?w crlf) 
    (assert (ancestor ?x ?w))   
)

The gist of the problem

The above code compiles and returns "true"(in other words, the construced rule is logically correct) and outputs expected results in the case of such list of facts.

However, there is a subtle problem:

This codes works for determining first and second generation of ancestors only.

In other words, it works only in the case if someone is a father/mother of someone or a grandfather/grandmother of someone, but not for checking if someone is a great grandfather/great grandmother or great great grandfather/great great grandmother of someone, etc.

The above code does not handle this issue.

How to overcome this problem?


Solution

  • CLIPS> 
    (deftemplate father-of 
       (slot father)
       (slot child))
    CLIPS> 
    (deftemplate mother-of 
       (slot mother)
       (slot child))
    CLIPS> 
    (deffacts family
       (father-of (father Bob) (child Frank))
       (mother-of (mother Linda) (child Frank))
       (father-of (father Frank) (child John))
       (mother-of (mother Susan) (child John))
       (father-of (father John) (child Mark))
       (mother-of (mother Alice) (child Mark)))
    CLIPS> 
    (defrule ancestor
       (or (mother-of (mother ?x) (child ?w))
           (father-of (father ?x) (child ?w))
           (and (ancestor ?x ?y)
                (ancestor ?y ?w)))
       (not (ancestor ?x ?w))
       =>
       (printout t ?x " is an ancestor of " ?w crlf) 
       (assert (ancestor ?x ?w)))
    CLIPS> (reset)
    CLIPS> (run)
    Alice is an ancestor of Mark
    John is an ancestor of Mark
    Susan is an ancestor of John
    Susan is an ancestor of Mark
    Frank is an ancestor of John
    Frank is an ancestor of Mark
    Linda is an ancestor of Frank
    Linda is an ancestor of Mark
    Linda is an ancestor of John
    Bob is an ancestor of Frank
    Bob is an ancestor of Mark
    Bob is an ancestor of John
    CLIPS>