Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
Column generation in column-and-constraint generation for adjustable robust optimization with Interdiction-type linking Constraints
No full textInternational audienceAbstract Adjustable robust optimization (ARO) is a powerful tool to model problems that have uncertain data and that feature a two-stage decision-making process. Computationally, they are often addressed using the column-and-constraint generation (CCG) algorithm introduced by Zeng and Zhao [45]. While it was empirically shown that the algorithm scales well if all second-stage decisions are continuous, the presence of integer variables in the second stage rapidly leads to challenging large-scale mixed-integer problems within CCG. These problems can no longer be solved to global optimality within reasonable time limits in general. In this work, we explicitly focus on ARO problems with mixed-integer second-stage decisions and discuss the main difficulties of successfully applying CCG to this problem class. We then introduce, for a large set of problems with specific structural properties, a stronger formulation, which can be used in place of the master problem in the classic CCG algorithm. We show how this model can be effectively solved by column generation (CG). Additionally, we introduce a new CG-based heuristic that is able to generate new feasible points to speed up the overall method. We apply this nested scheme, combining CCG and CG, to three problems from logistics and scheduling to show the applicability of our approach
Métaphore et comparaison, ellipses de l’analogie : convergences en linguistique et en Traitement Automatique du Langage Naturel
No full textInternational audienceL’article "Métaphore et comparaison, ellipses de l’analogie : convergences en linguistique et en Traitement Automatique du Langage Naturel", co-écrit par Emilia Hilgert et Jérémie Roux, réunit le point de vue linguistique et celui informatique dans la présentation de l’analogie comme base de la métaphore et de la comparaison. Ces deux approches s’éclairent mutuellement dans le but d’expliquer le fonctionnement sémantico-lexical de l’analogie sous la forme du carré analogique. Celui-ci révèle avec précision le processus inférentiel du glissement de sens métaphorique et génère la métaphore et la comparaison à deux ou trois termes par l’inférence, grâce à ses variantes à variables implicites. Les deux points de vue complémentaires se rencontrent aussi dans l’idée que l’analogie, qui peut être perçue intuitivement comme une ressemblance entre deux termes, fonctionne en fait grâce à l’activation automatique de deux autres termes supplémentaires et que ce sont les relations qui s’établissent avec ces termes de référence restrictive qui instruisent la prédication indirecte de l’analogie et de la métaphore, qui n’est qu’une ellipse de celle-ci. Les graphes informatisés générés par les moyens du TALN visualisent parfaitement ce processus
Implementation and Performance Analysis of a Digital BPSK Demodulation Technique for Galvanic-Coupling Communication
No full textInternational audienceThis paper presents a digital demodulation technique for use in galvanic coupling intra-body communication (GC IBC) with BPSK-modulated signals at low frequencies (below MHz). The technique relies on a direct oversampled acquisition of the BPSK-modulated signal with an analogueto-digital converter (ADC) associated with an original digital processing algorithm to extract the demodulated data from the acquired samples. The originality of the solution resides in the digital processing algorithm which combines several mechanisms to fully exploit the redundancy present in the collected samples in order to provide a high degree of robustness, while maintaining a low level of complexity compatible with efficient implementation in a microcontroller. Simulation and measurement results are presented, confirming the robustness of the proposed solution. In particular, hardware measurements carried out under controlled conditions demonstrate very good performance, with a Bit Error Rate (BER) below 3 × 10 -5 for a signal with a Signal-to-Noise Ratio (SNR) of -5 dB. The proposed solution is also validated under real conditions with a GC communication realized through the back muscle of a fish, resulting in a BER < 2.5 × 10 -6
A New Extended High-Gain Observer for Robotic Manipulators Robust to Variations in Measurements Sampling
No full textInternational audienceThis paper presents a novel sampled-data observer for robotic manipulators subject to internal and external disturbances. The proposed approach is a novel continuous-discrete extended high-gain observer featuring: (i) simultaneou estimation of both system states and disturbances; (ii) explicite consideration of sampled-data measurements, including potential differences in sampling frequencies between the controller and the measurement device, which provides robustness to variations in sampling; (iii) a new type of time-varying gain that significantly reduces the effect of measurement noise on the estimated variables; and (iv) a detailed theoretical analysis that guides parameter tuning to enhance the observer's estimation accuracy. The proposed observer has been validated through real-time experiments on ERRIC industrial manipulator. The obtained results show clearly the benefits of the proposed observer design and its effectiveness as well as robustness, compared to other solutions from the literature
Applications et limites de l'algorithme quantique de Grover
No full textThe Grover algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems, requiring O(√N) queries instead of O(N) classically. It works by repeatedly applying an oracle and a diffusion operator to amplify the probability of marked states. This advantage makes it relevant to cryptography, optimization, constraint satisfaction, and as a general primitive via amplitude amplification in areas like quantum machine learning and simulation. However, practical implementations are severely constrained by current Noisy Intermediate Scale Qualtum machines with limited coherence, deep oracle circuits and lack of scalable QRAM, restricting demonstrations to small-scale experiments with reproducibility challenges.</div
Cost Efficient Flip-Flop Designs With Multiple-Node Upset-Tolerance and Algorithm-Based Verifications
No full textInternational audienceThis paper presents radiation-hardened flip-flop (FF) designs capable of tolerating soft errors, e.g., single-node upsets (SNUs), double-node upsets (DNUs) and multiple-node upsets (MNUs). First, a 2-input FF and a 3-input FF are proposed as the baseline FFs that not only respectively tolerate SNUs and DNUs but also exhibit cost efficiency in terms of delay, power, and area. Through adding two stages of C-elements, a 4-input FF and a 5-input FF are proposed as the baseline FFs as well. Utilizing the structural characteristics of these FFs, an N-1 input FF and an N input FF are proposed as the extended FFs capable of tolerating more node upsets. Moreover, a highly efficient algorithm for verifying MNU-tolerance of these FFs is proposed. Algorithm and HSPICE-tool-based verification results both demonstrate the MNU-tolerance for the proposed FFs with more inputs
Humanoid Feet with Soft Sole and Passive Toe-Joint to Achieve Close-to-Human Walks
No full textInternational audienceThis paper explores the synergistic application of the intrinsically stable MPC algorithm and human gait data retrieved via Xsens motion capture to optimize the geometric parameters of robot soles for mimicking human walking. Additionally, it investigates the use of an Ogden hyper-elastic model to determine the mechanical parameters of a soft component added beneath the robot soles to enhance stability and robustness when encountering small obstacles. Through a combination of control theory, our approach aims to achieve natural and stable robot locomotion in dynamic environments. Experimental results demonstrate the effectiveness of the proposed method in improving the walking performance and obstacle negotiation capabilities of the robot, paving the way for advancements in humanoid robotics and assistive technologies
Design and Validation of a Soft Pneumatic Submodule for Adaptive Humanoid Foot Compliance
No full textInternational audienceAchieving stable contact on uneven terrain remains a key challenge in humanoid robotics, as most feet rely on rigid or passively compliant structures with fixed stiffness. This work presents the design, fabrication, and analytical modeling of a compact soft pneumatic submodule capable of tunable longitudinal stiffness, developed as a proof-of-concept unit for adaptive humanoid feet. The submodule features a tri-layer architecture with two antagonistic pneumatic chambers separated by an inextensible layer and reinforced by rigid inserts. A single-step wax-core casting process integrates all materials into a monolithic soft–rigid structure, ensuring precise geometry and repeatable performance. An analytical model relating internal pressure to equivalent stiffness was derived and experimentally validated, showing a linear stiffness–pressure relation with mean error below 10% across 0–30 kPa. Static and dynamic tests confirmed tunable stiffness between 0.18 and 0.43 N·m/rad, a rapid symmetric response (2.9–3.4 ms), and stable stiffness under cyclic loading at gait-relevant frequencies. These results demonstrate the submodule’s suitability as a scalable building block for distributed, real-time stiffness modulation in next-generation humanoid feet
Dichromatic number of chordal graphs
No full textInternational audienceThe dichromatic number of a digraph is the minimum integer such that admits a -dicolouring, \textit{i.e.} a partition of its vertices into acyclic subdigraphs. We say that a digraph is a super-orientation of an undirected graph if is the underlying graph of . If does not contain any pair of symmetric arcs, we just say that is an orientation of .In this work, we give both lower and upper bounds on the dichromatic number of super-orientations of chordal graphs. In general, the dichromatic number of such digraphs is bounded above by the clique number of the underlying graph (because chordal graphs are perfect). However, this bound can be improved when we restrict the symmetric part of such a digraph.Let be a super-orientation of a chordal graph . Let be the undirected graph with vertex set in which is an edge if and only if both and belongs to . An easy greedy procedure shows . We show that this bound is best possible by constructing, for every fixed with , a super-orientation of a chordal graph such that , and .When (\textit{i.e.} is an orientation of ), we give another construction showing that this is tight even for orientations of interval graphs.Next, we show that with the maximum average degree of .Finally, we show that if contains no as a subgraph, then . We justify that this is almost best possible by constructing, for every fixed , a super-orientation of a chordal graph with clique number such that is a disjoint union of paths and .We also exhibit a family of orientations of cographs for which the dichromatic number is equal to the clique number of the underlying graph
A proposal for building a compact and tunable representation of a concept lattice based on clustering
No full textbaixeries2025aInternational audienceA concept lattice provides a model of a dataset that can be navigated and explored by an analyst in an interactive way, except when the concept lattice is too large. Such a problem can be overcome by building a representation of the whole concept lattice that keeps a reasonable size and that can be interpreted by the analyst. Relying on previous work about link key discovery, we revisit in this paper an approach based on Formal Concept Analysis (FCA) and Agglomerative Hierarchical Clustering (AHC) applied to a set of concepts for building a representative set of clusters. Accordingly, we propose an AHC algorithm that (a) efficiently computes this representative set, and (b) respects the ordinal structure of the original concept lattice. A set of experiments performed over real datasets shows the effectiveness of our approach