A layered approach to learning coordination knowledge in multiagent environments

Multiagent learning involves acquisition of cooperative behavior among intelligent agents in order to satisfy the joint goals. Reinforcement Learning (RL) is a promising unsupervised machine learning technique inspired from the earlier studies in animal learning. In this paper, we propose a new RL technique called the Two Level Reinforcement Learning with Communication (2LRL) method to provide cooperative action selection in a multiagent environment. In 2LRL, learning takes place in two hierarchical levels; in the first level agents learn to select their target and then they select the action directed to their target in the second level. The agents communicate their perception to their neighbors and use the communication information in their decision-making. We applied 2LRL method in a hunter-prey environment and observed a satisfactory cooperative behavior. Guray Erus received the B.S. degree in computer engineering in 1999, and the M.S. degree in cognitive sciences, in 2002, from Middle East Technical University (METU), Ankara, Turkey. He is currently a teaching and research assistant in Rene“ Descartes University, Paris, France, where he prepares a doctoral dissertation on object detection on satellite images, as a member of the intelligent perception systems group (SIP-CRIP5). His research interests include multi-agent systems and image understanding. Faruk Polat is a professor in the Department of Computer Engineering of Middle East Technical University, Ankara, Turkey. He received his B.Sc. in computer engineering from the Middle East Technical University, Ankara, in 1987 and his M.S. and Ph.D. degrees in computer engineering from Bilkent University, Ankara, in 1989 and 1993, respectively. He conducted research as a visiting NATO science scholar at Computer Science Department of University of Minnesota, Minneapolis in 1992–93. His research interests include artificial intelligence, multi-agent systems and object oriented data models.     

An evolutionary approach to multiprocessor scheduling of dependent tasks

The scheduling of application tasks is a problem that occurs in all multiprocessor systems. This problem has been shown to be NP-hard if the tasks are not independent but are interrelated by mutual exclusion and precedence constraints.

This paper presents an approach for pre-runtime scheduling of periodic tasks on multiple processors for a real-time system that must meet hard deadlines. The tasks can be related to each other by mutual exclusion and precedence forming an acyclic graph. The proposed scheduler is based on genetic algorithms, which relieves the user from knowing how to construct a solution. Consequently, the paper focuses on the problem encoding, i.e., the representation of the problem by genes and chromosomes, and the derivation of an appropriate fitness function. The main benefit of the approach is that it is scalable to any number of processors and can easily be extended to incorporate further requirements.     

Opportunities for multiagent systems and multiagent reinforcement learning in traffic control

The increasing demand for mobility in our society poses various challenges to traffic engineering, computer science in general, and artificial intelligence and multiagent systems in particular. As it is often the case, it is not possible to provide additional capacity, so that a more efficient use of the available transportation infrastructure is necessary. This relates closely to multiagent systems as many problems in traffic management and control are inherently distributed. Also, many actors in a transportation system fit very well the concept of autonomous agents: the driver, the pedestrian, the traffic expert; in some cases, also the intersection and the traffic signal controller can be regarded as an autonomous agent. However, the “agentification” of a transportation system is associated with some challenging issues: the number of agents is high, typically agents are highly adaptive, they react to changes in the environment at individual level but cause an unpredictable collective pattern, and act in a highly coupled environment. Therefore, this domain poses many challenges for standard techniques from multiagent systems such as coordination and learning. This paper has two main objectives: (i) to present problems, methods, approaches and practices in traffic engineering (especially regarding traffic signal control); and (ii) to highlight open problems and challenges so that future research in multiagent systems can address them.     

A modern approach to multiagent development

Multiagent systems (MAS) development frameworks aim at facilitating the development and administration of agent-based applications. Currently relevant tools, such as JADE, offer huge possibilities but they are generally linked to a specific technology (commonly Java). This fact may limit some application domains when deploying MAS, such as low efficiency or programming language restrictions. To contribute to the evolution of multiagent development tools and to overcome these constraints, we introduce a multiagent platform based on the FIPA standards and built on top of a modern object-oriented middleware. Experimental results prove the scalability and the short response-time of the proposal and justify the design and development of modern tools to contribute the multiagent technology.     

