Work Program

I. General information

1. Title of the Project

Advanced Computer Technologies Supporting Dynamic Planning and Execution

2. Project Manager

Sokolov, Boris Vldimirovich

3. Participating Institutions

St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 39, 14^th Liniya, St. Petersburg, 199178, Russia
Telephone:+7-(812) 328-44-50; Fax:+7-(812) 328-0685/328-44-50;
E-mail: spiiran@mail.iias.spb.su
Name of individual empowered to make commitments on behalf of the Institute (Signature Authority):
Yusupov, Rafael Midhatovich, Professor, Director, SPIIRAS
Telephone:+7-(812) 328-44-50; Fax:+7-(812) 328-0685/328-44-50;
E-mail: yusupov@mail.iias.spb.su
Name(s) of Sub-institutions: No

4. Partner

European Office of Aerospace Research and Development,
223-231 Old Marylebone Road, London, NW1 5TH, United Kingdom
Name of individual empowered to make commitments on behalf of the Partner (Signature Authority):
Dr. Roy F. Phillips
Title: Program Manager, International Research
Tel: +44-20-7514-4950 Fax: +44-20-7514-4960
E-mail: eoard@london.af.mil
Contact Person:
Dr. Christopher E. Reuter
Tel: +44-20-7514-4474 Fax: +44-20-7514-4960
E-mail: chris.reuter@london.af.mil

II. Specific information

Task 1. Agent-based Intelligent System of Operation Planning and Scheduling: Architecture, Theoretical Background and Tool Prototype

(See also Power Point presentation Task 1)

1. Introduction and Overview

The first objective of the Task 1 is to develop a theoretical background and software tool prototype of agent-based intelligent system for operation planning and scheduling. From theoretical point of view this task is recognized as a real time planning and scheduling problem. Although the research on such problems have been pursued for several decades, the problem is still of hot interest. Many real life applications are formulated in terms of real time planning and scheduling, for example, manufacturing planning, transportation management, shipping, workflow management, etc. Many of newly arisen applications, for example, creation of virtual enterprises [1], business process reengineering [11], and so on, are also of the similar class. All these tasks are of exponential complexity and, as a rule, they cannot be solved efficiently in a traditional way. Use of knowledge-based approaches developed during last two decades makes it possible to cope with some of such applications of not very high dimensions and complexity. However, such approaches are not efficient for the most real-life planning and scheduling applications. Indeed, any real-life application in industry and military is distributed and is of extra high dimension. One more dimension of such tasks is time. As a rule, permissible decisions are constrained due to many complex and interconnected constraints that complicate the operation planning task much more.

It is elsewhere accepted now that real time planning and scheduling tasks can not be implemented efficiently without using advanced achievements in the area of modern information technologies. Recent achievements in the area of agent-based theory and in the respective technology propose a promising way to cope with the complexity of the real-time planning and scheduling tasks. Indeed, multi-agent technology is being developed especially for distributed high dimensional computationally complex applications. Specific properties of a multi-agent technology are distributed way of task solving and focusing on search of an approximate decision instead of optimal one. Due to this properties a complex task of planning and scheduling can be reduced to a limited number of much more simple tasks coordinated by a high level procedure. Moreover, in some cases coordination may be realized in purely distributed way without any high level coordination.

A specific of distributed way of decision making procedures in multi-agent systems is that each agent must make decision having a deficit of information about environment and other agents' behaviors (decisions). To master an information deficit and to coordinate individual behaviors, agents use negotiation. An algorithm of negotiation is called a negotiation protocol. Design of negotiation protocol is key point of any multi-agent system development including those that intended for solving planning and scheduling tasks. For competitive (self-interested) agents the most promising negotiation protocol is one that is based on the metaphor of an auction [14,15,16]. In fact, auction-based negotiation was the first model of negotiation used for coordination of agent behavior. Later on it was investigated by a number of authors (see, for example, [1,11,13,14]) where it was shown that auction-based negotiation protocol is an efficient way for self-interested agent behavior coordination. In the Project a variant of auction-based negotiation protocol will be used as well.

In general case an auction-based model of agents' negotiation protocol can be interpreted in two different senses in respect to application. On the one hand, agents can be representatives of really competing entities, which are self-interested and aiming at maximizing of own benefit only. In this case, auction is a mathematical model of a real-life competition of entities. On the other hand, an auction-based model of agent behavior coordination may be used only as a metaphor for complex high dimensional task decomposition. Such a metaphor if it is possible to introduce an artificial competition can be used as a coordination mechanism of sub-tasks as well. Note that such point of view have been not considered yet as a way of coordination of behavior in cases when agents are not self-interested. The latter idea is one of the major peculiarities of the approach to be used in the Project within the first task.

