Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes
Choisir la langue : FR | EN

43documents trouvés

16444
02/12/2016

Temporal and hierarchical models for planning and acting in robotics

A.BIT-MONNOT

RIS

Doctorat : INP de Toulouse, 2 Décembre 2016, 199p., Président: R.ALAMI, Rapporteurs: J.HERTZBERG, F.PECORA, Examinateurs: A.CESTA, C.PRALET, D.E.SMITH, Directeurs de thèse: M.GHALLAB, F.INGRAND , N° 16444

Lien : https://hal.laas.fr/tel-01444926

Diffusable

Plus d'informations

Abstract

The field of AI planning has seen rapid progress over the last decade and planners are now able to find plans with hundreds of actions in a matter of seconds. Despite those important progresses, robotic systems still tend to have a reactive architecture with very little deliberation on the course of the plan they might follow. In this thesis, we argue that a successful integration with a robotic system requires the planner to have capacities for both temporal and hierarchical reasoning. The former is indeed a universal resource central in many robot activities while the latter is a critical component for the integration of reasoning capabilities at different abstraction levels, typically starting with a high level view of an activity that is iteratively refined down to motion primitives. As a first step to carry out this vision, we present a model for temporal planning unifying the generative and hierarchical approaches. At the center of the model are temporal action templates complemented with a specification of the initial state as well as the expected evolution of the environment over time. In addition, our model allows for the specification of hierarchical knowledge possibly with a partial coverage. Consequently, our model generalizes the existing generative and hierarchical approaches together with an explicit time representation. In the subsequent chapter, we introduce a planning procedure suitable for our planning model. In order to support hierarchical features, we extend the existing Partial-Order Causal Link approach used in many constraint-based planners, with the notions of task and decomposition. We implement it in FAPE (Flexible Acting and Planning Environment) together with automated problem analysis techniques used for search guidance. We show FAPE to have performance similar to state of the art temporal planners when used in a generative setting, and the addition of hierarchical information to lead to further performance gain. Next, we study the usual methods used to reason on temporal uncertainty while planning. We relax the usual assumption of total observability and instead provide techniques to reason on the observations needed to maintain a plan dispatchable. We show how such needed observations can be detected at planning time and incrementally dealt with by considering the appropriate sensing actions. In a final chapter, we discuss the place of the proposed planning system as a central component for the control of a robotic actor. We demonstrate how the explicit time representation facilitates plan monitoring and action dispatching when dealing with contingent events that require observation. We take advantage of the constraint-based and hierarchical representation to facilitate both plan-repair procedures as well opportunistic plan refinement at acting time.

138414
16471
08/09/2016

Symbolic and geometric planning for teams of robots and humans

R.LALLEMENT

RIS

Doctorat : INSA de Toulouse, 8 Septembre 2016, 145p., Président: M.GHALLAB, Rapporteurs: F.CHARPILLET, A.SAFFIOTTI, Examinateurs: I.MAZZA, Directeurs de thèse: R.ALAMI , N° 16471

Lien : https://tel.archives-ouvertes.fr/tel-01534323

Diffusable

Plus d'informations

Abstract

Hierarchical Task Network (HTN) planning is a popular approach to build task plans to control intelligent systems. It is used in a variety of fields such as robotics, mission control, and so on. Its popularity comes from the intuitive representation that it uses, furthermore the planner uses that representation to cut down the search space (compared to classical planning approaches). In robotics, the domain representation consists in specifying high-level instructions on how robots and agents should perform tasks, while also giving the planner enough flexibility to choose the lower-level steps and their ordering. This thesis presents the HATP (Hierarchical Agent-based Task Planner) planning framework which extends the traditional HTN planning domain representation and semantics by making them more suitable for roboticists, and by offering human-awareness capabilities. This planning framework can be seen as a planning laboratory thanks to the ease to develop new domains and the possibility to extend its capabilities. When computing human-aware robot plans, it appears that the problems are very complex and highly intricate. To deal with this complexity we have integrated a geometric planner to reason about the actual impact of actions on the environment and allow to take into account the affordances (reachability, visibility). To benefit from this geometric layer, the symbolic layer refines the actions in the current plan it is computing by assessing their geometric feasibility in the current world state. In addition the geometric layer computes and sends back symbolic literals representing the effective outcome on the environment of the particular instance of actions chosen by the geometric planner. The symbolic layer can use these literals to reason about the side effects of the actions which allows to partially tackle the ramification problem. This thesis presents in detail this integration between two heterogeneous planning layers and explores how they can be combined to solve new classes of robotic planning problems. One of the main issues we face when combining the two layers is the planning time that grows rapidly and prevents any significantly-big problem to be solved in reasonable time. We study and propose in this thesis an improvement to the backtrack mechanism to drive the symbolic search toward more promising solutions using a combination of symbolic and geometric information.

