 |
Department of Systems and Computer Engineering
|
Original Description of the TRIO Project:
High-Level Design and Prototyping of Agent Systems Project
Principal investigator R.J.A. Buhr
We are in the Department of Systems
and Computer Engineering at Carleton
University, in Ottawa, Canada. This project performs fundamental research
into methods for high level design and prototyping of agent system software.
We develop high level techniques and methods that will enable the design
to flow systematically from requirements, support extensibility to accommodate
new requirements, and result in overall system behaviour that is desired,
constrained, controllable, stable, responsive, and predictable.
Below you will find
Current and Future Objectives
Long-term
- Perform fundamental research into methods and supporting tools for
high level design, prototyping, and understanding of multiagent systems.
- Apply the methods and tools to investigate selected difficult system
design issues that are characteristic of multiagent systems, such as negotiation,
economic trading, conflict resolution, adaptation, system self-modification,
usage rights, jurisdictional control, ontologies, service specification,
quality of service, agent mobility, failure, emergent behaviour, controllability,
stability, predictability, evolution, architecture, ODP,
design patterns, performance, admission control, resource allocation, load
balancing, verification/validation, and management.
- The focus is on the properties of systems of agents, not on the application
functionality of individual agents.
Short and Long-term
- Perform case studies of agent system issues in the context of applications,
in collaboration with TRIO member companies
and other agent researchers.
Short-term
- Develop a novel high level design/prototyping approach that systematically
transforms user requirements for system behaviour, expressed with Use Case
Maps (UCMs),
into implementable descriptions of agent systems that satisfy the UCMs
by construction and that can be understood by reference to UCMs. The term
"prototyping" means building executable models that focus on
properties of a system of agents as a whole, not on application functionality
of individual agents.
- Build an experimental facility to prove the initial approach and to
provide a starting point for evolution of a facility to support long term
research objectives. The initial facility will have three parts, of which
the first two will be useful in their own right, independent of UCMs.
- PART 1: A prototyping tool for experimenting with system issues in
multiagent systems.
- PART 2: An intermediate modeling tool for helping human designers construct
agent models in terms of concepts such as beliefs, desires, goals, plans,
intentions, negotiations, usage rights, and contracts, and for constructing
executable prototypes from these models with Part 1.
- PART 3: A high level modeling tool for designing agent systems in terms
of UCMs and transforming the UCMs into the intermediate models of Part
2, and thence into executable prototypes with Part 1.
Area of Research / Background
Agent systems have emerged as a potential solution to the problem of
constructing flexible network software. The problem is the impossibility
of building an entire system around predefined requirements for application
functionality, user interactions, communication protocols, available resources,
current technology, and so forth. All of these things may change over time.
The agent solution is to build intelligence into special system components
called agents, to enable them to work at a metalevel, compared to ordinary
software, that will enable them to adapt and evolve. The result is flexible,
but has a degree of fluidity at the whole system level that yields a very
complex system picture when viewed from a conventional software perspective.
As an example of the property of fluidity, multiagent systems may modify
their structure while they are running, meaning that agents may be created
and destroyed, visibility of fixed agents to other agents may change over
time, and mobile agents may move from site to site. Such system self modification
is one of the ways multiagent systems adapt to changing circumstances.
The effect is complex because self modification is intertwined with ordinary
interagent collaboration and agent operation.
The agent community may be said to be taking the following approach
to dealing with the complexity issue: Design individual agents for adaptation
and evolution (using metalevel agent concepts for heavyweight agents),
implement the result in code, and then stand back and hope that satisfactory
behaviour will emerge at the system level. Examples of intended system
behaviour may be provided, but using techniques that yield complex and
unwieldy system descriptions, do not scale, and do not yield sufficient
insight into system properties. For example, presenters of agent systems
at the PAAM97 agent conference
typically solved the problem of explaining their systems by displaying
sequences of box-arrow diagrams, in the style of object interaction diagrams
that are popularly used for software design. The boxes represented agents
and the arrows represented message paths. Each diagram provided a snapshot
of a particular system configuration and a sequence of different snapshots
indicated that the system was intended to be self modifying between the
snapshots. In addition to the undesirable characteristics enumerated above,
this approach is also unsatisfyingly incomplete because the means of self
modification is hidden between snapshots.
Murray Woodside
has pointed out that software performance engineers get complex and unwieldy
descriptions when conventional performance models are applied to self modifying
systems.
This project aims to work at the design problem from both ends: Work
at the system level with high level descriptions that are more abstract
than the style of box-arrow description described above, work at the individual
agent level with well known agent metamodels (or extensions of them), and
bring the two together with new conceptual glue and supporting tools. The
intent is not sweep everything away and start anew, but to supplement conventional
techniques from the agent domain and the software engineering domain with
new techniques that give a clearer system picture. To be practically useful,
the new techniques must be lightweight enough to capture a bird's eye view
of whole systems in a compact fashion.
We are starting with Use Case Maps as
our initial high level design approach because they provide a bird's eye
view of multiagent collaboration and system self modification that both
identifies them as separate system issues, in a way that current software
design techniques do not, and also allows them to be freely combined in
a high level way. UCMs combining these issues are easy for humans to understand
and construct, do scale up, are a starting point for detailed design in
more conventional terms, and do give an overview of system behaviour in
a more understandable and light weight way than by piecing together details.
Work on this approach was in progress before this project started (an ISRP
and other research), is showing promise, and will be accelerated by this
project. We think a process that starts from UCMs will ensure a measure
of controllability of the results, by constraining emergent behaviour to
follow specified requirements, rather than simply allowing behaviour to
emerge from the details and hoping for the best. We hope that a UCM-based
approach will help customers and system designers to communicate better
about requirements, provide a systematic starting point for transforming
requirements into designs using standard techniques, and help with system
evolution by providing a high level reference for understanding the system.
Applications will be selected to characterize difficult issues, such
as the need for conflict resolution, or the existence of strong system
self modification. We have provisionally identified two examples for initial
exploration, each of which characterizes one of these issues. Feature interaction
in telephony may be used to explore conflict resolution through means such
as negotiation, jurisdictional control, and contracts (this example is
currently being developed in collaboration with Mitel).
Agent support for system self-configuration (e.g., plug-and-play peripherals)
may be used to explore strong system self modification (we intend to develop
this example in collaboration with Bernie
Pagurek's Trio project on agents). Other applications will be identified
and investigated as the project progresses.
Achievements to Date
This is a new project, so no achievements yet, but project is built
on developing momentum in agents:
- UCM approach showing promise in collaborative work with Mitel
(consulting, TRIO ISRP); see agents-ucms.ps
for some recent results.
- Current TRIO work on agents for application performance management,
in the Mandas
project with IBM (Rolia,
Woodside),
and in a current project with Mitel (Rolia).
- Current TRIO work on components, ODP,
and midware in several directions (measurement, prototyping, specification)
is leading towards agents (all coinvestigators).
- Linkages to other agent academic researchers developing, facilitated
by Mitel (Tom Gray presentation).
This project does not have to make it happen, as was thought when the proposal
was written, it is already happening.
- UCM Editor currently under development (M.Eng. student Andrew
Miga supported by other TRIO funding).
- A UCM-ROOM Design Process being developed by Ph.D. student, previous
TRIO researcher, and ObjectTime
collaborator, Francis Bordeleau,
lays some groundwork for the UCM approach.
- Anecdotal evidence from UCM users in industry worldwide indicates they
are being found useful for the reasons advanced above.
Research Description 1997/98
(Participation of coinvestigators is identified under paragraph 9)
- Develop an initial experimental facility in three parts:
- PART 1 (prototyping tool): An agent-prototyping framework called MICMAC,
supplied by Mitel, will be used by both
this project and Pagurek's
TRIO project. The expert system part of
MICMAC will support intelligence for the
"heads" of agents (e.g., rules for conflict resolution). To pave
the way for evolution towards implementing actual agent systems in Java,
the control logic of agent "bodies" will be implemented in Java
programs that communicate with the heads through a Java API. The blackboard
part of MICMAC will be used to model both
head-body communication in single agents and interagent communication.
The term "model" means that literal interagent communication
through messages will not be implemented, but will be modelled by posting
tuples on the blackboard. The result will be a rather unusual "implementation"
of agents, split between "heads" in a centralized expert system
and "bodies" written in Java and perhaps running on a separate
computer (or computers), with interagent communication modelled by means
of the same blackboard. If this seems strange, remember that the initial
intent is to prototype key features of agent systems at a high level of
abstraction, not yet to literally implement them. In actual implementation,
heads and bodies would be together and interagent communication would be
by actual messaging. Responsibility: Darcy
Quesnel.
- PART 2 (intermediate modeling tool): There is no software available
for this part, or for the glue between it and parts 1 and 3, so we shall
develop this software from the ground up. Because of the use of Java for
part 1, our plan is to implement the part-2 software also in Java. The
initial software will primarily provide machine assistance for capturing,
storing, managing, and retrieving the data required by the intermediate
models. Initially, the glue between parts 1-2 and parts 2-3 will be primarily
in the minds of human users. Semi-automation of this glue will left as
an item for future work (possible thesis for Darcy Quesnel). A linear textual
form for UCM descriptions is required. Responsibility: Darcy Quesnel and
Mohammed Elammari.
- PART 3 (high level modeling tool): The starting point will be a C++
UCM tool currently under development by a graduate student, Andrew Miga.
In future, it may be desirable to reprogram this tool in Java, but doing
so initially would get in the way of proving the feasibility of our concepts,
so this will be left for future work. Required extensions to this tool
will either be added directly in C++, or added indirectly through a back
end in part 2. Responsibility: Andrew Miga.
- ALL PARTS: Begin work on the initial experimental facility by working
through, by hand, for a selected example, the process of constructing the
models for parts 1, 2, and 3. Use the results to define the intermediate
models and the machine assistance or semi-automation required. The initial
example will be conflict resolution in telephony feature interaction. Other
examples may also be used. Responsibility: Daniel
Amyot, Darcy Quesnel, and Mohammed Elammari.
- Define and perform case studies of example applications, with the help
of industrial partners. This requires first preparing a description of
the application that would be usable by graduate students and other researchers.
The case studies will at least include the examples used for developing
the initial ideas and tools. They should include strong elements of adaptation
and self modification, because these are aspects that uniquely characterize
agent systems and that cause difficulty for conventional methods. Responsibility:
All researchers.
- Train the project research engineer in the use of the experimental
facility so the engineer can support subsequent research by faculty and
students. Responsibility: Daniel Amyot (self-trained through the work on
item 1).
- Determine and document how to use the experimental facility to experiment
with agent system issues. Responsibility: Daniel Amyot.
- Through case studies, develop design patterns, architectures, unifying
principles, and methods, and document them for industrial use. Because
the agents overlap so many fields, develop a glossary of terminology. Responsibility:
All researchers.
- Work with industrial partners and other Trio thrusts to transfer the
research ideas to applications. With Mitel, this will continue work already
started in relation to their CATA prototypes.
- As this is a new area for many TRIO companies, a special effort will
be made to develop new partnerships in agent software design, in industry
and with other researchers. As part of this effort, open meetings will
be held approximately every six months among researchers, collaborators,
and interested Trio members. The first such meeting was held on May 15,
97, shortly after funding for the project was announced, and attracted
twenty participants. A second meeting is planned for mid-fall with an enlarged
invitation list.
- Investigate for future use other prototyping frameworks than the MICMAC/Java
combination proposed for the initial A. PART1. Responsibility: Initially
a background activity with no identified milestones, but hope to enlist
students to investigate.
- Coinvestigators have identified points of contact (listed here, without
attempting to be complete): Woodside, Rolia: help develop support in A.
PART 1 for Angio traces. Probert:
help develop support in A. PART 1 for test agents, and in all parts of
A for use case trees for test specification and evaluation. Woodside, Rolia,
Logrippo: help associate
with UCMs in A. PART 3 a number of properties and parameters needed for
research, such as, performance parameters, error recovery, quality of service,
relationships between preconditions and postconditions. All coinvestigators:
participate in case studies in B, with focus by Logrippo on use case design
methods and linkages with ODP, by Woodside and Rolia on architectures and
design patterns for performance, and by Probert on verification/validation.
Actual work depends on the availability of students. Some are in prospect
at University of Ottawa, but no
commitments can be made yet.
Future Direction of Research
- Evolve the experimental facility and the concepts to support the long
term objectives.
- Investigate the research issues identified in the long term objectives.
- Refine the approach through case studies.
- Expand collaborations.
- Develop support in the experimental facility for evolving prototypes
into practical agent systems.
Cohesion - Linkages and Cooperation
- Mitel: There is an associated current
ISRP with Mitel and Ph.D. student Mohammed
Elammari (begun January 97), plus ongoing related consulting collaborations.
- Other agent projects: Joint work is starting with B.
Pagurek's TRIO project on agents.
Linkages are planned with other university researchers who are working
with Mitel on agents, facilitated by Mitel.
- NRC's Seamless
Networking Laboratory: S.
Abu-Hakima has promised that her group will help with the application
of the expert system (CLIPS) part of MICMAC,
if we need help. Other linkages with this group may be possible, but our
project has to progress farther first.
- Nortel: There is a strong linkage
to a recently approved TRIO ISRP with Nortel to combine UCMs and performance
modeling.
- Linmor: Norm MacNeil attended the
May project meeting and a meeting is planned to discuss linkages with this
project.
- Metex: Tim Lloyd attended the May
project meeting. Future linkages remain to be explored.
- Liz Kendall, RMIT
(Australia): An informal collaboration is developing.
Expected Knowledge created in 1997/98
and its Product/Service Implication
- Deeper understanding of agent system issues.
- New modelling techniques for agent systems.
- Mappings between representations and from representations to implementations.
- Structural and behavioural patterns.
- Practical agent system architectures.
- Approaches to Control, Performance, and V/V research areas defined.
- Glossary of terminology.
Deliverables to Industry
- Agent system concept prototyping testbed with UCM-MICMAC.
- Case studies of agent applications.
- Working demonstrations.
- Ideas validated by application to industrial prototypes.
- Mitel initially, expect others eventually.
Benefits to Academia
- Faculty: Research stimulation provided by new problems in a difficult
and important area. Create expertise in a new area.
- Students: Attractor for quality students. Excellent area for student
training.
- Courses: Integration of agent issues into university courses, possible
development of new courses.
Co-Investigators and all other Personnel
1997/98 Milestones
- August 97 - By hand workthrough of UCMs-to-agent logic for a small
sample.
- August 97 - Case study application system defined.
- October 97 - MICMAC testbed installation/familiarization
complete.
- October 97 - Research engineering training completed.
- December 97 - Facility usage defined.
- January 98 - Full integration of UCM tool with the testbed.
- February 98 - First design/prototyping case study completed.
- April 98 - First results on design patterns, architectures, unifying
principles and methods, written up and transferred to industrial partners.
- April 98 - New working partnerships established.
Selected References
- R.J.A. Buhr, "Use Case Maps Updated: A Simple Notation to Help
Humans Understand and Architect the Emergent Behaviour of Large, Complex,
Self Modifying Systems", Carleton report (extract from a chapter on
a forthcoming ACM book on OO methods and applications) ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/ucmUpdate.ps
- R.J.A. Buhr, M. Elammari, T. Gray, S. Mankovski, D. Pinard, "A
High Level Visual Notation for Understanding and Designing Collaborative,
Adaptive Behaviour in Multiagent Systems", ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/agents_ucms.ps
- R.J.A. Buhr, Understanding Macroscopic Behaviour Patterns in Object-Oriented
Frameworks, with Use Case Maps, chapter of a forthcoming Wiley book on
"OO Application Frameworks". ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/uoof.ps.
- F. Bordeleau and R.J.A. Buhr, "The UCM-ROOM Design Method: from
Use Case Maps to Communicating State Machines, Conference on the Engineering
of Computer-Based Systems, Monterey, March 97. ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/UCM-ROOM.ps.
- R.J.A. Buhr, A. Hubbard, Use Case Maps for Engineering Real Time and
Distributed Computer Systems: A Case Study of an ACE Framework Application,
30th Hawaii International Conference on System Science, Jan 97. ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/hicss.ps.
- R.J.A. Buhr, Design Patterns at Different Scales, presented at PLoP96,
Allerton Park Illinois, Sep 96. ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/plop.ps.
- R.J.A. Buhr, Use Case Maps for Attributing Behaviour to Architecture,
Fourth International Workshop on Parallel and Distributed Real Time Systems
(WPDRTS), April 15-16, 1996, Honolulu, Hawaii, ftp://ftp.sce.carleton.ca/pub/UseCaseMaps/attributing.ps.
- R.J.A. Buhr, R.S. Casselman, T.W. Pearce, Design Patterns with Use
Case Maps: A Case Study in Re-engineering an Object-Oriented Framework,
ftp://ftp.sce.carleton.ca/UseCaseMaps/dpwucm.ps.
Related Standards, Tools, and
Platforms
UCM - Agents Group
Last modified: Oct. 15 EDT 1997