Technical Report MSC-2015-23

Title: Motion Planning in the Presence of Mobile Obstacles
Authors: Avi Stiefel
Supervisors: Gill Barequet
PDFCurrently accessibly only within the Technion network
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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion