Communication infrastructure in distributed scheduling

The emergence of distributed artificial intelligent (DAI) introduced a new approach to solve scheduling problems by a set of scheduling systems that interact with each other in the problem-solving process. In this paper, we describe a communication infrastructure to handle connection and communication between distributed Internet scheduling systems for distributed applications. First, we present an agent model of distributed scheduling systems where agents can communicate and coordinate activities with each other via an agent communication language. Then, we define the syntax and semantics for the agent communication languages, and negotiation mechanism. Following that, we discuss the design and development of the prototype for the multi-agent scheduling systems. We conclude with a discussion of communication issues for heterogeneous agent-based scheduling systems to solve distributed scheduling problems.     

基于DCOM的动态运输调度多智能体系统研究*

针对物流运输调度中的客户需求动态性和随机性问题的解决,设计了一种基于DCOM的动态运输调度多智能体系统。在多智能体系统中,设计了包括预规划智能体、实时监控智能体、决策智能体和车辆智能体四类智能体。智能体以DCOM式组件形式实现,智能体之间的通信和协调由决策智能体集中执行。通过一个实例验证了系统算法的有效性,同时也为动态运输调度问题的解决提供了一个可参考的思路。     

Cooperative, hybrid agent architecture for real-time traffic signal control

This paper presents a new hybrid, synergistic approach in applying computational intelligence concepts to implement a cooperative, hierarchical, multiagent system for real-time traffic signal control of a complex traffic network. The large-scale traffic signal control problem is divided into various subproblems, and each subproblem is handled by an intelligent agent with a fuzzy neural decision-making module. The decisions made by lower-level agents are mediated by their respective higher-level agents. Through adopting a cooperative distributed problem solving approach, coordinated control by the agents is achieved. In order for the multiagent architecture to adapt itself continuously to the dynamically changing problem domain, a multistage online learning process for each agent is implemented involving reinforcement learning, learning rate and weight adjustment as well as dynamic update of fuzzy relations using an evolutionary algorithm. The test bed used for this research is a section of the Central Business District of Singapore. The performance of the proposed multiagent architecture is evaluated against the set of signal plans used by the current real-time adaptive traffic control system. The multiagent architecture produces significant improvements in the conditions of the traffic network, reducing the total mean delay by 40% and total vehicle stoppage time by 50%.     

Multi-agent system and reinforcement learning approach for distributed intelligence in a flexible smart manufacturing system

Personalized production has emerged as a result of the increasing customer demand for more personalized products. Personalized production systems carry a greater amount of uncertainty and variability when compared with traditional manufacturing systems. In this paper, we present a smart manufacturing system using a multi-agent system and reinforcement learning, which is characterized by machines with intelligent agents to enable a system to have autonomy of decision making, sociability to interact with other systems, and intelligence to learn dynamically changing environments. In the proposed system, machines with intelligent agents evaluate the priorities of jobs and distribute them through negotiation. In addition, we propose methods for machines with intelligent agents to learn to make better decisions. The performance of the proposed system and the dispatching rule is demonstrated by comparing the results of the scheduling problem with early completion, productivity, and delay. The obtained results show that the manufacturing system with distributed artificial intelligence is competitive in a dynamic environment.     

A distributed asynchronous system for predictive and reactive scheduling

In DAS, the distributed asynchronous scheduler, the scheduling problem is decomposed both functionally and spatially across a hierarchy of communicating agents where each agent exhibits the properties of opportunism, reaction and belief maintenance. Each agent corresponds to a distinct software process, all of which may run concurrently. To be able to work towards a global solution each agent may react to change induced upon it by other agents and is able to negotiate with agents. The external world is treated as an agent with one exceptional property, negotiation is disallowed. The system is disciplined such that problem solving effort can be dynamically focused and decision making synchronized. DAS does not differentiate between prediction and reaction. By retaining knowledge of the search space explored and the remaining opportunities, reaction is considered as a continuation of search or conversely prediction is considered as a series of reactions.     

An evolutionary compensatory negotiation model for distributed dynamic scheduling

