The Taub Faculty of Computer Science Events and Talks

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 a complete reconstruction of the path, based on the new locations of the robot and the obstacle. Ideally, the algorithm would consist of faster iterations that create a complete approximate path, but can re-use information so that our approximation improves during each iteration. We begin by performing a locally-optimal convex decomposition of the freespace. At each iteration, we update the decomposition so that concave regions are split, but neighboring regions that can be fused into a larger convex region are fused. We then construct a piecewise-linear path that passes from the robot to the target, such that the joins are on edges created by the convex decomposition. We then augment the path to a smooth curve with bounded curvature; the specific form of curve is not relevant, but we present a number of different methods. Once an initial path is constructed, we iteratively improve our path while updating the convex decomposition. To do so, we remove or add linear segments as the convex decomposition demands. We then adjust the locations of the segments joins on the dividing edge segments, so that the adjusted path is an approximation of the shortest path. 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.