A Study Of Mobile Robot Path Planning For Stationary And Moving Obstacles Using An Efficient Search Strategy PDF Download

Abstract: Given growing emphasis on robot autonomy, the problem of planning a trajectory for these autonomous systems in a complex environment has become increasingly important. The objective of this research is to solve trajectory generation and optimization problems for mobile robot systems with both single and multiple goals. Considering the complexity of general trajectory planning problems, we concentrate mainly on two dynamic models: a holonomic system where velocity is a control variable and a nonholonomic system proposed by Dubins with constant velocity and constrained turning radius. For the simple holonomic model, we focus on computation of optimal trajectories with complex objective functions. We use a stochastic control framework to obtain characterizations of optimal trajectories as solutions of Hamilton-Jacobi-Bellman equations. Based on either upwind schemes or value iteration methods, we develop and evaluate alternative numerical methods for both isotropic (velocity-independent) and anisotropic (velocity-dependent) cost models. For the Dubins' vehicle model, we extend the results of Dubins and others to solve for minimum-time trajectories with diverse path and terminal constraints, characterizing solutions using Pontryagin's Maximum Principle. A direct application of these local shortest-path solutions is the Dubins' Traveling Salesman problem (DTSP), where the goal is to find the shortest trajectory for a Dubins' vehicle given a number of locations. We extend our analytic solutions to two-point and three-point Dubins' shortest path problems to obtain a receding horizon algorithm that outperforms alternative algorithms proposed in the literature when the visiting order is known. We also combine these algorithms with existing TSP heuristics to obtain improved algorithms when the order is not known. We also studied trajectory planning for Dubins' vehicles in the presence of moving obstacles. For stationary obstacles and holonomic vehicles, probabilistic algorithms such as rapidly-exploring random trees (RRTs) can provide guarantees of finding a path to a goal. We developed a variation of RRTs for time-varying obstacles and Dubins' dynamics. We prove probabilistic completeness for this algorithm, establishing that a path will be found if one exists. We also compared our approach with an alternative, the probabilistic roadmap algorithm, and established that our algorithm yields improvements for these problems.