Optimizing the body and brain of a robot is a coupled challenge: the morphology determines what control strategies are effective, while the control parameters influence how well the morphology performs. This joint optimization can be done through nested loops of evolutionary and learning processes, where the control parameters of each robot are learned independently. However, the control parameters learned by one robot may contain valuable information for others. Thus, we introduce a social learning approach in which robots can exploit optimized parameters from their peers to accelerate their own brain optimization. Within this framework, we systematically investigate how the selection of teachers, deciding which and how many robots to learn from, affects performance, experimenting with virtual soft robots in four tasks and environments. In particular, we study the effect of inheriting experience from morphologically similar robots due to the tightly coupled body and brain in robot optimization. Our results confirm the effectiveness of building on others' experience, as social learning clearly outperforms learning from scratch under equivalent computational budgets. In addition, while the optimal teacher selection strategy remains open, our findings suggest that incorporating knowledge from multiple teachers can yield more consistent and robust improvements.

Multi-task policy search is a challenging problem because policies are required to generalize beyond training cases. Curriculum learning has proven to be effective in this setting, as it introduces complexity progressively. However, designing effective curricula is labor-intensive and requires extensive domain expertise. LLM-based curriculum generation has only recently emerged as a potential solution, but was limited to operate in static, offline modes without leveraging real-time feedback from the optimizer. Here we propose an interactive LLM-assisted framework for online curriculum generation, where the LLM adaptively designs training cases based on real-time feedback from the evolutionary optimization process. We investigate how different feedback modalities, ranging from numeric metrics alone to combinations with plots and behavior visualizations, influence the LLM ability to generate meaningful curricula. Through a 2D robot navigation case study, tackled with genetic programming as optimizer, we evaluate our approach against static LLM-generated curricula and expert-designed baselines. We show that interactive curriculum generation outperforms static approaches, with multimodal feedback incorporating both progression plots and behavior visualizations yielding performance competitive with expert-designed curricula. This work contributes to understanding how LLMs can serve as interactive curriculum designers for embodied AI systems, with potential extensions to broader evolutionary robotics applications.

On the path towards truly autonomous robots, embodied agents will require to be adaptable to unforeseen circumstances. Yet, most robotic agents still suffer from significant performance degradation when scenarios change slightly, with many even failing their tasks entirely. In contrast, organisms in nature exhibit strong adaptability, largely due to bio-diversity, which has prevented the extinction of life throughout severe environmental changes. The concept of quality-diversity aims to emulate this natural resilience, yielding robust results through diversification of embodied agents in the behavior space. However, in nature, diversity occurs simultaneously at multiple levels: body, brain, and behavior. This study on the body-brain optimization of virtual embodied agents spans two brain representations—an Artificial Neural Network (ANN) and a graph—and investigates these levels to determine the most critical scope for diversity in fostering performance, generality, and robustness. We start by optimizing for a simple locomotion task, and then evaluate generality through transfer to a diverse set of tasks, including locomotion in new environments and interaction with objects. Our findings confirm the importance of simultaneously considering multiple axes of diversity for achieving good performance and adaptability—demonstrating zero-shot transfer on 18 new tasks. Moreover, we observe that the graph controller performs on par with the ANN, offering greater interpretability.

Curriculum learning (CL) consists in using a diverse set of user-provided test cases, with varying levels of difficulty and organized in a suitable progression, for learning a policy. The quality of test cases is important to allow optimization techniques as genetic programming (GP) to solve policy search problems. In this work, we evaluate large language models (LLMs) as providers of test cases for GP-based policy search. We consider two policy search tasks, a single-player and a multi-player game, and four LLMs differing in complexity and specialization, which we prompt in order to generate suitable test cases for the two games. We experimentally assess the intrinsic quality of LLM-generated test cases and their utility when inserted in a curriculum consumed by a GP optimization. We evaluate the robustness of the approach with respect to the way cases are scheduled in curricula and with respect to the policy representation, for which we use both graphs and linear programs evolved by GP. We observe that the effectiveness of LLM-assisted CL depends on both the choice of LLM and the design of the prompting and scheduling strategies. These findings highlight important considerations for leveraging LLMs in automated curriculum design for GP-based optimization.

Modeling the relationships between variables through probability distributions lies at the core of probabilistic models, enabling reasoning under uncertainty. Probabilistic programming offers an effective way to represent these models by blending the simplicity of standard programming constructs with the power of automatic inference algorithms. The languages for expressing probabilistic programs are augmented with primitives representing various probability distributions to effectively capture the stochastic behavior inherent in the data. However, writing a probabilistic program is hard, because it typically requires prior knowledge about the data generation mechanism. In this work, we propose a framework for automatically synthesizing probabilistic programs directly from data, thereby learning the underlying relationships between variables and the data-generating process. We adopt an evolutionary approach, specifically grammatical evolution (GE), to extensively explore the space of probabilistic programs, aiming to discover the most likely program that describes the observed data. We experimentally evaluate our method across several benchmarks, incorporating varying levels of prior knowledge through a sketching strategy embedded into the grammar fed to GE, to demonstrate the potential of this evolutionary framework. This evaluation highlights the flexibility and effectiveness of GE in synthesizing probabilistic programs under different informational constraints.

August 16 2024 Editorial: Special Issue "The Distributed Ghost"—Cellular Automata, Distributed Dynamical Systems, and Their Applications to Intelligence In Special Collection: CogNet Stefano Nichele, Stefano Nichele Østfold University College, NorwayOslo Metropolitan University, Norway Search for other works by this author on: This Site Google Scholar Hiroki Sayama, Hiroki Sayama Binghamton University, USAWaseda University, Japan Search for other works by this author on: This Site Google Scholar Eric Medvet, Eric Medvet University of Trieste, Italy Search for other works by this author on: This Site Google Scholar Chrystopher Nehaniv, Chrystopher Nehaniv University of Waterloo, Canada Search for other works by this author on: This Site Google Scholar Mario Pavone Mario Pavone University of Catania, Italy Search for other works by this author on: This Site Google Scholar Author and Article Information Stefano Nichele Østfold University College, NorwayOslo Metropolitan University, Norway Hiroki Sayama Binghamton University, USAWaseda University, Japan Eric Medvet University of Trieste, Italy Chrystopher Nehaniv University of Waterloo, Canada Mario Pavone University of Catania, Italy Online ISSN: 1530-9185 Print ISSN: 1064-5462 © 2024 Massachusetts Institute of Technology2024Massachusetts Institute of Technology Artificial Life 1–3. https://doi.org/10.1162/artl_e_00450 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn Email Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Stefano Nichele, Hiroki Sayama, Eric Medvet, Chrystopher Nehaniv, Mario Pavone; Editorial: Special Issue "The Distributed Ghost"—Cellular Automata, Distributed Dynamical Systems, and Their Applications to Intelligence. Artif Life 2024; doi: https://doi.org/10.1162/artl_e_00450 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsArtificial Life Search Advanced Search This content is only available as a PDF. © 2024 Massachusetts Institute of Technology2024Massachusetts Institute of Technology Article PDF first page preview Close Modal You do not currently have access to this content.

