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...
Human aware navigation of a mobile robot in crowded dynamic environments
Hacınecipoğlu, Akif; Konukseven, Erhan İlhan; Department of Mechanical Engineering (2019)
As mobile robots start operating in dynamic environments crowded with humans, human-aware and human-like navigation is required to make these robots navigate safely, efficiently and in socially compliant manner. People can navigate in an interactive and cooperative fashion so that, they are able to find their path to a destination even if there is no clear path leading to it. This is clearly a dexterity of humans. But the mobile robots which have to navigate in such environments lack this feature. Even perf...
Trajectory tracking control of unmanned ground vehicles in mixed terrain
Bayar, Gökhan; Koku, Ahmet Buğra; Konukseven, Erhan İlhan; Department of Mechanical Engineering (2012)
Mobile robots are commonly used to achieve tasks involving tracking a desired trajectory and following a predefined path in different types of terrains that have different surface characteristics. A mobile robot can perform the same navigation task task over different surfaces if the tracking performance and accuracy are not essential. However, if the tracking performance is the main objective, due to changing the characteristics of wheel-ground interaction, a single set of controller parameters or an equat...
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: