当前位置:首页 >> >> A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation

A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation

A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation
Pragnesh Jay Modi Hyuckchul Jung Milind Tambe Wei-Min Shen Shriniwas Kulkarni
University of Southern California/Information Sciences Institute 4676 Admiralty Way, Marina del Rey, CA 90292, USA modi,jungh,tambe,shen,kulkarni @isi.edu Abstract. In distributed resource allocation a set of agents must assign their resources to a set of tasks. This problem arises in many real-world domains such as disaster rescue, hospital scheduling and the domain described in this paper: distributed sensor networks. Despite the variety of approaches proposed for distributed resource allocation, a systematic formalization of the problem and a general solution strategy are missing. This paper takes a step towards this goal by proposing a formalization of distributed resource allocation that represents both dynamic and distributed aspects of the problem and a general solution strategy that uses distributed constraint satisfaction techniques. This paper de?nes the notion of Dynamic Distributed Constraint Satisfaction Problem (DyDCSP) and proposes two generalized mappings from distributed resource allocation to DyDCSP, each proven to correctly perform resource allocation problems of speci?c dif?culty and this theoretical result is veri?ed in practice by an implementation on a real-world distributed sensor network.

1 Introduction
Distributed resource allocation is a general problem in which a set of agents must intelligently perform operations and assign their resources to a set of tasks such that all tasks are performed. This problem arises in many real-world domains such as distributed sensor networks [7], disaster rescue[4], hospital scheduling[2], and others. Resource allocation problems of this type are dif?cult because they are both distributed and dynamic. A key implication of the distributed nature of this problem is that the control is distributed in multiple agents; yet these multiple agents must collaborate to accomplish the tasks at hand. Another implication is that the multiple agents each obtain only local information, and face global ambiguity — an agent may know the results of its local operations but it may not know which other collaborators must be involved to ful?ll the global task and which operations these collaborators must perform for success. Finally, the situation is dynamic so a solution to the resource allocation problem at one time may become obsolete when the underlying tasks have changed. This means that once a solution is obtained, the agents must continuously monitor it for changes and must have a way to express such changes in the problem. In this paper, we ?rst propose a formalization of distributed resource allocation that is expressive enough to represent both dynamic and distributed aspects of the problem. This formalization allows us to understand the complexity of different types of resource allocation problems. Second, in order to address this type of resource allocation problem, we de?ne the notion of a Dynamic Distributed Constraint Satisfaction Problem

(DyDCSP). DyDCSP is a generalization of DCSP (Distributed Constraint Satisfaction Problem) [8] that allows constraints to be added or removed from the problem as external environmental conditions change. Third, we present two reusable, generalized mappings from distributed resource allocation to DyDCSP, each proven to correctly perform resource allocation problems of speci?c dif?culty and experimentally veri?ed through implementation in a real-world application. In summary, our central contribution is 1) a formalization that may enable researchers to understand the dif?culty of their resource allocation problem and 2) generalized mappings to DyDCSP which provide automatic guarantees for correctness of the solution. There is signi?cant research in the area of distributed resource allocation; for instance, Liu and Sycara’s work[5] extends dispatch scheduling to improve resource allocation. Chia et al’s work on distributed vehicle monitoring and general scheduling (e.g. airport ground service scheduling) is well known but space limits preclude us from a detailed discussion [1]. However, a formalization of the general problem in distributed settings is yet to be forthcoming. Some researchers have focused on formalizing resource allocation as a centralized CSP, where the issue of ambiguity does not arise[3]. The fact that resource allocation is distributed means that ambiguity must be dealt with. Dynamic Constraint Satisfaction Problem has been studied in the centralized case by [6]. However, there is no distribution or ambiguity during the problem solving process. The paper is structured as follows: Section 2 describes the application domain of our resource allocation problem and Section 3 presents a formal model and de?nes subclasses of the resource allocation problem. Section 4 introduces Dynamic Distributed Constraint Satisfaction Problems. Then, Sections 5 and 6 describe solutions to subclasses of resource allocation problems of increasing dif?culty, by mapping them to DyDCSP. Section 7 describes empirical results and Section 8 concludes.

2 Application Domain
The domain in which this work has been applied is a distributed sensor domain. This domain consists of multiple stationary sensors, each controlled by an independent agent, and targets moving through their sensing range (Figure 1.a) illustrates the real hardware and simulator screen, respectively). Each sensor is equipped with a Doppler radar with three sectors. An agent may activate at most one sector of a sensor at a given time or switch the sensor off. While all of the sensor agents must act as a team to cooperatively track the targets, there are some key dif?culties in such tracking. First, in order for a target to be tracked accurately, at least three agents must collaborate — concurrently activating overlapping sectors. For example, in Figure 1.b which corresponds to the simulator in Figure 1.a, if an agent A1 detects a target 1 in its sector 0, it must coordinate with neighboring agents, A2 and A4 say, so that they activate their respective sectors that overlap with A1’s sector 0. Activating a sector is an agent’s operation. Since there are three sectors of 120 degrees, each agent has three operations. Since target 1 exists in the range of a sector for all agents, any combination of operations from three agents or all four agents can achieve the task of tracking target 1. Second, there is ambiguity in selecting a sector to ?nd a target. Since each sensor agent can detect only the distance and speed of a target, an agent that detects a target cannot tell other agents which sectors to activate. When there is only target 1 in Figure 1.b and agent A1 detects the target ?rst, A1 can tell A4 to activate sector 1. However,

Agent A1

Agent A2

1

O 2 Sector Number Target 1

Target 2 Agent A3 Agent A4

(a) hardware and simulator (b) sensor sectors Fig. 1. A distributed sensor domain

A1 cannot tell A2 which of the two sectors (sector 1 or sector 2) to activate since it only knows that there is a target in its sector 0. That is, agents don’t know which task is to be performed. Identifying a task to perform depends on the result of other related agents’ operations. Third, if there are multiple targets, that introduces resource contention — an agent may be required to activate more than one sector, which it can not! For instance, in Figure 1.b, A4 needs to decide whether to perform either a task for target 1 or a task for target 2. Since at most one sector can be activated at a given time, A4 should decide which task to perform. Thus, the relationship among tasks will affect the dif?culty of the resource allocation problem. Fourth, the situation is dynamic as targets move through the sensing range. The dynamic property of the domain makes problems even harder. Since target moves over time, after agents activate overlapping sectors and track a target, they may have to ?nd different overlapping sectors. The above application illustrates the dif?culty of resource allocation among distributed agents in dynamic environment. Lack of a formalism for dynamic distributed resource allocation problem can lead to ad-hoc methods which cannot be easily reused. On the other hand, adopting a formal model allows our problem and its solution to be stated in a more general way, possibly increasing our solution’s usefulness. More importantly, a formal treatment of the problem also allows us to study its complexity and provide other researchers with some insights into the dif?culty of their own resource allocation problems. Finally, a formal model allows us to provide guarantees of soundness and completeness of our results. The next section presents our general, formal model of resource allocation.

3 Formalization of Resource Allocation
A Distributed Resource Allocation Problem consists of 1) a set of agents that can each perform some set of operations, and 2) a set of tasks to be completed. In order to be completed, a task requires some subset of agents to perform the necessary operations. Thus, we can de?ne a task by the operations that agents must perform in order to complete it. The problem to be solved is an allocation of agents to tasks such that all tasks are performed. This problem is formalized next. , ? , ? where A Distributed Resource Allocation Problem is a structure – –
? ? ? ? = ?? ?? , ..., ?? , ..., ??

is a set of agents,

=

the p‘th operation of agent

? , ..., ? . is a set of operations, where operation ?? denotes . An operation can either succeed or fail. Let ??? ? ?,

denote the set of operations of . Operations in ??? ? are mutually exclusive; an agent can only perform one operation at a time. – ? is a set of tasks, where a task is a collection of sets of operations that satisfy the following properties: ? ? ?, (i) ? ? ?? ? (Power set of ? ) (ii) ? is nonempty and, ? ? ? , ? is nonempty; (iii) ?? , ?× ? ? , ?? ?× and ?× ?? . ?? and ?× are called minimal sets. Two minimal sets con?ict if they contain operations belonging to the same agent. Notice that there may be alternative sets of operations that can complete a given task. Each such set is a minimal set. (Property (iii) above requires that each set of operations in a task should be minimal in the sense that no other set is a subset of it.) A solution to a resource allocation problem then, involves choosing a minimal set for each task such that the minimal sets do not con?ict. In this way, when the agents perform the operations in those minimal sets, all tasks are successfully completed. To illustrate this formalism in the distributed sensor network domain, we cast each sensor as an agent and activating one of its (three) sectors as an operation. We will use ?? to denote the operation of agent activating sector p. For example, in Figure 1.b, = . Each agent can perform one of three we have four agents, ? so ?, ?, ?, ??? ?, where ??? ? = ?? ,?? , ?? . operations, so ? =

Now we only have left to de?ne our task set ?. We will de?ne a separate task for each target in a particular location, where a location corresponds to an area of overlap of sectors. In the situation illustrated in Figure 1.b, we have two targets shown, so we de?ne two tasks: ? = ?? , ?? . Since a target requires three agents to track it so that its position can be triangulated, Task ?? requires any three of the four possible agents to activate their correct sector, so we de?ne a minimal set corresponding to the all (4 ? ? ? ? ? ? ? choose 3) combinations. Thus, ?? = ?? , ?? , ?? , ?? , ?? , ?? , ?? , ?? , ?? , ? , ?? , ? ?? ? ? . Note that the subscript of the operation denotes the number of the sector the agent must activate. Task ?? can only be tracked by two agents, both of ? which are needed, so ?? = ?? , ?? . For each task, we use § (?? ) to denote the union of all the minimal sets of ?? , and for each operation, we use ? ??? ? to denote the set of tasks that include ?? . For instance, ? ? ? ? § (??) = ?? , ?? , ?? , ?? and ? (?? ) = ?? , ?? . We will also require that every 0. Formal de?nitions for operation should serve some task, i.e. ?? ? ? , ? ??? ) § and ? are as follows: –

?

set of tasks that are currently present. This set is determined by the environment. We call a resource allocation problem static if ? ??? ?? is constant over time and dynamic otherwise. So in our distributed sensor network example, a moving target represents a dynamic problem. Agents can execute their operations at any time, but the success of an operation is determined by the set of tasks that are currently present. The following two de?nitions formalize this interface with the environment.

?? ? ?, § (?? ) = ? ?? ? ?? – ?? ? ? , ? (?? ) = ?? ?? ? § (?? ) All the tasks in ? may not always be present. We use ? ??? ?? ( ?) to denote the
? ?

