WPI Computer Science Department

Computer Science Department
------------------------------------------

Appendix A. Intermediate Language Users Guide
------------------------------------------

The Intermediate Language is the format in which you must enter data into SiFAKA. This User's Guide will explain the format in which agent knowledge must be entered. This User's Guide will not explain how to use the Clipsifier or Launch program.

------------------------------------------

The Intermediate Language was designed based on SiFAKA, as described in the MQP report entitled "Design and Implementation of a Single Function Agent Generator" by Mark Santesson. The project code is DCB9502. SiFAKA was written in C for X Windows on a DEC Alpha by Patricia Currier as part of project number MQP-CS-DCB-9501.

This document explains how to enter an agent into SiFAKA. It is assumed that the reader already knows how to use SiFAKA, or is at least familiar with Graphical User Interfaces. This document does not explain how to control SiFAKA. If the user is not familiar with how to use a mouse, enter text into windows, and select options from a list, they should read the above mentioned report on SiFAKA or ask someone for help.

Agents are autonomous software entities who contain knowledge about a problem. Each agent uses its knowledge to perform certain actions. Many agents who are able to interact in a common environment are said to compose a multi-agent system. This document explains how to use SiFAKA to describe agents in a multi-agent system so that they can be translated into CLIPS code by the Clipsifier. The Clipsifier is described in the MQP report listed above, as well as in additional documents.

In a Single Function Agent (SiFA) system agents interact with each other through targets. Each agent has one target, for which it can determine values and initiate Conflicts. Each agent can use values of other targets, but is not allowed to influence the values contained by them.

The Intermediate Language (IL) is the form in which the user specifies what an agent knows and does. This encompasses not only Selection Methods, but also Conflict Detection and Resolution Methods. As such, there are many different parts to the IL. Currently, Selectors and Critics can be expressed in IL. Selectors use values from their selection list to propose values for targets. Critics can keep undesirable values from being accepted.

------------------------------------------

A.1 Components of the Intermediate Language

To define an agent, you will need to enter the following things:

This section will briefly describe where this information is entered and what is expected.

(neat-o gif of SiFAKA)

Figure A.1: Main Agent Window

When an agent is opened in SiFAKA, the main window will open, as shown in figure A.1. The agent's name is entered into the box titled "Agent Name". The name is a text string, spaces are allowed, but punctuation (especially semi-colons and parenthesis) should be avoided.

Each agent has a target. The name and type of the target must be entered into the window titled "Agent Target". The type precedes the agent name, and can be either "symbolic" or "numeric". The target name may not contain any spaces or punctuation.

The Selection List is entered by clicking on the "Edit Selection List" button, shown in Figure A.1. A new window will open, into which the data will be entered. One value is entered on each line. Symbolic values should be preceded by a single apostrophe, as shown in Figure A.1. Numeric values should always be constants, never functions or mathematical expressions.

The Selection Rules are entered by clicking on the "Edit Selection Method" button. Selection Rules have a value on the right hand side, which is used to set the target. Example Selection Rules are shown in Table A.1. A more complete explanation of how rules are formed is presented later.

Table A.1: Example Selection Rules:

IF: MATERIAL = 'wood         THEN: (basis * 1.5)
IF: MATERIAL = 'metal        THEN: (basis * 4.0)
IF: (X = Y) and (Z < 10)     THEN: (basis * Z)
IF: (X = Y) and (Z !< 10)    THEN: (basis * 10)
Conflict Detection Rules are similar to Selection Rules, but instead of indicating a value for the target they indicate whether the target's value is acceptable or not. Valid actions are "conflict", "accept", and "ignore". Table A.2 shows some sample Conflict Detection Rules. They are entered into the window shown in Figure A.2. Note that the agent shown in Figure A.1 is not the same agent shown in Figure A.2, since they have different targets. The window shown in Figure A.2 appears when the button titled "Conflict Knowledge..." in the lower right corner is clicked on from the window shown in Figure A.1.

Table A.2: Example Conflict Detection Rules:

IF: X within 10% of Y                 THEN: accept X
IF: ((X - Y) / Y) > 1                 THEN: conflict XY Aren't close enough
IF: (X - Y) < cons                    THEN: ignore X = Y, perfect!
IF: (X < accepted) and (accepted < Y) THEN: accept ((X + Y) / 2)


(neat-o gif of SiFAKA conflict resolution)

Figure A.2: Conflict Detection and Resolution Window

The Conflict Resolution Strategy is determined by turning on or off the various options shown in the lower left corner of the Conflict Knowledge window, shown in Figure A.2. The effects of the various items are explained in Table A.3.

Conflict Resolution Options
Name of OptionEffect of Option
Request an alternativeEnables the agent to request the other agent to suggest another alternative (from the preference list)
Relax constraintPermits this agent to relax it's objections to the other agent's values
Accept a "don't care"Permits this agent to successfully end a conflict if it receives a "don't care" message
Request more precisionNot implemented
Give an alternativeAn agent with this selected will always give an alternative when asked, as long as it has alternatives left
Give more precisionNot implemented
Refuse to give an alternativeAgents with this selected will not give alternatives as often as they would otherwise
Issue a "don't care"Permits an end to the conflict by indicating that the agent gives up
Request relaxationThe agent will ask for a relaxation sooner and more often than normal

