The problem with motorized wheelchairs is that they are large, clumsy and difficult to control. This is especially true if the driver has severely reduced capabilities. What we want is a wheelchair that can take instructionsfrom the driver and then based on its understanding of the environment, construct a plan that will take the user to the intended destination. The user should be able to sit in a room, tell the wheelchair that he wants to be in another room and the wheelchair should take him there as quickly and smoothly as possible. The planner presented in this thesis uses a randomized bi-directional tree search. It builds two trees, one from the start state and one from the goal state by randomly sampling the control space of the robot. Each node is a state and each edge is a control input to the robot. In order to decrease the execution time and improve path quality, the planner uses several heuristics to guide the planner. The heuristics are based on Rapidly-exploring Random Trees, Probabilistic Road-maps and the gradient method. For a normal household situation, this planner can construct a decent plan in mere seconds on relatively slow hardware. Most times it finishes in a fraction of a second. This means that the planner has the ability to run in real-time. As a consequence, the planner can handle a dynamic environment, inaccurate sensor readings and an inaccurate physical robot model.

RNA and protein molecules undergo a dynamic folding process that is important to their function. Computational methods are critical for studying this folding pro- cess because it is difficult to observe experimentally. In this work, we introduce new computational techniques to study RNA and protein energy landscapes, includ- ing a method to approximate an RNA energy landscape with a coarse graph (map) and new tools for analyzing graph-based approximations of RNA and protein energy landscapes. These analysis techniques can be used to study RNA and protein fold- ing kinetics such as population kinetics, folding rates, and the folding of particular subsequences. In particular, a map-based Master Equation (MME) method can be used to analyze the population kinetics of the maps, while another map analysis tool, map-based Monte Carlo (MMC) simulation, can extract stochastic folding pathways from the map. To validate the results, I compared our methods with other computational meth- ods and with experimental studies of RNA and protein. I first compared our MMC and MME methods for RNA with other computational methods working on the com- plete energy landscape and show that the approximate map captures the major fea- tures of a much larger (e.g., by orders of magnitude) complete energy landscape. Moreover, I show that the methods scale well to large molecules, e.g., RNA with 200+ nucleotides. Then, I correlate the computational results with experimental findings. I present comparisons with two experimental cases to show how I can pre- dict kinetics-based functional rates of ColE1 RNAII and MS2 phage RNA and their mutants using our MME and MMC tools respectively. I also show that the MME and MMC tools can be applied to map-based approximations of protein energy energy landscapes and present kinetics analysis results for several proteins.

At first glance, robots and proteins have little in common. Robots are commonly thought of as tools that perform tasks such as vacuuming the floor, while proteins play essential roles in many biochemical processes. However, the functionality of both robots and proteins is highly dependent on their motions. In order to study motions in these two divergent domains, the same underlying algorithmic framework can be applied. This method is derived from probabilistic roadmap methods (PRMs) originally developed for robotic motion planning. It builds a graph, or roadmap, where configurations are represented as vertices and transitions between configurations are edges. The contribution of this work is a set of intelligent methods applied to PRMs. These methods facilitate both the modeling and analysis of motions, and have enabled the study of complex and high-dimensional problems in both robotic and molecular domains. In order to efficiently study biologically relevant molecular folding behaviors we have developed new techniques based on Monte Carlo solution, master equation calculation, and non-linear dimensionality reduction to run simulations and analysis on the roadmap. The first method, Map-based master equation calculation (MME), extracts global properties of the folding landscape such as global folding rates. On the other hand, another method, Map-based Monte Carlo solution (MMC), can be used to extract microscopic features of the folding process. Also, the application of dimensionality reduction returns a lower-dimensional representation that still retains the principal features while facilitating both modeling and analysis of motion landscapes. A key contribution of our methods is the flexibility to study larger and more complex structures, e.g., 372 residue Alpha-1 antitrypsin and 200 nucleotide ColE1 RNAII. We also applied intelligent roadmap-based techniques to the area of robotic motion. These methods take advantage of unsupervised learning methods at all stages of the planning process and produces solutions in complex spaces with little cost and less manual intervention compared to other adaptive methods. Our results show that our methods have low overhead and that they out-perform two existing adaptive methods in all complex cases studied.

