Safe and Efficient Path Planning for Omni-directional Robots using an Inflated Voronoi Boundary

Aldahhan, Mohammed Rabeea Hashim
Schmidt, Klaus Verner
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 of following paths that consist of concatenated line segments. As the main contribution of the paper, we develop three new sampling-based path planning algorithms that address all of the stated performance metrics. The original idea of the paper is 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 (probabilistic roadmap), PRM* and FMT (fast marching tree). As a result, we are able to generate solution paths with a reduced computation time and increased path safety. Computational experiments with different environments show that the proposed algorithms outperform state-of-the-art algorithms.
Çankaya University Journal of Science and Engineering


MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives
Oral, Tugcem; Polat, Faruk (2016-01-01)
The need for determining a path from an initial location to a target one is a crucial task in many applications, such as virtual simulations, robotics, and computer games. Almost all of the existing algorithms are designed to find optimal or suboptimal solutions considering only a single objective, namely path length. However, in many real life application path length is not the sole criteria for optimization, there are more than one criteria to be optimized that cannot be transformed to each other. In this...
Multi-objective path planning for virtual environments
Oral, Tuğcem; Polat, Faruk; Department of Computer Engineering (2012)
Path planning is a crucial issue for virtual environments where autonomous agents try to navigate from a specific location to a desired one. There are several algorithms developed for path planning, but several domain requirements make engineering of these algorithms difficult. In complex environments, considering single objective for searching and finding optimal or sub-optimal paths becomes insufficient. Thus, multi objective cases are distinguished and more complicated algorithms to be employed is requir...
Comparison of 3D Versus 4D Path Planning for Unmanned Aerial Vehicles
Cicibas, Halil; Demir, Kadir Alpaslan; ARICA, NAFİZ (2016-11-01)
This research compares 3D versus 4D (three spatial dimensions and the time dimension) multi-objective and multi-criteria path-planning for unmanned aerial vehicles in complex dynamic environments. In this study, we empirically analyse the performances of 3D and 4D path planning approaches. Using the empirical data, we show that the 4D approach is superior over the 3D approach especially in complex dynamic environments. The research model consisting of flight objectives and criteria is developed based on int...
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...
Midcourse and final phase path planning for air vehicles to avoid countermeasures
Ataeli, Berk; Leblebicioğlu, Mehmet Kemal; Department of Electrical and Electronics Engineering (2021-3-25)
Path planning is a fundamental element of various common fields, such as robotics, computer animation, and wireless sensor networks. In this study, path planning for air vehicles is investigated in two phases. For the midcourse phase, the path with the minimum length, fuel consumption, and risk of being detected is sought between two particular points in 3D complicated environments. To achieve this aim, a Genetic Algorithm is utilized with a special feasible initial population creation method. Also, some pr...
Citation Formats
M. R. H. Aldahhan and K. V. Schmidt, “Safe and Efficient Path Planning for Omni-directional Robots using an Inflated Voronoi Boundary,” Çankaya University Journal of Science and Engineering, pp. 46–69, 2019, Accessed: 00, 2021. [Online]. Available: