Automatic generation of controllers for embodied legged organisms: a Pareto evolutionary multi-objective approach

In this paper, we investigate the use of a self-adaptive Pareto evolutionary multi-objective optimization (EMO) approach for evolving the controllers of virtual embodied organisms. The objective of this paper is to demonstrate the trade-off between quality of solutions and computational cost. We show empirically that evolving controllers using the proposed algorithm incurs significantly less computational cost when compared to a self-adaptive weighted sum EMO algorithm, a self-adaptive single-objective evolutionary algorithm (EA) and a hand-tuned Pareto EMO algorithm. The main contribution of the self-adaptive Pareto EMO approach is its ability to produce sufficiently good controllers with different locomotion capabilities in a single run, thereby reducing the evolutionary computational cost and allowing the designer to explore the space of good solutions simultaneously. Our results also show that self-adaptation was found to be highly beneficial in reducing redundancy when compared against the other algorithms. Moreover, it was also shown that genetic diversity was being maintained naturally by virtue of the system's inherent multi-objectivity.     

Preference representation using Gaussian functions on a hyperplane in evolutionary multi-objective optimization

Many-objective optimization has attracted much attention in evolutionary multi-objective optimization (EMO). This is because EMO algorithms developed so far often degrade their search ability for optimization problems with four or more objectives, which are frequently referred to as many-objective problems. One of promising approaches to handle many objectives is to incorporate the preference of a decision maker (DM) into EMO algorithms. With the preference, EMO algorithms can focus the search on regions preferred by the DM, resulting in solutions close to the Pareto front around the preferred regions. Although a number of preference-based EMO algorithms have been proposed, it is not trivial for the DM to reflect his/her actual preference in the search. We previously proposed to represent the preference of the DM using Gaussian functions on a hyperplane. The DM specifies the center and spread vectors of the Gaussian functions so as to represent his/her preference. The preference handling is integrated into the framework of NSGA-II. This paper extends our previous work so that obtained solutions follow the distribution of Gaussian functions specified. The performance of our proposed method is demonstrated mainly for benchmark problems and real-world applications with a few objectives in this paper. We also show the applicability of our method to many-objective problems.     

Classification as clustering: a Pareto cooperative-competitive GP approach

Intuitively population based algorithms such as genetic programming provide a natural environment for supporting solutions that learn to decompose the overall task between multiple individuals, or a team. This work presents a framework for evolving teams without recourse to prespecifying the number of cooperating individuals. To do so, each individual evolves a mapping to a distribution of outcomes that, following clustering, establishes the parameterization of a (Gaussian) local membership function. This gives individuals the opportunity to represent subsets of tasks, where the overall task is that of classification under the supervised learning domain. Thus, rather than each team member representing an entire class, individuals are free to identify unique subsets of the overall classification task. The framework is supported by techniques from evolutionary multiobjective optimization (EMO) and Pareto competitive coevolution. EMO establishes the basis for encouraging individuals to provide accurate yet nonoverlaping behaviors; whereas competitive coevolution provides the mechanism for scaling to potentially large unbalanced datasets. Benchmarking is performed against recent examples of nonlinear SVM classifiers over 12 UCI datasets with between 150 and 200,000 training instances. Solutions from the proposed coevolutionary multiobjective GP framework appear to provide a good balance between classification performance and model complexity, especially as the dataset instance count increases.     

Rejecting hydro-biogeochemical model structures by multi-criteria evaluation

This work presents a novel way for assessing and comparing different hydro-biogeochemical model structures and their performances. We used the LandscapeDNDC modelling framework to set up four models of different complexity, considering two soil-biogeochemical and two hydrological modules. The performance of each model combination was assessed using long-term (8 years) data and applying different thresholds, considering multiple criteria and objective functions. Our results show that each model combination had its strength for particular criteria. However, only 0.01% of all model runs passed the complete rejectionist framework. In contrast, our comparatively applied assessments of single thresholds, as frequently used in other studies, lead to a much higher acceptance rate of 40–70%. Therefore, our study indicates that models can be right for the wrong reasons, i.e., matching GHG emissions while at the same time failing to simulate other criteria such as soil moisture or plant biomass dynamics.     

Template matching using an improved electromagnetism-like algorithm

Template matching (TM) plays an important role in several image-processing applications such as feature tracking, object recognition, stereo matching, and remote sensing. The TM approach seeks for the best-possible resemblance between a subimage known as template and its coincident region within a source image. TM involves two critical aspects: similarity measurement and search strategy. The simplest available TM method aims for the best-possible coincidence between the images through an exhaustive computation of the normalized cross-correlation (NCC) values (similarity measurement) for all elements of the source image (search strategy). Recently, several TM algorithms that are based on evolutionary approaches have been proposed to reduce the number of NCC operations by calculating only a subset of search locations. In this paper, a new algorithm based on the electromagnetism-like algorithm (EMO) is proposed to reduce the number of search locations in the TM process. The algorithm uses an enhanced EMO version, which incorporates a modification of the local search procedure to accelerate the exploitation process. As a result, the new EMO algorithm can substantially reduce the number of fitness function evaluations while preserving the good search capabilities of the original EMO. In the proposed approach, particles represent search locations, which move throughout the positions of the source image. The NCC coefficient, considered as the fitness value (charge extent), evaluates the matching quality presented between the template image and the coincident region of the source image, for a determined search position (particle). The number of NCC evaluations is also reduced by considering a memory, which stores the NCC values previously visited to avoid the re-evaluation of the same search locations (particles). Guided by the fitness values (NCC coefficients), the set of candidate positions are evolved through EMO operators until the best-possible resemblance is determined. The conducted simulations show that the proposed method achieves the best balance over other TM algorithms in terms of estimation accuracy and computational cost.     

Evaluating spoken dialogue agents with PARADISE: Two case studies

This paper presents PARADISE (PARAdigm for DIalogue System Evaluation), a general framework for evaluating and comparing the performance of spoken dialogue agents. The framework decouples task requirements from an agent's dialogue behaviours, supports comparisons among dialogue strategies, enables the calculation of performance over subdialogues and whole dialogues, specifies the relative contribution of various factors to performance, and makes it possible to compare agents performing different taks by normalizing for task complexity. After presenting PARADISE, we illustrate its application to two different spoken dialogue agents. We show how to derive a performance function for each agent and how to generalize results across agents. We then show that once such a performance function has been derived, it can be used both for making predictions about future versions of an agent, and as feedback to the agent so that the agent can learn to optimize its behaviour based on its experiences with users over time.     

Reconfigurable swarm robots produce self-assembling and self-repairing organisms

Reconfigurable robots are set to become a vital factor in the theoretical development and practical utilization of robotics. The core problem in this scientific area is steady information transfer between a swarm and its organisms and vice versa. To this end, we present a basic theoretical framework that stipulates the interoperation between the two modes. We evaluate our proposed framework by constructing 100 mobile microrobots of three different types that initiate the processes of self-reconfigurability and self-repair. The autonomous decision to self-aggregate to an organism mainly derives from the necessity to overcome existing obstructive environmental conditions, e.g. ramps or clefts. The methodological dichotomy that we have chosen to evaluate our concept was to pursue in parallel an approach based on embodied distributed cognition and an evolutionary path mainly based on artificial genomes and reproduction. In this paper, we evaluate these two different approaches in two distinct grand challenges and present the main results.     

Learning concurrently data and rule bases of Mamdani fuzzy rule-based systems by exploiting a novel interpretability index

Interpretability of Mamdani fuzzy rule-based systems (MFRBSs) has been widely discussed in the last years, especially in the framework of multi-objective evolutionary fuzzy systems (MOEFSs). Here, multi-objective evolutionary algorithms (MOEAs) are applied to generate a set of MFRBSs with different trade-offs between interpretability and accuracy. In MOEFSs interpretability has often been measured in terms of complexity of the rule base and only recently partition integrity has also been considered. In this paper, we introduce a novel index for evaluating the interpretability of MFRBSs, which takes both the rule base complexity and the data base integrity into account. We discuss the use of this index in MOEFSs, which generate MFRBSs by concurrently learning the rule base, the linguistic partition granularities and the membership function parameters during the evolutionary process. The proposed approach has been experimented on six real world regression problems and the results have been compared with those obtained by applying the same MOEA, with only accuracy and complexity of the rule base as objectives. We show that our approach achieves the best trade-offs between interpretability and accuracy.     

A Modeling Framework for Troubleshooting Automotive Systems

This article presents a novel framework for modeling the troubleshooting process for automotive systems such as trucks and buses. We describe how a diagnostic model of the troubleshooting process can be created using event-driven, nonstationary, dynamic Bayesian networks. Exact inference in such a model is in general not practically possible. Therefore, we evaluate different approximate methods for inference based on the Boyen–Koller algorithm. We identify relevant model classes that have particular structure such that inference can be made with linear time complexity. We also show how models created using expert knowledge can be tuned using statistical data. The proposed learning mechanism can use data that is collected from a heterogeneous fleet of modular vehicles that can consist of different components. The proposed framework is evaluated both theoretically and experimentally on an application example of a fuel injection system.     

Evolutionary Multiobjective Optimization algorithm for multimedia delivery in critical applications through Content-Aware Networks

