Beliefs and Inference

This section explores how logic is represented in ASTRA, and how to use beliefs, logical expressions and inference rules within your programs.

How to model some knowledge as a belief

Beliefs are used to represent and query the state of the agent. Traditionally, in AOP, beliefs are defined as representing facts or knowledge about the agent or its environment. For example, if an agent is playing soccer, then it may have a belief about whether or not it sees the ball. This could be modelling in ASTRA by the belief:

seeBall()

This is a perfectly valid way of representing the knowledge, but is really an example of propositional logic thinking being applied to predicate logic (this is a quite common mistake, and I am sure you can spot examples of this in the ASTRA documentation). While the above belief is syntactically correct, it is not really following the spirit of predicate logic. In predicate logic, facts (like the above belief) are viewed as defining relationships between objects in the world of discourse. What this means is that the fact should include an object that the agent is aware of (like the ball) and the predicate should define a relation that can be applied to the ball (for example, whether or not you can see the ball). So, the above belief would be better modelled as follows:

see(ball)

Here, ball is a term that represents an object in the universe of discourse, and see is a relation defined on that object.

The problem is that, the ball object is not valid in Java. The identifier “ball” is basically treated as a variable; one that has not been declared in this case. So, while the second form of our belief is better from a modelling perspective, it is still not quite there from an ASTRA perspective. This is because logic is typically untyped and, as we saw earlier, ASTRA is typed. So, we need to decide on how to represent the ball. This really depends on how you are implementing your solution. If you have a Java class called Ball and you create an instance of that class when you see the ball, then you could simply use the Java object to represent the ball. A belief representing this cannot be written down because objects. If you were to print out the belief, it could look something like this:

see(1244defw@Ball)

Here the term is represented by the object reference for the instance of the Ball class.

If you don’t have a Java object representing the ball, then you need to use one of ASTRAs built in data types. Assuming there is only one ball, then the easiest way to model the ball is often to use a string:

see("ball")

This allows the agent to reason about a “ball”, but you, as the developer, maintain the mapping between the string “ball” and the ball object that exists in the environment.

Logical Expressions

A logical expression is something that can be evaluated to true or false. Typically, it involves some combination of beliefs and comparisons that are joined together using boolean operators (and, or, not). Logical expressions are used in the context of a plan rule, a query statement, and in any other place where the execution of a statement depends on the state of the agent.

|----------|--------|-----------------------------------------------------------------|
| OPERATOR | SYMBOL | EXAMPLE                                                         |
|----------|--------|-----------------------------------------------------------------|
| Not      |   ~    | ~likes(string X, "icecream")                                    |
|          |        | ~result(int X, int Y, int Z)                                    |
|----------|--------|-----------------------------------------------------------------|
| And      |   &    | likes(string X, "icecream") & is(X, "happy")                    |
|----------|--------|-----------------------------------------------------------------|
| Or       |   |    | has(X, "icecream") | has(X, "beer")                             |
|----------|--------|-----------------------------------------------------------------|
| Brackets |   ()   | hungry(string X) & (likes(X, "icecream") | likes(X, "burgers")) |
|----------|--------|-----------------------------------------------------------------|

For example, lets consider a football player who has do decide what to do next. The decision can be modeled as a goal !decde() that has a number of associated rules – one for each option available to the player.

If the player has the ball and is being closed down, but there is a player from the same team near the player then one option is to pass the ball to that player. On the other hand, if the player is in shooting range of the oppositions goal, then they should take a shot. This behaviour can be encoded as the following pair of rules:

plan +!decide() : 
        has("ball") & is("closed_down") & 
        close("opposition_goal") {
    shoot();
}

plan +!decide() : 
        has("ball") & is("closed_down") &
        near("team_player", string P) {
    pass(P);
}

Here, the contexts is a conjunction of belief literals (some beliefs that are “anded” together).

In addition to conjunction, we can also introduce disjunction (or operators). For example, consider somebody who will eat food only if the like that food, or at least tolerate that food:

plan +!eat(string F) : likes(F) | tolerates(F) {
    body.eat(F);
}

Inference Rules

Inference rules allow you to define new beliefs in terms of existing beliefs. An inference rule maps the new belief to a logical statement that expresses what must be true for the new belief to be true. Lets explore this idea by looking at the first two rules in the previous section. The rules are repeated below for ease of reading:

plan +!decide() : 
        has("ball") & is("closed_down") & 
        close("opposition_goal") {
    shoot();
}

plan +!decide() : 
        has("ball") & is("closed_down") &
        near("team_player", string P) {
    pass(P);
}

