Path planning algorithms for mobile robots are concerned with finding a feasible path between a start and goal location in a given environment without hitting obstacles. In the existing literature, important performance metrics for path planning algorithms are the path length, computation time and path safety, which is quantified by the minimum distance of a path from obstacles. The subject of this thesis is the development of path planning algorithms that consist of straight-line segments. Such paths are suitable for omni-directional robots and can as well be used as initial solution paths for applying smoothing. As the main contribution of the thesis, we develop three new planning methodologies that address all of the stated performance metrics. The original idea of the first approach is the pre-processing of the environment map by increasing the obstacle region. That is, when applying sampling-based path planning algorithms such as PRM* (probabilistic roadmap), RRT* (rapidly exploring random tree) or FMT (fast marching tree), node samples in irrelevant regions of the environment are avoided. This measure speeds up the path computation and increases path safety. The second approach proposes the computation of a modified environment map that confines solution paths to the vicinity of the Voronoi boundary of the given environment. Using this modified environment map, we adapt the sampling strategy of the popular path planning algorithms PRM, PRM* and FMT. As a result, we are able to generate solution paths with a reduced computation time and increased path safety. Different from the first two approaches, the third approach uses information about the topology of the environment from the generalized Voronoi diagram of the environment. Specifically, initial solution paths that follow Voronoi edges are iteratively refined by introduce shortcuts and by adding new waypoints to remove corners in the path. The thesis performs comprehensive computational experiments to illustrate the advantages of the proposed approaches. In particular, the third approach proves to be most promising since it addresses the properties of environments for mobile robots.
Path planning algorithms for mobile robots are concerned with finding a feasible path between a start and goal location in a given environment without hitting obstacles. In the existing literature, important performance metrics for path planning algorithms are the path length, computation time and path safety, which is quantified by the minimum distance of a path from obstacles. The subject of this thesis is the development of path planning algorithms that consist of straight-line segments. Such paths are suitable for omni-directional robots and can as well be used as initial solution paths for applying smoothing. As the main contribution of the thesis, we develop three new planning methodologies that address all of the stated performance metrics. The original idea of the first approach is the pre-processing of the environment map by increasing the obstacle region. That is, when applying sampling-based path planning algorithms such as PRM* (probabilistic roadmap), RRT* (rapidly exploring random tree) or FMT (fast marching tree), node samples in irrelevant regions of the environment are avoided. This measure speeds up the path computation and increases path safety. The second approach proposes the computation of a modified environment map that confines solution paths to the vicinity of the Voronoi boundary of the given environment. Using this modified environment map, we adapt the sampling strategy of the popular path planning algorithms PRM, PRM* and FMT. As a result, we are able to generate solution paths with a reduced computation time and increased path safety. Different from the first two approaches, the third approach uses information about the topology of the environment from the generalized Voronoi diagram of the environment. Specifically, initial solution paths that follow Voronoi edges are iteratively refined by introduce shortcuts and by adding new waypoints to remove corners in the path. The thesis performs comprehensive computational experiments to illustrate the advantages of the proposed approaches. In particular, the third approach proves to be most promising since it addresses the properties of environments for mobile robots.