Critical applications which need to deliver multimedia through the Internet, may achieve the required quality of service thanks to the Content-Aware Networks (CAN). The key element of CAN is an efficient decision algorithm responsible for the selection of the best content source and routing paths for content delivery. This paper proposes a two-phase decision algorithm, exploiting the Evolutionary Multiobjective Optimization (EMO) approach. It allows to consider valid information in different time scales, adapting decision-maker to the evolving network and server conditions as well as to get the optimal solution in different shapes of Pareto front. The simulation experiments performed in a large-scale network model, confirm the effectiveness of the proposed two-phase EMO algorithm, comparing to other multi-criteria decision algorithms used in CAN.     

On Set-Based Multiobjective Optimization

Assuming that evolutionary multiobjective optimization (EMO) mainly deals with set problems, one can identify three core questions in this area of research: 1) how to formalize what type of Pareto set approximation is sought; 2) how to use this information within an algorithm to efficiently search for a good Pareto set approximation; and 3) how to compare the Pareto set approximations generated by different optimizers with respect to the formalized optimization goal. There is a vast amount of studies addressing these issues from different angles, but so far only a few studies can be found that consider all questions under one roof. This paper is an attempt to summarize recent developments in the EMO field within a unifying theory of set-based multiobjective search. It discusses how preference relations on sets can be formally defined, gives examples for selected user preferences, and proposes a general preference-independent hill climber for multiobjective optimization with theoretical convergence properties. Furthermore, it shows how to use set preference relations for statistical performance assessment and provides corresponding experimental results. The proposed methodology brings together preference articulation, algorithm design, and performance assessment under one framework and thereby opens up a new perspective on EMO.      

Distributed genetic algorithm for Gaussian mixture model based speaker identification

This paper presents a novel algorithm for reducing the computational complexity of identifying a speaker within a Gaussian mixture speaker model (GMM) framework. We have combined distributed genetic algorithm (DGA) and the Markov random field (MRF) to avoid typical local minima for speaker vector quantization. To improve the computation efficiency, only unstable chromosomes corresponding to speaker data parts are evolved. Identification accuracies of 93% were achieved for 100 Mandarin speakers.     

Bayesian graph edit distance

This paper describes a novel framework for comparing and matching corrupted relational graphs. The paper develops the idea of edit-distance originally introduced for graph-matching by Sanfeliu and Fu (1983). We show how the Levenshtein distance (1966) can be used to model the probability distribution for structural errors in the graph-matching problem. This probability distribution is used to locate matches using MAP label updates. We compare the resulting graph-matching algorithm with that recently reported by Wilson and Hancock. The use of edit-distance offers an elegant alternative to the exhaustive compilation of label dictionaries. Moreover, the method is polynomial rather than exponential in its worst-case complexity. We support our approach with an experimental study on synthetic data and illustrate its effectiveness on an uncalibrated stereo correspondence problem. This demonstrates experimentally that the gain in efficiency is not at the expense of quality of match     

Psychometric Evaluation of the EMO and the SUS in the Context of a Large-Sample Unmoderated Usability Study

This article describes the psychometric properties of the Emotional Metric Outcomes (EMO) questionnaire and the System Usability Scale (SUS) using data collected as part of a large-sample unmoderated usability study (n = 471). The EMO is a concise multifactor standardized questionnaire that provides an assessment of transaction-driven personal and relationship emotional outcomes, both positive and negative. The SUS is a well-known standardized usability questionnaire designed to assess perceived usability. In previous research, psychometric evaluation using data from a series of online surveys showed that the EMO and its component scales had high reliability and concurrent validity with loyalty and overall experience metrics but did not find the expected four-factor structure. Previous structural analyses of the SUS have had mixed results. Analysis of the EMO data from the usability study revealed the expected four-factor structure. The factor structure of the SUS appeared to be driven by item tone. The estimated reliability of the SUS (.90) was consistent with previous estimates. The EMO and its subscales were also quite reliable, with the estimates of reliability for the various EMO scales ranging from .86 to .96. Regression analysis using SUS, EMO, and Effort as predictors revealed different key drivers for the outcome metrics of Satisfaction and Likelihood-to-Recommend. The key recommendations are to include the EMO as part of the battery of poststudy standardized questionnaires, along with the SUS (or similar questionnaire), but to be cautious in reporting SUS subscales such as Usable and Learnable.     

Repertoires of collaboration: incorporation of social media help requests into the common operating picture

ABSTRACT

Disasters present us with dynamic and emergent multi-stakeholder scenarios. Complex decision-making is supported by Emergency Management Organisation (EMO) ‘command and control’ disaster response systems that if pushed to failure, present problems in the development and monitoring of situational awareness. Nowhere is this more evident than when the general public use social media platforms to report crisis incidents when the official emergency management hotline (e.g. Triple Zero (000) in Australia) is overwhelmed or not available. This causes a number of issues for EMO as it is difficult to verify and determine the accuracy and veracity of social media posts and how to best incorporate the information within them into situational awareness for the assessment of and response to, an emergency incident. This paper analyses interview data from five Australian EMO that outlines and discusses these issues in detail. As a result of this analysis, we suggest that developing a supplementary ‘repertoires of collaboration’ approach to incorporating social media posts into the development of situational awareness during a disaster event, would help improve disaster response outcomes. We then recommend a way forward through the application of the Negotiated Arrangements for the Common Operating Picture (COP) in Extreme Events framework.     

The complexity of soft constraint satisfaction

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of constraints to a corresponding set of algebraic operations, known as polymorphisms.In this paper we extend the analysis of complexity to the more general framework of combinatorial optimisation problems expressed using various forms of soft constraints. We launch a systematic investigation of the complexity of these problems by extending the notion of a polymorphism to a more general algebraic operation, which we call a multimorphism. We show that many tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms. We also show that a simple set of NP-hard constraints has very restricted multimorphisms. Finally, we use the notion of multimorphism to give a complete classification of complexity for the Boolean case which extends several earlier classification results for particular special cases.     

进化多目标优化算法研究

进化多目标优化主要研究如何利用进化计算方法求解多目标优化问题,已经成为进化计算领域的研究热点之一.在简要总结2003年以前的主要算法后,着重对进化多目标优化的最新进展进行了详细讨论.归纳出当前多目标优化的研究趋势,一方面,粒子群优化、人工免疫系统、分布估计算法等越来越多的进化范例被引入多目标优化领域,一些新颖的受自然系统启发的多目标优化算法相继提出;另一方面,为了更有效的求解高维多目标优化问题,一些区别于传统Pareto占优的新型占优机制相继涌现;同时,对多目标优化问题本身性质的研究也在逐步深入.对公认的代表性算法进行了实验对比.最后,对进化多目标优化的进一步发展提出了自己的看法.     

An Approach for Asynchronous Awareness Support in Collaborative Non-Linear Storytelling

Workspace awareness support is mandatory for group support systems. It allows users not only to follow actions of others, but to understand and respond to any changes others make to the workspace. In this paper, we present a novel approach for asynchronous awareness support by offering different filters to retrieve relevant awareness information and visualizing the evolution of the shared artifact. We illustrate our approach with a tool for collaborative non-linear storytelling in which users can jointly create a story graph of interconnected audio files. Such a story graph is an example for a non-linear story. We describe the development of a prototype that visualizes how the collaborative story has evolved over time. We evaluate our approach for asynchronous awareness support in an experiment with 40 participants exploring story graphs of different complexity. The evaluation results show that our visualization approach helps group members to assess who has modified the shared story, how it was modified, what exactly has been modified, and when it has been modified.     

Automatically composing and parameterizing skills by evolving Finite State Automata

We propose a robotics algorithm that is able to simultaneously combine, adapt and create actions to solve a task. The actions are combined in a Finite State Automaton whose structure is determined by a novel evolutionary algorithm. The actions parameters, or new actions, are evolved alongside the FSA topology. Actions can be combined together in a hierarchical fashion. This approach relies on skills that with which the robot is already provided, like grasping or motion planning. Therefore software reuse is an important advantage of our proposed approach. We conducted several experiments both in simulation and on a real mobile manipulator PR2 robot, where skills of increasing complexity are evolved. Our results show that (i) an FSA generated in simulation can be directly applied to a real robot without modifications and (ii) the evolved FSA is robust to the noise and the uncertainty arising from real-world sensors.     

Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling

This paper shows how the performance of evolutionary multiobjective optimization (EMO) algorithms can be improved by hybridization with local search. The main positive effect of the hybridization is the improvement in the convergence speed to the Pareto front. On the other hand, the main negative effect is the increase in the computation time per generation. Thus, the number of generations is decreased when the available computation time is limited. As a result, the global search ability of EMO algorithms is not fully utilized. These positive and negative effects are examined by computational experiments on multiobjective permutation flowshop scheduling problems. Results of our computational experiments clearly show the importance of striking a balance between genetic search and local search. In this paper, we first modify our former multiobjective genetic local search (MOGLS) algorithm by choosing only good individuals as initial solutions for local search and assigning an appropriate local search direction to each initial solution. Next, we demonstrate the importance of striking a balance between genetic search and local search through computational experiments. Then we compare the modified MOGLS with recently developed EMO algorithms: the strength Pareto evolutionary algorithm and revised nondominated sorting genetic algorithm. Finally, we demonstrate that a local search can be easily combined with those EMO algorithms for designing multiobjective memetic algorithms.