Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction




Скачать 43.13 Kb.
НазваниеKeywords Distributed decision, constraint propagation, negotiation, decision support. Introduction
Дата28.10.2012
Размер43.13 Kb.
ТипДокументы
supporting cooperation and constraints negotiation between time and resource managers

Jean-Pierre Camalot

Patrick Esquirol

LAAS-CNRS

7, avenue du Colonel Roche

31077 Toulouse cedex 4

email : camalot@laas.fr, esquirol@laas.fr

INSA de Toulouse

Complexe scientifique de Rangueil

31077 Toulouse cedex

Abstract


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 ([16]). 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.

keywords


Distributed decision, constraint propagation, negotiation, decision support.

INTRODUCTION

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 ([4]), 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 [7].


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 ([9], [10], [12]). 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. [5]). 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 ([1], [13], [7]).

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 ([8], [6]), 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 set of decision variables ,

  • a set of domains (one domain for each decision variable), and

  • a set of constraints (each constraint restrict the assignments of one or more variables).

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:

  • is the subset of internal decision variables (those which center is responsible of)

  • is the subset of incoming decision variables.

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.

  • Organizational constraints come from the definition of the network and state who is in charge of the decision-making, the type of each variable, and what coordination rules that decision-making tasks should respect (time bounds, periodicity, precedence...). To that aim, the life cycle of an elementary decision is composed of three states (negotiable, renegotiable and frozen).

  • Model constraints describe the formal CSP model of local decision problems. They affect the domain of decision variables and the set of admissible decisions.

  • Protocols or procedural constraints structure the cooperation processes. They describe the type and the semantics of messages between two cooperating centers (e.g. commitments, expected behavior) and of the time constraints that limit the range of possible conversations.

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 [7]. 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):

  • Decision preparation. This stage is optional. Centers engage such a discussion when they want to ensure the robustness of a future decision or when they ask proposals from other centers. This discussion has an informational purpose but is susceptible to be applied in the future. The discussion does not commit the protagonists.

  • Decision-making. This stage is mandatory and closes negotiation or renegotiation processes. By default, centers commit themselves to honor the taken decisions. To modify taken decisions, centers must enter in a new renegotiation process.


Figure 1 : (re)negotiation decomposition

Protocols


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.

Decision-making protocol


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 (I accept the decisions described in E in my model) or . Depending on the responses it has collected, A must or E (see Figure 2). Decisions become commitment as soon as the message is sent.

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 (I don’t want to modify my decision) otherwise it makes a new proposal and follows Pt1.



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: , but also (adjustments) and (new proposals). Depending on the response it has collected, A can consult again the centers Bi ( and ) or it can close the decision preparation with (H is valid hypothesis) or .



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:

  • a private hypothesis concerns a constraint on any type of decision variable that has not been communicated;

  • an upstream hypothesis concerns a constraint on variables of , communicated by some upstream center;

  • a downstream hypothesis concerns a communicated constraint on some variables of .

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:

  • The time. Generally, some tree’s branches disappear. If limit dates are associated to the decision preparation process, some hypothesis can be transformed into commitments or suppressed. In any case this kind of behavior must be under the control of decision-makers.

  • The emission of new hypothesis, which create new branches. For example, if several decisions are compared, a new branch is created for each hypothesis.

  • The negotiation process which may create or destroy some branches. For example, when a center gets a new message, it creates a new hypothesis or a new commitment.



Figure 4: tree diagram of the center state

example


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 [3]). 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 [14]). 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).

Initial state


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

First step


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 adjustments (H4 and H5). The Figure 8 shows the evolution of the trees.



Figure 7: exchanged messages



Figure 8: center state at the end of the first step

Second 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 adjustments (H7).



Figure 9: second step

Third 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 (E8). The Figure 10 shows the evolution of the trees. We notice that the updating of E2 by E8 requires a new elaboration of all the nodes below the current model node of RP.



Figure 10: evolution of trees

Fourth step


RP estimates it has now enough autonomy. It answers clarification (H9) to P2. Once it integrates the answers, P1 become satisfied, so it closes the process (H10). The figure 11 shows the final trees. After this process, P1 can launch a decision-making process that stands a good chance to succeed.



Figure 11: final trees

Example conclusion


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:

  • his actual autonomy. Several indicators can be proposed to that aim: a consistency check of the current CSP model, the bounds of internal decisions (Deci) and incoming decision (Ini), a sensibility analysis… The availability and the cost of these indicators are dependant of the characteristics of the CSP model (real/rational/integer variables, binary/n-ary constraints …).

  • the consequences of some decisions, in the case of an acceptable level of autonomy. This information can be communicated to upstream or downstream centers in order to either to increase the chance to be consistent with future incoming decisions or to increase the robustness of its internal decisions.

  • which constraints to call into question, in the case of an unacceptable level of autonomy. An automated strategy can be built from the classification of constraints supplied by the decision-maker: hypothesis or constraints are relaxed in the reverse order they were taken until a consistent model is found.

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 limit time for the decision-making on some variables.

  • the limit time for replying to some messages.

Supporting communication


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.

CONCLUSION


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).

references


[1] 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.

[2] 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.

[3] 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.

[4] C. Bérard, JC. Deschamps, P. Farthouat, “ Une approche coopérative pour l'ordonnancement des systèmes de production”, GRP Cachan, October 1997.

[5] R.I. Brafman, M. Tennenholtz, “modeling agents as qualitative decision makers”, Artificial Intelligence, 94 pp. 217-268, 1997.

[6] 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.

[7] “L’entreprise communicante”, Claude Foulard, Hermes, 1998.

[8] 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.

[9] S. Kraus, J. Wilkenfeld, G. Zlotkin, “Multiagent negotiation under time constraints”, Artificial intelligence, 75:297-284, 1996.

[10] A. Nareyek, “Constraint-Based Agents”, AAAI 97 Workshop on Constraints and Agents, Providence, Rhode Island, July 27-31, 1997.

[11] S. Nurcan, “Analyse et conception de systèmes d’information coopératifs”, Technique et science informatiques, 15(9):1287-1315, 1996.

[12] S. Sen, T. Haynes, N. Arora, “Satisfying user preferences while negotiating meetings”, Int. J. Human-Computer Studies, 47, 407-427, 1997.

[13] T. Schael, “Théorie et pratique du workflow”, Springer, 1997

[14] 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.

[15] 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.

[16] E. Tsang, “Foundations of constraint satisfaction”, Academic Press, 1993.

Похожие:

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconKeywords Agents, Gaming, Autonomy, Negotiation, Artificial Intelligence. Introduction

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconDecision Support and Expert Systems (mis 538)

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconChapter 9 e-business Decision Support Learning Objectives

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconA spatial decision support system for bank location: a case study

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconEnabling Decision Support and Costing of Product Designs by using Visual Metaphors

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconRepresenting and using legal knowledge in integrated decision support systems: DataLex WorkStations

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconDecision support and disease management: a Logic Engineering approach John Fox and Richard Thomson

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction icon[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

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconSupply, 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)

Keywords Distributed decision, constraint propagation, negotiation, decision support. Introduction iconProving a distributed deadlock detection/resolution algorithm with constraint automata

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница