Overview
Complexity is one of the primary problems that we attempt to address with software development tools and methods. Complexity, if not managed, can cause a product to be low quality or delivered late, over budget, or the project could be cancelled completely. There are no easy solutions to removing complexity and improving productivity and quality. The best we can do is reduce or manage complexity. Modularity is a fundamental principle for achieving simplicity of design and development effort and thus reducing and managing complexity
Wednesday, August 15, 2007
Introduction to Software Design
Overview
Problems in Software Architectural Design
Function, Form, and Fabrication: The Vitruvian Triad
The Scope of Design
The Psychology and Philosophy of Design
General Methodology of Design
Summary
Overview
Higher-quality design, not just higher-quality development processes, is necessary in order to achieve a high-quality product. But what characterizes a higher-quality design, and how do we achieve it? And, more fundamentally, what characterizes an activity as design, and what is the product of design? This presents the fundamental methods of the software design process and establishes the scope of the architectural level of design. The same fundamental design principles and methods apply whether a software architect is analyzing the problem domain, specifying the function of an application to address the problem domain, or designing the structure or form of the software. They also apply when a software engineer is creating a detailed design (including coding) or testing an implementation or designing a development environment in which to create the code. A generalized method of design is presented.
The obstacles to achieving high-quality architectural design in software development are:
A lack of awareness of the importance of architectural design to software development
A lack of understanding of the role of the software architect
A widespread view that designing is an art form, not a technical activity
A lack of understanding of the design process
A lack of design experience in a development organization
Insufficient software architecture design methods and tools
A lack of understanding of how to evaluate designs
Poor communication among stakeholders
Most of these obstacles stem from ignorance around what software architecture and design are and why they are critical to the success of an application or other system development project. This ignorance results in an inability to effectively communicate what problems an application is really addressing and how a technical solution solves those problems.
The solution to the problem of inadequate design must address the obstacles to achieving adequate design. The solution involves the following:
Evangelizing the importance of software architecture
Improving software architecture education
Using architecture methods and tools
General Methodology of Design
In this section, we look at the general elements of a design method based on Pahl and Beitz (Pahl, 1996). Not all design methods include all of these elements, but these elements are present in all design methods:
Purposeful thinking
Analysis
Abstraction
Synthesis
General heuristics
Purposeful Thinking
Design requires systematic thinking, which separates design from routine tasks. Systematic, or discursive, techniques are not the opposite of creative techniques nor are they the opposite of subconscious, or intuitive, thought. Relying on intuition alone, however, is not a good design practice so we need to be more deliberate in our approach to design. A purely intuitive approach to design has several disadvantages: The right solution rarely comes at the right time, the results depend on the architect's skills and talents, and the solutions may be negatively influenced by preconceived ideas (also called fixation). Intuition can lead to good solutions but requires conscious and deliberate involvement with the problem. Discursive thought can stimulate intuitive thinking. Programmers experience this frequently. A programmer may spend hours or days struggling with some problem only to have the solution come to her while she is away from the computer, not even consciously thinking about the problem.
Design should be primarily discursive; that is, it should proceed deliberately in a stepwise fashion. Unconscious procedures can be transformed into deliberate and systematic methods through systematic rules, clear task formulation, and structured design procedures.
Errors are unavoidable so our processes must allow for this. Therefore the architect should analyze the design for errors or weak points in the early stages of development. Clearly defined requirements and problem statements help reduce the risk of design errors by minimizing the amount of guesswork that goes into the design process as well as minimizing the amount of rework that would otherwise be necessary. A discursive design approach helps reduce errors by enforcing systematic testing of design ideas and assumptions early in the development process. Fixed design ideas (assumptions) should be avoided and existing methods and tools should be adapted as necessary (don't let a given methodology artificially constrain you). The deliberate use of specific methods for failure or error identification should be used.
Creativity is inhibited or encouraged by different influences. Some techniques for encouraging creativity are:
Interrupt the activity to create incubation periods (but be careful; too many interruptions can be disruptive).
Apply different solution-finding methods.
Move from abstract to concrete ideas.
Find and collect information from design catalogues (such as design patterns).
Divide work among architecture team members.
Make realistic plans: Realistic planning is found to encourage motivation and creativity, while unrealistic planning is inhibiting.
Analysis
Analysis is the decomposition of complex systems into elements and their interrelationships, identifying essential distinctions, and discarding accidental distinctions. The activities of analysis include identification, definition, and structuring with the purpose of acquiring information about a subject that can be transformed into knowledge. Analytic methods are useful in all stages of software design, from requirements gathering to evaluating designs and technologies to implementation.
Formulating problems clearly and unambiguously, via analysis of an application domain, helps avoid many expensive design and implementation errors. Careful analysis and formulation of problems are two of the most important and effective tools a software architect has. All design methodologies have some analysis aspect. However, I find that many modern design methodologies tend to blur the distinction between analysis and design. Many object-oriented methodologies promote a seamless development concept where the problem or application domain is continuously transformed into a solution, for example, Object Modeling Technique (OMT). In practice, the analysis is rarely done or is not done adequately.
Structured analyses in software, such as the techniques of Gane and Sarson, Yourdon, DeMarco, Ward and Mellor, and the Structured Systems Analysis and Design Methodology (SSADM), are methods for formulating and structuring the problem. Structured analysis is a process where the problem is formulated in terms of data flows, as represented in data flow diagrams (DFDs) and in system state transitions as represented in state transition diagrams. These models emphasize a hierarchical structuring of the functions of a system.
Similarly, object-oriented analysis, such as the techniques of Jacobson, Booch, Rumbaugh (OMT), and Yourdon and Coad, are techniques for structuring the problem domain in terms of objects, their interrelationships, and their class hierarchies. Whereas structured analysis emphasizes a functional hierarchy, object orientation emphasizes a data hierarchy.
Abstraction
Through abstraction, we can infer more general and comprehensive relationships among the elements of our problem. Abstraction reduces the complexity of a problem while emphasizing the essential characteristics of it and aids in the discovery of solutions. Abstractions are not always invented; sometimes they are discovered by using existing abstraction models and attempting to fit the problem into them.
This is an example of predication: A statement is created about the problem abstraction and an existing model such as "problem A (new) is a form of problem B (existing)." An otherwise seemingly novel problem may turn out to be a variation of an existing problem to which some known solutions already exist. By formulating problem A in terms of problem B, the architect then only needs to find suitable abstractions for the remaining part of problem A. A problem can have many abstractions, and, using a discursive approach, the architect can discover several suitable abstractions and apply many existing problem models. Metamodels or reference models are examples of such reusable abstractions.
Analysis aids in the discovery and evaluation of abstractions. Not all analysis results in abstractions, but most abstractions are discovered via analysis.
Synthesis
Synthesis is the combining of individual elements or parts to produce a new effect. It is the integration of solutions to subproblems and the evaluation of the resulting system. When we decompose a problem via analysis into sub-problems and discover solutions to those subproblems, there is still the risk that synthesizing those solutions will not solve the larger problem entirely or, worse, the solutions will be incompatible. Existing abstraction models may also be synthesized to form larger, more specialized abstractions. Synthesis is not only applied to the models of software architecture, it is also applied to the design methods
General Heuristics
In this section, we look at some heuristic design methods. Heuristics are techniques that are characterized as the searching for suitable solutions. These methods apply to many design tasks:
Persistent questions
Negation
Forward steps
Backward steps
Factorization
Systematic variation
Division of labor and collaboration
The Method of Persistent Questions
This method is useful when applying any systematic procedure such as requirements engineering (systems analysis), architectural design, and architectural evaluation. Requirements are almost never complete or at the right level of abstraction and the architect must help the acquirer to discover the essential requirements of the application they are envisioning during the analysis of the requirements. Persistent questioning stimulates ideas and intuition and helps to eliminate assumptions and preconceived notions. The method of persistent questions is a tool that the architect may use when analyzing the problem to discover useful abstractions, as well as a tool for evaluating solutions. An architect or architecture team may even keep a database of standard sets of questions for various purposes. Such a database of questions helps extend the memory of the architect and transfer useful design methods and knowledge to others. Asking questions is considered one of the most important methodological tools, and the technique is found in many existing product development methodologies
The Method of Persistent Questions
This method is useful when applying any systematic procedure such as requirements engineering (systems analysis), architectural design, and architectural evaluation. Requirements are almost never complete or at the right level of abstraction and the architect must help the acquirer to discover the essential requirements of the application they are envisioning during the analysis of the requirements. Persistent questioning stimulates ideas and intuition and helps to eliminate assumptions and preconceived notions. The method of persistent questions is a tool that the architect may use when analyzing the problem to discover useful abstractions, as well as a tool for evaluating solutions. An architect or architecture team may even keep a database of standard sets of questions for various purposes. Such a database of questions helps extend the memory of the architect and transfer useful design methods and knowledge to others. Asking questions is considered one of the most important methodological tools, and the technique is found in many existing product development methodologies
The Method of Forward Steps
The method of forward steps is also known as the method of divergent thought. It starts with a first solution attempt and proceeds to follow as many solution paths as possible, yielding other solutions. The method of forward steps is not necessarily systematic and usually starts with an unsystematic divergence of ideas. For example, the first solution attempt at an application problem may be to apply a client/server architectural style. By applying forward steps, the architect follows several paths such as browser-based client, Web client with browser plug-ins, fat client with embedded browser, or fat client that speaks HTTP with the server.
This method can be applied to any model at any level of abstraction and is typically followed recursively as far down a path as possible. For example, starting with the fat client that speaks HTTP solution, additional application of the method of forward steps could yield solutions like fat client with local storage, fat client with server-side storage only, and fat client with heterogeneous local and server-side storage. The process can follow any path. This is a good way to brainstorm over an object model of the application domain as well as the choice of technologies in the solution domain. This method is similar to the method of systematic variation.
The Method of Backward Steps
The method of backward steps is also known as the method of convergent thought. In this approach, the architect starts with a goal in mind rather than the initial problem. This technique is most useful for setting up an engineering design process for a product and a product development plan after the architecture has been determined. Starting with the final objective of the development effort, all (or a reasonable subset of) possible paths that could have led up to the objective are retraced. This method is useful not only in preparing an engineering process but also for organizing an engineering department around the architecture of a product (known as Conway's law).
The Method of Factorization
This method is the basis of the refactoring technique, popular among software engineers when reworking existing source code to make it more readable, manageable, maintainable, and reusable. The method involves breaking a complex system into less complex elements or factors. Factorization is a type of analysis method. In architecting, this technique is used to find the essential problems being solved (for example, factoring the objectives into subobjectives). Just as in mathematics, the factorization may not be obvious and requires some insight, skill, and lots of practice. In algebra, you may factor an equation by introducing zero as a factor. Similarly, finding that one of the factors of a publishing system is a file-versioning repository may not be obvious (although the experienced architect may see the factorization immediately). Another example is taking what may appear to be an indivisible component and finding a way to divide it into two components and an interface.
The Method of Systematic Variation
The method of systematic variation of solutions may have originated with Leonardo DaVinci. DaVinci kept meticulous notes on his ideas and inventions and applied this technique to derive multiple variations of ideas, each varying only by a single characteristic from the former. The method starts with a generalized classification structure, such as a class hierarchy, that represents the various problem characteristics and possible solutions. By systematically varying a single characteristic, the architect may discover more optimized solutions. The approach yields a solution field. Evaluation techniques can be applied to each solution to determine its suitability.
Division of Labor and Collaboration
The study of human factors has found that implementing large and complex tasks requires a division of labor. The more specialized the task the more important the division of labor. Software development tasks are commonly based not only on functional areas of the system but also on the technology used. We typically have user interface designers, user interface engineers, middle-tier engineers, back-end or database engineers, test engineers, configuration management engineers, and so on. A complex application or system also benefits from a division of labor with respect to the architecture. For example, it seems natural to separate the tasks of requirements engineering, functional specification, interaction design, and structural design, all of which are in the scope of architecture. However, whenever there is a division of labor there is an information exchange problem. Systematic methods and the creation of models can help overcome this problem.
Problems in Software Architectural Design
Function, Form, and Fabrication: The Vitruvian Triad
The Scope of Design
The Psychology and Philosophy of Design
General Methodology of Design
Summary
Overview
Higher-quality design, not just higher-quality development processes, is necessary in order to achieve a high-quality product. But what characterizes a higher-quality design, and how do we achieve it? And, more fundamentally, what characterizes an activity as design, and what is the product of design? This presents the fundamental methods of the software design process and establishes the scope of the architectural level of design. The same fundamental design principles and methods apply whether a software architect is analyzing the problem domain, specifying the function of an application to address the problem domain, or designing the structure or form of the software. They also apply when a software engineer is creating a detailed design (including coding) or testing an implementation or designing a development environment in which to create the code. A generalized method of design is presented.
The obstacles to achieving high-quality architectural design in software development are:
A lack of awareness of the importance of architectural design to software development
A lack of understanding of the role of the software architect
A widespread view that designing is an art form, not a technical activity
A lack of understanding of the design process
A lack of design experience in a development organization
Insufficient software architecture design methods and tools
A lack of understanding of how to evaluate designs
Poor communication among stakeholders
Most of these obstacles stem from ignorance around what software architecture and design are and why they are critical to the success of an application or other system development project. This ignorance results in an inability to effectively communicate what problems an application is really addressing and how a technical solution solves those problems.
The solution to the problem of inadequate design must address the obstacles to achieving adequate design. The solution involves the following:
Evangelizing the importance of software architecture
Improving software architecture education
Using architecture methods and tools
General Methodology of Design
In this section, we look at the general elements of a design method based on Pahl and Beitz (Pahl, 1996). Not all design methods include all of these elements, but these elements are present in all design methods:
Purposeful thinking
Analysis
Abstraction
Synthesis
General heuristics
Purposeful Thinking
Design requires systematic thinking, which separates design from routine tasks. Systematic, or discursive, techniques are not the opposite of creative techniques nor are they the opposite of subconscious, or intuitive, thought. Relying on intuition alone, however, is not a good design practice so we need to be more deliberate in our approach to design. A purely intuitive approach to design has several disadvantages: The right solution rarely comes at the right time, the results depend on the architect's skills and talents, and the solutions may be negatively influenced by preconceived ideas (also called fixation). Intuition can lead to good solutions but requires conscious and deliberate involvement with the problem. Discursive thought can stimulate intuitive thinking. Programmers experience this frequently. A programmer may spend hours or days struggling with some problem only to have the solution come to her while she is away from the computer, not even consciously thinking about the problem.
Design should be primarily discursive; that is, it should proceed deliberately in a stepwise fashion. Unconscious procedures can be transformed into deliberate and systematic methods through systematic rules, clear task formulation, and structured design procedures.
Errors are unavoidable so our processes must allow for this. Therefore the architect should analyze the design for errors or weak points in the early stages of development. Clearly defined requirements and problem statements help reduce the risk of design errors by minimizing the amount of guesswork that goes into the design process as well as minimizing the amount of rework that would otherwise be necessary. A discursive design approach helps reduce errors by enforcing systematic testing of design ideas and assumptions early in the development process. Fixed design ideas (assumptions) should be avoided and existing methods and tools should be adapted as necessary (don't let a given methodology artificially constrain you). The deliberate use of specific methods for failure or error identification should be used.
Creativity is inhibited or encouraged by different influences. Some techniques for encouraging creativity are:
Interrupt the activity to create incubation periods (but be careful; too many interruptions can be disruptive).
Apply different solution-finding methods.
Move from abstract to concrete ideas.
Find and collect information from design catalogues (such as design patterns).
Divide work among architecture team members.
Make realistic plans: Realistic planning is found to encourage motivation and creativity, while unrealistic planning is inhibiting.
Analysis
Analysis is the decomposition of complex systems into elements and their interrelationships, identifying essential distinctions, and discarding accidental distinctions. The activities of analysis include identification, definition, and structuring with the purpose of acquiring information about a subject that can be transformed into knowledge. Analytic methods are useful in all stages of software design, from requirements gathering to evaluating designs and technologies to implementation.
Formulating problems clearly and unambiguously, via analysis of an application domain, helps avoid many expensive design and implementation errors. Careful analysis and formulation of problems are two of the most important and effective tools a software architect has. All design methodologies have some analysis aspect. However, I find that many modern design methodologies tend to blur the distinction between analysis and design. Many object-oriented methodologies promote a seamless development concept where the problem or application domain is continuously transformed into a solution, for example, Object Modeling Technique (OMT). In practice, the analysis is rarely done or is not done adequately.
Structured analyses in software, such as the techniques of Gane and Sarson, Yourdon, DeMarco, Ward and Mellor, and the Structured Systems Analysis and Design Methodology (SSADM), are methods for formulating and structuring the problem. Structured analysis is a process where the problem is formulated in terms of data flows, as represented in data flow diagrams (DFDs) and in system state transitions as represented in state transition diagrams. These models emphasize a hierarchical structuring of the functions of a system.
Similarly, object-oriented analysis, such as the techniques of Jacobson, Booch, Rumbaugh (OMT), and Yourdon and Coad, are techniques for structuring the problem domain in terms of objects, their interrelationships, and their class hierarchies. Whereas structured analysis emphasizes a functional hierarchy, object orientation emphasizes a data hierarchy.
Abstraction
Through abstraction, we can infer more general and comprehensive relationships among the elements of our problem. Abstraction reduces the complexity of a problem while emphasizing the essential characteristics of it and aids in the discovery of solutions. Abstractions are not always invented; sometimes they are discovered by using existing abstraction models and attempting to fit the problem into them.
This is an example of predication: A statement is created about the problem abstraction and an existing model such as "problem A (new) is a form of problem B (existing)." An otherwise seemingly novel problem may turn out to be a variation of an existing problem to which some known solutions already exist. By formulating problem A in terms of problem B, the architect then only needs to find suitable abstractions for the remaining part of problem A. A problem can have many abstractions, and, using a discursive approach, the architect can discover several suitable abstractions and apply many existing problem models. Metamodels or reference models are examples of such reusable abstractions.
Analysis aids in the discovery and evaluation of abstractions. Not all analysis results in abstractions, but most abstractions are discovered via analysis.
Synthesis
Synthesis is the combining of individual elements or parts to produce a new effect. It is the integration of solutions to subproblems and the evaluation of the resulting system. When we decompose a problem via analysis into sub-problems and discover solutions to those subproblems, there is still the risk that synthesizing those solutions will not solve the larger problem entirely or, worse, the solutions will be incompatible. Existing abstraction models may also be synthesized to form larger, more specialized abstractions. Synthesis is not only applied to the models of software architecture, it is also applied to the design methods
General Heuristics
In this section, we look at some heuristic design methods. Heuristics are techniques that are characterized as the searching for suitable solutions. These methods apply to many design tasks:
Persistent questions
Negation
Forward steps
Backward steps
Factorization
Systematic variation
Division of labor and collaboration
The Method of Persistent Questions
This method is useful when applying any systematic procedure such as requirements engineering (systems analysis), architectural design, and architectural evaluation. Requirements are almost never complete or at the right level of abstraction and the architect must help the acquirer to discover the essential requirements of the application they are envisioning during the analysis of the requirements. Persistent questioning stimulates ideas and intuition and helps to eliminate assumptions and preconceived notions. The method of persistent questions is a tool that the architect may use when analyzing the problem to discover useful abstractions, as well as a tool for evaluating solutions. An architect or architecture team may even keep a database of standard sets of questions for various purposes. Such a database of questions helps extend the memory of the architect and transfer useful design methods and knowledge to others. Asking questions is considered one of the most important methodological tools, and the technique is found in many existing product development methodologies
The Method of Persistent Questions
This method is useful when applying any systematic procedure such as requirements engineering (systems analysis), architectural design, and architectural evaluation. Requirements are almost never complete or at the right level of abstraction and the architect must help the acquirer to discover the essential requirements of the application they are envisioning during the analysis of the requirements. Persistent questioning stimulates ideas and intuition and helps to eliminate assumptions and preconceived notions. The method of persistent questions is a tool that the architect may use when analyzing the problem to discover useful abstractions, as well as a tool for evaluating solutions. An architect or architecture team may even keep a database of standard sets of questions for various purposes. Such a database of questions helps extend the memory of the architect and transfer useful design methods and knowledge to others. Asking questions is considered one of the most important methodological tools, and the technique is found in many existing product development methodologies
The Method of Forward Steps
The method of forward steps is also known as the method of divergent thought. It starts with a first solution attempt and proceeds to follow as many solution paths as possible, yielding other solutions. The method of forward steps is not necessarily systematic and usually starts with an unsystematic divergence of ideas. For example, the first solution attempt at an application problem may be to apply a client/server architectural style. By applying forward steps, the architect follows several paths such as browser-based client, Web client with browser plug-ins, fat client with embedded browser, or fat client that speaks HTTP with the server.
This method can be applied to any model at any level of abstraction and is typically followed recursively as far down a path as possible. For example, starting with the fat client that speaks HTTP solution, additional application of the method of forward steps could yield solutions like fat client with local storage, fat client with server-side storage only, and fat client with heterogeneous local and server-side storage. The process can follow any path. This is a good way to brainstorm over an object model of the application domain as well as the choice of technologies in the solution domain. This method is similar to the method of systematic variation.
The Method of Backward Steps
The method of backward steps is also known as the method of convergent thought. In this approach, the architect starts with a goal in mind rather than the initial problem. This technique is most useful for setting up an engineering design process for a product and a product development plan after the architecture has been determined. Starting with the final objective of the development effort, all (or a reasonable subset of) possible paths that could have led up to the objective are retraced. This method is useful not only in preparing an engineering process but also for organizing an engineering department around the architecture of a product (known as Conway's law).
The Method of Factorization
This method is the basis of the refactoring technique, popular among software engineers when reworking existing source code to make it more readable, manageable, maintainable, and reusable. The method involves breaking a complex system into less complex elements or factors. Factorization is a type of analysis method. In architecting, this technique is used to find the essential problems being solved (for example, factoring the objectives into subobjectives). Just as in mathematics, the factorization may not be obvious and requires some insight, skill, and lots of practice. In algebra, you may factor an equation by introducing zero as a factor. Similarly, finding that one of the factors of a publishing system is a file-versioning repository may not be obvious (although the experienced architect may see the factorization immediately). Another example is taking what may appear to be an indivisible component and finding a way to divide it into two components and an interface.
The Method of Systematic Variation
The method of systematic variation of solutions may have originated with Leonardo DaVinci. DaVinci kept meticulous notes on his ideas and inventions and applied this technique to derive multiple variations of ideas, each varying only by a single characteristic from the former. The method starts with a generalized classification structure, such as a class hierarchy, that represents the various problem characteristics and possible solutions. By systematically varying a single characteristic, the architect may discover more optimized solutions. The approach yields a solution field. Evaluation techniques can be applied to each solution to determine its suitability.
Division of Labor and Collaboration
The study of human factors has found that implementing large and complex tasks requires a division of labor. The more specialized the task the more important the division of labor. Software development tasks are commonly based not only on functional areas of the system but also on the technology used. We typically have user interface designers, user interface engineers, middle-tier engineers, back-end or database engineers, test engineers, configuration management engineers, and so on. A complex application or system also benefits from a division of labor with respect to the architecture. For example, it seems natural to separate the tasks of requirements engineering, functional specification, interaction design, and structural design, all of which are in the scope of architecture. However, whenever there is a division of labor there is an information exchange problem. Systematic methods and the creation of models can help overcome this problem.
The Architecture Design Process
the architectural view of software development is composed of a predesign phase, a domain analysis phase, a schematic design phase, and a design development phase. The focus of each phase is on a different, but possibly overlapping, set of problems. In the predesign phase, the architect is concerned mostly with forming and understanding the enterprise context in which an application will exist. This is represented by a model that depicts the system as an entity within a community of other entities, such as other software systems and human users. During the domain analysis phase, the application requirements are analyzed and structured. In particular, the requirements are those around the problem domain but not specific to the domain of software itself, such as user interface or HCI-related requirements. During the schematic design phase, the architect begins to develop the solution models such as identifying the modules of the system and the design rules that establish the boundaries between modules. Modules are discrete units of design work that rely on shared information and also have hidden information. Finally, during the design development phase, the architecture is refined and possibly multiple variations are created in order to explore the best fi
The basic architecture design process is composed of these steps:
Understand the problem.
Identify design elements and their relationships.
Evaluate the architecture design.
Transform the architecture design.
The first step is arguably the most crucial because it affects the quality of the design that follows. Without a clear understanding of the problem, it is not possible to create an effective solution.
In the second step, we identify design elements and their interdependencies. In the early phases of the design project, we perform a naive functional decomposition of the application, which establishes a baseline for future design tasks and design transformation. An example of this method can be seen in Jan Bosch's Design and Use of Software Architectures, which focuses on product-line architectures for real-time and embedded software systems. In Bosch's model, this step is called functionality-based architectural design (Bosch, 2000).
The third step involves assessing the architecture for conformance to architectural quality attribute requirements. The functional behavior of the application cannot be ideally tested from an architectural decomposition. However, many other quality attributes can be assessed by inspecting the design or by implementing prototypes of the architecturally significant component interactions.
The fourth step involves the application of design operations to transform the architecture design into a new design that addresses the quality attribute requirements better than the previous design. The phase may be repeated multiple times and even performed recursively
Identifying Design Elements and Their Relationships
In this step, we establish a baseline decomposition that initially splits the system based on functional requirements. The decomposition can be modeled using a design structure matrix (DSM), which represents the dependencies between design elements without prescribing the granularity of the elements. A first draft of this model could be created during the predesign phase, and then revised during subsequent steps.
Evaluating the Architecture
The third step involves evaluating the architectural design to determine if it satisfies the architectural requirements. The design is evaluated in order to gather qualitative measures or quantitative data, both of which are metrics
Transforming the Architecture
This step is performed after an evaluation or informal assessment of the architectural design. If the architectural design does not fully satisfy its quality attribute requirements, then it must be changed until it does satisfy them. However, instead of starting from scratch, we can take the existing design and apply design operators to it in order to transform it. The new version of the design is then assessed and the process continues until a satisfactory design is achieved. Sometimes you may need to reverse (undo) operations that were already applied and go down a different design path. You may also be creating several candidate designs at the same time. Starting with an initial root design (perhaps a single monolithic module), you may create a directed graph of designs. Each node represents a design decision path. Some paths may merge, in which case the application of design operations are commutative. In this case, you may transform some of the designs and eliminate ones that are obviously not going to transform well based on the requirements.
A design is transformed by applying design operators, styles, or patterns. There are two types of design operators: those that affect the modular architecture and those that affect the component architecture. There are six modular operators (Baldwin, 2000):
Splitting a design into two or more modules
Substituting one design module for another
Augmenting the system by adding a new module
Excluding a module from the system
Inverting a module to create new interfaces (design rules)
Porting a module to another system
Similar to the modular operators are design operators. The basic design operators identified by Bass (Bass, 1998) are:
Decomposition of a system into components.
Replication of components to improve reliability.
Compression of two or more components into a single component to improve performance.
Abstraction of a component to improve modifiability and adaptability.
Resource sharing, or the sharing of a single component instance with other components to improve integrability (the ability to integrate applications and systems), portability, and modifiability.
Modular and design operators are very similar. The modular operators are concerned with the module view of the system: those units of individual design and development that primarily affect the nonoperational qualities. The design operators are concerned with the runtime component view of the system, which are those units of execution that primarily affect the operational qualities
The basic architecture design process is composed of these steps:
Understand the problem.
Identify design elements and their relationships.
Evaluate the architecture design.
Transform the architecture design.
The first step is arguably the most crucial because it affects the quality of the design that follows. Without a clear understanding of the problem, it is not possible to create an effective solution.
In the second step, we identify design elements and their interdependencies. In the early phases of the design project, we perform a naive functional decomposition of the application, which establishes a baseline for future design tasks and design transformation. An example of this method can be seen in Jan Bosch's Design and Use of Software Architectures, which focuses on product-line architectures for real-time and embedded software systems. In Bosch's model, this step is called functionality-based architectural design (Bosch, 2000).
The third step involves assessing the architecture for conformance to architectural quality attribute requirements. The functional behavior of the application cannot be ideally tested from an architectural decomposition. However, many other quality attributes can be assessed by inspecting the design or by implementing prototypes of the architecturally significant component interactions.
The fourth step involves the application of design operations to transform the architecture design into a new design that addresses the quality attribute requirements better than the previous design. The phase may be repeated multiple times and even performed recursively
Identifying Design Elements and Their Relationships
In this step, we establish a baseline decomposition that initially splits the system based on functional requirements. The decomposition can be modeled using a design structure matrix (DSM), which represents the dependencies between design elements without prescribing the granularity of the elements. A first draft of this model could be created during the predesign phase, and then revised during subsequent steps.
Evaluating the Architecture
The third step involves evaluating the architectural design to determine if it satisfies the architectural requirements. The design is evaluated in order to gather qualitative measures or quantitative data, both of which are metrics
Transforming the Architecture
This step is performed after an evaluation or informal assessment of the architectural design. If the architectural design does not fully satisfy its quality attribute requirements, then it must be changed until it does satisfy them. However, instead of starting from scratch, we can take the existing design and apply design operators to it in order to transform it. The new version of the design is then assessed and the process continues until a satisfactory design is achieved. Sometimes you may need to reverse (undo) operations that were already applied and go down a different design path. You may also be creating several candidate designs at the same time. Starting with an initial root design (perhaps a single monolithic module), you may create a directed graph of designs. Each node represents a design decision path. Some paths may merge, in which case the application of design operations are commutative. In this case, you may transform some of the designs and eliminate ones that are obviously not going to transform well based on the requirements.
A design is transformed by applying design operators, styles, or patterns. There are two types of design operators: those that affect the modular architecture and those that affect the component architecture. There are six modular operators (Baldwin, 2000):
Splitting a design into two or more modules
Substituting one design module for another
Augmenting the system by adding a new module
Excluding a module from the system
Inverting a module to create new interfaces (design rules)
Porting a module to another system
Similar to the modular operators are design operators. The basic design operators identified by Bass (Bass, 1998) are:
Decomposition of a system into components.
Replication of components to improve reliability.
Compression of two or more components into a single component to improve performance.
Abstraction of a component to improve modifiability and adaptability.
Resource sharing, or the sharing of a single component instance with other components to improve integrability (the ability to integrate applications and systems), portability, and modifiability.
Modular and design operators are very similar. The modular operators are concerned with the module view of the system: those units of individual design and development that primarily affect the nonoperational qualities. The design operators are concerned with the runtime component view of the system, which are those units of execution that primarily affect the operational qualities
Software architecting involves
Software architecting involves the design of a system from multiple viewpoints. The common viewpoints used in software engineering are the technology stack (or physical) view, the object (or data) model, and the use case (or behavioral) view. These viewpoints are useful and necessary because they capture many types of design decisions and represent many system qualities such as functionality, information, and physical construction. They do not represent many other important system quality attributes such as modifiability, buildability, security, reliability, and performance, nor do they represent non-operational or business-oriented qualities such as the ability to reduce development and maintenance costs.
The problem with representing an architecture with this single technology-focused view is that we only see a vertical slice through a multidimensional system. Many architectural decisions cannot be represented in this view. If this is the only view we create, then we will probably neglect the other views to the detriment of the system itself.
There are a couple of philosophies concerning how to improve the software crisis. One approach is to improve the quality of the software development process. In this school of thought, quality can be improved by using iterative development techniques, rapid application development (RAD) tools, frequent integration and testing, and keeping careful records so that an organization can build up historical data that will aid in improving the process in future product cycles. It uses iterative/increment development processes like the Rational Unified Process and the Capability Maturity Model (CMM). Another approach for improving software quality is to stay away from the heavyweight planning-oriented processes and instead adopt agile processes and use of techniques such as RAD and eXtreme Programming (XP).
The problem with representing an architecture with this single technology-focused view is that we only see a vertical slice through a multidimensional system. Many architectural decisions cannot be represented in this view. If this is the only view we create, then we will probably neglect the other views to the detriment of the system itself.
There are a couple of philosophies concerning how to improve the software crisis. One approach is to improve the quality of the software development process. In this school of thought, quality can be improved by using iterative development techniques, rapid application development (RAD) tools, frequent integration and testing, and keeping careful records so that an organization can build up historical data that will aid in improving the process in future product cycles. It uses iterative/increment development processes like the Rational Unified Process and the Capability Maturity Model (CMM). Another approach for improving software quality is to stay away from the heavyweight planning-oriented processes and instead adopt agile processes and use of techniques such as RAD and eXtreme Programming (XP).
Monday, August 13, 2007
Lightweight Enterprise Architectures
Lightweight Enterprise Architecture (LEA) combines the successful elements of architecture implemented in organizations today, provides a simple framework that does not burden the organization, and offers quicker results. LEA is not a rigid architecture that requires a long learning cycle, but provides a solid framework to more successfully evolve the technical landscape of most organizations today. LEA is a simpler set of responsibilities and deliverables for the architect to facilitate better communication between the resources in an organization.
In addition, the success of integrating technology is not simply building a technical masterpiece, as there are many other factors of success. First, technology needs to offer the organization the needed functionality to deliver a product or service to the marketplace with minimal effort. This means that technology needs alignment with the direction of the corporate strategy and fit within the current infrastructure of the organization. Technology is not just building a better technical solution, but understanding the processes, people, and goals of the organization — all within the limits of striving for profitability. This is the core goal of successful enterprise architecture and the force behind the development of LEA.
Enterprise architecture as defined through LEA focuses on aligning all the systems in the organization to meet the needs of business from a holistic business perspective. It is the goal of enterprise architecture to deploy all the components of systems together as a whole, versus optimizing a particular aspect of technology. That is, it is more important to deliver a better total solution even through the sacrifice of one or more parts of the system. Specific architectures (e.g., application architecture, security architecture, etc.) are concerned with optimal design and evolution of their particular domain. These specific architectures in LEA play a support role and are critical to the successful execution of enterprise architecture but do not drive the enterprise architecture.
LEA bridges the gap of business vision and the technical community through a simple framework of architectural responsibilities. These responsibilities require a minimal set of deliverables other resources use (or consume) that progressively transforms the visions of the enterprise into structured, executable artifacts for technology. The simplicity of LEA is that in progressive stages of enterprise architecture, the artifacts support and build into the next set of artifacts. By keeping to a minimal set and building the artifacts onto each other, LEA is a simple framework to understand. This ultimately increases the chance of success as this design is more usable by diverse resources, simplifies communications, and reduces drifts of interpretation from vision to implementation
To better help the architect with these various levels of responsibility, LEA frames these into three separate and interrelated perspectives. LEA consists of three realms (or perspectives) of architecture that include Strategic Architecture, Conceptual Architecture, and Execution Architecture.
The Strategic Architecture focuses on building strategic principles and developing guidelines by working closely with the leadership of an organization. Taking input from the business vision and goals, the Strategic Architecture frames the measures and practices for the enterprise's technology. Essentially, the Strategic Architecture sets the direction for LEA to ensure effort on technology is consistent with the needs and visions of the enterprise.
Often in organizations, some of these activities are in the IT strategic plan. However, IT strategic plans often are vehicles promoting the budget requirements of a department versus an enterprise view. In LEA, the Strategic Architecture is a continuous, ongoing process to translate business strategy and provide the framework guiding technology stewardship as best interpreted from leadership.
Strategic Architecture
The Strategic Architecture goal is to capture the vision of leadership that translates readily for adoption in system design. Many strategy plans are well designed but are written by and mainly for the adoption of the business owners. Very few strategies offer the perspective of how to change systems, but rather focus on the intended outcome — either functional or budgetary needs. Some strategies provide some indication of how systems should change, but these are again mainly to reflect the business needs with minimal account for the technological impacts.
However, this does not mean the reformulation of the strategic plan to benefit technology, but rather the need for the translation of the strategic plan into tangible guides for technology to be successful
Business Strategy and LEA
In the Strategic Architecture, the architect needs good interaction with leadership and the business owners to best understand their stake in the future of the enterprise. This often entails participation in strategy meetings and identifying impacts on technology and the potential effect on various strategic scenarios. However, the key to a successful Strategic Architecture is the development of a core Strategic Architecture that remains consistent over time.
A good Strategic Architecture contains the following three fundamental components:
Enterprise Principles
Enterprise Patterns
Enterprise Guidelines
In addition, the success of integrating technology is not simply building a technical masterpiece, as there are many other factors of success. First, technology needs to offer the organization the needed functionality to deliver a product or service to the marketplace with minimal effort. This means that technology needs alignment with the direction of the corporate strategy and fit within the current infrastructure of the organization. Technology is not just building a better technical solution, but understanding the processes, people, and goals of the organization — all within the limits of striving for profitability. This is the core goal of successful enterprise architecture and the force behind the development of LEA.
Enterprise architecture as defined through LEA focuses on aligning all the systems in the organization to meet the needs of business from a holistic business perspective. It is the goal of enterprise architecture to deploy all the components of systems together as a whole, versus optimizing a particular aspect of technology. That is, it is more important to deliver a better total solution even through the sacrifice of one or more parts of the system. Specific architectures (e.g., application architecture, security architecture, etc.) are concerned with optimal design and evolution of their particular domain. These specific architectures in LEA play a support role and are critical to the successful execution of enterprise architecture but do not drive the enterprise architecture.
LEA bridges the gap of business vision and the technical community through a simple framework of architectural responsibilities. These responsibilities require a minimal set of deliverables other resources use (or consume) that progressively transforms the visions of the enterprise into structured, executable artifacts for technology. The simplicity of LEA is that in progressive stages of enterprise architecture, the artifacts support and build into the next set of artifacts. By keeping to a minimal set and building the artifacts onto each other, LEA is a simple framework to understand. This ultimately increases the chance of success as this design is more usable by diverse resources, simplifies communications, and reduces drifts of interpretation from vision to implementation
To better help the architect with these various levels of responsibility, LEA frames these into three separate and interrelated perspectives. LEA consists of three realms (or perspectives) of architecture that include Strategic Architecture, Conceptual Architecture, and Execution Architecture.
The Strategic Architecture focuses on building strategic principles and developing guidelines by working closely with the leadership of an organization. Taking input from the business vision and goals, the Strategic Architecture frames the measures and practices for the enterprise's technology. Essentially, the Strategic Architecture sets the direction for LEA to ensure effort on technology is consistent with the needs and visions of the enterprise.
Often in organizations, some of these activities are in the IT strategic plan. However, IT strategic plans often are vehicles promoting the budget requirements of a department versus an enterprise view. In LEA, the Strategic Architecture is a continuous, ongoing process to translate business strategy and provide the framework guiding technology stewardship as best interpreted from leadership.
Strategic Architecture
The Strategic Architecture goal is to capture the vision of leadership that translates readily for adoption in system design. Many strategy plans are well designed but are written by and mainly for the adoption of the business owners. Very few strategies offer the perspective of how to change systems, but rather focus on the intended outcome — either functional or budgetary needs. Some strategies provide some indication of how systems should change, but these are again mainly to reflect the business needs with minimal account for the technological impacts.
However, this does not mean the reformulation of the strategic plan to benefit technology, but rather the need for the translation of the strategic plan into tangible guides for technology to be successful
Business Strategy and LEA
In the Strategic Architecture, the architect needs good interaction with leadership and the business owners to best understand their stake in the future of the enterprise. This often entails participation in strategy meetings and identifying impacts on technology and the potential effect on various strategic scenarios. However, the key to a successful Strategic Architecture is the development of a core Strategic Architecture that remains consistent over time.
A good Strategic Architecture contains the following three fundamental components:
Enterprise Principles
Enterprise Patterns
Enterprise Guidelines
Agent Toolkits
Agent-based applications need a significant amount of enabling infrastructure before even one message is exchanged between agents. A large set of supporting services must be made available throughout an agent-based system before the application developer can move on to focus on the application domain, be it e-business, Grid computing, or Ambient Intelligence. Such services range from basic communication to discovery, coordination, security, and so on, and come together to provide an environment that can support agent-based computing. In this way, they can be considered as providing the operating system for agents
Agent Architectures : OTHER APPROACHES
AGENTO and PLACA
In the examples so far, the focus has been on agent architectures to support the design of agent-based systems. Another approach to building agents is to design a programming language with semantics based on some theory of rational or intentional agency, such as the BDI model, and to program the desired behavior of individual agents directly using mental attitudes. Such a technique is referred to as agent-oriented programming (AOP). An agent-oriented program comprises a set of transition rules that specify how an agent in a given mental state will respond to an input, which may be a set of messages from other agents, by defining its new mental state and any outputs.
The language we describe here is PLACA [44], which extends the expressive power of AGENTO [45] developed by Shoham, who introduced the concept of agent-oriented programs. We do not describe PLACA in detail, but include it simply as an example of an alternative approach, especially because of its formal nature, which provides a counterpoint to the earlier architectures in this chapter. This section thus only includes brief summaries, and the interested reader can explore further through the references.
When it was first introduced, AGENTO (and later its successor, PLACA) represented a new programming paradigm that supported the notion of a societal view of computation in which agents would interact with each other in order to achieve their individual goals. Shoham asserted that an approach that could enable a system of agents to be built in this way needs three particular elements, as follows:
It requires a formal logical language to describe the mental state of each agent. Such mental state consists of beliefs and intentions, as we have seen in other systems described in this chapter.
It also needs a programming language with which to specify the agents and their behavior.
Finally, it needs a method for adapting nonagent legacy systems so that they can be incorporated into an agent system, thereby allowing agents to communicate with them by attributing beliefs and intentions.
A program in PLACA is defined by an initial mental state and a set of mental-state rules specifying how the mental state changes in various scenarios. At run time, an agent's state consists of capabilities and its mental state, which comprises beliefs, intentions, and plans (where plans, and possibly intentions, are initially empty). At every step, an agent collects messages that have been received from others from the input buffer, clears this buffer, and updates its mental state according to its defining program.
At the beginning of each execution step, those transition rules that are satisfied in the current state are identified, and applied to the current mental state and messages collected from the input buffer. Once the mental state is updated, messages that need to be sent are placed in the output buffer, and actions that need to be performed are recorded and executed in the next step. If there is sufficient time before the next tick of the clock, the planner may construct and refine current plans for satisfying intentions. A basic representation of the PLACA interpreter is shown in Figure 2.7.
Figure 2.7: The PLACA interpreter. (After: [44].)
PLACA is based on a modal logic specification of the relationship between the mental-state components. Its designers claim that PLACA agents satisfy all the axioms provided, but the relationship between the logic and the programming language is not well-defined. This is a persistent problem in the agent field: how to determine the correspondence between computational systems on the one hand, and formal models, typically constructed in modal logic, on the other. One approach to this problem is to carefully design temporal logics so that agents can be described using logic formulas that are directly executable, as we will see next.
2.6.2 Concurrent METATEM
The same societal view of computation as in AOP is also present in Concurrent METATEM [46], a programming language in which each agent is defined as a concurrently executing process, communicating with other such processes via message-passing. The distinct characteristic of this work is that agents are specified using a temporal logic that is directly executable. To directly execute a specification written in a temporal logic formula, the interpreter attempts to construct a model structure in which the agent specification is satisfied. However, since the environment is dynamic, it may constantly be altering that model, so that responses must be made to what has just become true or untrue because of this dynamism.
The way in which the model is constructed in a dynamic environment is referred to as the execution strategy. When a Concurrent METATEM program is executed, it produces a sequence of temporally ordered states, each labeled with a model structure stating those propositions that are true. This trace provides Concurrent METATEM specifications with a concrete computational interpretation.
The basic form of a specification in Concurrent METATEM is as follows: "on the basis of what has happened in the past do something in the future." Thus, each agent is specified by a set of rules of the form:
and at each cycle, the precedent of each rule is matched against an internal history, firing if a match can be found. Once a rule fires, the agent is committed to the antecedent, which typically involves trying to make some predicate true.
As an example, consider the following Concurrent METATEM program, specifying the behavior of a controller agent solely responsible for supplying an infinitely renewable resource [47]. While the resource cannot be used by two agents at the same time, it is possible that the controller may be asked by two different agents for the resource simultaneously. The predicates ask(x) and give(x) mean that agent x has been asked for the resource, and that agent x has been given the resource, respectively.
In temporal logic, the formula, ○Form, is satisfied at present if Form is satisfied at the next time moment. Similarly, ◊Form is satisfied at present if Form is true at some time in the future, and FG is satisfied if F is true since G has been true.
The specification of the controller agent is defined in Concurrent METATEM as follows:
These three formulas can be interpreted in English as follows:
If an agent asks, then eventually give the resource to that agent;
Do not give to anyone unless they have asked since you last gave to them;
If you give to two people, then they must be the same person.
Concurrent METATEM is attractive because it is directly executable so that no time-consuming and error-prone refinement is required in the process from specification to implementation. In addition, specifications have a concrete computational semantics defined by the sequence of models that arise through the constant interplay of the dynamic environment and the action of the agent. However, since the execution of Concurrent METATEM is based on theorem-proving, some standard problems arise such as the undecidability of first-order logic and the complexity involved in simple propositional logic. In addition, it is not clear how other modal operators commonly associated with agents such as belief, desire, and intention could be incorporated into the language while maintaining its directly executable property.
In the examples so far, the focus has been on agent architectures to support the design of agent-based systems. Another approach to building agents is to design a programming language with semantics based on some theory of rational or intentional agency, such as the BDI model, and to program the desired behavior of individual agents directly using mental attitudes. Such a technique is referred to as agent-oriented programming (AOP). An agent-oriented program comprises a set of transition rules that specify how an agent in a given mental state will respond to an input, which may be a set of messages from other agents, by defining its new mental state and any outputs.
The language we describe here is PLACA [44], which extends the expressive power of AGENTO [45] developed by Shoham, who introduced the concept of agent-oriented programs. We do not describe PLACA in detail, but include it simply as an example of an alternative approach, especially because of its formal nature, which provides a counterpoint to the earlier architectures in this chapter. This section thus only includes brief summaries, and the interested reader can explore further through the references.
When it was first introduced, AGENTO (and later its successor, PLACA) represented a new programming paradigm that supported the notion of a societal view of computation in which agents would interact with each other in order to achieve their individual goals. Shoham asserted that an approach that could enable a system of agents to be built in this way needs three particular elements, as follows:
It requires a formal logical language to describe the mental state of each agent. Such mental state consists of beliefs and intentions, as we have seen in other systems described in this chapter.
It also needs a programming language with which to specify the agents and their behavior.
Finally, it needs a method for adapting nonagent legacy systems so that they can be incorporated into an agent system, thereby allowing agents to communicate with them by attributing beliefs and intentions.
A program in PLACA is defined by an initial mental state and a set of mental-state rules specifying how the mental state changes in various scenarios. At run time, an agent's state consists of capabilities and its mental state, which comprises beliefs, intentions, and plans (where plans, and possibly intentions, are initially empty). At every step, an agent collects messages that have been received from others from the input buffer, clears this buffer, and updates its mental state according to its defining program.
At the beginning of each execution step, those transition rules that are satisfied in the current state are identified, and applied to the current mental state and messages collected from the input buffer. Once the mental state is updated, messages that need to be sent are placed in the output buffer, and actions that need to be performed are recorded and executed in the next step. If there is sufficient time before the next tick of the clock, the planner may construct and refine current plans for satisfying intentions. A basic representation of the PLACA interpreter is shown in Figure 2.7.
Figure 2.7: The PLACA interpreter. (After: [44].)
PLACA is based on a modal logic specification of the relationship between the mental-state components. Its designers claim that PLACA agents satisfy all the axioms provided, but the relationship between the logic and the programming language is not well-defined. This is a persistent problem in the agent field: how to determine the correspondence between computational systems on the one hand, and formal models, typically constructed in modal logic, on the other. One approach to this problem is to carefully design temporal logics so that agents can be described using logic formulas that are directly executable, as we will see next.
2.6.2 Concurrent METATEM
The same societal view of computation as in AOP is also present in Concurrent METATEM [46], a programming language in which each agent is defined as a concurrently executing process, communicating with other such processes via message-passing. The distinct characteristic of this work is that agents are specified using a temporal logic that is directly executable. To directly execute a specification written in a temporal logic formula, the interpreter attempts to construct a model structure in which the agent specification is satisfied. However, since the environment is dynamic, it may constantly be altering that model, so that responses must be made to what has just become true or untrue because of this dynamism.
The way in which the model is constructed in a dynamic environment is referred to as the execution strategy. When a Concurrent METATEM program is executed, it produces a sequence of temporally ordered states, each labeled with a model structure stating those propositions that are true. This trace provides Concurrent METATEM specifications with a concrete computational interpretation.
The basic form of a specification in Concurrent METATEM is as follows: "on the basis of what has happened in the past do something in the future." Thus, each agent is specified by a set of rules of the form:
and at each cycle, the precedent of each rule is matched against an internal history, firing if a match can be found. Once a rule fires, the agent is committed to the antecedent, which typically involves trying to make some predicate true.
As an example, consider the following Concurrent METATEM program, specifying the behavior of a controller agent solely responsible for supplying an infinitely renewable resource [47]. While the resource cannot be used by two agents at the same time, it is possible that the controller may be asked by two different agents for the resource simultaneously. The predicates ask(x) and give(x) mean that agent x has been asked for the resource, and that agent x has been given the resource, respectively.
In temporal logic, the formula, ○Form, is satisfied at present if Form is satisfied at the next time moment. Similarly, ◊Form is satisfied at present if Form is true at some time in the future, and FG is satisfied if F is true since G has been true.
The specification of the controller agent is defined in Concurrent METATEM as follows:
These three formulas can be interpreted in English as follows:
If an agent asks, then eventually give the resource to that agent;
Do not give to anyone unless they have asked since you last gave to them;
If you give to two people, then they must be the same person.
Concurrent METATEM is attractive because it is directly executable so that no time-consuming and error-prone refinement is required in the process from specification to implementation. In addition, specifications have a concrete computational semantics defined by the sequence of models that arise through the constant interplay of the dynamic environment and the action of the agent. However, since the execution of Concurrent METATEM is based on theorem-proving, some standard problems arise such as the undecidability of first-order logic and the complexity involved in simple propositional logic. In addition, it is not clear how other modal operators commonly associated with agents such as belief, desire, and intention could be incorporated into the language while maintaining its directly executable property.
Agent Architectures : DISTRIBUTED AGENT ARCHITECTURES
The architectures described above may enable agents to interact with other agents. However, the design of these systems is concerned with the individual agents and the dimensions required to interact effectively with others. The macrolevel, conversely, considers a multiagent system from a holistic perspective, where interaction, coordination, and cooperation between agents are designed in advance of run time. The concern here is with the global system structure and mechanisms to support interaction, including agent communication protocols, and to enable effective coordination [32]. Although coordination is not the focus of this chapter, it is appropriate in the context of considering agent architectures to review at least some common mechanisms that are useful in providing such a holistic viewpoint.
2.5.1 Contract Net Protocol
Almost certainly, the most commonly employed coordination mechanism for controlling the problem-solving behavior of a collection of distributed agents is the contract net protocol [33]. This is concerned with the dynamic configuration and coordination of agents to form hierarchies that can achieve complex, distributed tasks.
In the examples of architectures above, there is generally no consideration of issues of coordination. In many systems in which agents interact, the forms of interaction and the relationships between agents are static, representing an unalterable structure. Since much of the value of agent-based computing derives from its ability to address the issues that arise from dynamic and open environments, however, this is inadequate. By contrast, the contract net protocol (CNP), proposed by Smith and Davis [33], provides a mechanism by which nodes (or agents) can dynamically create relationships in response to the current processing requirements of the system as a whole, thereby enabling opportunistic task allocation.
In the contract net framework, a node with a task to be achieved forms contracts with others who proceed to accomplish this task. The steps to forming and maintaining a contract are defined by the contract net protocol, described as follows, and shown in Figure 2.5:
A node decomposes a task into a number of subtasks. For each subtask, the node issues a task announcement describing what needs to be performed, along with eligibility requirements detailing the necessary processing requirements to complete the task.
Once a node receives a task announcement, if it fulfills the eligibility specification, it may bid for the task. Essentially, nodes evaluate their interest using task evaluation procedures specific to the problem at hand. If a node has sufficient interest in a task announcement, it will submit a bid to undertake to perform the task. A node will not bid unless it is free to perform the task.
Once all bids have been received by the original (potential manager) node, it ranks them according to criteria associated with the task, and awards a contract to the bidder with the highest ranked bid.
There is now a contract between the manager who made the task announcement and the bidder (the contractor) with the highest ranked bid. Over time, the manager monitors the problem-solving of the contractor, requesting progress reports or canceling the contract if necessary. The manager also integrates partial results from completed contracts to provide a complete solution to the original task.
The contractors issue reports to the manager, which may be interim reports, or final reports containing a result description. Finally, the manager terminates a contract with a termination message.
Figure 2.5: The contract net protocol.
The messages passed between the agents include information relating to the task, so that other nodes can evaluate whether they are suited to perform that task. For example, when the CNP is applied to the simulation of a distributed sensing system, a task announcement includes three types of information [34], as follows:
The Task Abstraction Slot specifies the identity and position of the manager that enables potential contractors to reply to the task announcement;
The Eligibility Specification specifies the location and capabilities required by any bidders;
The Bid Specification indicates that a bidder must specify its position and its sensing capabilities.
Contractor nodes may, in turn, subcontract parts of their task by announcing their own task announcements. In this way, the CNP is repeated with the contractor eventually becoming a manager for these subcontracts. This leads to a hierarchical configuration in the contract net, as shown in Figure 2.6.
Figure 2.6: The contract net manager-contractor hierarchy.
The contract net protocol was a novel means for dynamically allocating tasks in distributed systems, and it is still commonly found in many agent systems. However, it should be pointed out that it offers a very simple coordination mechanism, and does not provide any strategies for global coherence. It is thus only suited to situations in which the tasks are easily decomposable into independent subtasks. In addition, it is only suitable if agents are not in conflict, since it does not support mechanisms for bargaining or negotiating in general. However, it does serve to illustrate the general principles involved when considering the design of systems from the macrolevel perspective.
2.5.2 Agentis
Agent communication languages (ACLs) occupy a central position in the field of multiagent systems, underpinning the ability of different and heterogeneous agents to effectively interact. Efforts to develop and specify such languages continue, with perhaps the most significant languages to date being FIPA's ACL (see Chapter 5) and KQML, which have received much attention and interest for the last few years. At a basic level, communication languages do not encode information about how a particular message is received and used by a recipient in the context of a broader interaction—the higher-level structure that is required for effective and coherent agent interaction also needs to be investigated. (Some languages, such as FIPA ACL, are also tied to particular interaction protocols; Chapter 5 considers this further.)
The Agentis system is a framework for building interactive applications, and employs a set of just such protocols to ensure the reliable concurrent request and provision of services and tasks from and to agents. This is achieved in the context of an underlying asynchronous point-to-point messaging infrastructure (i.e., the standard one provided by dMARS [35]).
Agentis incorporates an agent interaction model that is based on well-defined notions of services and tasks. Services are units of work performed by Agentis agents. The usual flow of control is that a human user of the system requests one or more services, via a user interface process, from an agent dedicated to serving that user. Agents may also request and provide services from and to other agents, or from other interface processes such as database servers. Tasks are smaller units of work whose performance is part of the service contract that is created when an agent accepts a service request. For example, a user may be obliged to perform one or more information provision tasks to enable an agent to successfully complete a service.
In an Agentis system, a set of standard agents provide predefined services for process control and monitoring, user login and session management, and event logging. There are also user-configurable agents that provide user-defined services (specified in a high-level, dMARS-like, graphical process description language). In addition, a system may contain nonagent interface processes, such as user, database, or WWW interfaces that can request services from, or provide services to, Agentis agents. The framework is designed to be flexible and scalable, and to decouple the specification of custom application-dependent behavior from standard functionality. This makes it easy to design, configure, modify, and extend application systems whose key characteristic is that their behavior may be specified as sets of interactive event-driven or goal-driven processes.
The protocol set provides the ability to request, accept, or decline services and tasks, to return execution status information and output values progressively as they become available, and to cancel, suspend and resume services and tasks prior to completion. In addition, it is designed to guarantee that protocol message collisions are benign, that deadlocks do not occur, and that other constraints, such as the requirement that a task request only occurs in the context of a service provision, are enforced. It also includes a registration facility that provides service description, access control, and the ability for a service provider to inform a requestor about changes in service availability, as well as the ability to send simple notices or queries.
2.5.3 Other Approaches to Macrolevel Organization
Building agents that work together in a society for both individual and social value is clearly fundamental to building robust and effective multiagent systems in general. One such architecture, mentioned earlier, is DECAF, a software environment for the rapid design, development, and execution of intelligent agents to function together effectively in complex domains. This platform provides a means to evaluate such key social concepts as communication, planning, action scheduling, execution monitoring, coordination, and learning [30] The focus of DECAF is not on implementing specific agent architectures nor on building the basic communication primitives but rather on how generic behaviors can be reused, how plans can be easily built using a graphical editor, and how various existing middle-agents can be used.
Similarly, RETSINA [36] is a multiagent infrastructure that comprises a set of services, conventions, and knowledge that enable complex social interactions such as negotiation to take place. In this infrastructure the architecture of the individual agent is not considered, and all that is required is that the agent be "socially aware" and can communicate and interact with others and with the various infrastructural components supplied by RETSINA. It is claimed that the infrastructure can support any coordination scheme such as team behavior (see below), negotiation, and contract nets. What is deliberately not included in the architecture is any notion of social norms [37] [38] [39] [40], which are rules or conventions that a society of agents abide by such as, for example, driving on the correct side of the road in a particular locality. RETSINA does not consider such norms as part of the infrastructure but as being particular to the design of specific multiagent systems. RETSINA is considered in more detail in Chapter 3 in terms of its role as a toolkit.
A final example of macrolevel approaches can be seen in Teamcore. The key motivating principle behind the Teamcore architecture is that an agent integration infrastructure (a set of services and conventions) based on theoretical principles of coordination can automate robust coordination among heterogeneous agents in distributed systems [41]. Existing theories of teamwork on joint intentions and shared plans provide the analytical model for designing coordination that can be used to provide certain guarantees of system behavior. Even with a set of diverse heterogeneous agents, as long as they act as team members, each member acts responsibly to others, covers for execution failures, and exchanges key information as required. Other related work includes the open agent architecture (OAA) [42], a centralized integration architecture, and the adaptive agent architecture (AAA) [43], which provides a distributed extension to OAA.
2.5.1 Contract Net Protocol
Almost certainly, the most commonly employed coordination mechanism for controlling the problem-solving behavior of a collection of distributed agents is the contract net protocol [33]. This is concerned with the dynamic configuration and coordination of agents to form hierarchies that can achieve complex, distributed tasks.
In the examples of architectures above, there is generally no consideration of issues of coordination. In many systems in which agents interact, the forms of interaction and the relationships between agents are static, representing an unalterable structure. Since much of the value of agent-based computing derives from its ability to address the issues that arise from dynamic and open environments, however, this is inadequate. By contrast, the contract net protocol (CNP), proposed by Smith and Davis [33], provides a mechanism by which nodes (or agents) can dynamically create relationships in response to the current processing requirements of the system as a whole, thereby enabling opportunistic task allocation.
In the contract net framework, a node with a task to be achieved forms contracts with others who proceed to accomplish this task. The steps to forming and maintaining a contract are defined by the contract net protocol, described as follows, and shown in Figure 2.5:
A node decomposes a task into a number of subtasks. For each subtask, the node issues a task announcement describing what needs to be performed, along with eligibility requirements detailing the necessary processing requirements to complete the task.
Once a node receives a task announcement, if it fulfills the eligibility specification, it may bid for the task. Essentially, nodes evaluate their interest using task evaluation procedures specific to the problem at hand. If a node has sufficient interest in a task announcement, it will submit a bid to undertake to perform the task. A node will not bid unless it is free to perform the task.
Once all bids have been received by the original (potential manager) node, it ranks them according to criteria associated with the task, and awards a contract to the bidder with the highest ranked bid.
There is now a contract between the manager who made the task announcement and the bidder (the contractor) with the highest ranked bid. Over time, the manager monitors the problem-solving of the contractor, requesting progress reports or canceling the contract if necessary. The manager also integrates partial results from completed contracts to provide a complete solution to the original task.
The contractors issue reports to the manager, which may be interim reports, or final reports containing a result description. Finally, the manager terminates a contract with a termination message.
Figure 2.5: The contract net protocol.
The messages passed between the agents include information relating to the task, so that other nodes can evaluate whether they are suited to perform that task. For example, when the CNP is applied to the simulation of a distributed sensing system, a task announcement includes three types of information [34], as follows:
The Task Abstraction Slot specifies the identity and position of the manager that enables potential contractors to reply to the task announcement;
The Eligibility Specification specifies the location and capabilities required by any bidders;
The Bid Specification indicates that a bidder must specify its position and its sensing capabilities.
Contractor nodes may, in turn, subcontract parts of their task by announcing their own task announcements. In this way, the CNP is repeated with the contractor eventually becoming a manager for these subcontracts. This leads to a hierarchical configuration in the contract net, as shown in Figure 2.6.
Figure 2.6: The contract net manager-contractor hierarchy.
The contract net protocol was a novel means for dynamically allocating tasks in distributed systems, and it is still commonly found in many agent systems. However, it should be pointed out that it offers a very simple coordination mechanism, and does not provide any strategies for global coherence. It is thus only suited to situations in which the tasks are easily decomposable into independent subtasks. In addition, it is only suitable if agents are not in conflict, since it does not support mechanisms for bargaining or negotiating in general. However, it does serve to illustrate the general principles involved when considering the design of systems from the macrolevel perspective.
2.5.2 Agentis
Agent communication languages (ACLs) occupy a central position in the field of multiagent systems, underpinning the ability of different and heterogeneous agents to effectively interact. Efforts to develop and specify such languages continue, with perhaps the most significant languages to date being FIPA's ACL (see Chapter 5) and KQML, which have received much attention and interest for the last few years. At a basic level, communication languages do not encode information about how a particular message is received and used by a recipient in the context of a broader interaction—the higher-level structure that is required for effective and coherent agent interaction also needs to be investigated. (Some languages, such as FIPA ACL, are also tied to particular interaction protocols; Chapter 5 considers this further.)
The Agentis system is a framework for building interactive applications, and employs a set of just such protocols to ensure the reliable concurrent request and provision of services and tasks from and to agents. This is achieved in the context of an underlying asynchronous point-to-point messaging infrastructure (i.e., the standard one provided by dMARS [35]).
Agentis incorporates an agent interaction model that is based on well-defined notions of services and tasks. Services are units of work performed by Agentis agents. The usual flow of control is that a human user of the system requests one or more services, via a user interface process, from an agent dedicated to serving that user. Agents may also request and provide services from and to other agents, or from other interface processes such as database servers. Tasks are smaller units of work whose performance is part of the service contract that is created when an agent accepts a service request. For example, a user may be obliged to perform one or more information provision tasks to enable an agent to successfully complete a service.
In an Agentis system, a set of standard agents provide predefined services for process control and monitoring, user login and session management, and event logging. There are also user-configurable agents that provide user-defined services (specified in a high-level, dMARS-like, graphical process description language). In addition, a system may contain nonagent interface processes, such as user, database, or WWW interfaces that can request services from, or provide services to, Agentis agents. The framework is designed to be flexible and scalable, and to decouple the specification of custom application-dependent behavior from standard functionality. This makes it easy to design, configure, modify, and extend application systems whose key characteristic is that their behavior may be specified as sets of interactive event-driven or goal-driven processes.
The protocol set provides the ability to request, accept, or decline services and tasks, to return execution status information and output values progressively as they become available, and to cancel, suspend and resume services and tasks prior to completion. In addition, it is designed to guarantee that protocol message collisions are benign, that deadlocks do not occur, and that other constraints, such as the requirement that a task request only occurs in the context of a service provision, are enforced. It also includes a registration facility that provides service description, access control, and the ability for a service provider to inform a requestor about changes in service availability, as well as the ability to send simple notices or queries.
2.5.3 Other Approaches to Macrolevel Organization
Building agents that work together in a society for both individual and social value is clearly fundamental to building robust and effective multiagent systems in general. One such architecture, mentioned earlier, is DECAF, a software environment for the rapid design, development, and execution of intelligent agents to function together effectively in complex domains. This platform provides a means to evaluate such key social concepts as communication, planning, action scheduling, execution monitoring, coordination, and learning [30] The focus of DECAF is not on implementing specific agent architectures nor on building the basic communication primitives but rather on how generic behaviors can be reused, how plans can be easily built using a graphical editor, and how various existing middle-agents can be used.
Similarly, RETSINA [36] is a multiagent infrastructure that comprises a set of services, conventions, and knowledge that enable complex social interactions such as negotiation to take place. In this infrastructure the architecture of the individual agent is not considered, and all that is required is that the agent be "socially aware" and can communicate and interact with others and with the various infrastructural components supplied by RETSINA. It is claimed that the infrastructure can support any coordination scheme such as team behavior (see below), negotiation, and contract nets. What is deliberately not included in the architecture is any notion of social norms [37] [38] [39] [40], which are rules or conventions that a society of agents abide by such as, for example, driving on the correct side of the road in a particular locality. RETSINA does not consider such norms as part of the infrastructure but as being particular to the design of specific multiagent systems. RETSINA is considered in more detail in Chapter 3 in terms of its role as a toolkit.
A final example of macrolevel approaches can be seen in Teamcore. The key motivating principle behind the Teamcore architecture is that an agent integration infrastructure (a set of services and conventions) based on theoretical principles of coordination can automate robust coordination among heterogeneous agents in distributed systems [41]. Existing theories of teamwork on joint intentions and shared plans provide the analytical model for designing coordination that can be used to provide certain guarantees of system behavior. Even with a set of diverse heterogeneous agents, as long as they act as team members, each member acts responsibly to others, covers for execution failures, and exchanges key information as required. Other related work includes the open agent architecture (OAA) [42], a centralized integration architecture, and the adaptive agent architecture (AAA) [43], which provides a distributed extension to OAA.
Agent Architectures :HYBRID AGENT ARCHITECTURES
HYBRID AGENT ARCHITECTURES
In general, agents can be neither totally deliberative nor totally reactive. If they are only reactive, they cannot reason about their actions and will not be able to achieve any sophisticated behavior; if they are just deliberative they may never be able to act in time.
It is now generally recognized, therefore, that if agent systems are to survive in real and complex environments they need to be reactive in order to respond to environmental changes with sufficient speed, and be deliberative in order to achieve complex goals without deleteriously affecting longer-term options [27]. If environments change rapidly or unexpectedly, agents may need to act in a reactive manner, whereas more stable environments may allow agents time to deliberate on the best course of action. Architectures containing both deliberative and reactive components are hybrid architectures, of which two key examples, TouringMachines [4] and INTERRRAP [28], are discussed next.
2.4.1 TouringMachines
Ferguson proposed TouringMachines as an architecture for controlling and coordinating the actions of autonomous agents situated in dynamic multiagent worlds. He argued that agents operating in the real world would inevitably have to deal with several issues that had not—at that time—been considered in the vast array of architectures that exhibited quite well-defined preprogrammed behavior. Such architectures would need to address a number of possibly conflicting issues, as follows:
They need the ability to deal with unexpected events in the real (physical or electronic) world, and do so at different levels of granularity.
They need to deal with the dynamism in the environment created by the actions of other agents.
They must pay attention to environmental change.
They need to reason about temporal constraints in the knowledge that computation is necessarily resource-bounded.
They must reason about the impact the short-term actions may have on long-term goals.
In response, Ferguson proposed the TouringMachines architecture, illustrated in Figure 2.3 [27] The architecture is similar to the subsumption architecture in that it consists of a number of layers, the reactive layer, the planning layer, and the modeling layer, which continually compete to control the agent's behavior. The reactive layer responds quickly to events not explicitly programmed in the other layers, such as when a new agent or obstacle is perceived. Generating, executing, and modifying plans, such as constructing a route in order to move to a target destination, are the responsibilities of the planning layer. Finally, the modeling layer is used for building and maintaining models of entities in the environment (including the agent itself), which are used to understand the current behaviors of others and make predictions about their future behaviors.
Figure 2.3: The TouringMachines architecture. (After: [27])
Each layer models the agent's world at a different level of abstraction but, unlike the subsumption architecture, each is directly connected to both the action and perception of the agent, and any two layers can communicate with each other. Since these layers are each modeled at different abstraction levels, they each have an incomplete view of the world, encoding different strategies and tactics for responding to events. Conflicts over action-selection therefore inevitably arise, so the architecture includes a set of global context-dependent control rules to achieve coherence between these layers, which work by suppressing either the input to, or the output from, a layer.
Ferguson showed that this architecture was feasible and appropriate for agents operating in dynamic environments. Moreover, he demonstrated that it was possible to integrate expensive deliberative reasoning mechanisms with reactive behavior-based components in a resource-bounded agent. The architecture is important because it showed that it could successfully produce a wide variety of behaviors from reactive through to goal-directed, all required of a sophisticated agent embedded in a complex environment.
2.4.2 INTERRRAP
MüUller et al. [3] also argued that layered hybrid architectures are beneficial as they support the modeling of an agent's environment at different levels of abstraction, the different times taken to respond to an action (responsiveness), and the levels of knowledge and reasoning sophistication required by an agent. However, they also acknowledge that the design of individual layers is often quite personal and not guided by any general theory of agency.
In response, they proposed an architecture that combines the advantages of BDI-style architectures and those of layered ones. This architecture, called INTERRRAP, used the BDI model to guide the construction of each of the individual layers within the architecture.
The state of each layer is represented by beliefs, goals, and intentions, and each layer can receive what is known as perceived propositions. This means that each layer can perceive information from the environment, and from other layers, but this information is always in the form of simple propositions such as at (agent (A, B)). The architecture implements three basic functions at each layer, thus providing a uniform control structure for each layer. These are enumerated here:
Belief revision maps an agent's current perception and current beliefs to a set of new beliefs. For example, an agent may perceive that an object has moved, and belief revision updates the agent's current beliefs accordingly.
Situation recognition and goal activation take the current beliefs and goals and generate a new set of goals for the agent to try to achieve.
Planning and scheduling derive a new set of intentions (what the agent is committed to doing) from the current set of beliefs, goals, and intentions of the agent.
The motivation for this kind of architecture is based around the interfaces between each of the three layers, and the ways in which layers can communicate with other layers. The developers of INTERRRAP categorized Ferguson's TouringMachines architecture as horizontally layered—each layer can interact with every other layer, as well as with the perceptions and actions. In this kind of architecture, many communication paths have to be considered and any centralized control would therefore need to be very sophisticated. In response, INTERRRAP is a vertically layered architecture in which layers are configured similarly, but where communication is only possible between adjacent layers. Clearly, in this model, fewer communication channels have to be designed. Consider a system with n layers, for example. If each layer can only communicate with adjacent layers in both directions, at most 2(n−1) channels will be required. In a horizontal architecture, the first layer alone requires 2(n − 1) paths to communicate in both directions with every other layer, the next layer needs 2(n—2) paths to ensure communication with all succeeding layers, and so on. An n-layered horizontal architecture may therefore require anything up to 2n! communication paths. The disadvantage of vertically layered architectures is that for a layer to control behavior, the control must necessarily pass through all lower layers.
As indicated above, the INTERRRAP agent architecture [14] is an example of a vertically layered architecture and is shown in Figure 2.4, adapted from [3] It comprises four layers that can communicate in both directions with adjacent layers. INTERRRAP was developed to model resource-bounded autonomous agents that interact with others in dynamic environments, while implementing a pragmatic BDI architecture. The control of the agent is contained in three different hierarchical layers known as the behavior-based layer, the plan-based layer, and the cooperation-based layer. While the behavior-based layer is always carefully modeled for specific domains, the others contain more generic information pertaining to goal-directed and social behavior.
Figure 2.4: The INTERRRAP architecture. (After: [3].)
The agent's knowledge base is correspondingly split into three layers. At the lowest level, the agent's world model comprises beliefs about the environment. At the next level, the mental model contains knowledge about the agent itself, including its goals, plans, and intentions. The social model is the highest level containing information about others and the current state of joint-plans, joint-goals, and joint-intentions. These three knowledge bases are respectively accessed and updated by the behavior-based component, plan-based component, and cooperation component. The lowest level allows agents to react to unforeseen events and to quickly execute routine tasks without any explicit deliberative reasoning. The plan-based layer allows nonsocial goal-directed behavior. Plans are either hierarchical templates that call other plans or are directly executable behaviors. Finally, the social level enables the agent to interact with others by coordinating actions and forming joint-plans.
The essential operation of the agent is simple; in response to events in the environment, control spreads upwards until the appropriate level is reached and the functions described earlier are applied accordingly. The benefits of decentralizing knowledge and behavior into layers must be weighed against the cost of communication between, and coordination of, these layers; this is analogous to problems determining the number of agents required for building multiagent applications. Extending this analogy—that the design of layered architectures is analogous to designing multiagent systems by treating each layer as an autonomous agent—the contract net protocol is proposed as a useful mechanism for coordinating the concurrent execution of symbolic reasoning at different layers. We discuss the contract net in more detail later in this chapter.
2.4.3 Other Hybrid Architectures
In more recent work on building agent development tools and architectures, agents typically have both reactive and deliberative components.
For example, the Sensible Agent Testbed, a set of tools for the building, running, monitoring, and testing of complex multiagent systems [29], involves hybrid agents. The agent architecture contains a perspective modeler that maintains an explicit model of an agent's subjective view of its environment. The model includes both the behavioral (reactive) and intentional (proactive) models of itself and others. Similarly, the autonomy reasoner dynamically determines the appropriate decision-making framework for the agent. One such framework is categorized as command driven, where the agent does not function deliberatively but simply obeys orders directly from a master agent without deliberating.
In another recent example, the DECAF agent toolkit (Distributed, Environment-Centered Agent Framework), which allows a well-defined software engineering method to be used in building multiagent systems, also uses a hybrid agent architecture [30]. On one hand, the deliberative element is incorporated using a plan editor that builds a symbolic representation of a plan to achieve some objective. On the other hand, the reactive component is the executor that simply takes a set of enabled actions and produces a set of low-level commitments to very specific courses of action.
In general, agents can be neither totally deliberative nor totally reactive. If they are only reactive, they cannot reason about their actions and will not be able to achieve any sophisticated behavior; if they are just deliberative they may never be able to act in time.
It is now generally recognized, therefore, that if agent systems are to survive in real and complex environments they need to be reactive in order to respond to environmental changes with sufficient speed, and be deliberative in order to achieve complex goals without deleteriously affecting longer-term options [27]. If environments change rapidly or unexpectedly, agents may need to act in a reactive manner, whereas more stable environments may allow agents time to deliberate on the best course of action. Architectures containing both deliberative and reactive components are hybrid architectures, of which two key examples, TouringMachines [4] and INTERRRAP [28], are discussed next.
2.4.1 TouringMachines
Ferguson proposed TouringMachines as an architecture for controlling and coordinating the actions of autonomous agents situated in dynamic multiagent worlds. He argued that agents operating in the real world would inevitably have to deal with several issues that had not—at that time—been considered in the vast array of architectures that exhibited quite well-defined preprogrammed behavior. Such architectures would need to address a number of possibly conflicting issues, as follows:
They need the ability to deal with unexpected events in the real (physical or electronic) world, and do so at different levels of granularity.
They need to deal with the dynamism in the environment created by the actions of other agents.
They must pay attention to environmental change.
They need to reason about temporal constraints in the knowledge that computation is necessarily resource-bounded.
They must reason about the impact the short-term actions may have on long-term goals.
In response, Ferguson proposed the TouringMachines architecture, illustrated in Figure 2.3 [27] The architecture is similar to the subsumption architecture in that it consists of a number of layers, the reactive layer, the planning layer, and the modeling layer, which continually compete to control the agent's behavior. The reactive layer responds quickly to events not explicitly programmed in the other layers, such as when a new agent or obstacle is perceived. Generating, executing, and modifying plans, such as constructing a route in order to move to a target destination, are the responsibilities of the planning layer. Finally, the modeling layer is used for building and maintaining models of entities in the environment (including the agent itself), which are used to understand the current behaviors of others and make predictions about their future behaviors.
Figure 2.3: The TouringMachines architecture. (After: [27])
Each layer models the agent's world at a different level of abstraction but, unlike the subsumption architecture, each is directly connected to both the action and perception of the agent, and any two layers can communicate with each other. Since these layers are each modeled at different abstraction levels, they each have an incomplete view of the world, encoding different strategies and tactics for responding to events. Conflicts over action-selection therefore inevitably arise, so the architecture includes a set of global context-dependent control rules to achieve coherence between these layers, which work by suppressing either the input to, or the output from, a layer.
Ferguson showed that this architecture was feasible and appropriate for agents operating in dynamic environments. Moreover, he demonstrated that it was possible to integrate expensive deliberative reasoning mechanisms with reactive behavior-based components in a resource-bounded agent. The architecture is important because it showed that it could successfully produce a wide variety of behaviors from reactive through to goal-directed, all required of a sophisticated agent embedded in a complex environment.
2.4.2 INTERRRAP
MüUller et al. [3] also argued that layered hybrid architectures are beneficial as they support the modeling of an agent's environment at different levels of abstraction, the different times taken to respond to an action (responsiveness), and the levels of knowledge and reasoning sophistication required by an agent. However, they also acknowledge that the design of individual layers is often quite personal and not guided by any general theory of agency.
In response, they proposed an architecture that combines the advantages of BDI-style architectures and those of layered ones. This architecture, called INTERRRAP, used the BDI model to guide the construction of each of the individual layers within the architecture.
The state of each layer is represented by beliefs, goals, and intentions, and each layer can receive what is known as perceived propositions. This means that each layer can perceive information from the environment, and from other layers, but this information is always in the form of simple propositions such as at (agent (A, B)). The architecture implements three basic functions at each layer, thus providing a uniform control structure for each layer. These are enumerated here:
Belief revision maps an agent's current perception and current beliefs to a set of new beliefs. For example, an agent may perceive that an object has moved, and belief revision updates the agent's current beliefs accordingly.
Situation recognition and goal activation take the current beliefs and goals and generate a new set of goals for the agent to try to achieve.
Planning and scheduling derive a new set of intentions (what the agent is committed to doing) from the current set of beliefs, goals, and intentions of the agent.
The motivation for this kind of architecture is based around the interfaces between each of the three layers, and the ways in which layers can communicate with other layers. The developers of INTERRRAP categorized Ferguson's TouringMachines architecture as horizontally layered—each layer can interact with every other layer, as well as with the perceptions and actions. In this kind of architecture, many communication paths have to be considered and any centralized control would therefore need to be very sophisticated. In response, INTERRRAP is a vertically layered architecture in which layers are configured similarly, but where communication is only possible between adjacent layers. Clearly, in this model, fewer communication channels have to be designed. Consider a system with n layers, for example. If each layer can only communicate with adjacent layers in both directions, at most 2(n−1) channels will be required. In a horizontal architecture, the first layer alone requires 2(n − 1) paths to communicate in both directions with every other layer, the next layer needs 2(n—2) paths to ensure communication with all succeeding layers, and so on. An n-layered horizontal architecture may therefore require anything up to 2n! communication paths. The disadvantage of vertically layered architectures is that for a layer to control behavior, the control must necessarily pass through all lower layers.
As indicated above, the INTERRRAP agent architecture [14] is an example of a vertically layered architecture and is shown in Figure 2.4, adapted from [3] It comprises four layers that can communicate in both directions with adjacent layers. INTERRRAP was developed to model resource-bounded autonomous agents that interact with others in dynamic environments, while implementing a pragmatic BDI architecture. The control of the agent is contained in three different hierarchical layers known as the behavior-based layer, the plan-based layer, and the cooperation-based layer. While the behavior-based layer is always carefully modeled for specific domains, the others contain more generic information pertaining to goal-directed and social behavior.
Figure 2.4: The INTERRRAP architecture. (After: [3].)
The agent's knowledge base is correspondingly split into three layers. At the lowest level, the agent's world model comprises beliefs about the environment. At the next level, the mental model contains knowledge about the agent itself, including its goals, plans, and intentions. The social model is the highest level containing information about others and the current state of joint-plans, joint-goals, and joint-intentions. These three knowledge bases are respectively accessed and updated by the behavior-based component, plan-based component, and cooperation component. The lowest level allows agents to react to unforeseen events and to quickly execute routine tasks without any explicit deliberative reasoning. The plan-based layer allows nonsocial goal-directed behavior. Plans are either hierarchical templates that call other plans or are directly executable behaviors. Finally, the social level enables the agent to interact with others by coordinating actions and forming joint-plans.
The essential operation of the agent is simple; in response to events in the environment, control spreads upwards until the appropriate level is reached and the functions described earlier are applied accordingly. The benefits of decentralizing knowledge and behavior into layers must be weighed against the cost of communication between, and coordination of, these layers; this is analogous to problems determining the number of agents required for building multiagent applications. Extending this analogy—that the design of layered architectures is analogous to designing multiagent systems by treating each layer as an autonomous agent—the contract net protocol is proposed as a useful mechanism for coordinating the concurrent execution of symbolic reasoning at different layers. We discuss the contract net in more detail later in this chapter.
2.4.3 Other Hybrid Architectures
In more recent work on building agent development tools and architectures, agents typically have both reactive and deliberative components.
For example, the Sensible Agent Testbed, a set of tools for the building, running, monitoring, and testing of complex multiagent systems [29], involves hybrid agents. The agent architecture contains a perspective modeler that maintains an explicit model of an agent's subjective view of its environment. The model includes both the behavioral (reactive) and intentional (proactive) models of itself and others. Similarly, the autonomy reasoner dynamically determines the appropriate decision-making framework for the agent. One such framework is categorized as command driven, where the agent does not function deliberatively but simply obeys orders directly from a master agent without deliberating.
In another recent example, the DECAF agent toolkit (Distributed, Environment-Centered Agent Framework), which allows a well-defined software engineering method to be used in building multiagent systems, also uses a hybrid agent architecture [30]. On one hand, the deliberative element is incorporated using a plan editor that builds a symbolic representation of a plan to achieve some objective. On the other hand, the reactive component is the executor that simply takes a set of enabled actions and produces a set of low-level commitments to very specific courses of action.
Agent Architectures : DELIBERATIVE AGENT ARCHITECTURES
Agent systems able to maintain and manipulate representations of the world, without stimulus-response rules of the kind described above, are often called deliberative agents [1] In order to model rational or intentional agency in these kinds of agents, mentalistic notions, or mental attitudes are used to describe and characterize behavior. These attitudes include beliefs, goals, desires, knowledge, plans, motivations, and intentions, and are commonly grouped into three categories: informative, motivational, and deliberative [7]. The first category refers to that which a system considers to be true about the world, and includes knowledge, beliefs, and assumptions; the second refers to the wants of a system, including goals, desires, and motivations; and the third concerns how an agent's behavior is directed and includes plans and intentions. The distinction between the second and third categories is subtle, since it is possible that a system may desire a certain state without planning for it, or without intending it to happen.
There are several compelling reasons why agents defined using mental attitudes might be useful. First, if an agent can be described in terms of what it knows, what it wants, and what it intends, then, since it is modeled on familiar concepts, it becomes possible for users to understand and predict its behavior. Second, understanding the relationship between these different attitudes and how they affect behavior can provide the control mechanism for intelligent action in general. Third, computational agents designed in this way may be able to interpret the behavior of others independently from any implementation.
Moreover, many of these deliberative architectures are based on the belief-desire-intention (BDI) model of rational agency.
BDI Architecture
Although not a system, the BDI model provides a foundation for many systems and we therefore consider it separately as an abstract architecture in its own right. Arguably, the most successful agent architectures are founded on the BDI model, in which agents continually monitor their environments and act to change them, based on the three mental attitudes of belief, desire, and intention, representing informational, motivational, and decision-making capabilities. Architectures based on the BDI model explicitly represent beliefs, desires, and intentions as data structures, which determine the operation of the agent.
The intuition with BDI systems is that an agent will not, in general, be able to achieve all its desires, even if these desires are consistent. Agents must therefore fix upon some subset of available desires and commit resources to achieving them. These chosen desires are intentions, and an agent will typically continue to try to achieve an intention until either it believes the intention is satisfied, or it believes the intention is no longer achievable [8].
Many formal models have been devised in order to investigate and analyze the relationships between belief, desire, and intention. Much of this work investigates how modal and temporal logics can be used to specify theories of agent behavior. For example, Cohen and Levesque [8], Kinny et al. [9], Jennings [10], Haddadi [11], and Wooldridge [12] have all proposed such models. These models are often underpinned using the possible-worlds semantics first proposed by Hintikka [13]. Using this as a basis, it is possible to develop BDI modal logics that determine how different relationships between the mental attitudes produce different agent behavior.
As well as the formal models of BDI agents that specify desired behaviors of BDI agents, generic BDI architectures that encapsulate the BDI model have been constructed to support the design of practical agents [14], and programming languages have been proposed that can be used to implement BDI agents that satisfy some of the formal BDI properties [15]. In addition, BDI agents have been used extensively in real-world applications [16]. Many of the architectures and systems that are discussed in this chapter have been influenced by models of BDI, including the Intelligent Resource-Bounded Machine Architecture (IRMA) [17] and, arguably the best known and most established architecture, the Procedural Reasoning System (PRS). Both of these agent systems can be considered to be deliberative, and are considered next.
Procedural Reasoning System
Since the mid-1980s, many control architectures for practical reasoning agents have been proposed. Most of these have been deployed only in limited artificial environments; very few have been applied to realistic problems, and even fewer have led to the development of useful field-tested applications. The most notable exception is the Procedural Reasoning System (PRS). Originally described in 1987 [18], PRS has progressed from an experimental LISP version to a fully fledged C++ implementation known as the distributed MultiAgent Reasoning System (dMARS), which has been applied in perhaps the most significant multiagent applications to date [16]
For example, Oasis [19] is a system for air traffic management that can handle the flow of over 100 aircraft arriving at an airport. It addresses issues of scheduling aircraft, comparing actual progress with established sequences of aircraft, estimating delays, and notifying controllers of ways to correct deviations. The prototype implementation comprised several different kinds of agents, including aircraft agents and coordinator agents, each of which was based around PRS. Oasis successfully completed operational tests at Sydney Airport in 1995. Similarly, dMARS has been used as the basis of an agent-based simulation system, Swarmm, developed for Australia's Defence Science and Technology Organisation to simulate air mission dynamics and pilot reasoning. More recent work has sought to apply dMARS to represent different roles in an organization in more general business software for running call centers or Internet services. The Agentis system allowed the generation of fully automated, server-side customer-service applications, and the first major installation aimed to use 4,000 dMARS agents.
The PRS architecture has its conceptual roots in the BDI model of practical reasoning developed by Bratman and colleagues [17] As Figure 2.2 shows, a BDI architecture typically contains four key data structures: beliefs, goals, intentions, and a plan library. An agent's beliefs correspond to information the agent has about the world, which may be incomplete or incorrect. An agent's desires (or goals, in the system) intuitively correspond to the tasks allocated to it. Beliefs, desires, and intentions of PRS are represented explicitly in the Database, Goalbase, and Intention Structure, respectively. PRS agents continually respond to perceptions, or events, which represent new beliefs and goals, by selecting plans to become intentions.
In PRS agents, the BDI model is operationalized by plans. Each agent has a plan library, which is a set of plans, or recipes, specifying courses of action that may be undertaken by an agent in order to achieve its intentions. An agent's plan library represents its procedural knowledge, or know-how: knowledge about how to bring about states of affairs. Plans are designed by a programmer before run time to capture the procedural knowledge of the agent as recipes detailing courses of action. They are the main feature of PRS systems and comprise several components that we describe here.
The trigger or invocation specifies what an agent must perceive in order for a plan to become a contender for execution selection. For example, the plan make tea may be triggered by the event thirsty. In addition, the plan's context must be believed by the agent before the plan can be adopted for execution. For example, the plan make tea might have the context have tea bags. The plan body captures procedural knowledge as an OR-tree with arcs labeled with formulas that may be primitive external actions such as C++ function calls, internal actions such as adding a fact to its database, query goals that are matched to the agent's beliefs, or, finally, achieve goals that generate new subgoals. This make tea plan might have the body get boiling water; add tea bag to cup; add water to cup. Here, get boiling water is a subgoal (something that must be achieved when plan execution reaches this point in the plan), whereas add tea bag to cup and add water to cup are primitive actions (i.e., actions that can be performed directly by the agent).
At the start of execution, agents are initialized with a set of plans, goals, beliefs, an empty event buffer, and no intentions. The operation of the agent can then be enumerated as follows:
Perceive the world, and update the set of events.
For each event, generate the set of plans whose trigger condition matches the event. These are known as the relevant plans of an event.
For each event, select the subset of relevant plans whose context condition is satisfied by the agent's current beliefs. These plans are known as active plans.
From the set of active plans, select one for execution so that it is now an intention.
Include this new intention in the current intention structure either by creating a new intention stack or by placing it on the top of an existing stack.
Select an intention stack, take the topmost intention, and execute the next formula in it.
In this way, when a plan starts executing, its subgoals will be posted on the event queue, which in turn will cause plans that achieve this subgoal to become active, and so on. Once the intention stack executes successfully, the event is removed from the event queue. This is the basic execution model of dMARS agents. Note that agents do no first-principles planning at all, as all plans must be generated by the agent programmer at design time. The planning performed by agents consists entirely of context-sensitive subgoal expansion, which is deferred until a point in time at which the subgoal is selected for execution.
As mentioned above, a whole range of practical development efforts relating to BDI systems have been undertaken, and can be divided into those that are almost straightforward reimplementations and refinements of PRS and dMARS on the one hand, and those that are more loosely based on broader BDI principles. The former category includes systems such as UM-PRS developed at the University of Michigan, a freely available reimplementation of PRS [20], PRS-Lite developed at SRI by Myers [21], Huber's JAM system [22], and the commercial JACK system [23], which are respectively increasingly sophisticated. The latter category includes Bratman's IRMA architecture [17] Burmeister and Sundermeyer's COSY [24], and the GRATE* system developed by Jennings [25]. Nevertheless, PRS and dMARS remain as the exemplar BDI systems.
2.3.3 AgentSpeak(L)
Rao's AgentSpeak(L) [15] is an attempt to provide an operational and proof-theoretic semantics fora language that can be viewed as an abstraction of an implemented BDI system. Essentially, it captures the essence of a PRS system; the only PRS constructs not included in AgentSpeak(L) are simply those that have been designed to make programming tasks more efficient.
As we have seen above, agents have beliefs (about themselves, others, and the environment) and intentions, which are sequences of plans (called intended means). Each agent has a library of plans, and each plan comprises a trigger, context, and body, which is a sequence of actions and goals (collectively called formulas).
The basic operation of an AgentSpeak(L) agent is similar to PRS and has two aspects. The first concerns agents responding to internal events (new subgoals) and external events (new beliefs) by selecting appropriate plans. If the event queue is nonempty, an event is selected and those plans whose trigger matches the event are identified as relevant plans. Those relevant plans whose context is satisfied by the current beliefs become the active plans. From this set, one plan, called the intended means, is selected nondeterministically. Now, if the event that generated the intended means is external, the intended means creates a new intention. If the event is internal, then the intended means is pushed onto the intention whose top plan's current formula is the subgoal that generated the event.
The second aspect of the agent's operation is the execution of intentions. First, an intention is selected, and the next formula in the top plan of that intention is evaluated. If the formula is an action, it is placed in a buffer. If the formula is a query goal, and if it is satisfiable with respect to the beliefs using a substitution, the substitution is applied to the rest of the executing plan. Alternatively, if the formula is an achieve goal, then a new goal event is added to the set of events to be processed.
The AgentSpeak(L) language is a significant attempt to unite the theory and practice of BDI agents, but again, the link between mental attitudes as data structures in implemented systems [as modeled by AgentSpeak(L)] and as modal operators in the theoretical model is weak. Rao simply suggests that we, as designers, should ascribe these theoretical notions to implemented agents, rather than suggesting that there is an approach to defining a formal relationship between them.
In the next section, we briefly discuss IRMA, which is important because it was the first attempt, by Bratman himself among others, to build an architecture that captured the ideas to explain the BDI theory of resource-bounded reasoning. It also offers an alternative view of instantiating the BDI model.
2.3.4 IRMA
In considering the problem of enabling agents to perform means-ends reasoning, to weigh competing alternative plans of action, and to cope with interaction between these two forms of reasoning in a resource-bounded way, Bratman proposed a high-level architecture, subsequently implemented as IRMA [17] This architecture, based on the BDI model, recognizes that agents will always be computationally limited or resource-bounded, and that suboptimal decisions may have to be made.
As with PRS, IRMA explicitly represents the beliefs, desires, and intentions of an agent as data structures in the system. In IRMA, once a plan has been selected for execution it becomes an active plan, and therefore an intention. IRMA's reasoning cycle is based around five key processes, comprising the opportunity analyzer, the means-end reasoner, the compatibility filter, the filter override mechanism, and the deliberation process, described below.
Initially, IRMA perceives its environment and updates its beliefs. Then, using the opportunity analyzer it must check whether its current goals have been inadvertently achieved, whether existing intentions can no longer be realized, or whether new alternative plans can be proposed. Goals are achieved by presenting them to the means-end reasoner, which attempts to generate new subplans. Plans from both the opportunity analyzer and the means-end reasoner are passed to the filtering process made up of the compatibility filter and the filter override mechanism, which run in parallel.
The role of the compatibility filter is to ascertain whether new plans are consistent with the existing intentions of the agent. Typically, incompatible plans are discarded but, in some cases, if they satisfy certain properties, they can be passed to the deliberation process by the filter override mechanism instead. When the override mechanism intervenes in this way, existing incompatible intentions are suspended. Next, the deliberation process determines how the plans it is passed after filtering affect the current intention structure. This intention structure simply comprises plans that have been selected for execution, and may be updated to accommodate new plans, when appropriate.
IRMA has been demonstrated and tested in the Tileworld simulation environment [26], which showed that given appropriate overriding mechanisms, committing to plans by means of intentions is a useful strategy for effective agent behavior in a dynamic environment.
The real benefit of both IRMA and PRS is that they are built from a clear conceptual model of the relationship between beliefs, goals, intentions, and plans. One problem, however, is that neither architecture provides designers with guidance on how an agent makes decisions based on its mental state, nor do they provide general rules of how to construct agent plans before run time. In addition, although it is possible to simulate reactive behavior by building plans appropriately, this is not an efficient or effective way of doing so, since reactive responses can only take place at the end of each (quite long-winded) operation cycle of these agents.
There are several compelling reasons why agents defined using mental attitudes might be useful. First, if an agent can be described in terms of what it knows, what it wants, and what it intends, then, since it is modeled on familiar concepts, it becomes possible for users to understand and predict its behavior. Second, understanding the relationship between these different attitudes and how they affect behavior can provide the control mechanism for intelligent action in general. Third, computational agents designed in this way may be able to interpret the behavior of others independently from any implementation.
Moreover, many of these deliberative architectures are based on the belief-desire-intention (BDI) model of rational agency.
BDI Architecture
Although not a system, the BDI model provides a foundation for many systems and we therefore consider it separately as an abstract architecture in its own right. Arguably, the most successful agent architectures are founded on the BDI model, in which agents continually monitor their environments and act to change them, based on the three mental attitudes of belief, desire, and intention, representing informational, motivational, and decision-making capabilities. Architectures based on the BDI model explicitly represent beliefs, desires, and intentions as data structures, which determine the operation of the agent.
The intuition with BDI systems is that an agent will not, in general, be able to achieve all its desires, even if these desires are consistent. Agents must therefore fix upon some subset of available desires and commit resources to achieving them. These chosen desires are intentions, and an agent will typically continue to try to achieve an intention until either it believes the intention is satisfied, or it believes the intention is no longer achievable [8].
Many formal models have been devised in order to investigate and analyze the relationships between belief, desire, and intention. Much of this work investigates how modal and temporal logics can be used to specify theories of agent behavior. For example, Cohen and Levesque [8], Kinny et al. [9], Jennings [10], Haddadi [11], and Wooldridge [12] have all proposed such models. These models are often underpinned using the possible-worlds semantics first proposed by Hintikka [13]. Using this as a basis, it is possible to develop BDI modal logics that determine how different relationships between the mental attitudes produce different agent behavior.
As well as the formal models of BDI agents that specify desired behaviors of BDI agents, generic BDI architectures that encapsulate the BDI model have been constructed to support the design of practical agents [14], and programming languages have been proposed that can be used to implement BDI agents that satisfy some of the formal BDI properties [15]. In addition, BDI agents have been used extensively in real-world applications [16]. Many of the architectures and systems that are discussed in this chapter have been influenced by models of BDI, including the Intelligent Resource-Bounded Machine Architecture (IRMA) [17] and, arguably the best known and most established architecture, the Procedural Reasoning System (PRS). Both of these agent systems can be considered to be deliberative, and are considered next.
Procedural Reasoning System
Since the mid-1980s, many control architectures for practical reasoning agents have been proposed. Most of these have been deployed only in limited artificial environments; very few have been applied to realistic problems, and even fewer have led to the development of useful field-tested applications. The most notable exception is the Procedural Reasoning System (PRS). Originally described in 1987 [18], PRS has progressed from an experimental LISP version to a fully fledged C++ implementation known as the distributed MultiAgent Reasoning System (dMARS), which has been applied in perhaps the most significant multiagent applications to date [16]
For example, Oasis [19] is a system for air traffic management that can handle the flow of over 100 aircraft arriving at an airport. It addresses issues of scheduling aircraft, comparing actual progress with established sequences of aircraft, estimating delays, and notifying controllers of ways to correct deviations. The prototype implementation comprised several different kinds of agents, including aircraft agents and coordinator agents, each of which was based around PRS. Oasis successfully completed operational tests at Sydney Airport in 1995. Similarly, dMARS has been used as the basis of an agent-based simulation system, Swarmm, developed for Australia's Defence Science and Technology Organisation to simulate air mission dynamics and pilot reasoning. More recent work has sought to apply dMARS to represent different roles in an organization in more general business software for running call centers or Internet services. The Agentis system allowed the generation of fully automated, server-side customer-service applications, and the first major installation aimed to use 4,000 dMARS agents.
The PRS architecture has its conceptual roots in the BDI model of practical reasoning developed by Bratman and colleagues [17] As Figure 2.2 shows, a BDI architecture typically contains four key data structures: beliefs, goals, intentions, and a plan library. An agent's beliefs correspond to information the agent has about the world, which may be incomplete or incorrect. An agent's desires (or goals, in the system) intuitively correspond to the tasks allocated to it. Beliefs, desires, and intentions of PRS are represented explicitly in the Database, Goalbase, and Intention Structure, respectively. PRS agents continually respond to perceptions, or events, which represent new beliefs and goals, by selecting plans to become intentions.
In PRS agents, the BDI model is operationalized by plans. Each agent has a plan library, which is a set of plans, or recipes, specifying courses of action that may be undertaken by an agent in order to achieve its intentions. An agent's plan library represents its procedural knowledge, or know-how: knowledge about how to bring about states of affairs. Plans are designed by a programmer before run time to capture the procedural knowledge of the agent as recipes detailing courses of action. They are the main feature of PRS systems and comprise several components that we describe here.
The trigger or invocation specifies what an agent must perceive in order for a plan to become a contender for execution selection. For example, the plan make tea may be triggered by the event thirsty. In addition, the plan's context must be believed by the agent before the plan can be adopted for execution. For example, the plan make tea might have the context have tea bags. The plan body captures procedural knowledge as an OR-tree with arcs labeled with formulas that may be primitive external actions such as C++ function calls, internal actions such as adding a fact to its database, query goals that are matched to the agent's beliefs, or, finally, achieve goals that generate new subgoals. This make tea plan might have the body get boiling water; add tea bag to cup; add water to cup. Here, get boiling water is a subgoal (something that must be achieved when plan execution reaches this point in the plan), whereas add tea bag to cup and add water to cup are primitive actions (i.e., actions that can be performed directly by the agent).
At the start of execution, agents are initialized with a set of plans, goals, beliefs, an empty event buffer, and no intentions. The operation of the agent can then be enumerated as follows:
Perceive the world, and update the set of events.
For each event, generate the set of plans whose trigger condition matches the event. These are known as the relevant plans of an event.
For each event, select the subset of relevant plans whose context condition is satisfied by the agent's current beliefs. These plans are known as active plans.
From the set of active plans, select one for execution so that it is now an intention.
Include this new intention in the current intention structure either by creating a new intention stack or by placing it on the top of an existing stack.
Select an intention stack, take the topmost intention, and execute the next formula in it.
In this way, when a plan starts executing, its subgoals will be posted on the event queue, which in turn will cause plans that achieve this subgoal to become active, and so on. Once the intention stack executes successfully, the event is removed from the event queue. This is the basic execution model of dMARS agents. Note that agents do no first-principles planning at all, as all plans must be generated by the agent programmer at design time. The planning performed by agents consists entirely of context-sensitive subgoal expansion, which is deferred until a point in time at which the subgoal is selected for execution.
As mentioned above, a whole range of practical development efforts relating to BDI systems have been undertaken, and can be divided into those that are almost straightforward reimplementations and refinements of PRS and dMARS on the one hand, and those that are more loosely based on broader BDI principles. The former category includes systems such as UM-PRS developed at the University of Michigan, a freely available reimplementation of PRS [20], PRS-Lite developed at SRI by Myers [21], Huber's JAM system [22], and the commercial JACK system [23], which are respectively increasingly sophisticated. The latter category includes Bratman's IRMA architecture [17] Burmeister and Sundermeyer's COSY [24], and the GRATE* system developed by Jennings [25]. Nevertheless, PRS and dMARS remain as the exemplar BDI systems.
2.3.3 AgentSpeak(L)
Rao's AgentSpeak(L) [15] is an attempt to provide an operational and proof-theoretic semantics fora language that can be viewed as an abstraction of an implemented BDI system. Essentially, it captures the essence of a PRS system; the only PRS constructs not included in AgentSpeak(L) are simply those that have been designed to make programming tasks more efficient.
As we have seen above, agents have beliefs (about themselves, others, and the environment) and intentions, which are sequences of plans (called intended means). Each agent has a library of plans, and each plan comprises a trigger, context, and body, which is a sequence of actions and goals (collectively called formulas).
The basic operation of an AgentSpeak(L) agent is similar to PRS and has two aspects. The first concerns agents responding to internal events (new subgoals) and external events (new beliefs) by selecting appropriate plans. If the event queue is nonempty, an event is selected and those plans whose trigger matches the event are identified as relevant plans. Those relevant plans whose context is satisfied by the current beliefs become the active plans. From this set, one plan, called the intended means, is selected nondeterministically. Now, if the event that generated the intended means is external, the intended means creates a new intention. If the event is internal, then the intended means is pushed onto the intention whose top plan's current formula is the subgoal that generated the event.
The second aspect of the agent's operation is the execution of intentions. First, an intention is selected, and the next formula in the top plan of that intention is evaluated. If the formula is an action, it is placed in a buffer. If the formula is a query goal, and if it is satisfiable with respect to the beliefs using a substitution, the substitution is applied to the rest of the executing plan. Alternatively, if the formula is an achieve goal, then a new goal event is added to the set of events to be processed.
The AgentSpeak(L) language is a significant attempt to unite the theory and practice of BDI agents, but again, the link between mental attitudes as data structures in implemented systems [as modeled by AgentSpeak(L)] and as modal operators in the theoretical model is weak. Rao simply suggests that we, as designers, should ascribe these theoretical notions to implemented agents, rather than suggesting that there is an approach to defining a formal relationship between them.
In the next section, we briefly discuss IRMA, which is important because it was the first attempt, by Bratman himself among others, to build an architecture that captured the ideas to explain the BDI theory of resource-bounded reasoning. It also offers an alternative view of instantiating the BDI model.
2.3.4 IRMA
In considering the problem of enabling agents to perform means-ends reasoning, to weigh competing alternative plans of action, and to cope with interaction between these two forms of reasoning in a resource-bounded way, Bratman proposed a high-level architecture, subsequently implemented as IRMA [17] This architecture, based on the BDI model, recognizes that agents will always be computationally limited or resource-bounded, and that suboptimal decisions may have to be made.
As with PRS, IRMA explicitly represents the beliefs, desires, and intentions of an agent as data structures in the system. In IRMA, once a plan has been selected for execution it becomes an active plan, and therefore an intention. IRMA's reasoning cycle is based around five key processes, comprising the opportunity analyzer, the means-end reasoner, the compatibility filter, the filter override mechanism, and the deliberation process, described below.
Initially, IRMA perceives its environment and updates its beliefs. Then, using the opportunity analyzer it must check whether its current goals have been inadvertently achieved, whether existing intentions can no longer be realized, or whether new alternative plans can be proposed. Goals are achieved by presenting them to the means-end reasoner, which attempts to generate new subplans. Plans from both the opportunity analyzer and the means-end reasoner are passed to the filtering process made up of the compatibility filter and the filter override mechanism, which run in parallel.
The role of the compatibility filter is to ascertain whether new plans are consistent with the existing intentions of the agent. Typically, incompatible plans are discarded but, in some cases, if they satisfy certain properties, they can be passed to the deliberation process by the filter override mechanism instead. When the override mechanism intervenes in this way, existing incompatible intentions are suspended. Next, the deliberation process determines how the plans it is passed after filtering affect the current intention structure. This intention structure simply comprises plans that have been selected for execution, and may be updated to accommodate new plans, when appropriate.
IRMA has been demonstrated and tested in the Tileworld simulation environment [26], which showed that given appropriate overriding mechanisms, committing to plans by means of intentions is a useful strategy for effective agent behavior in a dynamic environment.
The real benefit of both IRMA and PRS is that they are built from a clear conceptual model of the relationship between beliefs, goals, intentions, and plans. One problem, however, is that neither architecture provides designers with guidance on how an agent makes decisions based on its mental state, nor do they provide general rules of how to construct agent plans before run time. In addition, although it is possible to simulate reactive behavior by building plans appropriately, this is not an efficient or effective way of doing so, since reactive responses can only take place at the end of each (quite long-winded) operation cycle of these agents.
Agent-Based Software Development : REACTIVE AGENT ARCHITECTURES
The traditional AI view is that in order for software agents to exhibit intelligent behavior, they need an internal (symbolic) representation of their environment. The agents then can manipulate and reason about this internal representation in order to determine what to do next. However, some have argued that effective behavior does not necessarily require symbolic representation and manipulation, a view strengthened by the problems that have emerged in mainstream artificial intelligence such as the complexity and, in some cases, intractability, of some symbolic manipulation problems such as planning. (Essentially, planning is the process of constructing a sequence of actions which, when performed in order, will achieve some of its goals.) This is because symbolic reasoning is very resource-and time-intensive in determining the best action to perform next, so that by the time the action is performed, the environment may have changed in such a way that the action is no longer useful. In this case, the agent could be said to have failed. The opposite view is that effective behavior is only achieved when systems are situated and embodied in the real world, and can respond to events in the environment in a timely fashion. In this view, agent behavior is directly coupled with the world, typically incorporating stimulus-response rules; the environment provides a stimulus that causes a rule to fire and the agent to respond in specified way.
Agents that do not maintain a symbolic representation of their environment are known as reactive agents, and their architectures as reactive architectures. Such reactive systems were originally proposed by Brooks, who developed the subsumption architecture for controlling the behavior of a robot. In a similar fashion, Maes, a former colleague of Brooks, developed the agent network architecture, built upon the principle that intelligent behavior is an emergent phenomenon arising from the interaction of "societies of nonintelligent systems." Both architectures are considered next.
Subsumption Architecture
Brooks proposed the subsumption architecture as a means of controlling the behavior of a mobile robot in real time, with three basic requirements [2], as follows:
Agents should be able to cope with multiple goals. For example, an agent might have the goal of moving to a certain location in its environment, directly ahead of it, as quickly as possible, while at the same time also possessing the goal to avoid obstacles. Clearly, when there is an obstacle in the path of an agent, these goals conflict, and any control mechanism for the robot needs to determine which of the goals takes priority.
Agents should have multiple sensors. In general, physical agents have several different sensors (including infra-red cameras and acoustic range-finders, for example) each with the possibility of giving erroneous or conflicting readings. Agents must be able to make decisions in these difficult circumstances.
Agents should be robust. Essentially, this refers to two aspects: first, agents must be able to function (albeit possibly less effectively) when some sensors fail; second, agents should be able to behave effectively when the environment is changing drastically around them.
The approach taken by Brooks is not a functional one in which component parts are isolated according to perception, action, reasoning, planning, and so on, with some overarching central control mechanism. Instead, it is achieved using an entirely different approach, the layered approach. Here, the architecture comprises several task-achieving behaviors, each of which is implemented separately and arranged as shown in Figure 2.1. The hierarchy of layers reflects how specific a behavior is; the more specific the task, the higher the layer. In the case of the mobile robot, there are eight layers of behavior, from 1 to 8, as follows.
Avoid contact with objects in the environment;
Wander aimlessly;
Explore the environment;
Build a map of the environment and plan routes within it;
Notice change in the environment;
Reason about and identify objects in the world, and perform certain tasks related to certain objects;
Build and execute plans that involve changing the world in some desirable way;
Reason about the behavior of other objects and how it might impact on plans, and consequently modify plans.
The different layers exist in parallel, with each unaware of the other layers that are above it, but able to examine data from lower layers. Each layer is connected to the sensors and actuators, but extracting only those aspects of the world (from the sensors) that are relevant to its function. In addition, layers can prevent lower layers from trying to control the behavior of the agent by suppressing their inputs and inhibiting their outputs.
The first step in the agent's construction is to build the 0th control layer and, once this has been tested, to build the 1st control layer on top of the 0th layer. The 1 st layer has access to the data at layer 0 and can also inject data to suppress the normal activity of the 0th layer. The 0th layer continues to execute, unaware that there is a higher layer intermittently influencing its behavior. This process can then be repeated for each successive layer, with each layer competing to control the behavior of the robot. In this way, the control system functions at a very early stage of system development, with higher layers being added as required without having to change the existing lower-layer architecture.
The robot architecture showed that robots could be designed by decomposing the control problem by behavior rather than using functional modules. The approach combines a modular structure with a clear control methodology, and supports a neat way of modeling the different levels of abstraction of the world and the reasoning required at each level. In this sense, it has had a significant impact on agent architectures in general, forming the basis for many hybrid architectures such as INTERRRAP [3] and TouringMachines [4]. These latter architectures, which we consider later in this chapter, also contain different levels of abstraction, each of which competes for control over an agent's actuators.
By itself, however, the subsumption architecture does not support any explicit reasoning, and it is not clear that it can be scaled up to domains requiring more sophisticated problem-solving behavior. In addition, the design of its layers was done on a rather ad hoc basis, and led by intuition rather than a clear methodology or set of guiding principles. Systems built on the subsumption architecture are quite complex and idiosyncratic, and it is almost impossible for any formal investigation of the properties of such systems. This makes it difficult to predict or explain such an agent's behavior in a given environmental scenario.
Agent Network Architecture
Building on some of the ideas of the subsumption architecture, and on those of Minsky [5], who has argued that intelligent systems consist of societies of mindless interacting systems, Maes developed the agent network architecture (ANA) [6]. The ANA consists of a collection of competence modules, each of which competes to control behavior. This competition depends on the activation of a module which, in turn, depends on both external and internal considerations. The former includes whether a module is executable, the agent's perception of the environment, and the current goals of the agent. However, the novelty of ANA lies in the internal mechanism by which modules affect the activation of other modules through links between them. Activated modules increase the activation of their successors, nonexecutable models activate their predecessors, and all modules decrease the activation of their conflictors.
For example, Maes considers modeling the behavior of an agent in drinking from a cup. She supposes that the agent has two permanent goals, to relieve its thirst and to be polite, the latter requiring the agent to move the cup to its mouth rather than its mouth to the cup. If the agent is thirsty in a situation in which the data observed includes the presence of a cup, then two modules, drink and recognize-cup, are activated. Once the external activation is calculated, the internal activation is considered. Then, since in this scenario the recognize-cup module is currently executable, activation spreads from this module to its successors, from all other modules to their predecessors, and from every module to all their conflictors. Finally, the activation of each module is inspected and, if one surpasses a threshold value, it becomes activated and controls the behavior of the agent.
Like Brooks, Maes argues that such an architecture is attractive because it is distributed, modular, and robust. However, while it represents a novel approach for constructing autonomous agents, and does provide some evidence that cognitive functions can be implemented in terms of simple behaviors, just like the subsumption architecture, it is difficult to see how it could be extended to achieve more rational behavior, or to provide a paradigm for designing agent applications in general.
Agents that do not maintain a symbolic representation of their environment are known as reactive agents, and their architectures as reactive architectures. Such reactive systems were originally proposed by Brooks, who developed the subsumption architecture for controlling the behavior of a robot. In a similar fashion, Maes, a former colleague of Brooks, developed the agent network architecture, built upon the principle that intelligent behavior is an emergent phenomenon arising from the interaction of "societies of nonintelligent systems." Both architectures are considered next.
Subsumption Architecture
Brooks proposed the subsumption architecture as a means of controlling the behavior of a mobile robot in real time, with three basic requirements [2], as follows:
Agents should be able to cope with multiple goals. For example, an agent might have the goal of moving to a certain location in its environment, directly ahead of it, as quickly as possible, while at the same time also possessing the goal to avoid obstacles. Clearly, when there is an obstacle in the path of an agent, these goals conflict, and any control mechanism for the robot needs to determine which of the goals takes priority.
Agents should have multiple sensors. In general, physical agents have several different sensors (including infra-red cameras and acoustic range-finders, for example) each with the possibility of giving erroneous or conflicting readings. Agents must be able to make decisions in these difficult circumstances.
Agents should be robust. Essentially, this refers to two aspects: first, agents must be able to function (albeit possibly less effectively) when some sensors fail; second, agents should be able to behave effectively when the environment is changing drastically around them.
The approach taken by Brooks is not a functional one in which component parts are isolated according to perception, action, reasoning, planning, and so on, with some overarching central control mechanism. Instead, it is achieved using an entirely different approach, the layered approach. Here, the architecture comprises several task-achieving behaviors, each of which is implemented separately and arranged as shown in Figure 2.1. The hierarchy of layers reflects how specific a behavior is; the more specific the task, the higher the layer. In the case of the mobile robot, there are eight layers of behavior, from 1 to 8, as follows.
Avoid contact with objects in the environment;
Wander aimlessly;
Explore the environment;
Build a map of the environment and plan routes within it;
Notice change in the environment;
Reason about and identify objects in the world, and perform certain tasks related to certain objects;
Build and execute plans that involve changing the world in some desirable way;
Reason about the behavior of other objects and how it might impact on plans, and consequently modify plans.
The different layers exist in parallel, with each unaware of the other layers that are above it, but able to examine data from lower layers. Each layer is connected to the sensors and actuators, but extracting only those aspects of the world (from the sensors) that are relevant to its function. In addition, layers can prevent lower layers from trying to control the behavior of the agent by suppressing their inputs and inhibiting their outputs.
The first step in the agent's construction is to build the 0th control layer and, once this has been tested, to build the 1st control layer on top of the 0th layer. The 1 st layer has access to the data at layer 0 and can also inject data to suppress the normal activity of the 0th layer. The 0th layer continues to execute, unaware that there is a higher layer intermittently influencing its behavior. This process can then be repeated for each successive layer, with each layer competing to control the behavior of the robot. In this way, the control system functions at a very early stage of system development, with higher layers being added as required without having to change the existing lower-layer architecture.
The robot architecture showed that robots could be designed by decomposing the control problem by behavior rather than using functional modules. The approach combines a modular structure with a clear control methodology, and supports a neat way of modeling the different levels of abstraction of the world and the reasoning required at each level. In this sense, it has had a significant impact on agent architectures in general, forming the basis for many hybrid architectures such as INTERRRAP [3] and TouringMachines [4]. These latter architectures, which we consider later in this chapter, also contain different levels of abstraction, each of which competes for control over an agent's actuators.
By itself, however, the subsumption architecture does not support any explicit reasoning, and it is not clear that it can be scaled up to domains requiring more sophisticated problem-solving behavior. In addition, the design of its layers was done on a rather ad hoc basis, and led by intuition rather than a clear methodology or set of guiding principles. Systems built on the subsumption architecture are quite complex and idiosyncratic, and it is almost impossible for any formal investigation of the properties of such systems. This makes it difficult to predict or explain such an agent's behavior in a given environmental scenario.
Agent Network Architecture
Building on some of the ideas of the subsumption architecture, and on those of Minsky [5], who has argued that intelligent systems consist of societies of mindless interacting systems, Maes developed the agent network architecture (ANA) [6]. The ANA consists of a collection of competence modules, each of which competes to control behavior. This competition depends on the activation of a module which, in turn, depends on both external and internal considerations. The former includes whether a module is executable, the agent's perception of the environment, and the current goals of the agent. However, the novelty of ANA lies in the internal mechanism by which modules affect the activation of other modules through links between them. Activated modules increase the activation of their successors, nonexecutable models activate their predecessors, and all modules decrease the activation of their conflictors.
For example, Maes considers modeling the behavior of an agent in drinking from a cup. She supposes that the agent has two permanent goals, to relieve its thirst and to be polite, the latter requiring the agent to move the cup to its mouth rather than its mouth to the cup. If the agent is thirsty in a situation in which the data observed includes the presence of a cup, then two modules, drink and recognize-cup, are activated. Once the external activation is calculated, the internal activation is considered. Then, since in this scenario the recognize-cup module is currently executable, activation spreads from this module to its successors, from all other modules to their predecessors, and from every module to all their conflictors. Finally, the activation of each module is inspected and, if one surpasses a threshold value, it becomes activated and controls the behavior of the agent.
Like Brooks, Maes argues that such an architecture is attractive because it is distributed, modular, and robust. However, while it represents a novel approach for constructing autonomous agents, and does provide some evidence that cognitive functions can be implemented in terms of simple behaviors, just like the subsumption architecture, it is difficult to see how it could be extended to achieve more rational behavior, or to provide a paradigm for designing agent applications in general.
Agent-Based Software Development: Agent Architectures
Although much of the value of the agent paradigm relates to the ways in which multiple agents come together to achieve complex tasks, the starting point of agent-based computing comprises the individual agents themselves.
There are two key reasons why agent architectures are important. The first is that we want to both predict and explain the behavior of an agent system based on its current state and that of the environment. The second is concerned with providing a methodology or blueprint of how to go about building real agent systems
We identify four agent architecture categories and review key examples we consider to be representative of each.
Typically, single agent architectures fall into one of three categories based on their architectures [1], as follows:
Reactive agent systems act by means of stimulus-response rules and do not symbolically represent their environment.
Deliberative agent systems symbolically model their environment and manipulate these symbols in order to act.
Hybrid agent systems can act both deliberatively and reactively.
Single-agent architectures result from what is referred to as the microlevel design perspective where the focus is on the individual agent. The macrolevel design perspective, on the other hand, describes the stance taken when dealing with the social or global dimensions of a distributed agent system. Such systems are designed at a holistic level as well as at the microlevel of individual agents. In particular, consideration of the macrolevel of agent design is used in the construction of distributed agent systems. In order to introduce the basic issues involved in constructing distributed intelligent systems, in this chapter we focus on perhaps the best-known technique for dynamically managing task allocation in a distributed system, the contract net protocol. We also outline the more recent Agentis framework for building interactive multiagent applications, which is based upon an agent interaction model whose central elements are services and tasks. Key to the operation of the Agentis system is the set of protocols that permits reliable concurrent-request and provision of services and tasks from and to agents, based on an underlying asynchronous point-to-point messaging infrastructure
There are two key reasons why agent architectures are important. The first is that we want to both predict and explain the behavior of an agent system based on its current state and that of the environment. The second is concerned with providing a methodology or blueprint of how to go about building real agent systems
We identify four agent architecture categories and review key examples we consider to be representative of each.
Typically, single agent architectures fall into one of three categories based on their architectures [1], as follows:
Reactive agent systems act by means of stimulus-response rules and do not symbolically represent their environment.
Deliberative agent systems symbolically model their environment and manipulate these symbols in order to act.
Hybrid agent systems can act both deliberatively and reactively.
Single-agent architectures result from what is referred to as the microlevel design perspective where the focus is on the individual agent. The macrolevel design perspective, on the other hand, describes the stance taken when dealing with the social or global dimensions of a distributed agent system. Such systems are designed at a holistic level as well as at the microlevel of individual agents. In particular, consideration of the macrolevel of agent design is used in the construction of distributed agent systems. In order to introduce the basic issues involved in constructing distributed intelligent systems, in this chapter we focus on perhaps the best-known technique for dynamically managing task allocation in a distributed system, the contract net protocol. We also outline the more recent Agentis framework for building interactive multiagent applications, which is based upon an agent interaction model whose central elements are services and tasks. Key to the operation of the Agentis system is the set of protocols that permits reliable concurrent-request and provision of services and tasks from and to agents, based on an underlying asynchronous point-to-point messaging infrastructure
Subscribe to:
Posts (Atom)
