Friday, October 07, 2005

Scalability: an important feature to achieve in a Multi-agent system

For commercial software systems, scalability it's an important feature to have. This gives the customer the possibility of expand the system according to present and future demand, without having to stop and start again. Nowadays many business work 24 hours a day 7 days a week. To stop is not an option. If we want MAS to have success in a commercial environment we need to build scalable MAS. For my MAS, the fact of having a hierarchical organization of agents to solve the crew recovery problem and another to solve the aircraft recovery problem, will allow at a certain extend, the scalability that I refer in the beginning of this post.
As an example, suppose that we deploy the system with 3 agents, each one implementing a different algorithm for crew recovery. Later on, the customer found that the system is not able to solve some specific problems or that a new and much improved algorithm has been discovered that deals better with those kinds of problems. In this situation, we just need to develop a new agent that implements the new or improved algorithm and attached it to the existing organization and everything should be fine. We can do that without interrupting the MAS.
Another possible situation is the following: suppose that we found the need to have a new sub-organization, at the same level of crew and aircraft recovery, to deal with a different kind of problems (for example, passenger recovery). To be a scalable system, we just need to build the new sub-organization, with all the necessary agents to solve that kind of specific problems, and attach it to the existing MAS. However, at this level and according to our first draft, the organization is not hierarchical. How to solve this problem? How can we prepare our system so that the new organization captures the problems that should be solved by them and the other organizations ignore that kind of problems? Do you think it will be possible to have some kind of learning, at this level, so that the MAS learns how to solve unexpected problems? As usual, if you have any comments, please do so, using the above option for that.

Monday, October 03, 2005

A Brief Summary of the GAIA Methodology

During my study I have prepared a brief summary of the GAIA methodology. For those interested, please click in the title of this blog to see the PDF with the presentation.
This presentation was based in the following paper:

Developing Multi-Agent Systems: The GAIA Methodology
F. Zambonelli, N. Jennings, M. Wooldridge
ACM, Vol. 12, N. 3, July 2003

Other interesting papers referenced in the above one are:

Towards requirements-driven information systems engineering: The TROPOS project
J. Castro, M. Kolp, J. Mylopoulos
Inf. System Vol. 27 N. 6, June 2002.

From object-oriented to goal-oriented requirements analysis
J. Mylopoulos, L. Chung, E. Yu
ACM Vol. 42, N. 1, January 1999

Representing agent interaction protocols in UML
J. Odell, H. Parunak, C. Bock
Proc. 1st Int. Work. AOSE, Vol. 1957, 2001

Agent UML: A formalism for specifying multiagent software systems
B. Bauer, J. P. Muller, J. Odell
Int. Journal Soft. Eng. Knowl. Eng. Vol. 11 N. 3, April 2001

As usual, if you want to share any comments or ideas on these, please feel free to use the comments link above this post.

A Multi-Agent System for Intelligent Monitoring of Airline Operations

I have finished my first paper regarding the subject of my thesis. This paper has been submitted to EUMAS 2005 (Third European Workshop on Multi-Agent Systems). At present date I do not know if it is going to be accepted. However, I would like to give you a roadmap of the paper and share with you some of the ideas presented. If you want to read the full paper, just click on the title of this post. For an introduction to the subject of Airline Operations Control and all related problems (Crew Recovery, Aircraft Recovery, Passenger recovery, etc.) I recommend the reading of Section 1 - Introduction and of Section 2 - The Airline Scheduling Problem. If you want to know what methodologies and tools we are using, just read section 3. Section 4 - Vision and Scope of our MAS states the vision for this project, including the goals we proposed to achieve. We also point out some of the problems that arise during airline operations control. Section 5 - Analysis and Proposed Architecture is the most important one. Here we present for hypothesis and predictions related with the most relevant parts of our work, namely:
  1. We hypothesize that the main objective of airline operation (that is, flights always on
    time) will be much easier to achieve (that is, less flights delayed) if we take advantage of the fact that the crew members belong to different bases. We predict that if we solve the problems first with local resources and then with non-local resources, the solutions to the eventual problems will be much faster to find and, in some cases, the non-local solutions might be the only solution available.
  2. Second, we hypothesize that the use of different algorithms to solve the same problem (in crew and aircraft recovery) will improve the achievement of the main objective of the crew and aircraft recovery process (that is, to always find the better solution regarding “ensuring every flight has a crew” and “ensuring that all flights are on time”, respectively). We predict that using different algorithms (genetic algorithms, heuristic, etc.) in comparison with using always the same algorithm, to solve the same problem, will permit to (1) always find the best solution (according to the criteria defined by the company) and (2) to always find a solution, especially taking into account the fact that we might benefit from solutions presented by other bases, as stated in the first hypothesis.
  3. Third, we hypothesize that the implementation of a learning mechanism that will learn from the use of crew members (in comparison with the previous and published schedule and in characterizing specific situations) will permit a better use of the resources (especially crew members) in future schedules. We predict that, for example, if we learn the real use of stand by crew members in each month and in specific situations, will allow adjusting the stand by roster in similar months or similar situations of future schedules, permitting to release crew members to be schedule to flights (crew members are one of the most expensive resources in an airline company).
  4. Forth, we hypothesize that if we extend the learning mechanism to learn the profile of each crew member, regarding his/her preferences, will increase the level of satisfaction of them. We predict that applying the learned profile of each crew member in future schedules of corresponding months will produce a roster that will achieve the goals of the airline company and, at the same time, the satisfaction of the crew members. Increasing the level of satisfaction of a crew member will decrease the crew member’s absence to work.
I will put a post for each hypothesis in my blog so that you may express your opinion regarding each one of this subjects. Another important thing in this section is the first simplified version of the proposed architecture that you can see in the following picture:


Finally, Section 6 - Future work, gives an overview of what we would like to explore in the future. So, click the title of this post, read the document and comment the other related posts.