Abstract:In order to specify properties relating to probability, real time, and knowledge on multi-agent systems, a logic system PTCTLK is proposed. Model checking is an automatic technique for checking if a multi-agent system satisfies a PTCTLK formula. The state explosion problem is the key obstacle in checking the feasibility of the model. In this paper, a bounded model checking algorithm for PTCTLK is proposed. First the model checking of PTCTLK is reduced to the model checking of PBTLK, which does not contain real time operators. Second, the bounded semantics of PBTLK is defined and its correctness is proven. Third, the bounded model checking procedure of PBTLK is transformed into a linear equation. Finally, the paper discusses the law of increasing of probability measure, and some termination criterions are given. The case study shows that compared with the unbounded model checking, if the length of the witness is short, then the bounded model checking needs less space.

Abstract:Researches on trust have attracted more and more attentions in multi-agent systems and networks. However, subjective trust generally has no transitivity, which brings much non-determination on delegation, network information propagation, and the construction of subjective trust network. To this end, the paper discusses the binary value of trust relation, and its transitivity in cooperative environment. First, the study gives the definition of objective trust and subjective trust. Next, the paper proposes some useful properties of trust related to the transitivity of trust and demonstrates that objective trust has a relation of equivalence, and subjective trust has a relation of constrained symmetry and transitivity. Finally, a feasible algorithm of subjective trust closure and test algorithms for connectedness are given, and the study has demonstrated that the computational complexities of the above algorithms are polynomial order. The paper made some initial explores on transitivity of subjective trust and gives some useful basic conclusions.

Abstract:Argumentation systems are a kind of non-monotonic formalisms, capable of supporting the reasoning and decision-making of individual agents, and the effective interactions among multiple agents. Since the knowledge, observations of an individual agent and the interacting process of different agents are dynamic in various argumentation systems, the changing of arguments and attacks is pervasive. As a new research area, the concepts, theories and methods related to dynamic of argumentation systems are far from mature. After introducing the basic working mechanism of argumentation systems, this paper presents two research directions of dynamics of argumentation systems (i.e., forward dynamics and backward dynamics) and discusses some open problems to be resolved. According to these problems, the paper briefly reviews the existing theories and methods, and analyzes their properties and shortcomings.

Abstract:Agent-Oriented programming (AOP) is inspired from the concepts and metaphors of multi-agent systems and borrows agent theory and technology to construct software systems. It represents a novel programming paradigm because its method, model, theory, and language are actually different from ones of existing mainstream programming technologies like OOP. As multi-agent system is considered as an effective technology to deal with the development of complex systems in open environment, AOP attracts many researchers and practitioners in the literatures of AI, software engineering and distributed computing. Significant progress has been made in the past twenty years. However, there are still great challenges to widely apply such a paradigm to support the development of complex systems in industry. In addition to using AI as basis, AOP should consider and borrow successful principles and practices of software engineering, especially existing programming paradigms, to promote its wide acceptance by software engineering practitioners. The aim of this paper is to give a systemic introduction of the research roadmap of AOP, investigate its state-of-the-art from a software engineering viewpoint by considering different programming levels of MAS and four research constituents of programming paradigms, including abstraction and model, mechanism and theory, language construct, and facility, supported platform. The survey intends to show the different research focuses and their changes in various stages. Moreover, the study identifies a number of issues and challenges in existing researches and prospect its future researches.

Abstract:Multi-Agent system (MAS) is widely used to develop applications in different domains. Currently, the computing platform is becoming more and more open, dynamic, and uncontrollable. Hence, software systems are required to adapt to the changing states of themselves and their running environments. In other words, systems should be context-aware. However, the way to enhance existing MAS applications with context-awareness is not well addressed by existing works. In this paper, based on the Separation of Concerns principle, the study combines context-oriented programming (COP), reflection, as well as code instrumentation technologies in a way to introduce context-awareness to existing MAS applications. With the proposed approach, agents of an existing MAS application are transformed to context-aware ones, even if the source code is unavailable. In addition, with the help of the underlying runtime environment, the administrator can dynamically adjust the context-aware behaviors of a specified agent (or a group of agents) at runtime.