in some minimal set succeed. More formally, De?nition 2: ?? ? ?, ?? is performed iff ?? ? ?? such that all the operations in ?? succeed. All tasks that satisfy this de?nition are contained in ? ??? ?? . Agents must somehow be informed of the set of current tasks. The noti?cation procedure is outside of this formalism. Thus, the following assumption states that at least one agent is noti?ed that a task is present by the success of one of its operations. (This assumption can be satis?ed in the distributed sensor domain by agents “scanning” for targets by rotating sectors when they are currently not tracking a target.) Noti?cation assumption: ?? ? ?, if ?? ? ? ??? ?? , then ?? ? § (?? ) such that ?×? ?? ? ? ? ??? ?? , ?? ? ?× and ?? succeeds. We now state some de?nitions that will allow us to categorize a given resource allocation problem and analyze its complexity. In many resource allocation problems, tasks of ) available have the property that they require at least agents from a pool? ?? (? agents. That is, the task contains a minimal set for each of the ? combinations. The following de?nition formalizes this notion. ? ? ? ? De?nition 3: ?? ? ?, ?? is task- ? -exact iff ?? has exactly ? minimal sets of size , where ? = § ??? ? . ? ? For example, the task ?? (corresponding to target 1 in Figure 1.b) is task- ? -exact. The following just de?nes the class of resource allocation problems where all tasks satisfy the above de?nition. ? ? , ?, De?nition 4 : ? -exact denotes?the class of resource allocation problems ? ? such that ?? ? ?, ?? is task- ?? -exact for?some ? . ? We ?nd it useful to de?ne a special case of ? -exact resource allocation problems, namely those when ? ?. In other words, the task contains only one minimal set. ? , ?, De?nition 5: ? -exact denotes?the class of resource allocation problems ? ? ? such that ?? ? ?, ?? is task- ??? -exact, where ?? ? § ??? ? . ? ? For example,the task ?? (corresponding to target 2 in Figure 1.b) is task- ? -exact. ? , De?nition 6: Unrestricted denotes the class of resource allocation problems ? , ? with no restrictions on tasks. The following de?nitions refer to relations between tasks. We de?ne two types of con?ict-free to denote tasks that can be performed concurrently. De?nition 7: A resource allocation problem is called strongly con?ict free (SCF) if ?? ?× ? ?, the following statement is true:
– if ??

De?nition 1: ?? ? ? , if ?? is executed and ?? ? ? ??? ?? such that ?? ? § (?? ), then ?? is said to succeed. ? So in our example, if agent ? executes operation ?? and if ?? ? ? ??? ?? , then ? will succeed, otherwise it will fail. Next, a task is performed when all the operations ??

? , then ? ? ?
× ?

?

,

? ?? ,
× ×

?

,

?

?

??(

) +

?

×

??(

)

1.

The SCF condition states that an operation can be required for no more than one task. This implies that we can choose any minimal set for each task and be guaranteed a non-con?icting solution. De?nition 8: A resource allocation problem is called weakly con?ict free (WCF) if ?? ?× ? ?, the following statement is true:
– if ??

? , then ? ? ?
× ?

?

,

? ??
×

×

?

,

?

?

??(

) +

?

×

??(

)

1.

The WCF condition is much weaker in that it implies that there exists a choice of minimal sets from the tasks that are non-con?icting or in other words, there exists at least one solution.

4 Dynamic DCSP
In order to solve general resource allocation problems that conform to our formalized model, we will use distributed constraint satisfaction techniques. Existing approaches to distributed constraint satisfaction fall short for our purposes however because they cannot capture the dynamic aspects of the problem. In dynamic problems, a solution to the resource allocation problem at one time may become obsolete when the underlying tasks have changed. This means that once a solution is obtained, the agents must continuously monitor it for changes and must have a way to express such changes in the problem. In order to address this shortcoming, the following section de?nes the notion of a Dynamic Distributed Constraint Satisfaction Problem (DyDCSP). A Constraint Satisfaction Problem (CSP) is commonly de?ned by a set of variables, each associated with a ?nite domain, and a set of constraints on the values of the variables. A solution is the value assignment for the variables which satis?es all the constraints. A distributed CSP is a CSP in which variables and constraints are distributed among multiple agents. Each variable belongs to an agent. A constraint de?ned only on the variable belonging to a single agent is called a local constraint. In contrast, an external constraint involves variables of different agents. Solving a DCSP requires that agents not only solve their local constraints, but also communicate with other agents to satisfy external constraints. DCSP assumes that the set of constraints are ?xed in advance. This assumption is problematic when we attempt to apply DCSP to domains where features of the environment are not known in advance and must be sensed at run-time. For example, in distributed sensor networks, agents do not know where the targets will appear. This makes it dif?cult to specify the DCSP constraints in advance. Rather, we desire agents to sense the environment and then activate or deactivate constraints depending on the result of the sensing action. We formalize this idea next. We take the de?nition of DCSP one step further by de?ning Dynamic DCSP (DyDCSP). DyDCSP allows constraints to be conditional on some predicate P. More specifically, a dynamic constraint is given by a tuple (P, C), where P is an arbitrary predicate that is continuously evaluated by an agent and C is a familiar constraint in DCSP. When P is true, C must be satis?ed in any DCSP solution. When P is false, C may be violated. An important consequence of dynamic DCSP is that agents no longer terminate when they reach a stable state. They must continue to monitor P, waiting to see if it changes. If its value changes, they may be required to search for a new solution. Note that a solution when P is true is also a solution when P is false, so the deletion of a constraint does not require any extra computation. However, the converse does not hold. When a constraint is added to the problem, agents may be forced to compute a new solution. In this work, we only need to address a restricted form of DyDCSP i.e. it is only necessary that local constraints be dynamic. AWC [8] is a sound and complete algorithm for solving DCSPs. An agent with local and sends this value to agents with whom it has variable , chooses a value ? for external constraints. It then waits for and responds to messages. When the agent receives

a variable value ( = ? ) from another agent, this value is stored in an AgentView. ? ), ( , ? ), ... . Intuitively, the Therefore, an AgentView is a set of pairs ( AgentView stores the current value of non-local variables. A subset of an AgentView is a NoGood if an agent cannot ?nd a value for its local variable that satis?es all conmay ?nd that the set ( ? ), ( , straints. For example, an agent with variable ? ) is a NoGood because, given these values for and , it cannot ?nd a value that satis?es all of its constraints. This means that these value assignments canfor not be part of any solution. In this case, the agent will request that the others change their variable value and a search for a solution continues. To guarantee completeness, a discovered NoGood is stored so that that assignment is not considered in the future. The most straightforward way to attempt to deal with dynamism in DCSP is to consider AWC as a subroutine that is invoked anew everytime a constraint is added. Unfortunately, in many domains such as ours, where the problem is dynamic but does not change drastically, starting from scratch may be prohibitively inef?cient. Another option, and the one that we adopt, is for agents to continue their computation even as local constraints change asynchronously. The potential problem with this approach is that when constraints are removed, a stored NoGood may now become part of a solution. We solve this problem by requiring agents to store their own variable values ?nds that as part of non-empty NoGoods. For example, if an agent with variable ? ), ( , ? ) , a value ? does not satisfy all constraints given the AgentView ( ? ), ( ? ), ( , ? ) as a NoGood. With this modi?cait will store the set ( tion to AWC, NoGoods remain “no good” even as local constraints change. Let us call this modi?ed algorithm Locally-Dynamic AWC (LD-AWC) and the modi?ed NoGoods “LD-NoGoods” in order to distinguish them from the original AWC NoGoods. Lemma I: LD-AWC is sound and complete. The soundness of LD-AWC follows from the soundness of AWC. The completeness of AWC is guaranteed by the recording of NoGoods. A NoGood logically represents a set of assignments that leads to a contradiction. We need to show that this invariant is maintained in LD-NoGoods. An LD-NoGood is a superset of some non-empty AWC NoGood and since every superset of an AWC NoGood is no good, the invariant is true when a LD-NoGood is ?rst recorded. The only problem that remains is the possibility that an LD-NoGood may later become good due to the dynamism of local constraints. A LD-NoGood contains a speci?c value of the local variable that is no good but never contains a local variable exclusively. Therefore, it logically holds information about external constraints only. Since external constraints are not allowed to be dynamic in LD-AWC, LD-NoGoods remain valid even in the face of dynamic local constraints. Thus the completeness of LD-AWC is guaranteed.

5 Solving SCF Problems via DyDCSP
In this section, we state the complexity of SCF resource allocation problems and map our formal model of the resource allocation problem onto DyDCSP. Our goal is to provide a general mapping so that any unrestricted SCF resource allocation problem can be solved in a distributed manner by a set of agents by applying this mapping. Our complexity analysis (not the DyDCSP mapping, but just the complexity analysis) here assumes a static problem. This is because a dynamic resource allocation problem can be cast as solving a sequence of static problems, so a dynamic problem is at

least as hard as a static one. Furthermore, our results are based on a centralized problem solver. We conjecture that distributed problem solving is no easier due to ambiguity, which requires more search. Theorem I: Unrestricted Strongly Con?ict Free resource allocation problems can be solved in time linear in the number of tasks. proof: Greedily choose any minimal set for each task. They are guaranteed not to con?ict by the Strongly Con?ict Free condition. ? We now describe a solution to this subclass of resource allocation problems by mapping onto DyDCSP. Mapping I is motivated by the following idea. The goal in DCSP is for agents to choose values for their variables so all constraints are satis?ed. Similarly, the goal in resource allocation is for the agents to choose operations so all tasks are performed. Therefore, in our ?rst attempt we map variables to agents and has three values of variables to operations of agents. So for example, if an agent operations it can perform, ?? ?? ?? , then the variable corresponding to this agent will have three values in its domain. However, this simple mapping attempt fails due to the dynamic nature of the problem; operations of an agent may not always succeed. Therefore, we de?ne two values for every operation, one for success and the other for failure. In our example, this would result in six values. It turns out that even this mapping is inadequate due to ambiguity. Ambiguity arises when an operation can be required for more than one task. We desire agents to be able to not only choose which operation to perform, but also to choose for which task they will perform the operation. For example in Figure 1.b, Agent A3 is required to active the same sector for both targets 1 and 2. We want A3 to be able to distinguish between the two targets, so that it does not unnecessarily require A2 to activate sector 2 when target 2 is present. So, for each of the values de?ned so far, we will de?ne new values corresponding to each task that an operation may serve. , ? , ? , the corresponding Mapping I: Given a Resource Allocation Problem DyDCSP is de?ned over a set of ? variables, – = ? Ag. We will use the notation ? , ? ,..., ? , one variable for each to interchangeably refer to an agent or its variable.

The domain of each variable is given by: –

?

, Dom(

)=

?

? ??
?

?? x? ??? )x

yes,no .

In this way, we have a value for every combination of operations an agent can perform, a task for which this operation is required, and whether the operation succeeds or fails. For example in Figure 1.b, Agent A3 has two operations (sector 1 and 2) with only one possible task (target) and one operation (sector 0) with two possible tasks (target 1 and 2). This means it would have 8 values in its domain. A word about notation: ?? ? ? , the set of values in ?? x? ??? )x yes will be = ?? *yes denotes that ? ? abbreviated by the term ?? *yes and the assignment ?. Intuitively, the notation is used when an agent detects that ?? *yes such that an operation is succeeding, but it is not known which task is being performed. This analogous to the situation in the distributed sensor network domain where an agent

may detect a target in a sector, but not know its exact location. Finally, when a variable is assigned a value, we assume the corresponding agent is required to execute the corresponding operation. Next, we must constrain agents to assign “yes” values to variables only when an operation has succeeded. However, in dynamic problems, an operation may succeed at some time and fail at another time since tasks are dynamically added and removed from the current set of tasks to be performed. Thus, every variable is constrained by the following dynamic local constraints. – Dynamic Local Constraint 1 (LC1): ?? ? ?, LC1( ) = (P, C), where P: ?? succeeds. ?? *yes C: – Dynamic Local Constraint 2 (LC2): ?? ? ?, LC2( ) = (P, C), where P: ?? does not succeed. C: ?? *yes

?? ? §?? ), we have ?? ? § (?? ), we have

The truth value of P is not known in advance. Agents must execute their operations, and based on the result, locally determine if C needs to be satis?ed. In dynamic problems, where the set of current tasks is changing over time, the truth value of P will change, and hence the corresponding DyDCSP will also be dynamic. We now de?ne the external constraint (EC) between variables of two different agents. EC is a normal static constraint and is always present. – External Constraint: EC( ): (1) (2) = ?? ?? yes ,

?

?? ? ?, ?? ? § (?? ), = ?? ?? yes, and ?? ? ?? , ?? ? ?? , ? ?? ? ??

?

,

The EC constraint requires some explanation. Condition (1) states that an agent has found an operation that succeeds for task ?? . Condition (2) quanti?es the other is one of those agents, the agents whose operations are also required for ?? . If is not required consequent requires it to choose its respective operation for the ?? . If for ?? , condition (2) is false and EC is trivially satis?ed. Finally, note that every pair of and , have two EC constraints between them: one from to and variables to . The conjunction of the two unidirectional constraints can be another from considered one bidirectional constraint. The following theorems state that our mapping can be used to solve any given SCF Resource Allocation Problem. The ?rst theorem states that our DyDCSP always has a solution, and the second theorem states that if agents reach a solution, all current tasks are performed. It is interesting to note that the converse of the second theorem does not hold, i.e. it is possible for agents to be performing all tasks before a solution state is reached. This is due to the fact that when all current tasks are being performed, agents whose operations are not necessary for the current tasks could still be violating constraints. ,? ,? , Theorem II: Given an unrestricted SCF Resource Allocation Problem ? ??? ?? ?, a solution always exists for the DyDCSP obtained from Mapping I.

proof: We proceed by presenting a variable assignment and showing that it is a solution. ? ?? ? ? ??? ?? ?? ? § (?? ) . We will ?rst assign values Let ? , then to variables in , then assign values to variables that are not in . If ?? ? ? ??? ?? ?? ? § (?? ). In our solution, we assign ?? ?? ? ×. If ? , ?? ?? ??. we may choose any ?? ?? ?? ? Dom( ) and assign To show that this assignment is a solution, we ?rst show that it satis?es the EC and , and show that EC( , ) constraint. We arbitrarily choose two variables, ? be given. is satis?ed. We proceed by cases. Let – case 1: Since satis?ed. – case 2:

? ?? ?? ??, condition (1) of EC constraint is false and thus EC is trivially

? then Next, we show that our assignment satis?es the LC constraints. If ?? ?? ? ×, and LC1, regardless of the truth value of P, is clearly not violated. Furthermore, it is the case that ?? succeeds, since ?? is present. Then the precondition ? and ?? ?? ??, it is P of LC2 is not satis?ed and thus LC2 is not present. If the case that ?? is executed and, by de?nition, does not succeed. Then the precondition P of LC1 is not satis?ed and thus LC1 is not present. LC2, regardless of the truth value of P, is clearly not violated. Thus, the LC constraints are satis?ed by all variables. We can conclude that all constraints are satis?ed and our value assignment is a solution to the DyDCSP. ? Theorem III: Given an unrestricted SCF Resource Allocation Problem ,? ,? , ? ??? ?? ? and the DyDCSP obtained from Mapping I, if an assignment of values to variables in the DyDCSP is a solution, then all tasks in ? ??? ?? are performed. proof: Let a solution to the DyDCSP be given. We want to show that all tasks in ? ??? ?? are performed. We proceed by choosing a task ?? ? ? ??? ?? . Since our choice is arbitrary and tasks are strongly con?ict free, if we can show that it is indeed performed, we can conclude that all members of ? ??? ?? are performed. Let ?? ? ? ??? ?? . By the Noti?cation Assumption, some operation ?? , required by ?? will be executed. However, the corresponding agent , will be unsure as to which task it is performing when ?? succeeds. This is due to the fact that ?? may be required for many different tasks. It may randomly choose a task, ?× ? ? ??? ?, and LC1 requires it to assign the value ?? ?× yes. The EC constraint will then require that all other agents , whose operations are required for ?× also execute those operations and

straint is false and thus EC is trivially satis?ed. ? ? – case 3: ?? ?? ? × and ?? ?× ? × in our solution. Let ?? ? ?? , ?? ? ?? . ?× and ?? must be strongly con?ict free since both are in ? ??? ?? . If ?× ?? , then ?? ? ? , ?? ? ?? . So condition (2) of EC( , ) is false and thus EC is trivially is helping perform ?? . satis?ed. If ?× ?? , then EC is satis?ed since

? ? ?? ?? ? × in our solution. Let ?? ? ?? , ?? ? ?? . We know that ?? ? ? ??? ?? and since ? , we conclude that ?? ? ?? . So condition (2) of the EC con-

assign ?? ?× ? ×. We are in solution, so LC2 cannot be present for . Thus, ?? succeeds. Since all operations required for ?× succeed, ?× is performed. By de?nition, ?× ? ? ??? ?? . But since we already know that ?× and ?? have an operation in common, ?? . Therefore, ?? is indeed the Strongly Con?ict Free condition requires that ?× performed. ?

6 Solving WCF problems via DyDCSP ? ? In this section, we state the complexity of ? -exact WCF resource allocation problems
and that of unrestricted WCF resource allocation problems. The following complexity results are based on a centralized problem solver, but as mentioned we conjecture that distributed problem solving is no easier. We also present a second mapping for WCF problems onto DyDCSP (Section 6.1). ? ? Theorem IV: ? -exact WCF resource allocation problems can be solved in ? time linear in the number of tasks. proof: Greedily choose the single minimal set for each task. ? ? Theorem V: ? -exact WCF resource allocation problems can be solved in time polynomial in the number of tasks and operations. ? ? proof: To prove this theorem, we convert a given ? -exact resource allocation problem to a network-?ow problem which is known to be polynomial. See Appendix. Theorem VI: Determining whether an unrestricted resource allocation problem is Weakly Con?ict Free is NP-Complete. proof-sketch: We reduce from 3 coloring problem. For reduction, let an arbitrary instance of 3-color with colors ? ? ? , vertices ? and edges , be given. We construct the resource allocation problem as follows: – For each vertex ? ? ? , add a task ?? to ?. – For each task ?? ? ?, for each color , add a minimal set ?? to ?? . – For each edge ? ? ? , for each color , add an operator ?? ? to ? and add this operator to minimal sets ?? and ?? . . – Assign each operator to a unique agent ?? ? in Figure 2 illustrates the mapping from a 3 node graph to a resource allocation problem. With the mapping above, it is somewhat easy to show that the 3-color problem has a solution if and only if the constructed resource allocation problem is weakly con?ict free. (We preclude a detailed proof due to space limits)
V1 O v1,v2 V2
Ck