Describing the properties of complex systems that evolve over time is a crucial requirement for monitoring and understanding them. Signal Temporal Logic (STL) is a framework that proved to be effective for this aim because it is expressive and allows state properties as human-readable formulae. Crafting STL formulae that fit a particular system is, however, a difficult task. For this reason, a few approaches have been proposed recently for the automatic learning of STL formulae starting from observations of the system. In this paper, we propose BUSTLE (Bi-level Universal STL Evolver), an approach based on evolutionary computation for learning STL formulae from data. BUSTLE advances the state of the art because it (i) applies to a broader class of problems, in terms of what is known about the state of the system during its observation, and (ii) generates both the structure and the values of the parameters of the formulae employing a bi-level search mechanism (global for the structure, local for the parameters). We consider two cases where (a) observations of the system in both anomalous and regular state are available, or (b) only observations of regular state are available. We experimentally evaluate BUSTLE on problem instances corresponding to the two cases and compare it against previous approaches. We show that the evolved STL formulae are effective and human-readable: the versatility of BUSTLE does not come at the cost of lower effectiveness.

Multi-cellular organisms typically originate from a single cell, the zygote, that then develops into a multitude of structurally and functionally specialized cells. The potential of generating all the specialized cells that make up an organism is referred to as cellular ‘‘totipotency’’, a concept introduced by the German plant physiologist Haberlandt in the early 1900s. In an attempt to reproduce this mechanism in synthetic organisms, we present a model based on a kind of modular robot called Voxel-based Soft Robot (VSR), where both the body, i.e., the arrangement of voxels, and the brain, i.e., the Artificial Neural Network (ANN) controlling each module, are subject to an evolutionary process aimed at optimizing the locomotion capabilities of the robot. In an analogy between totipotent cells and totipotent ANN-controlled modules, we then include in our model an additional level of adaptation provided by Hebbian learning, which allows the ANNs to adapt their weights during the execution of the locomotion task. Our in silico experiments reveal two main findings. Firstly, we confirm the common intuition that Hebbian plasticity effectively allows better performance and adaptation. Secondly and more importantly, we verify for the first time that the performance improvements yielded by plasticity are in essence due to a form of specialization at the level of single modules (and their associated ANNs): thanks to plasticity, modules specialize to react in different ways to the same set of stimuli, i.e., they become functionally and behaviorally different even though their ANNs are initialized in the same way. This mechanism, which can be seen as a form of totipotency at the level of ANNs, can have, in our view, profound implications in various areas of Artificial Intelligence (AI) and applications thereof, such as modular robotics and multi-agent systems.

Genetic programming (GP) is a popular problem-solving and optimization technique. However, generating effective test cases for training and evaluating GP programs requires strong domain knowledge. Furthermore, GP programs often prematurely converge on local optima when given excessively difficult problems early in their training. Curriculum learning (CL) has been effective in addressing similar issues across different reinforcement learning (RL) domains, but it requires the manual generation of progressively difficult test cases as well as their careful scheduling. In this work, we leverage the domain knowledge and the strong generative abilities of large language models (LLMs) to generate effective test cases of increasing difficulties and schedule them according to various curricula. We show that by integrating a curriculum scheduler with LLM-generated test cases we can effectively train a GP agent player with environments-based curricula for a single-player game and opponent-based curricula for a multi-player game. Finally, we discuss the benefits and challenges of implementing this method for other problem domains.

Graph-based Genetic Programming (GGP) can create interpretable control policies in graph form, but faces challenges such as local optima and solution fragility, which undermine its efficacy. Quality-Diversity (QD) has been effective in addressing similar issues, traditionally in Artificial Neural Network (ANN) optimization. In this paper, we introduce a general Graph Quality-Diversity (G-QD) framework to enhance the performance of GGP with QD optimization, obtaining a variety of interpretable, effective, and resilient policies. Using Cartesian Genetic Programming (CGP) as the GGP technique and MAP-Elites (ME) as the QD algorithm, we leverage a combination of behavior and graph structural descriptors. Experimenting on two navigation and two locomotion continuous control tasks, our framework yields an array of effective yet behaviorally and structurally diverse policies, surpassing the performance of a standard Genetic Algorithm (GA). The resulting solution set also increases interpretability, allowing for insight into the control tasks. Additionally, our experiments demonstrate the robustness of the solutions to faults such as sensor damage.

Cellular automata (CA) are a convenient way to describe the distributed evolution of a dynamical system over discrete time and space.They can be used to express evolutionary algorithms (EAs), where the time is the flow of iterations and the space is where the population is hosted.When the CA evolves over a finite grid of cells, the substrate, each cell hosts an individual and the CA rule applies variation operators using the local and neighbor individuals.In this paper, we explore the possibility of enforcing a structure on the substrate.Instead of a flat toroidal grid, we use substrates where some empty cells never host individuals.These cells may act as barriers, slowing down the propagation of genetic traits and hence potentially improving the population diversity, eventually mitigating the risk of premature convergence.We experimentally evaluate the impact of these substrates using a simple CA-based EA on multi-modal and multi-objective problems.We find evidence of a positive impact in some circumstances; on multi-modal problems, convergence is slightly faster and the EA more often reaches all the targets.

Modular robots are collections of simple embodied agents, the modules, that interact with each other to achieve complex behaviors. Each module may have a limited capability of perceiving the environment and performing actions; nevertheless, by behaving coordinately, and possibly by sharing information, modules can collectively perform complex actions. In principle, the greater the actuation, perception, and communication abilities of the single module are the more effective is the collection of modules. However, improved abilities also correspond to more complex controllers and, hence, larger search spaces when designing them by means of optimization. In this article, we analyze the impact of perception, actuation, and communication abilities on the possibility of obtaining good controllers for simulated modular robots, that is, controllers that allow the robots to exhibit collective intelligence. We consider the case of modular soft robots, where modules can contract, expand, attach, and detach from each other, and make them face two tasks (locomotion and piling), optimizing their controllers with evolutionary computation. We observe that limited abilities often do not prevent the robots from succeeding in the task, a finding that we explain with (a) the smaller search space corresponding to limited actuation, perception, and communication abilities, which makes the optimization easier, and (b) the fact that, for this kind of robot, morphological computation plays a significant role. Moreover, we discover that what matters more is the degree of collectivity the robots are required to exhibit when facing the task.

Interpretability is a critical aspect to ensure a fair and responsible use of machine learning (ML) in high-stakes applications. Genetic programming (GP) has been used to obtain interpretable ML models because it operates at the level of functional building blocks: if these building blocks are interpretable, there is a chance that their composition (i.e., the entire ML model) is also interpretable. However, the degree to which a model is interpretable depends on the observer. Motivated by this, we study a recently-introduced human-in-the-loop system that allows the user to steer GP’s generation process to their preferences, which shall be online-learned by an artificial neural network (ANN). We focus on the generation of ML models as analytical functions (i.e., symbolic regression) as this is a key problem in interpretable ML, and propose a two-fold contribution. First, we devise more general representations for the ML models for the ANN to learn upon, to enable the application of the system to a wider range of problems. Second, we delve into a deeper analysis of the system’s components. To this end, we propose an incremental experimental evaluation, aimed at (1) studying the effectiveness by which an ANN can capture the perceived interpretability for simulated users, (2) investigating how the GP’s outcome is affected across different simulated user feedback profiles, and (3) determining whether humans participants would prefer models that were generated with or without their involvement. Our results pose clarity on pros and cons of using a human-in-the-loop approach to discover interpretable ML models with GP.

Graphs are a way to describe complex entities and their relations that apply to many practically relevant domains. However, domains often differ not only in the properties of nodes and edges, but also in the constraints imposed to the overall structure. This makes hard to define a general representation and genetic operators for graphs that permit the evolutionary optimization over many domains. In this paper, we tackle this challenge. We first propose a representation template that can be customized by users for specific domains: the constraints and the genetic operators are given in Prolog, a declarative programming language for operating with logic. Then, we define an adaptive evolutionary algorithm that can work with a large number of genetic operators by modifying their usage probability during the evolution: in this way, we relieve the user from the burden of selecting in advance only operators that are "good enough". We experimentally evaluate our proposal on two radically different domains to demonstrate its applicability and effectiveness: symbolic regression with trees and text extraction with finite-state automata. The results are promising: our approach does not trade effectiveness for versatility and is not worse than other domain-tailored approaches.

Modular robots are promising for their versatility and large design freedom. Modularity can also enable automatic assembly and reconfiguration, be it autonomous or via external machinery. However, these procedures are error-prone and often result in misassemblings. This, in turn, can cause catastrophic effects on the robot functionality, as the controller deployed in each module is optimized for a different robot shape than the actual one. In this work, we address such shortcoming by proposing a shape-aware modular controller, operating with (1) a self-discovery phase, in which each module controller identifies the shape it is assembled in, followed by (2) a parameter selection phase, where the controller selects its parameters according to the inferred shape. We deploy a self-classifying neural cellular automaton for phase (1), and we leverage evolutionary optimization for implementing a library of controller parameters for phase (2). We test the validity of the proposed method considering voxel-based soft robots, a class of modular soft robots, and the task of locomotion. Our findings confirm the effectiveness of such a controller paradigm, and also show that it can be used to partially overcome unforeseen damages or assembly mistakes.

Embedding the learning of controllers within the evolution of morphologies has emerged as an effective strategy for the co-optimization of agents' bodies and brains. Intuitively, that is how nature shaped animal life on Earth. Still, the design of such co-optimization is a complex endeavor; one issue is the choice of the genetic encoding for the morphology. Such choice can be crucial for the effectiveness of learning, i.e., how fast and to what degree agents adapt, through learning, during their life. Here we evolve the morphologies of voxel-based soft agents with two different encodings, direct and indirect while learning the controllers with reinforcement learning. We experiment with three tasks, ranging from cave crawling to beam toppling, and study how the encoding influences the learning outcome. Our results show that the direct encoding corresponds to increased ability to learn, mostly in terms of learning speed. The same is not always true for the indirect one. We link these results to different shades of the Baldwin effect, consisting of morphologies being selected for increasing an agent's ability to learn during its lifetime.

A vital component of intelligent action is affordance detection: understanding what actions external objects afford the viewer. This requires the agent to understand the physical nature of the object being viewed, its own physical nature, and the potential relationships possible when they interact. Although robotics researchers have investigated affordance detection, the way in which the morphology of the robot facilitates, obstructs, or otherwise influences the robot's ability to detect affordances has yet to be studied. We do so here and find that a robot with an appropriate morphology can evolve to predict whether it will fit through an aperture with just minimal tactile feedback. We also find that some robot morphologies facilitate the evolution of more accurate affordance detection, while others do not if all have the same evolutionary optimization budget. This work demonstrates that sensation, thought, and action are necessary but not sufficient for understanding how affordance detection may evolve in organisms or robots: morphology must also be taken into account. It also suggests that, in the future, we may optimize morphology along with control in order to facilitate affordance detection in robots, and thus improve their reliable and safe action in the world.