Coordinating patient preferences through automated negotiation: A multiagent systems model for diagnostic services scheduling

This paper presents a multiagent systems model for patient diagnostic services scheduling. We assume a decentralized environment in which patients are modeled as self-interested agents who behave strategically to advance their own benefits rather than the system wide performance. The objective is to improve the utilization of diagnostic imaging resources by coordinating patient individual preferences through automated negotiation. The negotiation process consists of two stages, namely patient selection and preference scheduling. The contract-net protocol and simulated annealing based meta-heuristics are used to design negotiation protocols at the two stages respectively. In terms of game theoretic properties, we show that the proposed protocols are individually rational and incentive compatible. The performance of the preference scheduling protocol is evaluated by a computational study. The average percentage gap analysis of various configurations of the protocol shows that the results obtained from the protocol are close to the optimal ones. In addition, we present the algorithmic properties of the preference scheduling protocol through the validation of a set of eight hypotheses.     

Distributed constraint optimization with MULBS: A case study on collaborative meeting scheduling

This paper introduces MULBS, a new DCOP (distributed constraint optimization problem) algorithm and also presents a DCOP formulation for scheduling of distributed meetings in collaborative environments. Scheduling in CSCWD can be seen as a DCOP where variables represent time slots and values are resources of a production system (machines, raw-materials, hardware components, etc.) or management system (meetings, project tasks, human resources, money, etc). Therefore, a DCOP algorithm must find a set of variable assignments that maximize an objective function taking constraints into account. However, it is well known that such problems are NP-complete and that more research must be done to obtain feasible and reliable computational approaches. Thus, DCOP emerges as a very promising technique: the search space is decomposed into smaller spaces and agents solve local problems, collaborating in order to achieve a global solution. We show with empirical experiments that MULBS outperforms some of the state-of-the-art algorithms for DCOP, guaranteeing high quality solutions using less computational resources for the distributed meeting scheduling task.     

Analyzing and visualizing multiagent rewards in dynamic and stochastic domains

The ability to analyze the effectiveness of agent reward structures is critical to the successful design of multiagent learning algorithms. Though final system performance is the best indicator of the suitability of a given reward structure, it is often preferable to analyze the reward properties that lead to good system behavior (i.e., properties promoting coordination among the agents and providing agents with strong signal to noise ratios). This step is particularly helpful in continuous, dynamic, stochastic domains ill-suited to simple table backup schemes commonly used in TD(λ)/Q-learning where the effectiveness of the reward structure is difficult to distinguish from the effectiveness of the chosen learning algorithm. In this paper, we present a new reward evaluation method that provides a visualization of the tradeoff between the level of coordination among the agents and the difficulty of the learning problem each agent faces. This method is independent of the learning algorithm and is only a function of the problem domain and the agents’ reward structure. We use this reward property visualization method to determine an effective reward without performing extensive simulations. We then test this method in both a static and a dynamic multi-rover learning domain where the agents have continuous state spaces and take noisy actions (e.g., the agents’ movement decisions are not always carried out properly). Our results show that in the more difficult dynamic domain, the reward efficiency visualization method provides a two order of magnitude speedup in selecting good rewards, compared to running a full simulation. In addition, this method facilitates the design and analysis of new rewards tailored to the observational limitations of the domain, providing rewards that combine the best properties of traditional rewards.     

Consensus seeking in multiagent cooperative control systems with bounded control input

Consensus algorithms in multiagent cooperative control systems with bounded control input are studied in this paper.Consensus algorithms are considered for the single-integrator dynamics and double-integrator dynamics under different communication interaction topologies,and show that consensus is reached asymptotically using the algorithm proposed in this paper for the single-integrator dynamics if the undirected interaction graph is connected,and consensus is reached asymptotically if the directed interaction graph is strongly connected,respectively.In addition,the paper further shows that consensus is reached asymptotically using the algorithm proposed for the double-integrator dynamics if the directed interaction graph is strongly connected.The effectiveness of these algorithms is demonstrated through simulations.     