Résumé

La planification HTN (Hierarchical Task Network, ou Réseau Hiérarchique de Tâches) est une approche très souvent utilisée pour produire des séquences de tâches servant à contrôler des systèmes intelligents. Cette méthode est employée dans différents domaines parmi lesquels la robotique, le contrôle de missions, etc. La reconnaissance dont elle bénéficie vient de la façon intuitive qu’elle a de représenter les problèmes. De plus elle adopte cette description pour accélérer la recherche (par rapport à la planification dite classique). Encoder un domaine robotique consiste à spécifier des instructions de haut-niveau décrivant comment les robots et les agents doivent accomplir leurs tâches tout en assurant assez de flexibilité au planificateur pour lui permettre de choisir l’ordre des étapes de bas-niveau. Cette thèse présente le planificateur HATP (Hierarchical Agent-base Task Planner, ou Planificateur Hiérarchique centré Agent) qui étend la planification HTN classique en enrichissant la représentation des domaines et leur sémantique afin d’être plus adaptées à la robotique, tout en offrant aussi une prise en compte des humains. HATP peut être vu comme un laboratoire de planification de par sa capacité à être amélioré et la facilité à ajouter de nouveaux domaines. Quand on souhaite générer un plan pour des robots tout en prenant en compte les humains, il apparaît que les problèmes sont complexes et fortement interdépendants. Afin de faire face à cette complexité, nous avons intégré à HATP un planificateur géométrique apte à déduire l’effet réel des actions sur l’environnement et ainsi permettre de considérer la visibilité et l’accessibilité des éléments. Pour exploiter cette couche géométrique, la couche symbolique affine les actions du plan lors du calcul en en vérifiant la faisabilité dans l’état courant du monde. En outre la couche géométrique produit et renvoie des littéraux décrivant le résultat effectif d’une action particulière (instanciée) sur l’environnement quand celle-ci à été choisie par le planificateur géométrique. La couche symbolique peut alors faire face à une partie du problème de la ramification en s’appuyant sur ces littéraux qui incluent notamment les effets de bords des actions. Cette thèse se concentre sur l’intégration de ces deux planificateurs de nature différente et étudie comment par leur combinaison ils permettent de résoudre de nouvelles classes de problèmes de planification pour la robotique. Une des difficultés majeures de cette combinaison de couches vient du temps de calcul qui croît trop rapidement empêchant de fait la résolution de problèmes conséquents en un temps raisonnable. Nous étudions puis proposons un certain nombre d’améliorations au mécanisme dit de backtrack (ce qui signifie de revenir sur les choix faits plus tôt dans le calcul d’un plan) afin de mieux diriger la recherche vers des solutions plus prometteuses, le tout en utilisant des informations aussi bien symboliques que géométriques.

138515
16052
28/01/2016

Unsupervised Gaussian mixture models for the classification of outdoor environments using 3D terrestrial lidar data

A.O.MALIGO

RIS

Doctorat : INSA de Toulouse, 28 Janvier 2016, N°73, Président: M.DEVY, Rapporteurs: O.AYCARD, P.CHECCHIN, Directeurs de thèse: S.LACROIX , N° 16052

Lien : https://tel.archives-ouvertes.fr/tel-01297542

Diffusable

Plus d'informations

Abstract

The processing of 3D lidar point clouds enable terrestrial autonomous mobile robots to build semantic models of the outdoor environments in which they operate. Such models are interesting because they encode qualitative information, and thus provide to a robot the ability to reason at a higher level of abstraction. At the core of a semantic modelling system, lies the capacity to classify the sensor observations. We propose a two-layer classi- fication model which strongly relies on unsupervised learning. The first, intermediary layer consists of a Gaussian mixture model. This model is determined in a training step in an unsupervised manner, and defines a set of intermediary classes which is a fine-partitioned representation of the environment. The second, final layer consists of a grouping of the intermediary classes into final classes that are interpretable in a considered target task. This grouping is determined by an expert during the training step, in a process which is supervised, yet guided by the intermediary classes. The evaluation is done for two datasets acquired with different lidars and possessing different characteristics. It is done quantitatively using one of the datasets, and qualitatively using another. The system is designed following the standard learning procedure, based on a training, a validation and a test steps. The operation follows a standard classification pipeline. The system is simple, with no requirement of pre-processing or post-processing stages.

136347
15711
23/11/2015

Location models for visual place recognition

E.STUMM

RIS

Doctorat : Université de Toulouse III - Paul Sabatier, Novembre 2015, 160p., Président: P.DANES, Rapporteurs: D.FILLIAT, J.NEIRA, Examinateurs: I.POSNER, Directeurs de thèse: S.LACROIX, C.MEI , N° 15711

Lien : https://hal.laas.fr/tel-01376134

Diffusable

Plus d'informations

Résumé

Cette thèse traite de la cartographie et de la reconnaissance de lieux par vision en robotique mobile. Les recherches menées visent à identifier comment les modèles de localisation peuvent être améliorés en enrichissant les représentations existantes afin de mieux exploiter l’information visuelle disponible. Les problèmes de la cartographie et de la reconnaissance visuelle de lieux présentent un certain nombre de défis : les solutions doivent notamment être robustes vis-à-vis des scènes similaires, des changements de points de vue de d’éclairage, de la dynamique de l’environnement, du bruit des données acquises. La définition de la manière de modéliser et de comparer les observations de lieux est donc un élément crucial de définition d’une solution opérationnelle. Cela passe par la spécification des caractéristiques des images à exploiter, par la définition de la notion de lieu, et par des algorithmes de comparaison des lieux. Dans la littérature, les lieux visuels sont généralement définis par un ensemble ou une séquence d’observations, ce qui ne permet pas de bien traiter des problèmes de similarité de scènes ou de reconnaissance invariante aux déplacements. Dans nos travaux, le modèle d’un lieu exploite la structure d’une scène représentée par des graphes de covisibilité, qui capturent des relations géométriques approximatives entre les points caractéristiques observés. Grâce à cette représentation, un lieu est identifié et reconnu comme un sous-graphe. La reconnaissance de lieux exploite un modèle génératif, dont la sensibilité par rapport aux similarités entre scènes, aux bruits d’observation et aux erreurs de cartographie est analysée. En particulier, les probabilités de reconnaissance sont estimées de manière rigoureuse, rendant la reconnaissance des lieux robuste, et ce pour une complexité algorithme sous-linéaire en le nombre de lieux définis. Enfin les modèles de lieux basés sur des sacs de mots visuels sont étendus pour exploiter les informations structurelles fournies par le graphe de covisibilité, ce qui permet un meilleur compromis entre la qualité et la complexité du processus de reconnaissance.

Abstract

This thesis deals with the task of appearance-based mapping and place recognition for mobile robots. More specifically, this work aims to identify how location models can be improved by exploring several existing and novel location representations in order to better exploit the available visual information. Appearance-based mapping and place recognition presents a number of challenges, including making reliable data-association decisions given repetitive and self-similar scenes (perceptual aliasing), variations in view-point and trajectory, appearance changes due to dynamic elements, lighting changes, and noisy measurements. As a result, choices about how to model and compare observations of locations is crucial to achieving practical results. This includes choices about the types of features extracted from imagery, how to define the extent of a location, and how to compare locations. Along with investigating existing location models, several novel methods are developed in this work. These are developed by incorporating information about the underlying structure of the scene through the use of covisibility graphs which capture approximate geometric relationships between local landmarks in the scene by noting which ones are observed together. Previously, the range of a location generally varied between either using discrete poses or loosely defined sequences of poses, facing problems related to perceptual aliasing and trajectory invariance respectively. Whereas by working with covisibility graphs, scenes are dynamically retrieved as clusters from the graph in a way which adapts to the environmental structure and given query. The probability of a query observation coming from a previously seen location is then obtained by applying a generative model such that the uniqueness of an observation is accounted for. Behaviour with respect to observation errors, mapping errors, perceptual aliasing, and parameter sensitivity are examined, motivating the use of a novel normalization scheme and observation likelihoods representations. The normalization method presented in this work is robust to redundant locations in the map (from missed loop-closures, for example), and results in place recognition which now has sub-linear complexity in the number of locations in the map. Beginning with bag-of-words representations of locations, location models are extended in order to include more discriminative structural information from the covisibility map. This results in various representations ranging between unstructured sets of features and full graphs of features, providing a tradeoff between complexity and recognition performance.

