Multi-objective path planning for virtual environments

Download

index.pdf

Date

2012

Author

Oral, Tuğcem

Metadata

Show full item record

Item Usage Stats

174
views

67
downloads

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 required. It can be seen that more realistic and robust results can be obtained with these algorithms because they expand solution perspective into more than one criteria. Today, they are used in various games and simulation applications. On the other hand, most of these algorithms are off-line and delimitate interactive behaviours and dynamics of real world into a stationary virtuality. This situation reduces the solution quality and boundaries. Hence, the necessity of solutions where multi objectivity is considered in a dynamic environment is obvious. With this motivation, in this work, a novel multi objective incremental algorithm, MOD* Lite, is proposed. It is based on a known complete incremental search algorithm, D* Lite. Solution quality and execution time requirements of MOD* Lite are compared with existing complete multi objective off-line search algorithm, MOA*, and better results are obtained.

Subject Keywords

Heuristic algorithms., Heuristic programming., Approximation algorithms., Computer algorithms.

URI

http://etd.lib.metu.edu.tr/upload/12614643/index.pdf
https://hdl.handle.net/11511/21739

Collections

Graduate School of Natural and Applied Sciences, Thesis

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 Multi-Objective Incremental Path Planning Algorithm for Mobile Agents Oral, Tugcem; Polat, Faruk (2012-12-07) 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 p...
Voluntary Behavior on Cortical Learning Algorithm Based Agents Sungur, Ali Kaan; Sürer, Elif (2016-09-23) Operating autonomous agents inside a 3D workspace is a challenging problem domain in real-time for dynamic environments since it involves online interaction with ever-changing decision constraints. This study proposes a neuroscience inspired architecture to simulate autonomous agents with interaction capabilities inside a 3D virtual world. The environment stimulates the operating agents based on their place and course of action. They are expected to form a life cycle composed of behavior chunks inside this ...
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...
Optimal posture control algorithm to improve the stability of redundant haptic devices Baser, Ozgur; Konukseven, Erhan İlhan (SAGE Publications, 2013-5-9) Stability is indispensable to haptic interfaces for the simulation of a large variety of virtual environments. On a multi-degree of freedom (multi-DOF) haptic device, the passivity condition must be satisfied in both end-effector and joint space to achieve stable interaction. In this study, a conservative passivity condition is utilized for the stability such that guaranteeing the passivity at all joints is a sufficient condition for the passivity and then stability of the whole haptic system. An optimal po...

Citation Formats

T. Oral, “Multi-objective path planning for virtual environments,” M.S. - Master of Science, Middle East Technical University, 2012.