Donnerstag, 18. Oktober 2012

Petri-Net Taxonomy Reasoner

Petri nets (and Hierarchical Colored Petri nets [1] (HCPNs) in particular) are mathematically well-formed models which are based on an executable formalism. My tool of choice for working on HCPNs is "CPN Tools" [2].
However, you may even represent knowledge in HCPNs in forms of flattened graphs. I'll show you how a relatively simple taxonomy, which (in this case) is actually nothing more than a directed acyclic graph (DAG), is transformed into a data structure usable by the CPN ML language used in HCPNs to define color sets (data types), functions, and so on.
This allows us to create reasoners with which we can either learn additional things (add nodes to the taxonomy graph) or answer queries on this knowledge (i.e. actually applying some graph-algorithm and compute (parts of) the transitive closure or just single paths).

But enough chitchat for now, let's get down to business. In the following picture you can see the simple example taxonomy:
A simple taxonomy as a DAG created using yEd [3]

As you might see, the Is-A relationships are in reverse direction (the automatic layout of yEd would not allow the "correct" direction) but this is just a cosmetic issue. Anyways, what you can see is, that we defined the concepts (or classes) "Thing", "Animal", etc. and what it means is that "an animal is a thing" and so on (again, intention is reverse to edges' direction...). This is quite like a class inheritance tree as it is common to software technologists.

A short recall: we'd like to use such a graph as knowledge in an HCPN in order to reason about this knowledge.

CPN ML (a variant of SML/NJ) does not support hierarchical data structures (compare to the composite design pattern). [Edit:] Actually, CPN ML and SML/NJ DO support datatypes, which are inherently recursive. However, they cannot be used as colors in an HCPN, so this is out of the question [Thanks and credits to Michael Westergaard].
Thus, we must flatten this taxonomy graph into a list so that we can process it (feel free to tell me when there's a better solution).
I therefor wrote an eclipse plug-in with which you can comfortably do the conversion between a yEd's graphml file and an appropriate CPN ML list-style graph representation, which looks like:

val initial_knowledge = [

initial_knowledge is the list variable, p is the parent node, c is the actual node (i called it child...) anda is a list of attributes (key/value pairs).

Now let's see the Petri net (I'll post a link later under which you can find the plug-in and net)...

Please note: wherever there's "ontology" in the nets, replace it with "knowledge"...

In the middle bottom there is the large green rectangle which shows the (initial) knowledge, while in the top left there are three "queries" on this knowledge, which we can interpret as

1) is Anthony a Mammal?
2) is NAO a Robot?
3) is Sebastian a Robot?

And let's see what happens when we fire the transitions:

The transition chose query 2 and it is about to be answered...

When place "Accepted?" receives the query token (instead of an "empty" token) then this query was accepted, which can be interpreted as "the assertion is true".
Accordingly, query 3 should result in an "empty" token, since "Sebastian" is not a "Robot" in our knowledge (we skipped query 1 here, which is also accepted):

And the result:

Finally, let's have a look at the function which does all the work: accept ( ruleTest, ont ):

fun accept ( rt:RuleTest, []:Knowledge ) : BOOL
= true
| accept ( rt:RuleTest, know:Knowledge ) : BOOL
= testRule(#r rt, hd know) orelse runFold(rt, know);

As a shorthand, when we have no knowledge (empty list) just accept the RuleTest. Otherwise, look whether the searched pair is the root itself (another shorthand) or, otherwise, call runFold, which is explained further down.

The color sets used are:

colset ATTR_VAL = record k:STRING * v:STRING;
colset ATTR_LIST = list ATTR_VAL;
colset Rule = record p:STRING * c:STRING * a:ATTR_LIST;
colset Knowledge = list Rule;
colset RuleTest = record r:Rule * id:INT;

A Rule is actually a node in our flattened/serialized tree which knows about its parent's name (p) its own name (c) and has a list of attributes (a), whereas each attribute is a key/value pair. The attributes denote further knowledge about the node itself and could be used to store attributes of the edge (relationship) between the node and its parent, but, of course, you could also extend colorset Rule to have a second attribute list (to clearly separate the node's and the edge's attributes).

Variables (denoted by var) and the constant (denoted by val):
var rule,rule1,rule2,toLearn : Rule;
val emptyRule = {p="",c="",a=[]};
var ruleTest : RuleTest;
var parent,child,key,value,p1,c1 : STRING;
var id : INT;
var ont : Ontology;

Here's not much to say, except that we use emptyRuleas the constant for differentiating between an accepted and a rejected rule test/query.

The other functions needed:

fun runFold ( rt:RuleTest, know : Knowledge ) : BOOL
= #found (foldr foldRule {r=(#r rt),found=false} know);

fun foldRule ( rule:Rule, test:FoldRuleInput ) : FoldRuleInput
= if ((#found test) orelse (#c rule <> #c (#r test)))
then test (*search finished or continue search*)
else (if (#p rule = #p (#r test))
  then {r=(#r test),found=true} (*found*)
  else {r={p=(#p(#r test)),c=(#p know),a=(#a(#r test))},found=false} (*traverse upwards*)

So, here we have runFold which I introduced earlier. What this function actually does is traversing the serialized tree bottom-up (from leaf to root). Therefor it uses the SML function foldr and you could use foldl to go top-down.

I'll leave the rest to you and look forward to your comments, questions, and suggestions.

You find the sources under:
Search the trunk for "HCPN-Taxonomy-Reasoner".

[1] {Jensen, Kurt and Kristensen, Lars  M.} {Coloured Petri Nets} {2009}

Keine Kommentare:

Kommentar veröffentlichen