Color = {R, G, B}

TV1= {{O , O }, {O , O }, v1,v2 v1,v3 v1,v2 v1,v3 O v1,v3 V3
Ck

R

R

G

G

{OB , OB }} v1,v2 v1,v3 TV2= {{O }, {O }, {O }} v1,v2 v1,v2 v1,v2 TV3= {{O }, {O }, {O }} v1,v3 v1,v3 v1,v3
R G B R G B

Fig. 2. Reduction of graph 3-coloring to Resource Allocation Problems

6.1 Mapping II Our ?rst mapping has allowed us to solve any SCF resource allocation problem. However, when we attempt to solve WCF resource allocation problems with this mapping, it fails because the DyDCSP becomes overconstrained. This is due to the fact that the mapping requires all agents who can possibly help perform a task to do so. In some sense, this results in an overallocation of resources to some tasks. This in turn leaves other tasks without suf?cient resources to be performed. One way to solve this problem is to modify the constraints in the mapping to allow agents to reason about relationships among tasks. However, this requires adding non-binary external constraints to the mapping. This is problematic in a distributed situation because there are no ef?cient algorithms for non-binary distributed CSPs. Instead, create a new mapping that has only binary external constraints. This mapping is similar to the dual of a version of mapping I with non-binary external constraints. This new mapping allocates only minimal resources to each task, allowing WCF problems to be solved. This mapping is described next and proven correct. Here, each agent has a variable for each task in which its operations are included. , ? , ? , the corresponding Mapping II: Given a Resource Allocation Problem DyDCSP is de?ned as follows: – Variables: ?? ? ? ?? ? § ??? ?, create a DyDCSP variable ?? and assign it to agent . – Domain: For each variable ?? , create a value ?? for each minimal set in ?? , plus a “NP” value (not present). The NP value allows agents to avoid assigning resources to tasks that are not present and thus do not need to be performed. Next, we must constrain agents to assign non-NP values to variables only when an operation has succeeded, which indicates the presence of the corresponding task. However, in dynamic problems, an operation may succeed at some time and fail at another time since tasks are dynamically added and removed from the current set of tasks to be performed. Thus, every variable is constrained by the following dynamic local constraints. – Dynamic Local (Non-Binary) Constraint (LC1): ? , ?? ? ??( ), let B = ?? ?? ? ?? . Then let the constraint be de?ned as a non-binary constraint over the variables in B as follows: P: ?? succeeds NP. C: ?? ? B ?? – Dynamic Local Constraint (LC2): ?? ? ?, ?? ? § (?? ), let the constraint be de?ned on ?? as follows: P: ?? does not succeed C: ?? = NP We now de?ne the constraint that de?nes a valid allocation of resources and the external constraints that require agents to agree on a particular allocation.

?? , then the value of – Static Local Constraint (LC3): ?? ?× , if ?? cannot con?ict with the minimal set ?? . NP does not con?ict with anything.



– External Constraint (EC):

? ??

??

We will now prove that Mapping II can also be used to solve any given WCF Resource Allocation Problem. The ?rst theorem shows that our DyDCSP always has a solution, and the second theorem shows that if agents reach a solution, all current tasks are performed. ,? ,? , ? ??? ?? Theorem VII: Given a WCF Resource Allocation Problem ?, there exists a solution to DyDCSP obtained from Mapping II. proof: For all variables corresponding to tasks that are not present, we can assign the value “NP”. This value satis?es all constraints except possibly LC1. But the P condition must be false since the task is not present, so LC1 cannot be violated. We are guaranteed that there is a choice of non-con?icting minimal sets for the remaining tasks (by the WCF condition). We can assign the values corresponding to these minimal sets to those tasks and be assured that LC3 is satis?ed. Since all variable corresponding to a particular task get assigned the same value, the external constraint is satis?ed. So we have a solution to the DyDCSP.? Theorem VIII: Given a WCF Resource Allocation Problem ,? ,? , ? ??? ?? ? and the DyDCSP obtained from Mapping II, if an assignment of values to variables in the DyDCSP is a solution, then all tasks in ? ??? ?? are performed. proof Let a solution to the DyDCSP be given. We want to show that all tasks in ? ??? ?? are performed. We proceed by randomly choosing a task from ? ??? ?? and showing that it is performed. Since we are in a solution state, LC3 allows us to repeat this argument for every task in ? ??? ?? . Let ?? ? ? ??? ?? . By the Noti?cation Assumption, some operation ?? , required by ?? will be executed and (by de?nition) succeed. LC1 requires the corresponding agent , to assign a minimal set, say ?? to the variable ?? . The EC constraint will then require that all other agents , whose operation ?? is in the minimal set ?? , to ?? and execute that operation. LC2 requires that it succeeds. Since all assign ?? operations required for ?? succeed, ?? is performed. ?