A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling

Distributed Scheduling (DS) problems have attracted attention by researchers in recent years. DS problems in multi-factory production are much more complicated than classical scheduling problems because they involve not only the scheduling problems in a single factory, but also the problems in the higher level, which is: how to allocate the jobs to suitable factories. It mainly focuses on solving two issues simultaneously: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production schedules in each factory. Its objective is to maximize system efficiency by finding an optimal plan for a better collaboration among various processes. However, in many papers, machine maintenance has usually been ignored during the production scheduling. In reality, every machine requires maintenance, which will directly influence the machine's availability, and consequently the planned production schedule. The objective of this paper is to propose a modified genetic algorithm approach to deal with those DS models with maintenance consideration, aiming to minimize the makespan of the jobs. Its optimization performance has been compared with other existing approaches to demonstrate its reliability. This paper also tests the influence of the relationship between the maintenance repairing time and the machine age to the performance of scheduling of maintenance during DS in the studied models.     

A familiarity-based trust model for effective selection of sellers in multiagent e-commerce systems

In electronic marketplaces, trust is modeled, for instance, in order to allow buying agents to make effective selection of selling agents. Familiarity is often considered to be an important factor in determining the level of trust. In previous research, familiarity between two agents has been simply assumed to be the similarity between them. We propose an improved familiarity measurement based on the exploration of factors that affect a human’s feelings of familiarity. We also carry out experiments to show that the trust model with our improved familiarity measurement is more effective and more stable.     

An algorithm reminiscent of euclidean-gcd for computing a function related to pinwheel scheduling

The functionLM, which arises in the pinwheel scheduling problem, was previously known to be computable in polynomial time. In this paper we present a practical algorithm to computeLM that runs in linear time.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

An integrated selection and scheduling for disjunctive network problems

In network optimization problems, the application of conventional integrated selection and scheduling solution methods becomes complicated when the size of the problems, such as real life project management, assembly and transportation problems, get bigger. These kinds of problems often consist of disjunctive networks with alternative subgraphs. Traditionally, in order to handle alternative subgraphs in a disjunctive network, researchers consider first selection and then solution (scheduling) of the problem sequentially. However, the use of traditional approaches result in the loss of the problem structural integrity. When the approach losses its integrated structure, the network problem also losses its integrity. Therefore, these two issues, i.e. selection and scheduling, have to be considered together. To provide a new approach to maintain the problem integrity, we proposed an integrated genetic algorithm for solving this selection and scheduling problems together using a multi-stage decision approach. In this study, two newly defined problems with different disjunctive networks and different characteristics, i.e. resource constrained multiple project scheduling (rc-mPSP) models with alternative projects and variable activity times, and U-shaped assembly line balancing (uALB) models with alternative subassemblies, have been solved using the proposed solution approach to highlight the applicability and performance of the proposed solution approach.     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

基于遗传模拟退火算法的制造网格资源调度策略

为有效解决制造网格中资源调度问题,提出了多目标调度优化模型。并根据用户的要求,采用AHP算法确定各目标权重;联系到资源调度问题的特性,设计了基于遗传模拟退火算法的调度策略,最后给出一个典型实例,验证方法的有效性。     

An evolutionary approach to cancer chemotherapy scheduling

In this paper, we investigate the employment of evolutionary algorithms as a search mechanism in a decision support system for designing chemotherapy schedules. Chemotherapy involves using powerful anti-cancer drugs to help eliminate cancerous cells and cure the condition. It is given in cycles of treatment alternating with rest periods to allow the body to recover from toxic side-effects. The number and duration of these cycles would depend on many factors, and the oncologist would schedule a treatment for each patient’s condition. The design of a chemotherapy schedule can be formulated as an optimal control problem; using an underlying mathematical model of tumour growth (that considers interactions with the immune system and multiple applications of a cycle-phase-specific drug), the objective is to find effective drug schedules that help eradicate the tumour while maintaining the patient health’s above an acceptable level. A detailed study on the effects of different objective functions, in the quality and diversity of the solutions, was performed. A term that keeps at a minimum the tumour levels throughout the course of treatment was found to produce more regular treatments, at the expense of imposing a higher strain on the patient’s health, and reducing the diversity of the solutions. Moreover, when the number of cycles was incorporated in the problem encoding, and a parsimony pressure added to the objective function, shorter treatments were obtained than those initially found by trial and error.

An agent-based approach to solve dynamic meeting scheduling problems with preferences

Multi-agent systems are widely used to address large-scale distributed combinatorial applications in the real world. One such application is meeting scheduling (MS), which is defined by a variety of features. The MS problem is naturally distributed and especially subject to many alterations. In addition, this problem is characterized by the presence of users’ preferences that turn it into a search for an optimal rather than a feasible solution. However, in real-world applications users usually have conflicting preferences, which makes the solving process an NP-hard problem. Most research efforts in the literature, adopting agent-based technologies, tackle the MS problem as a static problem. They often share some common properties: allowing the relaxation of any user's time restriction, not dealing with achieving any level of consistency among meetings to enhance the efficiency of the solving process, not tackling the consequences of the dynamic environment, and especially not addressing the real difficulty of distributed systems which is the complexity of message passing operations.In an attempt to facilitate and streamline the process of scheduling meetings in any organization, the main contribution of this work is a new scalable agent-based approach for any dynamic MS problem (that we called MSRAC, for Meeting Scheduling with Reinforcement of Arc Consistency). In this approach we authorize only the relaxation of users’ preferences while maintaining arc-consistency on the problem. The underlying protocol can efficiently reach the optimal solution (satisfying some predefined optimality criteria) whenever possible, using only minimum localized asynchronous communications. This purpose is achieved with minimal message passing while trying to preserve at most the privacy of involved users. Detailed experimental results on randomly generated MS problems show that MSRAC is scalable and it leads to speed up over other approaches, especially for large problems with strong constraints.     

知识化制造系统中动态调度的自适应策略研究

针对知识化制造系统中的动态调度问题,结合知识化制造单元的高智能特征,提出了B-Q学习算法．并基于该算法构建了一种自适应调度控制策略．针对知识化制造系统运行过程中系统状态空间较大的特点,通过提取系统状态特征,对系统状态进行合理聚类,有效地降低了系统状态空间的复杂性．根据系统当前所处的瞬时状态．选取不同的调度规则对缓冲区中工件进行有效调度．仿真结果验证了所提出调度控制策略的有效性．     

一种基于调度的分簇无线传感器网络簇首选择策略

针对无线传感器网络中簇首更换出现的各节点均参与竞争而引起能耗较大的现象,提出了一种基于调度的无线传感器网络簇首选择策略.该策略将各节点分为簇首节点、成员节点和调度节点三种类型,在簇运行阶段,调度节点对各簇中簇首节点和成员节点的能量进行实时监测;在簇首更换阶段,由调度节点根据监测的结果指定相应的簇首节点,从而减少了簇首更换阶段各节点均参与簇首竞争而引起的能量消耗.最后进行了仿真实验与对比,实验结果表明改进的簇首选择策略能够有效地改进网络性能,延长网络生命周期.     

A genetic fuzzy agent using ontology model for meeting scheduling system

A Genetic Fuzzy Agent (GFA) using the ontology model for Meeting Scheduling System (MSS) is presented in this paper. The ontology model includes the Fuzzy Meeting Scheduling Ontology (FMSO) and the Fuzzy Personal Ontology (FPO) that can support to construct the knowledge base of the GFA. The FMSO is utilized to record and describe the meeting scheduling domain knowledge for the GFA. In addition, we implement a FMSO editor for generating the Web Ontology Language, OWL, that will be utilized by the GFA. Furthermore, the GFA will infer the suitable meeting time slots based on the ontology model. Moreover, it also adjusts the FMSO and FPO based on the results of the genetic learning mechanism for the next meeting. The experimental results show that our approach can effectively work for MSS.