Mobile robots are used on many areas and its demand on extreme terrain, hazardous area, or life-threatening place is increasing to reduce the loss of life. A good decision making capability is essential for successful navigation of autonomous robot and it affect finding the shortest or optimal path within given condition. The wavefront algorithm is simple to apply, yet yield an optimal path for a robot to follow in many different configurations. Although the path created using wavefront algorithm is an optimal in the sense that every node has the same cost, the result is not the best result in global perspective because of the algorithm is inconsiderate on the surrounding condition. To solve this issue and create the best result on global perspective, risk factor analysis method was implemented on the wavefront algorithm to improve the performance. In this work, the relationship between the wavefront algorithm and dynamic programming will be explained to show that the wavefront algorithm obeys the principle of optimality. The simulation result displays better performance on safety, while keeping the travelling distance minimum, if the risk factor is used on the wavefront algorithm and the robot on actual test behave accordingly. This work will contribute on decision making of mobile robot using risk factor method to create a most desirable and safe path. In addition to that, it will demonstrate how the risk factor method can be applied to the mobile robot navigation.

Robot actuators have physical limitations in how fast they can change their velocity. The more accurately planning algorithms consider these limitations, the better the robot is able to perform. Sampling-based algorithms have been successful in geometric domains, which ignore actuator limitations. They are simple, parameter-free, probabilistically complete and fast. Even though some algorithms like RRTs were specifically designed for kinodynamic problems, which take actuator limitations into account, they are less efficient in these domains or are, as we show, not probabilistically complete. A common approach to this problem is to decompose it, first planning a geometric path and then time-parameterizing it such that actuator constraints are satisfied. We improve the reliability of the latter step. However, the decomposition approach can neither deal with non-zero start or goal velocities nor provides an optimal solution. We demonstrate that sampling-based algorithms can be extended to consider actuator limitations in the form of acceleration limits while retaining the same advantageous properties as in geometric domains. We present an asymptotically optimal planner by combining a steering method with the RRT* algorithm. In addition, we present hierarchical rejection sampling to improve the efficiency of informed kinodynamic planning in high-dimensional spaces.

Maneuvering through 3D structures nimbly is pivotal to the advancement of legged locomotion. However, few methods have been developed that can generate 3D gaits in those terrains and fewer if none can be generalized to control dynamic maneuvers. In this thesis, foot placement planning for dynamic locomotion traversing irregular terrains is explored in three dimensional space. Given boundary values of the center of mass' apexes during the gait, sagittal and lateral Phase Plane trajectories are predicted based on multi-contact and inverted pendulum dynamics. To deal with the nonlinear dynamics of the contact motions and their dimensionality, we plan a geometric surface of motion beforehand and rely on numerical integration to solve the models. In particular, we combine multi-contact and prismatic inverted pendulum models to resolve feet transitions between steps, allowing to produce trajectory patterns similar to those observed in human locomotion. Our contributions lay in the following points: (1) the introduction of non planar surfaces to characterize the center of mass' geometric behavior; (2) an automatic gait planner that simultaneously resolves sagittal and lateral feet placements; (3) the introduction of multi-contact dynamics to smoothly transition between steps in the rough terrains. Data driven methods are powerful approaches in absence of accurate models. These methods rely on experimental data for trajectory regression and prediction. Here, we use regression tools to plan dynamic locomotion in the Phase Space of the robot's center of mass and we develop nonlinear controllers to accomplish the desired plans with accuracy and robustness. In real robotic systems, sensor noise, simplified models and external disturbances contribute to dramatic deviations of the actual closed loop dynamics with respect to the desired ones. Moreover, coming up with dynamic locomotion plans for bipedal robots and in all terrains is an unsolved problem. To tackle these challenges we propose here two robust mechanisms: support vector regression for data driven model fitting and contact planning, and trajectory based sliding mode control for accuracy and robustness. First, support vector regression is utilized to learn the data set obtained through numerical simulations, providing an analytical solution to the nonlinear locomotion dynamics. To approximate typical Phase Plane behaviors that contain infinite slopes and loops, we propose to use implicit fitting functions for the regression. Compared to mainstream explicit fitting methods, our regression method has several key advantages: 1) it models high dimensional Phase Space states by a single unified implicit function; 2) it avoids trajectory over-fitting; 3) it guarantees robustness to noisy data. Finally, based on our regression models, we develop contact switching plans and robust controllers that guarantee convergence to the desired trajectories. Overall, our methods are more robust and capable of learning complex trajectories than traditional regression methods and can be easily utilized to develop trajectory based robust controllers for locomotion. Various case studies are analyzed to validate the effectiveness of our methods including single and multi step planning in a numerical simulation and swing foot trajectory control on our Hume bipedal robot. / text