Although a considerable amount of efforts has been devoted to developing optimum negotiation for dynamic scheduling, most of them are inappropriate for the non-cooperative, self-interested participants in a distributed project for practical purpose. In this paper, an agent-based approach with a mutual influencing, many-issue, one-to-many-party, compensatory negotiation model is proposed. In the model, the activity agents possess various negotiation tactics and strategies formed by respective self-interested owner's subjective preference, aim to find the contracts of schedule adjustment mutually acceptable to respective participant's acquaintance while encountering conflicts over rescheduling settlement. In order to find the fitting negotiation strategies that are optimally adapted for each activity agent, an evolutionary computation approach that encodes the parameters of tactics and strategies of an agent as genes in GAs is also addressed. In the final, a prototype with a case discussed in researches is evaluated to validate the feasibility and applicability of the model, and some characteristics and future works are also exhibited.     

一种基于多Agent分布式协商框架的工程调度方法

本文介绍了一种分布式协商框架,并提出了一种基于Agent的补偿协商方法用以解决工程项目中因不可预见的因素而造成的工程计划调度问题,以一个简单的例子分析了Agent的协商过程。     

Shop-floor scheduling at shipbuilding yards using the multiple intelligent agent system

The intelligent agent system has become a typical approach to research distributed artificial intelligence and distributed problem solving. However, despite its various technical advantages, the distribution and expansion of the intelligent agent system approach has been limited because existing methodologies rely on specialized applications and therefore require intensive investment to develop new systems. In an attempt to conquer these difficulties, a standardized methodology to construct intelligent agent systems is proposed. This approach deviates from current agent system approaches of repeatedly constructing new and customized expert systems. Specifically, it provides an economical method for developing intelligent agent systems by investigating the possibility of standardizing message communication protocols in linguistics speech-act theory and by supplementing traditional algorithmic systems with intelligent segments using, among others, expert system tools. To verify effectiveness, the shop-floor scheduling system of a large-scale shipbuilding yard has been redesigned, developed, and tested using this approach. This shop-floor scheduling system requires the scheduling of when and where to process block construction under various constraints. It is a difficult four-dimensional time and space allocation problem involving traditional NP-complete search spaces. The tested intelligent agent system proposes an innovative method for reducing the search space into three levels: the algorithm level, the agent intelligence level, and the level of cooperation among agents. It also provides methods for solving deadlock occurrence and non-uniformity problems resulting from parallel processing. Test results demonstrate applicability and economy, among other technical advantages.     

Bargaining on an Internet Agent-based Market: Behavioral vs. Optimizing Agents

In this paper, we analyze an Internet agent-based market where non-cooperative agents using behavioral rules negotiate the price of a given product in a bilateral and sequential manner. In this setting, we study the optimal decision-making process of a buying agent that enters the market. Our approach is based on Negotiation Analysis (Raiffa, 1982; Sebenuis, 1992) and we consider that the optimizing buying agent maximizes her discounted expected utility using subjective probabilities. The optimal decision-making process of the buying agent is treated as a stochastic control problem that can be solved by dynamic programming. Three types of behavioral agents are studied, namely conceder agents, boulware agents and imitative agents. A set of simulations is undertaken in order to predict the average outcome in a negotiation process for different parameters of the optimizing buying agent and for the three possible selling agents' behaviors. Finally, we compare the performance of the optimizing agent with that of behavioral buying agents.     

Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations

Agent-based distributed simulations are confronted with load imbalance problem, which significantly affects simulation performance. Dynamic load balancing can be effective in decreasing simulation execution time and improving simulation performance. The characteristics of multi-agent systems and time synchronization mechanisms make the traditional dynamic load balancing approaches not suitable for dynamic load balancing in agent-based distributed simulations. In this paper, an adaptive dynamic load balancing model in agent-based distributed simulations is proposed. Due to the complexity and huge time consuming for solving the model, a distributed approximate optimized scheduling algorithm with partial information (DAOSAPI) is proposed. It integrates the distributed mode, approximate optimization and agent set scheduling approach. Finally, experiments are conducted to verify the efficiency of the proposed algorithm and the simulation performance under dynamic agent scheduling. The experiments indicate that DAOSPI has the advantage of short execution time in large-scale agent scheduling, and the distributed simulation performance under this dynamic agent scheduling outperforms that under static random agent distribution.     

Dynamic hierarchical control for distributed problem solving

Distributed problem solving (DPS) has become one of the central topics in AI. Much research has been concerned with finding an appropriate distributed control regime. We propose the concept of dynamic, hierarchical control (DHC) for distributed problem solving.

In many domains, DPS has a natural hierarchy or a subproblem hierarchy can be imposed by utilizing appropriate decomposition techniques. DHC aims at exploiting the power inherent in the hierarchical approach. It also enables the control of the problem solving process to fit the structure of a domain. This results in well-coordinated cooperation and coherent negotiation among distributed controllers.

We have used the DHC to perform plant combine production planning (PCPP). This task involves the activity of a network of production units, each with possibly different characteristics, collaborating to produce various items under dynamically changing conditions. We also describe the general structure of a single controller which adopts a blackboard and a knowledge source (KS) scheduling mechanism to carry out dynamic process execution.

The paper describes the results of our first solution to this problem. Finally, we discuss on-going research that aims at handling additional problems.     

An ontology based approach to organize multi-agent assisted supply chain negotiations

Effective supply chain management (SCM) comprises activities involving the demand and supply of resources and services. Negotiation is an essential approach to solve conflicting transaction and scheduling problems among supply chain members. The multi-agent system (MAS) technology has provided the potential of automating supply chain negotiations to alleviate human interactions. Software agents are supposed to perform on behalf of their human owners only when equipped with sophisticated negotiation knowledge. To better organize the negotiation knowledge utilized by agents and facilitate agents’ adaptive negotiation decision making ability, an ontology-based approach is proposed in this paper. Firstly, the multi-agent assisted supply chain negotiation scheme is presented to configure the general design components of the negotiation system, covering the agent intelligence modules, the knowledge organization method and the negotiation protocol. Then, the ontology-based negotiation knowledge organization method is specified. The negotiation knowledge is separated into shared negotiation ontology and private negotiation ontology to ensure both the agent communicative interoperability and the privacy of strategic knowledge. Inference rules are defined on top of the private negotiation ontology to guide agents’ reasoning ability. Through this method, agents’ negotiation behaviors will be more adaptive to various negotiation environments utilizing corresponding negotiation knowledge.     

Negotiation as a metaphor for distributed problem solving

We describe the concept of distributed problem solving and define it as the cooperative solution of problems by a decentralized and loosely coupled collection of problem solvers. This approach to problem solving offers the promise of increased performance and provides a useful medium for exploring and developing new problem-solving techniques.We present a framework called the contract net that specifies communication and control in a distributed problem solver. Task distribution is viewed as an interactive process, a discussion carried on between a node with a task to be executed and a group of nodes that may be able to execute the task. We describe the kinds of information that must be passed between nodes during the discussion in order to obtain effective problem-solving behavior. This discussion is the origin of the negotiation metaphor: Task distribution is viewed as a form of contract negotiation.We emphasize that protocols for distributed problem solving should help determine the content of the information transmitted, rather than simply provide a means of sending bits from one node to another.The use of the contract net framework is demonstrated in the solution of a simulated problem in area surveillance, of the sort encountered in ship or air traffic control. We discuss the mode of operation of a distributed sensing system, a network of nodes extending throughout a relatively large geographic area, whose primary aim is the formation of a dynamic map of traffic in the area.From the results of this preliminary study we abstract features of the framework applicable to problem solving in general, examining in particular transfer of control. Comparisons with planner, conniver, hearsay-ii, and pup6 are used to demonstrate that negotiation—the two-way transfer of information—is a natural extension to the transfer of control mechanisms used in earlier problem-solving systems.     

多Agent系统分布式问题求解的代数模型方法(Ⅰ): 社会行为、社会局势和社会动力学

该组论文提出一种新的代数模型方法，用于多Agent系统超分布超并行社会智能问题求解，该方法通过社会动力学和社会智能，统一地处理各种复杂的并行的社会行为，用于求解用常规方法难以处理的许多社会交互问题，本文是组合论文中第一篇，提出多Agent系统分布式问题求解的代数模型结构，讨论多Agent系统中典型社会行为模式及其性质，建立形式化描述，同时也论述了代数模型中的社会局势和社会动力学。     

Cooperation and Competition in ALIAS: A Logic Framework for Agents that Negotiate

This paper presents ALIAS, an agent architecture based on intelligent logic agents, where the main form of agent reasoning is abduction. The system is particularly suited for solving problems where knowledge is incomplete, where agents may need to make reasonable hypotheses about the problem domain and other agents, and where the raised hypotheses have to be consistent for the overall set of agents. ALIAS agents are pro-active, exhibiting a goal-directed behavior, and autonomous, since each one can solve problems using its own private knowledge base. ALIAS agents are also social, because they are able to interact with other agents, in order to cooperatively solve problems. The coordination mechanisms are modeled by means of LAILA, a logic-based language which allows to express intra-agent reasoning and inter-agent coordination. As an application, we show how LAILA can be used to implement inter-agent dialogues, e.g., for negotiation. In particular, LAILA is well-suited to coordinate the process of negotiation aimed at exchanging resources between agents, thus allowing them to execute the plans to achieve their goals.     

A negotiation framework for linked combinatorial optimization problems

We tackle the challenge of applying automated negotiation to self-interested agents with local but linked combinatorial optimization problems. Using a distributed production scheduling problem, we propose two negotiation strategies for making concessions in a joint search space of agreements. In the first strategy, building on Lai and Sycara (Group Decis Negot 18(2):169–187, 2009), an agent concedes on local utility in order to achieve an agreement. In the second strategy, an agent concedes on the distance in an attribute space while maximizing its local utility. Lastly, we introduce a Pareto improvement phase to bring the final agreement closer to the Pareto frontier. Experimental results show that the new attribute-space negotiation strategy outperforms its utility-based counterpart on the quality of the agreements and the Pareto improvement phase is effective in approaching the Pareto frontier. This article presents the first study of applying automated negotiation to self-interested agents each with a local, but linked, combinatorial optimization problem.     

基于Agent的电子商务博弈协商过程的研究

把人工智能的Agent技术和经济学的不完全信息动态博弈方法结合起来,在买方的立场上通过约束满足机制实现了自动协商的过程。该方法及自动协商过程可用于解决电子商务协商领域中的协商效率不高的问题。     

Intelligent negotiation model for ubiquitous group decision scenarios

Supporting group decision-making in ubiquitous contexts is a complex task that must deal with a large amount of factors to succeed. Here we propose an approach for an intelligent negotiation model to support the group decision-making process specifically designed for ubiquitous contexts. Our approach can be used by researchers that intend to include arguments, complex algorithms, and agents’ modeling in a negotiation model. It uses a social networking logic due to the type of communication employed by the agents and it intends to support the ubiquitous group decision-making process in a similar way to the real process, which simultaneously preserves the amount and quality of intelligence generated in face-to-face meetings. We propose a new look into this problem by considering and defining strategies to deal with important points such as the type of attributes in the multicriterion problems, agents’ reasoning, and intelligent dialogues.     

An agent-oriented approach to resolve scheduling optimization in intelligent manufacturing

Agent technology is considered as a promising approach for developing optimizing process plans in intelligent manufacturing. As a bridge between computer aided design (CAD) and computer aided manufacturing (CAM), the computer aided scheduling optimization (CASO) plays an important role in the computer integrated manufacturing (CIM) environment. In order to develop a multi-agent-based scheduling system for intelligent manufacturing, it is necessary to build various functional agents for all the resources and an agent manager to improve the scheduling agility. Identifying the shortcomings of traditional scheduling algorithm in intelligent manufacturing, the architecture of intelligent manufacturing system based on multi-agent is put forward, among which agent represents the basic processing entity. Multi-agent-based scheduling is a new intelligent scheduling method based on the theories of multi-agent system (MAS) and distributed artificial intelligence (DAI). It views intelligent manufacturing as composed of a set of intelligent agents, who are responsible for one or more activities and interacting with other related agents in planning and executing their responsibilities. In this paper, the proposed architecture consists of various autonomous agents that are capable of communicating with each other and making decisions based on their knowledge. The architecture of intelligent manufacturing, the scheduling optimization algorithm, the negotiation processes and protocols among the agents are described in detail. A prototype system is built and validated in an illustrative example, which demonstrates the feasibility of the proposed approach. The experiments prove that the implementation of multi-agent technology in intelligent manufacturing system makes the operations much more flexible, economical and energy efficient.