Department of Systems and Computer Engineering

Description of the CITO Project:

High-Level Design and Prototyping of Dynamic Agencies

Principal investigator R.J.A. Buhr

July 1st, 1998 to June 30, 2000

Description of the Proposed Research

Introduction and Overview.

  1. Motivation and goals. Perform fundamental research into understanding, designing and verifying dynamic agencies. Dynamic agencies are sets of collaborating agents, in a distributed environment, that dynamically coalesce, self organize, and then possibly dissolve. Their dynamic nature offers the prospect of systems that can incrementally and dynamically adapt to continually changing technology, user requirements, and environmental conditions. Although current technology allows such systems to be implemented, current design techniques are weak in providing the system understanding needed to get it right. This project is concerned with ways of solving this problem through a constructive approach that begins with a new way of visualizing dynamic agencies at a whole system level.
  2. Constructive approach. Develop a constructive approach in which dynamic agencies are represented at four different levels of abstraction: i) agency models expressed with Use Case Maps (UCMs), ii) agent meta-models of a kind well known in the agent literature, iii) high level executable prototypes in which interoperability of agents is simulated, and iv) actual distributed implementations. Humans manipulate abstractions at one level into abstractions at the next lower level by adding information. The research problem is developing a conceptual framework and a set of tools that make this possible for practical applications.
  3. Practical implementations. To prove the practicality of the approach, we must show how the prototypes of item 2 can be transformed into practical implementations in truly distributed environments, taking account of issues such as the selection of execution environment, use of mobile agents, generation of correct code, fault tolerance, performance, and load balancing.
  4. Visualization. Visualization is a fundamental theme of this project. The new research problem is tying visualization at the execution level to visualization at the UCM level by means of appropriate tools.
  5. Testing. Demonstrating the practicality of the constructive approach requires developing testing techniques that verify the results in terms of the starting point of the construction (UCMs). We plan to work towards an approach that will ultimately enable agent systems to perform self testing and to evolve through feedback of the results.
  6. Agency issues. The whole point of the exercise is to provide good ways for humans to design dynamic agencies that are capable of resolving well known difficult issues, such as negotiation, economic trading, conflict resolution, adaptation, resource allocation, and quality of service (to name but a few), in a flexible and stable manner.
  7. Case studies. The orientation towards practical techniques requires the development of case studies of problems of industrial interest.

Previous related work.

  1. The proposed project will build on techniques and tools developed by current TRIO projects (including an ISRP) and demonstrated at the Oct 21, 1997 CITO meeting in Toronto and at a project presentation in Ottawa on Dec 9, 1997. The TRIO work has provided starting points as follows: a working UCM tool (A. Miga);  a working prototyping environment that combines Java agents and competing CLIPS rule engines that solve conflict resolution issues and perform intra-agent and inter-agent coordination through a Micmac blackboard (a joint effort with Mitel);  a demonstration-of-concept set of tools for supporting the constructive approach (developed by D. Amyot and D.Quesnel, with the help of M. Elammari);  and a worked out application of industrial relevance (feature interaction, developed jointly with Mitel).
  2. Papers on this work were accepted for PAAM98 in London in March (one paper) and HICSS98 in Hawaii in January (two papers) 1998.
  3. Technology transfer has taken place via 6-monthly project presentations to invited audiences, regular meetings with industrial collaborators, tutorials (e.g., OOPSLA, Mitel), and graduate courses. The approach has been identified by Mitel’s Strategic Technology Group as part of a planned approach for future commercial systems.
  4. Kunz brings extensive research interests and expertise in all aspects of distributed and parallel systems, ranging from programming environments and visualization tools to network protocols and distributed systems management. Logrippo and Amyot (UofO) bring experience with the application of UCMs to Wireless Intelligent Networks (with Nortel) and with the generation of test cases from UCMs for General Packet Radio Services (with Motorola), and will also draw on the work of Probert and Williams (UofO) on testing pair-wise coverage of network elements. Woodside has collaborated on a project with Nortel on the development of the UCM editor for application to performance problems and Bordeleau has worked with ObjecTime on the relationship between UCMs and communicating state machine models. A UCM-Agents design process being developed by Ph.D. student, and previous TRIO ISRP holder, M. Elammari, laid some groundwork for the approach of this project.

