Prudens

Contents

Introduction

Suppose you own one of these robot vacuum cleaners and that you can interact with it in order to train it to behave as you wish. Moreover, suppose that once you charge and set to action your robot vacuum cleaner for the first time, you give it the following command:

"Clean all the house every day at 7 PM!"

Now, let us suppose that it is Sunday afternoon, 6:59 PM and that you are relaxing. Suddenly, you hear an annoying sound coming from the living room; it is the robot vacuum cleaner that has just started cleaning. It doesn't take you long to realise that you should make some adjustments to your cleaner's settings. Consequently, you get up, go to your living room and give the following command to your tirelessly obedient cleaner:

"Do not clean the house at 7 PM on Sundays! Instead, wait for me to tell you when to start cleaning on Sundays!""

In the above, you have just provided your automated cleaner with an exception to its generic "Clean the house every day at 7 PM!" policy. Proceeding in this way, you may find more circumstances in which you would like your cleaner to deviate from its previous policy and temporarily adopt some other behaviour.

Situations like the one described above, where a human coaches a machine in order to accomplish some certain tasks are captured by Machine Coaching (MC) (see here for more). In short, MC is an iterative human-machine interaction process through which a human can transfer knowledge to an agent who, in turn, acts based on it and returns explanations in the form of arguments constructed from its accumulated knowledge. Given the machine's feedback, the user may provide some input in the form of some counter-argument, in order to update the agent's knowledge. MC is implemented by Prudens, a tool that allows human users to iteratively train their own agents, in a fashion similar to the one described above.

The Language of Prudens

Since MC offers a means of communication between humans and machines, it is natural that there should exist some common language through which knowledge is transferred from the human end-user to the machine agent and vice-versa. In this section we will describe the syntax and the semantics of this language as well as provide numerous examples clarifying its features.

Predicates, variables and constants

At some extent, Prudens's language shares several common features with prolog. To begin with, Prudens's language allows for predicates to be used to denote relations between entities of the universe. Syntactically, each predicate consists of two parts:

  1. its name, which starts with a lower-case letter of the English alphabet (a-z) which may be followed by any finite sequence of letters (a-z, A-Z), digits (0-9) and underscores (_), and;
  2. its list of arguments, which follows its name separated by no other character and consists of a comma-separated list of arguments enclosed in left and right parentheses.

So, the syntactical form of a predicate is the following: 

name(arg1,arg2,...,argn)

We will refer to the (fixed) number, n, of arguments appearing in a predicate's arguments list as the predicate's arity and we will also refer to a predicate of arity n as an n-ary predicate.

Regarding a predicate's arguments, they are restricted to be either constants or variables or valid mathematical expressions — validity is decided based on ECMAScript 6 syntax. Constants are intended to be interpreted as specific entities of our universe while variables serve as placeholders for constants. In Prudens's language, constants are represented by strings which start with a lower-case letter (a-z) which may be followed by any finite sequence of letters (a-z, A-Z), digits (0-9) and underscores (_) — exactly as with a predicate's name. On the other hand, variables are represented by string which starts with an upper-case letter (A-Z) which may again be followed by any finite sequence of letters (a-z, A-Z), digits (0-9) and underscores (_). So, for instance, the following: 

fatherOf(X,bob)

is a binary predicate symbol, fatherOf(·,·), with an arguments list consisting of a variable, X, and a constant, bob. In case we interpret fatherOf(X,Y) as "X is the father of Y" and assume that there exists some entity named Bob in our universe, then the above may be interpreted as "Someone (X) is the father of Bob".

We should remark at this point that a predicate's arity might well be zero. In this case, the predicate is treated as a propositional symbol, being either true or false, regardless of the assignment of any variables. Thus, Prudens's language supports both relational (first-order) as well as propositional policies, as we shall see next.

Proceeding with predicates' syntax, Prudens also allows for two types of special predicates:

  • action predicates, whose name is preceded by an exclamation mark (!), such as !brotherOf(X,bob) and;
  • custom predicates, whose name is preceded by a question mark (?), such as ?custom(X,Y,Z).

Action predicates are used, if needed, to distinguish between actions that an agent should take and other intermediate inferences. Custom predicates, on the other hand, are references to Boolean functions implemented by the developer — more on this here.

Lastly, we should mention at this point that Prudens's language has a special built-in predicate, ?=(·,·), which serves as an extended unification and equality predicate. Prior to explaining the various capabilities of ?=(·,·), we shall provide an example. Consider the following policy: 

@KnowledgeBase
                                    R1 :: siblingOf(bob,Y), ?=(Y,alice) implies olderSibling(Y);

Given the following context:

siblingOf(bob, charlie); siblingOf(bob, alice); siblingOf(bob, david);

we may infer: olderSibling(alice). Essentially, ?=(·,·) checks whether its two arguments unify and, if so, it unifies them.

As one may suspect, ?=(·,·) may also be negated. So, if instead of the above policy we use the following one: 

@KnowledgeBase
                                    R1 :: siblingOf(bob,Y), -?=(Y,alice) implies brotherOf(bob, Y);

using the same context we infer: 

brotherOf(bob, charlie); brotherOf(bob, david);

We shall remark that any variable mentioned within the arguments of the equality predicate should be also referenced by at least one other predicate in the same rule's body or as a free variable within the context — for more, see here. Lastly, ?=(·,·) may be used to perform mathematical operations, as we discuss here.

Policies, contexts and inference

All predicates may be negated by appending a dash (-) in front of them. A literal is either a predicate or its negation. Two literals that stem from the same predicate but have conflicting signs (i.e., the one is the predicate itself while the other is its negation) are conflicting. Literals, as we shall see, are the building blocks of policies in Prudens. Examples of literals are the following ones: 

fatherOf(X,bob), -fatherOf(Y,alice)

Utilizing literals, rules are defined as a string of the following form: 

name :: body implies head;

So, each rules consists of:

  1. a name, which is a string separated by :: from the rule's main part;
  2. a body, which is a comma-separated list of literals and;
  3. a head, which is a single literal separated from the rule's body by the implies keyword.

Intuitively, each rule is interpreted as an IF-body-THEN-head inference. So, for instance, the following rule, where all predicates have the obviously intended interpretation is interpreted as "Any two people having the same mother are siblings": 

R1 ::\ motherOf(X,Z), motherOf(Y,Z) implies siblings(X,Y);

Two rules with conflicting literals as heads are conflicting. A policy is a set of rules (conflicting or not) alongside an order relation defined over all pairs of conflicting rules. By default, Prudens assumes that priorities are determined by the order of appearance of rules in the policy (the later a rule appears, the higher its priority over conflicting ones). For instance, the following is an example of a policy: 

@KnowledgeBase}
                                    R1 :: bird(X) implies flies(X);
                                    R2 :: penguin(X) implies bird(X);
                                    R3 :: penguin(X) implies -flies(X);

where R3 is of higher priority than R1, since it appears later on in the policy. The @KnowledgeBase decorator above all rules is a keyword of Prudens's language, used to indicate where the policy's rules start.

Policies, intuitively, are an abstraction of the agent's behavior under several circumstances. These circumstances within MC are called contexts and are actually sets of pairwise non conflicting literals. So, for instance, the following is a context: 

penguin(bob);

According to it, an entity of our universe, bob, is a penguin. Given the above policy, we can infer various things about bob. Namely:

  1. Initially, only knowing that bob is a penguin, we infer from rule R2 that bob is a bird and from R3 that it cannot fly.
  2. Knowing now that bob is also a bird, we could infer, through R1, that is can fly. However, since R3 is of higher priority than R1, we do not infer that bob flies.

So, eventually, given the above context and policy, we infer that bob is a bird that cannot fly.

Defining custom predicates

As we have already discussed here, one may also define their own custom predicates. Such predicates are JavaScript Boolean functions, and are declared under the @Code decorator, as in the example shown below: 

@KnowledgeBase
                                    R1 ::\ heightOf(X, H), ?isWithinLimits(H) implies accept(X);
                                    
                                    @Code
                                    function isWithinLimits(x) {
                                        const xFloat = parseFloat(x);
                                        return xFloat > 170 \&\& xFloat < 190;
                                    }

There are several points that we should highlight regarding the syntax of custom predicates:

  1. @KnowledgeBase should always appear above @Code.
  2. When references in a policy rule, under the @KnowledgeBase decorator, the custom predicate's name should be preceded by a ?. On the contrary, this is not the case when the custom predicate itself is declared as a JavaScript function under the @Code decorator, since this would be invalid JavaScript syntax.
  3. All code following the @Code decorator should be valid under the ECMAScript 6 specifications.
  4. All JavaScript functions defining custom predicates should return some Boolean value. If this is not the case, any returned value is interpreted as a Boolean value according to ECMAScript 6 specifications — more on what is true in ECMAScript 6 here.
  5. No function calls are allowed within any of the functions defined under the @Code decorator. That is, any function defined below @Code should correspond to some custom predicate, otherwise it is cannot be utilized as an auxiliary function.
  6. All arguments in a function defined under @Code are considered to be strings. That is, in case a predicate's arguments are intended to be floats, you need to use parseFloat as above, or parseInt, in case they are supposed to be integers. More on these two functions may be found here and here respectively.

Mathematical operations

