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

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

11
views

8
downloads

Cite This

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