Скачать 43.13 Kb.
|supporting cooperation and constraints negotiation between time and resource managers|
7, avenue du Colonel Roche
31077 Toulouse cedex 4
email : email@example.com, firstname.lastname@example.org
INSA de Toulouse
Complexe scientifique de Rangueil
31077 Toulouse cedex
This paper is concerned with the design of distributed decision support systems for organizations (companies, project consortiums, virtual enterprises), in which several decision-makers have to cooperate. Typical situations can be found in the domain of the distributed management of time and resources (i.e. planning, scheduling, personal management, allocation of shared resources…). Each decision-maker has some latitude that enables to accommodate himself with unpredictable changes of his environment without disturbing the overall organization, making this last more reactive. Nevertheless this autonomy must be evaluated and controlled to ensure the global consistency of local decisions. To facilitate autonomy regulations between decision-makers, we propose to design tools supporting both local problem solving and cooperation. Our approach is based on a rigorous but non-deterministic use of CSP models and constraint propagation mechanisms (). The goal is the improvement of the robustness of decisions each decision-maker imposes to others, but also, in a reversible way, to evaluate the acceptability of external decisions he must comply with. We propose some protocols associated to asynchronous communications (via mailboxes) whereby decision-makers coordinate themselves and negotiate constraints. Managing interlaced conversations and several plausible solving scenarios is a complex task that needs first a good representation of the state of decision processes. We propose a tree-structure, in which nodes represent CSP models, and branching represent constraints addition derived from internal or external hypothesis. Our communication protocols and the evolution of such CSP trees are illustrated through several scenarios in the context of the resource-constrained multi-project management. We conclude on specifications of the distributed decision support systems that are currently under development.
Distributed decision, constraint propagation, negotiation, decision support.
When attempting to model the decision-making in socio-technical organizations, one has resort to the concept of distributed decision systems, in which several decision-makers or more generally decision centers, interact to realize some global objectives. Distribution can result first form decomposition. Due to the complexity and the volume of information to be managed, the decision system of enterprises is generally decomposed into several functions, solving smaller and more homogeneous sub-problems. Most often sub-problems are not independent and decision-makers need to cooperate. For example, in the context of the production management (), planners and shop-floor managers must cooperate to solve a load-balancing problem. Distributed decision problems also happen with the grouping of companies or with temporary organizations such as project consortiums or virtual enterprises .
From a computational perspective, much research works on negotiation and cooperation have been proposed in the field of Distributed Artificial Intelligence. The main topics concern multi-agents systems, distributed problem solving and constraints-based agents (, , ). Although many techniques and algorithms have emerged of these works, most of them do not include the social dimension of interactions between human decision-makers (e.g. ). This led to define artificial organizations where decision-makers are replaced by software agents or where their role is limited to the tuning of some numerical parameters of the model of these agents (e.g. priority or utility factors). At the same time, the increasing availability of communication and computation capacities suggest to study new methods of cooperative work, using workflow-based information systems and Groupware (, , ).
This work investigates the particular field of organizations dealing with time and resource management problems, for which we intend to design distributed decision support systems. Our approach seems relevant in the case of organizations with a limited level of decision automation, but with a good level of communication. We first recall the basic concepts and assumptions of our approach of the cooperation.
A constraint based approach of the cooperation in a network of decision centers.
In a network of decision centers (, ), each node corresponds to one or several decision-makers eventually assisted by software tools; the decision center is in charge of a subset of decision variables, values of which must be communicated to other centers and influence their decisions. We suppose the final value of each decision variable is managed by only one node, but several recipient nodes may exist. Each decision center has some latitude that it uses to absorb unpredictable changes of its environment. This kind of autonomy generally increases the reactivity of the network by limiting the diffusion of unexpected happens and the time spent to treat them. Nevertheless, autonomy is generally limited and regulations are necessary to ensure that local decisions are globally consistent.
We study the cooperation through the interaction processes by which decision centers regulate their autonomy in order to satisfy both private and global objectives. Two aspects of cooperation are highlighted here.
Coordination deals with time aspects of the cooperation and suggests the existence of explicit rules that states causal precedence or time bounds between several local decision-making sessions. Such coordination constraints link for example the planning and the scheduling functions in shop manufacturing: planning is computed on a weekly basis taking into account inventory levels and firm orders, as scheduling is processed every day and must consider the planning output and the really daily capacities.
Negotiation takes place to prevent or to solve conflicts between decision centers. It can be facilitated by protocols i.e. procedural rules that decision centers follow when communicating. We distinguish conversations in which two decision centers prepare future decisions (negotiation) and conversations leading to revise decisions previously accepted (re-negotiation).
In each center , local problem is formulated as a Constraint Satisfaction Problem (CSP). This CSP model is characterized by:
A local solution is a compound assignment (one value for each decision variable) such that all constraints are satisfied. The influence of external decisions on the decision-making in center is expressed by the presence of some external decisions in and ; more precisely, is decomposed into two complementary subsets:
Furthermore, we distinguish in communicated and not communicated (private) variables: .
In the following, we will call downstream centers (relatively to ), those to which at least one decision of must be communicated.
Conversely, upstream centers denote centers responsible of at least one decision of . Formally:
The special case of the decisions that come from the exterior of the network leads to model some source centers with empty sets , and . Conversely centers that only receive decisions of the network are modelled as sink centers and have empty sets , and .
In any center (excepted source and sink centers) a first form of autonomy evaluation can be realized through the analysis of the space of admissible internal decisions for given values of external decision variables. This deductive analysis is based on general or dedicated constraint propagation mechanisms and yet implemented in several programming languages.
The second form of autonomy evaluation makes a reversible use of these CSP models. Assuming commitments and preferable internal decisions in one center, the same propagation mechanisms may determine the range of compatible external decisions. This information can be communicated to upstream centers in order to prevent conflicts. In this case, the analysis can help decision-makers to evaluate the autonomy margins that they can expect from negotiations.
We give at the end of this paper a synthesis of the different kinds of specifications that can be proposed for the design of such distributed decision support systems.
Classification of constraints
Many types of constraints must be considered in practice. We propose to first distinguish three kinds of formal explicit constraints that influence the decision making in each decision-center.
Actually, for the sake of simplicity, we make the strong hypothesis that decision centers do not have the autonomy to revise the network architecture and its coordination rules or to modify procedural constraints. Therefore, support systems are intended to assist the user to question only the model constraints.
Modeling interactions between centers
A general classification of situations involving cooperation has been proposed in . It distinguishes several cooperation schemes according to space and time criteria (same/different place and same/different time).
We only consider organizations where decision-makers can be at different place (virtual enterprise, network of companies…) and/or at different time. So, we choose an approach based on electronic asynchronous private messages as e-mail. Let us recall that asynchronous conversations don’t stop a center as for synchronous ones (phone, meeting, etc).
Negotiation and renegotiation process
We distinguish negotiations from renegotiations. Although the purpose of both processes is to take decisions, negotiations occur before decisions are taken for the first time, whereas, renegotiations occur when a center wants to question an already taken decision.
Generally, negotiations are used for planning. Renegotiations, and specially the ones that need to be reactive, often require that new decisions are close for the old ones in order to ensure a relative stability of the decision process.
Decision preparation and decision making
Negotiation and renegotiation processes are decomposed in two stages (see Figure 1):
Figure 1 : (re)negotiation decomposition
We propose two protocols that implement decision preparation and decision making. Both stages can be initiated by the center responsible of a decision (A) or by its downstream centers (Bi). But in all cases, center A provides the control and the conclusion of the conversation.
Let us describe the protocol Pt1 in which A, the center responsible of a set of decisions, send a message E to ask downstream centers (Bi) for an opinion. Bi centers may reply
If a downstream center B1 initiates the process, an additional stage is inserted at the beginning of Pt1: B1 sends a message to ask A to call a decision (previously communicated by A to Bi) into question. If A does not agree with B1, it replies
Figure 2: decision making initiated by A
Decision preparation protocol
This process is less restrained than the decision-making process. It allows “free” conversation between centers.
This process starts with a request H initiated by A or Bi (see Figure 3). During the process, each center can give its opinion:
Figure 3: decision preparation
state representation of the solving process
The goal of any center is to determine at least one set of admissible values for all variables it is in charge of, taking into account all types of constraints that are relevant at time t. As one or several conversations are in progress, some decision values are still hypothetical. In the following, we name hypothesis any constraint that is either the assignment of a decision variable (e.g. x=v) or a domain constraint (xD). Let us notice that several types of hypothesis exist:
Hypotheses become commitments as soon as the decision-making process succeeds (see protocol Pt1 above).
To represent both the local problem in a center, different hypotheses, and different possible solutions, a tree structure is proposed (see Figure 4).
Each node corresponds to the state of a CSP model according to several hypothesis and commitments. The transition from a node to a descendant node corresponds to constraint addition in the model of the parent CSP. The root node represents the initial model with invariable data (nor decidable neither negotiable) and constraints. Under the root, the current model node corresponds to the initial model plus the constraints and decisions resulting of all commitments. Nodes of the lower levels (e.g.: M1,M2,M3) include nodes that result from the integration of private, upstream and downstream hypothesis. Finally, alternative solutions (e.g.: S1) can be also represented on the lowest leaves of this tree. Adding inconsistent hypothesis can lead to a CSP model with no solution (e.g.: M3 on Figure 3). The order in which hypotheses are chained, create a hierarchy representing for example the level of confidence (or plausibility), decision-makers have in each hypothesis.
This tree evolves with:
Figure 4: tree diagram of the center state
The aim of this example is to show a network of centers, its different constraints, and a negotiation process.
This example is derived from a real problem in project management (see ). In this example, 2 projects argue about the allocation of 2 resources (an “heavy” resource and personal). Each project and each resource is managed by a specific center (P1, P2,,Rh and Rp).
Description of the network of centers
Organizational and procedural constraints
Each project center i has to manage one project. It has to establish the date (tij) at which project tasks (j) start. It has to take into consideration the delivery date (Di) negotiated with the client and the resources availability. The task duration (pij) may change according to the allocated amount of personal, excepted for tasks using Rh, which have a fixed duration.
Each resource center has to manage one resource type and ensures that there is not any conflict of utilization. The resource Rh is a disjunctive one: two tasks cannot be executed at the same time.
The personal resource is a cumulative one: each task requires a given amount (qij) to be processed; at any time, the sum of the amounts required by the set of tasks using this resource must be smaller than the capacity of the resource. Increasing the number of allocated persons can shorten the duration of any task that use some personal.
In brief, project centers decide the starting dates of the tasks and the personal center decides the duration of the tasks.
Figure 5: project management centers
Normally, a project center knows the delivery date (Di) of the project before taking its decisions. In addition, the personal center knows the starting date of tasks before it takes its allocation decisions.
Model of each center
Since project centers manage one project and no resource (only precedence constraints and no resource constraints), their CSP model has only real variables and linear binary constraints. In this special case, we can use general methods such as the simplex algorithm or graph-based methods as PERT. Constraint propagation is very efficient and useful: unfeasible problems are always detected; if the problem has at least one solution, the maximal range for each variable can be easily determined. This information can drastically restrict the search space of any automated or interactive solving tool.
Resource centers have to manage resource disjunctive or/and cumulative resource constraints. So, CSP models are composed of real and integer variables. In this case, constraint propagation mechanisms are less efficient (see ). These models can be solved by exact methods or by heuristics methods depending on the size of the model. As our example is very limited, we choose an exact method (linear integer programming included in the Xpress-MP software).
Project 1 is being running: two tasks have been completed, but a third is still running. The duration and the amount of personal allocated to tasks of project 1 have been already decided and negotiated. Project 2 must begin as soon as possible. P2 must negotiate the plan for its tasks. The Figure 6 shows the tree representation of the initial state of each center. E1 represents the commitment on the starting dates (between P1 and Rh, Rp), and E2 the commitment on the amount of personal allocated (between P1 and Rp).
Figure 6: initial state of each center
To establish a plan, P2 asks RH and RP to evaluate H3. It launches a new decision preparation process (see Figure 7). The bounds of starting dates constitute the initial hypothesis (H3). Each resource center responds
Figure 7: exchanged messages
Figure 8: center state at the end of the first step
Once it integrates the answers, P2 estimates that it does not have enough autonomy: the number of choices to decide the date of the last task is too small. P2 center sends a new proposal (H6) with smaller boundaries than in H3 (see Figure 9). RH responds
Figure 9: second step
If RP applies the new hypothesis, no solution can be found. A different use of the CSP model helps then to determine a conflict between the last task of each project. One way to remove the conflict is to reduce the amount of personal alloted to the last task of the project 1. So, RP launches a new renegotiation process with the P1. This last responds
Figure 10: evolution of trees
RP estimates it has now enough autonomy. It answers
Figure 11: final trees
This example shows a negotiation process between three centers. The purpose of this negotiation is a regulation of the autonomy: P1 needs some autonomy and tries to get it from Rp. Rp launches a renegotiation with P2. P2 transfers this autonomy to P1 via RP.
GENERAL SPECIFICATIONS OF A DISTRIBUTED DECISION SUPPORT SYSTEM
We give hereafter a synthesis of the different kinds of specifications that can be proposed for the design of distributed decision support systems. A prototype is actually developed. It addresses the problem presented in the example above.
Supporting the problem modeling and the problem solving
In a given state during the decision process, a decision-maker may have to determine:
Taking time into consideration
Nevertheless the problem of each decision-center is not static. As time passes, information continuously arrives in one center and the set of variables and the set of constraints change. To help decision-makers, decision support tools must not be limited to the analysis of static problems. The support system must maintain a state representation of the center: it helps the decision-maker to manage and to update several scenarios. Moreover, the decision-maker can be warned when some limit times are close to be reached, example:
The support system may help the decision-maker to manage his mailbox (selection, ordering…). For example, it would better to treat decision making messages prior to preparation ones, renegotiation messages prior to negotiation ones, … The decision support system may also help to respect the communication protocols and to determine who to first negotiate with.
This paper has presented an approach of the distributed decision problem in organizations in which several decision centers must cooperate. This cooperation is based on the modeling of both the local problem of each center and of its interface with the network, essentially in terms of constraints. Thanks to the use of constraint propagation mechanisms, useful information can be logically inferred to serve the negotiation between centers. The goal of this work is not to design artificial architectures such as agent networks, but want to be compliant with real interaction process developed in socio-technical organizations where humans keep a major role in the decision-making. A set of general specifications for the design of decision support systems has been given. Its originality is to integrate various questions that are linked to the distributed decision problem in a dynamical environment (problem analysis, solving and communication).
 A. Agostini, G. De Michelis, S. Patriarca, R. Tinini, “A prototype of an integrated coordination support system”, Computer Supported Cooperative Work, 2:209-238, 1994.
 I. Bazet, G. De Terssac, J. Erschler, “Les interactions dans la gestion des contraintes : la double gestion des contraintes”, ERGO IA, Biarritz (France), Oct 1998.
 G. Bel, J.B. Cavaillé, J. Delmas, D. Dubois, J. Erschler, P. Esquirol, H. Fargier, C. Mercé , P. Lopez, H. Prade, C.Thierry., “Distribution de la décision pour la gestion du temps et des ressources (projet DIDOM)”, 7eme EURO conf de Bruges, March 1997.
 C. Bérard, JC. Deschamps, P. Farthouat, “ Une approche coopérative pour l'ordonnancement des systèmes de production”, GRP Cachan, October 1997.
 R.I. Brafman, M. Tennenholtz, “modeling agents as qualitative decision makers”, Artificial Intelligence, 94 pp. 217-268, 1997.
 JP. Camalot, P. Esquirol, “Aide à la décision et à la négociation dans un problème de gestion de production distribuée”, 2ème congrès international Franco-Québécois de génie industriel, Albi (France), Septembre 1997.
 “L’entreprise communicante”, Claude Foulard, Hermes, 1998.
 MJ. Huguet, G. De Terssac, J. Erschler, N. Lompré, “De la réalité à la modélisation de la coopération en gestion de production”, coopération et conception, Eds. G. De Terssac and E. Friedberg, Octares Editions, 149-169, 1996.
 S. Kraus, J. Wilkenfeld, G. Zlotkin, “Multiagent negotiation under time constraints”, Artificial intelligence, 75:297-284, 1996.
 A. Nareyek, “Constraint-Based Agents”, AAAI 97 Workshop on Constraints and Agents, Providence, Rhode Island, July 27-31, 1997.
 S. Nurcan, “Analyse et conception de systèmes d’information coopératifs”, Technique et science informatiques, 15(9):1287-1315, 1996.
 S. Sen, T. Haynes, N. Arora, “Satisfying user preferences while negotiating meetings”, Int. J. Human-Computer Studies, 47, 407-427, 1997.
 T. Schael, “Théorie et pratique du workflow”, Springer, 1997
 P. Torres, P. Lopez, “A generic algorithm for solving the not-first/not-last problem in disjunctive scheduling”, 6th international worshop on project management and scheduling, Istanbul, 305-308, july 1998.
 D. Trentesaux, “L'analyse multicritère : une approche performante pour l’intégration de l'opérateur humain pour le pilotage réactif et distribué des systèmes de production”, GRP Cachan, October 1997.
 E. Tsang, “Foundations of constraint satisfaction”, Academic Press, 1993.
|Keywords Agents, Gaming, Autonomy, Negotiation, Artificial Intelligence. Introduction||Decision Support and Expert Systems (mis 538)|
|Chapter 9 e-business Decision Support Learning Objectives||A spatial decision support system for bank location: a case study|
|Enabling Decision Support and Costing of Product Designs by using Visual Metaphors||Representing and using legal knowledge in integrated decision support systems: DataLex WorkStations|
|Decision support and disease management: a Logic Engineering approach John Fox and Richard Thomson||[Abel 1992] Abel, D. J., Yap, S. K., Ackland, R. G., Cameron, M. A., Smith, D. F. et Walker, F. G., Environmental decision support system project: An|
|Supply, Installation, Testing, Integrating and commissioning of Boundary layer wind profiler at igi airport –as part of strengthening of Instrumentations for suitable completion of the project of Aviation Weather Decision Support System (awdss)||Proving a distributed deadlock detection/resolution algorithm with constraint automata|