Abstract:In the construction of dynamic and open multi-agent systems, several issues in existing agent-oriented programming should be solved including a lack of high-level abstraction, a great gap between the implementation and design models, insufficient execution mechanism and programming constructs to support dynamics. To deal with these issues, this paper proposes an organization-based agent-oriented programming approach, which takes organizations, groups, roles, and agents as first-class entities to narrow the gap between implementation and design models. Moreover, this approach introduces serveral organization mechanisms, i.e. role enactment mechanism and role-based interactions, to support the dynamics such as the dynamic composition of the agents’ behaviors and dynamic interactions among agents. Based on the above ideas, an organization-based agent-oriented programming language, Oragent, is designed by defining its abstract syntax and formal operational semantics. Finally, a case is studied to show how to construct dynamic and flexible multi-agent systems with the programming approach and Oragent language.

Abstract:Green-Waved traffic control is one of the most efficient strategies in allowing continuous traffic from major directions flow over multiple intersections to improve urban transportation efficiency. When the number of traffic lights scales up, traditional centralized control suffers a bottleneck in both communication and computation. Decentralized control is potentially inefficient when local traffic lights only gain very limited observations to the whole network. This paper proposes a decentralized, multi-agent based schema to adaptively control massive traffic lights, which promotes the effects of green-wave. The key is that agents use the prospection of local state one time ahead as evidence to support decisions. Noting that only the traffic from the adjacent intersections affect the next state of a given intersection, the study models the interactions as decentralized agents to cooperatively coordinate each intersection by using decision theoretical models. This paper presents the algorithm and simulation results to prove the feasibility of the approach to massive urban transportation system.

Abstract:Mobile agents (MA) have been widely applied in detecting abnormal events in wireless sensor networks. Based on the characteristics of the event, the data center (i.e., the sink) sends a specific MA to collect the data sensed by the sensors (acted as source sensors) in the nearby area of the target event. Different from the traditional client-server transmission model, the MA technology can compress and aggregate the sensed data and reduce the amount of data and the energy consumption of sensors for data transmission. When MA passes more source sensors, the size of the collected data becomes larger. This paper investigates the existing MA itinerary planning algorithms, and proposes an agent data separation strategy. The strategy can determine whether to send the collected data to the sink in advance based on a data separation rule. If data separation is performed, the data collected by the MA will be sent to the sink, while the MA only with the head will continue visiting the rest source sensors. Because the data carried by the MA is reduced, the proposed agent data separation strategy conserves the energy consumption of sources sensors. The strategy is a general scheme and can be applied in most of the existing MA itinerary planning algorithms to enhance their performance. The ultimate goal of the proposed strategy is to reduce the data transmitted by source sensors and extend their working lifetime for monitoring the targets.

Abstract:In previous research, most related works on inferring the structures of diffusion networks are designed for recovering the process of information propagation. The learning data adopted by these works is distinct in terms of both format and features from the available surveillance data of epidemics. Therefore, the existing methods are not competent when dealing with epidemic surveillance data with some intractable properties such as coarse granularity, spatial and temporal multi-scale, and incompleteness. To address this issue, an AOC (autonomy oriented computing) based method is proposed to model epidemic networks, as well as to infer their structures from epidemic surveillance data. In this method, the structure of an epidemic network and the process of disease spread are modeled by an autonomous multi-agent system named D-AOC, and the parameters of the system are automatically estimated by a self-discovery process. During this process, the parameters are adjusted and thereafter, the behaviors of agents are updated by a feedback mechanism which combines the Monte Carlo simulation and swarm intelligence. The objective is to reduce the difference between emergent behavior of the D-AOC and observed surveillance data. Regulated by the feedback mechanism, it is expected that the D-AOC will keep evolving toward the real system to be simulated. In this way, the structure of epidemic network and main biological features related to the epidemic will finally be recovered. The effectiveness and applicability of the proposed method have been validated and discussed by analyzing the real surveillance data of the H1N1 swine-flu in Hong Kong during 2009. Moreover, one scenario of applying epidemic network inference is also demonstrated by a case study of epidemic risk assessment in Hong Kong.