------------------------------------------

A.2 The Selection List

An agent's Selection List contains values that are acceptable or which the agent may use to determine acceptable values for its target.

Only Selectors have Selection Lists. Critics, Praisers, and some of the other agent types do not. Agents that do not have selection lists do not need Selection Lists or Selection Rules.

The Selection List consists of a list of values. Values can be either symbolic or numeric in nature. As explained above, each agent must explicitly declare what type of value it's target holds (and therefore, for Selectors, what type of values are contained by it's selection list). All symbolic values must be prefixed with an apostrophe, as demonstrated in Figure A.1.

Values in the selection list should be ordered by preference. More desirable values should come before less desirable values in the selection list. The most desirable value should be the first value, which is preceded by the number "0" as shown in the bottom half of Figure A.1. The least desirable value should be last. In addition, the last item should be the worst value which is still potentially acceptable (if no other values are accepted by other agents during negotiation).

------------------------------------------

A.3 The Selection Rules

Selection Rules determine values for targets based on values from the Selection List. A Selection Rule consists of a condition and a value.

The Selection Rules are a manifestation of an agent's design knowledge, they determine how the agent selects values for its target. When the Selection Rule's condition is satisfied, the value described is used for the target. The value can be either a constant or a function. This value is then used for the agent's target. Since each agent may hold different knowledge about the relation between it's own Selection List and the target's value, each agent must be able to translate between the two. The act of turning a value from the Selection List into a value for the target is referred to as "mapping".

Some example conditions for an agent, expressed in English, are:

Since Selection Rules are responsible for mapping values from the Selection List into a value for a target, the Selection Rules must have access to an appropriate "source" value from the Selection List. This value is termed the basis value, since it is the basis of the target value. The value of basis comes from the Selection List. Examples using basis were shown in Table A.1, in Section A.1.

------------------------------------------

A.4 The Acceptable List

In addition to a selection list, each agent also is considered to have an acceptable list, which is a list of values from the Selection List that have already been proposed. An agent's acceptable list contains all values which are currently acceptable when an agent system is running. This list is not entered explicitly by the user. The user does not specify it. Its values come from the Selection List, as will be explained below. It exists only during the execution of the SiFA system, but is an extremely important concept to understand in order to write agents.

The Selection List starts out containing all values which the agent might conceivably use to arrive at an acceptable value for its target (via mapping, discussed above). The acceptable list starts out with only one value, the first value from the Selection List (which is, by definition, the most preferred value). Values will migrate from the Selection List to the acceptable list. The agent itself must decide during negotiation when it is ready to do this.

The existence of the acceptable list during Conflict Detection is very useful. The agent can very easily compare a value from the target (which another agent has proposed) to values it has already agreed to in the past. The acceptable list is accessed by using the keyword "acceptable" or the abbreviation "acc".

------------------------------------------

A.5 The Conflict Detection Rules

The Conflict Detection Rules govern the agents' initiation of conflicts, and their ability to recognize when they are over. When a target is given a value by an agent, all other agents who also have that target must agree with the value or initiate a conflict.

Depending on the situation, agents can accept the value. This gives the agent the opportunity to add a value to the Acceptable List. The agent must specify a value to be placed in the Acceptable List, or a function which gives the value. In the future, the agent will automatically recognize that the target's value is acceptable.

In other circumstances, an agent may want to decline a conflict but not actually accept the value. For this instance, agents may choose to ignore the potential conflict, so that there is no conflict initiated, but the agent's list of acceptable values does not change.

An agent may also choose to initiate a conflict. In order to make it easier for the user to tell what an agent is doing during executions, the ignore and conflict options will display a message if they are triggered. The user enters the message into SiFAKA as an argument after the conflict or ignore instruction, as shown in rule #0 of Figure A.2.

Due to the nature of the accept directive, it may not have accompanying comments, but a suitable (although not user specified) comment is displayed automatically. The user should refrain from using semi-colons, parenthesis, and certain symbols (such as "$") in the comment. Since the comment will be included in the CLIPS code exactly as the user enters it into SiFAKA, and these characters have meaning to CLIPS; an incorrectly written comment could conceivably ruin the structure of the CLIPS rule it appears in.

Just as Selection Rules have access to a "basis", Conflict Detection rules have access to "next", "accepted", and "constraint" which are all described below. The "accepted" variable is used when an agent is interested in what values are in the Acceptable List, for instance whenever the agent is determining if certain values are acceptable. A rule using "accepted" will fire if there exists any value in the acceptable list which allows the rule's conditions to be satisfied.

The "next" variable would be useful if an agent was interested in what the next alternative from the Selection List would be, since that is the value that the agent might be forced to agree to if it signals a conflict and enters negotiations.

The "constraint" variable is available so that agents can include the effects of relaxing their constraints. This variable counts how many times the agent has agreed to relax its constraint. Constraints can be relaxed during negotiations, but they have no effect unless "constraint" is used at some point during the Conflict Detection Rules. The value of "constraint" starts at zero, and increases by one every time it is relaxed. This scheme was chosen because of the way Conflict Resolution had to be implemented. Specifically, Conflict Resolution has an option for relaxing the constraint, but no definition of what this means is possible. Therefore, it simply records how many times the constrain has been relaxed, and the Conflict Detection is responsible for using this information. An example is included in the third line of Table A.2

------------------------------------------

A.6 Conflict Resolution Options

Conflict Resolution Rules are determined by the Resolution Options, shown in the lower left of Figure A.2.

The Conflict Resolution rules are arguably the most important. They determine how agents resolve their conflicts with other agents. Unlike the other rule sets, the Conflict Resolution Rules are not explicitly written by the user. Instead, the user uses SiFAKA to select which options should be included in the resolution strategy. The user can select any combination of the items shown in Table A.3. The exact effects of each of these options is unimportant. The Clipsifier will alert the user when inappropriate options have been selected, such as "Give an Alternative" when the agent has no Selection List.

------------------------------------------

A.7 Format for Selection and Conflict Detection Rules

Selection Rules and Conflict Detection Rules both follow the same format. Figure A.3 shows the BNF representation of rules, followed by an explanation in English. Terminals such as IF and THEN, are not entered by the user but are part of the Intermediate Language.

<Selection-Rule> :== IF <Condition>, THEN <Value>

<Conflict-Detection-Rule> :== IF <Condition>, THEN <Action>

<Condition> :==   <Value> <Boolean-Operator> <Value>
                | ( <Condition> ) <Boolean-Logic> ( <Condition> )
                | <Value> within <Value>[%] of <Value>

<Boolean-Operator> :== < | > | =

<Boolean-Logic> :== and | or

<Value> :==   <Constant-Numeric-Value>
            | <Constant-Symbolic-Value>
            | <Target-Name>
            | accepted | constraint | next | basis
            | ( <Value> <Mathematical-Operator> <Value> )

<Mathematical-Operator> :== + | - | * | /

<Action> :==   conflict <Text-Message>
             | ignore <Text-Message>
             | accept <Value>
Figure A.3: BNF Representation of Rules

In its most basic form, expressions for conditions are composed of an operator and two operands (with one exception, explained later). The consequence (or action) has one operator and one operand (selection methods have only one possible action, so it is assumed and not explicitly written).

Valid operators are:

		=	Equals
		<	Less than
		>	More than
		within	Close to a value
		and	Logical AND
		or	Logical OR
		+	Addition
		-	Subtraction
		*	Multiplication
		/	Division
Valid operands are:

Operands can be written using other operands. For instance, numerical operands (used for "=", "<", ">", and "within") can be constructed using the mathematical operands ("+", "=", "*", and "/"), but the logical AND and OR operands should not be used since these result in a Boolean value. Numerous examples will be given below.

Since space is limited in the SiFAKA editor to type in rules, abbreviations for common keywords are recognized. Specifically, "cons" and "constr" have the same meaning as "constraint". Also, "acc" is an alternative to "accepted". It is very important that these keywords are not used as names for a target in the system.

The only exception to the operand/operator structure is the within condition operator. Since it requires three values, it's syntax is:

operand within operand of operand

where every operand is a number (or next, accepted, constraint, a target, or a function which has the value of a number).

To illustrate the capabilities of the Intermediate Language just described, the following is a list of example conditions for rules.

Table A.4: Example Conditions Using Boolean Operations

     IF: (MATERIAL = 'wood) and (COLOR = 'red)
     IF: (MATERIAL = 'metal) and (THICKNESS < 0.3)
     IF: (MATERIAL = 'metal) and (WEIGHT within 50% of 9.0)
     IF: (MATERIAL = 'wood) or (MATERIAL = 'plastic)

Table A.5: Example Conditions Using Mathematical Operations

     IF: (DEPTH * WIDTH) > 4.0
     IF: ((DEPTH * WIDTH) * HEIGHT)) > 8.0
     IF: ((DEPTH + WIDTH) + HEIGHT)) within 30% of SURFACEAREA
     IF: DEPTH within (30 * constraint)% of HEIGHT

Since there is limited room in the window into which conditions are entered, using long target names (such as those used above) may prohibit complex combinations of functions. Long conditions actually can be entered into SiFAKA, but long rules will not be entirely displayed at one time. Therefore, short target names should be used so that the rules can be read easier.

For more information on the Intermediate Language, consult the MQP report referenced at the beginning of this document.

------------------------------------------

User's Guides are available for the other two components of SiFASyB:

------------------------------------------

<<<< To SiFA Home Page

Written by: markts@wpi.wpi.edu

[Feedback] [Search Our Web] [Help & Index]

[Return to the WPI Homepage] [Return to CS Homepage]

dcb@cs.wpi.edu / Aug 6, 1996