137179
15606
13/10/2015

Introducing contextual awareness within the state estimation process: Augmenting Bayes filters with context-dependent time-heterogeneous distributions

A.RAVET

RIS

Doctorat : INSA de Toulouse, 13 Octobre 2015, 193p., Président: D.FILLIAT, Rapporteurs: A.DUTECH, Examinateurs: M.GHALLAB, E.RACHELSON, Directeur de thèse: S.LACROIX , N° 15606

Lien : https://tel.archives-ouvertes.fr/tel-01291871

Diffusable

Plus d'informations

Abstract

Prevalent approaches for endowing robots with autonomous navigation capabilities require the estimation of a system state representation based on noisy sensor information. This system state usually depicts a set of dynamic variables such as the position, velocity and orientation required for the robot to achieve a task. In robotics, and in many other contexts, research e orts on state estimation converged towards the popular Bayes lter. The primary reason for the success of Bayes ltering is its simplicity, from the mathematical tools required by the recursive ltering equations, to the light and intuitive system representation provided by the underlying Hidden Markov Model. Recursive ltering also provides the most common and reliable method for real-time state estimation thanks to its computational eciency. To keep low computational complexity, but also because real physical systems are not perfectly understood, and hence never faithfully represented by a model, Bayes lters usually rely on a minimum system state representation. Any unmodeled or unknown aspect of the system is then encompassed within additional noise terms. On the other hand, autonomous navigation requires robustness and adaptation capabilities regarding changing environments. This creates the need for introducing contextual awareness within the ltering process. In this thesis, we speci cally focus on enhancing state estimation models for dealing with context-dependent sensor performance alterations. The issue is then to establish a practical balance between computational complexity and realistic modeling of the system through the introduction of contextual information. We investigate on achieving this balance by extending the classical Bayes lter in order to compensate for the optimistic assumptions made by modeling the system through time-homogeneous distributions, while still bene ting from the recursive ltering computational eciency. Based on raw data provided by a set of sensors and any relevant information, we start by introducing a new context variable, while never trying to characterize a concrete context typology. Within the Bayesian framework, machine learning techniques are then used in order to automatically de ne a context-dependent time-heterogeneous observation distribution by introducing two additional models: a model providing observation noise predictions and a model providing observation selection rules. The investigation also concerns the impact of the training method. In the context of Bayesian ltering, the underlying model we exploit is usually trained in the generative manner. Thus, optimal parameters are those that allow the model to explain at best the data observed in the training set. On the other hand, discriminative training can implicitly help in compensating for mismodeled aspects of the system, by optimizing the model parameters with respect to the ultimate system performance, the estimate accuracy. In a further discussion, we also analyse how the training method changes the meaning of the model, and how this property can be properly exploited. Throughout the manuscript, results obtained with simulated and representative real data are presented and analysed.

135988
15636
24/09/2015

Trajectory planning and control for robot manipulations

R.ZHAO

RIS

Doctorat : Université de Toulouse III - Paul Sabatier, 24 Septembre 2015, 137p., Président: R.ALAMI, Rapporteurs: A.CROSNIER, R.AHMED, Examinateurs: C.BES, M.MICHELIN, Directeurs de thèse: D.SIDOBRE , N° 15636

Lien : https://tel.archives-ouvertes.fr/tel-01285383