Η δημιουργία αυτόνομων ρομπότ (είτε οχημάτων ή αρθρωτών ρομπότ) έχει προσελκύσει το ενδιαφέρον πολλών ερευνητών που ασχολούνται με το αντικείμενο της ρομποτικής. Τα ρομπότ πρέπει να είναι ικανά να δέχονται υψηλού-επιπέδου οδηγίες για την εργασία τους και να την εκτελούν (με το μικρότερο δυνατόν κόστος) παίρνοντας μόνα τους αποφάσεις καθώς κινούνται με ασφάλεια στο χώρο εργασίας τους. Οι οδηγίες θα καθορίζουν τι πρέπει να κάνουν χωρίς να ορίζουν το τρόπο που θα το κάνουν. Αναγνωρίζοντας ότι η εκτέλεση οποιασδήποτε εργασίας από ένα ή περισσότερα ρομπότ είναι μια ακολουθία από διαδοχικές κινήσεις στο χώρο εργασίας τους, το ελάχιστο που μπορεί κάποιος να περιμένει από ένα ρομπότ είναι η ικανότητα δημιουργίας της διαδρομής που πρέπει να ακολουθήσει για να εκτελέσει τις απαιτούμενες εργασίες. Αντικείμενο της παρούσας διατριβής είναι η μελέτη και η επίλυση του προβλήματος σχεδιασμού κίνησης για ένα ή περισσότερα ρομπότ (είτε οχημάτων ή βραχιόνων) τα οποία καλούνται να εκτελέσουν μια σειρά από εργασίες. Αρκετές βασικές βιομηχανικές και μη εφαρμογές όπως παραλαβή και παράδοση προϊόντων, συνεχής συγκόλληση, καθαρισμός κτιρίων κτλ, απαιτούν την ομαλή κίνηση του ρομπότ στο χώρο εργασίας του. Το ρομπότ θα πρέπει να αποφεύγει κινούμενα ή ακίνητα εμπόδια ή ακόμη και άλλα ρομπότ τα οποία μπορεί να εργάζονται στον ίδιο χώρο. Η δυσκολία του προβλήματος εξαρτάται από: τη γεωμετρία (πολυπλοκότητα) του περιβάλλοντος, τη διάσταση του χώρου εργασίας, τη διάσταση του ρομπότ και τους κινηματικούς περιορισμούς του ρομπότ. Αρχικά, έγινε η γενίκευση της Bump-Surface καθώς επίσης και το μαθηματικό της μοντέλο για την αντιμετώπιση του προβλήματος ΣΚΡ σε πολυδιάστατους χώρους. Με την χρήση της γενικευμένης Bump-Surface, οι ιδιότητες του χώρου εργασίας στον οποίο κινείται το ρομπότ μεταφέρονται στην επιφάνεια η οποία κατασκευάζεται χρησιμοποιώντας γενικευμένες B-Spline επιφάνειες. Η διαδρομή του κινούμενου αντικειμένου παριστάνεται στο αρχικό περιβάλλον με μια B-Spline καμπύλη. Ο βασικός στόχος ήταν η ανάπτυξη μιας ενιαίας και ολοκληρωμένης μεθοδολογίας για τον σχεδιασμό κίνησης ρομπότ. Με τον τρόπο αυτό συμβάλλουμε στην εξέλιξη των μεθόδων, σχεδιασμού κίνησης ρομπότ εισάγοντας μια μεθοδολογία η οποία θα μπορεί να επίλυση το πρόβλημα σχεδιασμού κίνησης μεταβάλλοντας την διάσταση του χώρου εργασίας και προσθαφαιρώντας κριτήρια και περιορισμούς ανάλογα με το πρόβλημα που θα έχουμε να αντιμετωπίσουμε. Έγινε διερεύνηση, της εξάρτησης του υπολογιστικού χρόνου που απαιτείται για την κατασκευή της γενικευμένης Bump-Surface από την διάσταση και την γεωμετρία του χώρου εργασίας και της εξάρτησης του υπολογιστικού χρόνου που απαιτείται για την επίλυση του προβλήματος ΣΚΡ όταν διατηρείται η γεωμετρία του περιβάλλοντος σταθερή και μεταβάλλεται ο αριθμός των ρομπότ που κινούνται στο χώρο εργασίας. Σε αντίθεση με τις προηγούμενες μεθόδους επίλυσης του προβλήματος σχεδιασμού κίνησης μη-ολονομικών ρομπότ οι οποίες έλυναν το πρόβλημα σε δύο στάδια: (α) προσδιορισμός της βέλτιστης διαδρομής του ρομπότ θεωρώντας το ρομπότ σημειακό (β) τροποποιούν τη διαδρομή λαμβάνοντας υπόψη τη διάσταση του και τους μη-ολονομικούς περιορισμούς του ρομπότ. Στη παρούσα διατριβή, προτάθηκε ένας ενιαίος τρόπος αντιμετώπισης του προβλήματος σχεδιασμού κίνησης μη-ολονομικών ρομπότ όπου τόσο η διάσταση του ρομπότ όσο και οι μη-ολονομικοί περιορισμοί στη κίνηση του λαμβάνονται υπόψη εξ’ αρχής στη διαδικασία εύρεσης της διαδρομής. Επίσης, επιλύθηκε για πρώτη φορά το πρόβλημα σχεδιασμού κίνησης για μια ομάδα ρομπότ με την ταυτόχρονη εύρεση της βέλτιστης διαδρομής για κάθε ένα ρομπότ. Τέλος, η προτεινόμενη μεθοδολογία εφαρμόστηκε με επιτυχία στο συνδυαστικό πρόβλημα ΣΚΡ και προγραμματισμού εργασιών για αυτόνομο όχημα. Λόγω της πολυπλοκότητας των δύο προβλημάτων δεν είχαν προταθεί μέχρι τώρα μέθοδοι για την ταυτόχρονη επίλυση τους. / Developing autonomous robots (either mobile or articulated robots) is a fundamental goal in modern industrial production systems and has attracted the attention of many researchers from the robotics fields. The robots must be able to accept high-level instructions of their missions and carry out these missions (at the lowest cost) by making their own decisions while moving safely in the shop floor. Such vehicles will be capable to accept high level descriptions of desired tasks and execute them without any human intervention. The theme of this thesis is the study and the solution of the motion planning problem either for one robot or for a set of robots (mobile or articulated robots). Most of the industrial applications such as pickup and delivery of products, spot-welding, multiple drilling, laser cutting and car-painting, they demand the smooth motion of the robot (or the robots) in the workspace. Each robot should be able to avoid the obstacles (static or moving) or the other robots. The complexity of the problem is depended by the geometry of the environment, the dimension of the robots’ workspace and by the robots’ kinematical constraints. Firstly, the generalization of the Bump-Surface concept for the solution of the motion planning problem in multidimensional workspaces is presented. Using the generalized Bump-Surface concept, the properties of the workspace are transferred into the surface which is constructed by B-Spline Surfaces. The robot’s path is represented by a B-Spline curve in the initial environment. The main target was the development of a methodology which is able to solve the basic motion planning problem and its generalizations. Secondly, is presented the computational time study required to construct the generalized Bump-surface depends only on the geometry and on the dimension of the environment. Furthermore, is presented the computational time required to solve the motion planning problem with constant workspace and varying number of robots. In contract with previous methods which are solved the motion planning problem for non-holonomic robots in two phases, in the present thesis is presented a solution of the problem under a global way with the capacity to handle either holonomic or non-holonomic robot (or a set of robots) moving in a dynamic 2D environment. Furthermore, is presented for a first time the solution of the combinatorial problem of motion planning and task scheduling for a set of robots.

