Topic: 020201 artificial intelligence & image processing - Searchworks@Jio Institute Digital Library Search Results

Showing total 50 results

Start Over Topic 020201 artificial intelligence & image processing

50 results

1. Adaptive Request Scheduling for the I/O Forwarding Layer using Reinforcement Learning

Author: Philippe O. A. Navaux, Jean Luca Bez, Toni Cortes, Francieli Zanon Boito, Alberto Miranda, Ramon Nou, Instituto de Informática da UFRGS (UFRGS), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Topology-Aware System-Scale Data Management for High-Performance Computing (TADAAM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Data Aware Large Scale Computing (DATAMOVE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), This study was financed in part by the Coordenac¸ao de Aperfeicoamento de Pessoal de Nıvel Superior - Brasil (CAPES) - Finance Code 001. It has also received support from the Conselho Nacional de Desenvolvimento Cientıfico e Tecnologico (CNPq), Brazil, the LICIA International Laboratory, NCSA-Inria-ANL-BSC-JSC-Riken Joint-Laboratory on Extreme Scale Computing (JLESC), the Spanish Ministry of Science and Innovation under the TIN2015–65316 grant, and the Generalitat de Catalunya under contract 2014– SGR–1051. This research received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 800144. Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www. grid5000.fr). The authors acknowledge the National Laboratory for Scientific Computing (LNCC/MCTI, Brazil) for providing HPC resources of the SDumont supercomputer, which have contributed to the research results reported within this paper., Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors, Barcelona Supercomputing Center, Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest
Subjects: I/O forwarding, Parallel I/O, I/O scheduling, Computer Networks and Communications, Computer science, Distributed computing, Auto-tuning, 02 engineering and technology, Scheduling (computing), I/O Scheduling, I/O Forwarding, Machine learning, Reinforcement learning, Aprenentatge automàtic, 0202 electrical engineering, electronic engineering, information engineering, Informàtica::Arquitectura de computadors [Àrees temàtiques de la UPC], Input/output, High performance I/O, 020206 networking & telecommunications, Workload, Reinforcement Learning, Hardware and Architecture, Superordinadors, 020201 artificial intelligence & image processing, High performance computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software
Abstract: In this paper, we propose an approach to adapt the I/O forwarding layer of HPC systems to applications’ access patterns. I/O optimization techniques can improve performance for the access patterns they were designed to target, but they often decrease performance for others. Furthermore, these techniques usually depend on the precise tune of their parameters, which commonly falls back to the users. Instead, we propose to do it dynamically at runtime based on the I/O workload observed by the system. Our approach uses a reinforcement learning technique – contextual bandits – to make the system capable of learning the best parameter value to each observed access pattern during its execution. That eliminates the need of a complicated and time-consuming previous training phase. Our case study is the TWINS scheduling algorithm, where performance improvements depend on the time window parameter, which in turn depends on the workload. We evaluate our proposal and demonstrate it can reach a precision of 88% on the parameter selection in the first hundreds of observations of an access pattern, achieving 99% of the optimal performance. We demonstrate that the system – which is expected to live for years – will be able to adapt to changes and optimize its performance after having observed an access pattern for a few (not necessarily contiguous) minutes. This study was financed in part by the Coordenaçao de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001. It has also received support from the Conselho Nacional de Desenvolvimento Científico e Tecnologico (CNPq), Brazil; the LICIA International Laboratory; NCSA-Inria-ANL-BSC-JSC-Riken Joint-Laboratory on Extreme Scale Computing (JLESC); the Spanish Ministry of Science and Innovation under the TIN2015–65316 grant; and the Generalitat de Catalunya under contract 2014– SGR–1051. This research received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 800144.
Published: 2020

2. Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment

Author: Pierrick Gaudry, Emmanuel Thomé, Fabrice Boudot, Aurore Guillevic, Nadia Heninger, Paul Zimmermann, XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), University of California [San Diego] (UC San Diego), University of California (UC), This work was possible thanks to a 32M-hour allocation on the Juwels super-computer from the PRACE research infrastructure.Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was supported by the French 'Ministère de l'Enseignement Supérieur et de la Recherche', by the 'Conseil Régional de Lorraine', by theEuropean Union, through the 'Cyber-Entreprises' project, and by the US National Science Foundation under grant no. 1651344.High Performance Computing resources were partially provided by the EXPLOR centre hosted by the University de Lorraine.Computations carried out at the University of Pennsylvania were performed on Cisco UCS servers donated by Cisco., Daniele Micciancio, Thomas Ristenpart, Grid5000, University of California, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), This work was possible thanks to a 32M-hour allocation on the Juwels super-computer from the PRACE research infrastructure.Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was supported by the French ``Ministère de l'Enseignement Supérieur et de la Recherche', by the ``Conseil Régional de Lorraine', by theEuropean Union, through the ``Cyber-Entreprises' project, and by the US National Science Foundation under grant no.~1651344.High Performance Computing resources were partially provided by the EXPLOR centre hosted by the University de Lorraine.Computations carried out at the University of Pennsylvania were performed on Cisco UCS servers donated by Cisco., and Daniele Micciancio, Thomas Ristenpart
Subjects: FOS: Computer and information sciences, Computer Science - Cryptography and Security, Computer science, discrete logarithm, Computation, number field sieve, 02 engineering and technology, law.invention, General number field sieve, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Software, cryptanalysis, Factorization, law, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Hardware_ARITHMETICANDLOGICSTRUCTURES, Arithmetic, factoring, business.industry, Numerical digit, Factoring, Discrete logarithm, 020201 artificial intelligence & image processing, Cryptanalysis, business, Cryptography and Security (cs.CR)
Abstract: International audience; We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records.The last page of this paper also reports on the factorization of RSA-250.
Published: 2020

3. More efficient periodic traversal in anonymous undirected graphs

Author: Kunihiko Sadakane, Ioannis Lignos, Leszek Gsieniec, Ralf Klasing, Jesper Jansson, Stefan Dobrev, Russell Martin, David Ilcinkas, Wing-Kin Sung, Jurek Czyzowicz, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Institute of Mathematics, Slovak Academy of Science [Bratislava] (SAS), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Ochanomizu University, Department of Computer Science, Durham University, Principles of Informatics Research Division, National Institute of Informatics (NII), National University of Singapore (NUS), See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), INRIA Futurs, See paper for details., ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: FOS: Computer and information sciences, General Computer Science, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Constant-memory agent, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, law.invention, Theoretical Computer Science, Combinatorics, Graph exploration, law, Graph power, Line graph, Graph traversal, 0202 electrical engineering, electronic engineering, information engineering, Algorithms and data structures, Oblivious agent, Undirected graph, Mathematics, Discrete mathematics, Mobile entity, Voltage graph, Three-layer partition, Butterfly graph, Periodic graph traversal, Tree traversal, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Periodic graph (geometry), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Span tree, Period length, Computer Science - Discrete Mathematics, Computer Science(all)
Abstract: International audience; We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3.75n−2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most for oblivious agents and a period length of at most 3.5n−2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n−2, on the period length for the oblivious case.
Published: 2012

4. Adaptive control of Lipschitz time-delay systems by sigma modification with application to neuronal population dynamics

Author: Alain Destexhe, Jakub Orlowski, Antoine Chaillet, Mario Sigalotti, Laboratoire des signaux et systèmes (L2S), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Institut des Neurosciences Paris-Saclay (NeuroPSI), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Control And GEometry (CaGE ), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), This paper has received support from the Institute for Control and Decision of Paris Saclay (iCODE), France and Digiteo, France. AD was supported by the CNRS, France and the European Commission (Human Brain Project H2020-945539)., Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: 0209 industrial biotechnology, Time-delay systems, Adaptive control, General Computer Science, Computer science, Mechanical Engineering, Dynamics (mechanics), Sigma, 02 engineering and technology, Dissipation, Sigma modification, Lipschitz continuity, Nonlinear system, Neuronal populations, 020901 industrial engineering & automation, Quadratic equation, Control and Systems Engineering, Control theory, Stability in the mean, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Electrical and Electronic Engineering, Neuronal population
Abstract: International audience; Adaptive control using the -modification provides an easily implementable way to stabilize systems with uncertain or fluctuating parameters. Motivated by a specific application from neuroscience, we extend here this methodology to nonlinear time-delay systems ruled by globally Lipschitz dynamics. In order to make the result more handy in practice, we provide an explicit construction of a Lyapunov–Krasovskii functional (LKF) with linear bounds and strict dissipation rate based on the knowledge of an LKF with quadratic bounds and point-wise dissipation rate. When applied to a model of neuronal populations involved in Parkinson’s disease, the benefits with respect to a pure proportional stabilization scheme are discussed through numerical simulations.
Published: 2022

5. HInT: Hybrid and Incremental Type Discovery for Large RDF Data Sources

Author: Georgia Troullinou, Kenza Kellou-Menouer, Zoubida Kedad, Dimitris Plexousakis, Nikolaos Kardoulakis, Haridimos Kondylakis, Données et algorithmes pour une ville intelligente et durable - DAVID (DAVID), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Hellenic Foundation for Research and Innovation, ΕΛ.ΙΔ.Ε.Κ: 1147, and Work reported in this paper has been partially supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the '2nd Call for H.F.R.I. Research Projects to support Post-Doctoral Researchers' (iQARuS Project No 1147)
Subjects: Exploit, LSH, Process (engineering), Computer science, media_common.quotation_subject, 02 engineering and technology, Machine learning, computer.software_genre, RDF, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Quality (business), [INFO]Computer Science [cs], media_common, Complement (set theory), business.industry, Hybrid type discovery, Linked data, computer.file_format, Automatic summarization, Schema (genetic algorithms), 020201 artificial intelligence & image processing, Incrementality, Artificial intelligence, business, computer
Abstract: International audience; The rapid explosion of linked data has resulted into many weakly structured and incomplete data sources, where typing information might be missing. On the other hand, type information is essential for a number of tasks such as query answering, integration, summarization and partitioning. Existing approaches for type discovery, either completely ignore type declarations available in the dataset (implicit type discovery approaches), or rely only on existing types, in order to complement them (explicit type enrichment approaches). Implicit type discovery approaches are based on instance grouping, which requires an exhaustive comparison between the instances. This process is expensive and not incremental. Explicit type enrichment approaches on the other hand, are not able to identify new types and they can not process data sources that have little or no schema information. In this paper, we present HInT, the first incremental and hybrid type discovery system for RDF datasets, enabling type discovery in datasets where type declarations are missing. To achieve this goal, we incrementally identify the patterns of the various instances, we index and then group them to identify the types. During the processing of an instance, our approach exploits its type information, if available, to improve the quality of the discovered types by guiding the classification of the new instance in the correct group and by refining the groups already built. We analytically and experimentally show that our approach dominates in terms of efficiency, competitors from both worlds, implicit type discovery and explicit type enrichment while outperforming them in most of the cases in terms of quality.
Published: 2021

6. Optimizing Motor Intention Detection With Deep Learning: Towards Management of Intraoperative Awareness

Author: Laurent Bougrain, Oleksii Avilov, Anton Popov, Sébastien Rimbert, National Technical University of Ukraine 'Kyiv Polytechnic Institute' [Kiev], Analysis and modeling of neural systems by a system neuroscience approach (NEUROSYS), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Complex Systems, Artificial Intelligence & Robotics (LORIA - AIS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Oleksii Avilov was supported by scholarship from the French Embassy to Ukraine while working on this topic at the NEUROSYS team at LORIA (Université de Lorraine/CNRS/Inria), Nancy, France. Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (https://www.grid5000.fr)., Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, Computer science, Biomedical Engineering, motor imagery AAGA: accidental awareness during general anesthesia, 02 engineering and technology, Intention, Electroencephalography, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Intraoperative Awareness, 020901 industrial engineering & automation, Motor imagery, median nerve stimulation, Deep Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], intraoperative awareness during general anesthesia, 0202 electrical engineering, electronic engineering, information engineering, medicine, [INFO.INFO-IM]Computer Science [cs]/Medical Imaging, Functional electrical stimulation, Humans, Brain-computer interface (BCI), Artificial neural network, medicine.diagnostic_test, Median nerve stimulation, business.industry, electroencephalogram (EEG), Deep learning, [SCCO.NEUR]Cognitive science/Neuroscience, Pattern recognition, Linear discriminant analysis, Median nerve, medicine.anatomical_structure, machine learning, Frontal lobe, Brain-Computer Interfaces, Imagination, 020201 artificial intelligence & image processing, Artificial intelligence, business, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Algorithms, Motor cortex
Abstract: International audience; Objective: This article shows the interest in deep learning techniques to detect motor imagery (MI) from raw electroencephalographic (EEG) signals when a functional electrical stimulation is added or not. Impacts of electrode montages and bandwidth are also reported. The perspective of this work is to improve the detection of intraoperative awareness during general anesthesia. Methods: Various architectures of EEGNet were investigated to optimize MI detection. They have been compared to the state-of-the-art classifiers in Brain-Computer Interfaces (based on Riemannian geometry, linear discriminant analysis), and other deep learning architectures (deep convolution network, shallow convolutional network). EEG data were measured from 22 participants performing motor imagery with and without median nerve stimulation. Results: The proposed architecture of EEGNet reaches the best classification accuracy (83.2%) and false-positive rate (FPR 19.0%) for a setup with only six electrodes over the motor cortex and frontal lobe and for an extended 4-38 Hz EEG frequency range while the subject is being stimulated via a median nerve. Configurations with a larger number of electrodes result in higher accuracy (94.5%) and FPR (6.1%) for 128 electrodes (and respectively 88.0% and 12.9% for 13 electrodes).Conclusion: The present work demonstrates that using an extended EEG frequency band and a modified EEGNet deep neural network increases the accuracy of MI detection when used with as few as 6 electrodes which include frontal channels. Significance: The proposed method contributes to the development of Brain-Computer Interface systems based on MI detection from EEG.
Published: 2021

7. Binary level toolchain provenance identification with graph neural networks

Author: Tristan Benoit, Jean-Yves Marion, Sébastien Bardin, Carbone (CARBONE), Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), CEA- Saclay (CEA), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), This work is supported by (i) a public grant overseen by the French National Research Agency (ANR) as part of the 'Investissements d'Avenir' French PIA project 'Lorraine Université d'Excellence', reference ANR-15-IDEX-04-LUE, and (ii) has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 830927 (Concordia). Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr)., GRID5000, IMPACT-DIGITRUST, ANR-15-IDEX-0004,LUE,Isite LUE(2015), European Project: 830927,CONCORDIA(2019), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Theoretical computer science, Artificial neural network, Computer science, Binary number, graph neural networks, 020207 software engineering, 02 engineering and technology, computer.software_genre, toolchain provenance, Toolchain, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Scalability, 0202 electrical engineering, electronic engineering, information engineering, Graph reduction, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.7: Distribution, Maintenance, and Enhancement/D.2.7.5: Restructuring, reverse engineering, and reengineering, ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.5: Testing and Debugging/D.2.5.2: Diagnostics, Control flow graph, binary code analysis, 020201 artificial intelligence & image processing, Binary code, Compiler, computer, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.6: Learning
Abstract: International audience; We consider the problem of recovering the compiling chain used to generate a given stripped binary code. We present a Graph Neural Network framework at the binary level to solve this problem, with the idea to take into account the shallow semantics provided by the binary code's structured control flow graph (CFG).We introduce a Graph Neural Network, called Site Neural Network (SNN), dedicated to this problem. To attain scalability at the binary level, feature extraction is simplified by forgetting almost everything in a CFG except transfer control instructions and performing a parametric graph reduction. Our experiments show that our method recovers the compiler family with a very high F1-Score of 0.9950 while the optimization level is recovered with a moderately high F1-Score of 0.7517. On the compiler version prediction task, the F1-Score is about 0.8167 excluding the clang family. A comparison with a previous work demonstrates the accuracy and performance of this framework.
Published: 2021

8. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths

Author: Muhammad Zaid Dauhoo, Laurent Dumas, Yusra Bibi Ruhomally, Université de Maurice, Laboratoire de Mathématiques de Versailles (LMV), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), University of Mauritius, UoM, and We would like to acknowledge the assistance of Mr Maheshsingh Mungur from the University of Mauritius in the preparation of this work. This work has been conducted under the HEC (Higher Education Commission Mauritius) MPhil/PhD scholarship. The authors would also like to thank the reviewers for their constructive and valuable comments, which led to the improvement of the paper.
Subjects: Statistics and Probability, 050402 sociology, Relation (database), media_common.quotation_subject, targeted campaigns of prevention, [SDV]Life Sciences [q-bio], Population, 02 engineering and technology, relation-based, 0504 sociology, 0202 electrical engineering, electronic engineering, information engineering, Set (psychology), education, Recreation, Neighbourhood (mathematics), media_common, Consumption (economics), education.field_of_study, peer influence, Applied Mathematics, Addiction, 05 social sciences, Marijuana, Modeling and Simulation, graph cellular automaton, Graph (abstract data type), 020201 artificial intelligence & image processing, Psychology, Social psychology
Abstract: International audience; A novel approach depicting the dynamics of marijuana usage to gauge the effects of peer influence in a school population, is the site of investigation. Consumption of drug is considered as a contagious social epidemic which is spread mainly by peer influences. A relation-based graph-CA (r-GCA) model consisting of 4 states namely, Nonusers (N), Experimental users (E), Recreational users (R) and Addicts (A), is formulated in order to represent the prevalence of the epidemic on a campus. The r-GCA model is set up by local transition rules which delineates the proliferation of marijuana use. Data available in [4] is opted to verify and validate the r-GCA. Simulations of the r-GCA system are presented and discussed. The numerical results agree quite accurately with the observed data. Using the model, the enactment of campaigns of prevention targeting N, E and R states respectively were conducted and analysed. The results indicate a significant decline in marijuana consumption on the campus when a campaign of prevention targeting the latter three states simultaneously, is enacted.
Published: 2021

9. Towards a semantic indoor trajectory model: application to museum visits

Author: Claudia Marinica, Karine Zeitouni, Dimitris Kotzinos, Dan Vodislav, Alexandros Kontarinis, Données et algorithmes pour une ville intelligente et durable - DAVID (DAVID), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Equipes Traitement de l'Information et Systèmes (ETIS - UMR 8051), Ecole Nationale Supérieure de l'Electronique et de ses Applications (ENSEA)-Centre National de la Recherche Scientifique (CNRS)-CY Cergy Paris Université (CY), Horizon 2020 Framework Programme, H2020: 777695, This work was supported by the TRAJECTOIRES project funded by the Paris Seine Graduate School Humanities, Creation, Heritage, Investissement d’Avenir ANR-17-EURE-0021 – Foundation for Cultural Heritage Science., and Karine Zeitouni’s work in this paper was supported by the MASTER project that has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie-Slodowska Curie grant agreement N. 777695.
Subjects: Computer science, media_common.quotation_subject, Geography, Planning and Development, Big data, Museum visitor study, 02 engineering and technology, Space (commercial competition), Article, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Sequential Pattern Mining, Representation (mathematics), media_common, Information retrieval, business.industry, Semantic trajectory, Indoor trajectory, Analytics, Model application, Trajectory pattern mining, Trajectory, Conceptual model, 020201 artificial intelligence & image processing, Trajectory modeling, Louvre museum, business, Information Systems
Abstract: International audience; In this paper we present a new conceptual model of trajectories, which accounts for semantic and indoor space information and supports the design and implementation of context-aware mobility data mining and statistical analytics methods. Motivated by a compelling museum case study, and by what we perceive as a lack in indoor trajectory research, we combine aspects of state-of-the-art semantic outdoor trajectory models, with a semantically-enabled hierarchical symbolic representation of the indoor space, which abides by OGC’s IndoorGML standard. We drive the discussion on modeling issues that have been overlooked so far and illustrate them with a real-world case study concerning the Louvre Museum, in an effort to provide a pragmatic view of what the proposed model represents and how. We also present experimental results based on Louvre’s visiting data showcasing how state-of-the-art mining algorithms can be applied on trajectory data represented according to the proposed model, and outline their advantages and limitations. Finally, we provide a formal outline of a new sequential pattern mining algorithm and how it can be used for extracting interesting trajectory patterns.
Published: 2021

10. Evolution Control for parallel ANN-assisted simulation-based optimization application to Tuberculosis Transmission Control

Author: Mohand-Said Mezmaz, Nouredine Melab, Romain Ragonnet, Guillaume Briffoteaux, Daniel Tuyttens, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), University of Mons [Belgium] (UMONS), Monash University [Melbourne], Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), and Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).
Subjects: Artificial Neural Network, Computer Networks and Communications, Computer science, Monte Carlo method, Context (language use), 02 engineering and technology, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Simulation-based optimization, Surrogate-assisted Optimization, 0202 electrical engineering, electronic engineering, information engineering, Massively parallel, Dropout (neural networks), Artificial neural network, Evolution Control, business.industry, Deep learning, 020206 networking & telecommunications, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Supercomputer, Computer engineering, Hardware and Architecture, 020201 artificial intelligence & image processing, Artificial intelligence, Massively Parallel Computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Software, Simulation
Abstract: International audience; In many optimal design searches, the function to optimise is a simulator that is computationally expensive. While current High Performance Computing (HPC) methods are not able to solve such problems efficiently, parallelism can be coupled with approximate models (surrogates or meta-models) that imitate the simulator in timely fashion to achieve better results. This combined approach reduces the number of simulations thanks to surrogate use whereas the remaining evaluations are handled by supercomputers. While the surrogates' ability to limit computational times is very attractive, integrating them into the over-arching optimization process can be challenging. Indeed, it is critical to address the major trade-off between the quality (precision) and the efficiency (execution time) of the resolution. In this article, we investigate Evolution Controls (ECs) which are strategies that define the alternation between the simulator and the surrogate within the optimization process. We propose a new EC based on the prediction uncertainty obtained from Monte Carlo Dropout (MCDropout), a technique originally dedicated to quantifying uncertainty in deep learning. Investigations of such uncertainty-aware ECs remain uncommon in surrogate-assisted evolutionary optimization. In addition, we use parallel computing in a complementary way to address the high computational burden. Our new strategy is implemented in the context of a pioneering application to Tuberculosis Transmission Control. The reported results show that the MCDropout-based EC coupled with massively parallel computing outperforms strategies previously proposed in the field of surrogate-assisted optimization.
Published: 2020

11. On the complexity of computing integral bases of function fields

Author: Simon Abelard, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Boulier F., England M., Sadykov T.M., and Vorozhtsov E.V.
Subjects: Algebraic function field, Computer Science - Symbolic Computation, FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 050101 languages & linguistics, Plane curve, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], 02 engineering and technology, Symbolic Computation (cs.SC), Commutative Algebra (math.AC), Puiseux series, Mathematics - Algebraic Geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Polynomial matrices, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 0501 psychology and cognitive sciences, Linear algebra, Algebraic Geometry (math.AG), Mathematics, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Irreducible polynomial, 05 social sciences, Basis (universal algebra), Function (mathematics), Mathematics - Commutative Algebra, 020201 artificial intelligence & image processing, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Monic polynomial
Abstract: Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to B\"ohm et al. and achieve a quasi-optimal runtime., Comment: Preliminary version
Published: 2020

12. A comparative study of high-productivity high-performance programming languages for parallel metaheuristics

Author: Jan Gmys, Nouredine Melab, Daniel Tuyttens, El-Ghazali Talbi, Tiago Carneiro, University of Mons [Belgium] (UMONS), Faculté polytechnique de Mons, Université de Mons (UMons), Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université de Lille, and The experiments presented in this paper were carried out on the Grid’5000 testbed, hosted by INRIA and including several other organizations. Wethank Bradford Chamberlain, Elliot Ronaghan (Cray inc.) and Louis Jenkins (University of Rochester) for their support on Chapel’s Gitter platform.
Subjects: Parallel computing, General Computer Science, Quadratic assignment problem, Computer science, General Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Thread (computing), Metaheuristics, computer.software_genre, High productivity, Chapel, 0202 electrical engineering, electronic engineering, information engineering, Metaheuristic, computer.programming_language, Programming language, 05 social sciences, 050301 education, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Python (programming language), High-productivity languages, Parallel metaheuristics, Scalability, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0503 education, computer
Abstract: International audience; Parallel metaheuristics require programming languages that provide both, high performance and a high level of programmability. This paper aims at providing a useful data point to help practitioners gauge the difficult question of whether to invest time and effort into learning and using a new programming language. To accomplish this objective, three productivity-aware languages (Chapel, Julia, and Python) are compared in terms of performance, scalability and productivity. To the best of our knowledge, this is the first time such a comparison is performed in the context of parallel metaheuristics. As a test-case, we implement two parallel metaheuristics in three languages for solving the 3D Quadratic Assignment Problem (Q3AP), using thread-based parallelism on a multi-core shared-memory computer. We also evaluate and compare the performance of the three languages for a parallel fitness evaluation loop, using four different test-functions with different computational characteristics. Besides providing a comparative study, we give feedback on the implementation and parallelization process in each language.
Published: 2020

13. Parallel Surrogate-assisted Optimization: Batched Bayesian Neural Network-assisted GA versus q-EGO

Author: Guillaume Briffoteaux, Romain Ragonnet, Jan Gmys, Nouredine Melab, Mohand Mezmaz, Maxime Gobert, Daniel Tuyttens, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), University of Mons [Belgium] (UMONS), Monash University [Melbourne], Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques [Mons], Université de Mons (UMons), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), and Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).
Subjects: General Computer Science, Computer science, General Mathematics, Evolutionary algorithm, 02 engineering and technology, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Machine learning, computer.software_genre, Surrogate model, Genetic algorithm, Surrogate-assisted Optimization, 0202 electrical engineering, electronic engineering, information engineering, Massively parallel, Global optimization, Artificial neural network, Bayesian Optimization, business.industry, 05 social sciences, Bayesian optimization, Evolutionary Algorithm, 050301 education, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Efficient Global Optimization, Benchmark (computing), 020201 artificial intelligence & image processing, Artificial intelligence, Massively Parallel Computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, 0503 education, computer, Simulation
Abstract: International audience; Surrogate-based optimization is widely used to deal with long-running black-box simulation-based objective functions. Actually, the use of a surrogate model such as Kriging or Artificial Neural Network allows to reduce the number of calls to the CPU time-intensive simulator. Bayesian optimization uses the ability of surrogates to provide useful information to help guiding effectively the optimization process. In this paper, the Efficient Global Optimization (EGO) reference framework is challenged by a Bayesian Neural Network-assisted Genetic Algorithm, namely BNN-GA. The Bayesian Neural Network (BNN) surrogate is chosen for its ability to provide an uncertainty measure of the prediction that allows to compute the Expected Improvement of a candidate solution in order to improve the exploration of the objective space. BNN is also more reliable than Kriging models for high-dimensional problems and faster to set up thanks to its incremental training. In addition, we propose a batch-based approach for the parallelization of BNN-GA that is challenged by a parallel version of EGO, called q-EGO. Parallel computing is a highly important complementary way (to surrogates) to deal with the computational burden of simulation-based optimization. The comparison of the two parallel approaches is experimentally performed through several benchmark functions and two real-world problems within the scope of Tuberculosis Transmission Control (TBTC). The study presented in this paper proves that parallel batched BNN-GA is a viable alternative to q-EGO approaches being more suitable for high-dimensional problems, parallelization impact, bigger databases and moderate search budgets. Moreover, a significant improvement of the solutions is obtained for the two TBTC problems tackled.
Published: 2020

14. Foreground-Background Ambient Sound Scene Separation

Author: Michel Olvera, Romain Serizel, Emmanuel Vincent, Gilles Gasso, Speech Modeling for Facilitating Oral-Based Communication (MULTISPEECH), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), This work was made with the support of the French National Research Agency, in the framework of the project LEAUDS 'Learning to understandaudio scenes' (ANR-18-CE23-0020). Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientificinterest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr)., GRID5000, ANR-18-CE23-0020,LEAUDS,Apprentissage statistique pour la compréhension de scènes audio(2018), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU), and ANR-18-CE23-0020,LEAUDS,LEARNING TO UNDERSTAND AUDIO SCENES(2018)
Subjects: Normalization (statistics), Signal Processing (eess.SP), FOS: Computer and information sciences, Sound (cs.SD), Computer Science - Machine Learning, Computer science, Generalization, Ambient noise level, 02 engineering and technology, Computer Science - Sound, Machine Learning (cs.LG), Signal-to-noise ratio, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Audio and Speech Processing (eess.AS), 0202 electrical engineering, electronic engineering, information engineering, ambient sound scenes, FOS: Electrical engineering, electronic engineering, information engineering, Foreground-background, Computer vision, generalization ability, Electrical Engineering and Systems Science - Signal Processing, Sound (geography), Signal processing, geography, geography.geographical_feature_category, business.industry, Deep learning, deep learning, audio source separation, 020206 networking & telecommunications, Feature (computer vision), [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], 020201 artificial intelligence & image processing, Artificial intelligence, business, Electrical Engineering and Systems Science - Audio and Speech Processing
Abstract: International audience; Ambient sound scenes typically comprise multiple short events occurring on top of a somewhat stationary background. We consider the task of separating these events from the background, which we call foreground-background ambient sound scene separation. We propose a deep learning-based separation framework with a suitable feature normaliza-tion scheme and an optional auxiliary network capturing the background statistics, and we investigate its ability to handle the great variety of sound classes encountered in ambient sound scenes, which have often not been seen in training. To do so, we create single-channel foreground-background mixtures using isolated sounds from the DESED and Audioset datasets, and we conduct extensive experiments with mixtures of seen or unseen sound classes at various signal-to-noise ratios. Our experimental findings demonstrate the generalization ability of the proposed approach.
Published: 2020

15. Towards ultra-scale Branch-and-Bound using a high-productivity language

Author: Tiago Carneiro, Daniel Tuyttens, Jan Gmys, Nouredine Melab, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), University of Mons [Belgium] (UMONS), and The experiments presented in this paper were carried out on the Grid’5000 testbed, hosted by INRIA and including several other organizations. Wethank Bradford Chamberlain, Elliot Ronaghan (Cray inc.) and Paul Hargrove (Berkeley lab.) for helping us to run GASNet on GRID5000. We also thank Michael Ferguson, Lydia Duncan (Cray inc.), and Louis Jenkins (University of Rochester) for their support on Chapel’s Gitter platform.
Subjects: POSIX Threads, Speedup, Branch and bound, Job shop scheduling, Computer Networks and Communications, Computer science, PGAS, Branch-and-Bound, 020206 networking & telecommunications, 02 engineering and technology, Parallel computing, Load balancing (computing), Hardware and Architecture, Ultra-scale optimization, Chapel, Scalability, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Partitioned global address space, MPI+X, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, Software, computer.programming_language
Abstract: Due to the highly irregular nature and prohibitive execution times of Branch-and-Bound (B&B) algorithms applied to combinatorial optimization problems (COPs), their parallelization has received the se two last decades great attention. Indeed, significant efforts have been made to revisit the parallelization of B&B following the rapid evolution of high-performance computing technologies dealing with their associated scientific and technical challenges. However, these parallelization efforts have always been guided by the performance objective setting aside programming productivity. Nevertheless, this latter is crucial for designing ultra-scale algorithms able to harness modern supercomputers which are increasingly complex, including millions of processing cores and heterogeneous building-block devices. In this paper, we investigate the partitioned global address space (PGAS)-based approach using Chapel for the productivity-aware design and implementation of distributed B&B for solving large COPs. The proposed algorithms are intensively experimented using the Flow-shop scheduling problem as a test-case. The Chapel-based implementation is compared to its MPI+X-based traditionally used counterpart in terms of performance, scalability, and productivity. The results show that Chapel is much more expressive and up to 7 . 8 × more productive than MPI+Pthreads. In addition, the Chapel-based search presents performance equivalent to MPI+Pthreads for its best results on 1024 cores and reaches up to 84 % of the linear speedup. However, there are cases where the built-in load balancing provided by Chapel cannot produce regular load among computer nodes. In such cases, the MPI-based search can be up to 4 . 2 × faster and reaches speedups up to 3 × higher than its Chapel-based counterpart. Thorough feedback on the experience is given, pointing out the strengths and limitations of the two opposite approaches (Chapel vs. MPI+X). To the best of our knowledge, the present study is pioneering within the context of exact parallel optimization.
Published: 2020

16. Transfer learning of the expressivity using flow metric learning in multispeaker text-to-speech synthesis

Author: Ajinkya Kulkarni, Vincent Colotte, Denis Jouvet, Jouvet, Denis, Speech Modeling for Facilitating Oral-Based Communication (MULTISPEECH), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr)., Grid'5000, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)
Subjects: Computer science, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, Mean opinion score, Speech recognition, deep metric learning, Inference, Speech synthesis, 02 engineering and technology, Latent variable, 010501 environmental sciences, [INFO] Computer Science [cs], computer.software_genre, expressivity, 01 natural sciences, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], variational autoencoder, text-to-speech, 0105 earth and related environmental sciences, Acoustic model, Speaker recognition, inverse autoregressive flow, Autoencoder, Metric (mathematics), Embedding, 020201 artificial intelligence & image processing, Transfer of learning, computer
Abstract: International audience; In this paper, we present a novel deep metric learning architecture along with variational inference incorporated in a paramet-ric multispeaker expressive text-to-speech (TTS) system. We proposed inverse autoregressive flow (IAF) as a way to perform the variational inference, thus providing flexible approximate posterior distribution. The proposed approach condition the text-to-speech system on speaker embeddings so that latent space represents the emotion as semantic characteristics. For representing the speaker, we extracted speaker em-beddings from the x-vector based speaker recognition model trained on speech data from many speakers. To predict the vocoder features, we used the acoustic model conditioned on the textual features as well as on the speaker embedding. We transferred the expressivity by using the mean of the latent variables for each emotion to generate expressive speech in different speaker's voices for which no expressive speech data is available. We compared the results obtained using flow-based variational inference with variational autoencoder as a base-line model. The performance measured by mean opinion score (MOS), speaker MOS, and expressive MOS shows that N-pair loss based deep metric learning along with IAF model improves the transfer of expressivity in the desired speaker's voice in synthesized speech.
Published: 2020

17. Computing AES related-key differential characteristics with constraint programming

