Search

Showing total 9 results
Start Over Topic fos: computer and information sciences Language undetermined
9 results

1. SGX Switchless Calls Made Configless

Author

Yuhala, Peterson, Paper, Michael, Zerbib, Timothée, Felber, Pascal, Schiavoni, Valerio, and Tchana, Alain

Subjects
FOS: Computer and information sciences, Computer Science - Cryptography and Security, Cryptography and Security (cs.CR)
Abstract

Intel's software guard extensions (SGX) provide hardware enclaves to guarantee confidentiality and integrity for sensitive code and data. However, systems leveraging such security mechanisms must often pay high performance overheads. A major source of this overhead is SGX enclave transitions which induce expensive cross-enclave context switches. The Intel SGX SDK mitigates this with a switchless call mechanism for transitionless cross-enclave calls using worker threads. Intel's SGX switchless call implementation improves performance but provides limited flexibility: developers need to statically fix the system configuration at build time, which is error-prone and misconfigurations lead to performance degradations and waste of CPU resources. ZC-SWITCHLESS is a configless and efficient technique to drive the execution of SGX switchless calls. Its dynamic approach optimises the total switchless worker threads at runtime to minimise CPU waste. The experimental evaluation shows that ZC-SWITCHLESS obviates the performance penalty of misconfigured switchless systems while minimising CPU waste., Comment: 10 pages, 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

Published
2023
Full Text
View/download PDF

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. Learning Intermediate Representations using Graph Neural Networks for NUMA and Prefetchers Optimization

Author

TehraniJamsaz, Ali, Popov, Mihail, Dutta, Akash, Saillard, Emmanuelle, Jannesari, Ali, Iowa State University (ISU), STatic Optimizations, Runtime Methods (STORM), 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)-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, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), We would like to thank the Research IT team of Iowa State University for their continuous support in providing access to HPC clusters for conducting the experiments of this research project. Experiments presented in this paper were carried out using the experimental testbeds PlaFRIM, supported by Inria, CNRS (LABRI and IMB), Universite de Bordeaux, Bordeaux INP, Conseil Regional d’Aquitaine, and Grid’5000, supported by a scientific interest group hosted by Inria, CNRS, RENATER and several Universities as well as other organizations., and Grid'5000

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Artificial Intelligence (cs.AI), NUMA, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Artificial Intelligence, graph neural networks, OpenMP, LLVM Intermediate Representation, [INFO]Computer Science [cs], Distributed, Parallel, and Cluster Computing (cs.DC), prefetching, Machine Learning (cs.LG)
Abstract

International audience; There is a large space of NUMA and hardware prefetcher configurations that can significantly impact the performance of an application. Previous studies have demonstrated how a model can automatically select configurations based on the dynamic properties of the code to achieve speedups. This paper demonstrates how the static Intermediate Representation (IR) of the code can guide NUMA/prefetcher optimizations without the prohibitive cost of performance profiling. We propose a method to create a comprehensive dataset that includes a diverse set of intermediate representations along with optimum configurations. We then apply a graph neural network model in order to validate this dataset. We show that our static intermediate representation based model achieves 80% of the performance gains provided by expensive dynamic performance profiling based strategies. We further develop a hybrid model that uses both static and dynamic information. Our hybrid model achieves the same gains as the dynamic models but at a reduced cost by only profiling 30% of the programs.

Published
2022

4. Bayesian Decision Theory and Stochastic Independence

Author

Philippe Mongin, HEC Paris - Recherche - Hors Laboratoire, Ecole des Hautes Etudes Commerciales (HEC Paris), HEC Research Paper Series, and Haldemann, Antoine

Subjects
FOS: Computer and information sciences, Stochastic independence, History, Property (philosophy), Computer science, Savage, 050905 science studies, lcsh:QA75.5-76.95, History and Philosophy of Science, Probability theory, Computer Science - Computer Science and Game Theory, Representation (mathematics), Probability interpretations, Preference (economics), Probability measure, Bayes estimator, lcsh:Mathematics, 05 social sciences, Probabilistic Independence, JEL: D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D81 - Criteria for Decision-Making under Risk and Uncertainty, Stochastic Independence, Subjective expected utility, lcsh:QA1-939, Philosophy, Work (electrical), Mathematical development, J2, [SHS.GESTION]Humanities and Social Sciences/Business administration, lcsh:Electronic computers. Computer science, Bayesian Decision Theory, 0509 other social sciences, [SHS.GESTION] Humanities and Social Sciences/Business administration, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling, Mathematical economics, JEL: D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D89 - Other, Computer Science and Game Theory (cs.GT)
Abstract

Stochastic independence has a complex status in probability theory. It is not part of the definition of a probability measure, but it is nonetheless an essential property for the mathematical development of this theory. Bayesian decision theorists such as Savage can be criticized for being silent about stochastic independence. From their current preference axioms, they can derive no more than the definitional properties of a probability measure. In a new framework of twofold uncertainty, we introduce preference axioms that entail not only these definitional properties, but also the stochastic independence of the two sources of uncertainty. This goes some way towards filling a curious lacuna in Bayesian decision theory., Comment: In Proceedings TARK 2017, arXiv:1707.08250

