Previous Section : Table of Contents  Next Section : Semantic Needs

"Reality in not user-friendly"

It is a good step to define what is the world's conceptual framework. Doing so, we begin to examine the essential object ontology that should be use in our system design. Natural languages are very expressive but they are not too objective. Making a good classification of these concepts and then formalize them, is necessary to create the needed working vocabulary.

The Universe is everything and is where everything happens. Not much to say about that! The Universe minus all players (i.e., humans), is called the arena.

An object is a part of the Universe that can be isolated from the rest, i.e., it is something meaningful as a separate entity. Everything outside the object is the environment. Of course, for each object there is a different environment. The intersection of all environments (that is, the Universe without its objects) is called the world. The world has some intrinsic world parameters (or physics), that all objects must comply. The world may have specific areas with special parameters named sectors.

Every single thing that has a specific name (an object, a class, some world parameter, ...) is an item.

Every physical object can be measured by certain parameters (e.g., mass, height, weight, length,  temperature, cost, velocity, acceleration, ...). Measurements can be divided into two main categories, objective and subjective.

Some objective measures have a standard unit that define the type of that specific measure (e.g., centimeters or units, for distance; clicks for time; Kelvin for temperature, <day,month,year> for dates, ...). Some can also have an associate metric defining the distance between two different values.

There are two ways to interpret this data, direct and fuzzy interpretation. Direct interpretation is when we attribute the real value of the measure (e.g., he weights 60 Kg). In fuzzy interpretation we define several groups (e.g., a man can be a baby, young, adolescent, adult, old, very old), and define inclusion degrees for every measurement value. Then, according to certain simple calculations, find which one is appropriate (e.g., a man with 75 years is 70% very old, and 30% old).

Subjective measures are harder to define (e.g., ugliness, deliciousness, happiness...). It is not a good solution to impose a numerical scale on subjective categories (e.g., how beautiful is Atilla the Hun? 0.13?). However, although these measures are not numbers, they can be compared and ordered using relation < (e.g., in terms of beautiful people, we can classify the next ones in the following way: The Elephant Man < Atilla, the Hun   <  You < Claudia Schiffer).

A n-tuple is a vector of dimension N, with measurement values A₁, A₂, ..., A_n of certain types. Let's represent this tuple as <A₁,A₂,...,A_n>. A n-ary relation is a set of n-tuples.

Ok! What the Hell is that? Let's see an example. To define a relation Father, we just need to define its set of tuples. Let them be, <Alex. Dumas, Alex. Dumas Son>, <Arathorn, Aragorn>, <Xerxes, Artaxerxes> and <John, Peter>. If I ask the following question, does Peter have a Father? Or, more formally, It exists a x, such that <x, Peter> is true? The answer is yes, the x is John!

A function is just special kind of relation. Any given object of the relation is related to exactly another object. For e.g., multiplication is a functional 3-ary relation, since for each pair x,y, there is only one z, such that <x,y,z> belongs to multiplication (<2,3,6>, <10,3,30>, <4,0,0>, ...). A function is defined by its name and its arguments types, i.e., its signature. I'm not going to elaborate since there are millions of good math texts that deal with this subject.

The Universe is not a random collection of things. Certain objects share certain properties or patterns that make us construct classes or categories to include and classify them. For example, the banana and the apple that I'm going to eat at lunch, are both fruits. So, Fruit represents a class of objects. Of course, one object may belong to more than one class (my banana also belongs to the Banana class, and also the Eatable-Things class).

A class can have many sub-classes (Banana is a sub-class of Fruit), and can also have super-classes (Fruit is a super-class of Banana). All class relations in a Universe define its taxonomy. In most applications, it is usual to simplify these matters and state the following: an object is an instance of only one class. Another simplification is that one class can only have one super-class (not like C++, but like many other OOP languages).

The OOP paradigm defines an object as a collection of data (measures, properties) and related methods (functions, procedures). An object configuration is the set of actual measure values of that object.

An object method can change inner information or change environment information. The first one is called an adaptation, the second one, an action. Each behavior changes the object configuration, and each action produces a set of reactions by the environment that can lead to event(s) creation. The set of adaptations and actions of a certain object is called the behavior of that object.

Let's see some operations that can be applied to classes:

Set operations - The class taxonomy can be handled as being sets. Some operators are:

1. x belongs to y, means that x is an object of class y or of one of its subclasses.
2. x is included in y or x is-a y, means that x is a sub-class of y.

Reification -  This is the process of turning a class or a function into an object. (e.g., Humanity is the class of all Humans. If we reified that class, it is possible to use it in Size(Humanity) giving 6 billion).

Inheritance - Means a class specialization. Every property that a class has is inherit to its sub-classes (e.g., if a Banana is a sub-class of Fruit, and all Fruit objects are eatable then, in principle, all Banana objects are also eatable). The next three operations are part of inheritance.

Abstraction (abstract classes) - A class that is not meaningful on its own (you cannot create instances of an abstract class). This presents a template to define new sub-classes. Each abstract function on class must be defined in the subsequent sub-class (if it is not abstract again, of course).

Termination (final classes) - A class that cannot be extended any more. This happens to prevent further specialization, it is a leaf in the taxonomy. The same can be done to a specific data or method of a class, preventing its overriding when its class is inherited.

Overriding (virtual functions) - A class may override a function that is defined is its super-class. This is a kind of exception treatment for classes (e.g., class Bird has a boolean property Fly? equal to true, but a sub-class Penguin overrides it, setting it to false).

Information Hiding - Each class member (data or method) have a specific visibility. Public members are accessible anywhere the class is accessible. Protected members are accessible inside its class and for its sub-classes. Private members are not accessible outside its class.

Per-Class members - A class can have data or methods that are intrinsic part of that class and not of its instances (e.g., the total property of class agent). These are usually called static data and static methods.

Almost all application will work on some kind of space-time Universe. An event is something that happens in the Universe, at a specific time and a specific space. An interval is a section on time, containing all events during that time. A place is a section on space, containing all events occurring on that space.

On Event Programming paradigm, an event triggers a method on one or more objects, probably making them change its own configuration. (e.g., if a bomb object receives a touch event, it executes method explode).

Every dynamic Universe have changes. Some of these changes affect the objects, making them adapt and change themselves. Since, every application is always a computer algorithm, space (units) and time (clicks) are discrete. We will say that an event is continuous in time (space) if it happens during a closed set of clicks (units).

A process represents a continuous change event. Each subpart of a process is still the same process (e.g., Raining event is still the same process during its duration, or just in the first half).

A state represents a continuous non-change event. These may mean, for instance, that an object in a certain state, exhibits a homogenous behavior. (e.g., a monster in Happy state is consistently less aggressive than in Unhappy state).

Some of the object data can be other objects. One interpretation is that an object contains another one (e.g., like a box contains some food, or a bag some gold coins). This notion is formalized as an contains relation. An object can have more than one object of the same kind (e.g., object bag contains 2 object gold-coins). The set of objects contained by one object, is called its inventory.

The entire Universe can be seen as a BIG object, containing everything else. The physics are just the collection of data, methods and event handling defining that Universe. However, we will not use this viewpoint.

An object that cannot be split into sub-parts, is called an atomic or primitive object. However, an object can be part of another object. There can be many uses of this notion. A continent is made of several countries; a body of legs, arms, head and torso. An object that is made of parts, is called a composite object. Classes of composite objects are characterized by their common structure. Composed objects may be reversible (they may be decomposed again) or not.

When an object is separated, those properties that remain the same, are called intrinsic properties (e.g., density, color, ownership, flavor). Otherwise, they are extrinsic properties (e.g., weight, shape, functionality).

Some objects may not be seen as primitives or composites. For example, the object water contained in a glass object. If we take some part of the water and sprinkle it over the table, how many objects we get? It is not obvious what to do with this type of objects. When a object can be split but cannot be divided into parts, it is called a stuff, in opposition of thing, a well-behaved object. Water, smoke, fire are stuffs! Boxes, bodies, umbrellas are things!

A stuff object is one with an associate quantity of a certain type (e.g., 10000 grams of water). Each stuff object may be divided into smaller parts, that be can connected or not. As in composite objects, stuff objects have intrinsic and extrinsic properties. If some objects are connected, a change in one object reflects on the intrinsic properties of the other objects. When two sets of non connected objects are blended, all objects become connected. There should be two abstract methods in Stuff class, named Blend and Divide, in order to define how two objects may blend/divide into one another.