Thus, the first task of the Project aims at development of mathematical foundations, architecture and principles of implementation of the multi-agent technology for real-life operation planning and scheduling. The research group of SPIIRAS that will be involved in this research possesses the required experience to carry it out successfully. The main related original publications are given below (see [2],[10]). At present the group is involved in the projects that are close to the present one. In particular, the projects that are now under research were got from Russian Foundation of Basic Research ("Agent-based model, mathematical basis and algorithms of distributed solving of combinatorial tasks", 1999-2000), and from Ministry of Science and Technology of Russian Federation ("Agent-based Technology for Real time Planning, Scheduling", 1999-2000). The experience obtained within the above projects fulfillment will be utilized for the present Project.

References

[1]. K.Fisher, J.Muller, I.Heimig, A-W.Scheer. 1996, Intelligent Agents in Virtual Enterprises. In Proc. of the First Intern. Conference "The Practical Application of Intelligent Agents and Multi-Agent Technology", London, pp.205-224.

[2] V.Gorodetski, O.Karsaev. Algorithm of Rule Extraction from Learning Data. Proceedings of the 8th International Conference (joint Europe-USA) "Expert Systems Application & Artificial Intelligence" (EXPERSYS-96). 1996, IITT International, Paris, France, pp.133-138.

[3] V.Gorodetski. Basic Ideas of Agent Behavior Coordination and Auction-based Scheduling Model. Proceedings of the International Workshop "Distributed Artificial Intelligence and Multi-agent Systems"(DAIMAS'97). June15-18, 1997, St. Petersburg, Russia, pp.282-291. (in Russian)

[4] V.Gorodetski. Multi-agent Technology for Planning, Scheduling and Resource Allocation. Proceedings of the Third International Conference on Multi-agent systems (ISMAS'98). IEEE Computer Society, 1998, pp.429-430.

[5] V.Gorodetski. Information Technology and Multi-agent Systems. Journal " Problems of Informatization" No.1, 98, pp.3-15 (in Russian).

[6] V.Gorodetski. Multi-agent Technology for Real Time Planning. Journal " Problems of Informatization " No.1, 98, pp.33-40 (in Russian).

[7] V.Gorodetski. Multi-agent-Systems: The Main Properties and Models of Behavior Coordination. Journal "Information Technologies and Computer Systems", No.1, 1998, pp.22-34 (in Russian).

[8] V.Gorodetski, A.Lebedev. Multi-agent model for Real Time Resource Allocation. International Journal "Computacion y Sistemas", Vol.3, No.1, Julio-Septiembre/99, Mexico-City, pp. 17-24.

[9] V.Gorodetski, A.Lebedev Agent-based model of combinatorial optimization task. CD of papers of MAAMAW'99.

[10] V.Gorodetski, O.Karsaev, V.Samoilov. Multi-agent Technology for Distributed Planning and Scheduling. Proceedings of the International Conference "Intelligent Computer-oriented Design Systems-2000". Russia, September 3-8, 2000 (In Russian).

[11] N.R. Jennings, P. Paratin, M. Jonson, 1996. Using Intelligent Agents to Manage Business Processes. In Proc. of the First International Conference and Exhibition "The Practical Application of Intelligent Agents and Multi-Agent Technology", London, UK, pp.345- 376.

[12] J.P.Muller, M.Pishel, and M.Thiel, 1994. Modelling Reactive Behaviour in Vertically Layered Agent Architectures. In: Intelligent Agents. ECAI-94 Workshop on Agent Theories, Architecture and Languages. Amsterdam, The Netherlands, (Eds. M.J.Wooldridge and N.R.Jennings). Proceedings. Springer Verlag: 261-276.

[13] T.W.Sandholm. 1993, An Implementation of Contract Net Protocol Based on Marginal Cost Calculations, In Proceedings of 11^th AAAI, pp.256-262.

[14] T.W.Sandholm1996, Negotiation among Self-interested Computationally Limited Agents. Dissertation for Ph.D., 1996. http:// www.cs.wustl.edu/~sandholm/dissertation.ps

[15] Smith R. G., 1980, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on Computers C-29(12), pp. 1104-1113.

[16] Smith R. G., Davis R., 1981, Framework for Cooperation in Distributed Problem Solving, IEEE Transactions on Systems, Man and Cybernetics, SMC-11, pp.61-70.

2. Expected Results and Their Applications

The expected results of the first task of the Project will be a formal framework, mathematical model, architecture and software prototype of the agent-based operation planning and scheduling (OPS) systems, aiming to support technology of distributed OPS within a class of application. It is supposed that related applications correspond to the cases when decision must meet various types of constraints. In particular, decisions must meet a number of real-time and temporal constraints, technological constraints and resource constraints. It is supposed that the theoretical results and developed software will be validated on the basis of a case study for OPS. In more details, the expected results associated with the first task will be as follows:

1. Conceptual model of OPS technology and ontology of sub-tasks associated with the accepted technology of the operation planning and scheduling. Case study used in development of the OPS system software prototype.
2. Decomposition of the OPS task into generic sub-tasks that will make it possible to determine generic agents, their functionalities and task allocation over them.
3. Architecture of particular generic agents that constitute together an agent-based OPS system as a whole.
4. Mathematical basis and protocol of auction-based agents' negotiation and language for agent communication. It is supposed that the aforementioned mathematical basis will include three components: (1) algorithm of calculation of contracting strategy used by agent-contractors (this strategy must depend on information about environment available to agent-contractor), (2) bargaining strategy and (3) multi-dimensional criterion of the auction winner selection.
5. Object-oriented project of OPS system under development.
6. Software prototype implementing the developed mathematical basis, algorithms and architecture of OPS system.
7. Results of extended simulation of the developed OPS software system on the basis of a case study to be agreed with AFRL/IF.

Although the Project does not aim at the development of any industrial technology, nevertheless, to provide a possibility of its further technological development, it is intended to develop software using modern standard software tools like Visual C++, JAVA 2, SQL server, XML, etc.

The results to be obtained in the Project will not contain any business confidential information.

Completion of the Project in the future should open for research teams perspectives of collaboration with commercial and/or industrial organizations in development of advanced technologies in the area of advanced computer technologies supporting dynamic planning and execution

3. Scope of Activities

The scope of activity associated with the first task of the Project consists of five parts. The first part will be devoted to the development of the mathematical model of OPS system. The respective activity will include development of the task-oriented ontology of the domain "operation planning and scheduling" on the conceptual level and development of the formal models of the ontology components (concepts, tasks, scenarios etc.). In more details, this task comprises

1. Development of the domain concepts,
2. Tasks, data, resources and associated constraints structuring,
3. Decomposition of the models of the object behavior in terms of atomic acts, scenarios of behavior and meta-scenarios,
4. Specification of the relationships over concepts, tasks and scenarios, and relationships over scenarios of behavior and resources,
5. Formation of the classes of generic agents, their functionalities and task allocation over them.

The above part of activity will get ready all results that are necessary for the development of the architectures of the particular agents as well as architecture of the multi-agent OPS system as a whole. This task corresponds to the second part of activity.

The third part of activity will be devoted to the development of the negotiation and communication component of OPS systems. It will include development of a mathematical basis (a contracting strategy, a bargaining strategy, a winner selection strategy, etc.), protocol of auction-based agents' negotiation and language for agent communication.

The fourth part of activity will include development of the object- oriented project of the OPS software prototype. A standard tool for object oriented design will be used at this phase of research. This part activity will be very time consuming.

The last part of activity will include development, debugging and testing of the software prototype implementing the developed mathematical basis, algorithms and architecture of OPS system as well as extended simulation of the developed OPS software system on the basis of the developed case study. Software prototype code will be developed on the basis of the advanced software development kits including Visual C++, JAVA 2, SQL server, XML language, etc.

4. Technical Approach and Methodology

Technical approach within the research on Task 1 will be based on the recent achievements in the area of multi-agent systems with self-interested agents, theory of market-based agents' behavior coordination, methodology of discrete optimization, knowledge-based systems, agents' communication languages and some others. Development of the software prototype will be carried out on the basis on object-oriented design using a standard tool. The advanced software development kits (Visual C++, JAVA 2, SQL Server, XML, etc.) will be used for the development of the OPS system software prototype.

The basic idea of the methodology and technical approach that will be used in OPS system development is that operation is formulated as a network of contacts executed in a distributed way by a multi-agent system.

In brief, the agent-based model of an operation planning and scheduling task is built as follows. The entire operation is decomposed into interconnected atomic operations and each of them is considered as a contract. Thus, the entire operation is specified in terms of a contract network which nodes and arcs (directed edges) must meet many constraints of various types (temporal, real-time, technological, etc.). Each atomic operation must be executed via a number of different ways (processes) and each such process can be mapped a "Quality of Service" vector (QoS vector). The set of processes is factored into a set of specialized agent-contractors that interested in execution as many contracts as possible and that is why competing for getting such contracts.

Using contract network, contract allocation and multi-agent system metaphors make it possible to formalize operation planning in terms of multi-agent system using market-based approach as negotiation protocol for particular agents' behavior coordination. As a result, operation planning and scheduling task is formalized in terms of multi-agent model. The latter makes it possible to use advances in the theory and practice of multi-agent systems.