Published
2020

5. A proof of the Brill-Noether method from scratch

Author

Berardini, Elena, Couvreur, Alain, Lecerf, Grégoire, Berardini, Elena, Algèbre, preuves, protocoles, algorithmes, courbes, et surfaces pour les codes et leurs applications - - BARRACUDA2021 - ANR-21-CE39-0009 - AAPG2021 - VALID, Department of Mathematics and Computer Science [Eindhoven], Eindhoven University of Technology [Eindhoven] (TU/e), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-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), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), This paper is part of a project that has received funding from the French 'Agence de l'innovation de défense'. Elena Berardini has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987. Alain Couvreur is funded by the ANR Grant ANR-21-CE39-0009-BARRACUDA., and ANR-21-CE39-0009,BARRACUDA,Algèbre, preuves, protocoles, algorithmes, courbes, et surfaces pour les codes et leurs applications(2021)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, FOS: Computer and information sciences, Algebraic curves, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [MATH.MATH-AG] Mathematics [math]/Algebraic Geometry [math.AG], Newton polygons, Symbolic Computation (cs.SC), Brill–Noether method, Mathematics - Algebraic Geometry, Riemann–Roch spaces, FOS: Mathematics, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Hensel lemmas, Algebraic Geometry (math.AG)
Abstract

In 1874 Brill and Noether designed a seminal geometric method for computing bases of Riemann-Roch spaces. From then, their method has led to several algorithms, some of them being implemented in computer algebra systems. The usual proofs often rely on abstract concepts of algebraic geometry and commutative algebra. In this paper we present a short self-contained and elementary proof that mostly needs Newton polygons, Hensel lifting, bivariate resultants, and Chinese remaindering.

Published
2022
Full Text
View/download PDF

6. A benchmark of state-of-the-art sound event detection systems evaluated on synthetic soundscapes

Author

Ronchini, Francesca, Serizel, Romain, 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), Departement of Electrical Engineering-SCD [Leuven] (ESAT-SCD), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), 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)., ANR-18-CE23-0020,LEAUDS,Apprentissage statistique pour la compréhension de scènes audio(2018), and European Project: 826276,CPS4EU(2019)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Sound (cs.SD), open-source datasets, deep learning, Computer Science - Sound, Machine Learning (cs.LG), Sound event detection, [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], FOS: Electrical engineering, electronic engineering, information engineering, Electrical Engineering and Systems Science - Audio and Speech Processing, synthetic soundscapes
Abstract

International audience; This paper proposes a benchmark of submissions to Detection and Classification Acoustic Scene and Events 2021 Challenge (DCASE) Task 4 representing a sampling of the state-of-the-art in Sound Event Detection task. The submissions are evaluated according to the two polyphonic sound detection score scenarios proposed for the DCASE 2021 Challenge Task 4, which allow to make an analysis on whether submissions are designed to perform fine-grained temporal segmentation, coarse-grained temporal segmentation, or have been designed to be polyvalent on the scenarios proposed. We study the solutions proposed by participants to analyze their robustness to varying level target to non-target signal-to-noise ratio and to temporal localization of target sound events. A last experiment is proposed in order to study the impact of non-target events on systems outputs. Results show that systems adapted to provide coarse segmentation outputs are more robust to different target to non-target signal-to-noise ratio and, with the help of specific data augmentation methods, they are more robust to time localization of the original event. Results of the last experiment display that systems tend to spuriously predict short events when non-target events are present. This is particularly true for systems that are tailored to have a fine segmentation.

Published
2022
Full Text
View/download PDF

7. Natural Scales in Geographical Patterns

Author

Telmo Menezes, Camille Roth, Centre Marc Bloch (CMB), Ministère de l'Europe et des Affaires étrangères (MEAE)-Bundesministerium für Bildung und Forschung-Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.)-Centre National de la Recherche Scientifique (CNRS), Médialab (Sciences Po) (Médialab), Sciences Po (Sciences Po), Centre National de la Recherche Scientifique (CNRS), This paper has been partially supported by grants 'Phantomgrenzen' and 'Algodiv' (ANR-15-CE38-0001), funded respectively by the BMBF (German Federal Ministry for Education and Research) and by the ANR (French National Agency of Research)., and ANR-15-CE38-0001,ALGODIV,Algodiv: Recommandation algorithmique et diversité des informations du web(2015)

