When intelligent agents act in a stochastic environment, the principle of maximizing expected rewards is used to optimize their policies. The rationality of the maximum rewards becomes a single objective when agents’ decision problems are solved in most cases. This sometimes leads to the agents’ behaviors (the optimal policies for solving the decision problems) that are not legible . In other words, it is difficult for users (or other agents and even humans) to understand the agents’ intentions when they are executing the optimal policies. Hence, it becomes pertinent to consider the legibility of agents’ decision problems. The key challenge lies in formulating a proper legibility function in the problems. Using domain experts’ inputs leans to be subjective and inconsistent in specifying legibility values, and the manual approach quickly becomes infeasible in a complex problem domain. In this article, we aim to learn such a legibility function parallel to developing a (conventional) reward function. We adopt inverse reinforcement learning techniques to automate a legibility function in agents’ decision problems. We first demonstrate the effectiveness of the inverse reinforcement learning technique when legibility is solely considered in a decision problem. Things become complicated when both the reward and legibility functions are to be found. We develop a multi-objective inverse reinforcement learning method to automate the two functions in a good balance simultaneously. We vary problem domains in the performance study and provide empirical results in support.

Discovering common intentions of multiple agents is one of the important ways to detect the tendency of their collaborative behaviours. Existing work mainly focuses on intention recognition in a single-agent setting and uses a descriptive model, e.g. Bayesian networks, in the recognition process. In this article, we develop a new approach of identifying intentions for multiple agents through analysing their behaviours over time. We first define a prescriptive, behavioural model for a single agent that represents the agent’s behaviours where their intentions are hidden in the plan execution. We introduce landmarks into the behavioural model therefore enhancing informative features to identify common intentions for multiple agents. Subsequently, we refine the model by focusing only on action sequences in their plans and provide a light model for identifying and comparing their intentions. The new model provides a simple approach of grouping agents’ common intentions upon partial plans observed in agents’ interactions. After that, we transform the intention recognition into an un-supervised learning problem and adapt a clustering algorithm to group intentions of multiple agents through comparing their behavioural models. We conduct the clustering process through measuring similarity of probability distributions over potential landmarks in the behavioural models so as to discover agents’ common intentions. Finally, we examine the new intention recognition approaches in two problem domains. We demonstrate importance of recognising common intentions of multiple agents in achieving their goals and provide experimental results to show performance of the new approaches.

Preference learning, especially pairwise preference learning, is an efficient method for modeling implicit feedback in item recommendation. However, it is insufficient and not always valid to work for a basic pairwise preference model, which assumes that users prefer interacted (i.e., bought or viewed) items to un-interacted (i.e., not bought or not viewed) items. Recently, the state-of-the-art approaches have emerged as two separate but powerful methods, namely, pairwise preferences over item-sets and asymmetric pairwise preference models, respectively, to address limitations of the basic models. In spite of the success achieved by these methods, the assumption that the horizontal pairwise preference is with respect to two items does not always hold in asymmetric pairwise preference. Hence, it is appealing to integrate them into a uniform approach. In this article, we propose a novel symmetric pairwise preference assumption. We use a weighted average through a softmax function and define the overall preferences that can better discover users’ preference patterns. With the new assumption and the weighted average method, we propose a novel recommendation algorithm to improve the recommendation quality. Extensive empirical studies show that our new algorithms can significantly outperform several state-of-the-art and baseline methods over a number of public datasets.

Modeling other agents' behaviors plays an important role in decision models for interactions among multiple agents. To optimize its own decisions, a subject agent needs to model what other agents act simultaneously in an uncertain environment. However, modeling insufficiency occurs when the agents are competitive and the subject agent cannot get full knowledge about other agents. Even when the agents are collaborative, they may not share their true behaviors due to their privacy concerns. Most of the recent research still assumes that the agents have common knowledge about their environments and a subject agent has the true behavior of other agents in its mind. Consequently, the resulting techniques are not applicable in many practical problem domains. In this article, we investigate into diversifying behaviors of other agents in the subject agent's decision model before their interactions. The challenges lie in generating and measuring new behaviors of other agents. Starting with prior knowledge about other agents' behaviors, we use a linear reduction technique to extract representative behavioral features from the known behaviors. We subsequently generate their new behaviors by expanding the features and propose two diversity measurements to select top- K $K$ behaviors. We demonstrate the performance of the new techniques in two well-studied problem domains. The top- K $K$ behavior selection embarks the study of unknown behaviors in multiagent decision making and inspires investigation of diversifying agents' behaviors in competitive agent interactions. This study will contribute to intelligent systems dealing with unknown unknowns in an open artificial intelligence world.