Together, the rules define how a football agent makes a decision about what to do based on their current context. The first rule states that, if they have the ball, have been closed down, and are close to the goal, then they should shoot at the goal. The second rule states that, if they have the ball, have been closed down and there is a teammate who is close, then they should pass to that teammate. Understanding these rules can be a little difficult because it involves analysing the logical statement provided in each context. We have to read each formula and understand what the combination means. Informally, we could state that the first context identifies when they should shoot, and the second context identifies when they should pass to another player.

Why are we discussing this? Well, instead of using the complex beliefs statements, we could introduce new beliefs to model the two contexts. We do this by using inference rules. In ASTRA, an inference rule takes the form:

inference <new belief> :- <belief statement>;

It is read: if the belief statement is true, then the new belief is true. For example, we could model the first rule context as follows:

inference should("shoot") :-
        has("ball") & is("closed_down") & 
        close("opposition_goal");

If we add this inference rule, we can simplify the corresponding rule:

plan +!decide() : should("shoot") {
    shoot();
}

We can do something similar for the second rule:

inference should("passTo", string P) :-
        has("ball") & is("closed_down") &
        near("team_player", P);

plan +!decide() : should("passTo", string P)) {
    pass(P);
}

So, to recap, the purpose of inference rules is to introduce new beliefs that capture more complex belief statements. This allows us to express a specific state of the environment more succinctly.

Another example of this can be explored in a blocks/tower world scenario. Here the agent is organising blocks on the table into towers. One piece of knowledge that can be useful to have is whether or not a block is free (i.e. whether or not another block is on top of it). We can express this through the belief sentence:

~on(string Y, X)

This states that there is no block on top of X. This can be used as part of a rule that, for example, involves picking up a block:

plan +!holding(string X) : ~holding(string Y) & ~on(string Z, X) {
    pickup(X);
}

This rule states that the agent can only achieve the goal to be holding X by picking X up if it is not holding a block and there is no block on top of X. It would be less of a mouthful if we could say that the agent can only achieve the goal to be holding X by picking X up if it is not holding a block and X is free. To model the fact that X is free, we can use an inference rule:

inference free(string X) :- ~on(string Y, X);

This inference rule states that the agent believes X is free if there is no block on X, and it can be used to make the plan rule easier to understand:

plan +!holding(string X) : ~holding(string Y) & free(X) {
    pickup(X);
}

We could do something like this for the gripper:

inference empty("gripper") :- ~holding(string Y);

plan +!holding(string X) : empty("gripper") & free(X) {
    pickup(X);
}

This refined rule is definitely easier to understand. However, ultimately, the same beliefs must hold (or not) for this rule to be selected as for the first version of the rule.

Inference rules can be useful in situations where there are many possible states that can trigger a rule (i.e. do something if X is true or Y is true or Z is true). Inference rules can be a nice way of simplify such situations by saying do something if A is true, and A is true if X is true, or Y is true or Z is true:

inference A :- X;
inference A :- Y;
inference A :- Z;

Obviously, the above is propositional logic and is not valid ASTRA code. A nice example that illustrates this idea is Tic-Tac-Toe. The game can be modelled as a set of beliefs about locations on the board. We can model the board as nine numbered locations:

-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 6 |
-------------
| 7 | 8 | 9 |
-------------

We can model the presence of counters (played by players) by the belief contains(int, string), where the first argument is a location and the second is the token played at that location. In a typical game, the players may make moves, which could be represented by the following beliefs (this is not a program but state):

contains(1, "X")
contains(4, "O")
contains(2, "X")
contains(6, "O")
contains(3, "X")

We can design our approach so that the lack of a contains belief means that there is no token played at that location. This can be nicely modelled using the inference rule:

inference free(int X) :- ~contains(X, string Y);

Note that there is a downside to this: you cannot use an unbound variable here - you must ask is location X free (e.g. free(5) would work, but free(int x) would not).

Where inference rules bevome useful is identifying winning states of the board. Any line of the same token is a winning state, for example if an X is places in locations 1, 2 and 3, then X wins. Inference allows us to enumerate all these possible configurations, meaning we can simply ask if there is a winner:

inference winner(string X) :- contains(1, X) & contains(2, X) & contains (3, X);
inference winner(string X) :- contains(4, X) & contains(5, X) & contains (6, X);
inference winner(string X) :- contains(7, X) & contains(8, X) & contains (9, X);
inference winner(string X) :- contains(1, X) & contains(5, X) & contains (9, X);
inference winner(string X) :- contains(1, X) & contains(4, X) & contains (7, X);

Obviously, there are more scenarios than the ones given above, but we can produce an inference for each possible winning position and then we can query the agents beliefs to see if there is a winner.

The idea is to allow you to introduce more abstract concepts into the beliefs of the agent.