Motion planning is an increasingly important field of research. Factory automation is becoming more prevalent and at the same time, production runs are shortening in the name of customisation. With computer controlled equipment becoming cheaper and more modular, setting up near-fully automated production lines is becoming fast and easy. This means that the actual programming of the robots and assembly system is becoming the rate determining step. Automated motion planning is a possible solution to this—but only if it can run fast enough. Many heuristic planners have been created in an attempt to achieve the necessary speeds in off-line (or more ambitiously, on-line) processing. This thesis aims to show that different types of heuristic planners can be designed to take advantage of specialised environments or robot characteristics. To show this, three distinct classes of heuristic planners are put forward for discussion. The first of these classes, addressed in Chapter 2, is of very generic planners which will work in virtually all situations (ie. almost any combination of robot and environment). This generality is obviously useful when lacking more specific domain knowledge. However these methods do suffer performance-wise in comparison with more specialised planners when there are characteristics of the problem which can be targeted. Chapter 3 moves to planners which are designed to specifically address certain peculiarities of the environment. Particular focus is given to environments whose corresponding configuration-spaces contain narrow gaps and passages. Finally Chapter 4 addresses a third class of planners: those which are designed for specific types of robots and movements. The particular focus is on locomotion for legged vehicles. For each of these three classes, some discussion is made of existing planners which can be so characterised. In addition, a novel algorithm is introduced in each as an example for particular consideration.

