Integrating Ontologies into Multiagent Systems Engineering Jonathan DiLeo1, Timothy Jacobs2, Scott DeLoach3 1 College of Aerospace Doctrine, Research and Education, 620 Chennault Circle, Maxwell AFB, AL, USA 36112-6428 [email protected] 2 Air Force Institute of Technology, AFIT/ENG, 2950 P Street, Building 640, Wright-Patterson AFB, OH, USA, 45433 [email protected] 3 Kansas State University, Department of Computing and Information Sciences, 234 Nichols Hall, Manhattan, KS 66506 [email protected] Abstract. Multiagent systems have received much attention in recent years due to their advantages in complex, distributed environments. A number of methodologies have been proposed for engineering multiagent systems, however, these methodologies do not adequately address the information domain of the system, which is an integral part of designing proper system execution. Previous work at the Air Force Institute of Technology (AFIT) has developed a methodology for analyzing, designing, and developing multiagent systems, called Multiagent Systems Engineering (MaSE). This research extends the MaSE methodology to include the use of ontologies for information domain specification. The extensions allow the designer to specify information flow by using objects from the ontology as parameters in agent conversations. The developer can then ensure system functionality by verifying that each agent has the information required to accomplish the system goals. Introduction In recent years, interest in multiagent systems has increased as software designers look for new methods of solving problems in complex environments. As agent technology has progressed, research into agent-oriented software engineering has attempted to develop methodologies to help develop robust and reliable multiagent systems [10]. Constructing multiagent systems involves all the problems of traditional distributed systems along with the problems that arise from the behavior of the individual agents. For instance, the individual behavior of the agents can combine to form emergent system behavior that is adverse to proper system execution. Designers need an engineering approach for system development of multiagent systems to address and avoid these problems. Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2006 2. REPORT TYPE 00-00-2006 to 00-00-2006 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER Integrating Ontologies into Multiagent Systems Engineering 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION College of Aerospace Doctrine, Research and Educaiton,620 Chennault REPORT NUMBER Circle,Maxwell AFB,AL,36112-6428 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES The original document contains color images. 14. ABSTRACT see report 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE 15 unclassified unclassified unclassified Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 Integrating legacy systems further increases the difficulties of designing multiagent systems due to the varying semantics of different information systems. Different systems can have different terms that represent the same concept, introducing a complication in integrating the systems. Any complete methodology for building multiagent systems must address the data models used by the system and the individual components in the system. Currently several methodologies exist for building multiagent systems, each varying in their level of development [5,9,15]. MESSAGE [5] is one of the few methodologies that address the information domain of the system. Just as important as the system’s representation of the information domain is the various agents’ information domain view. Heterogeneous systems can contain agents with differing data models, a case that can occur when reusing previously built agents or integrating legacy components into the system. Most existing methodologies lack specific guidance on the development of the information domain specification for a multiagent system and for the agents in the system. Failure to incorporate information domain specifications results in designs that do not fully address multiagent system behavior. The interaction between agents in the system frequently occurs through communication. Although communication can occur by the simple passing of performative messages, systems of a complex nature will require the passing of information between agents in the form of parameters. Without specifying the information domain of the system, the designer cannot specify what data types are passed as parameters and cannot describe the information flow in the multiagent system. The Multiagent Systems Engineering (MaSE) methodology has been developed at the Air Force Institute of Technology (AFIT) to assist in the development of multiagent systems by leading the designer from the initial system specifications to a set of formal design models [3]. The transformations from each step in MaSE are formally defined and provide the engineering approach needed for multiagent system engineering. Despite its benefits in multiagent systems design, MaSE does not currently address the design of the information domain, leading the developer to construct a set of design documents that do not fully specify the semantics of the data passed between agents. In this paper, we expand MaSE to include ontologies as a mechanism for specifying the information domain of the system and the individual agents. The next section presents an overview of MaSE before ontologies were introduced, followed by a discussion of the changes made to the methodology. The extended MaSE is analyzed in a later section based on experiences of using it to design a distributed course scheduling system. Background – Multiagent Systems Engineering The Multiagent Systems Engineering (MaSE) methodology has been researched at the Air Force Institute of Technology for the last few years. Research focuses on developing a robust methodology for constructing multiagent systems. MaSE divides the development of multiagent systems into analysis, design, and implementation phases [3]. MaSE originally consisted of three steps in the analysis phase and four steps in the design phase as shown in Figure 1. The developers of MaSE intended for these phases and steps to be applied iteratively. During system implementation the models from the analysis and design phases are used to program the system into code. This paper discusses the addition of the System Ontology step, shown in Figure 1, into the MaSE methodology. Requirements Capturing Goal Hierarchy Goals Use Cases Applying Use Cases Sequence A Diagrams n a ly s is System Building Ontology Ontology Concurrent Roles Refining Roles Tasks Agent Creating Agent Classes Classes Constructing Conver- D sations Conversations e s ig Assembling n Agent Architecture Agent Classes Deployment System Design Diagrams Fig. 1. Extended MaSE Phases, Steps and Models Analysis Phase The Analysis Phase is concerned with establishing a set of roles and assigning tasks to those roles to describe the system requirements. The Capturing Goals step starts this phase with the transformation of the initial system specification into a goal hierarchy. This step allows the designer to organize the goals that the system needs to accomplish. The basic scenarios that the system should perform are captured in the Applying Use Cases step. Use cases are created and then transformed into sequence diagrams. The final step of analysis, Refining Roles, uses the outputs from the previous two steps to create roles and assign the tasks to be performed by those roles in the system. Tasks are associated with each role to describe the behavior that the role must have to accomplish its assigned goals. Figure 2 is an example of a Role Model in MaSE, that indicates the goals each role is assigned, the tasks associated with each role, and the communication between the tasks using the protocols indicated by arrows. Fig. 2. Example MaSE Role Model [2] Fig. 3. HandleTasking Concurrent Task Diagram [2] Tasks are defined graphically using a finite state automaton, as shown in the Concurrent Task Diagram of Figure 3. Transitions in the concurrent task diagrams follow the syntax trigger [guard] ^ transmission(s). This syntax represents that a transition is enabled only when the event trigger occurs and the condition guard evaluates to true. When the transition is executed, the specified transmission(s) will be executed by the role. Once in a state, the task remains in that state until all actions defined in that state have been completed and a transition out of the state has been enabled. Design Phase Once the requirements for the system have been modeled during the Analysis Phase, the design of the multiagent system begins. The first step in the Design Phase is Creating Agent Classes, where the roles are assigned to specific agent classes. This step creates an Agent Class Diagram, as shown in Figure 4, that shows the classes in the system, the roles played by the agent classes (listed under the agent class name), and the conversations between classes (denoted by arrows pointing from the initiator class to the responder class). Fig. 4. Example Agent Class Diagram [3] Details of the conversations are defined in the Constructing Conversations step, where finite state automata are used to show the states in a conversation. Each conversation has two diagrams: one for the initiator and one for the responder of the conversation, with Figure 5 demonstrating the diagram for the initiator of the RequestNotification conversation of Figure 4. The set of conversations that an agent class participates in is derived from the communications of the roles that the agent plays. For example, the FileNotifier and AdminNotifier roles are defined by concurrent tasks that communicate with each other. Since these two tasks are in separate agent classes in Figure 4, this communication becomes the RequestNotification conversation. The third step in design, Assembling Agent Classes, defines the components of the agent architecture, allowing for the logical decomposition of agents. The final step of System Design creates a Deployment Diagram to show the amount and location of each type of agent in the system. The outputs from the design steps describe the actions and conversations used in the multiagent systems. The semantics of the parameters passed in those conversations were not previously defined in the MaSE process. Fig. 5. RequestNotification Conversation Diagram [3] agentTool agentTool is an automated development environment that supports the MaSE methodology by allowing the designer to create the MaSE Models in a graphical environment [3]. Using transformations defined in [13], agentTool allows for the automatic generation of design documents based on the role models and task diagrams. Once the designer specifies the system in agentTool, the program can output Java code for the system. Because information domain specifications are not incorporated in the MaSE methodology, the code produced from agentTool classifies all parameters as Java Objects. The implementer must then go through and change the declarations to the appropriate data structure used to represent the semantic concepts of the parameters. Including the construction of the system data model removes the necessity of this step, as the parameters can automatically be specified as the correct type. Including Ontologies in Multiagent Systems Engineering The word ontology was taken from philosophy where it represents the study of the nature of being. Much debate exists on the exact definition of an ontology when used for knowledge engineering or artificial intelligence [8]. The most common definitions state that an ontology is a specification of a conceptualization [7] or that an ontology is the shared understanding of some domain of interest [14]. This research uses the latter definition, specifically that an ontology defines classes, functions, object constants, and axioms to constrain meaning of some type of world view of a given domain. The classes in an ontology describe the objects in the system’s view of the information domain. The functions and object constants define the properties of and relationships between those objects. The analyst uses axioms to describe any additional relationships or restrictions on concepts in the ontology. For instance, an axiom might specify that a student must be registered or signed up to take at least one class. With these concepts, the ontology describes the concepts and relationships used to interact in the domain. In this research, we use ontologies to specify the information domain of a multiagent system. Just as it is important to specify the data model in a traditional software development process, the data model for a multiagent system must also be specified. The agents in the system interact by passing messages and these messages frequently involve passing parameters. These parameters are objects of some sort, and without an information domain specification, the methodology cannot address the information contained in these parameters. To use ontologies to describe the information domain of a system in MaSE, this research introduces a new step in which the designer constructs the ontology for the system during the MaSE analysis phase. We determined the step should occur after the Applying Use Cases step. This placement allows the designer to use terms from the goal hierarchy, use cases, and sequence diagrams as possible concepts in the ontology. The resultant ontology can be used to create tasks in the refining roles step of MaSE. Tasks often indicate parameter passing, so the step is placed after the construction of the ontology to allow the designer to specify the type of the parameters as classes from the ontology. The extended MaSE diagram is shown in Figure 1. Constructing Ontologies for Multiagent Systems An appropriate methodology for developing ontologies must be defined for designers to use for specifying domain representations in multiagent systems. The existing methodologies for designing domain ontologies are built to describe everything about a specific domain; however, this is not appropriate for multiagent systems because the system ontology should only specify the information required for proper system execution. The system ontology acts as a prerequisite for future reuse of the system, as the ontology specifies the view of the information domain used by the multiagent system. Any system that reuses the developed multiagent system must ensure that the previously developed system ontology does not conflict with the ontology being used in the new system. Reinventing the wheel, by developing a whole new methodology, does not make sense, because many years of research have gone into developing domain ontology methodologies. Instead, we extract the main steps common to the IDEF5 and Methontology methodologies [11,6]. To construct the ontology, the designer first determines the purpose and scope of the ontology and then collects and analyzes data from the information domain for possible use in the ontology. Finally, the analyst constructs the initial ontology and refines, validates, and matures the model into a complete ontology. Each of these steps is discussed in detail below. Define Purpose and Scope of Ontology The designer must describe why the ontology is being developed as well as the range of intended users of the ontology. This facilitates ontology reuse by allowing others to quickly see the reason the ontology was constructed and what information the ontology contains. For example, when designing a multiagent system to perform course scheduling, the ontology must define classes regarding courses, quarters, instructors, classrooms, etc. The software requirements and the goal hierarchy help define the purpose of the ontology, as the purpose of the ontology is to fulfill the information needs of the multiagent system. The purpose describes why the ontology exists, such as to list all classes in the education domain required when scheduling courses. The scope defines the level of detail to which the ontology describes the objects, such as defining only the semantic ideas necessary to schedule courses in a distributed network environment. To further define the scope, the designer can utilize the previously identified use cases to determine the types of data that the system will use. For example, a use case may describe one agent passing another agent a specific course to schedule. The designer uses this situation to determine the level of detail necessary to describe a course so that the system can properly execute the events described in the use case. Collect Data Having defined the scope, the analyst knows the level of detail and domain the ontology represents and can start building the model. The designer first creates a list of possible terms or concepts that the ontology must describe. Designers form this list by examining the goal hierarchy, use cases, and sequence diagrams from the previous MaSE steps for candidate ontology terms. The analyst looks for nouns in these models that could represent some type of information in the system. For instance, when reviewing the sequence diagram for scheduling courses, the analyst might place schedule, lock, section, student, instructor, and classroom in the candidate list, if these terms appear in the sequence diagram. The actions in the sequence diagram illustrate that these terms could be part of the information passed in the system. The designer examines the system requirements, goal hierarchy, and use case models in a similar manner to create the candidate term list for the ontology. Construct Initial Ontology To construct the initial ontology, the designer takes the list of terms or concepts and organizes them into classes and attributes and produces an initial draft of the data model. When creating the ontology, the analyst must remember to only specify the concepts that the system needs to accomplish its goals. For example, the ontology should not specify all attributes of a Human, such as height, age and weight, when the system only requires the name of a Human to function. Before creating an entirely new ontology, the designer must determine whether any existing ontologies can meet the system needs. The user reviews ontology libraries and existing company data models looking for objects that resemble the concepts listed in the term list built earlier. The benefit to using an existing ontology is that the system is interoperable, in terms of passing data, with any other system that uses the same data model. If no existing ontologies fully specify the information needed for the system, the designer must build a new ontology. If the designer finds an ontology that partially satisfies the system needs, that ontology can be used as a starting point for the new ontology. Users should post created models in some shared repository so that others can reuse the data model, increasing the interoperability of future systems. Continuing the course-scheduling example, the analyst decides what terms from the candidate list should become classes and then organizes them into the class hierarchy shown in the left most pane of Figure 6. Terms that will become attributes of the classes or that the designer decides are not necessary as classes are not included. For instance, the lock term identified earlier is not included in the example ontology. The analyst can decide that the term will be implemented in a manner that will not require the creation of a Lock class. The attributes of each class describe the properties of the class and the relationships to other classes. Figure 6 shows how the Schedule class has two attributes: composedOfSections and courseTypes. The composedOfSections attribute is multiple, indicating it is a list of the Section objects included in the schedule. The courseTypes attribute is a list of String objects used to describe the type of courses that the schedule contains, such as AERO or CSCE. Fig. 6. Ontology Editor Program Refine and Validate Ontology Once the designer defines the classes, attributes, and axioms of the ontology, he must validate that the ontology meets the system requirements. To validate the model, the analyst examines the situations described in the use cases and sequence diagrams to