7 Experiments in a Real-World Domain
We have successfully applied the DyDCSP approach to the distributed sensor network problem, using the mapping introduced in Section 6. In the last evaluation trials conducted in government labs in August and September 2000, this DyDCSP implementation was successfully tested on four actual hardware sensor nodes (see Figure 1.a), where agents collaboratively tracked a moving target. This target tracking requires addressing noise, communication failures, and other real-world problems; although this was done outside the DyDCSP framework and hence not reported here. The unavailability of the hardware in our lab precludes extensive hardware tests; but instead, a detailed simulator that very faithfully mirrors the hardware has been made available to us. We have done extensive tests using this simulator to further validate the DyDCSP formalization: indeed a single implementation runs on both the hardware and the simulator. One key evaluation criteria for this implementation is how accurately it is able to track targets, e.g., if agents do not switch on overlapping sectors at the right time, the target tracking has poor accuracy. Here, the accuracy of a track is measured in terms of the RMS (root mean square) error in the distance between the real position of a

target and the target’s position as estimated by a team of sensor agents. Domain experts termed the RMS error of upto 3 units as acceptable. Table 1 presents our results from the implementation with the Mapping II in Section 6. Experiments were conducted in different dynamic situations varying the type of resource allocation problem, the number of nodes/targets, and the con?guration. RMS error, message number, and sector change are averaged over the number of involved agents. In the “node number” column, the number in parentheses indicates the number of rows and columns of the grid con?guration where sensor agents are located. For instance, the last row represents the result of the WCF resource allocation problem with 12 sensor nodes (in 3x4 grid) and 4 four targets: the RMS of 3.24 units with average 30 messages and 2 sector changes per node. The results show that our mapping works, and agents are able to accurately track targets, with average RMS around 3 units as the experts require. This proves the usefulness of the DyDCSP approach to this resource allocation problem. Furthermore, scaling up the number of nodes and targets does not degrade the tracking accuracy. Some interesting differences between WCF and SCF arise: WCF resource allocation problems require more number of messages and sector changes than SCF problems. These are due to the fact that, given WCF problems, agents need to reason about possible minimal sets of the current tasks to be performed.
RAP type node number target number avg RMS avg message number avg sector changes WCF/SCF 4 (2x2) 1 2.58 14 0.5 SCF 8 (2x4) 2 3.21 17.08 0.5 SCF 9 (3x3) 2 3.21 21.89 0.2 SCF 16 (4x4) 4 2.58 23.13 0.5 WCF 6 (2x3) 2 2.50 45.17 1.6 WCF 12 (3x4) 4 3.24 30 2.0 Table 1. Results from sensor network domain for dynamic resource allocation problems.

8 Summary
In this paper, we proposed a formalization of distributed resource allocation that is expressive enough to represent both dynamic and distributed aspects of the problem. We de?ne different categories of dif?culties of the problem and present complexity results for them. Table 2 summarizes these complexity results. To address these formalized problems, we de?ne the notion of Dynamic Distributed Constraint Satisfaction Problem (DyDCSP) and present a generalized mapping from distributed resource allocation to DyDCSP. Through both theoretical analysis and experimental veri?cations, we have shown that this approach to dynamic and distributed resource allocation is powerful and unique, and can be applied to real-problems such as the Distributed Sensor Network Domain. Indeed, in the future, our formalization may enable researchers to understand the dif?culty of their resource allocation problem, choose a suitable mapping using DyDCSP, with automatic guarantees for correctness of the solution.

Acknowledgements
This research is sponsored in part by DARPA/ITO under contract number F30602-992-0507, and in part by AFOSR under grant number F49620-01-1-0020.

Table 2. Complexity Classes of Resource Allocation, ? = size of task set ?, ? = size of operation set ?

SCF WCF ??? -exact O(?) O(?) ??? ? -exact O(?) O(?? · ??? ) unrestricted O(?) NP-Complete

References
1. M. Chia, D. Neiman, and V. Lesser. Poaching and distraction in asynchronous agent activities. In ICMAS, 1998. 2. K. Decker and J. Li. Coordinated hospital patient scheduling. In ICMAS, 1998. 3. C. Frei and B. Faltings. Resource allocation in networks using abstraction and constraint satisfaction techniques. In Proc of Constraint Programming, 1999. 4. Hiroaki Kitano. Robocup rescue: A grand challenge for multi-agent systems. In ICMAS, 2000. 5. J. Liu and K. Sycara. Multiagent coordination in tightly coupled task scheduling. In ICMAS, 1996. 6. S. Mittal and B. Falkenhainer. Dynamic constraint satisfaction problems. In AAAI, 1990. 7. Sanders. Ecm challenge problem, http://www.sanders.com/ants/ecm.htm. 2001. 8. M. Yokoo and K. Hirayama. Distributed constraint satisfaction algorithm for complex local problems. In ICMAS, July 1998.

Theorem V: ? -exact WCF resource allocation problems can be solved in time polynomial in the number of tasks and operations. ? ? proof: We can convert a given ? -exact resource allocation problem to a network?ow problem known to be polynomial. Let such a resource allocation problem be given. We ?rst construct a tripartite graph and then convert it to a network-?ow problem. – Create three empty sets of vertices, U, V, and W and an empty edge set E. – For each task ?? ? ?, add a vertex ?? to U. – For each agent ? , add a vertex ? to V. – For each agent , for each operation ?? ? ??? ?, add a vertex ?? to W. – For each agent , for each operation ?? ? ??? ?, add an edge between vertices ? , ?? to E. – For each task ?? , for each operation ?? ? § (?? ), add an edge between vertices ?? , ?? to E. We convert this tripartite graph into a network-?ow graph in the usual way. Add two new vertices, a supersource ×, and supersink ?. Connect × to all vertices in V and assign a max-?ow of 1. For all edges among V, W, and U, assign a max-?ow of 1. Now, connect ? to all vertices in U and for each edge (?? , ?), assign a max-?ow of ? . We now ? have a network ?ow graph with an upper limit on ?ow of ? . We show that the resource allocation problem has a solution if and only if the max? ?ow is equal to ? . ? Let a solution to the resource allocation problem be given. We will now construct ? a ?ow equal to ? . This means, for each edge between vertex ?? in U and ?, we

Appendix

? ?

