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>

This dissertation focuses on the path planning of unmanned aerial vehicle (UAV) swarms under distributed and hybrid control scenarios. It presents two such models and analyzes them both from theory and practice. In the first method, a distributed formation control strategy for UAV swarm based on consensus law is presented. This model makes use of the fundamental concepts of leader-follower structure, social potential functions, and algebraic graph theory to jointly address flocking and de-confliction in the formation control problem. The impact of network topology on formation control is analyzed. It is shown that the degree distribution of the network representing the multi-agent system defines the rate at which formation is attained. Conditions for convergence and stability are derived. In the second method, a hybrid framework for path planning and coverage area by UAV swarms is presented. This strategy significantly improves the current labor-intensive and resource-constraint operations in aquaculture farms. To monitor the farms periodically, an optimized back-and-forth flight path based on the Shamos algorithm is utilized. A trajectory tracking strategy for UAV swarms under uncertain wind conditions is presented.

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.