Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
INM-Explain -Expliquer les controverses médicales : Application au cas des interventions non médicamenteuses
No full textNational audienceMedical controversies, present on social media, bringing to the fore heated debates, differences of opinion, contradictory interpretations of scientific evidences, etc. Some medical controversies are ethical issues with direct implications for public health. In this article, we describe the INMExplain tool for exploring and quantifying these controversies, and apply it to the case of non-drug interventions.Les controverses médicales, très présentes dans les médias sociaux, mettent en avant des débats animés, des divergences d'opinions, des interprétations contradictoires de preuves scientifiques, etc. Véritable enjeu éthique, certaines controverses médicales ont des implications directes sur la santé publique. Dans cet article, nous décrivons l'outil INM-Explain qui permet d'explorer et de quantifier ces controverses et nous l'appliquons au cas des interventions non médicamenteuses
IntelliMove: Enhancing Robotic Planning with Semantic Mapping
No full texthttps://link.springer.com/chapter/10.1007/978-3-031-72059-8_7International audienceSemantic navigation enables robots to understand their environments beyond basic geometry, allowing them to reason about objects, their functions, and their interrelationships. In semantic robotic navigation, creating accurate and semantically enriched maps is fundamental. Planning based on semantic maps not only enhances the robot's planning efficiency and computational speed but also makes the planning more meaningful, supporting a broader range of semantic tasks. In this paper, we introduce two core modules of IntelliMove: IntelliMap, a generic hierarchical semantic topometric map framework developed through an analysis of current technologies strengths and weaknesses, and Semantic Planning, which utilizes the semantic maps from IntelliMap. We showcase use cases that highlight IntelliMove's adaptability and effectiveness. Through experiments in simulated environments, we further demonstrate IntelliMove's capability in semantic navigation
Compound Logics for Modification Problems
No full textInternational audienceWe introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSO) and have models of bounded treewidth, while target sentences express first-order logic (FO) properties. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Our main result is that, for this compound logic, model-checking can be done in quadratic time on minor-free graphs. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle's theorem and Gaifman's theorem. Our algorithmic meta-theorem encompasses, unifies, and extends the known meta-algorithmic results for CMSO and FO on minor-closed graph classes
Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
No full textInternational audienceThe degree-constrained Steiner problem in graphs is well known in the literature. In an undirected graph, positive integer degree bounds are associated with nodes and positive costs with the edges. The goal is to find the minimum cost tree spanning a given node set while respecting the degree bounds. As it is known, finding a tree satisfying the constraints is not always possible. The problem differs when the nodes can participate multiple times in the coverage and the constraints represent a limited degree (a capacity) for each occurrence of the nodes. The optimum corresponds to a graph-related structure, i.e., to a hierarchy. Finding the solution to this particular Steiner problem is NP-hard. We investigate the conditions of its existence and its exact computation. The gain of the hierarchies is demonstrated by solving ILPs to compute hierarchies and trees. The advantages of the spanning hierarchies are conclusive: (1) spanning hierarchies can be found in some cases where spanning trees matching the degree constraints do not exist; (2) the cost of the hierarchy can be lower even if the Steiner tree satisfying the constraints exists
Blow-ups and extensions of trees in tournaments
No full textA class of acyclic digraphs is linearly unavoidable if there exists a constant such that every digraph is contained in all tournaments of order . The class of all acyclic digraphs is not linearly avoidable, and Fox, He, and Widgerson recently showed that this is not even the case for acyclic digraphs with bounded maximum degree. On the positive side, Thomason and Häggkvist proved that the class of oriented trees is linearly unavoidable. In this work, we generalize this result to acyclic digraphs obtained from an oriented tree by adding at most vertices, and -blow-ups of oriented trees, for every fixed integer . More precisely, we show that if is obtained from an oriented tree of order by adding universal vertices, then is contained in every tournament of order ; and if is obtained from by replacing each vertex by an independent set of size and every arc by all possible arcs from to , then is contained in every tournament of order
Graphes expanseurs et applications à la cryptographie en théorie de l'information
No full textThis PhD thesis is a work on spectral graph theory and its applications to cryptography in the framework of algorithmic theory of information.We start by presenting a general introduction on spectral graph theory. We first explain the various connections between the spectrum of regular graphs and their combinatorial properties, in particular their expansion properties. We follow by presenting most of the technical tools that are classical in the field and necessary for our contribution.Secondly, we study several models of random graphs that are potentially useful for practical applications. The graphs we study here are sparse. Our work first focus on numerical experiments on such graphs. We provide experimental evidence that some models of random graphs such as random Schreier graphs of the general linear group or graphs from Toeplitz matrices are very good spectral expander, at least for the set of parameters we tested. Moreover, we give some theoretical bounds on the expected second largest eigenvalue of Schreier graphs that gives guarantees on the spectral expansion of such mathematical objects for fixed parameters.We follow our study with some applications of spectral and combinatorial properties of graphs to communication problems in the framework of algorithmic information theory. We start by giving the general context on Kolmogorov complexity and mutual information extractability. After this introductory work, we detail our technical tools from graph theory that are then used to prove mutual information inextractability properties of some algebraic structures represented as graphs (the graphs that will be of use here are much denser than that of the previous chapter). After explaining the background needed from information theoretic cryptography, we use these properties to establish worst case upper bounds on communication complexity on secret key agreement with three participants, and other impossibility results on communication problems in cryptography.Cette thèse de doctorat porte sur la théorie spectrale des graphes et ses applications à la cryptographie dans le cadre de la théorie algorithmique de l'information. Nous commençons par présenter une introduction générale à la théorie spectrale des graphes. Nous expliquons d'abord les diverses relations entre le spectre des graphes réguliers et leurs propriétés combinatoires, en particulier leurs propriétés d'expansion. Nous poursuivons en présentant la plupart des outils techniques classiques dans ce domaine et nécessaires à notre contribution. Dans un deuxième temps, nous étudions plusieurs modèles de graphes aléatoires qui sont potentiellement utiles pour des applications pratiques. Les graphes étudiés ici ont relativement peu d'arêtes. Notre travail se concentre d'abord sur des expériences numériques sur ces graphes. Nous fournissons des preuves expérimentales que certains modèles de graphes aléatoires, tels que les graphes de Schreier aléatoires du groupe général linéaire ou les graphes issus des matrices de Toeplitz, sont de très bons expanseurs spectraux, du moins avec les paramètres que nous avons testés. De plus, nous fournissons des bornes théoriques sur l'espérance de la deuxième plus grande valeur propre de nos graphes de Schreier, ce qui offre des garanties sur l'expansion spectrale de tels objets mathématiques pour des paramètres fixés. Nous poursuivons notre étude avec quelques applications des propriétés spectrales et combinatoires des graphes aux problèmes de communication dans le cadre de la théorie algorithmique de l'information. Nous commençons par donner le contexte général de la complexité de Kolmogorov et de l'extractibilité de l'information mutuelle. Après ce travail introductif, nous détaillons nos outils techniques issus de la théorie des graphes qui sont ensuite utilisés pour prouver des propriétés d'inextractibilité de l'information mutuelle de certaines structures algébriques représentées sous forme de graphes (les graphes qui nous seront utiles ici seront beacuoup plus denses que précédement). Après avoir expliqué les bases nécessaires issues de la cryptographie en théorie de l'information, nous utilisons ces propriétés pour établir des bornes supérieures en pire cas sur la complexité de communication lors d'un accord de clé secrète avec trois participants, ainsi que d'autres résultats d'impossibilité sur des problèmes de communication en cryptographie
Compact Solution Representation in Qualitative Constraint-Based Reasoning
No full textInternational audienceIn the framework of Qualitative Spatio-Temporal Reasoning (QSTR), we can consider constraints like x{is above ∨ is under} y, and combinations thereof, to represent and reason about spatial or temporal information in an intuitive, human-like way. QSTR becomes particularly important in view of possible lack, uncertainty, and/or imperfection of metric data, as treating such quantitative information qualitatively would provide more leeway to perform sound reasoning. Adding to the usefulness of QSTR, in this short paper, we introduce the notion of multi-scenario for representing solutions of networks of qualitative spatio-temporal constraints in a compact manner, as a means to assessing and enhancing the explainability and robustness of AI systems that involve spatio-temporal information. Further, we prove certain theoretical properties pertaining to this novel notion, and even introduce some robustness measures relating to our notion of multi-scenario
Direct TPS-based 3D non-rigid motion estimation on 3D colored point cloud in eye-in-hand configuration
No full textInternational audienceIn this paper, a method for 3D non-rigid motion estimation of a surface using an RGB-D camera in eye-in-hand configuration is presented. The eye-in-hand configuration eliminates errors typically associated with camera-end-effector calibration, and is thus desirable for task on moving surfaces such as bioprinting. However, its implementation is challenging since camera and surface of interest are moving, making mesh-based approaches unsuitable. Thus, the proposed method operates directly on point clouds, benefiting from accurate and simplified data processing. A point cloud contains both intensity and depth data, with the former used to estimate in-plane deformation and the latter to compute full 3D deformation. Surface deformation is modeled via a Thin Plate Spline model. The method accuracy is assessed at 0.1 mm accuracy in simulated datasets, rendering it suitable for precision tasks, and its feasibility is validated experimentally on a moving platform that deforms at a rate of 0.8 Hz with a 4 mm in-plane amplitude and a 20 mm elevation amplitude
Robots programmés à impact
No full textThe surge in e-commerce has outpaced the capacity of human labor, which has long been the backbone of logistics. This pressing issue necessitates the integration of robots into repetitive and labor-intensive tasks, marking a significant shift in the logistics landscape.Humans employ diverse parcel-handling techniques, ranging from pre-grabbing maneuvers to placing and throwing. In contrast, robots have been constrained in their ability to pick and place. This thesis introduces an innovative approach to address this disparity by iterating impact-aware control with model-based task definitions.The first part of this thesis details a novel strategy for planning robotic motions tailored to impact-intensive tasks such as tossing, grabbing, and boxing. While the current state of robotics technology features high-performance hardware, robots tend to decelerate to zero velocity when approaching contact (e.g., for picking up items).Our research focuses on enabling motion generation to embrace contact at non-zero velocity configurations and facilitate non-stop trajectory cycles. This is achieved by enhancing a sampling-based planner that integrates kinodynamic constraints and utilizes kinematic redundancy to define optimized paths. We also explore high-dynamic logistic tasks —like tossing items to different targets with or without controlled impact velocity, dual-arm grabbing, and dynamic box tilting—applying the improved planner to these scenarios. This approach has demonstrated efficiency in both motion generation and the robot's control ability to handle impacts and perform complex maneuvers effectively.Following this, the thesis presents a model-based method for determining the optimal sequence of pokes to achieve desired planar motions using a robotic manipulator. Nonprehensible manipulations, where grasping is not involved, have proven valuable in real-world applications. One area of interest is manipulating objects on a planar environment. However, this task could be expedited by introducing impacts into the process. A new mixed-integer nonlinear problem is formulated to tackle this challenge, integrating a carefully designed planar friction model that accounts for both sliding and spinning motions. The optimized poking actions are then used to compute the robot's end-effector velocities and directional effective inertia. Afterward, an impact-aware jerk-based planner and quadratic programming (QP) are employed to plan and track the desired impact trajectories.Lastly, the thesis explores trajectory optimization taking into account the modeling of suction cup deformation in the different phases of manipulation (including grabbing, holding, and tossing). This is motivated mainly by observations during preliminary experiments and results.A trajectory optimization is formulated to handle the discussed suction cup deformable model. This investigation improves our understanding of how suction cups deform under high acceleration motions, ultimately enabling efficient planning for tossing tasks.In conclusion, this thesis aims to improve robots' capabilities to handle impacts through impact-aware planning techniques and detailed task modeling, ultimately enhancing their operational efficiency in logistics applications. This work contributes to the broader goal of developing more adaptable and resilient robotic systems for the industrial sector.Le commerce électronique a dépassé les capacités humaines, qui ont longtemps été l'élément clé de la logistique. La résolution de ce problème nécessite l'intégration de robots dans les tâches répétitives et à forte intensité de main-d'œuvre, ce qui marque un changement important dans le domaine de la logistique.Les humains utilisent diverses techniques de manipulation des colis, allant des manœuvres de préhension à la mise en place et au lancement. En revanche, les robots ont été limités dans leur capacité à prélever et à déposer les colis. Cette thèse propose une approche pour répondre à cette disparité en intégrant un contrôle conscient de l'impact avec des définitions de tâches basées sur des modèles.Le premier chapitre de cette thèse détaille une nouvelle stratégie de planification des mouvements robotiques adaptée aux tâches d’impact. Bien que l'état actuel de la technologie robotique présente un matériel de haute performance, les robots ont tendance à décélérer jusqu'à une vitesse nulle lorsqu'ils s’approchent d'un contact.Notre recherche se concentre sur la génération de mouvements permettant de maintenir le contact à des configurations de vitesse non nulle et de faciliter les cycles de trajectoire non-stop. Nous y parvenons en améliorant un planificateur basé sur l'échantillonnage qui intègre les contraintes kinodynamiques et utilise la redondance cinématique pour définir des trajectoires optimisées. Nous explorons également des tâches logistiques très dynamiques, telles que le lancer d'objets vers différentes cibles avec ou sans contrôle de la vitesse d'impact, la saisie à deux bras et le basculement dynamique d'une boîte, en appliquant le planificateur amélioré à ces scénarios. Cette approche a prouvé son efficacité dans la génération de mouvements ainsi que dans la capacité de contrôle du robot à gérer les impacts et à effectuer des manœuvres complexes de manière efficace.Ensuite, la thèse présente une méthode basée sur la modélisation des mouvements planaires afin de déterminer la séquence optimale de coups réalisés à l'aide d'un manipulateur robotique.Dans les applications du monde réel, les manipulations non-préhensibles, où la saisie n'est pas nécessaire, sont très utiles. L'un des domaines d'intérêt est la manipulation d'objets dans un environnement plan. Cependant, cette tâche pourrait être accélérée en introduisant des impacts dans le processus. Pour relever ce défi, un nouveau problème non linéaire en variables mixtes est formulé, en intégrant un modèle de frottement planaire soigneusement conçu qui prend en compte à la fois des mouvements de glissement et de rotation. Les actions optimisées de manipulation sont ensuite utilisées pour calculer les vitesses de l’outil du robot et l'inertie effective directionnelle. Enfin, un planificateur qui minimise les saccades et un contrôleur basé sur la programmation quadratique sont utilisés pour planifier et suivre les trajectoires d'impact désirées.Enfin, la thèse explore l'optimisation des trajectoires en prenant en compte la modélisation de la déformation de la ventouse lors des différentes étapes de la manipulation (y compris la saisie, le maintien et le lancer). Ceci est motivé principalement par les observations faites lors des expériences préliminaires et les résultats obtenus.Une optimisation de la trajectoire est formulée pour traiter le modèle de déformation de la ventouse déjà mentionné. Cette étude nous permet de mieux comprendre la manière dont les ventouses se déforment sous l'effet de mouvements à forte accélération, ce qui nous permettra de planifier efficacement les tâches de lancer.En conclusion, cette thèse vise à améliorer les capacités des robots à gérer les impacts grâce à des techniques de planification intégrant le modèle d’impacts et une modélisation détaillée des tâches. Ce travail contribue au développement des systèmes robotiques plus adaptables et résistants afin de répondre aux besoins du secteur industriel