This paper proposes a distributed solution approach to a certain class of dynamic resource allocation problems and develops a dynamic programming-based multiagent decision-making, learning, and communication mechanism. In the class of dynamic resource allocation problems we consider, a set of reusable resources of different types has to be assigned to tasks that arrive randomly over time. The assignment of a resource to a task removes the task from the system, modifies the state of the resource, and generates a contribution. We build a decision-making scheme where the decisions regarding the resources in different sets of states are made by different agents. We explain how to coordinate the actions of different agents using nonlinear functional approximations, and show that in a distributed setting, nonlinear approximations produce sequences of min-cost network flow problems that naturally yield integer solutions. We also experimentally compare the performances of the centralized and distributed solution strategies. M onolithic solution approaches to optimization problems arising in the context of complex systems are generally not feasible. Distributed solution techniques divide these problems into loosely coupled subproblems and solve them independently by using an inter-subproblem communication mechanism that ensures that the independent solutions of the subproblems will yield a high-quality solution. In this paper, we present a distributed solution approach to dynamic resource allocation problems. Our approach divides the problem into subproblems and relies on multiple agents to solve them. We develop a dynamic programming-based communication mechanism that helps each agent to estimate the impact of their solutions on the other agents. Central to our approach is the use of nonlinear functional approximations to handle the coordination. Dynamic resource allocation problems considered in this paper involve the assignment of a set of discrete and reusable resources to tasks that occur randomly over time. Each resource in the system has a state and a type associated with it, which together determine the contribution of assigning a resource to a task. The arrival process of the tasks is known only through a probability distribution. The assignment of a resource to a task produces a reward, removes the task from the system, and modifies the state of the resource. Such problems arise in many fields, such as dynamic crew scheduling (staff members are the resources, flights are the tasks, location and hours on duty of the staff member are the resource state), fleet management (vehicles are the resources, loads are the tasks, vehicle location is the resource state), machine assignment (machines are the resources, jobs are the tasks, machine wear is the resource state), and emergency equipment/personnel management (ambulances/doctors are the resources, patients are the tasks, location/hours on duty is the resource state). Multiple resource states and the indivisibility of the resources differentiate our problem class from other resource allocation problems where a single divisible resource (for example, computing capacity) has to be allocated among different tasks. The latter type of problems occur frequently in distributed computing systems (see Kurose and Simha 1989, Waldspurger et al. 1992). We were confronted with this problem in the context of managing fleets of vehicles to serve loads that occur over time at a set of locations. In real-world operations, usually there is one decision agent for each location responsible for managing the vehicles at that location, and when making its decisions, the decision agent pays very little attention to what is happening in other locations. We devise an efficient way of assessing the impact of the decisions made at a certain location on the decisions made at the other locations and at future time periods. In this way, the decision makers in different locations can work collectively to achieve the maximum expected reward over all time periods, and we obtain a distributed solution method where the division of subproblems perfectly matches the operational decisionmaking structure. To achieve this collaboration, the agents that solve different subproblems assess and learn the impact of their actions on the other parts of the system through nonlinear functional approximations. Roughly speaking, each agent makes its decisions to maximize the contribution of its actions and the impact of its actions on the rest of the system. However, a communication mechanism built on nonlinear functional approximations brings special challenges in coordinating the actions of different agents. Consider Figure 1 , where we illustrate the interaction of the agents over time. At the current time period t, agents a, b, and c solve their subproblems to maximize the contribution of their own decisions and the impact of their decisions on the rest of the system. Assume that these agents can potentially impact agent b at time period t + by sending resources from the subproblems that they solve at time period t to the subproblem that agent b is going to solve at time period t + , and this impact is approximated by a nonlinear function of the total number of resources in the future subproblem. Clearly, the impact of a particular agent on the future subproblem depends on the number of resources sent to the future subproblem by the other agents. Therefore, the agents cannot concentrate only on their own subproblems when assessing the impact of their decisions on the rest of the system. We note that if the approximations were linear, such a problem would not occur. In this paper, we introduce a communication mechanism built on nonlinear functional approximations, which allows each agent to concentrate on its own subproblem. We facilitate the learning of the agents by updating the parameters of the functional approximations adaptively as each agent solves the subproblems under its control. Motivated by the fact that the expected marginal contribution (profit, revenue, reward, etc.) from an incremental resource decreases as the number of available resources increases, we use concave, piecewise-linear approximations in this paper. Hence, the parameters that characterize these approximations are their slopes over different parts of their domains. To update the parameters of the functional approximations, we use the dual solution information from the subproblems, which roughly tells us the marginal worth of a resource. Thus, the primal solution is utilized to determine which actions to take, and the dual solution is utilized to update the functional approximations and contrive an adaptive learning mechanism. An important question is how well the agents perform after having been trained for a certain period of time. To answer this question, we carry on the learning process (i.e., updating the approximations) for a certain amount of time. After this learning period, we fix the parameters of the approximations and test how well the system performs with the fixed set of approximations. Our work falls into the area of distributed artificial intelligence, which has traditionally been divided into two subdisciplines (see Bond and Gasser 1988 , Gasser and Huhns 1989 , O'Hare and Jennings 1996 , Moulin and Chaib-Draa 1996 for a general overview of the area). The first discipline, distributed problem solving, focuses on information division and management when a large problem is decomposed into smaller subproblems to obtain the optimal solution by solving independent subproblems (see Corkill 1982 , Durfee et al. 1987 , Pope et al. 1992 for representative approaches). The second discipline, multiagent systems, deals with the behavior management of independent entities called agents (see Stone and Veloso 2000 for a recent survey). Our approach is a distributed problemsolving method. However, this paper has ties with both disciplines. Motivated both by the natural division of information among the decision makers in the real world and the need for computational tractability, we decompose a complex problem into smaller subproblems. Once we obtain the functional approximations by the distributed solution procedure, the evolution of the system has multiagent characteristics, as each decision agent now makes its decisions independently and the behaviors of the agents are coordinated with the functional approximations. An important part of our approach is a reinforcement learning mechanism where the agent acquires knowledge from its past experiences (i.e., the dual solution of all the subproblems solved by the agent). The learning of each agent is captured This paper builds on Topaloglu and Powell (2002) and Godfrey and Powell (2002) , who formulate our dynamic resource allocation problem as a dynamic program and propose using separable, nonlinear (specifically piecewiselinear, concave) approximations of the value function, decomposing the problem into time stages. Here we take the dynamic programming formulation of Topaloglu and Powell (2002) , decompose each time stage of this formulation into even smaller subproblems, and distribute them to multiple agents. In the fleet management example that was the motivating application for this work, the classical dynamic programming formulation solves one subproblem for each time period. Here, we decompose each time period so that we solve one subproblem for each time period and each location. For this reason, we call this decomposition scheme spatial decomposition. Adaptive learning using dynamic programming approximations is a research area that has been very active within the past two decades. The previous research can be classified into two groups according to how the value function approximations are represented. The first group represents the approximations as simple table look-up functions. This amounts to maintaining a table containing the approximate value function values V s s ∈ or the approximate Q-factor values Q s a s ∈ a ∈ , where and are, respectively, the sets of possible states and actions. There exist a number of techniques to generate the values in these tables using trajectory samples of the system, s 1 a 1 s 2 a 2 , where s k and a k are the kth state and action visited. For example, temporal difference learning methods (Sutton 1984 (Sutton , 1988  , where c s k s k+1 is the immediate reward obtained by the transition from state s k to s k+1 and is a proper step size. Note that the term in parentheses is the new estimate of V s k , and we merge the old and the new estimates using a simple smoothing operation. Similarly, Q-learning (Watkins 1989, Watkins and Dayan 1992) updates the approximate Q-values as Q s k a k ← 1 − Q s k a k + c s k s k+1 + max a∈ Q s k+1 a . We note that the advantage of these methods is that they do not require the transition probabilities, which may be hard to obtain for practical problems. However, maintaining the tables may become cumbersome if or includes many elements. The second body of work seeks more compact representations by using parameterized functional approximations. A family of functions V · r r ∈ n , parameterized by r, is used as an approximation to the true value function, and the challenge is to find a value of r such that V · r is a "good" approximation. This representation has to maintain the values of only n parameters, rather than or parameters as in table look-up methods. Offline, least-squares methods can be used to fit the approximations to the value functions estimated using sampled trajectories (Bertsekas and Tsitsiklis 1996) . Alternatively, using temporal differences, we can estimate the parameters iteratively (Dayan 1992 and Tsitsiklis and Van Roy 1997 present convergence results in online settings). When V · r is linear in r, a good value of r can be obtained by solving a large linear program without using trajectory samples. These linear programs have n variables and constraints, and therefore require some approximation procedure (Schweitzer and Seidmann 1985, de Farias and Van Roy 2003) . Our approach is more akin to the parameterized approximation strategies. We utilize very compact representations of the value function approximations. For a problem with 200 resources and 100 state-type pairs, a table look-up method needs to store about 200 100 values, whereas our approach needs to store about 100 ×200 slope values. Also, our approach is sampling based and does not require the knowledge of transition probabilities. The final and the most novel aspect of our approach is revealed when we finally have a good approximation V · r and we want to use it to make a decision. This requires solving a problem that maximizes the sum of the immediate reward and the value function approximation. However, if the approximation does not have a special structure, solving this problem may require enumeration over all possible solutions. We are interested in large-scale applications, such as fleet management, where such enumeration is infeasible. The separable, piecewise-linear, concave approximations we choose help us to convert these problems into min-cost network flow problems, where integer solutions are obtained very fast. In this paper, we make the following research contributions: (1) We present a distributed solution approach to dynamic resource allocation problems that closely captures the multiagent decision-making structure of real-world operations, and develop a dynamic programming-based learning mechanism. (2) We show how to coordinate different subproblems to obtain high-quality solutions by using computationally tractable piecewise-linear, concave approximations of the value function. (3) We prove that the problem reduces to solving sequences of simple mincost network flow problems. (4) We illustrate the extension of our methodology to handle multiperiod resource transformation times and derive a key result that significantly accelerates the performance of our solution scheme. (5) We numerically compare our distributed solution method with a centralized method in Topaloglu and Powell (2002) and present what we gain or lose by decomposition. In §1, we define the problem, briefly describe the dynamic programming formulation due to Topaloglu and Powell (2002) , and present our agent-based dynamic programming formulation. Section 2 describes the basic idea of approximating the value function and establishes that the approximate subproblems under spatial decomposition are min-cost network flow problems when we use separable, piecewise-linear, concave value function approximations. Section 3 summarizes how to update the value function approximations. Section 4 presents a series of numerical results on deterministic and stochastic experiments that test the solution quality of the new distributed solution methodology. Section 5 presents conclusions.
This was the choice of the authors in REF , where they model the problem of resource allocation related to fleet management.
A Distributed Decision-Making Structure for Dynamic Resource Allocation Using Nonlinear Functional Approximations
Oper. Res.
Oper. Res.
Computer Science