In many natural environments, different forms of living organisms successfully accomplish the same task while being diverse in shape and behavior. This biodiversity is what made life capable of adapting to disrupting changes. Being able to reproduce biodiversity in artificial agents, while still optimizing them for a particular task, might increase their applicability to scenarios where human response to unexpected changes is not possible. In this work, we focus onVoxel-based Soft Robots(VSRs), a form of robots that grants great freedom in the design of both morphology and controller and is hence promising in terms of biodiversity. We useevolutionary computationfor optimizing, at the same time, morphology and controller of VSRs for the task of locomotion. We investigate experimentally whether three key factors—representation, Evolutionary Algorithm (EA), and environment—impact the emergence of biodiversity and if this occurs at the expense of effectiveness. We devise an automatic machine learning pipeline for systematically characterizing the morphology and behavior of robots resulting from the optimization process. We classify the robots into species and then measure biodiversity in populations of robots evolved in a multitude of conditions resulting from the combination of different morphology representations, controller representations, EAs, and environments. The experimental results suggest that, in general, EA and environment matter more than representation. We also propose a novel EA based on a speciation mechanism that operates on morphology and behavior descriptors and we show that it allows to jointly evolve morphology and controller of effective and diverse VSRs.

Modularity in robotics holds great potential. In principle, modular robots can be disassembled and reassembled in different robots, and possibly perform new tasks. Nevertheless, actually exploiting modularity is yet an unsolved problem: controllers usually rely on inter-module communication, a practical requirement that makes modules not perfectly interchangeable and thus limits their flexibility. Here, we focus on Voxel-based Soft Robots (VSRs), aggregations of mechanically identical elastic blocks. We use the same neural controller inside each voxel, but without any inter-voxel communication, hence enabling ideal conditions for modularity: modules are all equal and interchangeable. We optimize the parameters of the neural controller---shared among the voxels---by evolutionary computation. Crucially, we use a local self-attention mechanism inside the controller to overcome the absence of inter-module communication channels, thus enabling our robots to truly be driven by the collective intelligence of their modules. We show experimentally that the evolved robots are effective in the task of locomotion: thanks to self-attention, instances of the same controller embodied in the same robot can focus on different inputs. We also find that the evolved controllers generalize to unseen morphologies, after a short fine-tuning, suggesting that an inductive bias related to the task arises from true modularity.1

Modularity is a desirable property for embodied agents, as it could foster their suitability to different domains by disassembling them into transferable modules that can be reassembled differently. We focus on a class of embodied agents known as voxel-based soft robots (VSRs). They are aggregations of elastic blocks of soft material; as such, their morphologies are intrinsically modular. Nevertheless, controllers used until now for VSRs act as abstract, disembodied processing units: Disassembling such controllers for the purpose of module transferability is a challenging problem. Thus, the full potential of modularity for VSRs still remains untapped. In this work, we propose a novel self-organizing, embodied neural controller for VSRs. We optimize it for a given task and morphology by means of evolutionary computation: While evolving, the controller spreads across the VSR morphology in a way that permits emergence of modularity. We experimentally investigate whether such a controller (i) is effective and (ii) allows tuning of its degree of modularity, and with what kind of impact. To this end, we consider the task of locomotion on rugged terrains and evolve controllers for two morphologies. Our experiments confirm that our self-organizing, embodied controller is indeed effective. Moreover, by mimicking the structural modularity observed in biological neural networks, different levels of modularity can be achieved. Our findings suggest that the self-organization of modularity could be the basis for an automatic pipeline for assembling, disassembling, and reassembling embodied agents.

In many natural environments, there are different forms of living creatures that successfully accomplish the same task while being diverse in shape and behavior. This biodiversity is what made life capable of adapting to disrupting changes. Being able to reproduce biodiversity in non-biological agents, while still optimizing them for a particular task, might increase their applicability to scenarios where human response to unexpected changes is not possible.

We describe the design and implementation of a system for executing search-and-replace text processing tasks automatically, based only on examples of the desired behavior. The examples consist of pairs describing the original string and the desired modified string. Their construction, thus, does not require any specific technical skill. The system constructs a solution to the specified task that can be used unchanged on popular existing software for text processing. The solution consists of a search pattern coupled with a replacement expression: the former is a regular expression which describes both the strings to be replaced and their portions to be reused in the latter, which describes how to build the modified strings. Our proposed system is internally based on genetic programming and implements a form of cooperative coevolution in which two separate populations are evolved independently, one for search patterns and the other for replacement expressions. We assess our proposal on six tasks of realistic complexity obtaining very good results, both in terms of absolute quality of the solutions and with respect to the challenging baselines considered.

Voxel-based soft robots (VSRs) are aggregations of elastic, cubic blocks that have sparkled the interest of Robotics and Artificial Life researchers. VSRs can move by varying the volume of individual blocks, according to control signals dictated by a controller, possibly based on inputs coming from sensors embedded in the blocks. Neural networks (NNs) have been used as centralized processing units for those sensing controllers, with weights optimized using evolutionary computation. This structuring breaks the intrinsic modularity of VSRs: decomposing a VSR into modules to be assembled in a different way is very hard.

In recent years, Artificial Neural Networks (ANNs) pruning has become the focal point of many researches, due to the extreme overparametrization of such models. This has urged the scientific world to investigate methods for the simplification of the structure of weights in ANNs, mainly in an effort to reduce time for both training and inference. Frankle and Carbin [1], and later Renda, Frankle, and Carbin [2] introduced and refined an iterative pruning method which is able to effectively prune the network of a great portion of its parameters with little to no loss in performance. On the downside, this method requires a large amount of time for its application, since, for each iteration, the network has to be trained for (almost) the same amount of epochs of the unpruned network. In this work, we show that, for a limited setting, if targeting high overall sparsity rates, this time can be effectively reduced for each iteration, save for the last one, by more than 50%, while yielding a final product (i.e., final pruned network) whose performance is comparable to the ANN obtained using the existing method.

During the last few decades, artificial neural networks (ANN) have achieved an enormous success in regression and classification tasks. The empirical success has not been matched with an equally strong theoretical understanding of such models, as some of their working principles (training dynamics, generalization properties, and the structure of inner representations) still remain largely unknown. It is, for example, particularly difficult to reconcile the well known fact that ANNs achieve remarkable levels of generalization also in conditions of severe over-parametrization. In our work, we explore a recent network compression technique, called Iterative Magnitude Pruning (IMP), and apply it to convolutional neural networks (CNN). The pruned and unpruned models are compared layer-wise with Canonical Correlation Analysis (CCA). Our results show a high similarity between layers of pruned and unpruned CNNs in the first convolutional layers and in the fully-connected layer, while for the intermediate convolutional layers the similarity is significantly lower. This suggests that, although in intermediate layers representation in pruned and unpruned networks is markedly different, in the last part the fully-connected layers act as pivots, producing not only similar performances but also similar representations of the data, despite the large difference in the number of parameters involved.