Prudens supports mathematical operations under certain conditions. To begin with, as mentioned in here, ?=(·,·) may be used for mathematical operations within its arguments, provided that they do not invoke any variables that remain unassigned once the rule is triggered. So, a rule like: 

R1 :: f(X), ?=(Y, X+3) implies g(Y);

with a context containing f(2) would infer g(5). However, using: 

R2 :: f(X), ?=(Y-3, X) implies g(Y);

with the same context would not, since there is no value assigned to Y by the time the rule is invoked. Any mathematical expressions within ?=(·,·) should adhere to the usual ECMAScript 6 syntax.

Prudens's language also allows for math operations to be executed within any predicate, given the restrictions mentioned above, about unassigned variables. Similarly to the equality predicate, numerical operations may not be used in head literals. For instance, the following rule: 

R1 ::\ f(X, 2*X) implies double;

given a context containing f(2,4) infers double. An equivalent rule, avoiding within-predicate operations, would be: 

R2 ::\ f(X, Y), ?=(Y, 2*X) implies double;

which, however, introduces an additional variable, Y, and leads to slightly slower processing time. Thus, whenever possible, within-predicate math operations should be preferred against ?=(·,·).

Custom Priorities and Dilemmas

Rule priorities are by default determined by order of appearance within a policy. However, one may define custom priorities as well. In fact, this can be done in two ways: programmatically, by providing a priority function as an optional argument to the Prudens's core reasoning function — for more, see here — and; syntactically, by providing priorities explicitly within each rule's declaration. Regarding syntactic priority manipulation, the language's "vanilla" rule syntax is extended to allow for priorities to be declared through integers following a rule's head, separated by a |, as follows: 

name ::\ body implies head | priority;

There, numbers indicate priority, with negative values being allowed as well. So, given a context containing a; b;, the following policy would yield z, since R1 is preferred over R2. 

@KnowledgeBase
                                    R1 :: a implies z | 1;
                                    R2 :: b implies -z | 0;

Naturally, allowing for custom priorities, there might be cases where two rules are incomparable, either because no priority between them has been explicitly determined or because they are of the same priority, as with the following policy: 

@KnowledgeBase
                                    R1 :: a implies z | 1;
                                    R2 :: b implies -z | 1;

Such cases are called dilemmas. Since there is no clear way to resolve a dilemma, the reasoning engine abstains from making a decision, ignoring both rules and proceeding with the reasoning process. Any dilemmas encountered throughout a reasoning cycle are noted and returned separately from the rest inferences.

Ungrounded Contexts

Literals in a context may be partially or even totally ungrounded. That is, a context may well contain literals like f(Y), even if Y is a free variable. In any such case, variables propagate throughout inferences, unifying with other variables whenever it makes sense. For instance consider the following policy: 

@KnowledgeBase
                                    R1 :: f(A), g(X) implies h(X,A);

Using the left one with a context containing f(Y); g(3); one infers h(3,Y). Note at this point that any unassigned context variables are not distinguished from policy variables in case they bear the same name. So, having f(X) in our context instead of f(Y), would lead to inferring h(3,3), since X is a variable that also appears in R1, substituted by 3. Using a context containing f(Y) with the policy shown below, this time, we could infer z(3). 

@KnowledgeBase
                                    R1 :: f(A), g(X) implies h(X,A);
                                    R2 :: h(X,b) implies z(X);

Extended Conflict Semantics

In the vanilla version of the language, two literals are considered conflicting in case they stem from the same predicate but have opposite signs. Prudens's language, however, also allows for rules that determine broader conflicts between arbitrary predicates. Such rules are called compatibility constraints and adhere to the following syntax: 

ruleName ::\ pred1 \# pred2;

So, for instance, using the policy shown below and a context containing a; b;, one infers y, since C1 declares y and x as conflicting literals. 

@KnowledgeBase
                                    R1 :: a implies x;
                                    R2 :: b implies y;
                                    
                                    C1 :: x \# y;

Note at this point that there are assumed no priorities between compatibility constraints, opposed to what is the case with the rest rules in a policy.

Reasoning

Having presented the language of Prudens in detail, we shall now shed more light on how Prudens "thinks".

Simple Forward Reasoning

The ground upon which Prudens's reasoning algorithm relies is a simple forward reasoning process. For instance, let us consider the following policy: 

@KnowledgeBase
                                    R1 :: a implies x;
                                    R2 :: b, c implies y;
                                    R3 :: x, y implies z;

Given a context containing a; b; c;, we can infer all x, y and z. The exact way this is conducted is presented below:

  • Consider a list, ℓ, initially containing all facts that are contained in our context; namely, a, b and c;
  • Given these facts, rules R1 and R2 fire, allowing us to infer x and y and, consequently, add them to ℓ;
  • Now, knowing x and y, rule R3 fires as well, allowing us to infer z and append it to ℓ;
  • Given that no other inferences may be drawn given our currently known facts and rules, the process terminates.

