Structured Knowledge Description Language

to Represent Objects and Knowledge of an Agent

in response to

FIPA's First Call for Proposals


10 January 1997

Key-Sun Choi, Woon-Jae Lee, Seongyong Kim, Jun-Sik Park, and Namil Kim


Korea Advanced Institute of Science and Technology

Center for Artificial Intelligence Research

Department of Computer Science

kschoi@cs.kaist.ac.kr

Table of Contents

Abstract
1. Introduction
2. Categories of Objects and Knowledge Representation Schemes
3. Standard Generalized Markup Language(SGML)
4. Structured Knowledge Description Language(SKDL)
4.1 General Structure of SKDL
4.2 Specialization of SKDL to an Agent
4.2.1 SKDL Elements
5. An Example Description of SKDL for Personal Travel Assistance
6. Related Technologies
7. Conformance to the Criteria
8. Conclusion
References
Appendix A: a Preliminary Research for SKDL - Text and Dictionary Management System / Standard Dictionary Markup Language (TDMS/SDML)
A.1 Standard Dictionary Markup Languages (SDML)
A.2 The Structure of Text and Dictionary Management System
A.2.1 Standard Dictionary (SD)
A.2.2 Standard Dictionary Editor (SDE)
A.2.3 SD Encoder/SD Decoder

List of Figures

<Figure 1> General structure of SKDL
<Figure 2> Header and definition part of SKDL
<Figure 3> The initial definition of <body>
<Figure 4> An example of body structure modification
<Figure 5> An example of the structure of an SKDL-formatted document for database store
<Figure 6> The reference model of human/agent and agent/agent communication in PTA
<Figure 7> Step1: Natural language sentence as the output of Speech Recognition Agent
<Figure 8> Step2: Meaning for the NL sentence as the output of NL Understanding Agent
<Figure 9> Step3: Plan for the meaning of the NL sentence as the output of Planning Agent
<Figure 10> Message Broker Agent as a message distributor among agents
Figure A.1. The Structure of TDMS 17

Abstract

An agent actively tackles a given situation to form a goal and to set a sequence of actions to reach the goal. In that process, the agent needs to have the ability to store, retrieve, and manipulate its knowledge. It also should be able to get necessary knowledge from other agents through agent/agent communication and to deliver its processing results upon other agents' requests. It entails that an agent should have a method, i.e., a language, for describing and managing those knowledge for internal representation or external communications.

It is desirable to represent knowledge both internal to the agent and for external communication by the same, uniform description language. This language must have the following features: a) independence of the types of agents and software, b) ability to represent various information and knowledge, c) to support human/agent and agent/agent communications with no difficulty, and d) to comply with standards.

In this proposal, we present, as the agent's objects and knowledge description method, Structured Knowledge Description Language (SKDL) which is based on Standard Generalized Markup Language (SGML). SKDL can describe and manipulate various objects and knowledge in a uniform fashion and can support the communications between agents. SKDL is an indispensable method for representation and manipulation of the agent's objects and knowledge.

Keywords: Structured Knowledge Description Language (SKDL), Knowledge Representation (KR), Knowledge Management, SGML

1. Introduction

We can assume the following steps for agent/agent communications and human/agent interactions [Hodgson]:

  1. "The communication unit of an agent is an utterance. The utterance is a sentence, which is made up of a sequence of words."

The communication unit can be one of the following: a set of pre-defined messages (primitive), a set of message templates (intermediate), sublanguage (controlled), or full natural language (human-oriented) [Choi 97]. The details of those levels are discussed in that proposal, so we omit the explanation here. The utterance (sentence) in this proposal means one of the four types of messages.

  1. "An agent(A) receives an utterance and analyze (parse) the sentence."
  2. "The agent(A) assigns a meaning to the parsed sentence." The Structured Knowledge Description Language (SKDL) is needed in this step.
  3. "The agent(A) forms a plan to respond to the given utterance, and may co-operate with other agent(B) to execute the plan. This co-operation will be represented as a sequence of actions that will be executed by the agent(B)."
  4. "The agent(A) requests to the agent(B) to execute corresponding actions. In other words, the agent(A) needs to form an utterance which is delivered to the agent(B)."

An agent actively tackles a given situation to form a goal and to set a sequence of actions to reach the goal. In that process, the agent needs to have the ability to store, retrieve, and manipulate its knowledge. It also should be able to get necessary knowledge from other agents through agent/agent communication and to deliver its processing results upon other agents' requests. It entails that an agent should have a method, i.e., a language, for describing and managing those knowledge for internal representation or external communications.

It is desirable to represent knowledge both internal to the agent and for external communication by the same, uniform description language. This language must have the following features: a) independence of the types of agents and software, b) ability to represent various information and knowledge, c) to support human/agent and agent/agent communications with no difficulty, and d) to comply with standards. In order to share the same or redundant information or knowledge among several agents, the shared objects should be given in a general and flexible format. Some formatted information such as database entity need not to be re-compiled for uniform representation, however, since this kind of information may need to be compiled only upon request during the execution of corresponding agents. We propose Structured Knowledge Description Language (SKDL), based on Standard Generalized Markup Language (SGML), as the agent's objects and knowledge description language.

In step 3 of the aforementioned assumption, for example, an agent can keep its parsed sentence meaning in Prolog representation form. This kind of internal representation can differ according to the types or characteristics of agents. But, the internal representation should be of uniform format for inter-agent communications. The description language for this purpose is SKDL, which can fulfill the necessary features given above.

The first Call for Proposals(CFP) of FIPA addresses agent technologies (Chapter 5) about agent management, human/agent and agent/agent communication, and agent/software interaction. But, it does not address the technology for objects and knowledge representation (description) of an agent. The Agent Interface Description Language (AIDL) has somewhat similar features to this SKDL, but the former focused on the external features of an agent such as agent identification whereas the latter focused on both objects and knowledge that an agent can deal with. Thus, it seems necessary to include this sort of agent technology in the specification.

2. Categories of Objects and Knowledge Representation Schemes

Objects that are to be handled by an agent can be physical objects or the knowledge representation of them. Physical objects include text, database entity, drawings or images, audio/visual objects, and objects that have application-specific structures. The knowledge representation can be of four categories of schemes according to [Mylopoulos 84]:

  1. Logical representation schemes: uses expressions in formal logic to represent a knowledge base. (e.g. Prolog is the ideal programming language for implementing these schemes.)
  2. Procedural representation schemes: represent knowledge as a set of instructions for solving a problem. (e.g. production systems)
  3. Network representation schemes: capture knowledge as a graph in which the nodes represent objects or concepts in the problem domain and the arcs represent relations or associations between them. (e.g. semantic networks, conceptual dependencies, conceptual graphs)
  4. Structural representation schemes: extend networks by allowing each node to be a complex data structure consisting of named slots with attached values. (e.g. scripts, frames, and objects)

The problems of an agent is mainly related to the problems of searching appropriate objects or knowledge and of applying retrieved knowledge to certain actions. Hence, those objects and knowledge need to be represented in an appropriate structure for the processing by an agent. In addition, since an agent may send to or receive from other agent objects and knowledge in different message levels as depicted in [Choi 97] (primitive, intermediate, controlled, human-oriented), the description language should cope with this issue.

In the following sections, Standard Generalized Markup Language (SGML) is briefly explained and SKDL will be described in turn.

3. Standard Generalized Markup Language(SGML)

SGML is a meta-language that defines a syntax of a markup language. Once SGML defines a structure for documents, then the documents are marked up according to the structure. This definition of document structures is called Document Type Definition (DTD), and the marked up document by that DTD is called Document Instance (DI) [Bryan 88, Goldfarb 90].

