Herself’s Artificial Intelligence

Inter-agent Communication

One of the obstacles in designing agents is to find a common language for them to use to communicate with each other and other people’s agents. Right now each designer writes a communications system for her own agents, so they can only talk to each other, much like people who speak only one language can only speak with others who speak the same language. Several ideas have been put forth and these are the most promising.

KQML (Knowledge Query Markup Language) messages carry information about the type information they are transmitting; assertion, request, query. Performatives are the primitives which define permissible operations agents may do in effort to communicate with each other.

It uses special agents called facilitators that handle many tasks: Track locations of agents by specific identity or type of service; Track services available and needed by agents; Act like post offices, holding, forwarding, receiving messages for agents; Translate between agent communication languages; Break complex problems in to parts and distribute tasks to agents that can handle them; Monitor the agents.

KQML uses categories or levels for agent communication content the content of the message, text, binary strings etc. communication sender, recipient, message ids. message identifies protocols for message transfer, handles encoding, and de scriptions of content

Requirements of KQML
form simple, declarative, and easily understood by humans
semantics Should be familiar, unambiguous, well grounded in theory
implementation Needs to be efficient and backward compatible
networking Platform independent across networks and support synchronous and asynchronous.
environment will be distributed, dynamic and non-heterogeneous.
reliability must be reliable and secure
content the language should be layered, like all networked software.

There are still some difficulties with KQML. There are ambiguities and vagueness and misdirections, misclassifications and some things that are needed but not yet in existence, in statements known as performatives (statements that work just by declaration).

KSE (Knowledge Sharing Effort) is sponsored by the Advanced Research Projects Agency. It is a project to put together a uniform method for agents to communicate with each other. KQML is one of the projects being developed. The two main subproblems are: translating from one representation language to another; content sharing among applications. Communication protocols must develop: an interaction protocol; a communication language; and a transport protocol (SMTP, HTTP, …).

ACL (Agent Communication Language) has three pieces; vocabularies, KIF, and KQML. The vocabulary uses an open ended dictionary of terms that can be referenced by agents.

KIF (Knowledge Interchange Format) is particular syntax format, similar to Lisp, for first predicate calculus communication between agents. KIF can perform translation from one language format to another. It can also be used to communicate between agents. KIF is a first order predicate calculus using prefix format. It supports the definition of objects, functions, relations, rules and meta knowledge. It is not a programming language. KIF has three main parts; variables, operators, and constants. KIF has two types of variables; individual (begin with ?) and sequences (begin with @). It has four operators; term (objects), rule (legal logical inference steps), sentence (facts), definition (constants). A form is a sentence, rule or definition.

Telescript is an object orientated remote programming language for use with mobile agents developed by General Magic. It has three main parts: a language for developing agents and environments; an interpreter for the Telescript language; and communication protocols (TCP/IP). The entire application can be written in Telescript but usually a combination of Telescript and C/C++ is used.

KAoS (Knowledgeable Agent-orientated System) differs from the other inter agent communication methods in that it considers not only the message but the sequence of messages in which it occurs. This enables agents to coordinate frequently recurring interactions. KAoS makes use of ‘agent orientated programming’ which is an extension of object orientated programming. This provides a consistent structure for the agents and an easier way to do agent programming. The agents contain: Knowledge (facts, beliefs); Desires; Intentions; and Capabilities. From birth the agent goes into a loop of ‘updating the structure’ and ‘formulating and acting on intentions’, unless it is in a cryogenic state, until its death.

Communication takes place with messages containing verbs, and informa tion. The messages are structured much like the KQML messages. Communication between agents takes place only within the domain the agents are in. Proxy agents communicate between domains in a given environment. Mediation agents communicate with outside agents.

Instances of agents of particular classes are created to work in various do mains. Using inheritance specialized agents are created. Domain managers control entry and exit of agents in a domain, and matchmaker agents give ac cess and information about services in the domain they are in.

More information:
Robots evolve and learn how to lie

See also:
Ant Algorithms

One of the trickier parts of designing artificial intelligence is how to represent information to something that can not understand language. Knowledge representation is defined by its syntax and its facts (semantics) which together along with the rules for deducing new sentences make up the logic. Entailment is the relationship between current sentences and new sentences derived from the current sentences. A good knowledge representation language will combine the ease of spoken and written languages, like English, with the conciseness of a computer language, like C.

Propositional (boolean) Logic This consists of a syntax, the semantics and rules for deducing new sentences. Symbols are used to represent facts which may or may not be true. W may 72 represent the fact it is windy outside. The symbols are combined with boolean logic to generate new sentences. Facts can be true or false only. The program may know a statement is true or false or be uncertain as to its truth or falsity. The syntax consists of , v, => (if x then y), (equal), and (not). Backus-Naur Form (bnf) is the grammar used to put sentences together. The semantics are just the interpretation of a statement about a proposition. Truth tables are used to define the semantics of sentences or test validity of statements.

Truth table for AND

T and T = T

T and F = F

F and F = F