Diffusable

Plus d'informations

Abstract

In order to perform a large variety of tasks in interaction with human or in human environments, a robot needs to guarantee safety and comfort for humans. In this context, the robot shall adapt its behavior and react to the environment changes and human activities. The robots based on learning or motion planning are not able to adapt fast enough, so we propose to use a trajectory controller as an intermediate control layer in the software structure. This intermediate layer exchanges information with the low level controller and the high level planner. The proposed trajectory controller, based on the concept of Online Trajectory Generation (OTG), allows real time computation of trajectories and easy communication with the different components, including path planner, trajectory generator, collision checker and controller. To avoid the replan of an entire trajectory when reacting to a human behaviour change, the controller must allow deforming locally a trajectory or accelerate/decelerate by modifying the time function. The trajectory controller must also accept to switch from an initial trajectory to a new trajectory to follow. Cubic polynomial functions are used to describe trajectories, they provide smoothness, flexibility and computational simplicity. Moreover, to satisfy the objective of aesthetics, smoothing algorithm are proposed to produce human-like motions. This work, conducted as part of the ANR project ICARO, has been integrated and validated on the KUKA LWR robot platform of LAAS-CNRS.

Résumé

Comme les robots effectuent de plus en plus de tâches en interaction avec l’homme ou dans un environnement humain, ils doivent assurer la sécurité et le confort des hommes. Dans ce contexte, le robot doit adapter son comportement et agir en fonction des évolutions de l’environnement et des activités humaines. Les robots développés sur la base de l’apprentissage ou d’un planificateur de mouvement ne sont pas en mesure de réagir assez rapidement, c’est pourquoi nous proposons d’introduire un contrôleur de trajectoire intermédiaire dans l’architecture logicielle entre le contrôleur bas niveau et le planificateur de plus haut niveau Le contrôleur de trajectoire que nous proposons est basé sur le concept de générateur de trajectoire en ligne (OTG), il permet de calculer des trajectoires en temps réel et facilite la communication entre les différents éléments, en particulier le planificateur de chemin, le générateur de trajectoire, le détecteur de collision et le contrôleur. Pour éviter de replanifier toute une trajectoire en réaction à un changement induit par un humain, notre contrôleur autorise la déformation locale de la trajectoire et la modification de la loi d’évolution pour accélérer ou décélérer le mouvement. Le contrôleur de trajectoire peut également commuter de la trajectoire initiale vers une nouvelle trajectoire. Les fonctions polynomiales cubiques que nous utilisons pour d´ecrire les trajectoires fournissent des mouvements souples et de la flexibilité sans nécessiter de calculs complexes. De plus, les algorithmes de lissage que nous proposons permettent de produire des mouvements esthétiques ressemblants à ceux des humains. Ce travail, mené dans le cadre du projet ANR ICARO, a été intégré et validé avec les robots KUKA LWR de la plate-forme robotique du LAAS-CNRS.

Mots-Clés / Keywords
Robotics; Trajectory planning; Trajectory control; Human-robot interaction; Manipulation; Robotique; Planification de trajectoires; contrôle de trajectoire; Interaction homme-robot;

136074
15728
16/09/2015

Geometric reasoning and planning in the context of human robot interaction

M.GHARBI

RIS

Doctorat : INSA de Toulouse, 16 Septembre 2015, 179p., Président: T.SIMEON, Rapporteurs: M.BEETZ, R.CHATILA, Examinateurs: A.SUAREZ, Directeurs de thèse: R.ALAMI , N° 15728

Lien : https://hal.laas.fr/tel-01376082

Diffusable

Plus d'informations

Abstract

In the last few years, the Human robot interaction (HRI) field has been in the spotlight of the robotics community. One aspect of this field is making robots act in the presence of humans, while keeping them safe and comfortable. In order to achieve this, a robot needs to plan its actions while explicitly taking into account the humans and adapt its plans to their whereabouts, capacities and preferences. The first part of this thesis is about human-robot handover: where, when and how to perform them? Depending on the human preferences, it may be better, or not, to share the handover e ort between him and the robot, while in other cases, a unique handover might not be enough to achieve the goal (bringing the object to a target agent) and a sequence of handovers might be needed. In any case, during the handover, a number of cues should be used by both protagonists involved in one handover. One of the most used cue is the gaze. When the giver reaches out with his arm, he should look at the object, and when the motion is finished, he should look at the receiver's face to facilitate the transfer. The handover can be considered as a basic action in a bigger plan, the second part of this thesis reports about a formalization of these kind of basic actions" and more complex ones by the use of conditions, search spaces and restraints. It also reports about a framework and di erent algorithms used to solve and compute these actions based on their description. The last part of the thesis shows how the previously cited framework can fit in with a higher level planner (such as a task planner) and a method to combine a symbolic and geometric planner. The task planner uses external calls to the geometric planner to assess the feasibility of the current task, and in case of success, retrieve the state of the world provided by the geometric reasoner and use it to continue the planning. This part also shows di erent extensions enabling a faster search. Some of these extensions are \Geometric checks" where we test the infeasibility of multiple actions at once, \constraints" where adding constraints at the symbolic level can drive the geometric search, and \cost driven search" where the symbolic planner uses information form the geometric one to prune out over costly plans.

Résumé

Au cours des dernières années, la communauté robotique s'est largement intéressée au domaine de l'interaction homme-robot (HRI). Un des aspects de ce domaine est de faire agir les robots en présence de l'homme, tout en respectant sa sécurité ainsi que son confort. Pour atteindre cet objectif, un robot doit planifier ses actions tout en prenant explicitement en compte les humains afin d'adapter le plan à leurs positions, leurs capacités et leurs préférences. La première partie de cette thèse concerne les transferts d'objets entre humains et robots : où, quand et comment les effectuer? Dépendant des préférences de l'Homme, il est parfois préférable, ou pas, partager l'effort du transfert d'objet entre lui et le robot, mais encore, à certains moments, un seul transfert d'objet n'est pas sufisant pour atteindre l'objectif (amener l'objet à un agent cible), le robot doit alors planifier une séquence de transfert d'objet entre plusieurs agents afin d'arriver à ses fins. Quel que soit le cas, pendant le transfert d'objet, un certain nombre de signaux doivent être échangés par les deux protagonistes afin de réussir l'action. Un des signaux les plus utilisés est le regard. Lorsque le donneur tend le bras afin de transférer l'objet, il doit regarder successivement le receveur puis l'objet afin de faciliter le transfert. Le transfert d'objet peut être considéré comme une action de base dans un plan plus vaste, nous amenant à la seconde partie de cette thèse qui présente une formalization de ce type d'actions de base" et d'actions plus complexes utilisant des conditions, des espaces de recherche et des contraintes. Cette partie rend aussi compte du framework et des différents algorithmes utilisés pour résoudre et calculer ces actions en fonction de leur description. La dernière partie de la thèse montre comment ce framework peut s'adapter à un planificateur de plus haut niveau (un planificateur de tâches par exemple) et une méthode pour combiner la planification symbolique et géométrique. Le planificateur de tâches utilise des appels à des fonctions externes lui permettant de vérifier la faisabilité de la tâche courante, et en cas de succès, de récupérer l'état du monde fourni par le raisonneur géométrique et de l'utilisé afin de poursuivre la planification. Cette partie montre également différentes extensions de cette algorithme, tels que les \validation géométriques" où nous testons l'infaisabilité de plusieurs actions à la fois ou \les contraintes" où l'ajout de contraintes au niveau symbolique peut dirigée la recherche géométrique ou encore \recherche dirigé par coût" où le planificateur symbolique utilise les informations fournies par la partie géométrique afin d'éviter le calcul de plans moins intéressants.

137417
15282
04/06/2015

Modèles et algorithmes pour systèmes multirobots hétérogènes. Application à la patrouille et au suivi de cible

C.ROBIN

RIS

Doctorat : INSA de Toulouse, 4 Juin 2015, 249p., Président: R.ALAMI, Rapporteurs: A EL FALLAH SEGROUCHNI, O.SIMONIN, Examinateurs: V.SERFATY, N.BOURAQUADI, Directeur de thèse: S.LACROIX , N° 15282