Detailed description

The following points expand on those at the beginning of this document:
  1. Motivation and goals. Although the scope of this project may appear very wide, all the elements are necessary to demonstrate practicality. However, not all the elements will be developed to the same depth. We strive only for proof-of-concept. We said that current design techniques are weak for dynamic agencies—this is because they leave system behaviour to emerge in an uncontrolled fashion from details (on one hand, from details of agent-centric declarative meta-models, such as BDI; and on the other hand, from details of operational software models such as those used for OO, exemplified by the emerging UML standard). In either case, the models leave dynamic situations at the whole agency level to messages and protocols, which are second order issues in agencies. First order issues include environmental conditions that agents encounter (e.g., resources available, quality of service required, and diversity of parties involved), the nature of transactions being collectively performed by agents, and the meta-level content of information passed between agents. Descriptions at the level of message protocols hide first order issues under clouds of second order details.
  2. Constructive approach. We are basing our work on a visual representation (UCMs) that does not suffer from these problems. UCMs describe dynamically modifiable "behaviour structures" for whole systems in a precise, compact and understandable fashion that provides a starting point for a constructive approach to designing dynamic agencies. Although UCMs are derived from scenarios, which are inherently an incomplete form of system description, a relatively complete picture can be constructed, from composite UCMs, of all possible causal paths that can traverse individual agents (an agent-centric UCM view). Agent-centric UCM views provide starting points for manipulating UCMs into tabular representations that correspond to more conventional agent meta-models. We are using a variation of the BDI meta-model in our initial investigations and plan to investigate use of the more expressive OPI meta-model of Barbuceanu (UofT). A research issue is the extent to which the constructive approach may be automated through the use of techniques such as design patterns and the dynamic selection of alternatives based on current system conditions. The high level description of agent meta-models (e.g., BDI, OPI) in the form of various tables drives the generation of executable code. We are currently working with a rapid prototyping environment that combines Java agent "bodies", CLIPS rules for agent "heads" and use of a blackboard (a.k.a. tuple space) to simulate all forms of intra-agent and inter-agent communication. Research issues for this environment include the use of hierarchical and distributed tuple spaces to improve scalability, KQML-like exchange of knowledge between agents, and, for the study of feature interaction problems, the link to existing telephony systems (using TAPI and JTAPI standards).
  3. Practical implementations. We also need to look beyond this environment to practical implementations. We will explore how to translate the high-level prototypes into actual code, executing in a truly distributed environment. One relatively straightforward idea would be to translate the agents into Java-based mobile agents, using tools such as ObjectSpace Voyager or IBM's aglets. This code translation should be automated as much as possible. The agents will execute in a distributed and asynchronous environment, so we need to devise protocols that handle partial failures and synchronization between agents. We also need algorithms that spread the load across multiple machines. These algorithms will be based on the hierarchical tuple spaces used in the high-level prototypes.
  4. Visualization. Assuming that code generation can not be automated completely, the executing agents are very likely buggy. Distributed debuggers and performance tools frequently provide visualizations of executions to aid in the understanding process. We need to define an appropriate visualization model and develop techniques that capture the relevant information in an agent environment to drive the visualization. Given the expected complexity of agent systems, high-level abstract views of the execution would be beneficial. The definition of these abstract views could be guided by the UCMs that served as the starting point. Ideally, the execution should be visualized/animated in a fashion similar to the original high-level design, reducing the effort required by a programmer to understand the execution and to identify errors by comparing the actual execution against the expected behaviour.
  5. Testing. Achieve functional coverage of important scenarios (from UCM paths), pair-wise coverage of dynamic combinations of agents and features, and to detect conflicts and behaviour instabilities. Although our constructive approach begins with UCMs, there are many steps between UCMs and prototypes that require human intervention, so the results cannot be guaranteed to be correct by construction. Testing is still necessary. Systems that changes their structure and behaviour while they are running offer difficult testing challenges, because of combinatorial explosion. We will investigate techniques for deriving high yield test cases that will achieve functional coverage of important UCM paths through agencies and pair-wise coverage of dynamic combinations in and between agents. Along the way, insight will be gained into detecting conflicts (e.g., feature interactions) and instabilities (e.g., unexpected departures from UCM paths). The results of this work will guide the development of methods for avoiding conflicts and instabilities and for introducing self-testing into agency designs.
  6. Agency issues. The focus to date has been on negotiation, conflict resolution, and emergent behaviour, in the context of telephony feature interaction. We will continue to study these and other issues (e.g., ontology detection, economic trading, resource allocation) via the feature interaction problem and new problems.
  7. Case studies. The feature interaction case study must be expanded at both the UCM and prototyping levels to include more features and the implications of features being dynamically added as a system is running. We need to expand the examples we are studying beyond feature interaction. Some possibilities include concurrent applications sharing the same agents, adding resource issues to telephone calls (e.g., internet calls), and mobile agents. Examples are needed that broaden the scope of issues covered by the intermediate agent meta-models (e.g., what if a common ontology cannot be assumed?).

Contributions to knowledge.

The major new contribution to knowledge will be systematic techniques for understanding, designing, explaining and architecting dynamic agencies. Already have met with some success (see papers), but more work is needed. Evidence that the approach is new to the agent community is provided by the fact that reviewers of our paper for PAAM98 said that they had not seen anything like the UCM approach elsewhere.

Intellectual uncertainties.

The constructive approach we are developing will have a human-input aspect and an automation aspect. The uncertainties mainly center around the degree of automation possible, through the use of design patterns and the ability to define environmental and other factors for selection of protocols.

Other related projects.

Complementary agent projects in the CITO domain include Pagurek and Biesczed (Carleton SCE), Abu-Hakima (NRC), Karmouch (UofO), Barbuceanu and Yu (Toronto). Logrippo (UofO) is applying UCMs to Wireless Intelligent Networks (WIN) in a project with Nortel (on which Buhr is a co-investigator). Woodside (Carleton) and Buhr are applying UCMs to system performance modelling in a TRIO project with Nortel (an extension of which is being applied for under CITO). An interest in traceability issues is shared with Bordeleau and Corriveau (Carleton SCS) and Probert (UofO), and in feature interaction problems with Atlee (Waterloo).

Industrial Relevance

Bad consequences, in terms of both safety and cost, may follow from the weaknesses of existing techniques described previously. Changes and additions made to a system without clear knowledge of how large scale dynamic situations were conceived may cause an entire system to become unstable. Developers may form incompatible views of a system as a whole, complicating and slowing down the developmental process. Software may become very resistant to the continual evolution that is required by competitive pressures. With current techniques, these situations can only be detected and corrected with extensive regression testing which prolongs development, delays time to market, and opens the field to competitors.

Feature interaction is an example of a problem of practical interest to industry. Agents are very suitable for addressing such problems because of their ability to handle conflict resolution situations dynamically. Ways are needed of making the feature interaction problem more visible (with UCMs and other vizualization techniques), of resolving feature interactions dynamically (through prototyping with competing rule engines), and of enabling solutions to flow from high level descriptions (with UCMs and testing). Successful research will lead to a scalable approach that permits adding new features incrementally at run-time; this is important for the type of telecom applications that interest us, where no deterministic or optimal solution is known, and where opportunistic problem solving seems to be the most practical approach. This research aims to demonstrate the essence of an intended approach for future commercial systems.

Benefits to Mitel will be as follows. New methods and tools will help address a new technology area (dynamic, net-based software) for which few methods and tools yet exist. The expected benefits are shortened development time and reduced time to market. The strategic technology group has identified this approach as part of a new way of developing future commercial products.

Other than Mitel, considerable interest in this project has been shown by companies such as Metex (Tim Lloyd, K.Brower), Linmor (N. MacNeil), Microcell Labs (C. Alie), and ObjecTime (B. Selic). Demonstrations of some interim results at the Oct. 21 CITO meeting in Toronto, at the Dec. 9 presentation in Ottawa, and at the Jan. 8 ObjecTime workshop attracted considerable industrial interest.

As both a co-investigator and co-sponsor, Mitel is much involved in this project as they intend to use our technological results for the design of their next line of product.

Work with our Mitel coinvestigators will take place, as it has for the current TRIO project, through regular meetings (usually twice a month), joint authorship of papers, attendance at conferences, joint development of prototypes and case studies, joint demonstrations of the results, working group meetings (such as a series of meetings being organized by Mitel for the spring and fall with several university research groups participating), and consulting arrangements.

Additionally, interaction with take place with H. Guestrin on testing issues.

Nortel is also expected to take advantage of our work through Woodside’s project on performance and Logrippo’s project on Wireless Intelligent Networks. In the first case, the UCM tool is to be used for describing performance models. In the second case, UCMs will help designing and documenting WIN features. The UCM tool, together with its linear form and parser, are expected to be used. There is also a common interest in UCM-based functional testing.

Any company in the telecom industry (Newbridge, Lucent, Ericsson, Motorola, Bell, etc.) or in the object-oriented/agent fields can be a potential user of the concepts and techniques developed in this project. Some contacts have been made through several TRIO/CITO events.

Interested companies do not need large resources to exploit our results. Experience with agents, AI, OO, and real-time and distributed systems concepts is however an asset in understanding the techniques. An access to a Java environment and to Sun Solaris can be useful for some of our tools. All companies that have access to Internet can already get several research results through our Web page (http://www.sce.carleton.ca/rads/agents/) and FTP site (http://www.sce.carleton.ca/ftp/pub/UseCaseMaps/). Reports, papers, and work on the UCM grammar and parser are freely available. Mitel also published its Java and C++ interface for Micmac (blackboard) on their Web site (http://micmac.mitel.com/). The UCM editor can also be made available upon request.

Technology transfer will take place via 6-monthly project presentations to invited audiences, regular meetings with industrial collaborators, tutorials, and graduate courses (including Congese), regular reports, papers, and consulting.

Revised Work Plan (August 1998)

The CITO project is planned over two years. Year-by-year activities are given below. Names associated with these activities included the following.  D. Amyot worked part time as the research engineer on the TRIO project and will be focusing, for the next two years, on the aspects of this project relevant to his Ph.D. thesis (UCM validation).  K. Lam is a second year student who works on the project this summer and who will continue part-time (Java meta-models GUI).  A. Miga, who just completed his Masters, will continue his work as a part-time employee until the beginning of 1999 (UCM Navigator).  D. Petriu is a Masters student who has been working on this project since May and who will continue his work until the end of year one as part of his Masters thesis (OPI and feature interactions).  D. Quesnel is a Masters student who has been working on the TRIO project and who will continue for the first half of year 1 of the CITO project, until completion of his thesis (Java supporting platform for agents). C. Witham is a third year student who works on the UCM Navigator for this summer.

Year 1 (12 months, starting 1 July 1998)

Will consolidate and extend the constructive approach and the tool support for it developed in the TRIO projects, add new lines of investigation (OPI, validation), and extend the range of applications being studied.

Year 2 (12 months, starting 1 July 1999)

Will perform investigations of agency issues for applications of industrial interest, present the results to industry, and use the feedback to identify any needed refinements to the constructive approach and the tools.
UCM - Agents Group


Last modified: February 25th, 1999