We consider the task of segmentation of images of mosaics, where the goal is to segment the image in such a way that each region corresponds exactly to one tile of the mosaic. We propose to use a recent deep learning technique based on a kind of convolutional neural networks, called U-net, that proved to be effective in segmentation tasks. Our method includes a preprocessing phase that allows to learn a U-net despite the scarcity of labeled data, which reflects the peculiarity of the task, in which manual annotation is, in general, costly. We experimentally evaluate our method and compare it against the few other methods for mosaic images segmentation using a set of performance indexes, previously proposed for this task, computed using 11 images of real mosaics. In our results, U-net compares favorably with previous methods. Interestingly, the considered methods make errors of different kinds, consistently with the fact that they are based on different assumptions and techniques. This finding suggests that combining different approaches might lead to an even more effective segmentation.

Grammatical evolution (GE) is one of the most widespread techniques in evolutionary computation. Genotypes in GE are bit strings while phenotypes are strings, of a language defined by a user-provided context-free grammar. In this paper, we propose a novel procedure for mapping genotypes to phenotypes that we call weighted hierarchical GE (WHGE). WHGE imposes a form of hierarchy on the genotype and encodes grammar symbols with a varying number of bits based on the relative expressive power of those symbols. WHGE does not impose any constraint on the overall GE framework, in particular, WHGE may handle recursive grammars, uses the classical genetic operators, and does not need to define any bound in advance on the size of phenotypes. We assessed experimentally our proposal in depth on a set of challenging and carefully selected benchmarks, comparing the results of the standard GE framework as well as two of the most significant enhancements proposed in the literature: 1) position-independent GE and 2) structured GE. Our results show that WHGE delivers very good results in terms of fitness as well as in terms of the properties of the genotype-phenotype mapping procedure.

Context-free grammars are useful tools for modeling the solution space of problems that can be solved by optimization algorithms. For a given solution space, there exists an infinite number of grammars defining that space, and there are clues that changing the grammar may impact the effectiveness of the optimization. In this article, we investigate theoretically and experimentally the possibility of specializing a grammar in a problem, that is, of systematically improving the quality of the grammar for the given problem. To this end, we define the quality of a grammar for a problem in terms of the average fitness of the candidate solutions generated using that grammar. Theoretically, we demonstrate the following findings: 1) that a simple mutation operator employed in a (1 + 1)-EA setting can be used to specialize a grammar in a problem without changing the solution space defined by the grammar and 2) that three grammars of equal quality for a grammar-based version of the ONEMAX problem greatly vary in how they can be specialized with that (1 + 1)-EA, as the expected time required to obtain the same improvement in quality can vary exponentially among grammars. Then, experimentally, we validate the theoretical findings and extend them to other problems, grammars, and a more general version of the mutation operator.

Current signature detection mechanisms can be easily evaded by malware writers by applying obfuscation techniques. Employing morphing code techniques, attackers are able to generate several variants of one malicious sample, making the corresponding signature obsolete. Considering that the signature definition is a laborious process manually performed by security analysts, in this paper we propose a method, exploiting static analysis and Machine Learning classification algorithms, to identify whether a mobile application is modified by means of one or more morphing techniques. We perform experiments on a real-world dataset of Android applications (morphed and original), obtaining encouraging results in the obfuscation technique(s) identification.

WPA2 Enterprise is a fundamental technology for secure communication in enterprise wireless networks. A key requirement of this technology is that WiFi-enabled devices (i.e., supplicants) be correctly configured before connecting to the enterprise wireless network. Supplicants that are not configured correctly may fall prey of attacks aimed at stealing the network credentials very easily. Such credentials have an enormous value because they usually unlock access to all enterprise services.

The huge diffusion of malware in mobile platform is plaguing users. New malware proliferates at a very fast pace: as a matter of fact, to evade the signature-based mechanism implemented in current antimalware, the application of trivial obfuscation techniques to existing malware is sufficient. In this paper, we show how the application of several morphing techniques affects the effectiveness of two widespread malware detection approaches based on Machine Learning coupled respectively with static and dynamic analysis. We demonstrate experimentally that dynamic analysis-based detection performs equally well in evaluating obfuscated and non-obfuscated malware. On the other hand, static analysis-based detection is more accurate on non-obfuscated samples but is greatly negatively affected by obfuscation: however, we also show that this effect can be mitigated by using obfuscated samples also in the learning phase.

Malware signature extraction is currently a manual and a time-consuming process. As a matter of fact, security analysts have to manually inspect samples under analysis in order to find the malicious behavior. From research side, current literature is lacking of methods focused on the malicious behavior localization: designed approaches basically mark an entire application as malware or non-malware (i.e., take a binary decision) without knowledge about the malicious behavior localization inside the analysed sample. In this paper, with the twofold aim of assisting the malware analyst in the inspection process and of pushing the research community in malicious behavior localization, we propose VizMal, a tool for visualizing the dynamic trace of an Android application which highlights the portions of the application which look potentially malicious. VizMal performs a detailed analysis of the application activities showing for each second of the execution whether the behavior exhibited is legitimate or malicious. The analyst may hence visualize at a glance when at to which degree an application execution looks malicious.

We consider the automatic synthesis of an entity extractor, in the form of a regular expression, from examples of the desired extractions in an unstructured text stream. This is a long-standing problem for which many different approaches have been proposed, which all require the preliminary construction of a large dataset fully annotated by the user. In this paper, we propose an active learning approach aimed at minimizing the user annotation effort: the user annotates only one desired extraction and then merely answers extraction queries generated by the system. During the learning process, the system digs into the input text for selecting the most appropriate extraction query to be submitted to the user in order to improve the current extractor. We construct candidate solutions with genetic programming (GP) and select queries with a form of querying-by-committee, i.e., based on a measure of disagreement within the best candidate solutions. All the components of our system are carefully tailored to the peculiarities of active learning with GP and of entity extraction from unstructured text. We evaluate our proposal in depth, on a number of challenging datasets and based on a realistic estimate of the user effort involved in answering each single query. The results demonstrate high accuracy with significant savings in terms of computational effort, annotated characters, and execution time over a state-of-the-art baseline.

Evolvability is a measure of the ability of an Evolutionary Algorithm (EA) to improve the fitness of an individual when applying a genetic operator. Other than the specific problem, many aspects of the EA may impact on the evolvability most notably the genetic operators and, if present, the genotype-phenotype mapping function. Grammatical Evolution (GE) is an EA in which the mapping function plays a crucial role since it allows to map any binary genotype into a program expressed in any user-provided language, defined by a context-free grammar. While GE mapping favored a successful application of GE to many different problems, it has also been criticized for scarcely adhering to the variational inheritance principle, which itself may hamper GE evolvability. In this paper, we experimentally study GE evolvability in different conditions, that is, problems, mapping functions, genotype sizes, and genetic operators. Results suggest that there is not a single factor determining GE evolvability: in particular, the mapping function alone does not deliver better evolvability regardless of the problem. Instead, GE redundancy, which itself is the result of the combined effect of several factors, has a strong impact on the evolvability.

Unmanned Aerial Vehicles (UAVs) are becoming increasingly popular and the amount of UAV traffic in urban environments will largely increase in the future, due to profitable tasks which are particularly suited to UAVs, e.g., parcel delivery and surveillance, in particular in the context of smart cities. Trying to ensure the traffic safety and efficiency by acting on the UAV controller alone might be challenging, since the set of involved players (regulators, manufacturers, business users) is large and diversified. In this work, we address this problem by proposing a language for defining rules suitable for UAV traffic which can be enforced in a decentralized way by the UAVs themselves, without any need for communication and regardless of the UAV navigation algorithm. The language allows to express realistic rules, such as ``when cruising, keep a minimum altitude'', concisely and such that they can be processed online by each single UAV basing on its perception of the nearby environment. We experimentally validate the ability of our proposal to impact on the UAV traffic efficiency and safety by performing a large number of simulations with and without a set of realistic rules.

While mobile devices have become more pervasive every day, the interest in them from attackers has also been increasing, making effective malware detection tools of ultimate importance for malware investigation and user protection. Most informative malware identification techniques are the ones that are able to identify where the malicious behavior is located in applications. In this way, better understanding of malware can be achieved and effective tools for its detection can be written. However, due to complexity of such a task, most of the current approaches just classify applications as malicious or benign, without giving any further insights. In this work, we propose a technique for automatic analysis of mobile applications which allows its users to automatically identify the sub-sequences of execution traces where malicious activity happens, hence making further manual analysis and understanding of malware easier. Our technique is based on dynamic features concerning resources usage and system calls, which are jointly collected while the application is executed. An execution trace is then split in shorter chunks that are analyzed with machine learning techniques to detect local malicious behaviors. Obtained results on the analysis of 3,232 Android applications show that collected features contain enough information to identify suspicious execution traces that should be further analysed and investigated.

The rapid growth in smartphone and tablet usage over the last years has led to the inevitable rise in targeting of these devices by cyber-criminals. The exponential growth of Android devices, and the buoyant and largely unregulated Android app market, produced a sharp rise in malware targeting that platform. Furthermore, malware writers have been developing detection-evasion techniques which rapidly make anti-malware technologies ineffective. It is hence advisable that security expert are provided with tools which can aid them in the analysis of existing and new Android malware. In this paper, we explore the use of topic modeling as a technique which can assist experts to analyse malware applications in order to discover their characteristic. We apply Latend Dirichlet Allocation (LDA) to mobile applications represented as opcode sequences, hence considering a topic as a discrete distribution of opcode. Our experiments on a dataset of 900 malware applications of different families show that the information provided by topic modeling may help in better understanding malware characteristics and similarities.

We consider the problem of the filtering of Twitter posts, that is, the hiding of those posts which the user prefers not to visualize on his/her timeline. We define a language for specifying filtering policies suitable for Twitter posts. The language allows each user to decide which posts to filter out based on his/her sensibility and preferences. Since average users may not have the skills necessary to translate their filtering needs into a set of rules, we also propose a method for inferring a policy automatically, based solely on examples of the desired filtering behavior. The method is based on an evolutionary approach driven by a multi-objective optimization scheme. We assess our proposal experimentally on a real Twitter dataset and the results are highly promising.

Consumer reviews are an important information resource for people and a fundamental part of everyday decision-making. Product reviews have an economical relevance which may attract malicious people to commit a review fraud, by writing false reviews. In this work, we investigate the possibility of generating hundreds of false restaurant reviews automatically and very quickly. We propose and evaluate a method for automatic generation of restaurant reviews tailored to the desired rating and restaurant category. A key feature of our work is the experimental evaluation which involves human users. We assessed the ability of our method to actually deceive users by presenting to them sets of reviews including a mix of genuine reviews and of machine-generated reviews. Users were not aware of the aim of the evaluation and the existence of machine-generated reviews. As it turns out, it is feasible to automatically generate realistic reviews which can manipulate the opinion of the user.

A large class of entity extraction tasks from text that is either semistructured or fully unstructured may be addressed by regular expressions, because in many practical cases the relevant entities follow an underlying syntactical pattern and this pattern may be described by a regular expression. In this work, we consider the long-standing problem of synthesizing such expressions automatically, based solely on examples of the desired behavior. We present the design and implementation of a system capable of addressing extraction tasks of realistic complexity. Our system is based on an evolutionary procedure carefully tailored to the specific needs of regular expression generation by examples. The procedure executes a search driven by a multiobjective optimization strategy aimed at simultaneously improving multiple performance indexes of candidate solutions while at the same time ensuring an adequate exploration of the huge solution space. We assess our proposal experimentally in great depth, on a number of challenging datasets. The accuracy of the obtained solutions seems to be adequate for practical usage and improves over earlier proposals significantly. Most importantly, our results are highly competitive even with respect to human operators. A prototype is available as a web application athttp://regex.inginf.units.it.

Presents corrections to typographical errors in the paper, "Inference of regular expressions for text extraction from examples," (Bartoli, A., et al), IEEE Trans. Knowl. Data Eng., vol. 28, no. 5, pp. 1217–1230, May 2016.

