This work is dedicated to robot path planning with using principles of dynamic programing in discrete state space. Theoretical part is dedicated to actual situation in this field and to principle of applying Markov decission process to path planning. Practical part is dedicated to implementation of two algorithms based on MDP principles.

This thesis deals with robot path planning by means of graph-based algorithms. The theoretical part contains basic approaches to robot path planning, and pay closer look at various methods of graph-based algorithms. In the second part of this thesis a simulation environment for robot navigation was created in C#. And in this environment chosen methods of graph-based algorithms have been implemented. This thesis was written within the research project MSM 0021630529: Intelligent systems in automation.

This thesis deals with robot path planning by means of ant colony optimization algorithms. The theoretical part of this thesis introduces basics of path planning problematics. The theoretical part either deals with ant algorithms as optimization and path planning tools. The practical part deals with design and implementation of path planning by means of ant algorithms in Java language.

This diploma´s thesis analyzes methods for robot path planning by means of algorithms AO*. The practical part focuses on the implementation of selected methods AO*, which are designed for planning under uncertainty environment. There was created the simulation program in this work. Simulation program enables testing the methods, that were implemented.

Plus de la moitié de la population mondiale vit aujourd’hui en zone urbaine et passe plus de 90 % de son temps à l’intérieur de bâtiments. Cette thèse propose un système, nommé BiMov, de planification automatique de chemin à l’intérieur de bâtiments, basé sur leur maquette numérique (un BIM au format IFC). Le processus consiste à exploiter les caractéristiques sémantiques, géométriques et topologiques des constituants du BIM afin de générer des graphes de navigation possible, en fonction du profil du navigant et de l’état conjoncturel d’accessibilité des espaces et transitions, dans lesquels le plus court chemin d’un point à un autre puisse être déterminé. BiMov s’appuie sur quatre modèles de données (1) un modèle de bâtiment déduit du BIM, qui représente et structure les caractéristiques essentielles du bâtiment en vue de la mobilité intérieure (2) un modèle de navigant à même de représenter ses caractéristiques d’encombrement, ses aptitudes aux déplacements horizontaux et verticaux ainsi que ses habilitations (3) un modèle de calendrier permettant de connaître l’état d’accessibilité des espaces et des transitions (4) un modèle de graphe sur trois niveaux de détails. Le niveau Macro représente un simple graphe de connectivité entre les espaces intérieurs voisins ; il permet aux architectes de vérifier leur conception architecturale en termes d’accessibilité. Le niveau Externe permet de connecter les espaces accessibles via leurs transitions horizontales ou verticales. Il est destiné aux navigants qui n’exigent pas un chemin détaillé pour se déplacer. Le niveau Interne intègre un maillage des espaces, en 2D pour la navigation au sol, en 3D pour la navigation de drones. Il est conçu pour considérer les obstacles intérieurs comme les meubles, les machines ou les équipements. Ce niveau est destiné aux navigants devant fiabiliser leur déplacement à l’intérieur des espaces, comme les manutentionnaires d’objets encombrants ou les robots mobiles. L’approche proposée a fait l’objet d’un développement informatique qui permet d’illustrer quelques scénarios de planification de chemin dans des modèles BIM d’origine externe à la thèse. / More than 50% of humans today live in urban areas and spend more than 90 % of their time indoor. This thesis suggests a system, called BiMov, dedicated to automatic path planning in complex building based on their digital mockup (a BIM in IFC format). The process consists in exploiting the semantic, geometric and topologic features of the constituents of a BIM, so as to generate navigation graphs, taking into account the profile of Navigants as well as the operational state of accessibility of spaces and transitions, for finally determining a shortest path. BiMov is based on 4 data models: (1) a building model deduced from the BIM that represents and structures the building features that are relevant for indoor mobility (2) a Navigant model capable to represent its bulk size, abilities for horizontal and vertical displacements and social habilitations (3) a calendar model representing the conjectural state of accessibility of spaces and transitions (4) a navigation graph model with three levels of detail: the Macro level represents a simple graph of connectivity between neighboring interior spaces. It is intended to help architects verify their architectural design in terms of accessibility. The Extern level is used to connect accessible spaces via their horizontal or vertical transitions. This level is intended for Navigants who do not require a detailed path. The Intern level integrates a meshing of each space: a 2D mesh for planar mobility or a 3D mesh for drones. This level is intended for Navigants like bulky objects handlers of mobile robots, needing to validate a reliable path within spaces containing furniture, machinery or equipment. The proposed approach was implemented in a prototype software that allows to illustrate different path planning scenarios in BIM models that were generated externally.

This thesis deals with the general problem of robot motion planning and control. It proposes the hypothesis that it should bepossible to create a generic software framework capable of dealing with all robot motion planning and control problems, independent of the robot being used, the task being solved, the workspace obstacles or the algorithms employed. The thesis work then consisted of identifying the requirements and creating a design and implementation of such a framework. This report motivates and documents the entire process. The framework developed was tested on two different robot arms under varying conditions. The testing method and results are also presented.The thesis concludes that the proposed hypothesis is indeed valid.

