Décomposition LU | EPFL Graph Search

En algèbre linéaire, la décomposition LU est une méthode de décomposition d'une matrice comme produit d'une matrice triangulaire inférieure (comme lower, inférieure en anglais) par une matrice triangulaire supérieure (comme upper, supérieure). Cette décomposition est utilisée en analyse numérique pour résoudre des systèmes d'équations linéaires. Définition Soit une matrice carrée. On dit que admet une décomposition LU s'il existe une matrice triangulaire inférieure formée de 1 sur la diagonale, notée , et une matrice triangulaire supérieure, notée , qui vérifient l'égalité :A = L U ; Il n'est pas toujours vrai qu'une matrice admette une décomposition LU. Cependant dans certains cas, en permutant des lignes de , la décomposition devient possible. On obtient alors une décomposition de la forme :A = P L U ; où est une matrice de permutation. Bien que les décompositions LU et PLU conduisent à des formules distinctes, généralement quand on

Automatic extraction of constraints in manipulation tasks for autonomy and interaction

Ana-Lucia Ureche

Tasks routinely executed by humans involve sequences of actions performed with high dexterity and coordination. Fully specifying these actions such that a robot could replicate the task is often difficult. Furthermore the uncertainties introduced by the use of different tools or changing configurations demand the specification to be generic, while enhancing the important task aspects, i.e. the constraints. Therefore the first challenge of this thesis is inferring these constraints from repeated demonstrations. In addition humans explaining a task to another person rely on the person's ability to apprehend missing or implicit information. Therefore observations contain user-specific cues, alongside knowledge on performing the task. Thus our second challenge is correlating the task constraints with the user behavior for improving the robot's performance. We address these challenges using a Programming by Demonstration framework. In the first part of the thesis we describe an approach for decomposing demonstrations into actions and extracting task-space constraints as continuous features that apply throughout each action. The constraints consist of: (1) the reference frame for performing manipulation, (2) the variables of interest relative to this frame, allowing a decomposition in force and position control, and (3) a stiffness gain modulating the contribution of force and position. We then extend this approach to asymmetrical bimanual tasks by extracting features that enable arm coordination: the master--slave role that enables precedence, and the motion--motion or force--motion coordination that facilitates the physical interaction through an object. The set of constraints and the time-independent encoding of each action form a task prototype, used to execute the task. In the second part of the thesis we focus on discovering additional features implicit in the demonstrations with respect to two aspects of the teaching interactions: (1) characterizing the user performance and (2) improving the user behavior. For the first goal we assess the skill of the user and implicitly the quality of the demonstrations by using objective task--specific metrics, related directly to the constraints. We further analyze ways of making the user aware of the robot's state during teaching by providing task--related feedback. The feedback has a direct influence on both the teaching efficiency and the user's perception of the interaction. We evaluated our approaches on robotic experiments that encompass daily activities using two 7 degrees of freedom Kuka LWR robotic arms, and a 53 degrees of freedom iCub humanoid robot.

EPFL2018

The stable set polytope of quasi-line graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. Such a conjecture exists for the class of quasi-line graphs. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. Ben Rebea's conjecture states that the stable set polytope of a quasi-line graph is completely described by clique-family inequalities. Chudnovsky and Seymour recently provided a decomposition result for claw-free graphs and proved that Ben RA a's conjecture holds, if the quasi-line graph is not a fuzzy circular interval graph.. In this paper, we give a proof of Ben Rebea's conjecture by showing that it also holds for fuzzy circular interval graphs. Our result builds upon an algorithm of Bartholdi, Orlin and Ratliff which is concerned with integer programs defined by circular ones matrices

2008

Circular Ones Matrices and the Stable set Polytopes of Quasi-Line Graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. Such a conjecture exists for the class of quasi-line graphs. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. Ben Rebea’s conjecture states that the stable set polytope of a quasi-line graph is completely described by clique-family inequalities. Chudnovsky and Seymour recently provided a decomposition result for claw-free graphs and proved that Ben Rebea’s conjecture holds, if the quasi-line graph is not a fuzzy circular interval graph. In this paper, we give a proof of Ben Rebea’s conjecture by showing that it also holds for fuzzy circular interval graphs. Our result builds upon an algorithm of Bartholdi, Orlin and Ratliff which is concerned with integer programs defined by circular ones matrices.

2005

Automatic extraction of constraints in manipulation tasks for autonomy and interaction

Ana-Lucia Ureche

EPFL2018