With the wide diffusion of smartphones and their usage in a plethora of processes and activities, these devices have been handling an increasing variety of sensitive resources. Attackers are hence producing a large number of malware applications for Android (the most spread mobile platform), often by slightly modifying existing applications, which results in malware being organized in families. Some works in the literature showed that opcodes are informative for detecting malware, not only in the Android platform. In this paper, we investigate if frequencies of ngrams of opcodes are effective in detecting Android malware and if there is some significant malware family for which they are more or less effective. To this end, we designed a method based on state-of-the-art classifiers applied to frequencies of opcodes ngrams. Then, we experimentally evaluated it on a recent dataset composed of 11120 applications, 5560 of which are malware belonging to several different families. Results show that an accuracy of 97% can be obtained on the average, whereas perfect detection rate is achieved for more than one malware family.

There is an increasing interest in the development of techniques for automatic relation extraction from unstructured text. The biomedical domain, in particular, is a sector that may greatly benefit from those techniques due to the huge and ever increasing amount of scientific publications describing observed phenomena of potential clinical interest. In this paper, we consider the problem of automatically identifying sentences that contain interactions between genes and proteins, based solely on a dictionary of genes and proteins and a small set of sample sentences in natural language. We propose an evolutionary technique for learning a classifier that is capable of detecting the desired sentences within scientific publications with high accuracy. The key feature of our proposal, that is internally based on Genetic Programming, is the construction of a model of the relevant syntax patterns in terms of standard part-of-speech annotations. The model consists of a set of regular expressions that are learned automatically despite the large alphabet size involved. We assess our approach on two realistic datasets and obtain 74% accuracy, a value sufficiently high to be of practical interest and that is in line with significant baseline methods.

We systematically analyse the design of the low-level vision components of a real-time system able to help a blind person in his/her social interactions. We focus on the acquisition and processing of the video sequences that are acquired by a wearable sensor (a smartphone camera or a Webcam) for the detection of faces in the scene. We review some classical and some very recent techniques that seem appropriate to the requirements of our goal.

We propose a system for continuous reauthentication of Web users based on the observed mouse dynamics. Key feature of our proposal is that no specific software needs to be installed on client machines, which allows to easily integrate continuous reauthentication capabilities into the existing infrastructure of large organizations. We assess our proposal with real data from 24 users, collected during normal working activity for several working days. We obtain accuracy in the order of 97%, which is aligned with earlier proposals requiring instrumentation of client workstations for intercepting all mouse activity-quite a strong requirement for large organizations. Our proposal may constitute an effective layer for a defense-in-depth strategy in several key scenarios: Web applications hosted in the cloud, where users authenticate with standard mechanisms, organizations which allow local users to access external Web applications, and enterprise applications hosted in local servers or private cloud facilities.

Regex golf has recently emerged as a specific kind of code golf, i.e., unstructured and informal programming competitions aimed at writing the shortest code solving a particular problem. A problem in regex golf consists in writing the shortest regular expression which matches all the strings in a given list and does not match any of the strings in another given list. The regular expression is expected to follow the syntax of a specified programming language, e.g., Javascript or PHP. In this paper, we propose a regex golf player internally based on Genetic Programming. We generate a population of candidate regular expressions represented as trees and evolve such population based on a multi-objective fitness which minimizes the errors and the length of the regular expression. We assess experimentally our player on a popular regex golf challenge consisting of 16 problems and compare our results against those of a recently proposed algorithm---the only one we are aware of.Our player obtains scores which improve over the baseline and are highly competitive also with respect to human players. The time for generating a solution is usually in the order of tens minutes, which is arguably comparable to the time required by human players.

We consider the problem of matching the topics of a scientific paper with those of possible publication venues for that paper. While every researcher knows the few top-level venues for his specific fields of interest, a venue recommendation system may be a significant aid when starting to explore a new research field. We propose a venue recommendation system which requires only title and abstract, differently from previous works which require full-text and reference list: hence, our system can be used even in the early stages of the authoring process and greatly simplifies the building and maintenance of the knowledge base necessary for generating meaningful recommendations. We assessed our proposal using a standard metric on a dataset of more than 58000 papers: the results show that our method provides recommendations whose quality is aligned with previous works, while requiring much less information from both the paper and the knowledge base.

Information extraction from printed documents is still a crucial problem in many interorganizational workflows. Solutions for other application domains, for example, the web, do not fit this peculiar scenario well, as printed documents do not carry any explicit structural or syntactical description. Moreover, printed documents usually lack any explicit indication about their source. We present a system, which we call PATO, for extracting predefined items from printed documents in a dynamic multisource scenario. PATO selects the source-specific wrapper required by each document, determines whether no suitable wrapper exists, and generates one when necessary. PATO assumes that the need for new source-specific wrappers is a part of normal system operation: new wrappers are generated online based on a few point-and-click operations performed by a human operator on a GUI. The role of operators is an integral part of the design and PATO may be configured to accommodate a broad range of automation levels. We show that PATO exhibits very good performance on a challenging data set composed of more than 600 printed documents drawn from three different application domains: invoices, datasheets of electronic components, and patents. We also perform an extensive analysis of the crucial tradeoff between accuracy and automation level.

Internet security threats often involve the fraudulent modification of a web site, often with the addition of new pages at URLs where no page should exist. Detecting the existence of such hidden URLs is very difficult because they do not appear during normal navigation and usually are not indexed by search engines. Most importantly, drive-by attacks leading users to hidden URLs, for example for phishing credentials, may fool even tech-savvy users, because such hidden URLs are increasingly hosted within trusted sites, thereby rendering HTTPS authentication ineffective. In this work, we propose an approach for detecting such URLs based only on their lexical features, which allows alerting the user before actually fetching the page. We assess our proposal on a dataset composed of thousands of URLs, with promising results.

Search-and-replace is a text processing task which may be largely automated with regular expressions: the user must describe with a specific formal language the regions to be modified (search pattern) and the corresponding desired changes (replacement expression). Writing and tuning the required expressions requires high familiarity with the corresponding formalism and is typically a lengthy, error-prone process.

The huge and ever increasing amount of text generated by Twitter users everyday embeds a wealth of information, in particular, about themes that become suddenly relevant to many users as well as about the sentiment polarity that users tend to associate with these themes. In this paper, we exploit both these opportunities and propose a method for: (i) detecting novel popular themes, i.e. events, (ii) summarizing these events by means of a concise yet meaningful representation, and (iii) assessing the prevalent sentiment polarity associated with each event, i.e., positive vs. negative. Our method is fully unsupervised and requires only a precompiled topic description in the form of set of potentially relevant keywords that might appear in the events of interest. We validate our proposal on a real corpus of about 8,000,000 tweets, by detecting, classifying and summarizing events related to three wide topics associated with tech-related brands.