F and T = F

A model is a world in which a sentence is true under a particular interpreta tion. There can be several models at once that have the same interpretations. An inference rule is a rule that is derived from a pattern that is true all the time for specific cases.

First Order Logic (first-order predicate calculus)
This consists of objects, predicates on objects, connectives and quantifiers. Predicates are the relations between objects, or properties of the objects. Connectives and quantifiers allow for universal sentences. Relations between objects can be true or false as well as the objects themselves. The program may not know whether something is true or false or give it a probability of truth or falseness.

Procedural Representation
This method of knowledge representation encodes facts along with the sequence of operations for manipulation and processing of the facts. This is what expert systems are based on. Knowledge engineers question experts in a given field and code this information into a computer program. It works best when experts follow set procedures for problem solving, i.e. a doctor making a diagnoses.

The most popular of the Procedural Representations is the Declarative. In the Declarative Representation the user states facts, rules, and relationships. These represent pure knowledge. This is processed with hard coded procedures.

Relational Representation
Collections of knowledge are stored in table form. This is the method used for most commercial databases, Relational Databases. The information is manipulated with relational calculus using a language like SQL. This is a flexible way to store information but not good for storing complex relationships. Problems arise when more than one subject area is attempted. A new knowledge base from scratch has to be built for each area of expertise.

Hierarchical Representation
This is based on inherited knowledge and the relationships and shared attributes between objects. This good for abstracting or granulating knowledge. Java and C++ are based on this.

Semantic Net
A data graph structure is used and concrete and abstract knowledge is represented about a class of problems. Each one is designed to handle a specific problem. The nodes are the concepts features or processes. The edges are the relationships (is a, has a, begins, ends, duration, etc). The edges are bidirectional, backward edges are called ‘Hyper Types’ or ‘Back Links’. This allows backward and forward walking through the net. The reasoning part of the nets includes: expert systems; blackboard architecture; and a semantic net description of the problem. These are used for natural language parsing and databases. Predicate Logic and propositional Most of the logic done with AI is predicate logic. It used to represent objects, functions and relationships. Predicate logic allows representation of complex facts about things and the world. (If A then B). A ‘knowledge base’ is a set of facts about the world called ‘sentences’. These are put in a form of ‘knowledge representation language’. The program will ‘ASK’ to get information from the knowledge base and ‘TELL’ to put information into the knowledge base. Using objects, relations between them, and their attributes almost all knowledge can be represented. It does not do well deriving new knowledge. The knowledge representation must take perceptions and turn them into sentences for the program to be able to use them, and it must take queries and put them into a form the program can understand.

Resolution and unification
Resolution: prove A true by proving A Not is false. Unification: take two predicate logic sentences and using substitutions make them the same. Unification is the single operation that can be done on data structures (expression trees) in Prolog. These are the techniques used to process predicate logic knowledge and the are the basis for Lisp and Prolog.

Frames
Each frame has a name and a set of attribute-value pairs called slots. The frame is a node in a semantic network. Hybrid frame systems are meant to over come serious limitations in current setups. They work much like an object oriented language. A frame contains an object, its attributes, relationships and its inherited attributes. This is much like Java classes. We have a main class and sub classes that have attributes, relationships, and methods for use.

A logic has a language, inference rules, and semantics. Two logical languages are propositional calculus and predicate calculus.

Propositional Calculus which is a descendant of boolean algebra is a language that can express constraints among objects, values of objects, and inferences about objects and values of objects.

The elements of propositonal calculus are:
Atoms: the smallest elements
Connectives: or, and, implies, not
Sentences: aka ‘well-formed formula’s, wffs

The legal wwfs
disjunction: or
conjunction: and
implication: implies
negation: not

