Using Expressive and Flexible Action Representations to Reason about Capabilities for Intelligent Agent Cooperation

Home Page

Thesis (PDF)

Abstract (PDF)

Acknowledgements (PDF)

--The Thesis Story--

Chapter 1: Introduction: Capability Brokering

The aim of this thesis is to address the problem of capability brokering. For this purpose we will define a new capability description language and show that it has two desirable properties: it is expressive and highly flexible. The first step towards this goal must be a definition of the problem addressed in this thesis. The contribution of this chapter will be a characterisation of the problem of capability brokering and its context, as well as criteria for a successful solution.

Sections:

• The Problem of Capability Brokering: In this section we will define the problem of capability brokering for intelligent software agents, especially those that may be based on AI planning technology. This is the main problem addressed in this thesis.
• Capability Brokering in Context: In this section we will characterise several types of context for capability brokering; we will look at the various combinations of these types and evaluate each in turn to come up with the context for capability brokering that will be used in this thesis. This discussion will clarify what the problem of capability brokering is.
• Criteria for Success: In this section we will discuss what it means to successfully address the problem of capability brokering. The criteria for success described here will be used for a critical evaluation of the work presented in this thesis in chapters 6 and 9.

Chapter 2: Capability Brokering: A Literature Survey

At this point the general problem of capability brokering that is to be addressed in this thesis has been described and discussed. Our aim is to address this problem with a new capability description language that will be expressive and highly flexible and can be used to reason about capabilities. The next step towards this goal will be to investigate how previous approaches to representing generic capabilities attempted to do so. The contribution of this chapter will be a broad review of approaches to representing and reasoning about knowledge similar to the capability knowledge we need to represent.

Sections:

• Software Agents: In this section we will look at work in the wider area of intelligent software agents and, more specifically, at approaches to capability brokering found there.
• Modelling Capabilities with Logics: In this section we will look at how some logics have been or could be used to represent the capabilities of intelligent agents.
• Actions in AI Planning: In this section we will review approaches to action representations in AI planning, the area we see most closely related to capability modelling.
• Models of Problem Solving: In this section we will review approaches to modelling problem-solving methods.

Chapter 3: Scenarios, Agents, and Messages

At this point the general problem of capability brokering has been described and previous approaches to representing generic capabilities have been discussed. Our aim is to define a new capability description language that will be expressive and highly flexible and can be used to reason about capabilities. The next step towards this goal will be to define several scenarios that illustrate the expected behaviour of the different agents involved. The most interesting of these scenarios will be presented in section 3.3. The contribution of this chapter will be a clear definition of the expected problem-solving behaviour and a characterisation of the knowledge that needs to be represented in the message exchanges described.

Sections:

• The Initial Scenario: In this section we will present an example domain and a simple, initial scenario involving several agents that play different roles. This domain and scenario will reoccur throughout the thesis.
• Inter-Agent Messages: In this section we will show what the messages look like that the different agents will need to exchange. These messages are expressed in a high level communication language. We have chosen KQML for this purpose. This section will also show what knowledge the messages will need to contain, i.e. what needs to be represented in capability descriptions.
• More Complex Scenarios: In this section we will introduce some more interesting agents and scenarios that will be used in the thesis to highlight the usefulness of the two properties of the capability description language: expressiveness and flexibility. This section constitutes a major part for the motivation for the work described in this thesis.

Chapter 4: A Capability Description Language: CDL

At this point we have looked at the knowledge we need to represent in the messages exchanged during capability brokering and several areas of AI that need to represent similar knowledge. Our aim is to define a new capability description language that will be expressive and highly flexible and can be used to reason about capabilities. In the next step towards this goal we will define our new capability description language, CDL, that will be used for capability brokering. The contribution of this chapter will be the definition of the different aspects of CDL, including its syntax and various examples to illustrate the language.

Sections:

• Problems for Capability Representations: In this section we will look at problems with approaches to representing capabilities, described in chapter 2, when they are used for capability brokering. We will also highlight crucial ideas that we will adopt for our capability description language. This section sets the frame for the capability language that follows.
• Achievable Objectives: In this section we will define the core of our capability description language. This will include basic concepts, syntax, and examples to illustrate the language.
• Performable Tasks: In this section we will extend CDL to allow for the representation of performable actions which will be based on the description of achievable objectives. This will include basic concepts, syntax, and examples to illustrate the language.
• Other Properties: In this section we will show how an agent advertising its capabilities can be represented in CDL and we describe additional properties which are required to accomplish this.
• Examples: In this section we will show how the scenarios introduced in chapter 3 and the agents involved in them can use CDL to represent their capabilities. The content of the messages described in section 3.3 will be given in CDL here.

Chapter 5: Algorithms and Implementation of CDL

At this point we have defined the capability description language CDL that will be used to represent general capability knowledge. Our aim is now to show that CDL can be used to reason about capabilities as illustrated in our scenarios and that it is indeed expressive and flexible. The next step towards this goal will be to show how specific problems can be evaluated against capability descriptions in CDL. The contribution of this chapter will be the description of the algorithm used to perform this evaluation and its integration into the agent framework chosen for the implementation.

