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

Download
2019
Kandehir, Başe
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.
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.