Industrial robots rapidly gained popularity as they can perform tasks quickly, repeatedly and accurately in static environments. However, in modern manufacturing, robots should also be able to safely interact with arbitrary objects and dynamically adapt their behavior to various situations. The large masses and rigid constructions of industrial robots prevent them from easily being re-tasked. In this context, this work proposes an immediate solution to make rigid manipulators compliant and able to efficiently handle object interactions, with only an add-on module (a custom designed instrumented compliant wrist) and an original control framework which can easily be ported to different manipulators. The proposed system utilizes both offline and online trajectory planning to achieve fully automated object interaction and surface following with or without contact where no prior knowledge of the objects is available. To minimize the complexity of the task, the problem is formulated into four interaction motion modes: free, proximity, contact and a blend of those. The free motion mode guides the robot towards the object of interest using information provided by a RGB-D sensor. The RGB-D sensor is used to collect raw 3D information on the environment and construct an approximate 3D model of an object of interest in the scene. In order to completely explore the object, a novel coverage path planning technique is proposed to generate a primary (offline) trajectory. However, RGB-D sensors provide only limited accuracy on the depth measurements and create blind spot when it reaches close to surfaces. Therefore, the offline trajectory is then further refined by applying the proximity motion mode and contact motion mode or a blend of them (blend motion mode) that allow the robot to dynamically interact with arbitrary objects and adapt to the surfaces it approaches or touches using live proximity and contact feedback from the compliant wrist. To achieve seamless and efficient integration of the sensory information and smoothly switch between different interaction modes, an original hybrid switching scheme is proposed that applies a supervisory (decision making) module and a mixture of hard and blend switches to support data fusion from multiple sensing sources by combining pairs of the main motion modes. Experimental results using a CRS-F3 manipulator demonstrate the feasibility and performance of the proposed method.

Le chapitre 1 est pour l'essentiel une brève introduction générale qui donne le contexte générale de la planification et présente l'organisation du document dans son ensemble et quelques uns des points clés retenus : robot humanoïde, environnement non statique, perception par vision artificielle, et représentation de cet environnement par grilles d'occupation. Dans le chapitre 2, après une revue de littérature bien menée, l'auteur propose de considérer les points de repère de l'environnement dès la phase de planification de chemin afin de rendre plus robuste l'exécution des déplacements en cas d'évolution de l'environnement entre le moment où la planification est menée et celui où le robot se déplace ( évolution étant entendu comme liée à une amélioration de la connaissance par mise à jour, ou due à un changement de l'environnement lui-même). Le concept est décrit et une formalisation proposée. Le chapitre 3 s'intéresse en détail à la planification dans le cas d'environnements dynamiques. Les méthodes existantes, nombreuses, sont tout d'abord analysées et bien présentées. Le choix est fait ici de décrire l'environnement comme étant décomposé en cellules, regroupant elles-mêmes des voxels, éléments atomiques de la représentation. L'environnement étant changeant, l'auteur propose de réévaluer le plan préétabli à partir d'une bonne détection de la zone qui a pu se trouver modifiée dans l'environnement. L'approche est validée expérimentalement en utilisant une des plateformes robotiques du LAAS qui dispose de bonnes capacités de localisation : le manipulateur mobile Jido étant à ce jour plus performant sur ce plan que l'humanoïde HRP2, c'est lui qui a été utilisé. Ces expérimentations donnent des indications concordantes sur l'efficacité de l'approche retenue. Notons également que la planification s'appuie sur une boite englobante de l'humanoïde, et non pas sur une représentation plus riche (multi-degré-deliberté). En revanche, c'est bien de planification pour l'humanoïde considéré dans toute sa complexité qu'il s'agit au chapitre 4 : on s'intéresse ici à tous les degrés de liberté du robot. L'auteur propose des évolutions de méthodes existantes et en particulier sur la manière de tirer profit de la redondance cinématique. L'approche est bien décrite et permet d'inclure une phase d'optimisation de la posture globale du robot. Des exemples illustrent le propos et sont l'occasion de comparaison avec d'autres méthodes. Le chapitre 5 s'intéresse à la manière de modéliser l'environnement, sachant qu'on s'intéresse ici au cas d'une perception par vision artificielle, et précisément au cas de l'humanoïde, robot d'assurer lui-même cette perception au fur et à mesure de son avancée dans l'environnement. On est donc dans le cadre de la recherche de la meilleure vue suivante qui doit permettre d'enrichir au mieux la connaissance qu'a le robot de son environnement. L'approche retenue fait à nouveau appel à la boite englobante de l'humanoïde et non à sa représentation complète ; il sera intéressant de voir dans le futur ce que pourrait apporter la prise en compte des degrés de liberté de la tête ou du torse à la résolution de ce problème. Le chapitre 6 décrit la phase d'intégration de tous ces travaux sur la plateforme HRP2 du LAAS-CNRS, partie importante de tout travail de roboticien. / This thesis starts by proposing a new framework for motion planning using stochastic maps, such as occupancy-grid maps. In autonomous robotics applications, the robot's map of the environment is typically constructed online, using techniques from SLAM. These methods can construct a dense map of the environment, or a sparse map that contains a set of identifiable landmarks. In this situation, path planning would be performed using the dense map, and the path would be executed in a sensor-based fashion, using feedback control to track the reference path based on sensor information regarding landmark position. Maximum-likelihood estimation techniques are used to model the sensing process as well as to estimate the most likely nominal path that will be followed by the robot during execution of the plan. The proposed approach is potentially a practical way to plan under the specific sorts of uncertainty confronted by a humanoid robot. The next chapter, presents methods for constructing free paths in dynamic environments. The chapter begins with a comprehensive review of past methods, ranging from modifying sampling-based methods for the dynamic obstacle problem, to methods that were specifically designed for this problem. The thesis proposes to adapt a method reported originally by Leven et al.. so that it can be used to plan paths for humanoid robots in dynamic environments. The basic idea of this method is to construct a mapping from voxels in a discretized representation of the workspace to vertices and arcs in a configuration space network built using sampling-based planning methods. When an obstacle intersects a voxel in the workspace, the corresponding nodes and arcs in the configuration space roadmap are marked as invalid. The part of the network that remains comprises the set of valid candidate paths. The specific approach described here extends previous work by imposing a two-level hierarchical structure on the representation of the workspace. The methods described in Chapters 2 and 3 essentially deal with low-dimensional problems (e.g., moving a bounding box). The reduction in dimensionality is essential, since the path planning problem confronted in these chapters is complicated by uncertainty and dynamic obstacles, respectively. Chapter 4 addresses the problem of planning the full motion of a humanoid robot (whole-body task planning). The approach presented here is essentially a four-step approach. First, multiple viable goal configurations are generated using a local task solver, and these are used in a classical path planning approach with one initial condition and multiple goals. This classical problem is solved using an RRT-based method. Once a path is found, optimization methods are applied to the goal posture. Finally, classic path optimization algorithms are applied to the solution path and posture optimization. The fifth chapter describes algorithms for building a representation of the environment using stereo vision as the sensing modality. Such algorithms are necessary components of the autonomous system proposed in the first chapter of the thesis. A simple occupancy-grid based method is proposed, in which each voxel in the grid is assigned a number indicating the probability that it is occupied. The representation is updated during execution based on values received from the sensing system. The sensor model used is a simple Gaussian observation model in which measured distance is assumed to be true distance plus additive Gaussian noise. Sequential Bayes updating is then used to incrementally update occupancy values as new measurements are received. Finally, chapter 6 provides some details about the overall system architecture, and in particular, about those components of the architecture that have been taken from existing software (and therefore, do not themselves represent contributions of the thesis). Several software systems are described, including GIK, WorldModelGrid3D, HppDynamicObstacle, and GenoM.