Author: Christine Solnon, Marine Minier, David Gerault, Pascal Lafourcade, Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), This research was conducted with the support of the FEDER program of 2014-2020, the region council of Auvergne-Rhône-Alpes, the GDR-IA, and the ANR (DeCrypt ANR-18-CE39-0007). We thank the reviewers for their comments that helped us improving the paper, Jérémie Detrey for implementing the C code that checks the completeness of the sets xorEq_l, Charles Prud’homme and Jean-Guillaume Fages for their technical support on the use of Choco, and Neng-Fa Zhou for his technical support on the use of Picat., ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Linguistics and Language, Differential cryptanalysis, Theoretical computer science, Optimization problem, Computer science, 02 engineering and technology, Encryption, Language and Linguistics, law.invention, Constraint Programming, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Artificial Intelligence, law, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Constraint programming, Block cipher, AES, business.industry, Advanced Encryption Standard, Key (cryptography), 020201 artificial intelligence & image processing, Cryptanalysis, business
Abstract: International audience; Cryptanalysis aims at testing the properties of encryption processes, and this usually implies solving hard optimization problems. In this paper, we focus on related-key differential attacks for the Advanced Encryption Standard (AES), which is the encryption standard for block ciphers. To mount these attacks, cryptanalysts need to solve the optimal related-key differential characteristic problem. Dedicated approaches do not scale well for this problem, and need weeks to solve its hardest instances. In this paper, we improve existing Constraint Programming (CP) approaches for computing optimal related-key differential characteristics: we add new constraints that detect inconsistencies sooner, and we introduce a new decomposition of the problem in two steps. These improvements allow us to compute all optimal related-key differential characteristics for AES-128, AES-192 and AES-256 in a few hours.
Published: 2020

18. Deep Variational Metric Learning for Transfer of Expressivity in Multispeaker Text to Speech

Author: Vincent Colotte, Ajinkya Kulkarni, Denis Jouvet, Speech Modeling for Facilitating Oral-Based Communication (MULTISPEECH), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Experiments presented in this paper were carried out using the Grid5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations. (see https://www.grid5000.fr), and Grid'5000
Subjects: Computer science, Speech recognition, deep metric learning, Contrast (statistics), 020206 networking & telecommunications, Speech synthesis, 02 engineering and technology, expressivity, computer.software_genre, Speaker recognition, Autoencoder, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Identity (music), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Metric (mathematics), 0202 electrical engineering, electronic engineering, information engineering, variational autoencoder, 020201 artificial intelligence & image processing, Expressivity (genetics), text-to-speech, Representation (mathematics), computer
Abstract: In this paper, we propose an approach relying on multiclass N-pair loss based deep metric learning in recurrent conditional variational autoencoder (RCVAE). We used RCVAE for implementation of multispeaker expressive text-to-speech (TTS) system. The proposed approach condition text-to-speech system on speaker embeddings, and leads to clustering the latent space representation with respect to emotion. The deep metric learning helps to reduce the intra-class variance and increase the inter-class variance in latent space. Thus, we present multiclass N-pair loss to enhance the meaningful representation of the latent space. For representing the speaker, we extracted speaker embed-dings from the x-vector based speaker recognition model trained on speech data from many speakers. To predict the vocoder features, we used RCVAE for the acoustic modeling, in which the model is conditioned on the textual features as well as on the speaker embedding. We transferred the expressivity by using the mean of the latent variables for each emotion to generate expressive speech in different speaker's voices for which no expressive speech data is available. We compared the results with those of the RCVAE model without multiclass N-pair loss as baseline model. The performance measured by mean opinion score (MOS), speaker MOS, and expressive MOS shows that N-pair loss based deep metric learning significantly improves the transfer of expressivity in the target speaker's voice in synthesized speech.
Published: 2020

19. Automatic Waypoint Generation to Improve Robot Navigation Through Narrow Spaces

Author: Javier Gonzalez-Jimenez, Jose-Raul Ruiz-Sarmiento, Cipriano Galindo, Javier Monroy, Francisco-Angel Moreno, Machine Perception and Intelligent Robotics Group (MAPIR), [Moreno,FA, Monroy,J, Ruiz-Sarmiento,JR, Galindo,C, Gonzalez-Jimenez,J] Machine Perception and Intelligent Robotics Group (MAPIR), Dept. of System Engineering and Automation Biomedical Research Institute of Malaga (IBIMA), University of Malaga, Málaga, Spain., and This work has been supported by the research projects WISER (DPI2017-84827-R), funded by the Spanish Government and the European Regional Development’s Funds (FEDER), MoveCare (ICT-26-2016b-GA-732158), funded by the European H2020 program, and by a postdoc contract from the I-PPIT program of the University of Malaga. The publication of this paper has been funded by the University of Malaga.
Subjects: 0209 industrial biotechnology, Traverse, Phenomena and Processes::Mathematical Concepts::Algorithms [Medical Subject Headings], Computer science, Chemicals and Drugs::Inorganic Chemicals::Free Radicals::Reactive Oxygen Species [Medical Subject Headings], waypoint generation, Real-time computing, Information Science::Information Science::Computing Methodologies::Artificial Intelligence::Robotics [Medical Subject Headings], 02 engineering and technology, lcsh:Chemical technology, Biochemistry, Article, Analytical Chemistry, Task (project management), Waypoint generation, Organisms::Eukaryota::Animals::Chordata::Vertebrates::Mammals::Primates::Haplorhini::Catarrhini::Hominidae::Humans [Medical Subject Headings], Waypoint, robot deployment, 020901 industrial engineering & automation, Information Science::Information Science::Computing Methodologies::Artificial Intelligence [Medical Subject Headings], Navigation assistant, robot navigation, Artificial Intelligence, mobile robots, robot localization, 0202 electrical engineering, electronic engineering, information engineering, Mobile robots, Mapa, lcsh:TP1-1185, Electrical and Electronic Engineering, Instrumentation, business.industry, Robot localization, Robotics, Mobile robot, Atomic and Molecular Physics, and Optics, Inteligencia artificial, Trajectory, Robot navigation, Map, Robot, 020201 artificial intelligence & image processing, Noise (video), Artificial intelligence, business, Robótica, Robot deployment
Abstract: In domestic robotics, passing through narrow areas becomes critical for safe and effective robot navigation. Due to factors like sensor noise or miscalibration, even if the free space is sufficient for the robot to pass through, it may not see enough clearance to navigate, hence limiting its operational space. An approach to facing this is to insert waypoints strategically placed within the problematic areas in the map, which are considered by the robot planner when generating a trajectory and help to successfully traverse them. This is typically carried out by a human operator either by relying on their experience or by trial-and-error. In this paper, we present an automatic procedure to perform this task that: (i) detects problematic areas in the map and (ii) generates a set of auxiliary navigation waypoints from which more suitable trajectories can be generated by the robot planner. Our proposal, fully compatible with the robotic operating system (ROS), has been successfully applied to robots deployed in different houses within the H2020 MoveCare project. Moreover, we have performed extensive simulations with four state-of-the-art robots operating within real maps. The results reveal significant improvements in the number of successful navigations for the evaluated scenarios, demonstrating its efficacy in realistic situations.
Published: 2019
Full Text: View/download PDF

20. Energy-efficient joint video encoding and transmission framework for WVSN

Author: Youssef Fakhri, Patrick Corlay, Driss Aboutajdine, François-Xavier Coudoux, Othmane Alaoui-Fdili, Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), Laboratoire de Recherche en Informatique et Télécommunications [Rabat] (GSCM-LRIT), University of Mohammed V, COMmunications NUMériques - IEMN (COMNUM - IEMN), Institut d’Électronique, de Microélectronique et de Nanotechnologie - Département Opto-Acousto-Électronique - UMR 8520 (IEMN-DOAE), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France), Faculté des Sciences [Kenitra], Université Ibn Tofaïl (UIT), Université Mohammed V de Rabat [Agdal] (UM5), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), and Acknowledgements This research was supported by the excellence fellowships program of the National Center for Scientific and Technical Research (CNRST) of Morocco (G01/003) and the Franco-Moroccan cooperation program in STICs for the research project 'RECIF'. The authors would also like to thank the editorial office Christian Malan, the editor-in-chief, the guest editors as well as the anonymous reviewers for their efforts and valuable comments and suggestions that have led to improvements in this paper.
Subjects: Computer Networks and Communications, Computer science, Real-time computing, 02 engineering and technology, Video quality, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [SPI]Engineering Sciences [physics], Packet loss, Video encoding, Region of interest, 0202 electrical engineering, electronic engineering, information engineering, Media Technology, [INFO]Computer Science [cs], Block-matching algorithm, "Energy-efficiency in WVSN", business.industry, 020206 networking & telecommunications, Scalable Video Coding, [SPI.TRON]Engineering Sciences [physics]/Electronics, "Video distortion prediction", Rate–distortion optimization, Transmission (telecommunications), Hardware and Architecture, "Cross-layer design", 020201 artificial intelligence & image processing, "Energy consumption prediction", business, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Wireless sensor network, Encoder, "Energy-efficient reliable routing", Software, Computer network
Abstract: JIF=2.101; International audience; In this paper, we propose an energy-efficient joint video encoding and transmission framework for network lifetime extension, under an end-to-end video quality constraint in the Wireless Video Sensor Networks (WVSN). This framework integrates an energy-efficient and adaptive intra-only video encoding scheme based on the H.264/AVC standard, that outputs two service differentiated macroblocks categories, namely the Region Of Interest and the Background. Empirical models describing the physical behavior of the measured energies and distortions, during the video encoding and transmission phases, are derived. These models enable the video source node to dynamically adapt its video encoder's configuration in order to meet the desired quality, while extending the network lifetime. An energy-efficient and reliable multipath multi-priority routing protocol is proposed to route the encoded streams to the sink, while considering the remaining energy, the congestion level as well as the packet loss rates of the intermediate nodes. Moreover, this protocol interacts with the application layer in order to bypass congestion situations and continuously feed it with current statistics. Through extensive numerical simulations, we demonstrate that the proposed framework does not only extend the video sensor lifetime by 54%, but it also performs significant end-to-end video quality enhancement of 35% in terms of Mean Squared Error (MSE) measurement.
Published: 2017

21. A creative prototype illustrating the ambient user experience of an intelligent future factory

Author: Petri Mannonen, Hannu Paunonen, Eija Kaasinen, Maiju Aikala, Tiina Kymäläinen, Lauri Lehtikunnas, Jouni Ruotsalainen, Tomi Heimonen, Jaakko Hakulinen, VTT Technical Research Centre of Finland, Tampere University, University of Wisconsin-Madison, Department of Computer Science, KCL Paper Science Centre, R and D Valmet Automation Inc., Aalto-yliopisto, Aalto University, Viestintätieteiden tiedekunta - Faculty of Communication Sciences, and University of Tampere
Subjects: Industry 4.0, Computer science, prototyping process, 02 engineering and technology, prototypointi, käyttäjäkeskeinen suunnittelu, älykkäät ympäristöt, user experience research, User experience design, surveys, ambient intelligence, Human–computer interaction, 0202 electrical engineering, electronic engineering, information engineering, 0501 psychology and cognitive sciences, Tietojenkäsittely ja informaatiotieteet - Computer and information sciences, technological trends, 050107 human factors, Ambient intelligence, factories of the futures, business.industry, user-centered design (UCD), science fiction prototyping (SFP), 05 social sciences, process control work, Industrial research, user experience design, science fictions, human computer interaction, Factory (object-oriented programming), user centered design UCD, 020201 artificial intelligence & image processing, industrial research, tehdasvalvomot, käyttäjäkokemus, business, (ambient) user experience (UX) design, Sähkö-, automaatio- ja tietoliikennetekniikka, elektroniikka - Electronic, automation and communications engineering, electronics, Software
Abstract: This article introduces user experience research that has been carried out by evaluating a video-illustrated science fiction prototype with process control workers. Essentially, the prototype 'A remote operator's day in a future control center in 2025' was aimed at discovering opportunities for new interaction methods and ambient intelligence for the factories of the future. The theoretical objective was to carry out experience design research, which was based on explicit ambient user experience goals in the nominated industrial work context. This article describes the complete creative prototyping process, starting from the initial user research that included evaluations of current work practices, technological trend studies and co-design workshops, and concluding with user research that assessed the final design outcome, the science fiction prototype. The main contribution of the article is on the ambient user experience goals, the creation process of the video-illustrated science fiction prototype, and on the reflection of how the experience-driven prototype was evaluated in two research setups: as video sequences embedded in a Web survey, and as interviews carried out with expert process control workers. For the science fiction prototyping process, the contribution demonstrates how the method may employ video-illustration as a means for future-oriented user experience research, and how complementary user-centered methods may be used to validate the results.
Published: 2017

