The current state of 3D path-planning leaves room for improvement. To navigate a 3D environment, techniques which were developed for 2D navigation are used and slightly adapted to generate convincing motion. However, these techniques often constrict the motion to a single plane. This constriction is not only a limitation, but also increases the error. We created a new method to compute a path in a 3D world without a planar constraint. We will discuss the computation of a Navigation Volume Network (NavNet), and how it finds a path. A NavNet is the 3D generalization of NavMeshes, and holds boundary and connection information which is utilized when planning a path for motion. Similar to how NavMeshes allow path-planning by simplifying the ground meshes, the NavNet simplifies the search space by approximating the 3D world through sampling. / Thesis / Master of Applied Science (MASc)

We propose a novel 3D navigation system for autonomous vehicle path-planning. The system processes a point-cloud data from an rgb-d camera and creates a 3D occupancy grid with adaptable cell size. Occupied grid cells contain normal distribution characterizing the data measured in the area of the cell. The normal distributions are then used for cell classification, traversability and collision checking. The space of traversable cells is then used for path-planning. The ability to work in three-dimensional space allows the usage of autonomous robots in highly structured environments with multiple levels, uneven surface or various elevated and underground crossings. That is important for the usage of robots in real- world scenarios, in urban areas or for disaster rescue missions. Powered by TCPDF (www.tcpdf.org)

In this work we present the problem of multi-agent path-finding with dynamic obstacles, a generalisation of multi-agent path-finding (MAPF) in which the environment contains randomly-moving dynamic obstacles. This generalisation can be though of as an abstraction of incomplete knowledge of the environment or as a simplification of the multi-agent path-finding where we do not include all agents in the cooperative planner. We adapt three planning algorithms for MAPF to work in an environment with dy- namic obstacles: Local-Repair A* (LRA*), Windowed Hierarchical Cooper- ative A* (WHCA*) and Operator Decomposition with Independence Detec- tion (OD/ID). In addition, we propose two heuristics for these algorithms in dynamic environments: Path Rejoining and Obstacle Predictor. In our experiments, we find that LRA* and WHCA* are best suited for the dy- namic environment. The Path Rejoining heuristic is successful in improving run-times at a small cost in makespan. Obstacle Prediction is capable of lowering the number of times a plan has to be found, but the overhead of our implementation outweighs any performance benefits in most cases. 1

This thesis is concerned with the problem of planning paths for autonomous cars through a smart traffic intersection. In this thesis, we describe existing concepts for solving this problem and discuss the possibilities of approaching intersection problems theoretically. Then, we choose one specific approach and design a declarative model for solving the problem. We use that model to perform a series of theoretical experiments to test the throughput and the quality of intersection paths described by different graphs. After that, we translate theoretical plans to actions for real robots and run it. In these experiments, we measure the degree of robots desynchronization and performance success of the plans based on the collision rate. We also describe how to improve action translation to achieve better performance than that for real robots following the straightforward plans.

In this thesis, strategies for navigating a crowded area using an autonomous holonomic robot are discussed and evaluated. The focus is set on path planning and the topic is therefore largely decoupled from the prediction (i.e. machine learning) and control theory techniques needed for a practical implementation outside of the simulated environment. Existing methods and algorithms for path planning in highly dynamic environments are compared using several measures via computer simulations in different environments. A new, effective, and yet simple, algorithm is introduced and proven to be useful in certain scenarios. This algorithm, ART, predicts the future states of the crowd and using these predictions finds better paths to the goal than traditional algorithms. / I detta examensarbete utvärderas och diskuteras strategier för navigering bland folk med hjälp av en självstyrd holonomisk robot. Fokus är satt på navigeringsproblemet i sig och närliggande ämnen som maskininlärning och reglerteknik behandlas ej även om en fördjupning på dessa områden vore nödvändigt för en praktisk implementation utanför den simulerade världen. Existerande strategier och algoritmer för navigering av dynamiska miljöer utvärderas genom datorsimuleringar i varierande miljöer. En ny algorithm presenteras och visar sig vara användbar i vissa situationer. Denna algoritm, ART, förutser folkmassans rörelser och använder denna information för att hitta bättre vägar till målet.

Geometry optimization is a fundamental step in the numerical modelling of chemical reactions. Many thermodynamic and kinetic properties are closely related to the structure of the reactant, product, and the transition states connecting them. Different from the reaction and product, which are local minima on the potential energy surface, a transition state is the first-order saddle point with only one negative curvature. Over years, many methods have been devised to tackle the problem. Locating stable structures is relatively easy with a reliable algorithm and high accuracy. One can follow the gradient descent direction to pursuit the local minimum until convergence is reached. But for the transition state, the determination is more challenging as either the up-hill or down-hill direction is allowed in the process. Motivated by the difficulty, many well-designed optimization algorithms are elaborated specifically to stress the problem. The performance of geometry optimization is affected by various aspects: the initial guess structure, the coordinate system representing the molecule, the accuracy of the initial Hessian matrix, the Hessian update schemes, and the step-size control of each iteration. In this thesis, we propose a new geometry optimization algorithm considering all the important components. More specifically, in Chapter 2, a new set of robust dihedral and redundant internal coordinates is introduced to effectively represent the molecular structures, as well as a computational efficient transformation method to generate a guess structure. In Chapter 3 and 5, a sophisticated robust algorithm is presented and tested to solve intricate transition state optimization problems. In Chapter 4, a new algorithm to exploring reaction pathways based on redundant internal coordinates is illustrated with real chemical reactions. Last but not least, in Chapter 6, a systematic test to explore the optimal methods in each procedure is presented. A well-performed combination of optimization methods is drawn for generic optimization purposes. All the methods and algorithms introduced in this thesis is included in our forth-coming open-source Python package named GOpt. It's a general-purpose library that can work in conjunction with major quantum chemistry software including Gaussian. More features are under development and await to be released in the coming update. / Thesis / Doctor of Science (PhD)

Presented master thesis defines and investigates Adversarial Cooperative Path-finding problem (ACPF), a generalization of standard Cooperative Path-finding. In addition to the Cooperative path- finding where non-colliding paths for multiple agents connecting their initial positions and destinations are searched, consideration of agents controlled by the adversary is included in ACPF. This work is focused on both theoretical properties and practical solving techniques of the considered problem. ACPF is introduced formally using terms from graph theory. We study computational complexity of the problem where we show that the problem is PSPACE-hard and belongs to EXPTIME complexity class. We introduce and discuss possible methods suitable for practical solving of the problem. Considered solving approaches include greedy algorithms, minimax methods, Monte Carlo Tree Search and adaptation of algorithm for the cooperative version of the problem. Surprisingly frequent success rate of greedy methods and rather weaker results of Monte Carlo Tree Search are indicated by the conducted experimental evaluation. Powered by TCPDF (www.tcpdf.org)

Navigation of a group of autonomous agents that are needed to maintain a formation is a challenging task which has not been studied much in especially 3-D terrains. This thesis presents a novel approach to collision free path finding of multiple agents preserving a predefined formation in a 3-D terrain. The proposed method could be used in many areas like navigation of semi-automated forces (SAF) at unit level in military simulations and non player characters (NPC) in computer games. The proposed path finding algorithm first computes an optimal path from an initial point to a target point after analyzing the 3-D terrain data from which it constructs a weighted graph. Then, it employs a real-time path finding algorithm specifically designed to realize the navigation of the group from one way point to the successive one on the optimal path generated at the previous stage, preserving the formation and avoiding collision both. A software was developed to test the methods discussed here.

The complexity of the path finding and navigation problem increases when multiple agents are involved and these agents have to maintain a predefined formation while moving on a 3-D terrain. In this thesis, a novel approach for multiresolution formation representation is proposed, that allows hierarchical formations of arbitrary depth to be defined using different referencing schemes. This formation representation approach is then utilized to find and realize a collision free optimal path from an initial location to a goal location on a 3-D terrain, while preserving the formation. The proposed metod first employs a terrain analysis technique that constructs a weighted search graph from height-map data. The graph is used by an off-line search algorithm to find the shortest path. The path is realized by an on-line planner, which guides the formation along the path while avoiding collisions and maintaining the formation. The methods proposed here are easily adaptable to several application areas, especially to real time strategy games and military simulations.

Nowadays people use mobile phones and other mobile devices. Most of us have a small computing device that is always with us. People use it example for calling, as calendar and organizer. Mobile devices with GPS receiver are also used to find paths in navigation. The main disadvantage of those systems is that we have to know places which we want to visit and they usually do not store any usable, valuable information about points of interest except phone numbers and addresses. The main idea of this thesis was to design a system that will run on most of phones and palms and will be helpful when visiting some new places and cities. This system should be able to find a route using user criteria. Those criteria should be simple and natural, like for example: a list of museums, the most famous historical objects, restaurants to visit, constraints to travel by bus and by walking. The system should find a path that fulfils those criteria, show it on screen, show names of objects, some short descriptions and photos of them and possible entrance costs. It should also be able to estimate time needed to travel from one object to the next and if it is possible, advise which bus line or other public means of transport may be used. It should be helpful for people that want to visit a city without having much information about it. Paths that are output of this system are only a proposition for trip. They will not be optimal but can not be counterintuitive and must be acceptable by the user.