برنامه ریزی تولید چندمنظوره چندعاملی توزیع شده و چارچوب برنامه ریزی برای روبات های تلفن همراه

Inspired by the new achievements in mobile robotics having as a result mobile robots able to execute different production tasks, we consider a factory producing a set of distinct products via or with the additional help of mobile robots. This particularly flexible layout requires the definition and the solution of a complex planning and scheduling problem. In order to minimize production costs, dynamic determination of the number of robots for each production task and the individual robot allocation are needed. We propose a solution in terms of a two-level decentralized Multi-Agent System (MAS) framework: at the first, production planning level, agents are tasks which compete for robots (resources at this level); at the second, scheduling level, agents are robots which reallocate themselves among different tasks to satisfy the requests coming from the first level. An iterative auction based negotiation protocol is used at the first level while the second level solves a Multi-Robot Task Allocation (MRTA) problem through a distributed version of the Hungarian Method. A comparison of the results with a centralized approach is presented.

An external demand of a manufacturing system is generally a fluctuating stochastic process, usually known with a satisfactory accuracy only over a limited time horizon ahead. This introduces, at the strategic level, a high degree of uncertainty in the design of a production system and a supply chain where critical decisions must be taken based on aggregate and approximate information (see, e.g., Mun, 2002). In traditional shop-floor planning, establishing a production facility requires the selection of static production machines and robot manipulators which would be suitable for long term production plans. With the advances in the development of mobile production resources, now it is possible for many products, once manufactured only by large production machines permanently tied to single locations, to be manufactured with smaller, mobile robots. One of the first such robots was presented in July 2010 by robotic producer Kuka (Bischoff et al., 2010). The shop floor layout with mobile robots makes the strategic decisions less critical with respect to the ones associated to the design of a plant where machines (i.e., production resources) are located on static positions. A dynamic layout represents in fact a less constrained facility where design decisions are postponed to the operative level and become reversible options. Furthermore, it is more effective in responding to a fluctuating external demand and can be considered, for this reason, in the same vein as other solutions adopted through the years in the manufacturing domain for the same purpose, like, among others, Flexible Manufacturing Systems (e.g., Huang & Chen, 1986), Group Technology (see, e.g., Selim, Askin, & Vakharia, 1998), Holonic Manufacturing (see, e.g., Christensen, 1994), and Agile Production Systems (see, e.g., Dugnay, Landry, & Pasin, 1997). The high degree of flexibility achieved by the proposed dynamic multi-robot layout leads to a more complex operation management which may render centralized architectures unviable. Centralized architectures in such complex environments are often impractical because of computational and communication bottleneck and the vulnerability of system failure. On the other hand, a bottom-up multi-agent modular architecture distributes computational resources and capabilities among the agents and does not suffer from the “critical point of failure” problem associated with centralized systems (see, e.g., Wooldridge, 2002). Further advantages of a decentralized multi-agent approach are modularity, decentralized knowledge bases, fault-tolerance, redundancy and extendibility, in the sense that new robots can be added to the original system without any change in the system architecture (see, e.g., Lueth & Laengle, 1994). For all the above reasons and because mobile robots are autonomous entities with limited vision and communication capacities, in this paper we propose a decentralized two-level Multi-Agent System (MAS) framework for the case where the production is executed exclusively or with the additional help of mobile robots, as shown, e.g., by Helms et al., 2002 and Tan et al., 2009. On the first, production planning level, tasks compete for the mobile resources (robots) required for their execution. Assuming that the planning time horizon is subdivided into a finite number of time periods, the objective of the production planning level is the determination of the number of the robots to be assigned in each time period to the tasks. This is done in order to minimize the total production cost for each task (with the products’ demand known over all the time periods in the given time horizon). The resulting problem is a multiple decision maker multi-item dynamic lot-sizing problem with limited production capacity (e.g., see Jans & Degraeve, 2008). The problem is NP-hard since it can be shown to generalize the very special case with single-decision maker, single-item, zero inventory holding cost, convex production cost function, unit set-up cost, and no production capacity, that has been proved to be NP-hard by Florian, Lenstra, and Rinnooy Kan (1980). Since the problem at production planning level is NP-hard this level of the MAS framework is coupled with a heuristic iterative auction based negotiation protocol to coordinate the agents’ decisions (see, e.g.: Kutanoglu and Wu, 2006, Roundy et al., 1991 and Schneider et al., 2005). The resource prices, needed for the iterative auction based protocol, are updated using a strategy inspired by the subgradient technique used in the Lagrangian relaxation approach (see, e.g., Barahona and Anbil, 2000 and Chen et al., 1998). Given the number of robots assigned to the tasks in each time period according to the decisions made at the first, planning level, on the second, scheduling level, the objective is to minimize the total distance covered by the robots in the reallocation between consecutive periods. Therefore, a Multi-Robot Task Allocation (MRTA) problem is solved for each period. The objective of the MRTA problem is to find the assignment of n robots to a set of n tasks (target positions) based on the optimization of some global objective function (see, e.g., Gerkey & Mataric, 2003). We assume that the decision making environment for this level is decentralized as well, with as many decision makers (agents) as there are the robots in the system. In particular, we assume robots to be collaborative, homogeneous, arranged in regular networks and relying on local communication only between neighboring robots. We use a distributed version of the Hungarian Method for this allocation problem, a distributed combinatorial optimization algorithm which solves the assignment problem in strongly polynomial time (Giordani, Lujak, & Martinelli, 2010). Note that the problem definition and the proposed modeling framework are general enough so that the production planning and scheduling problem and the solution model can be applied also to other types of mobile manufacturing resources and production operators. We experiment the proposed model considering a fluctuating demand modeled through an ARMA process. To measure the effectiveness of the approach, the social welfare (see, e.g., Chevaleyre et al., 2006) of the task agents in the decentralized scenario is compared with the performance obtained through a centralized solution. Preliminary results regarding the first level of the proposed framework have been presented by Giordani, Lujak, and Martinelli (2009) where the problem addressed on the second level (the robot movement) was not considered. The integrated solution of the two levels is a viable solution for the incorporation of mobile robots on the shop-floor and provides indeed an interesting insight into the problem. In particular, we show that the decentralized approach of the first level gives comparable results to the centralized one while the required total movement distance of the robots’ reallocation is in general inferior. The remainder of the paper is organized as follows. We introduce related work and review some of the economic models used in MAS negotiation for resource allocation in Section 2. In Section 3, the decentralized production scheduling problem is presented. The two-level solution approach is given in Section 4. In Section 5, we present the simulation results. We close the paper with the conclusions in Section 6.

