-
Execution Semantics of Behavior Trees in Robotic Applications
Authors:
Enrico Ghiorzi,
Armando Tacchella
Abstract:
This document aims at describing, in a suitably precise and unambiguous though informal way, the execution semantics of Behavior Trees as used in Robotics applications, with particular attention to the Halt semantics.
This document aims at describing, in a suitably precise and unambiguous though informal way, the execution semantics of Behavior Trees as used in Robotics applications, with particular attention to the Halt semantics.
△ Less
Submitted 31 July, 2024;
originally announced August 2024.
-
Which products activate a product? An explainable machine learning approach
Authors:
Massimiliano Fessina,
Giambattista Albora,
Andrea Tacchella,
Andrea Zaccaria
Abstract:
Tree-based machine learning algorithms provide the most precise assessment of the feasibility for a country to export a target product given its export basket. However, the high number of parameters involved prevents a straightforward interpretation of the results and, in turn, the explainability of policy indications. In this paper, we propose a procedure to statistically validate the importance…
▽ More
Tree-based machine learning algorithms provide the most precise assessment of the feasibility for a country to export a target product given its export basket. However, the high number of parameters involved prevents a straightforward interpretation of the results and, in turn, the explainability of policy indications. In this paper, we propose a procedure to statistically validate the importance of the products used in the feasibility assessment. In this way, we are able to identify which products, called explainers, significantly increase the probability to export a target product in the near future. The explainers naturally identify a low dimensional representation, the Feature Importance Product Space, that enhances the interpretability of the recommendations and provides out-of-sample forecasts of the export baskets of countries. Interestingly, we detect a positive correlation between the complexity of a product and the complexity of its explainers.
△ Less
Submitted 5 December, 2022;
originally announced December 2022.
-
A Bayesian approach to translators' reliability assessment
Authors:
Marco Miccheli,
Andrej Leban,
Andrea Tacchella,
Andrea Zaccaria,
Dario Mazzilli,
Sébastien Bratières
Abstract:
Translation Quality Assessment (TQA) is a process conducted by human translators and is widely used, both for estimating the performance of (increasingly used) Machine Translation, and for finding an agreement between translation providers and their customers. While translation scholars are aware of the importance of having a reliable way to conduct the TQA process, it seems that there is limited…
▽ More
Translation Quality Assessment (TQA) is a process conducted by human translators and is widely used, both for estimating the performance of (increasingly used) Machine Translation, and for finding an agreement between translation providers and their customers. While translation scholars are aware of the importance of having a reliable way to conduct the TQA process, it seems that there is limited literature that tackles the issue of reliability with a quantitative approach. In this work, we consider the TQA as a complex process from the point of view of physics of complex systems and approach the reliability issue from the Bayesian paradigm. Using a dataset of translation quality evaluations (in the form of error annotations), produced entirely by the Professional Translation Service Provider Translated SRL, we compare two Bayesian models that parameterise the following features involved in the TQA process: the translation difficulty, the characteristics of the translators involved in producing the translation, and of those assessing its quality - the reviewers. We validate the models in an unsupervised setting and show that it is possible to get meaningful insights into translators even with just one review per translation; subsequently, we extract information like translators' skills and reviewers' strictness, as well as their consistency in their respective roles. Using this, we show that the reliability of reviewers cannot be taken for granted even in the case of expert translators: a translator's expertise can induce a cognitive bias when reviewing a translation produced by another translator. The most expert translators, however, are characterised by the highest level of consistency, both in translating and in assessing the translation quality.
△ Less
Submitted 12 April, 2022; v1 submitted 14 March, 2022;
originally announced March 2022.
-
A Toolchain to Design, Execute, and Monitor Robots Behaviors
Authors:
Michele Colledanchise,
Giuseppe Cicala,
Daniele E. Domenichelli,
Lorenzo Natale,
Armando Tacchella
Abstract:
In this paper, we present a toolchain to design, execute, and verify robot behaviors. The toolchain follows the guidelines defined by the EU H2020 project RobMoSys and encodes the robot deliberation as a Behavior Tree (BT), a directed tree where the internal nodes model behavior composition and leaf nodes model action or measurement operations. Such leaf nodes take the form of a statechart (SC), w…
▽ More
In this paper, we present a toolchain to design, execute, and verify robot behaviors. The toolchain follows the guidelines defined by the EU H2020 project RobMoSys and encodes the robot deliberation as a Behavior Tree (BT), a directed tree where the internal nodes model behavior composition and leaf nodes model action or measurement operations. Such leaf nodes take the form of a statechart (SC), which runs in separate threads, whose states perform basic arithmetic operations and send commands to the robot. The toolchain provides the ability to define a runtime monitor for a given system specification that warns the user whenever a given specification is violated.
We validated the toolchain in a simulated experiment that we made reproducible in an OS-virtualization environment.
△ Less
Submitted 29 June, 2021;
originally announced June 2021.
-
Formalizing the Execution Context of Behavior Trees for Runtime Verification of Deliberative Policies
Authors:
Michele Colledanchise,
Giuseppe Cicala,
Daniele E. Domenichelli,
Lorenzo Natale,
Armando Tacchella
Abstract:
In this paper, we enable automated property verification of deliberative components in robot control architectures. We focus on formalizing the execution context of Behavior Trees (BTs) to provide a scalable, yet formally grounded, methodology to enable runtime verification and prevent unexpected robot behaviors. To this end, we consider a message-passing model that accommodates both synchronous a…
▽ More
In this paper, we enable automated property verification of deliberative components in robot control architectures. We focus on formalizing the execution context of Behavior Trees (BTs) to provide a scalable, yet formally grounded, methodology to enable runtime verification and prevent unexpected robot behaviors. To this end, we consider a message-passing model that accommodates both synchronous and asynchronous composition of parallel components, in which BTs and other components execute and interact according to the communication patterns commonly adopted in robotic software architectures. We introduce a formal property specification language to encode requirements and build runtime monitors. We performed a set of experiments, both on simulations and on the real robot, demonstrating the feasibility of our approach in a realistic application and its integration in a typical robot software architecture. We also provide an OS-level virtualization environment to reproduce the experiments in the simulated scenario.
△ Less
Submitted 16 September, 2021; v1 submitted 23 June, 2021;
originally announced June 2021.
-
Product Progression: a machine learning approach to forecasting industrial upgrading
Authors:
Giambattista Albora,
Luciano Pietronero,
Andrea Tacchella,
Andrea Zaccaria
Abstract:
Economic complexity methods, and in particular relatedness measures, lack a systematic evaluation and comparison framework. We argue that out-of-sample forecast exercises should play this role, and we compare various machine learning models to set the prediction benchmark. We find that the key object to forecast is the activation of new products, and that tree-based algorithms clearly overperform…
▽ More
Economic complexity methods, and in particular relatedness measures, lack a systematic evaluation and comparison framework. We argue that out-of-sample forecast exercises should play this role, and we compare various machine learning models to set the prediction benchmark. We find that the key object to forecast is the activation of new products, and that tree-based algorithms clearly overperform both the quite strong auto-correlation benchmark and the other supervised algorithms. Interestingly, we find that the best results are obtained in a cross-validation setting, when data about the predicted country was excluded from the training set. Our approach has direct policy implications, providing a quantitative and scientifically tested measure of the feasibility of introducing a new product in a given country.
△ Less
Submitted 31 May, 2021;
originally announced May 2021.
-
Relatedness in the Era of Machine Learning
Authors:
Andrea Tacchella,
Andrea Zaccaria,
Marco Miccheli,
Luciano Pietronero
Abstract:
Relatedness is a quantification of how much two human activities are similar in terms of the inputs and contexts needed for their development. Under the idea that it is easier to move between related activities than towards unrelated ones, empirical approaches to quantify relatedness are currently used as predictive tools to inform policies and development strategies in governments, international…
▽ More
Relatedness is a quantification of how much two human activities are similar in terms of the inputs and contexts needed for their development. Under the idea that it is easier to move between related activities than towards unrelated ones, empirical approaches to quantify relatedness are currently used as predictive tools to inform policies and development strategies in governments, international organizations, and firms. Here we focus on countries' industries and we show that the standard, widespread approach of estimating Relatedness through the co-location of activities (e.g. Product Space) generates a measure of relatedness that performs worse than trivial auto-correlation prediction strategies. We argue that this is a consequence of the poor signal-to-noise ratio present in international trade data. In this paper we show two main findings. First, we find that a shift from two-products correlations (network-density based) to many-products correlations (decision trees) can dramatically improve the quality of forecasts with a corresponding reduction of the risk of wrong policy choices. Then, we propose a new methodology to empirically estimate Relatedness that we call Continuous Projection Space (CPS). CPS, which can be seen as a general network embedding technique, vastly outperforms all the co-location, network-based approaches, while retaining a similar interpretability in terms of pairwise distances.
△ Less
Submitted 10 March, 2021;
originally announced March 2021.
-
NeVer 2.0: Learning, Verification and Repair of Deep Neural Networks
Authors:
Dario Guidotti,
Luca Pulina,
Armando Tacchella
Abstract:
In this work, we present an early prototype of NeVer 2.0, a new system for automated synthesis and analysis of deep neural networks.NeVer 2.0borrows its design philosophy from NeVer, the first package that integrated learning, automated verification and repair of (shallow) neural networks in a single tool. The goal of NeVer 2.0 is to provide a similar integration for deep networks by leveraging a…
▽ More
In this work, we present an early prototype of NeVer 2.0, a new system for automated synthesis and analysis of deep neural networks.NeVer 2.0borrows its design philosophy from NeVer, the first package that integrated learning, automated verification and repair of (shallow) neural networks in a single tool. The goal of NeVer 2.0 is to provide a similar integration for deep networks by leveraging a selection of state-of-the-art learning frameworks and integrating them with verification algorithms to ease the scalability challenge and make repair of faulty networks possible.
△ Less
Submitted 18 November, 2020;
originally announced November 2020.
-
Automated Requirements-Based Testing of Black-Box Reactive Systems
Authors:
Massimo Narizzano,
Luca Pulina,
Armando Tacchella,
Simone Vuotto
Abstract:
We present a new approach to conformance testing of black-box reactive systems. We consider system specifications written as linear temporal logic formulas to generate tests as sequences of input/output pairs: inputs are extracted from the Buchi automata corresponding to the specifications, and outputs are obtained by feeding the inputs to the systems. Conformance is checked by comparing input/out…
▽ More
We present a new approach to conformance testing of black-box reactive systems. We consider system specifications written as linear temporal logic formulas to generate tests as sequences of input/output pairs: inputs are extracted from the Buchi automata corresponding to the specifications, and outputs are obtained by feeding the inputs to the systems. Conformance is checked by comparing input/output sequences with automata traces to detect violations of the specifications. We consider several criteria for extracting tests and for stopping generation, and we compare them experimentally using both indicators of coverage and error-detection. The results show that our methodology can generate test suites with good system coverage and error-detection capability.
△ Less
Submitted 14 May, 2020;
originally announced May 2020.
-
Verification of Neural Networks: Enhancing Scalability through Pruning
Authors:
Dario Guidotti,
Francesco Leofante,
Luca Pulina,
Armando Tacchella
Abstract:
Verification of deep neural networks has witnessed a recent surge of interest, fueled by success stories in diverse domains and by abreast concerns about safety and security in envisaged applications. Complexity and sheer size of such networks are challenging for automated formal verification techniques which, on the other hand, could ease the adoption of deep networks in safety- and security-crit…
▽ More
Verification of deep neural networks has witnessed a recent surge of interest, fueled by success stories in diverse domains and by abreast concerns about safety and security in envisaged applications. Complexity and sheer size of such networks are challenging for automated formal verification techniques which, on the other hand, could ease the adoption of deep networks in safety- and security-critical contexts.
In this paper we focus on enabling state-of-the-art verification tools to deal with neural networks of some practical interest. We propose a new training pipeline based on network pruning with the goal of striking a balance between maintaining accuracy and robustness while making the resulting networks amenable to formal analysis. The results of our experiments with a portfolio of pruning algorithms and verification tools show that our approach is successful for the kind of networks we consider and for some combinations of pruning and verification techniques, thus bringing deep neural networks closer to the reach of formally-grounded methods.
△ Less
Submitted 17 March, 2020;
originally announced March 2020.
-
A new and stable estimation method of country economic fitness and product complexity
Authors:
Vito D. P. Servedio,
Paolo Buttà,
Dario Mazzilli,
Andrea Tacchella,
Luciano Pietronero
Abstract:
We present a new metric estimating fitness of countries and complexity of products by exploiting a non-linear non-homogeneous map applied to the publicly available information on the goods exported by a country. The non homogeneous terms guarantee both convergence and stability. After a suitable rescaling of the relevant quantities, the non homogeneous terms are eventually set to zero so that this…
▽ More
We present a new metric estimating fitness of countries and complexity of products by exploiting a non-linear non-homogeneous map applied to the publicly available information on the goods exported by a country. The non homogeneous terms guarantee both convergence and stability. After a suitable rescaling of the relevant quantities, the non homogeneous terms are eventually set to zero so that this new metric is parameter free. This new map almost reproduces the results of the original homogeneous metrics already defined in literature and allows for an approximate analytic solution in case of actual binarized matrices based on the Revealed Comparative Advantage (RCA) indicator. This solution is connected with a new quantity describing the neighborhood of nodes in bipartite graphs, representing in this work the relations between countries and exported products. Moreover, we define the new indicator of country net-efficiency quantifying how a country efficiently invests in capabilities able to generate innovative complex high quality products. Eventually, we demonstrate analytically the local convergence of the algorithm involved.
△ Less
Submitted 12 October, 2018; v1 submitted 23 July, 2018;
originally announced July 2018.
-
SMarTplan: a Task Planner for Smart Factories
Authors:
Arthur Bit-Monnot,
Francesco Leofante,
Luca Pulina,
Erika Abraham,
Armando Tacchella
Abstract:
Smart factories are on the verge of becoming the new industrial paradigm, wherein optimization permeates all aspects of production, from concept generation to sales. To fully pursue this paradigm, flexibility in the production means as well as in their timely organization is of paramount importance. AI is planning a major role in this transition, but the scenarios encountered in practice might be…
▽ More
Smart factories are on the verge of becoming the new industrial paradigm, wherein optimization permeates all aspects of production, from concept generation to sales. To fully pursue this paradigm, flexibility in the production means as well as in their timely organization is of paramount importance. AI is planning a major role in this transition, but the scenarios encountered in practice might be challenging for current tools. Task planning is one example where AI enables more efficient and flexible operation through an online automated adaptation and rescheduling of the activities to cope with new operational constraints and demands.
In this paper we present SMarTplan, a task planner specifically conceived to deal with real-world scenarios in the emerging smart factory paradigm. Including both special-purpose and general-purpose algorithms, SMarTplan is based on current automated reasoning technology and it is designed to tackle complex application domains. In particular, we show its effectiveness on a logistic scenario, by comparing its specialized version with the general purpose one, and extending the comparison to other state-of-the-art task planners.
△ Less
Submitted 19 June, 2018;
originally announced June 2018.
-
Automated Verification of Neural Networks: Advances, Challenges and Perspectives
Authors:
Francesco Leofante,
Nina Narodytska,
Luca Pulina,
Armando Tacchella
Abstract:
Neural networks are one of the most investigated and widely used techniques in Machine Learning. In spite of their success, they still find limited application in safety- and security-related contexts, wherein assurance about networks' performances must be provided. In the recent past, automated reasoning techniques have been proposed by several researchers to close the gap between neural networks…
▽ More
Neural networks are one of the most investigated and widely used techniques in Machine Learning. In spite of their success, they still find limited application in safety- and security-related contexts, wherein assurance about networks' performances must be provided. In the recent past, automated reasoning techniques have been proposed by several researchers to close the gap between neural networks and applications requiring formal guarantees about their behavior. In this work, we propose a primer of such techniques and a comprehensive categorization of existing approaches for the automated verification of neural networks. A discussion about current limitations and directions for future investigation is provided to foster research on this topic at the crossroads of Machine Learning and Automated Reasoning.
△ Less
Submitted 24 May, 2018;
originally announced May 2018.
-
Constrained Image Generation Using Binarized Neural Networks with Decision Procedures
Authors:
Svyatoslav Korneev,
Nina Narodytska,
Luca Pulina,
Armando Tacchella,
Nikolaj Bjorner,
Mooly Sagiv
Abstract:
We consider the problem of binary image generation with given properties. This problem arises in a number of practical applications, including generation of artificial porous medium for an electrode of lithium-ion batteries, for composed materials, etc. A generated image represents a porous medium and, as such, it is subject to two sets of constraints: topological constraints on the structure and…
▽ More
We consider the problem of binary image generation with given properties. This problem arises in a number of practical applications, including generation of artificial porous medium for an electrode of lithium-ion batteries, for composed materials, etc. A generated image represents a porous medium and, as such, it is subject to two sets of constraints: topological constraints on the structure and process constraints on the physical process over this structure. To perform image generation we need to define a mapping from a porous medium to its physical process parameters. For a given geometry of a porous medium, this mapping can be done by solving a partial differential equation (PDE). However, embedding a PDE solver into the search procedure is computationally expensive. We use a binarized neural network to approximate a PDE solver. This allows us to encode the entire problem as a logical formula. Our main contribution is that, for the first time, we show that this problem can be tackled using decision procedures. Our experiments show that our model is able to produce random constrained images that satisfy both topological and process constraints.
△ Less
Submitted 23 February, 2018;
originally announced February 2018.
-
Consistency of Property Specification Patterns with Boolean and Constrained Numerical Signals
Authors:
Massimo Narizzano,
Luca Pulina,
Armando Tacchella,
Simone Vuotto
Abstract:
Property Specification Patterns (PSPs) have been proposed to solve recurring specification needs, to ease the formalization of requirements, and enable automated verification thereof. In this paper, we extend PSPs by considering Boolean as well as atomic assertions from a constraint system. This extension enables us to reason about functional requirements which could not be captured by basic PSPs.…
▽ More
Property Specification Patterns (PSPs) have been proposed to solve recurring specification needs, to ease the formalization of requirements, and enable automated verification thereof. In this paper, we extend PSPs by considering Boolean as well as atomic assertions from a constraint system. This extension enables us to reason about functional requirements which could not be captured by basic PSPs. We contribute an encoding from constrained PSPs to LTL formulas, and we show experimental results demonstrating that our approach scales on requirements of realistic size generated using an artificial probabilistic model. Finally, we show that our extension enables us to prove (in)consistency of requirements about an embedded controller for a robotic manipulator.
△ Less
Submitted 12 December, 2017;
originally announced December 2017.
-
On the Synthesis of Guaranteed-Quality Plans for Robot Fleets in Logistics Scenarios via Optimization Modulo Theories
Authors:
Francesco Leofante,
Erika Ábrahám,
Tim Niemueller,
Gerhard Lakemeyer,
Armando Tacchella
Abstract:
In manufacturing, the increasing involvement of autonomous robots in production processes poses new challenges on the production management. In this paper we report on the usage of Optimization Modulo Theories (OMT) to solve certain multi-robot scheduling problems in this area. Whereas currently existing methods are heuristic, our approach guarantees optimality for the computed solution. We do not…
▽ More
In manufacturing, the increasing involvement of autonomous robots in production processes poses new challenges on the production management. In this paper we report on the usage of Optimization Modulo Theories (OMT) to solve certain multi-robot scheduling problems in this area. Whereas currently existing methods are heuristic, our approach guarantees optimality for the computed solution. We do not only present our final method but also its chronological development, and draw some general observations for the development of OMT-based approaches.
△ Less
Submitted 12 November, 2017;
originally announced November 2017.
-
Economic Complexity: "Buttarla in caciara" vs a constructive approach
Authors:
Luciano Pietronero,
Matthieu Cristelli,
Andrea Gabrielli,
Dario Mazzilli,
Emanuele Pugliese,
Andrea Tacchella,
Andrea Zaccaria
Abstract:
This note is a contribution to the debate about the optimal algorithm for Economic Complexity that recently appeared on ArXiv [1, 2] . The authors of [2] eventually agree that the ECI+ algorithm [1] consists just in a renaming of the Fitness algorithm we introduced in 2012, as we explicitly showed in [3]. However, they omit any comment on the fact that their extensive numerical tests claimed to de…
▽ More
This note is a contribution to the debate about the optimal algorithm for Economic Complexity that recently appeared on ArXiv [1, 2] . The authors of [2] eventually agree that the ECI+ algorithm [1] consists just in a renaming of the Fitness algorithm we introduced in 2012, as we explicitly showed in [3]. However, they omit any comment on the fact that their extensive numerical tests claimed to demonstrate that the same algorithm works well if they name it ECI+, but not if its name is Fitness. They should realize that this eliminates any credibility to their numerical methods and therefore also to their new analysis, in which they consider many algorithms [2]. Since by their own admission the best algorithm is the Fitness one, their new claim became that the search for the best algorithm is pointless and all algorithms are alike. This is exactly the opposite of what they claimed a few days ago and it does not deserve much comments. After these clarifications we also present a constructive analysis of the status of Economic Complexity, its algorithms, its successes and its perspectives. For us the discussion closes here, we will not reply to further comments.
△ Less
Submitted 15 September, 2017;
originally announced September 2017.
-
Why we like the ECI+ algorithm
Authors:
Andrea Gabrielli,
Matthieu Cristelli,
Dario Mazzilli,
Andrea Tacchella,
Andrea Zaccaria,
Luciano Pietronero
Abstract:
Recently a measure for Economic Complexity named ECI+ has been proposed by Albeaik et al. We like the ECI+ algorithm because it is mathematically identical to the Fitness algorithm, the measure for Economic Complexity we introduced in 2012. We demonstrate that the mathematical structure of ECI+ is strictly equivalent to that of Fitness (up to normalization and rescaling). We then show how the clai…
▽ More
Recently a measure for Economic Complexity named ECI+ has been proposed by Albeaik et al. We like the ECI+ algorithm because it is mathematically identical to the Fitness algorithm, the measure for Economic Complexity we introduced in 2012. We demonstrate that the mathematical structure of ECI+ is strictly equivalent to that of Fitness (up to normalization and rescaling). We then show how the claims of Albeaik et al. about the ability of Fitness to describe the Economic Complexity of a country are incorrect. Finally, we hypothesize how the wrong results reported by these authors could have been obtained by not iterating the algorithm.
△ Less
Submitted 3 August, 2017;
originally announced August 2017.
-
Ontologies in System Engineering: a Field Report
Authors:
Marco Menapace,
Armando Tacchella
Abstract:
In recent years ontologies enjoyed a growing popularity outside specialized AI communities. System engineering is no exception to this trend, with ontologies being proposed as a basis for several tasks in complex industrial implements, including system design, monitoring and diagnosis. In this paper, we consider four different contributions to system engineering wherein ontologies are instrumental…
▽ More
In recent years ontologies enjoyed a growing popularity outside specialized AI communities. System engineering is no exception to this trend, with ontologies being proposed as a basis for several tasks in complex industrial implements, including system design, monitoring and diagnosis. In this paper, we consider four different contributions to system engineering wherein ontologies are instrumental to provide enhancements over traditional ad-hoc techniques. For each application, we briefly report the methodologies, the tools and the results obtained with the goal to provide an assessment of merits and limits of ontologies in such domains.
△ Less
Submitted 23 February, 2017;
originally announced February 2017.
-
An introduction to associative geometry with applications to integrable systems
Authors:
Alberto Tacchella
Abstract:
The aim of these notes is to provide a reasonably short and "hands-on" introduction to the differential calculus on associative algebras over a field of characteristic zero. Following a suggestion of Ginzburg's we call the resulting theory associative geometry. We argue that this formalism sheds a new light on some classic solution methods in the theory of finite-dimensional integrable dynamical s…
▽ More
The aim of these notes is to provide a reasonably short and "hands-on" introduction to the differential calculus on associative algebras over a field of characteristic zero. Following a suggestion of Ginzburg's we call the resulting theory associative geometry. We argue that this formalism sheds a new light on some classic solution methods in the theory of finite-dimensional integrable dynamical systems.
△ Less
Submitted 2 November, 2016;
originally announced November 2016.
-
The Build-Up of Diversity in Complex Ecosystems
Authors:
Andrea Tacchella,
Riccardo Di Clemente,
Andrea Gabrielli,
Luciano Pietronero
Abstract:
Diversity is a fundamental feature of ecosystems, even when the concept of ecosystem is extended to sociology or economics. Diversity can be intended as the count of different items, animals, or, more generally, interactions. There are two classes of stylized facts that emerge when diversity is taken into account. The first are Diversity explosions: evolutionary radiations in biology, or the proce…
▽ More
Diversity is a fundamental feature of ecosystems, even when the concept of ecosystem is extended to sociology or economics. Diversity can be intended as the count of different items, animals, or, more generally, interactions. There are two classes of stylized facts that emerge when diversity is taken into account. The first are Diversity explosions: evolutionary radiations in biology, or the process of escaping 'Poverty Traps' in economics are two well known examples. The second is nestedness: entities with a very diverse set of interactions are the only ones that interact with more specialized ones. In a single sentence: specialists interact with generalists. Nestedness is observed in a variety of bipartite networks of interactions: Biogeographic, macroeconomic and mutualistic to name a few. This indicates that entities diversify following a pattern. Since they appear in such very different systems, these two stylized facts point out that the build up of diversity is driven by a fundamental probabilistic mechanism, and here we sketch its minimal features. We show how the contraction of a random tripartite network, which is maximally entropic in all its degree distributions but one, can reproduce stylized facts of real data with great accuracy which is qualitatively lost when that degree distribution is changed. We base our reasoning on the combinatoric picture that the nodes on one layer of these bipartite networks can be described as combinations of a number of fundamental building blocks. The stylized facts of diversity that we observe in real systems can be explained with an extreme heterogeneity (a scale-free distribution) in the number of meaningful combinations in which each building block is involved. We show that if the usefulness of the building blocks has a scale-free distribution, then maximally entropic baskets of building blocks will give rise to very rich behaviors.
△ Less
Submitted 12 September, 2016;
originally announced September 2016.
-
Poisson-Nijenhuis structures on quiver path algebras
Authors:
Claudio Bartocci,
Alberto Tacchella
Abstract:
We introduce a notion of noncommutative Poisson-Nijenhuis structure on the path algebra of a quiver. In particular, we focus on the case when the Poisson bracket arises from a noncommutative symplectic form. The formalism is then applied to the study of the Calogero-Moser and Gibbons-Hermsen integrable systems. In the former case, we give a new interpretation of the bihamiltonian reduction perform…
▽ More
We introduce a notion of noncommutative Poisson-Nijenhuis structure on the path algebra of a quiver. In particular, we focus on the case when the Poisson bracket arises from a noncommutative symplectic form. The formalism is then applied to the study of the Calogero-Moser and Gibbons-Hermsen integrable systems. In the former case, we give a new interpretation of the bihamiltonian reduction performed in [3].
△ Less
Submitted 30 December, 2016; v1 submitted 7 April, 2016;
originally announced April 2016.
-
Reverse Engineering of Middleware for Verification of Robot Control Architectures
Authors:
Ali Khalili,
Lorenzo Natale,
Armando Tacchella
Abstract:
We consider the problem of automating the verification of distributed control software relying on publish-subscribe middleware. In this scenario, the main challenge is that software correctness depends intrinsically on correct usage of middleware components, but structured models of such components might not be available for analysis, e.g., because they are too large and complex to be described pr…
▽ More
We consider the problem of automating the verification of distributed control software relying on publish-subscribe middleware. In this scenario, the main challenge is that software correctness depends intrinsically on correct usage of middleware components, but structured models of such components might not be available for analysis, e.g., because they are too large and complex to be described precisely in a cost-effective way. To overcome this problem, we propose to identify abstract models of middleware as finite-state automata, and then to perform verification on the combined middleware and control software models. Both steps are carried out in a computer-assisted way using state-of-the-art techniques in automata-based identification and verification. Our main contribution is to show that the combination of identification and verification is feasible and useful when considering typical issues that arise in the implementation of distributed control software.
△ Less
Submitted 7 November, 2014;
originally announced November 2014.
-
How the Taxonomy of Products Drives the Economic Development of Countries
Authors:
Andrea Zaccaria,
Matthieu Cristelli,
Andrea Tacchella,
Luciano Pietronero
Abstract:
We introduce an algorithm able to reconstruct the relevant network structure on which the time evolution of country-product bipartite networks takes place. The significant links are obtained by selecting the largest values of the projected matrix. We first perform a number of tests of this filtering procedure on synthetic cases and a toy model. Then we analyze the bipartite network constituted by…
▽ More
We introduce an algorithm able to reconstruct the relevant network structure on which the time evolution of country-product bipartite networks takes place. The significant links are obtained by selecting the largest values of the projected matrix. We first perform a number of tests of this filtering procedure on synthetic cases and a toy model. Then we analyze the bipartite network constituted by countries and exported products, using two databases for a total of almost 50 years. It is then possible to build a hierarchically directed network, in which the taxonomy of products emerges in a natural way. We study the influence of the structure of this taxonomy network on countries' development; in particular, guided by an example taken from the industrialization of South Korea, we link the structure of the taxonomy network to the empirical temporal connections between product activations, finding that the most relevant edges for countries' development are the ones suggested by our network. These results suggest paths in the product space which are easier to achieve, and so can drive countries' policies in the industrialization process.
△ Less
Submitted 9 August, 2014;
originally announced August 2014.
-
On a family of quivers related to the Gibbons-Hermsen system
Authors:
Alberto Tacchella
Abstract:
We introduce a family of quivers $Z_{r}$ (labeled by a natural number $r\geq 1$) and study the non-commutative symplectic geometry of the corresponding doubles $\mathbf{Q}_{r}$. We show that the group of non-commutative symplectomorphisms of the path algebra $\mathbb{C}\mathbf{Q}_{r}$ contains two copies of the group $\mathrm{GL}_{r}$ over a ring of polynomials in one indeterminate, and that a par…
▽ More
We introduce a family of quivers $Z_{r}$ (labeled by a natural number $r\geq 1$) and study the non-commutative symplectic geometry of the corresponding doubles $\mathbf{Q}_{r}$. We show that the group of non-commutative symplectomorphisms of the path algebra $\mathbb{C}\mathbf{Q}_{r}$ contains two copies of the group $\mathrm{GL}_{r}$ over a ring of polynomials in one indeterminate, and that a particular subgroup $\mathcal{P}_{r}$ (which contains both of these copies) acts on the completion $\mathcal{C}_{n,r}$ of the phase space of the $n$-particles, rank $r$ Gibbons-Hermsen integrable system and connects each pair of points belonging to a certain dense open subset of $\mathcal{C}_{n,r}$. This generalizes some known results for the cases $r=1$ and $r=2$.
△ Less
Submitted 12 April, 2015; v1 submitted 15 November, 2013;
originally announced November 2013.
-
A Note on the Automorphism Group of the Bielawski-Pidstrygach Quiver
Authors:
Igor Mencattini,
Alberto Tacchella
Abstract:
We show that there exists a morphism between a group $Γ^{\mathrm{alg}}$ introduced by G. Wilson and a quotient of the group of tame symplectic automorphisms of the path algebra of a quiver introduced by Bielawski and Pidstrygach. The latter is known to act transitively on the phase space $\mathcal{C}_{n,2}$ of the Gibbons-Hermsen integrable system of rank 2, and we prove that the subgroup generate…
▽ More
We show that there exists a morphism between a group $Γ^{\mathrm{alg}}$ introduced by G. Wilson and a quotient of the group of tame symplectic automorphisms of the path algebra of a quiver introduced by Bielawski and Pidstrygach. The latter is known to act transitively on the phase space $\mathcal{C}_{n,2}$ of the Gibbons-Hermsen integrable system of rank 2, and we prove that the subgroup generated by the image of $Γ^{\mathrm{alg}}$ together with a particular tame symplectic automorphism has the property that, for every pair of points of the regular and semisimple locus of $\mathcal{C}_{n,2}$, the subgroup contains an element sending the first point to the second.
△ Less
Submitted 30 April, 2013; v1 submitted 17 August, 2012;
originally announced August 2012.
-
Clause/Term Resolution and Learning in the Evaluation of Quantified Boolean Formulas
Authors:
E. Giunchiglia,
M. Narizzano,
A. Tacchella
Abstract:
Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of clauses. Deduction starts by inferring new clauses by resolution, and goes on until the empty clause is generated or satisfiability of the set of cla…
▽ More
Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of clauses. Deduction starts by inferring new clauses by resolution, and goes on until the empty clause is generated or satisfiability of the set of clauses is proven, e.g., because no new clauses can be generated.
In this paper, we restrict our attention to the problem of evaluating Quantified Boolean Formulas (QBFs). In this setting, the above outlined deduction process is known to be sound and complete if given a formula in CNF and if a form of resolution, called Q-resolution, is used. We introduce Q-resolution on terms, to be used for formulas in disjunctive normal form. We show that the computation performed by most of the available procedures for QBFs --based on the Davis-Logemann-Loveland procedure (DLL) for propositional satisfiability-- corresponds to a tree in which Q-resolution on terms and clauses alternate. This poses the theoretical bases for the introduction of learning, corresponding to recording Q-resolution formulas associated with the nodes of the tree. We discuss the problems related to the introduction of learning in DLL based procedures, and present solutions extending state-of-the-art proposals coming from the literature on propositional satisfiability. Finally, we show that our DLL based solver extended with learning, performs significantly better on benchmarks used in the 2003 QBF solvers comparative evaluation.
△ Less
Submitted 26 September, 2011;
originally announced November 2011.
-
A network analysis of countries' export flows: firm grounds for the building blocks of the economy
Authors:
Guido Caldarelli,
Matthieu Cristelli,
Andrea Gabrielli,
Luciano Pietronero,
Antonio Scala,
Andrea Tacchella
Abstract:
In this paper we analyze the bipartite network of countries and products from UN data on country production. We define the country-country and product-product projected networks and introduce a novel method of filtering information based on elements' similarity. As a result we find that country clustering reveals unexpected socio-geographic links among the most competing countries. On the same foo…
▽ More
In this paper we analyze the bipartite network of countries and products from UN data on country production. We define the country-country and product-product projected networks and introduce a novel method of filtering information based on elements' similarity. As a result we find that country clustering reveals unexpected socio-geographic links among the most competing countries. On the same footings the products clustering can be efficiently used for a bottom-up classification of produced goods. Furthermore we mathematically reformulate the "reflections method" introduced by Hidalgo and Hausmann as a fixpoint problem; such formulation highlights some conceptual weaknesses of the approach. To overcome such an issue, we introduce an alternative methodology (based on biased Markov chains) that allows to rank countries in a conceptually consistent way. Our analysis uncovers a strong non-linear interaction between the diversification of a country and the ubiquity of its products, thus suggesting the possible need of moving towards more efficient and direct non-linear fixpoint algorithms to rank countries and products in the global market.
△ Less
Submitted 19 April, 2012; v1 submitted 12 August, 2011;
originally announced August 2011.
-
On rational solutions of multicomponent and matrix KP hierarchies
Authors:
Alberto Tacchella
Abstract:
We derive some rational solutions for the multicomponent and matrix KP hierarchies generalising an approach by Wilson. Connections with the multicomponent version of the KP/CM correspondence are discussed.
We derive some rational solutions for the multicomponent and matrix KP hierarchies generalising an approach by Wilson. Connections with the multicomponent version of the KP/CM correspondence are discussed.
△ Less
Submitted 5 November, 2010;
originally announced November 2010.
