Simulation of Euclidean Shortest Path Planning Algorithms Based on the Framed-Quadtree Data Structure

The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics, we are concerned in the automatic synthesis of robot motions, given specifications of tasks and geometric models of the robot and the obstacles. The Mover’s problem is to find a continuous, collision free path for a moving object through an environment containing obstacles.

In this project, we implement an algorithm which finds the conditional shortest path, a collision-free path of shortest distance based on known information on an obstacle-scattered environment at a given time. This method utilizes a circular path planning wave and is based on a revolutionary data structure, the framed quadtree, which improves upon existing square-grid and quadtree-based techniques. This algorithm works in linear time and guarantees a conditional shortest path in any known 2-D environment.