SGML defines the logical structure of a document and leave the freedom of defining the physical structure to anyone as needed. This feature makes it possible to extract and handle only necessary parts from a common document format, independent of the application program thereof. In the process of publishing documents using SGML, for example, once the whole document were marked up by a DTD, each application programs such as editing, proofreading, composing, or illustration programs can then handle only relevant parts of the document, and hence can get better performance [Travis 95].

However, SGML has so broad coverage that implementing whole functionality is quite difficult. Therefore, it is a natural tendency to use a restricted form of SGML. Hypertext Markup Language (HTML) is one of such examples. It is a subset of SGML and focuses mainly on document formatting and hyperlink. The lack of functionality in HTML carries difficulty in representing knowledge of an agent.

4. Structured Knowledge Description Language(SKDL)

SKDL in this proposal can be viewed as a subset of SGML, and can provide a guideline for representing inter-agent communication parameters and shared information/knowledge among agents.

4.1 General Structure of SKDL

SKDL is composed of three parts: header (skdlHeader), definition part(front), data part(body). Header has information including ID, name, type, and the definition part prescribes attribute/value pairs which are to be used in the data part. Figure 1 show a general structure of SKDL. Figure 2 depicts the detailed structure of the header and the definition part.

<SKDL type=angent_service_type>

<skdlHeader> [header information] </skdlHeader>

<front> [definition of attribute - value pairs] </front>

<body> [SKDL elements] </body>