Electronic devices capable of wireless communication are becoming ubiquitous. They enable a wide range of novel applications but these are often difficult to deploy in practice because wireless channels provide ample opportunities to attackers. A number of approaches have been proposed for building secure channels in these scenarios. An approach that would be simple, general and effective consists in establishing a shared secret between two devices by placing them in physical contact for a few seconds. This approach has not been exploited in practice due to the lack of common interfaces. We demonstrate the practical feasibility of the approach for devices equipped with a small LCD screen and cameras. We transfer secret keys between Android-based smartphones put in contact with each other for just a few seconds. The transfer occurs across a visual channel that cannot be intercepted.

We consider the automatic annotation of faces of people mentioned in news. News stories provide a constant flow of potentially useful image indexing information, due to their huge diffusion on the web and to the involvement of human operators in selecting relevant images for the stories. In this work we investigate the possibility of actually exploiting this wealth of information. We propose and evaluate a system for automatic face annotation of image news that is fully unsupervised and does not require any prior knowledge about topic or people involved. Key feature of our proposal is that it attempts to identify the essential piece of information -- how a person with a given name looks like -- by querying popular image search engines. Mining the web allows overcoming intrinsic limitations of approaches built above a predefined collection of stories: our system can potentially annotate people never handled before since its knowledge base is constantly expanded, as long as search engines keep on indexing the web. On the other hand, leveraging on image search engines forces to cope with the substantial amount of noise in search engine results. Our contribution shows experimentally that automatic face annotation may indeed be achieved based entirely on knowledge that lives in the web.

A key step in the understanding of printed documents is their classification based on the nature of information they contain and their layout. In this work we consider a dynamic scenario in which document classes are not known a priori and new classes can appear at any time. This open world setting is both realistic and highly challenging. We use an SVM-based classifier based only on image-level features and use a nearest-neighbor approach for detecting new classes. We assess our proposal on a real-world dataset composed of 562 invoices belonging to 68 different classes. These documents were digitalized after being handled by a corporate environment, thus they are quite noisy---e.g., big stamps and handwritten signatures at unfortunate positions and alike. The experimental results are highly promising.

Web site defacement, the process of introducing unauthorized modifications to a Web site, is a very common form of attack. In this paper we describe and evaluate experimentally a framework that may constitute the basis for a defacement detection service capable of monitoring thousands of remote Web sites systematically and automatically. In our framework an organization may join the service by simply providing the URLs of the resources to be monitored along with the contact point of an administrator. The monitored organization may thus take advantage of the service with just a few mouse clicks, without installing any software locally or changing its own daily operational processes. Our approach is based on anomaly detection and allows monitoring the integrity of many remote Web resources automatically while remaining fully decoupled from them, in particular, without requiring any prior knowledge about those resources. We evaluated our approach over a selection of dynamic resources and a set of publicly available defacements. The results are very satisfactory: all attacks are detected while keeping false positives to a minimum. We also assessed performance and scalability of our proposal and we found that it may indeed constitute the basis for actually deploying the proposed service on a large scale.

Hand-held devices have become widespread and provided with significant computing capabilities, which results in an increasing pressure for using these devices to perform tasks formerly limited to notebooks, like web browsing. Due to their small screens, however, hand-held devices cannot visualize directly documents that were not designed explicitly for small-screen rendering. Such documents may be rendered either at a scale too small to be useful, or at a scale that requires intensive scrolling operations by the user. Unfortunately, scrolling a small window across a large document with a hand-held device is quite cumbersome. In this paper we propose a scrolling system much simpler and more natural to use, based on the embedded camera-a component available in every modern hand-held device. We detect device motion by analyzing the video stream generated by the camera and then we transform the motion in a scrolling of the content rendered on the screen. This way, the user experiences the device screen like a small movable window on a larger virtual view, without requiring any dedicated motion-detection hardware. We performed an experimental evaluation aimed at assessing the effectiveness of the proposed system in the considered scenario, characterized by low image quality, unpredictable framed scene and soon. We performed an objective benchmark quantifying the accuracy of the detected trajectory and a subjective benchmark examining users' confidence with the proposed system. For the latter evaluation, we involved a panel of 20 subjects that executed a trajectory with our system and, as a comparison, with keyboard, mouse and touchpad. The results demonstrate that our approach is indeed practical.

Phishing is a form of online fraud that aims to steal a user’s sensitive information, such as online banking passwords or credit card numbers. The victim is tricked into entering such information on a web page that is crafted by the attacker so that it mimics a legitimate page. Recent statistics about the increasing number of phishing attacks suggest that this security problem still deserves significant attention. In this paper, we present a novel technique to visually compare a suspected phishing page with the legitimate one. The goal is to determine whether the two pages are suspiciously similar. We identify and consider three page features that play a key role in making a phishing page look similar to a legitimate one. These features are text pieces and their style, images embedded in the page, and the overall visual appearance of the page as rendered by the browser. To verify the feasibility of our approach, we performed an experimental evaluation using a dataset composed of 41 realworld phishing pages, along with their corresponding legitimate targets. Our experimental results are satisfactory in terms of false positives and false negatives. 1

Web site defacement, the process of introducing unauthorized modifications to a Web site, is a very common form of attack. Detecting such events automatically is very difficult because Web pages are highly dynamic and their degree of dynamism may vary widely across different pages. In this paper we propose a novel detection approach based on genetic programming (GP), an established evolutionary computation paradigm for automatic generation of algorithms. What makes GP particularly attractive in this context is that it does not rely on any domain-specific knowledge, whose description and synthesis is invariably a hard job. In a preliminary learning phase, GP builds an algorithm based on a sequence of readings of the remote page to be monitored and on a sample set of attacks. Then, we monitor the remote page at regular intervals and apply that algorithm, which raises an alert when a suspect modification is found. We developed a prototype based on a broader Web detection framework we proposed earlier and we tested our approach over a dataset of 15 dynamic Web pages, observed for about a month, and a collection of real Web defacements. We compared the results to those of a solution we developed earlier, whose design embedded a substantial amount of domain specific knowledge, and the results clearly show that GP may be an effective approach for this job.