Essentially, we apply all known and applicable rules, trying to infer new facts and repeat until nothing new may be inferred.

While all rules in the above example were purely propositional, the same applies to relational policies like the one shown below: 

@KnowledgeBase
                                    R1 :: parentOf(X, Z), parentOf(Y, Z) implies siblings(X, Y);
                                    R2 :: siblings(X, Y), ageOf(X, Age1), ageOf(Y, Age2), ?=(Age1, Age2) implies twins(X, Y);

Given a context containing the following: 

parentOf(alice,charlie); parentOf(bob,charlie); ageOf(alice,23), ageOf(bob,23);

one may infer the following: 

siblings(alice,alice); siblings(alice,bob); siblings(bob,alice); siblings(bob,bob); twins(alice,alice); twins(alice,bob); twins(bob,alice); twins(bob,bob);

Quite messy, right? As you may observe, there are several quite trivial facts that Prudens has inferred above, like: 

siblings(alice,alice); siblings(bob,bob); twins(alice,alice); twins(bob,bob);

To shed more light on it, we shall expose some of Prudens's internal reasoning:

  • At first, since we know parentOf(alice, charlie) and parentOf(bob, charlie), rule R1 fires, so, all possible substitutions to its body's variables, X, Y, and Z, are generated, by unifying all body literals with those in the context:
    • X→alice, Y→alice, Z→charlie;
    • X→alice, Y→bob, Z→charlie;
    • X→bob, Y→alice, Z→charlie;
    • X→bob, Y→bob, Z→charlie;
  • For each one of the above substitutions, the corresponding inference is drawn:
    • siblings(alice, alice);
    • siblings(alice, bob);
    • siblings(bob, alice);
    • siblings(bob, bob);

Similarly, Prudens proceeds with the rest of the process, inferring the rest of the facts presented above.

Introducing Exceptions

So far, we have presented some simple examples of forward reasoning, were from some facts, given a set of rules, we infer some new facts and then we iterate until we have exhausted what we could learn from the above. However, what makes Prudens really powerful, is its ability to handle conflicts between rules. Consider, for example, the following policy: 

@KnowledgeBase
                                    R1 :: a implies z;
                                    R2 :: a, b implies -z;

Given a context containing only a, rule R1 fires, yielding z. However, if our context also contained b, then both R1 and R2 would fire, inferring z and -z at the same time. In this case, -z would survive and z would be rejected, since Prudens silently assumes that the later a rule appears within the same policy, the higher its priority in case of conflicts.

As a more complex example, consider the following policy: 

@KnowledgeBase
                                    R1 :: a implies x;
                                    R2 :: a, b implies y;
                                    R3 :: a, x implies -y;

In this case, a context containing a> and b would lead us infer x and -y, as follows:

  • At first, knowing a and b, R1 and R2 fire, allowing us to infer x and y;
  • Knowing x, rule R3 fires, leading to -y, which conflicts with y. This conflict is resolved by preferring -y over y, since the former was inferred by R3, which is of higher priority than R2.
  • Having inferred x and -y, nothing more may be inferred, so the process terminates.

Let us also consider a first-order policy containing conflicts: 

@KnowledgeBase
                                    R1 :: f(X) implies z(X);
                                    R2 :: f(X), g(X, 4) implies -z(X);

In this case, having a context containing f(1); f(2); g(1,4); we might infer z(2) and -z(1), since:

  • f(1) and g(1,4) trigger both R1 and R2 and R2 is of higher priority than R1 but;
  • f(2) triggers R1 and there is nothing like g(2,4) to trigger R2 in this case.

Dilemmas

So far, we have referred to dilemmas as those cases when no priority has been determined between two conflicting rules. In such cases, Prudens abstains from making any inference, noting down the dilemma and proceeding with the rest of the reasoning process. To shed more light on that, let us revisit a policy we used above: 

@KnowledgeBase
                                    R1 :: a implies x;
                                    R2 :: a, b implies y | 1;
                                    R3 :: a, x implies -y | 1;

We have explicitly stated that R2 and R3 are of the same priority. So, with a context containing a and b, we get nothing more than x in this case. Indeed, this time, the reasoning process goes as follows:

  • At first, knowing a and b, R1 and R2 fire, allowing us to infer x and y;
  • Knowing x, rule R3 fires, leading to -y, which conflicts with y. This conflict remains unresolved, since R2 and R3 are of the same priority, so y is removed from the known facts list;
  • Since there is nothing more to infer, the algorithm terminates.