Subjects
FOS: Computer and information sciences, 0301 basic medicine, Physics - Physics and Society, FOS: Physical sciences, Distribution (economics), computer science, Network science, Physics and Society (physics.soc-ph), Space (commercial competition), human movement, Article, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Natural (archaeology), geographical networks, 03 medical and health sciences, network science, community detection, applied mathematics, 91D20, 91D30, Social and Information Networks (cs.SI), [SHS.STAT]Humanities and Social Sciences/Methods and statistics, Multidisciplinary, business.industry, Orders of magnitude (acceleration), Computer Science - Social and Information Networks, [SHS.GEO]Humanities and Social Sciences/Geography, Partition (database), Discontinuity (linguistics), 030104 developmental biology, Geography, business, Scale (map), Cartography
Abstract

Human mobility is known to be distributed across several orders of magnitude of physical distances, which makes it generally difficult to endogenously find or define typical and meaningful scales. Relevant analyses, from movements to geographical partitions, seem to be relative to some ad-hoc scale, or no scale at all. Relying on geotagged data collected from photo-sharing social media, we apply community detection to movement networks constrained by increasing percentiles of the distance distribution. Using a simple parameter-free discontinuity detection algorithm, we discover clear phase transitions in the community partition space. The detection of these phases constitutes the first objective method of characterising endogenous, natural scales of human movement. Our study covers nine regions, ranging from cities to countries of various sizes and a transnational area. For all regions, the number of natural scales is remarkably low (2 or 3). Further, our results hint at scale-related behaviours rather than scale-related users. The partitions of the natural scales allow us to draw discrete multi-scale geographical boundaries, potentially capable of providing key insights in fields such as epidemiology or cultural contagion where the introduction of spatial boundaries is pivotal.

Published
2017

8. Towards a Minimal Stabilizer ZX-calculus

Author

Backens, Miriam, Perdrix, Simon, Wang, Quanlong, School of Computer Science [Birmingham], University of Birmingham [Birmingham], Designing the Future of Computational Models (MOCQUA), 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 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)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Oxford], University of Oxford, The authors would like to thank Bob Coecke, Ross Duncan, Emmanuel Jeandel, Aleks Kissinger, Kang Feng Ng and Renaud Vilmart for valuable discussions. We also thank the anonymous reviewers for their comments. QW acknowledges funding from Région Lorraine, EPSRC IAA in collaboration with Cambridge Quantum Computing Ltd., and AFOSR grant FA2386-18-1-4028. MB has received funding from EPSRC via grant EP/L021005/1 and from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) ERC grant agreement no. 334828. The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. No new data were created during this study. SP acknowledges support from the projects ANR-17-CE25-0009 SoftQPro, ANR-17-CE24-0035 VanQuTe, PIA-GDN/Quantex, and LUE / UOQ., ANR-17-CE25-0009,SoftQPRO,Solutions logicielles pour l'optimisation des programmes et ressources quantiques(2017), ANR-17-CE24-0035,VanQuTe,Validation des technologies quantiques émergentes(2017), and University of Oxford [Oxford]

Subjects
FOS: Computer and information sciences, Quantum Physics, Computer Science - Logic in Computer Science, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], F.3.2, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], FOS: Physical sciences, F.1.1, Quantum Physics (quant-ph), [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Logic in Computer Science (cs.LO)
Abstract

13+15 pages; International audience; The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics. The language is sound and complete: one can transform a stabilizer ZX-diagram into another one using the graphical rewrite rules if and only if these two diagrams represent the same quantum evolution or quantum state. We previously showed that the stabilizer ZX-calculus can be simplified by reducing the number of rewrite rules, without losing the property of completeness [Backens, Perdrix & Wang, EPTCS 236:1--20, 2017]. Here, we show that most of the remaining rules of the language are indeed necessary. We do however leave as an open question the necessity of two rules. These include, surprisingly, the bialgebra rule, which is an axiomatisation of complementarity, the cornerstone of the ZX-calculus. Furthermore, we show that a weaker ambient category -- a braided autonomous category instead of the usual compact closed category -- is sufficient to recover the meta rule 'only connectivity matters', even without assuming any symmetries of the generators.

Published
2017
Full Text
View/download PDF

9. Optimal Exploration of Terrains with Obstacles

Author

Andrzej Pelc, Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), 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), 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
FOS: Computer and information sciences, Convex hull, 0209 industrial biotechnology, Matching (graph theory), Computer science, Terrain, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Geometry, exploration, mobile robot, 01 natural sciences, Computer Science::Robotics, 020901 industrial engineering & automation, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Point (geometry), obstacle, Discrete mathematics, Mobile robot, polygon, Computer Science::Graphics, 010201 computation theory & mathematics, Polygon, Trajectory, Robot, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity $O(P+D\sqrt{k})$, where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity $O(P+A+\sqrt{Ak})$, where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain ${\mathcal T}$ with obstacles is c-fat if R/r ≤ c, where R is the radius of the smallest disc containing ${\mathcal T}$ and r is the radius of the largest disc contained in ${\mathcal T}$.) We also prove a matching lower bound $\Omega(P+A+\sqrt{Ak})$ on the complexity of exploration for limited vision, even if the terrain is known to the robot.

Published
2010