Optimal Path Finding in Direction, Location and Time Dependent Environments.

Optimal Path Finding;Dynamic Programming;Time-Dependent Environment;Anisotropic Environment;Path With Bounded Curvature (Dubins Car);Optimal Control;Industrial and Operations Engineering;Engineering;Industrial & Operations Engineering

Dolinskaya, Irina SergeyevnaSun, Jing ;

University of Michigan

关键词: Optimal Path Finding;    Dynamic Programming;    Time-Dependent Environment;    Anisotropic Environment;    Path With Bounded Curvature (Dubins Car);    Optimal Control;    Industrial and Operations Engineering;    Engineering;    Industrial & Operations Engineering;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/64828/dolira_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This dissertation examines optimal path finding problems where cost function and constraints are direction, location and time dependent.Path-finding problems have been studied for decades in various applications; however, the published work introduces numerous assumptions to make the problem more tractable. These assumptions are often so strong as to render the model unrealistic for real life applications. In our research, we relax a number of such restrictive assumptions to create an accurate and yet tractable model suitable for implementation for a large class of problems.We first discuss optimal path finding in an anisotropic (direction-dependent), time and space homogeneous environment. We find a closed form solution for the problems with obstacle-free domain without making any assumptions on the structure of the speed function. We employ our findings to adapt a emph{visibility graph search} method of computational geometry to an anisotropic environment and deliver an optimal obstacle-avoiding path finding algorithm for a direction-dependent medium.Next, we extend our analysis to a set of problems where path curvature is constrained by a direction-dependent minimum turning radius function. We invoke techniques from optimal control theory to demonstrate the problem;;s controllability (by reducing the problem to Dubins car problem), prove existence of an optimal path (via Filippov;;s Theorem), and derive a necessary condition for optimality (using Pontryagin;;s Principle). Further analysis delivers a closed form characterization of an optimal path and presents an algorithm that facilitates the implementation of our results. %the solution of our problem.Finally, the assumption of time and space homogeneity is relaxed, and we develop a dynamic programming model to find an optimal path in a location, direction and time dependent environment. The results for anisotropic homogeneous environment are integrated into the model to improve its accuracy, efficiency and run-time. The path finding model addresses limited information availability, control-feasibility and computational demands of a time-dependent environment.To demonstrate the applicability and performance of our path-finding methods, computational experiments for an optimum vessel performance in evolving wave-field project are presented.