In this paper, a dynamic factory layout with a set of mobile production resources (e.g. robots) carrying out the production, has been proposed. Notice, however, that the latter can also be used to increment the production capacity of already existing machines in the traditional factories. In respect to a classical layout where the production locations are placed on static positions, a less constrained facility is obtained, which allows to postpone critical design decisions to the operative level and makes the plant more capable of responding to a fluctuating external demand. The proposed solution can be considered as an extension of traditional factories since every control policy implemented in plants with a static layout can be applied in the dynamic factory proposed in this paper, while the viceversa is not true. This extension is at the price of a more complex scheduling problem, involving, for each period of the planning time horizon, the determination of the robots’ positions in order to minimize all the production costs. Owing to this complexity, and/or also for the inherent decentralized structure of the system, a two-level decentralized multi-agent system production scheduling architecture was proposed: at the first level the agents are the tasks which compete for the robots, and at the second level the agents are the robots which reallocate themselves among different tasks to satisfy the requests coming from the first level. An iterative auction based negotiation protocol was used at the first level while the second level resolves a Multi-Robot Task Allocation problem through a distributed version of the Hungarian Method. The advantages of the decentralized architecture with respect to the centralized one were discussed in the paper and include robustness and efficiency (notice that the decentralized approach can be in some cases the only viable solution for the structural organization of the system). From the simulation results it can be observed, however, that the lack of information associated with the decentralized solution implies larger production costs, with respect to the centralized approach when the system has a strict number of robots necessary to carry out requested production: in this case, in fact, the centralized approach is characterized by a much higher robot displacement distance with respect to the decentralized solution; the latter tending to under-utilize the production resources and representing a sub-optimal control policy. Moreover, the proposed dynamic layout (even if sub-optimally controlled) shows a significant superiority with respect to a static plant, in particular if the fluctuation of the demand is characterized by low frequency components or by a drift in the average demand: in these cases, in fact, the strategic static sizing of the plant (i.e. the decision on the number of machines which must be dedicated to a particular product) may result completely inappropriate for long time periods, while a dynamic solution with mobile production robots adequately adapts their roles and positions in the plant to track the perturbations.