טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentStiefel Avi
SubjectMotion Planning in the Presence of Mobile Obstacles
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet
Full Thesis textFull thesis text - English Version


Abstract

        We take a new approach to motion planning specifically designed for handling mobile obstacles. Previous methods are modified versions of the algorithms for static obstacles, but with speed-ups designed to ensure real-time operation. Because of this logic, each iteration requires we completely recompute the path, based on the new locations of the robot and the obstacles. Ideally, the algorithm should allow us to, during each iteration, simply update the previous path based on the new configuration of the robot and the obstacles.
               We begin by dividing the area accessible to the robot, the freespace, into convex regions. We then create perform a path search in the dual graph of this decomposition, creating a piecewise-linear path stretching from the robot to the target, such that each linear segment is fully contained within a single convex region. This path is a greedy estimate of the shortest path; each segment is placed to minimize the difference towards the target. Last, the path is augmented to become a smooth curve with bounded curvature, with each segment fully contained within a convex region. 
               After the first iteration, we assume that only small changes need to be made to our model to maintain a usable path. Therefore, we ensure that the convex decomposition remains convex, updating if necessary. We refine our path, given the previous state of the path and the current state of the decomposition. Last, we augment the path again given the new geometric bounds.
               We show that our method is computationally faster than pre-existing algorithms. Furthermore, we show that because of the structure of the algorithm we can more easily determine if the entire path avoids obstacles. We show that the under the iterative improvements to the path, the path length always tends towards a local minimum.