22. Analyzing the impact of speaker localization errors on speech separation for automatic speech recognition

Author: Emmanuel Vincent, Sunit Sivasankaran, Dominique Fohr, Speech Modeling for Facilitating Oral-Based Communication (MULTISPEECH), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Grid'5000, ANR-16-CE33-0006,VOCADOM,Commande vocale robuste adaptée à la personne et au contexte pour l'autonomie à domicile(2016), This work was made with the support of the French National Research Agency, in the framework of the project VOCADOM 'Robust voice commandadapted to the user and to the context for AAL' (ANR-16-CE33-0006). Experiments presented in this paper were carried out using the Grid’5000testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several universities as well as other organizations (see https://www.grid5000.fr) and using the EXPLOR centre, hosted by the University of Lorraine., Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)
Subjects: Multichannel speech separation, WSJ0-2mix reverberated, Signal processing, Noise measurement, Artificial neural network, Computer science, Speech recognition, Word error rate, 020206 networking & telecommunications, 02 engineering and technology, Speech processing, Signal-to-noise ratio, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Audio and Speech Processing (eess.AS), [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], 0202 electrical engineering, electronic engineering, information engineering, FOS: Electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Adaptive beamformer, Electrical Engineering and Systems Science - Audio and Speech Processing
Abstract: We investigate the effect of speaker localization on the performance of speech recognition systems in a multispeaker, multichannel environment. Given the speaker location information, speech separation is performed in three stages. In the first stage, a simple delay-and-sum (DS) beamformer is used to enhance the signal impinging from the speaker location which is then used to estimate a time-frequency mask corresponding to the localized speaker using a neural network. This mask is used to compute the second order statistics and to derive an adaptive beamformer in the third stage. We generated a multichannel, multispeaker, reverberated, noisy dataset inspired from the well studied WSJ0-2mix and study the performance of the proposed pipeline in terms of the word error rate (WER). An average WER of $29.4$% was achieved using the ground truth localization information and $42.4$% using the localization information estimated via GCC-PHAT. The signal-to-interference ratio (SIR) between the speakers has a higher impact on the ASR performance, to the extent of reducing the WER by $59$% relative for a SIR increase of $15$ dB. By contrast, increasing the spatial distance to $50^\circ$ or more improves the WER by $23$% relative only, Comment: Submitted to ICASSP 2020
Published: 2019
Full Text: View/download PDF

23. Linear Search by a Pair of Distinct-Speed Robots

Author: Tomasz Kociumaka, Jurek Czyzowicz, David Ilcinkas, Leszek Gąsieniec, Ralf Klasing, Dominik Pająk, Evangelos Bampas, School of of Electrical and Computer Engineering [Athens] (School of E.C.E), National Technical University of Athens [Athens] (NTUA), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), University of Warsaw (UW), Institute of informatics [Wrocław], See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Pajak, Dominik S, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institute of Informatics [Warsaw], Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW)-University of Warsaw (UW), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: Engineering, General Computer Science, Computer science, different speeds, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Bang-bang robot, linear search, 01 natural sciences, Article, Computer Science::Robotics, Position (vector), mobile robots, 0202 electrical engineering, electronic engineering, information engineering, Cartesian coordinate robot, Point (geometry), Computer vision, [INFO]Computer Science [cs], Online algorithm, Simulation, Linear search, 021103 operations research, business.industry, Applied Mathematics, Mobile robot, Computer Science Applications, 010201 computation theory & mathematics, group search, Moment (physics), Line (geometry), Robot, 020201 artificial intelligence & image processing, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business
Abstract: Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{17}+4\approx 8.123$$\end{document}17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.
Published: 2019

24. Polyhedral Dataflow Programming: a Case Study

Author: Laure Gonnord, Romain Fontaine, Lionel Morel, CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, CASH - Compilation and Analysis, Software and Hardware (CASH), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), CEA Tech en régions (CEA-TECH-Reg), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), We are grateful to people at Kalray for allowing us to experiment with their ΣC compiler. Some of the experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inriaand including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).This work was also partially funded by the French National Agency of Research in theCODAS Project (ANR-17-CE23-0004-01), ANR-17-CE23-0004,CODAS,Ordonnancement de programmes à structures de données complexes(2017), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: parallelism, dataflow programming, Computer science, Programming language, Dataflow, Dataflow programming, 020206 networking & telecommunications, 02 engineering and technology, Load balancing (computing), runtime system, computer.software_genre, Toolchain, Runtime system, load-balancing, 0202 electrical engineering, electronic engineering, information engineering, compilation, 020201 artificial intelligence & image processing, Compiler, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer
Abstract: International audience; Dataflow languages expose the application's potential parallelism naturally and have thus been studied and developed for the past thirty years as a solution for harnessing the increasing hardware parallelism. However, when generating code for parallel processors, current dataflow compilers only take into consideration the overall dataflow network of the application. This leaves out the potential parallelism that could be extracted from the internals of agents, typically when those include loop nests, for instance, but also potential application of intra-agent pipelining, or task splitting and rescheduling. In this work, we study the benefits of jointly using polyhedral compilation with dataflow languages. More precisely, we propose to expend the parallelization of dataflow programs by taking into account the parallelism exposed by loop nests describing the internal behavior of the program's agents. This approach is validated through the development of a prototype toolchain based on an extended version of the ΣC language. We demonstrate the benefit of this approach and the potentiality of further improvements on relevant case studies.
Published: 2018

25. Checksum-Filtered List Decoding Applied to H.264 and H.265 Video Error Correction

Author: Patrick Corlay, Stephane Coulombe, Firouzeh Golaghazadeh, François-Xavier Coudoux, Institut d’Électronique, de Microélectronique et de Nanotechnologie - Département Opto-Acousto-Électronique - UMR 8520 (IEMN-DOAE), Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), COMmunications NUMériques - IEMN (COMNUM - IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), This work was supported by the Natural Sciences and Engineering Research Council of Canada Discovery Grant. This paper was recommended by Associate Editor Siwei Ma, Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), and Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)
Subjects: Computer science, Real-time computing, List decoding, 02 engineering and technology, Data_CODINGANDINFORMATIONTHEORY, Smacker video, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], "Video Transmission", [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [SPI]Engineering Sciences [physics], "H.265", 0202 electrical engineering, electronic engineering, information engineering, Media Technology, [INFO]Computer Science [cs], Electrical and Electronic Engineering, Bitstream, Motion compensation, "List Decoding", Network packet, "Video Error Correction", 020206 networking & telecommunications, computer.file_format, Coding tree unit, Scalable Video Coding, [SPI.TRON]Engineering Sciences [physics]/Electronics, "High Efficiency Video Coding (HEVC)", "H.264", Checksum, "Checksum", 020201 artificial intelligence & image processing, Multiview Video Coding, Error detection and correction, Algorithm, computer, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract: JIF=4.046; International audience; The latest video coding standards, H.264 and H.265, are highly vulnerable in error-prone networks. Reconstructed packets may exhibit significant degradation in terms of peak signal-to-noise ratio and visual quality. This paper presents a novel list-decoding approach exploiting the receiver side user datagram protocol (UDP) checksum. The proposed method identifies the possible locations of errors by analyzing the pattern of the calculated UDP checksum. This permits considerably reducing the number of candidate bitstreams in comparison to conventional list decoding approaches. When a packet composed of N bits contains a single-bit error, instead of considering N candidate bitstreams, as is the case in conventional list decoding approaches, the proposed approach considers N/32 candidate bitstreams, leading to a reduction of 97% of the number of candidates. For a two-bit error, the reduction increases to 99.6%. The method's performance is evaluated using H.264 and H.265 test model software. Our simulation results reveal that, on average, the error was corrected perfectly 80%-90% of the time (the original bitstream was recovered). In addition, the proposed approach provides, on average, a 2.79-dB gain over frame copy (FC) error concealment using the joint model and a 3.57-dB gain over our implementation of FC error concealment in the High Efficiency Video Coding test model.
Published: 2018

26. {3D} Morphable Face Models -- Past, Present and Future

Author: Sami Romdhani, Michael Zollhoefer, William A. P. Smith, Volker Blanz, Adam Kortylewski, Thabo Beeler, Thomas Vetter, Florian Bernard, Christian Theobalt, Bernhard Egger, Ayush Tewari, Timo Bolkart, Stefanie Wuhrer, Massachusetts Institute of Technology (MIT), University of York [York, UK], Max Planck Institute for Informatics [Saarbrücken], Capture and Analysis of Shapes in Motion (MORPHEO), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Stanford University, Disney Research, Johns Hopkins University (JHU), Idemia, Universität Siegen [Siegen], University of Basel (Unibas), This survey paper was initiated at the Dagstuhl Seminar 19102 on 3D Morphable Models [Egger et al. 2019] and contains ideas resulting from discussions at this seminar. This survey paper was partially funded by Early PostDoc Mobility Grant, Swiss National Science Foundation P2BSP2_178643, ERC Consolidator Grant 4DRepLy and the Max Planck Center for Visual Computing and Communications (MPC-VCC). We thank Barış Geçer for his help on the teaser figure, and Haiwen Feng for providing the FLAME texture space. We thank the anonymous reviewers whose comments have greatly improved this manuscript., Capture and Analysis of Shapes in Motion [2016-2019] (MORPHEO [2016-2019]), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jean Kuntzmann [2016-2019] (LJK [2016-2019]), Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019] (Grenoble INP [2007-2019])-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019] (Grenoble INP [2007-2019])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Stanford University [Stanford], and University of Siegen
Subjects: FOS: Computer and information sciences, Image formation, Computer Science - Machine Learning, Computer science, Computer Vision and Pattern Recognition (cs.CV), Analysis-by-Synthesis, Computer Science - Computer Vision and Pattern Recognition, 02 engineering and technology, Statistical Modelling, Machine Learning (cs.LG), Computer graphics, Computer Science - Graphics, 0202 electrical engineering, electronic engineering, information engineering, Computer Graphics, Generative Models, Graphics, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], 020207 software engineering, Computer Graphics and Computer-Aided Design, Data science, Graphics (cs.GR), [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], 3D Computer Vision, 13. Climate action, Face (geometry), 020201 artificial intelligence & image processing
Abstract: In this paper, we provide a detailed survey of 3D Morphable Face Models over the 20 years since they were first proposed. The challenges in building and applying these models, namely capture, modeling, image formation, and image analysis, are still active research topics, and we review the state-of-the-art in each of these areas. We also look ahead, identifying unsolved challenges, proposing directions for future research and highlighting the broad range of current and future applications., ACM Transactions on Graphics (TOG)
Full Text: View/download PDF

27. Observer design for linear singular time-delay systems