Rules of inference are used to produce other wwfs
modus ponens: ( x AND ( x implies y) ) implies y
AND introduction: x, y implies ( x AND y )
AND commutativity: x AND y implies x
OR introduction: x, y implies ( x OR y )
NOT elimination: NOT ( NOT x ) implies x
resolution: combining rules of inference into one rule:
{ example: (x OR y) AND ( NOT y OR z ) = x OR z
Horn clauses: a clause having one TRUE literal, there are three types: a single atom (q); an implication or rule ( p AND q = r ); a set of negative literals ( p OR q => ) . These have linear time algorithms.

Definitions:
Semantics:
associations of elements of a language with the elements of the domain

Propositions:
a statement about an atom, example: The car is running. Car is the atom, ‘is running’ is the proposition.

interpretation:
is the association of the proposition with the atom

denotation:
in a given interpretation the proposition associated with the atom is the denotation

value:
TRUE, FALSE, given to an atom

knowledge base:
a collection of propositional calculus statements that are true in the domain

truth table:
a tablular format for representing states

satisfies:
a true statement under a given interpretation

model:
an interpretation that satisfies each statement in a set of statements.

validity:
a statement that is TRUE under all interpretations

equivalence:
statements are equivalent if their truth values are identical under all interpretations.

Examples:
DeMorgan’s Laws:
NOT (x OR y ) = ( NOT x ) AND ( NOT y )
NOT ( x AND y ) = ( Not x ) OR ( NOT y )

Contrapositive:
( x implies y ) = ( NOT x implies NOT y )
if ( x = y ) then ( x implies y ) = ( y implies x )

Propositional satisfiability, aka PSAT
a model formula that comprises the conjunction of all the statements in the set.

Predicate Calculus takes propositional calculus further by allowing statements about propositions as well as about objects. This is first order predicate calculus.
Contains:
object constants, term: strings of characters, xyz, linda, paris
relation constants: divided by, distance to/from, larger than
function constants: small, big, blue
functional expression: examples: distance(here, there); xyz;
worlds: can have infinite objects, functions on objects, relations over objects
interpretations: maps object constants into objects in the world
quantifiers: can be universal or for a selected object or group of objects

Predicate Calculus is used to express mathematical theories. It consists of sentences, inference rules and symbols. First-order predicate calculus symbols consist of variables about which a statement can be made, logic symbols (and, or, not, for all, there exists, implies) and punctuation ( ‘(‘, ‘)’ ).

If we have a set S in which all of the statements are true then S is a model. If S implies U then U is true for all models of S and NOT U is false for all models of S. If we make a set S’ which has all of the statements of S and the statement NOT U it is not a model. All statements in a model must be true. S’ is unsatisfiable since there is no way for the statements of S and the statement NOT U, both of which are in S’ to be true at the same time. This is used to prove formulas in theorem proving. To show S implies U is is sufficient to show S’= S, NOT U is unsatisfiable.

Resolution and unification

Resolution: prove A true by proving A Not is false.

Unification: take two predicate logic sentences and using substitutions make them the same. Unification is the single operation that can be done on data structures (expression trees) in Prolog. These are the techniques used to process predicate logic knowledge and the are the basis for Lisp and Prolog.

Resolution is one way to prove unsatisfiability.

More information:
Programming in Haskell ( pdf)
Real World Haskell
The Haskell Road to Logic (pdf)
First Order Predicate Calculus
Syntax of Predicate Calculus (pdf)
Knowledge Representation and Predicate Calculus (pdf)
Predicate Calculus (pdf)

See also:
Knowledge based expert systems

Reasoning Programs and Common Sense

Programs that have commonsense are some of the earliest attempts at artificial intelligence. The problem with the commonsense programs is there is no way to easily define the knowledge in a way the computer can use with out the computer understanding language. Little success was made here, but the descendants of common sense programs, expert systems have been very successful at problem solving of the type people learn in college, like engineering, law and medical diagnoses. From these studies came the computer languages Lisp and Prolong.

“Common sense knowledge includes the basic facts about events (including actions) and their effects, facts about knowledge and how it is obtained, facts about beliefs and desires. It also includes the basic facts about material objects and their properties.” [John McCarthy]

John McCarthy’s paper on common sense shaped the artificial intelligence movement for several decades. The Advice Taker is a program that was to have commonsense. He states that ‘A program has common sense if it automatically deduces for itself a sufficiently wide class of immediate consequences of anything it is told and what it already knows’. So the goal is for the Advice Taker to be able to discover simple abstractions. McCarthy defines proof of a program having common sense to be: that all behaviors be representable in the system; interesting changes in behavior must be expressible in a simple way; the system must understand the concept of partial success; and the system must be able to create subroutines to be used in procedures.

Another attempt at a general problem solving program following this type of reasoning is the “General Problem Solver” [Newell, Shaw, Simon, Ernst]. The program was given objects and operators with which to compare objects, take actions, and develop situations. An initial situation and a goal are given to the program and the program determines how to get from here to there. Three basic steps are taken to do this:
Evaluate difference between current situation and the goal state
Find an operator that lowers the difference between current and goal state
If it is legal to apply this operator, do so, else determine a situation that can use that operator and set it as a short term goal.

Reasoning Programs are the next step in this line of research. They will need to be able to sense and or find information about their environment, to prove whether or not solutions exist to problems given them. They will need to be able to reason out steps from initial situations to goals. Importantly it will need a language to define objects, goals, operators, logic, and temporality, states of being and other things.

Situational states or states of being are data structures and often defined with matrices, lists, statements, sets, trees, or more commonly graphs. Situational calculus, a derivative of first-order predicate calculus was developed to allow for states to be described as data structures as well as the effect of actions on states.

Common sense is very different than intelligence or education. Some people have one, two, or all three of these qualities. Teaching and testing for common sense has not progressed well with people and will probably not do well with computers until we have a greater understanding of exactly what common sense is, how it is acquired and how it can be tested for. Some other problems developing these systems are putting common sense into a language that is easily understood by people and computers. A second major problem has been representing time and changes that occur over time. Common sense seems to be learned from doing rather than being taught, so it may be that agents may gain common sense about the computer network they exist on, or further down the line robots may gain a bit of what we consider common sense about our world.

See also:
Knowledge based expert systems