A Multi-Objective Incremental Path Planning Algorithm for Mobile Agents

Oral, Tugcem
Polat, Faruk
Path planning is a crucial issue in unknown environments where an autonomous mobile agent has to reach a particular destination from some initial location. There are several incremental algorithms such as D-star[1], D-star Lite [2] that are able to ensure reasonable paths in terms of path length in unknown environments. However, in many real-world problems we realize that path length is not only the sole objective. For example in computer games, a non-player character needs to not only find a minimum cost path to some target location but also minimize threat exposure. This means that path planning/finding activity of an agent in a multi-agent environment has to consider more than one objective to be achieved. In this paper, we propose a new incremental search algorithm called MOD star Lite extending Koenig's D-star Lite algorithm and show that MOD* Lite is able to optimize path quality in more than one criteria that cannot be transformed to each other. Experimental results show that MOD* Lite is able to find optimal solutions and is fast enough to be used in real-world multi-agent applications such as robotics, computer games, or virtual simulations.


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...
Generalizations of multi-agent path finding problem for incremental environments
Semiz, Fatih; Polat, Faruk; Department of Computer Engineering (2022-7-20)
Multi-Agent Path Finding problem (MAPF) is finding a path for multiple agents from a list of starting locations to a list of goal locations in such a way that the agents’ routes do not pass through the same location at the same time. The problem occurs in real-world during the transporting packages in warehouse environments with robots moving on rails, cleaning closed areas with cleaning robots, and protecting areas with multiple robots etc. It is usually sufficient to use discrete maps to express these pro...
A genetic algorithm for the p-hub center problem with stochastic service level constraints
Eraslan Demirci, Şükran; Meral, Fatma Sedef; Department of Industrial Engineering (2010)
The emphasis on minimizing the costs and travel times in a network of origins and destinations has led the researchers to widely study the hub location problems in the area of location theory in which locating the hub facilities and designing the hub networks are the issues. The p-hub center problem considering these issues is the subject of this study. p-hub center problem with stochastic service level constraints and a limitation on the travel times between the nodes and hubs is addressed, which is an unc...
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 ...
Planning unmanned aerial vehicle's path for maximum information collection using evolutionary algorithms
Ergezer, Halit; Leblebicioğlu, Mehmet Kemal (2011-01-01)
Path planning is a problem of designing the path the vehicle is supposed to follow in such a way that a certain objective is optimized. In our study the objective is to maximize collected amount of information from Desired Regions (DR), meanwhile flying over the Forbidden Regions is avoided. In this paper, the path planning problem for single unmanned air vehicle (UAV) is studied with the proposal of novel evolutionary operators; Pull-to-Desired-Region (PTDR), Push-From-Forbidden-Region (PFFR), Pull-to-Fini...
Citation Formats
T. Oral and F. Polat, “A Multi-Objective Incremental Path Planning Algorithm for Mobile Agents,” 2012, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/44022.