Sections:

• Basic Capability Evaluation: In this section we will show how simple capability descriptions in CDL are represented internally and can be evaluated against simple task descriptions.
• Extended Capability Evaluation: In this section we will show how more complex capability descriptions containing input-output constraints, performable actions, and properties can be evaluated against task descriptions in CDL.
• Capability Retrieval in JAT: In this section we will show how the Java Agent Template was used to implement the agents described in this thesis. We will also describe how the broker reacts to different message types it may receive and how it retrieves capabilities.

Chapter 6: Further Experiments and Results

At this point we have defined CDL, an expressive and flexible action representation that can be used to represent and reason about capabilities of intelligent agents. Our aim in defining this formalism was to address the problem of capability brokering. The next step will be to conduct further experiments with the broker by exploring variations on the scenarios described in section 3.3. The contribution of this chapter will be a summary of the practical results achieved in this thesis.

Sections:

• Variations on the Expressiveness Scenario: In this section we will present further interestingly different variations of the expressiveness scenario (example 3.2) to illustrate the generality of our broker as well as some limitations.
• Variations on the Flexibility Scenario: In this section we will present further interestingly different variations of the flexibility scenario (example 3.3) to illustrate the generality of our broker as well as some limitations.
• Performance Issues: In this section we will reflect on some performance issues: how expressiveness and flexibility affect broker performance and how our approach might scale up if the number of problem-solving agents was increased drastically.

Chapter 7: Expressiveness of CDL

At this point we have described our capability description language CDL which can be used to represent the content of messages required for capability brokering. We also have shown how CDL can be used for capability retrieval. Our aim now is to show that CDL has two desirable properties: it is expressive and flexible. The next step towards this goal will be to describe what we mean by expressiveness. The contribution of this chapter will be a description of our concept of expressiveness of action representations and its application to CDL. A comparison of the expressiveness of CDL with that of other action representations will follow in section 9.2.

Sections:

• Why more Expressiveness?: In this section we will discuss why expressiveness is one of the properties we want in CDL. We will use the more complex scenarios (from section 3.3) to illustrate this point along with providing a more theoretical argument.
• Expressiveness of AR Languages: In this section we will introduce a (fairly lightweight) theoretical framework that defines what we mean by the expressiveness of action representation languages and allows for comparisons of such formalisms.
• CDL: An AR1 Language: In this section we will present a formal semantics for CDL that can be used to compare its expressiveness to that of other action representation languages. Such a comparison will follow in section 9.2.

Chapter 8: Flexibility of CDL

At this point we have described our capability description language CDL which can be used to represent the content of messages required for capability brokering. We have also shown how CDL can be used for capability retrieval. Our aim is to show that CDL has two desirable properties: it is expressive and flexible. The next step towards this goal will be to define what we mean by flexibility in action representations. The contribution of this chapter will be a discussion of how flexibility has been achieved through decoupled action representations. In particular, we will be highlighting the issues involved in implementing this approach in CDL. A comparison of the flexibility of CDL with that of other representations will follow in section 9.2.

Sections:

• Why Flexible Action Representations?: In this section we will argue why we need a flexible action representation for capability descriptions. This argument will be based on a scenario presented earlier in this thesis (in section 3.3).
• Defining and Implementing Flexibility: In this section we will define what we mean by flexibility and discuss some of the problems involved in implementing flexible representations such as CDL through decoupled languages.

Chapter 9: Related Work and Evaluation

At this point we have defined CDL, an expressive and flexible action representation that can be used to represent and reason about capabilities of intelligent agents. Our aim in defining this formalism was to address the problem of capability brokering. The next step will be to compare CDL to the more closely related work described in chapter 2. The contribution of this chapter is an evaluation of CDL, specifically its expressiveness and flexibility, through a comparison with related work. It will also use a range of examples from other domains to demonstrate the generality of our approach.

Sections:

• Comparison with other Brokers: In this section we will present a comparison of our CDL broker with several other brokers described in section 2.1. Our focus will be on the capability description languages and matching algorithms used by the different systems.
• CDL: Expressiveness and Flexibility: In this section we will look at the two important properties of CDL again and show what has been achieved and where there are still open issues.
• Other Domains: In this section we will briefly discuss and reflect on the adequacy of CDL if it was applied to common domains used in related systems and approaches. It will demonstrate the generality of our approach.

Chapter 10: Conclusions

At this point we have described and addressed the problem of capability brokering. We have defined a new capability description language that can be used for this purpose. We also have demonstrated and discussed two new and desirable properties of this language: its expressiveness and flexibility. The final step will be to summarise the argument presented in this thesis and reflect on it.

• Possible Extensions: In this section we will indicate how the scenarios described in chapter 3 could be extended and how these extensions could be realized in the framework described in this thesis. This will show the extensibility as well as current limitations of our approach.
• Summary: In this section we will summarise the results of the work presented in this thesis. This will include what has been achieved as well as problems encountered.