Voronoi Boundary Visibility for Efficient Path Planning

Download

10.1109:ACCESS.2020.3010819.pdf

Date

2020-01-01

Author

Al-Dahhan, Mohammed Rabeea Hashim
Schmidt, Klaus Verner

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

112
views

170
downloads

The subject of this paper is the computation of paths for mobile robots that navigate from a start position to a goal position in environments with static obstacles. Specifically, we focus on paths that are represented by straight lines. Such paths can for example directly be followed by omni-directional robots or can be used as an initial solution for path smoothing. In this context, the most common performance metrics are the path length, the obstacle clearance and the computation time. In this paper, we develop a new path planning algorithm that addresses all the stated performance metrics. Our method first determines all possible connections between the start position and goal position along the edges of the generalized Voronoi diagram (GVD) of a given obstacle map. The shortest connections are then refined using a balanced method for creating shortcuts along existing waypoints and introducing new waypoints in order to cut corners. As an important feature, our method reduces the number of required waypoints by iteratively adding new waypoints and then removing unnecessary waypoints along solution paths. Moreover, our method takes into account multiple start-goal connections, since the shortest start-goal connection along the edges of the GVD might not lead to the shortest solution path. A comprehensive computational evaluation for a large number of maps with different properties shows that the proposed method outperforms sampling-based algorithms such as Probabilistic Roadmaps (PRM) and exact methods such as Visibility Graphs (VG) by computing close-to-optimal solution paths with a specified minimum obstacle clearance in less time.

Subject Keywords

General Engineering, General Materials Science, General Computer Science, Path planning, Mobile robots, Measurement, Safety, Navigation, Shape, Obstacles, Voronoi diagram

URI

https://hdl.handle.net/11511/39619

Journal

IEEE ACCESS

DOI

https://doi.org/10.1109/access.2020.3010819

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

Safe and Efficient Path Planning for Omni-directional Robots using an Inflated Voronoi Boundary Aldahhan, Mohammed Rabeea Hashim; Schmidt, Klaus Verner (2019-11-01) 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 paper is the development of path planning algorithms for omni-directional robots, which have the ability ...
A unifying grid approach for solving potential flows applicable to structured and unstructured grid configurations Cete, A. Ruhsen; Yuekselen, M. Adil; Kaynak, Uenver (Elsevier BV, 2008-01-01) In this study, an efficient numerical method is proposed for unifying the structured and unstructured grid approaches for solving the potential flows. The new method, named as the "alternating cell directions implicit - ACDI", solves for the structured and unstructured grid configurations equally well. The new method in effect applies a line implicit method similar to the Line Gauss Seidel scheme for complex unstructured grids including mixed type quadrilateral and triangle cells. To this end, designated al...
girdap: Open source object-oriented autonomous grid management library for solving equations of conservation laws Uzgoren, Eray (Elsevier BV, 2017-10-12) girdap is an object-oriented grid generation and management library that uses finite volume operator objects to provide researchers and educators a framework to solve different sets of algebraic and differential equations on multiple grid objects, which are allowed to interact with each other. Grid objects have the capability of performing local anisotropic grid refinement (h-adaptation) as well as relocating their vertices (r-adaptation) to resolve length scales based on solution field obtained using algeb...
EROSION OF BASINS OF ATTRACTION - PERFORMANCE LOSSES IN SENSORIMOTOR LEARNING OF A ROBOT MANIPULATOR UNERI, M; Erkmen, Aydan Müşerref (1992-08-13) The sensorimotor learning phase is considered in the context of a collision-free dynamic path planning architecture for a robot manipulator in an uncertain task environment. The robot dynamics are effected by a vector field generated by partially known attractors and repellers, with uncertainty represented by entropy measures. The joint space is transformed into a cell space, and sensor uncertainty is taken proportional to cell size. The authors use a cell-to-cell mapping concept to develop a simple cell ma...
A temporal neural network model for constructing connectionist expert system knowledge bases Alpaslan, Ferda Nur (Elsevier BV, 1996-04-01) This paper introduces a temporal feedforward neural network model that can be applied to a number of neural network application areas, including connectionist expert systems. The neural network model has a multi-layer structure, i.e. the number of layers is not limited. Also, the model has the flexibility of defining output nodes in any layer. This is especially important for connectionist expert system applications.

Citation Formats

M. R. H. Al-Dahhan and K. V. Schmidt, “Voronoi Boundary Visibility for Efficient Path Planning,” IEEE ACCESS, pp. 134764–134781, 2020, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39619.