No description available.

The need for faster and more reliable logistics solutions is rapidly increasing. This is due to higher demands on the logistical services to improve quality,  quantity, speed and reduce the error tolerance. An arising solution to these increased demands is automated solutions in warehouses, i.e., automated material  handling. In order to provide a satisfactory solution, the vehicles need to be smart and able to solve unexpected situations without human interaction.  The purpose of this thesis was to investigate if obstacle detection and avoidance in a semi-unknown environment could be achieved based on the data from a 2D LIDAR-scanner. The work was done in cooperation with the development of a new load-handling vehicle at Toyota Material Handling. The vehicle is navigating from a map that is created when the vehicle is introduced to the environment it will be operational within. Therefore, it cannot successfully navigate around new unrepresented obstacles in the map, something that often occurs in a material handling warehouse. The work in this thesis resulted in the implementation of a modified occupancy grid map algorithm, that can create maps of previously unknown environments if the position and orientation of the AGV are known. The generated occupancy grid map could then be utilized in a lattice planner together with the A* planning algorithm to find the shortest path. The performance was tested in different scenarios at a testing facility at Toyota Material Handling.  The results showed that the occupancy grid provided an accurate description of the environment and that the lattice planning provided the shortest path, given constraints on movement and allowed closeness to obstacles. However, some performance enhancement can still be introduced to the system which is further discussed at the end of the report.  The main conclusions of the project are that the proposed solution met the requirements placed upon the application, but could benefit from a more efficient usage of the mapping algorithm combined with more extensive path planning. / <p>Digital framläggning</p>

Robot path planning and dynamic obstacle avoidance are defined as a problem that robots plan a feasible path from a given starting point to a destination point in a nonlinear dynamic environment, and safely bypass dynamic obstacles to the destination with minimal deviation from the trajectory. Path planning is a typical sequential decision-making problem. Dynamic local observable environment requires real-time and adaptive decision-making systems. It is an innovation for the robot to learn the policy directly from demonstration trajectories to adapt to similar state spaces that may appear in the future. We aim to develop a method for directly learning navigation behavior from demonstration trajectories without defining the environment and attention models, by using the concepts of Generative Adversarial Imitation Learning (GAIL) and Sequence Generative Adversarial Network (SeqGAN). The proposed SeqGAIL model in this thesis allows the robot to reproduce the desired behavior in different situations. In which, an adversarial net is established, and the Feature Counts Errors reduction is utilized as the forcing objective for the Generator. The refinement measure is taken to solve the instability problem. In addition, we proposed to use the Rapidly-exploring Random Tree* (RRT*) with pre-trained weights to generate adequate demonstration trajectories in dynamic environment as the training data, and this idea can effectively overcome the difficulty of acquiring huge training data.

This dissertation addresses motion planning, modeling, and feedback control for autonomous vehicle systems. A hierarchical approach for motion planning and control of nonlinear systems operating in obstacle environments is presented. To reduce computation time during the motion planning process, dynamically feasible trajectories are generated in real-time through concatenation of pre-specified motion primitives. The motion planning task is posed as a search over a directed graph, and the applicability of informed graph search techniques is investigated. Specifically, a locally greedy algorithm with effective backtracking ability is developed and compared to weighted A* search. The greedy algorithm shows an advantage with respect to solution cost and computation time when larger motion primitive libraries that do not operate on a regular state lattice are utilized. Linearization of the nonlinear system equations about the motion primitive library results in a hybrid linear time-varying model, and an optimal control algorithm using the L2-induced norm as the performance measure is applied to ensure that the system tracks the desired trajectory. The ability of the resulting controller to closely track the trajectory obtained from the motion planner, despite various disturbances and uncertainties, is demonstrated through simulation. Additionally, an approach for obtaining dynamically feasible reference trajectories and feedback controllers for a small unmanned aerial vehicle (UAV) based on an aerodynamic model derived from flight tests is presented. The modeling approach utilizes the two step method (TSM) with stepwise multiple regression to determine relevant explanatory terms for the aerodynamic models. Dynamically feasible trajectories are then obtained through the solution of an optimal control problem using pseudospectral optimal control software. Discrete-time feedback controllers are then obtained to regulate the vehicle along the desired reference trajectory. Simulations in a realistic operational environment as well as flight testing with the feedback controller demonstrate the capabilities of the approach. The TSM is also applied for system identification of an aircraft using motion capture data. In this application, time domain system identification techniques are used to identify both linear and nonlinear aerodynamic models of large-amplitude pitching motions driven by control surface deflections. The resulting models are assessed based on both their predictive capabilities as well as simulation results. / Ph. D.