</SKDL>

  • <Figure 1> General structure of SKDL

    <skdlHeader>

    <skdlID> [SKDL ID] </skdlID>

    <skdlName> [SKDL name] </skdlName>

    <skdlVer> [version number] </skdlVer>

    <skdlType> [SDKL type] </skdlType>

    <skdlDate> [date and time of creation] </skdlDate>

    <skdlAgent> [skdl creation agent] </skdlAgent>

    <skdlNote> [explanation] </sdNote>

    </skdlHeader>

    <front>

    <attrdefgroup>

    <attrdef> [definition of an attribute] </attrdef>

    <attrdef> [definition of an attribute] </attrdef>

    [repetition of attrdef's]

    </attrdefgroup>

    <valdefgroup>

    <valdef> [declaration of an attribute value] </valdef>

    <valdef> [declaration of an attribute value] </valdef>

    [repetition of valdef's]

    </valdefgroup>

    </front>

    <attrdef>

    <attrname> [attribute name] </attrname>

    <attrlist>

    <attr> [real attribute]</attr>

    [repetition of attr's]

    </attrlist>

    </attrdef>

    <valdef>

    <valname> [value name] </valname>

    <vallist>

    <val> [real value]</val>

    [repetition of val's]

    </vallist>

    </valdef>

  • <Figure 2> Header and definition part of SKDL

    4.2 Specialization of SKDL to an Agent

    Each individual agent specializes and adjusts the basic structure to define the messages that it can handle.

    4.2.1 SKDL Elements

    An element can consist of one simple field or have the form of complex tree structure. For this purpose, the agent developer identifies necessary SKDL elements and defines the body so that the necessary elements can reflect an appropriate structure in the body. This specialized body part follows the general format of SGML but has some restrictions so that the resultant structure can easily be implemented. The following are some examples of such restrictions.

    1. Basic elements of SGML content model adopted in SKDL are only "," (sequence connector), "|" (or connector), "*" (optional and repeatable occurrence indicator), "+" (required and repeatable occurrence indicator), "?" (optional occurrence indicator).
    2. If there exists a defined tag already in the SKDL, then the developer uses it rather than create a new tag to guarantee the compatibility.
    3. Attributes used in the body are defined by "ATTLIST" command. However, these attributes must be defined and their values declared in the definition part (front) in order to be properly handled by an application program such as SKDL editor.

    The <body> is initially defined as depicted in Figure 3. Therefore, if the developer wants to modify the structure, then he may overwrite those elements which he wants to modify. Figure 4 shows an example of such modification, and Figure 5 depicts an example of the structure of an SKDL-formatted document for database store.

    <!ELEMENT body - - (#PCDATA)* >

  • <Figure 3> The initial definition of <body>

    <!DOCTYPE skdlf SYSTEM "skdl.dtd" [

    <!ELEMENT body - o (sen-tree)+ >

    <!ELEMENT sen-tree - o (agent,action,object?,time?) >

    <!ELEMENT agent - o (#PCDATA) >

    <!ELEMENT action - o (tense,verb) >

    .....

    ]>

  • <Figure 4> An example of body structure modification
    id tag name attribute parent sibling child content
    0 SKDL PTree x x 1  
    1 skdlHeader   0 12 2  
    12 body   0 x 13  
    13 sen-tree   12 nnn 14  
    14 agent   13 15 x I
    15 action   13 18 16  
    16 tense   15 17 x must
    17 verb   15 x x meet
    18 object   13 nnn 19 M. Kane
  • <Figure 5> An example of the structure of an SKDL-formatted document for database store

    5. An Example Description of SKDL for Personal Travel Assistance

    Let's assume the following situation to show an example of SKDL description for PTA. A traveler requests the following to the User Interface Agent (UIA) using a telephone call.

    "I must meet M. Kane of Rosebud company in New York in the afternoon of the 29th of September. Plan me a trip for this appointment. I would like an answer by tomorrow evening, take my standard preferences into account."

    The reference model for this human/agent and agent/agent communications is shown in Figure 6.

  • <Figure 6> The reference model of human/agent and agent/agent communication in PTA

    • The operational concept of Figure 6 is as follows.

    1. UIA receives the voice of a traveler and passes it to the Speech Recognition Agent. Speech Recognition Agent recognizes a natural language sentence and sends it back to the UIA (Figure 7).

    <SKDL type=NLSen>

    <skdlHeader> .....

    <body>

    <sen> I must meet M. Kane of Rosebud company in

    New York in the afternoon of the 29th of

    September.

    <sen> Plan me a trip for this appointment.

    <sen> I would like an answer by tomorrow evening,

    take my standard preferences into account.

    </body>

    </SKDL>

  • <Figure 7> Step1: Natural language sentence as the output of Speech Recognition Agent

    2. UIA passes the natural language sentence (result of step 1) to Natural Language (NL) Understanding Agent, and then the latter agent parses the message and returns the meaning (parse tree or concept) to the UIA (Figure 8).

    <SKDL type=PTree>

    <skdlHeader> .....

    <body>

    <sen-tree>

    <agent> I

    <action>

    <tense> must

    <verb> meet

    <object> M. Kane

    <of> Rosebud company

    <in> New York

    <time> afternoon

    <of> 29th, September

    </sen-tree>

    .....

    </body>

    </SKDL>

  • <Figure 8> Step2: Meaning for the NL sentence as the output of NL Understanding Agent

    3. UIA receives the result of step 2 and then passes it to Planning Agent. Planning Agent develops a plan for the message and returns it back to UIA (Figure 9).

    <SKDL type=plan>

    <skdlHeader> .....

    <body>

    <plan>

    <action_class> plan_trip

    <Actor> user

    <path> PATH

    <Desstination> New York

    <preconditions> ....

    <decomposition> ....

    </plan>

    <plan>

    <action_class> ....

    .....

    </body>

    </SKDL>

  • <Figure 9> Step3: Plan for the meaning of the NL sentence as the output of Planning Agent

    4. UIA gets the plan from Planning Agent and passes it to either Travel Service Agent or Broker to get a desirable response.

    During this process, the UIA determines if the received message meets its interest. This can be determined by investigating the header's type information. When the UIA transmits its requesting message to other agents, it actually passes the message to Message Broker Agent, which then decides appropriate destination of the message and delivers as such. The Message Broker Agent therefore keeps the information about other agents and their interests (processing message types). Figure 10 depicts such notion.

  • <Figure 10> Message Broker Agent as a message distributor among agents

    • 6. Related Technologies

    An agent should not only be able to parse SKDL to get necessary information and to identify its contributability to the message but also be able to construct an information or request in SKDL form to get other agent's co-operation. For these functionalities, an agent should interface to SKDL parser and SKDL generation software. In addition, to get necessary information from Common Knowledge Base (see Figure 6), the following agents have to be involved in the overall process.

    1. Common Knowledge Management Agent with Structured IR System
    2. SKDL Agent: Each agent should clearly define its SKDL interface format because every message to / from the agent is encapsulated by SKDL. SKDL Agent takes a role as an interface format design tool for that agent. SKDL Agent also collects information about other agents' task types and interface formats with the help of Message Broker Agent, in order to advise the current agent in developing functionalities for co-operation. When an agent's interface format and task types are developed, the developer then register them to the Message Broker Agent.
    3. Message Broker Agent: As mentioned before, this agent identifies the types incoming messages and passes them to the appropriate agents for action. For the unregistered message format, however, the agent may get a help from other Message Broker Agent or returns error message to the message sender. And, it can deliver information about message formats to the SKDL Agent upon request.

    7. Conformance to the Criteria

    In Introduction, we discussed that SKDL is one of indispensable agent technologies but the current CFP doesn't address the corresponding area of technologies. We presented the following criteria for such technology branch, and through the main body of this proposal we think the proposed SKDL complies to them.

    1. Independence of the types of agents and software
    2. Ability to represent various information and knowledge
    3. To support human/agent and agent/agent communications with no difficulty
    4. To comply with standards.

    In addition to the conformance to the criteria, SKDL has several advantages as a knowledge representation scheme: a) Because SKDL is based on SGML, it can store information and knowledge into database with uniform formats. This further makes it easy to share objects and knowledge among agents; b) a document encoded in SKDL reflects its structure so that fine-grained and thus accurate retrieval results can be found. Also as a message content description language, SKDL preserves independence of agent or software characteristics while supports the agents various knowledge representation forms and communication capability.

    8. Conclusion

    To achieve a goal with co-working various agents, it is necessary to define a standard description method of knowledge used in inter-agent communication and common knowledge sharing. In this proposal, we defined SKDL, described some characteristics of it, and showed that it complies to the following features: a) independence of the types of agents and software, b) ability to represent various information and knowledge, c) to support human/agent and agent/agent communications with no difficulty, and d) to comply with standards. We described as a possible application the PTA using SKDL and Message broker to show that SKDL can simplify and make clear the problem when used in an agent system. In appendix A, we enclosed a preliminary research work on Text and Dictionary Management System / Standard Dictionary Manipulation Language (TDMS/SDML) to show the possibility of a standard method for objects and knowledge representation, store, and retrieval.

    References

    [Hodgson] J.P.E.Hodgson. Agents that communicate. (http://www.sju.edu/~jhodgson/ugai/commun.html)

    [Choi 97] Key-Sun Choi, Jun-Sik Park, Namil Kim, Seongyong Kim, and Woon-Jae Lee. January, 1997. Classification of message levels and the use of machine translation technology for the flexible communication between agents. A proposal in response to FIPA's first Call for Proposals.

    [Mylopoulos 84] J. Mylopoulos and H.J.Levesque. 1984. An overview of knowledge representation. In M.L.Brodie, J. Mylopoulos, and J.W.Schmidt (eds.), On Conceptual Modeling. New York: Springer-Verlag.

    [Bryan 88] Bryan, M.(1988), SGML: An Author's Guide to the Standard Generalized Markup Language, Addison-Wesley.

    [Goldfarb 90] Charles F. Goldfarb, " The SGML Handbook," Clarendon Press, Oxford, 1990.

    [Ide 95] Nancy Ide and Jean Veronis, "Text Encoding Initiative Background and Context," Kluwer Academic Publishers, 1995.

    [ISO 94] "Information technology - Text and office systems - Document Style Semantics and Specification Language(DSSSL) - Draft", ISO/IEC DIS 10179.2, 1994.

    [Travis 95] Travis, B. E. and Waldt, D. C. "The SGML Implementation Guide," Springer-Verlag Berlin Heidelberg, pp3-20, 1995.

     

    Appendix A: a Preliminary Research for SKDL - Text and Dictionary Management System / Standard Dictionary Markup Language (TDMS/SDML)

    As the first step to testing the specification of SKDL, we developed an Standard Dictionary Markup Language (SDML) and constructed Text and Dictionary Management System (TDMS) for its application.

    A.1 Standard Dictionary Markup Languages (SDML)

    The standard dictionary formats have all the information on the base of TDMS. These information is composed of two kinds of information. One is required by the standard dictionary editor (SDE) to edit and maintain the dictionary. The description format of the dictionary entry and the pointer tag for a hypertext are the examples of the maintaining information. The other is required by the application dictionaries. The functional description with SGML for the format and content of dictionaries are included here. In general, a dictionary consists of many entries with headwords as its indexes. The entry structures are subject to change according as the headword's features. SDML is a subset of SGML, which restricts some SGML functions only to describe the structure of a dictionary.

    A.2 The Structure of Text and Dictionary Management System

    TDMS consists of 3 components, e.g. Standard Dictionary (SD), the format of which is defined in a subset of SGML, Standard Dictionary Editor (SDE) which creates, edits and browses the SD, and SD Encoder & Decoder which can transform both non standard dictionary format into SD format and SD into various dictionary formats according to the application.

    A.2.1 Standard Dictionary (SD)

    Standard Dictionary is defined in a subset of SGML and holds various forms of each dictionary. In the structure of SD the tag set is used which is described in SGML DTD (Document Type Definition). All the information of dictionary is represented in text form, therefore we need not have any special program in order to see the lexical information in SD. In front of SD there is a pre-defined part of the logical structure , with which we can examine the lexical structure during the parsing.

    Such a lexicon structure is in fact based on the DTD definition in SGML, which represents the logical structure of the lexicon according to the SGML definitions. On the basis of this structure we make a Standard Dictionary Format (SDF).

    A.2.2 Standard Dictionary Editor (SDE)

    The Standard Dictionary Editor is used not only for editing and modifying the contents and structure of SD, but for retrieving and browsing the lexical information. The information of one lexical entry is represented in a window per default, and if there is not enough space for the explanation of a entry, the system supports the scrolling of window.


  • Figure A.1. The Structure of TDMS

    Because each dictionary has its own structure, it is not easy to find a meaningful structural description. We need to have a flexible means to represent the internal structure. We must seize the structure of SD and make the system dynamic to present information of each entries on it. In TDMS we have the following function related with this purpose.

    1. Function to interpret the DTD of SGML and to define it as a internal structure.
    2. Function to understand the SD and assign data into the internal structure.
    3. Function to transform of the internal structure into the textual linear form in SD.

    We can also create a new dictionary from the existing dictionary, i.e. we can make a dictionary by merging two different dictionaries, or we can make a dictionary from one dictionary by extracting needed information (by change of structure).

    A.2.3 SD Encoder/SD Decoder

    Many dictionaries for NLP systems are saved (or defined) in binary file, or in text file according to their application. These types of dictionaries can be converted into SD by SD-Decoder and SD into another dictionaries by SD-Encoder.

    Dictionaries which are used for the application programs are very different in their structures. In our implementation we provide a tool for the conversion of dictionaries only for some application, which is most used. (e.g. trie, tree, hash etc.) For the forms which are not supported by our system, one should develop a converter for himself in order to use the SDE.