must assign a ?ow of ? . It is required that the in-?ow to ?? equal ? . Since each edge between W and U has capacity 1, we must choose ? vertices from W that have an edge into ?? and ?ll them to capacity. Let ?? be the task corresponding to vertex ?? , and ?? ? ?? be the minimal set chosen in the given solution. We will assign a ?ow of 1 to all edges (?? ?? ) such that ?? corresponds to the operation ?? that is required in ?? . There are exactly ? of these. Furthermore, since no operation is required for two different tasks, when we assign ?ows through vertices in U, we will never choose ?? again. For vertex ?? such that the edge (?? , ?? ) is ?lled to its capacity, assign a ?ow of 1 to the edge (? , ?? ). Here, when a ?ow is assigned through a vertex ?? , no other ?ow is assigned through ?? ? ??? ? (? ? ) because all operations in ??? ? are mutually exclusive. Therefore, ? ’s out?ow cannot be greater than 1. Finally, the assignment of ?ows from × to V is straightforward. Thus, we will always have a valid ?ow (in?ow=out?ow). Since all edges from U to ? are ?lled to capacity, the max-?ow ? is equal to ? . ? Assume we have a max-?ow equal to ? ? . Then for each vertex ?? in U, there are ? incoming edges ?lled to capacity 1. By construction, the set of vertices in W matched to ?? corresponds to a minimal set in ?? . We choose this minimal set for the solution to the resource allocation problem. For each such edge (?? , ?? ), ?? has an in-capacity of 1, so every other edge out of ?? must be empty. That is, no operation is required by multiple tasks. Furthermore, since outgoing ?ow thorough ? is 1, no more than one operation in ??? ? is required. Therefore, we will not have any con?icts between minimal sets in our solution. ?


更多相关文档:

A Dynamic Distributed Constraint Satisfaction Appro....pdf

A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation - Abstract. In dist...

...A Distributed Constraint Satisfaction Approach_....pdf

Dynamic Distributed Resource Allocation A Distributed Constraint Satisfaction Approach_专业资料。Abstract. In distributed resource allocation a set of agents must ...

...distributed constraint satisfaction problems Dis....pdf

Dynamic constraint weigh... 暂无评价 12页 免费 A best first approach fo....An approach to over-constrained distributed constraint satisfaction problems Distri...

A Constraint Satisfaction Approach to Makespan Sche....pdf

A Dynamic Distributed Co... 暂无评价 16页 免费 A NEW COMBINATORIAL A......A Constraint Satisfaction Approach to Makespan Scheduling In this paper, we ...

...Solving Distributed Constraint Satisfaction Prob....pdf

Kulkarni. A dynamic distributed constraint satisfaction approach to resource allocation. In Proceedings of the International Conference on Principles and Practice ...

Thesis title Conflict Resolution Strategies and The....pdf

A Dynamic Distributed Constraint Satisfaction Approach to Resource Allocation, Proceedings of the International Conference on Principles and Practice of Constraint ...

...Dynamic Distributed Constraint Satisfaction for ....pdf

Extended Abstract Dynamic Distributed Constraint Satisfaction for Resource ...Each variable belongs to an agent. A constraint de?ned only on the ...

...Distributed Constraint Satisfaction Problems_图....pdf

An approach to Symmetry Breaking in Distributed Constraint Satisfaction Problems Roland Martin1 and David A. Burke2 SAF AG, Simulation, Analysis and ...

Distributed constraint satisfaction through constra....pdf

Distributed constraint satisfaction through constraint ...according to a static ( [15]) or dynamic ( ...as well as temporal relations and resource capacity...

A constraint-based approach to diagnosing software ....pdf

as a dynamic partial constraint satisfaction problem...to resolve these names in a distributed fashion....1990. Reasoning about resource constraints in con ...

...A general approach to constraint satisfaction_免....pdf

A stochastic approach to... 暂无评价 2页 免费 A Dynamic Distributed Co.....Divide and concur A general approach to constraint satisfaction Many difficult...

...Distributed Constraint Satisfaction Problems.pdf

Algorithm for Dynamic and Distributed Constraint Satisfaction Problems_专业资料。...In a binary CSP each constraint Cij ∈ C is associated to a binary ...

...Solving Distributed Constraint Satisfaction Prob....pdf

(1998) 4. Modi, P., Jung, H., Tambe, M., Shen, W., Kulkarni, S.: A dynamic distributed constraint satisfaction approach to resource allocation. ...

A Discrete and Dynamic Approach to ApplicationOpera....pdf

Such applications as desktop video-over-IP and distributed virtual A Discrete and Dynamic Approach to Application/Operating System QoS Resource Management Scott...

...Approach to Cooperative, Distributed Problem Sol....pdf

A Cooperative Mediation-Based Protocol for Dynamic, Distributed Resource ...“Using Cooperative Mediation to Solve Distributed Constraint Satisfaction ...

1 A Discrete and Dynamic Approach to ApplicationOpe....pdf

A Discrete and Dynamic Approach to Application/Operating System QoS Resource ...Such applications as desktop video-over-IP and distributed virtual cubicles ...

A constraint satisfaction framework for managing mi....pdf

A constraint satisfaction framework for managing ...to ever be as dynamic and exible as human-...We comment brie y on how to approach the ...

...Real-Time Systems with Dynamic Constraint Progra....pdf

A Dynamic File Allocatio... 暂无评价 6页 免费 ...of such complex distributed applications is to de...it is a dif?cult constraint satisfaction problem....

...Advances in Dynamic, Distributed Constraint Opti....pdf

Recent Advances in Dynamic, Distributed Constraint ...cally, constraint satisfaction/optimization is a ...Examples include planning, scheduling, resource ...

On the feasibility of distributed constraint satisfaction_....pdf

belongs to a class of Constraint Satisfaction Problems CSPs that present ...A Dynamic Distributed ... 暂无评价 16页 免费 On Communication in So......

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com