Notice that this stuff concept is not an is-a or a contains relation, but some kind of is-same relation (if you have a better term, tell me).

As I said early, the world may be split into sectors (or zones). A sector defines a certain world area (or volume), where there are some different parameters from the world (e.g., an house, a country, a door between two rooms, a foggy swamp can be defined as sectors). Two sectors are separated by a common frontier. A sector can be inside another sector, being a subsector of the former (which is called the supersector).

Each sector inherits all world parameters, but can change them and therefore have its own physics (e.g., gravity, inertia, friction) or some other new parameters (e.g., enable/disable communication, enable/disable magical artifacts). In fact, a sector is a small world within the main world. Each subsector inherits the parameters of its supersector (just like classes).

When a moving object crosses a frontier, it will receive two events, warning the exit of one sector and the entrance on a new one. Each one of the object methods can change its behavior accordingly to the sector features (e.g., a player would jump less in a high gravity sector).

Communication is an essential feature of any Universe. We are doing that just now! Communication is an explicit change of information, having always one sender, and zero, one or more receivers.

In principle, any object may communicate with other objects. The information carrier is named a message. A message consists of the following items:

Sender Id - it identifies who sent the message. There can be white, gray and black messages (just like in email Diplomacy). In white messages, the sender is who the message tell us. In grey message, the message is anonymous. In black messages, the sender identification may be faked.

Receiver Id - it identifies who receives the message. It may be no one (that is, to the world); to one object; to a specific group (e.g., a class of objects, all objects in a radius, a team of players, ...); or a broadcast to all objects.

Content - the information itself. There must be a protocol defining the information structure, in order to be perceptible (e.g., strings, complex data types, ...). It may be written in a specific language (in a multi-language game world). Also important is the type of message:

1. Information - sending some facts to the receiver(s). May be seen as a Belief, if the information has a probability < 1 attached to it;
2. Query - asking something;
3. Answer - answering a former query;
4. Request - requesting (commanding, treating) some task to the receiver(s);
5. Offer - bargaining the exchange of tasks (e.g., I will do A, if you do B);
6. Acknowledge - sending an ok to a request or an offer;
7. Posting - conveying the message from a sender to a receiver.

Another important feature is transportation, how a message is carried. Messages can be subject to physics. The kind of transportation used (e.g., by voice, by horse, by air mail, by radio, ...) may affect some features, like the radius of the message, how fast is received, if it can be corrupted, intercepted, encrypted, ...

A message can be seen as an event producer: all receiver objects must handle some kind of Incoming-Msg event.

An agent is an object that has complex behavior defined not only by its environment. This implies that it must have some kind of inner knowledge (a kind of mental state) and is able to use it to analyze a problem, define a set of decisions and take some proper action. Usually, taking the complexity of its mental state, there is a spectrum of agents ranging from reactive to cognitive. A reactive agent has no mental state, it just reacts to the environment in some specific way (so, on that sense, it is more a complex object than a simple agent). On the other side, a cognitive agent have a  "mind", using it to perform complex tasks, like planning or learning.

This subject has some deep philosophic arguments and profound discussions. My intention is not that, but I want to leave a quick note. To an outside observer, any object is a black box facing the environment and its problems. The observer just see the objects, what problems they face, and how they react in order to solve them. He does not see any (hypothetical) mental state. However, if an object is able to solve its problems efficiently, then it shows rationality relative to its own Universe.

There are at least three types of agents:

A simple behavior mechanism for reactive agents is to use Finite State Machines. This data structure defines a set of states. The agent must be at one specific state that includes a set of methods defining its proper behavior. The state can change with incoming events to another state. You can find a lot of this in the literature, since this is a well known and very used procedure. I inserted here a little Java applet of mine to make an example.

Exercise: Try to find the bot's behavior (hint: it has 5 different states)

The mental state of a bot, at a given time interval, consists in the following elements:

The knowledge consists of the first two points (so, knowledge is made of facts, rules and goals). The last two are computed by a decision making procedure based on the actual mental state and the actual Universe state.