Abstract With the availability of significant amount of data, data-driven decision making becomes an alternative way for solving complex multiagent decision problems. Instead of using domain knowledge to explicitly build decision models, the data-driven approach learns decisions (probably optimal ones) from available data. This removes the knowledge bottleneck in the traditional knowledge-driven decision making, which requires a strong support from domain experts. In this paper, we study data-driven decision making in the context of interactive dynamic influence diagrams (I-DIDs)—a general framework for multiagent sequential decision making under uncertainty. We propose a data-driven framework to solve the I-DIDs model and focus on learning the behavior of other agents in problem domains. The challenge is on learning a complete policy tree that will be embedded in the I-DIDs models due to limited data. We propose two new methods to develop complete policy trees for the other agents in the I-DIDs. The first method uses a simple clustering process, while the second one employs sophisticated statistical checks. We analyze the proposed algorithms in a theoretical way and experiment them over two problem domains.

This article embarks a study on multiagent transfer learning (TL) for addressing the specific challenges that arise in complex multiagent systems where agents have different or even competing objectives. Specifically, beyond the essential backbone of a state-of-the-art evolutionary TL framework (eTL), this article presents the novel TL framework with prediction (eTL-P) as an upgrade over existing eTL to endow agents with abilities to interact with their opponents effectively by building candidate models and accordingly predicting their behavioral strategies. To reduce the complexity of candidate models, eTL-P constructs a monotone submodular function, which facilitates to select Top-${K}$models from all available candidate models based on their representativeness in terms of behavioral coverage as well as reward diversity. eTL-P also integrates social selection mechanisms for agents to identify their better-performing partners, thus improving their learning performance and reducing the complexity of behavior prediction by reusing useful knowledge with respect to their partners’ mind universes. Experiments based on a partner-opponent minefield navigation task (PO-MNT) have shown that eTL-P exhibits the superiority in achieving higher learning capability and efficiency of multiple agents when compared to the state-of-the-art multiagent TL approaches.

Multifactorial evolutionary algorithm (MFEA) exploits the parallelism of population-based evolutionaryalgorithm and provides an efficient way to evolve individuals for solving multiple tasks concurrently.Its efficiency is derived by implicitly transferring the genetic information among tasks.However, MFEA doesn?t distinguish the information quality in the transfer compromising the algorithmperformance. We propose a group-based MFEA that groups tasks of similar types and selectivelytransfers the genetic information only within the groups. We also develop a new selection criterionand an additional mating selection mechanism in order to strengthen the effectiveness andefficiency of the improved MFEA. We conduct the experiments in both the cross-domain and intra-domainproblems.

Meme automaton is an adaptive entity that autonomously acquires an increasing level of capability and intelligence through embedded memes evolving independently or via social interactions. This paper begins a study on memetic multiagent system (MeMAS) toward human-like social agents with memetic automaton. We introduce a potentially rich meme-inspired design and operational model, with Darwin's theory of natural selection and Dawkins' notion of a meme as the principal driving forces behind interactions among agents, whereby memes form the fundamental building blocks of the agents' mind universe. To improve the efficiency and scalability of MeMAS, we propose memetic agents with structured memes in this paper. Particularly, we focus on meme selection design where the commonly used elitist strategy is further improved by assimilating the notion of like-attracts-like in the human learning. We conduct experimental study on multiple problem domains and show the performance of the proposed MeMAS on human-like social behavior.

