Spelling suggestions: "subject:"path finding"" "subject:"math finding""
1 |
NavNets: 3D Path-planning systemGwosdz, Thomas January 2019 (has links)
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)
|
2 |
3D navigace pro mobilní roboty / 3D Navigation for Mobile RobotsŠkoda, Jan January 2017 (has links)
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)
|
3 |
Řešící algoritmy pro multi-agentní hledání cest s dynamickými překážkami / Solving Algorithms for Multi-agent Path Planning with Dynamic ObstaclesMajerech, Ondřej January 2017 (has links)
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
|
4 |
Inteligentní křižovatka / Smart Traffic IntersectionŠkopková, Věra January 2019 (has links)
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.
|
5 |
Crowd Navigation : Autonomous navigation in an urban environment / Navigering i folkmassor : Autonom navigering i stadsmiljöFreider, Elias January 2015 (has links)
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.
|
6 |
New Transition State Optimization and Reaction Path Finding Algorithm with Reduced Internal CoordinatesYang, Xiaotian January 2021 (has links)
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)
|
7 |
Kooperativní hledání cest s protivníkem / Kooperativní hledání cest s protivníkemIvanová, Marika January 2014 (has links)
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)
|
8 |
Formation Preserving Navigation Of Agent Teams In 3-d TerrainsBayrak, Ali Galip 01 August 2008 (has links) (PDF)
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.
|
9 |
Multiresolution Formation Preserving Path Planning In 3-d Virtual EnvironmentsHosgor, Can 01 September 2011 (has links) (PDF)
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.
|
10 |
Intelligent Tourist Information SystemJeleń, Krzysztof January 2008 (has links)
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.
|
Page generated in 0.0652 seconds