Each fact and rule may have a confidence status (a number between [0,1]). A fact/rule with a confidence less than 1 is a guess. It is possible to associate fuzzy concepts to illustrate the confidence degree to a certain guess (e.g., confidence in [0.9, 1.0[ means an almost certain guess).

Each goal may have a priority (also a number between [0,1]) and an utility status. Priority gives the need of the goal, utility gives the usefulness of achieving that goal. This two values may be balanced differently on different agents (e.g., if all actual goals have priority < 0.5, choose the one with maximum utility). Both measures should ease the decision making process, when determining what action to take from its intentions.

Of course, there should be a way to insert, modify and remove facts, rules and goals.

If the agent has several states, rules and goals may differ for different states. That would accelerate decision making, since the number of rules and goals would decrease (it would use just the specific state rules). Each state can be defined as a fact (e.g., state(hungry)), and changing states implies removing one fact and adding a new one (e.g., remove-Fact( state(hungry) ); add-Fact( state(eating) ).

Knowledge Representation

In order to formalize these concepts, there must be some kind of knowledge representation language. How can we represent knowledge? Let's see some examples:

First-Order Logic

First-Order Logic is the standard of logics. Invented in the XIX^th century, it resisted more than a hundred years to mathematical progress. I suppose everyone knows it (the universal quantifier, the existential quantifier, ...).

Let's see an example. Take two relations: friend and enemy. The knowledge of a bot about who is friendly or not may be defined by them. For agent X, sets friend(X) = {bot12, player07, bot02} and enemy(X) = {player10,player02} defines what it knows about this subject. How to state rules of behavior?

E.g. 1: If something attacks me, shoot it and put it in the enemy list

    attacked( Y, Self ) => shoot( Y ) and enemy(Y) = true

E.g. 2: if somebody friendly is attacked, help him or shoot the foe (so, there are two possible actions. It is the decision making job to decide between them)

    attacked( Y, X ) and friend( X ) => shoot( Y ) or help( X )

This logic is a good candidate for the job, since there are many works about it, and there are good decision process algorithms in the scientific literature. Check [1] for an excellent survey.

High-Order Logic

Using high-order logics, allow us to use sentences as arguments. An example?

If a teacher says that the shooting-ladies-of-the-lake rule is bad, then forget that rule.

    teacher( X ) and classify( X, lady-of-lake(Y) => shoot(Y) ) = bad => remove( lady-of-lake(Y) => shoot(Y) )

Modal Logic

Roughly, modal logics are languages based on first-order logic to which some new operators that take sentences as arguments (called modal operators) have been added. Modal logic extends the expressiveness of first-order logic, but not its computational lower bounds.

Introducing a modal extension to first-order logic, implies a possible world semantics. Stated in a simple manner, possible worlds are the problem solutions that are consistent with the actual knowledge kept inside the agent mental state. The usual modal operators are box [] and diamond <>. Let's take a preposition A, []A means that A is true is all possible worlds, and <>A means A is true in at least one of those possible worlds.

There are several interpretations of these modal operators. Here are three illustrious examples:

To see more about modal logic, check this book (it is a postscript file). 

The main problem with modal logics is that decision making procedures are very complex and are still in development (check here for details).

Learning

If the Universe state can used to classify the consequences of a chosen action, it is possible to adapt confidence status. Decrease the confidence of the used fact/rule, if the result was bad; increase them, if the result is good. This is reinforcement learning acting on the agent mental state. For each fact/rule there should be an experience measure, informing how receptive it is for learning (e.g., an old rule changes less than a young rule), and a momentum measure, stating its inertia for change (e.g., one failure does not count much, if the last five were successes).

There are many things in the Universe that we don't know for sure. For instance, a bot cannot know exactly what a  player will do on that moment in time, but it should decide to do something about it. So, a bot must deal with situations that it does not understand too well. If information provides knowledge about the process, uncertainty provides belief. How can we measure that uncertainty? Let's see some ways:

Probability

Well, everybody knows this one, the [0,1] real interval set! There are two different interpretations for probability. The first one deals with frequency. A probability is a property of a set of similar events (e.g., the six dice results) and the probability of a specific event is the frequency of its outcome comparing with the set of all results. The other interpretation is a more subjective one, expressing the degree of belief that we have on the occurrence of an event. See below, on Evidence Theory subsection for some more.

Laplace Law

Let's first state the Principle of Insufficient Reason:

If there is no strong reason to think that something is true or false, we assign equal probabilities to each event.

How can we use this idea in this context? One example, imagine an urn with white and black balls with unknown proportion. If we take N consecutive white balls, what are the chances that the next one will be also white? One answer if given by Laplace Succession Law. Since we do not know the distribution of white/black balls, we assign an equal probability to both, i.e., 50%. Then , Laplace says that the probability for the next white ball is N+1/N+2.

Another simple example: A man goes to a restaurant for the first time. Since he does not know anything about the food, he states that the probability of eating well is 50%. If that happens, the next time he will think that the probability will be 2/3 = 66%. After ten days, if he always eaten well, the probability raises to 11/12 = 92%, and so on...

More formally: For k events, N_k is the number of occurrences of event k. The actual probability of an occurrence of event j is p(j) = (N_i + 1) / (N₁ + ... + N_k + k).

Of course, there are situations where the Laplace Law cannot be applied (e.g., if the event is "live one more year", than Laplace Law would state that an 80 year old man would have more probability of staying alive the next year, than a 10 year old child). But it can give interesting results on total obscure situations.

Evidence Theory

Probability gives information about possible events of a random process (e.g., 1/6 for each value of an impartial dice). But it does not say anything about the ignorance that we have concerning that process. Evidence theory tries to fill the gap, extending probability.

Let U be the universe of possible events:

Probability theory defines a function, called probability, mapping all events of U into the real set [0,1], i.e., p:U->[0,1].

Evidence theory defines another function, called mass, mapping all subsets of U (i.e., the power set of U, 2^U) into the real set [0,1], i.e., m:2^U->[0,1].

What means this difference? In Evidence Theory, sets of events also have a certain measure attached. Ok, an example:

Imagine yourself as Inspector Clouseu. You arrive at home. You have an oriental servant named Kato that hides in the house to attack you by surprise (always training your battle instincts!). You know that there is 30% possibility that he is hiding in the fridge (he is nuts, well, both are), 10% for the closet, 10 % in the bathroom, and 50% in the living room or in the bed room or in the bathroom. See the point? You cannot separate (by some obscure reason) the probability of the last three places, but you state a value for that set, i.e., those events assemble an event set that cannot be described by Probability Theory but is captured in Evidence Theory.

There are two main functions for computing uncertainty about set A included in U

1. Belief Function, Bel(A) = Sum of all m(B), where set B is   included in A
2. Plausibility Function, Pl(A) = Sum of all m(B), such as (B intersect A) is not empty

Belief includes the mass of all parts in a certain set. In our example, for A = attacked in the kitchen or bathroom, Bel(A) = m(fridge) + m(bathroom) = 40%, and Pl(A) = m(fridge) + m(bathroom) + m(living room or bed room or bathroom ) = 90%.

Fuzzy Sets

The western culture was based on many principles. One of those (a very old one, btw) is called the Law of the Excluded Middle that just says something like, some object A have property B or not. This principle lead too many important ideas, like, a person is good or bad, a Nation is friendly or hostile, you go to Heaven or Hell, and much more (good or bad, hehe...) stuff like that.

In Fuzzy Sets, property B can have a degree of membership with object A that varies between [0,1], with value 0 meaning that it does not belong at all, and 1 meaning total inclusion. Taking the age example, if Mary has 70 years, she belongs to the fuzzy set of old people with 75% of membership.

There is a difference in Probability and Fuzzy Sets. When we say that the probability of Mary being a old people is 75%, what we are saying is that she is an old people (75% chance) or not (25%). In Fuzzy Sets, Mary is a member of the set of old people with 75% membership.

There are a lot of stuff about Fuzzy Logic and Fuzzy Sets. A short introduction is found here.

Most of the important work still lies in finding what is relevant and should be implemented, in order to give those agents, real and effective cognitive minds. Not only in the internal mental states (like knowledge, learning, beliefs, …), but also, and especially, in introducing and formalizing social mechanisms to provide complex social interactions between virtual agents and interested humans (like power and trust, laws and rights, autonomy and dependence, negotiation and diplomacy, and so on...). This is yet to be done!

 

Previous Section : Table of Contents Next Section : Semantic Needs

Last modified: 27/09/04 by Joćo Pedro Neto