Distributed computing environments offer vast amounts of computational power for use in parallel memetic algorithms. However, they consist of heterogeneous computing nodes, in terms of computational power, operating platform, network connectivity and latency. The behavior of parallel memetic algorithms in such environment is poorly understood: the vast majority of current parallel MAs assumes homogeneous environment. To deal with the heterogeneity of the computing resources, a hierarchical model PMA (hPMA-DLS) is proposed to provide the speed-up regardless of the heterogeneity in the distributed environment while preserving the standard behavior of the PMA. The empirical study on several large scale quadratic assignment problems (QAPs) shows that hPMA-DLS can enhance the efficiency of the island model PMA-DLS [22] search without deterioration in the solution quality.

In this paper, we propose the island model parallel memetic algorithm with diversity-based dynamic adaptive strategy (PMA-DLS) for controlling the local search frequency and demonstrate its utility in solving complex combinatorial optimization problems, in particular large-scale quadratic assignment problems (QAPs). The empirical results show that PMA-DLS converges to competitive solutions at significantly lower computational cost when compared to the canonical MA and PMA. Furthermore, compared to our previous work on PMA using static adaptation strategy, it is found that the diversity-based dynamic adaptation strategy displays better robustness in terms of solution quality across the class of QAP problems considered without requiring extra effort in selecting suitable parameters.

In recent decades, many meta-heuristics, including genetic algorithm (GA), ant colony optimization (ACO) and various local search (LS) procedures have been developed for solving a variety of NP-hard combinatorial optimization problems. Depending on the complexity of the optimization problem, a meta-heuristic method that may have proven to be successful in the past might not work as well. Hence it is becoming a common practice to hybridize meta-heuristics and local heuristics with the aim of improving the overall performance. In this paper, we propose a novel adaptive GA-ACO-LS hybrid algorithm for solving quadratic assignment problem (QAP). Empirical study on a diverse set of QAP benchmark problems shows that the proposed adaptive GA-ACO-LS converges to good solutions efficiently. The results obtained were compared to the recent state-of-the-art algorithm for QAP, and our algorithm showed obvious improvement.

Memetic algorithms have become to gain increasingly important for solving large scale combinatorial optimization problems. Typically, the extent of the application of local searches in canonical memetic algorithm is based on the principle of "more is better". In the same spirit, the island model parallel memetic algorithm (PMA) is an important extension of the canonical memetic algorithm which applies local searches to every transitional solutions being considered. For PMA which applies complete local search, we termed it as PMA-CLS. In this paper, we consider the island model PMA with selective application of local search (PMA-SLS) and demonstrate its utility in solving complex combinatorial optimization problems, in particular large-scale quadratic assignment problems (QAPs). Based on our empirical results, the PMA-SLS compared to the PMA-CLS, can reduce the computational time spent significantly with little or no lost of solution quality. This we concluded is due mainly to the ability of the PMA-SLS to manage a more desirable diversity profile as the search progresses.

This paper extends our previous work on the island model parallel hybrid-genetic algorithm (PHGA) for large scale quadratic assignment problems (QAPs). Some issues on the control parameters of the migration process and how they affect the quality of the solutions and the efficiency of algorithm deserve further evaluative study. In this paper, we investigate the effect of migration topology on the performance of the PHGA. Two topologies, one-way ring topology and random topology, are studied and analyzed. The empirical results show that the PHGA with ring topology is better able to achieve an appropriate tradeoff between exploration and exploitation and hence more helpful to improve the performance of PHGA for solving large scale QAPs.

In this paper, we consider a parallel hybrid-GA (PHGA) for solving large combinatorial optimization problem. The approach of our PHGA is based on the island model whereby islands of subpopulations are farmed to multiple processing nodes for execution. The PHGA was applied to solve the quadratic assignment problems (QAP) to demonstrate the potential effectiveness of the models. In particular, we concentrate on QAP benchmarks of high complexity for n ranging from 60 to 256. Our results show that a two-island PHGA which employs a simplistic elite migration between islands outperforms the serial hybrid-GA (SHGA) significantly. As the size and complexity of the problem increases, the advantage of the PHGA in terms of computation time and solution quality becomes more evident. This opens up a wide channel for further exploration on implementation of the PHGA in a grid computing environment.