Lien : https://tel.archives-ouvertes.fr/tel-01200717

Diffusable

Plus d'informations

Abstract

Detecting, localizing or following targets is at the core of numerous robotic applications in industrial, civilian and military application contexts. Much work has been devoted in various research communities to planning for such problems, each community with a different standpoint. Our thesis first provides a unifying taxonomy to go beyond the frontiers of specific communities and specific problems, and to enlarge the scope of prior surveys. We review various work related to each class of problems identified in the taxonomy, highlighting the different approaches, models and results. This analysis specifically points out the lack of representativity of the exploited models, which are in vast majority only 2D single-layer models where motion and sensing are mixed up. We consider those unrealistic models as too restrictive to handle the full synergistic potential of an heterogeneous team of cooperative robots. In response to this statement, we suggest a new organisation of the necessary models, stating clearly the links and separation between models and planning algorithms. This has lead to the development of a C++ library that structures the available models and defines the requests required by the planning process. We then exploit this library through a set of algorithms tackling area patrolling and target tracking. These algorithms are supported by a sound formalism and we study the impact of the models on the observed performances, with an emphasis on the complexity and the quality of the resulting solutions. As a more general consideration, models are an essential link between Artificial Intelligence and applied Robotics : improving their expressiveness and studying them rigorously are the keys leading toward better robot behaviours and successful robotic missions. This thesis help to show how important the models are for planning and other decision processes for multi-robot missions.

Résumé

La détection et le suivi de cibles sont des missions fréquentes pour la robotique mobile, que le contexte soit civil, industriel ou militaire. Ces applications constituent un domaine de choix pour la planification multirobot, et sont abordées par de multiples communautés selon différents points de vue. Nous proposons dans un premier temps une taxonomie commune qui permet de regrouper et de comparer les différentes approches de ces problèmes, afin de mieux les analyser et de mettre en évidence leurs lacunes respectives. En particulier, on note la faible représentativité des modèles exploités, peu expressifs : la plupart des algorithmes évoluent dans un monde en deux dimensions où les observations et le déplacement sont conditionnés par les mêmes obstacles. Ces modèles éloignés de la réalité nous semblent trop restrictifs pour pleinement exploiter la synergie des équipes multirobot hétérogènes : nous proposons une organisation des différents modèles nécessaires, en explicitant une séparation claire entre modèles et algorithmes de planification. Cette organisation est concrétisée par une librairie qui structure les modèles disponibles et définit les requêtes nécessaires aux algorithmes de planification. Dans un second temps, nous proposons un ensemble d’algorithmes utilisant les modèles définis précédemment pour planifier des missions de patrouille de zones et de poursuite de cibles. Ces algorithmes s’appuient sur un formalisme mathématique rigoureux afin d’étudier l’impact des modèles sur les performances. Nous analysons notamment l’impact sur la complexité – c’est-à-dire en quoi des modèles plus élaborés impactent la complexité de résolution – et sur la qualité des solutions résultantes, indépendamment des modèles, selon des métriques usuelles. D’une manière plus générale, les modèles sont un lien essentiel entre l’Intelligence Artificielle et la Robotique : leur enrichissement et leur étude approfondie permettent d’exhiber des comportements plus efficaces pour la réussite des missions allouées aux robots. Cette thèse contribue à démontrer l’importance des modèles pour la planification et la conduite de mission multirobots.

Mots-Clés / Keywords
Détection de cible; Suivi de cibles; Missions de patrouille; Modèles pour la planification; Multi-robot systems; Target detection; Patrolling; Target tracking; Models for planning; Systèmes multirobots;

135042
14510
10/10/2014

Extensions of sampling-based approaches to path planning in complex cost spaces: applications to robotics and structural biology

D.DEVAURS

RIS

Doctorat : INP de Toulouse, 10 Octobre 2014, 150p., Président: R.ALAMI, Rapporteurs: L.KAVRAKI, F.CAZALS, Examinateurs: S.REDON, T.SIMEON, Directeurs de thèse: J.CORTES , N° 14510

Lien : https://tel.archives-ouvertes.fr/tel-01079963

Diffusable

Plus d'informations

Abstract

Planning a path for a robot in a complex environment is a crucial issue in robotics. So-called probabilistic algorithms for path planning are very successful at solving dicult problems and are applied in various domains, such as aerospace, computer animation, and structural biology. However, these methods have traditionally focused on nding paths avoiding collisions, without considering the quality of these paths. In recent years, new approaches have been developed to generate high-quality paths: in robotics, this can mean nding paths maximizing safety or control; in biology, this means nding motions minimizing the energy variation of a molecule. In this thesis, we propose several extensions of these methods to improve their performance and allow them to solve ever more dicult problems. The applications we present stem from robotics (industrial inspection and aerial manipulation) and structural biology (simulation of molecular motions and exploration of energy landscapes).

Résumé

Planifier le chemin d'un robot dans un environnement complexe est un problème crucial en robotique. Les méthodes de planification probabilistes peuvent résoudre des problèmes complexes aussi bien en robotique, qu'en animation graphique, ou en biologie structurale. En général, ces méthodes produisent un chemin évitant les collisions, sans considérer sa qualité. Récemment, de nouvelles approches ont été créées pour générer des chemins de bonne qualité : en robotique, cela peut être le chemin le plus court ou qui maximise la sécurité ; en biologie, il s'agit du mouvement minimisant la variation énergétique moléculaire. Dans cette thèse, nous proposons plusieurs extensions de ces méthodes, pour améliorer leurs performances et leur permettre de résoudre des problèmes toujours plus dificiles. Les applications que nous présentons viennent de la robotique (inspection industrielle et manipulation aérienne) et de la biologie structurale (mouvement moléculaire et conformations stables).

Mots-Clés / Keywords
Cost space; Robotics; Structural biology; Planification de chemins; Espace de coût; Robotique; Biologie structurale; Path planning;

133525
14614
18/04/2014

Algorithmics of motion: From robotics, through structural biology, toward atomic-scale CAD

J.CORTES

RIS

Habilitation à diriger des recherches : 18 Avril 2014, 150p., Président: R.ALAMI, Rapporteurs: F.CAZALS, S.DONCIEUX, M.NILGES, Examinateurs: O.BROCK, J.P.JESSEL, J.P.LAUMOND, Membre invité: P.MONSAN, Directeurs de thèse: T.SIMEON , N° 14614

Lien : https://tel.archives-ouvertes.fr/tel-01110545

Diffusable

Plus d'informations

Abstract

Algorithmics of motion is a fundamental part of robotics. It deals with the development of methods to compute, simulate and analyze motions of physical systems such as articulated mechanisms or mobile robots. Nevertheless, these methods can be applied to other problems beyond robotics. Indeed, a significant part of my activities are focused on interdisciplinary research in the areas of structural bioinformatics and materials science. My main methodological contributions concern motion planning and simulation algorithms for complex systems. Complexity in this context mainly concerns high-dimensionality together with multiple types of motion constraints, being kinematic loop closure an important class of them. I have also investigated variants of sampling-based motion planning algorithms able to provide good-quality solutions when a cost-function is defined over the space being explored. Parallel implementations of these algorithms have also been studied. In robotics, my research has been mainly focused on problems related to manipulation in the context of several European projects. More recently, I have started to conduct research on aerial robotics. Motion planning for aerial robots involves additional difficulties compared to other classes of robots such as simple wheeled robots or manipulators. Whereas a purely geometric approach is suitable for planning motions of other types of systems that are more easily controllable, aerial robots require to consider dynamics in order to ensure the feasibility of the planned trajectory. Structural bioinformatics and materials science are very interesting areas for the development of methods since they involve extremely challenging problems related to motion. Doubtless, biological macromolecules (such as proteins or RNA) and polymers, at the atomic scale, can be seen as extremely complex mobile systems. The development of methods for modeling/simulating motions of such systems is essential to better understand their physicochemical properties and biological functions. These methods are also of key importance for advances in application areas such as health (e.g. drug design), biotechnology (e.g. engineered enzymes for bio-catalysis) or nanotechnologies (e.g. nucleic acid-based nano-devices).

Mots-Clés / Keywords
Algorithmic motion planning; Structural bioinformatics; Robotics;

133934
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/