Abstract:With the expansion of distributed multi-agent system applications and the increasing scale of the system, the characters of complex network have become an important factor in system performance. This paper makes an initial effort to find the effects of complex network characters on large-scale distributed multi-agent coordination to create a systemic analysis of the system performance and provide organization optimization algorithm designs. The study primarily investigated typical complex networks: random network, small-world network, grid network and scale-free network in multi-agent coordination on theoretical analysis and practical simulations. In theoretical analysis, the study has built the cooperative information transmission model based on Markov chain over different network topologies and compared their efficiencies on either random walk or intelligent routing model. In addition, the study explored the characters of complex network in three main coordination simulations: cooperative information transmission, multi-agent team coordination, and multi-agent network recovery. It is found that the characters of complex network such as small-world or scale-free attributes will bring significant differences in spite of the same coordination schema, and it is feasible to design some desired intelligent algorithms to take the advantage of those effects so that system performance can be promoted.

Abstract:The concurrent negotiation based on genetic algorithm has special advantages in e-commerce applications. But, the relativity of issues and the dynamic weights of issues are not taken into account in existing research. Thus, this paper proposes a solution to these problems by grouping the issues and adapting the dynamic weights, according to data mining from history resources. The concurrent negotiation model of relative issues is described in detail, including the formal definition of the model, the design of concurrent negotiation algorithm, and the update scheme of dynamic weights. The experimental results show that the model can meet the requirements of different negotiations, solve the issues’ relativity problem in the process of negotiation, and improve the negotiation efficiency.

Abstract:To effectively solve large-scale optimization problems, the paper proposes a distributed agent computing framework based on the parallel particle swarm optimization (PSO). The framework uses a master swarm for evolving complete solutions of the problem, and uses a set of slave swarms for evolving sub-solutions of the subproblems concurrently. The master swarm and slave swarms alternatively implement the PSO procedure to improve the problem-solving efficiency. Using the asynchronous team based agent architecture, a master/slave swarm consists of different kinds of agents, which share a population of solutions and cooperate to evolve the population, such as initializing solutions, moving particles, handling constraints, and decomposing/synthesizing sub-solutions. The framework can be used to solve complicated constained and multiobjective optimization problems efficiently. Experimental results demonstrate that this approach has significant performance advantage over two other state-of-the-art algorithms on a typical transportation problem.

Abstract:With the rapid development of Internet, it has been difficult for existing network architecture to meet the development of new applications, and ossification has grown to some extent. Network virtualization is considered to be the main means of solving the ossification problem. In network virtualization, virtual network mapping problem researches how to map virtual networks with nodes and links’ constraints to substrate network, which is surveyed in this paper. First, a formal definition of virtual network mapping problem is proposed, which is used to describe the problem in abstraction level. Meanwhile, challenges and solving goals of the problem are also investigated. Second classification of solving methods for this problem is analyzed, and, on the basis of the classification, many typical solving methods are introduced and compared. Finally, future research trends of the solving methods for this problem are reviewed.

Abstract:The problem of joining multicast routing and spectrum allocation with QoS constraints is studied in cognitive wireless mesh networks. A framework of solving the above problem, which contains a problem description, a representation of solution, fitness function, spectrum allocation algorithm, is proposed in this paper. Two algorithms for joint multicast routing and a spectrum allocation with end-to-end delay constraints based on intelligent computation are proposed in this paper. The first one is multicast routing and spectrum allocation algorithm based on genetic algorithm (GA-MRSA). The second one is multicast routing and spectrum allocation algorithm based on simulated annealing algorithm (SA-MRSA). The object of the two algorithms is to minimize the total channel conflict. Under the condition of getting lower total channel conflict number, the number of used channels is also few. Simulation results show that the two algorithms can achieve the expected goal: it can achieve a lower total channel conflict number.

Abstract:Network virtualization allows multiple isolated virtual networks to run simultaneously on a shared substrate infrastructure to provide diversifying services to the end user, solving the Internet ossification problem. However, a major challenge is efficiently mapping multiple virtual networks with different topologies into a shared infrastruture, named the virtual network embedding problem. This paper surveys the current literature primarily according to the composition of the infrastructure. Firstly, the concept and feature of network virtualizations are elaborated, and the corresponding model of virtual network embedding is formulated. Secondly, the latest research progress of virtual network embedding algorithms is reviewed according to the composing way of infrastructure, the integrity of problem space, the number of embedding stage and so on. Finally, the potential future research directions are outlined in the aspects of fairness, scalability, high utilization and trust.