A comparative study of quadtree decomposition and constrained delaunay triangulation using MDP and artificial potential field based path planning

Download

index.pdf

Date

2019

Author

Kandehir, Başe

Metadata

Show full item record

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

Item Usage Stats

158
views

67
downloads

The general purpose of a mobile robot is moving from one point to another and perform certain tasks. To do so, it first computes a motion strategy and then tries to execute it. This is not feasible most of the time unless uncertainties of the real world is taken into account. Markov decision processes (MDPs) provide a mathematical system to deal with uncertainties of planning and execution stages. MDPs require finite set of states. Therefore, continuous space of the real world must be discretized. In this study, two widely used space discretization methods, namely quadtree decomposition (QD) and constrained Delaunay triangulation (CDT), are compared in terms of path length, travel time, two safety measures, planning time, number of iterations, and number of states to find out which one of these discretization methods is better in the context of MDP and planar motion planning. MDP framework is used as high-level planner, and value iteration is used to obtain the optimal policy. Then, artificial potential field (APF) method is used for low-level execution. Results showed that QD and CDT are both suitable in the context of MDP and planar path planning with APF. QD results in longer paths but requires less travel time whereas CDT results in shorter paths but requires more travel time. QD and CDT perform almost equally in terms of safety. QD has clear disadvantages compared to CDT in terms of planning time, number of iterations, and number of states. QD and CDT might be preferable for different applications. Thus, it is best to optimize parameters for preferred metrics on a specific problem.

Subject Keywords

Markov processes ., Keywords: Quadtree decomposition, constrained Delaunay triangulation, Markov decision process, artificial potential field, space discretization, motion planning

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A Deep Incremental Boltzmann Machine for Modeling Context in Robots Doğan, Fethiye Irmak; Çelikkanat, Hande; Kalkan, Sinan (2018-05-25) Context is an essential capability for robots that are to be as adaptive as possible in challenging environments. Although there are many context modeling efforts, they assume a fixed structure and number of contexts. In this paper, we propose an incremental deep model that extends Restricted Boltzmann Machines. Our model gets one scene at a time, and gradually extends the contextual model when necessary, either by adding a new context or a new context layer to form a hierarchy. We show on a scene classific...
A Modular Real-Time Fieldbus Architecture for Mobile Robotic Platforms Saranlı, Uluç; Oeztuerk, M. Cihan (Institute of Electrical and Electronics Engineers (IEEE), 2011-03-01) The design and construction of complex and reconfigurable embedded systems such as small autonomous mobile robots is a challenging task that involves the selection, interfacing, and programming of a large number of sensors and actuators. Facilitating this tedious process requires modularity and extensibility both in hardware and software components. In this paper, we introduce the universal robot bus (URB), a real-time fieldbus architecture that facilitates rapid integration of heterogeneous sensor and actu...
A control system using behavior hierarchies and neuro-fuzyy approach Arslan, Didem; Alpaslan, Ferda Nur (null; 2005-09-14) In agent-based systems, especially in autonomous mobile robots, modelling the environment and its changes is a source of problems. It is not always possible to effectively model the uncertainty and the dynamic changes in complex, real-world domains. Control systems must be robust to changes and must be able to handle the uncertainties to overcome this problem. In this study, a reactive behaviour based agent control system is modelled and implemented. The control system is tested in a navigation task using a...
A programming technique for multifunctional use of industrial robots Balkan, T (1996-08-16) In this study, a software is developed in order to use an industrial robot, specifically an are welding robot, as a palletizing robot by using programming codes of a FANUC ARC Mate Sr. on a FANUC R-G2 controller environment. The software performs all standard palletizing options of a material handling robot in the same category without requirement of any optional built-in software. In addition, multiplication and division can be performed without any optional software for these functions, by using standard ...
A comparative evaluation of adaptive and non-adaptive Sliding Mode, LQR & PID control for platform stabilization Akgul, Emre; Mutlu, Mehmet; Saranlı, Afşar; Yazıcıoğlu, Yiğit (2012-12-01) During the uniform locomotion of compliant legged robots and other terrain vehicles, the body of the robot often exhibits complex oscillations which may have a disturbing effect on onboard sensors. For a camera mounted on such a robot, due to perspective projection, the effects of angular disturbances are particularly pronounced as compared to translational disturbances. This paper is motivated by the particular problem of legged robots exhibiting angular body motions and attempts to evaluate the performanc...

Citation Formats

B. Kandehir, “A comparative study of quadtree decomposition and constrained delaunay triangulation using MDP and artificial potential field based path planning,” Thesis (M.S.) -- Graduate School of Natural and Applied Sciences. Electrical and Electronics Engineering., Middle East Technical University, 2019.