Author: Francisco Javier Bejarano, Gang Zheng, Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Escuela Superior de Ingeniería Mecánica y Eléctrica - Unidad Profesional Ticomán (ESIME-UPT), Instituto Politecnico Nacional [Mexico] (IPN), This paper was supported in part by Ministry of Higher Education and Research Nord-Pas de Calais Regional Council, by FEDER through the Contrat de Projets Etat Region (CPER), by ARCIR Project ESTIREZ Nord-Pas de Calais Regional Council. F.J. Bejarnano acknowledges as well the support of Proyecto SIP 20161492, Mexico., Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: commensurate delays, 0209 industrial biotechnology, Class (set theory), Time delays, Observer (quantum physics), Existential quantification, observer, 02 engineering and technology, State (functional analysis), Delayed singular systems, 020901 industrial engineering & automation, Control and Systems Engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, State observer, Electrical and Electronic Engineering, Mathematics
Abstract: International audience; This paper investigates the problem of observer design for a general class of linear singular time-delay systems, in which the time delays are involved in the state and its derivatives, the output and the known input (if there exists). The involvement of the delay could be multiple which however is rarely studied in the literature. Sufficient conditions are proposed which guarantees the existence of a Luenberger-like observer for the general system.
Published: 2017

28. Bootstrapping Q-Learning for Robotics from Neuro-Evolution Results

Author: Matthieu Zimmer, Stéphane Doncieux, Architectures et modèles d'Adptation et de la cognition (AMAC), Institut des Systèmes Intelligents et de Robotique (ISIR), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), This work has been supported by the FET project DREAM, that has received funding from the European Unions Horizon 2020 research and innovation programme under grant agreement No 640891. The authors would like to thank Olivier Sigaud for his comments on a first draft of the article. The data has been numerically analysed with the free software package GNU Octave and scikit-learn. Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by INRIA and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr)., and GRID5000
Subjects: Computer Science::Machine Learning, 0209 industrial biotechnology, Learning classifier system, business.industry, Computer science, Evolutionary robotics, Q-learning, Online machine learning, Multi-task learning, generation of representation during development, 02 engineering and technology, transfer learning, Robot learning, robots with development and learning skills, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 020901 industrial engineering & automation, Artificial Intelligence, 0202 electrical engineering, electronic engineering, information engineering, Reinforcement learning, 020201 artificial intelligence & image processing, Instance-based learning, Artificial intelligence, business, Software
Abstract: International audience; Reinforcement learning problems are hard to solve in a robotics context as classical algorithms rely on discrete representations of actions and states, but in robotics both are continuous. A discrete set of actions and states can be defined, but it requires an expertise that may not be available, in particular in open environments. It is proposed to define a process to make a robot build its own representation for a reinforcement learning algorithm. The principle is to first use a direct policy search in the sensori-motor space, i.e. with no predefined discrete sets of states nor actions, and then extract from the corresponding learning traces discrete actions and identify the relevant dimensions of the state to estimate the value function. Once this is done, the robot can apply reinforcement learning (1) to be more robust to new domains and, if required, (2) to learn faster than a direct policy search. This approach allows to take the best of both worlds: first learning in a continuous space to avoid the need of a specific representation, but at a price of a long learning process and a poor generalization, and then learning with an adapted representation to be faster and more robust.
Published: 2017

29. Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations

Author: Michèle Sebag, Cédric Gouy-Pailler, Yoann Isaac, Quentin Barthélemy, Jamal Atif, Laboratoire d'analyse des données et d'intelligence des systèmes (LADIS), Département Métrologie Instrumentation & Information (DM2I), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, TAckling the Underspecified (TAU), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Mensia Technologies [Rennes], Mensia Technologies [Paris], Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), The work presented in this paper has been partially funded by DIGITEO under the Grant 2011-053D, Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Signal processing, Optimization problem, Noise reduction, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, 02 engineering and technology, Machine Learning (cs.LG), [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Recovery, Computer Science - Data Structures and Algorithms, Prior probability, Regularization, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Electrical and Electronic Engineering, Selection, Image restoration, Mathematics, business.industry, Linear Inverse Problems, 020206 networking & telecommunications, Pattern recognition, Sparse approximation, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Regression, Minimization, Computer Science - Learning, Image-Restoration, Control and Systems Engineering, Statistical analysis, 020201 artificial intelligence & image processing, [SDV.NEU]Life Sciences [q-bio]/Neurons and Cognition [q-bio.NC], Computer Vision and Pattern Recognition, Decomposition method (constraint satisfaction), Artificial intelligence, Minification, Lasso, business, Software, Algorithms, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: This paper addresses the structurally constrained sparse decomposition of multi-dimensional signals onto overcomplete families of vectors, called dictionaries. The contribution of the paper is threefold. Firstly, a generic spatio-temporal regularization term is designed and used together with the standard ź 1 regularization term to enforce a sparse decomposition preserving the spatio-temporal structure of the signal. Secondly, an optimization algorithm based on the split Bregman approach is proposed to handle the associated optimization problem, and its convergence is analyzed. Our well-founded approach yields same accuracy as the other algorithms at the state of the art, with significant gains in terms of convergence speed. Thirdly, the empirical validation of the approach on artificial and real-world problems demonstrates the generality and effectiveness of the method. On artificial problems, the proposed regularization subsumes the Total Variation minimization and recovers the expected decomposition. On the real-world problem of electro-encephalography brainwave decomposition, the approach outperforms similar approaches in terms of P300 evoked potentials detection, using structured spatial priors to guide the decomposition. HighlightsA sparse structured decomposition method is proposed for multi-dimensional signals.Knowledge priors are encoded in a regularization to obtain plausible representations.The proposed split-Bregman based method outperforms counterparts in terms of speed.The approach is applied to EEG denoising for the extraction of P300 potentials.
Published: 2017

30. Blind estimation of blur in hyperspectral images

Author: Benoit Vozel, Kacem Chehdi, Vladimir V. Lukin, Mykhail Uss, Mo Zhang, Sergey K. Abramov, Institut d'Électronique et des Technologies du numéRique (IETR), Nantes Université (NU)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Kharkov National University, This work has been co-funded by the Brittany Region and the Côtes d'Armor Department. The authors would like to thank all the authors of the semi-blind methods comparatively assessed in this paper for making their code publicly available., Université de Nantes (UN)-Université de Rennes 1 (UR1), Université de Nantes (UN)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: Point spread function, Computer science, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Sparse distribution, 02 engineering and technology, Regularization (mathematics), Augmented lagrangian, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Signal-to-noise ratio, 0202 electrical engineering, electronic engineering, information engineering, Alternating direction method of multipliers (admm), Regularization parameter, Image restoration, Total variation, business.industry, Cumulative distribution function, Hyperspectral imaging, 020206 networking & telecommunications, Pattern recognition, Thresholding, [SPI.TRON]Engineering Sciences [physics]/Electronics, Kernel estimation, 020201 artificial intelligence & image processing, Noise (video), Artificial intelligence, business, Salient edges, Blind image restoration, Remote sensing images
Abstract: International audience; Hyperspectral images acquired by remote sensing systems are generally degraded by noise and can be sometimes more severely degraded by blur. When no knowledge is available about the degradations present on the original image, blind restoration methods can only be considered. By blind, we mean absolutely no knowledge neither of the blur point spread function (PSF) nor the original latent channel and the noise level. In this study, we address the blind restoration of the degraded channels component-wise, according to a sequential scheme. For each degraded channel, the sequential scheme estimates the blur point spread function (PSF) in a first stage and deconvolves the degraded channel in a second and final stage by means of using the PSF previously estimated. We propose a new component-wise blind method for estimating effectively and accurately the blur point spread function. This method follows recent approaches suggesting the detection, selection and use of sufficiently salient edges in the current processed channel for supporting the regularized blur PSF estimation. Several modifications are beneficially introduced in our work. A new selection of salient edges through thresholding adequately the cumulative distribution of their corresponding gradient magnitudes is introduced. Besides, quasi-Automatic and spatially adaptive tuning of the involved regularization parameters is considered. To prove applicability and higher efficiency of the proposed method, we compare it against the method it originates from and four representative edge-sparsifying regularized methods of the literature already assessed in a previous work. Our attention is mainly paid to the objective analysis (via l1- norm) of the blur PSF error estimation accuracy. The tests are performed on a synthetic hyperspectral image. This synthetic hyperspectral image has been built from various samples from classified areas of a real-life hyperspectral image, in order to benefit from realistic spatial distribution of reference spectral signatures to recover after synthetic degradation. The synthetic hyperspectral image has been successively degraded with eight real blurs taken from the literature, each of a different support size. Conclusions, practical recommendations and perspectives are drawn from the results experimentally obtained. © 2017 SPIE.
Published: 2017

31. Derandomizing random walks in undirected graphs using locally fair exploration strategies

Author: Ralf Klasing, Adrian Kosowski, Colin Cooper, David Ilcinkas, Department of Computer Science (DCS), King‘s College London, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mathematical optimization, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Random walk, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Indifference graph, Graph exploration, law, Graph power, Line graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Pancyclic graph, Mathematics, Discrete mathematics, Block graph, graph exploration : Propp machine, Directed graph, Feedback arc set, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Robbins' theorem, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.
Published: 2011

32. Defining and controlling the heterogeneity of a cluster: The Wrekavoc tool

Author: Olivier Dubuisson, Emmanuel Jeannot, Jens Gustedt, Louis-Claude Canon, Algorithms for the Grid (ALGORILLE), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Efficient runtime systems for parallel architectures (RUNTIME), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS), This work was supported by a one year internship grant for the second author by FONGECIF to INRIA Nancy -- Grand~Est. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies see https://www.grid5000.fr., and Grid'5000
Subjects: 020203 distributed computing, Emulation, Interconnection, Computer science, Distributed computing, Principal (computer security), Overlay network, 02 engineering and technology, Heterogeneous systems, Performance modeling, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], Hardware and Architecture, Scalability, 0202 electrical engineering, electronic engineering, information engineering, Cluster (physics), 020201 artificial intelligence & image processing, Tool for experimentation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software, Information Systems
Abstract: International audience; The experimental validation and the testing of solutions that are designed for heterogeneous environments is challenging. We introduce Wrekavoc as an accurate tool for this purpose: it runs unmodified applications on emulated multisite heterogeneous platforms. Its principal technique consists in downgrading the performance of the platform characteristics in a prescribed way. The platform characteristics include the compute nodes themselves (CPU and memory) and the interconnection network for which a controlled overlay network above the homogeneous cluster is built. In this article we describe the tool, its performance, its accuracy and its scalability. Results show that Wrekavoc is a very versatile tool that is useful to perform high-quality experiments (in terms of reproducibility, realism, control, etc.
Published: 2010

33. Fast radio broadcasting with advice

Author: David Ilcinkas, Andrzej Pelc, Dariusz R. Kowalski, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Liverpool], University of Liverpool, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow. Andrzej Pelc was partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais., and Alexander A. Shvartsman, Pascal Felber
Subjects: Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Theoretical Computer Science, Broadcasting (networking), Computer Science::Networking and Internet Architecture, 0202 electrical engineering, electronic engineering, information engineering, Advice, Deterministic broadcasting, Computer Science::Information Theory, Distributed algorithm, business.industry, Radio network, Ask price, 010201 computation theory & mathematics, Order (business), Broadcast communication network, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Constant (mathematics), Radio broadcasting, Algorithm, Advice (complexity), Computer Science(all), Computer network
Abstract: International audience; We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with {\em advice}. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: $O(n)$ bits of advice are sufficient but $o(n)$ bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
Published: 2010

34. Remembering without memory: Tree exploration by asynchronous oblivious robots

Author: Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, Distributed Computing Research Group [Ottawa], University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Partially supported by NSERC Discovery grant. Andrzej Pelc is also partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow., and Alexander A. Shvartsman, Pascal Felber
Subjects: Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Constructive, Theoretical Computer Science, Combinatorics, Computer Science::Robotics, oblivious, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, asynchronous, Discrete mathematics, Degree (graph theory), Swarm behaviour, robot, Mobile robot, Binary logarithm, tree, Asymptotically optimal algorithm, 010201 computation theory & mathematics, Asynchronous communication, Robot, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science(all)
Abstract: International audience; In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is {\sc Asynch} where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of {\em exploration}: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are $n$-node trees where $\Omega(n)$ robots are necessary; this holds even if the maximum degree is $4$. On the other hand, we show that if the maximum degree is $3$, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically {\em optimal}: there are trees of degree $3$, whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.
Published: 2010

35. Analyzing the exhaustiveness of the synapse protocol

Author: Vincenzo Ciancaglini, Zoran Ognjanović, Bojan Marinković, Paola Glavan, Luigi Liquori, Petar Maksimovic, Mathematical Institute of the Serbian Academy of Sciences and Arts, Serbian Academy of Sciences and Arts (SASA), Logical Networks: Self-organizing Overlay Networks and Programmable Overlay Computing Systems (LOGNET), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Zagreb, and The work presented in this paper was supported by the Serbian Ministry of Education, Science and Technological Development, projects ON174026 and III44006, through Matematicki Institut SANU and by Ministarstvo znanosti, obrazovanja i sporta republike Hrvatske.
Subjects: Theoretical computer science, Computer Networks and Communications, Computer science, Distributed computing, Overlay network, 0102 computer and information sciences, 02 engineering and technology, Peer-to-peer, computer.software_genre, 01 natural sciences, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Synapse, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0202 electrical engineering, electronic engineering, information engineering, Abstract State Machines, Protocol (object-oriented programming), Computer communication networks, Retrieval probability, Formal description, Quantitative Biology::Neurons and Cognition, DASM, Peer-to-Peer Protocols, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], DHT-based overlay networks, 010201 computation theory & mathematics, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.2: Network Protocols, Scalability, Abstract state machines, 020201 artificial intelligence & image processing, computer, Software
Abstract: International audience; The Synapse protocol is a scalable protocol designed for information retrieval over inter-connected heterogeneous overlay networks. In this paper, we give a formal description of Synapse using the Abstract State Machines framework. The formal description pertains to Synapse actions that manipulate distributed keys. Based on this formal description, we present results concerning the expected exhaustiveness for a number of scenarios and systems maintained by the Synapse protocol, and provide comparisons to the results of the corresponding simulations and experiments. We show that the predicted theoretical results match the obtained experimental results, and give recommendations on the design of systems using Synapse.
Published: 2015

36. Automatic Distributed Code Generation from Formal Models of Asynchronous Concurrent Processes

Author: Frédéric Lang, Hugues Evrard, Construction of verified concurrent systems (CONVECS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), This work was partly funded by the French Fonds national pour la Société Numérique (FSN), Pôles Minalogic, Systematic and SCS (project OpenCloudware).Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr)., Grid'5000, and Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Programming language, Semantics (computer science), Computer science, Distributed computing, Concurrency, Process (computing), 02 engineering and technology, computer.software_genre, Asynchronous communication, 020204 information systems, Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Code generation, Compiler, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, Formal verification
Abstract: International audience; Formal process languages inheriting the concurrency and communication features of process algebras are convenient formalisms to model distributed applications, especially when they are equipped with formal verification tools (e.g., model-checkers) to help hunting for bugs early in the development process. However, even starting from a fully verified formal model, bugs are likely to be introduced while translating (generally by hand) the concurrent model —which relies on high-level and expressive communication primitives— into the distributed implementation —which often relies on low-level communication primitives. In this paper, we present DLC, a compiler that enables distributed code to be generated from models written in a formal process language called LNT, which is equipped with a rich verification toolbox named CADP. The generated code can be either executed in an autonomous way (i.e., without requiring additional code to be defined by the user), or connected to external software through user-modifiable C functions. We present an experiment where DLC generates a distributed implementation from the LNT model of the Raft consensus algorithm.
Published: 2015

37. Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Networks

Author: Christian Glacet, Nicolas Hanusse, Colette Johnen, David Ilcinkas, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), See paper for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: Routing protocol, Leader election, Theoretical computer science, Computer Networks and Communications, Computer science, 02 engineering and technology, Theoretical Computer Science, Artificial Intelligence, shortest-path, disconnected network, Node (computer science), 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Discrete mathematics, Connected component, routing algorithm, business.industry, Shortest-path tree, 020206 networking & telecommunications, Task (computing), Tree (data structure), self-stabilization, Hardware and Architecture, Asynchronous communication, Shortest path problem, 020201 artificial intelligence & image processing, Enhanced Data Rates for GSM Evolution, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Daemon, business, Software, Computer network
Abstract: Many articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r . In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r . We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous weighted networks with the following additional strong properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2 n + D rounds for a network of n nodes and hop-diameter D .
Published: 2014

38. Exploration of Constantly Connected Dynamic Graphs Based on Cactuses

Author: Ahmed Mouhamadou Wade, David Ilcinkas, Ralf Klasing, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See papers for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: Mobile agent, Block graph, Discrete mathematics, Symmetric graph, Cactus graph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Combinatorics, Connectivity over time, 010201 computation theory & mathematics, law, Random regular graph, Clique-width, Line graph, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Pancyclic graph, Dynamic graphs, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, Distance-hereditary graph
Abstract: International audience; We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of $n$ vertices \cite{IW13}. In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most $2^{O(\sqrt{\log n})} n$ time units. We show that the lower bound of the algorithm is $2^{\Omega(\sqrt{\log n})} n$ time units.
Published: 2014

39. Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring

Author: David Ilcinkas, Ahmed Mouhamadou Wade, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, Ecole polytechnique de Thiès, Ecole Polytechnique de Thiès, ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Exploration problem, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Stability (probability), Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Connection (algebraic framework), Time complexity, Mathematics, Dynamic graphs, Discrete mathematics, Mobile agent, Ring (mathematics), Unit of time, 020206 networking & telecommunications, T-interval-connectivity, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computational Theory and Mathematics, 010201 computation theory & mathematics, Theory of computation, Interval (graph theory), 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Focus (optics)
Abstract: In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and $n+ \frac {n}{\max \{1, T-1\} } (\delta -1) \pm {\Theta }(\delta )$ time units otherwise, where δ is the maximum time between two successive appearances of an edge.
Published: 2013

40. A benchmark of kriging-based infill criteria for noisy optimization

Author: Tobias Wagner, David Ginsbourger, Victor Picheny, Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT INRA), Institut National de la Recherche Agronomique (INRA), Technische Universität Dortmund [Dortmund] (TU), University of Bern, Deutsche Forschungsgemeinschaft (DFG) [SFB/TR TRR 30] Funding Text : The contributions of Tobias Wagner to this paper are based on investigations of the project D5 of the Collaborative Research Center SFB/TR TRR 30, which is kindly supported by the Deutsche Forschungsgemeinschaft (DFG)., and Picheny, Victor
Subjects: Mathematical optimization, Control and Optimization, Covariance function, 0211 other engineering and technologies, 02 engineering and technology, Metamodeling, symbols.namesake, 510 Mathematics, DESIGN, Kriging, Homoscedasticity, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], [MATH]Mathematics [math], Gaussian process, GLOBAL OPTIMIZATION, Mathematics, EGO, 021103 operations research, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Covariance, Computer Graphics and Computer-Aided Design, Computer Science Applications, COMPUTER EXPERIMENTS, Control and Systems Engineering, Gaussian noise, SIMULATION, symbols, 020201 artificial intelligence & image processing, Engineering design process, Noise, Software
Abstract: International audience; Responses of many real-world problems can only be evaluated perturbed by noise. In order to make an efficient optimization of these problems possible, intelligent optimization strategies successfully coping with noisy evaluations are required. In this article, a comprehensive review of existing kriging-based methods for the optimization of noisy functions is provided. In summary, ten methods for choosing the sequential samples are described using a unified formalism. They are compared on analytical benchmark problems, whereby the usual assumption of homoscedastic Gaussian noise made in the underlying models is meet. Different problem configurations (noise level, maximum number of observations, initial number of observations) and setups (covariance functions, budget, initial sample size) are considered. It is found that the choices of the initial sample size and the covariance function are not critical. The choice of the method, however, can result in significant differences in the performance. In particular, the three most intuitive criteria are found as poor alternatives. Although no criterion is found consistently more efficient than the others, two specialized methods appear more robust on average.
Published: 2013

41. Unknown Input Observer with Fuzzy Fault Tolerant Control for Wind Energy System

Author: Mireille Bayart, Elkhatib Kamal, Reza Ghorbani, Abdel Aitouche, Systèmes Tolérants aux Fautes (STF), Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille, Mechnaical Engineering Laboratory, University of Hawai‘i [Mānoa] (UHM), IFAC PAPER ON LINE, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, Engineering, Wind power, Observer (quantum physics), business.industry, reconfigurable control, Induction generator, Stability (learning theory), Control engineering, Fault tolerance, 02 engineering and technology, Fuzzy logic, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Nonlinear system, 020901 industrial engineering & automation, Applications and fault tolerant control, Control theory, Convex optimization, Power plants and power systems, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business
Abstract: International audience; This paper proposes a Fuzzy Dedicated Observers (FDOS) method using a Nonlinear Unknown Input Fuzzy Observer (UIFO) with a Fuzzy Fault Tolerant Control (FFTC) algorithm for fuzzy Takagi-Sugeno (TS) systems subject to sensor faults. FDOS provide residuals for detection and isolation of sensor faults which can affect a TS model. Parallel Distributed Compensation (PDC) is employed to design the fuzzy Fault Tolerant Controller from a TS fuzzy model. Sufficient stabilization conditions of the FFTC systems are given, which are formulated in terms of Linear Matrix Inequalities (LMIs). The LMIs can be efficiently solved using convex optimization techniques. Based on the derivation and simulation of the proposed FFTC approach, the stability of the closed-loop system in the event of sensor failures and unknown inputs is guaranteed. A wind Energy System (WES) with a Doubly-Fed Induction Generator (DFIG) example is illustrated to show the effectiveness of the proposed design method.
Published: 2012

42. Dislocation detection in field environments: A belief functions contribution

Author: Carl T. Haas, Saiedeh Razavi, Emmanuel Duflos, Philippe Vanheeghe, Department of Civil and Environmental Engineering [Waterloo], University of Waterloo [Waterloo], Sequential Learning (SEQUEL), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), LAGIS-SI, Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), The research work was sponsored by a CNRS International Scientific Collaboration Program (PICS)., This paper results from the collaboration between the Laboratoire d'Automatique Génie Informatique et Signal (UMR CNRS 8219, Lille, France) and the Department of Civil and Environmental Engineering of the University of Waterloo (Canada)., Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), and Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: GPS, 0211 other engineering and technologies, Construction materials, 02 engineering and technology, Machine learning, computer.software_genre, Field (computer science), Dislocation detection, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Artificial Intelligence, Position (vector), 021105 building & construction, 0202 electrical engineering, electronic engineering, information engineering, Radio-frequency identification, Mathematics, RFID, business.industry, Frame (networking), General Engineering, Function (mathematics), belief functions, Sensors network, Computer Science Applications, Discrete time and continuous time, Global Positioning System, 020201 artificial intelligence & image processing, Artificial intelligence, business, Focus (optics), Algorithm, computer, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract: Highlights? The greedy acceptance criterion for the glowworms updating positions is proposed. ? The new formulas for the glowworms movement are proposed. ? Uniform design experiments were investigated the effect of parameters. ? The proposed improvement algorithms were effective than the classical algorithm. Dislocation is defined as the change between discrete sequential locations of critical items in field environments such as large construction projects. Dislocations on large sites of materials and critical items for which discrete time position estimates are available represent critical state changes. The ability to detect dislocations automatically for tens of thousands of items can ultimately improve project performance significantly. Detecting these dislocations in a noisy information environment where low cost radio frequency identification tags are attached to each piece of material, and the material is moved sometimes only a few meters, is the main focus of this study. We propose in this paper a method developed in the frame of belief functions to detect dislocations. The belief function framework is well-suited for such a problem where both uncertainty and imprecision are inherent to the problem. We also show how to deal with the calculations. This method has been implemented in a controlled experimental setting. The results of these experiments show the ability of the proposed method to detect materials dislocation over the site reliably. Broader application of this approach to both animate and inanimate objects is possible.
Published: 2012

43. Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles

Author: Paola Flocchini, David Ilcinkas, Nicola Santoro, School of Electrical Engineering and Computer Science (EECS), University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Ottawa], Carleton University, See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Theoretical computer science, General Computer Science, FIFO (computing and electronics), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Topology (electrical circuits), 0102 computer and information sciences, 02 engineering and technology, Dangerous graphs, Topology, 01 natural sciences, Graph exploration, Autonomous robots, 0202 electrical engineering, electronic engineering, information engineering, Search problem, Pebble, Mathematics, Applied Mathematics, Black hole search, Distributed computing, Computer Science Applications, 010201 computation theory & mathematics, Asynchronous communication, Theory of computation, 020201 artificial intelligence & image processing, Node (circuits), Mobile agents, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node), can locate the black hole in an arbitrary network of known topology; this can be done with Θ(nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles.
Published: 2012

44. Cost Reduction Through SLA-driven Self-Management

Author: Jean-Louis Pazat, Nikos Parlavantzas, André Lage Freitas, Design and Implementation of Autonomous Distributed Systems (MYRIADS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), The research leading to these results has received funding from the European Community's Seventh Framework Programme [FP7/2007-2013] under grant greement 215483 (S-CUBE). Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr)., European Project: 215483,EC:FP7:ICT,FP7-ICT-2007-1,S-CUBE(2008), Inria, GRID'5000, CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer science, computer.internet_protocol, Distributed computing, QoS, Cloud computing, 02 engineering and technology, computer.software_genre, grid, self-sadptation, Profit (economics), 020204 information systems, self-adaptation, 0202 electrical engineering, electronic engineering, information engineering, cloud, service-oriented computing, business.industry, Quality of service, Service-oriented architecture, Service provider, Grid, Cost reduction, web services, Risk analysis (engineering), 020201 artificial intelligence & image processing, Web service, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, computer
Abstract: International audience; A main challenge for service providers is managing service-level agreements (SLAs) with their customers while satisfying their business objectives, such as maximizing profits. Most current systems fail to consider business objectives and thus to provide a complete SLA management solution. This work proposes an SLA-driven management solution that aims to maximize the provider's profit by reducing resource costs as well as fines owning to SLA violations. Specifically, this work proposes a framework that comprises multiple, configurable control loops and supports automatically adjusting service configurations and resource usage in order to maintain SLAs in the most cost-effective way. The framework targets services implemented on top of large-scale distributed infrastructures, such as clouds. Experimental results demonstrate its effectiveness in maintaining SLAs while reducing provider costs.
Published: 2011

45. On the Power of Waiting When Exploring Public Transportation Systems

Author: Ahmed Mouhamadou Wade, David Ilcinkas, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Mobile agent, Discrete mathematics, PV-graph, Class (set theory), Computer science, business.industry, Distributed computing, Multiplicative function, Context (language use), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Power (physics), Set (abstract data type), 010201 computation theory & mathematics, Public transport, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Time complexity, Dynamic graphs
Abstract: International audience; We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro (ISAAC 2009) studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal number of steps (and thus of moves) to explore a n-node PV-graph of k carriers and maximal period p is in Theta(k p^2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least Theta(p), while the time complexity is reduced to Theta(n p). (In any connected PV-graph, we have n < k p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.
Published: 2011

46. Communication algorithms with advice

Author: Pierre Fraigniaud, Andrzej Pelc, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Computer Networks and Communications, Distributed computing, Message complexity, Network, 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Graph, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Size of advice, Dissemination, Mathematics, Linear number, business.industry, Applied Mathematics, Telecommunications network, Algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Broadcast communication network, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Advice (complexity), Wakeup
Abstract: International audience; We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.
Published: 2010

47. Label-Guided Graph Exploration by a Finite Automaton

Author: David Ilcinkas, David Peleg, Amos Korman, Pierre Fraigniaud, Reuven Cohen, Department of Electrical and Computer Engineering [Boston University] (ECE), Boston University [Boston] (BU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Reuven Cohen was supported by the Pacific Theaters Foundation. Pierre Fraigniaud and David Ilcinkas were supported by the project ``PairAPair' of the ACI Masses de Données, the project ``Fragile' of the ACI Sécurité et Informatique, and by the project ``Grand Large' of INRIA., L. Caires, G. Italiano, L. Monteiro, C. Palamidessi, M. Yung, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Theoretical computer science, Graph labeling, Computer science, Labeling schemes, Symmetric graph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Simplex graph, law.invention, Computer Science::Robotics, Mathematics (miscellaneous), Graph exploration, Graph power, law, Clique-width, Line graph, String graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Lattice graph, Time complexity, Complement graph, Mathematics, Forbidden graph characterization, Discrete mathematics, Degree (graph theory), Visibility graph, Voltage graph, Quartic graph, Graph theory, Butterfly graph, Graph, Finite graph, Vertex-transitive graph, Graph bandwidth, 010201 computation theory & mathematics, Bounded function, Cubic graph, Distributed algorithms, 020201 artificial intelligence & image processing, Regular graph, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, ACM C.2.1, ACM C.2.2, ACM C.2.4, ACM E.1
Abstract: A finite automaton, simply referred to as a robot , has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k -state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph G , so that R can explore the colored graph G . Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).
Published: 2008

48. Distributed Computing with Advice: Information Sensitivity of Graph Coloring

Author: Andrzej Pelc, Cyril Gavoille, Pierre Fraigniaud, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais., Lars Arge, Christian Cachin, Tomasz Jurdzinski, Andrzej Tarlecki, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Network algorithms, Theoretical computer science, Computer Networks and Communications, Computer science, Distributed computing, Computation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, network algorithm, 01 natural sciences, Oracle, Theoretical Computer Science, Distributed coloring, Greedy coloring, distributed computing, graph coloring, 0202 electrical engineering, electronic engineering, information engineering, Graph coloring, Advice, Computer communication networks, Information sensitivity, Computational Theory and Mathematics, Hardware and Architecture, 010201 computation theory & mathematics, Theory of computation, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.
Published: 2007

49. The Reduced Automata Technique for Graph Exploration Space Lower Bounds

Author: Sergio Rajsbaum, David Ilcinkas, Pierre Fraigniaud, Sébastien Tixeuil, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), See paper for details., Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Finite-state machine, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph theory, robot, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Graph, Directed cycle, Automaton, finite automaton, Combinatorics, Computer Science::Robotics, Graph exploration, 010201 computation theory & mathematics, Search algorithm, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots, modeled as finite automata. For exploration to be completed, each edge of the graph has to be traversed by at least one robot. In this paper, the robots have no a priori knowledge of the topology of the graph, nor of its size, and we are interested in the amount of memory the robots need to accomplish exploration, We introduce the so-called {\em reduced automata technique}, and we show how to use this technique for deriving several space lower bounds for exploration. Informally speaking, the reduced automata technique consists in reducing a robot to a simpler form that preserves its “core” behavior on some graphs. Using this technique, we first show that any set of $q\geq 1$ non-cooperative robots, requires $\Omega(\log(\frac{n}{q}))$ memory bits to explore all $n$-node graphs. The proof implies that, for any set of $q K$-state robots, there exists a graph of size $O(qK)$ that no robot of this set can explore, which improves the $O(K^{O(q)})$ bound by Rollik (1980). Our main result is an application of this latter result, concerning {\em terminating} graph exploration with one robot, i.e., in which the robot is requested to stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes (without such a marker, even terminating exploration of cycles cannot be achieved). We prove that terminating exploration requires $\Omega(\log n)$ bits of memory for a robot achieving this task in all $n$-node graphs.
Published: 2006

50. Alzette: A 64-Bit ARX-box: (feat. CRAX and TRAX)

Author: Luan Cardoso dos Santos, Qingju Wang, Aleksei Udovenko, Christof Beierle, Alex Biryukov, Johann Großschädl, Vesselin Velichkov, Léo Perrin, Ruhr-Universität Bochum [Bochum], University of Luxembourg [Luxembourg], Cryptologie symétrique, cryptologie fondée sur les codes et information quantique (COSMIQ), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), CryptoExperts, University of Edinburgh, Part of the work of Christof Beierle was funded by Deutsche Forschungsgemeinschaft (DFG), project number 411879806, and part of the work of Christof Beierle was performed while he was at the University of Luxembourg and funded by the SnT CryptoLux RG budget. Luan Cardoso dos Santos is supported by the Luxembourg National Research Fund through grant PRIDE15/10621687/SPsquared. Part of the work of Aleksei Udovenko was performed while he was at the University of Luxembourg and funded by the Fonds National de la Recherche Luxembourg (project reference 9037104).Part of the work by Vesselin Velichkov was performed while he was at the University of Luxembourg. The work of Qingju Wang is funded by the University of Luxembourg Internal Research Project (IRP) FDISC. The experiments presented in this paper were carried out using the HPC facilities of the University of Luxembourg, Micciancio, Daniele, Ristenpart, Thomas, Deutsche Forschungsgemeinschaft (DFG) [sponsor], Fonds National de la Recherche - FnR [sponsor], and University of Luxembourg - UL [sponsor]
Subjects: Differential cryptanalysis, Computer science, MEDCo, Context (language use), Cryptography, 02 engineering and technology, Crax, Space (mathematics), Related-tweak setting, (tweakable) block cipher, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, Arithmetic, Computer science [C05] [Engineering, computing & technology], MELCC, biology, (Tweakable) block cipher, business.industry, biology.organism_classification, Sciences informatiques [C05] [Ingénierie, informatique & technologie], 020202 computer hardware & architecture, Bit (horse), Long trailstrategy, Symmetric-key algorithm, Linear cryptanalysis, Long trail strategy, 020201 artificial intelligence & image processing, MEDCP, business, Alzette
Abstract: S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ones (e.g., 32 bits). In this context, an S-box is then defined as a subfunction whose cryptographic properties can be estimated precisely.We present a 64-bit ARX-based S-box called Alzette, which can be evaluated in constant time using only 12 instructions on modern CPUs. Its parallel application can also leverage vector (SIMD) instructions. One iteration of Alzette has differential and linear properties comparable to those of the AES S-box, and two are at least as secure as the AES super S-box. As the state size is much larger than the typical 4 or 8 bits, the study of the relevant cryptographic properties of Alzette is not trivial. We further discuss how such wide S-boxes could be used to construct round functions of 64-, 128- and 256-bit (tweakable) block ciphers with good cryptographic properties that are guaranteed even in the related-tweak setting. We use these structures to design a very lightweight 64-bit block cipher (Crax) which outperforms SPECK-64/128 for short messages on micro-controllers, and a 256-bit tweakable block cipher (Trax) which can be used to obtain strong security guarantees against powerful adversaries (nonce misuse, quantum attacks).

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

50 results

Search Results

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources