MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives

Date

2016-01-01

Author

Oral, Tugcem
Polat, Faruk

Metadata

Show full item record

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

Item Usage Stats

237
views

0
downloads

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 paper, we introduce a novel multiobjective incremental algorithm, multiobjective D* lite (MOD* lite) built upon a well-known path planning algorithm, D* lite. A number of experiments are designed to compare the solution quality and execution time requirements of MOD* lite with the multiobjective A* algorithm, an alternative genetic algorithm we developed multiobjective genetic path planning and the strength Pareto evolutionary algorithm.

Subject Keywords

Incremental Path Planning, Multiobjective Path Planning (MOPP)

URI

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

Journal

IEEE TRANSACTIONS ON CYBERNETICS

DOI

https://doi.org/10.1109/tcyb.2015.2399616

Collections

Department of Computer 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 ...
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...
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...
Real-time edge follow: A real-time path search approach Undeger, Cagatay; Polat, Faruk (2007-09-01) Real-time path search is the problem of searching a path from a starting point to a goal point in real-time. In dynamic and partially observable environments, agents need to observe the environment to track changes, explore to learn unknowns, and search suitable routes to reach the goal rapidly. These tasks frequently require real-time search. In this paper, we address the problem of real-time path search for grid-type environments; we propose an effective heuristic method, namely a real-time edge follow al...
Suboptimal conflict based search for multi agent pathfinding Karabulut, İlhan Yoldaş; Polat, Faruk; Department of Computer Engineering (2019) Multiagent pathﬁnding is a problem faced in many ﬁelds including computer games, simulation software, and robotics. These applications generally require complete and real-time solutions. The class of methods which solves the problem optimally and completely spends much more time than real-time solutions. The algorithms to solve the problem within expected time limits, are mostly incomplete and do not guarantee anoptimumsolution. Inthisthesis,weproposedamethodthatimprovestheConﬂict Based Search algorithm whi...

Citation Formats

T. Oral and F. Polat, “MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives,” IEEE TRANSACTIONS ON CYBERNETICS, pp. 245–257, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/42559.