Algorithms for path planning in the presence of moving obstacles and movable obstacles

Kamala Krithivasan (I.I.T. Madras)

In this talk, we consider algorithms for some specific problems of motion planning among moving obstacles and movable obstacles. We consider the following problems. In the case of moving obstacles the optimal path is taken as the time minimal path. Under this criterion, we consider the following problems: Optimal path in $L_2$ metric in the prescence of obstacles which are parallel line segments. Optimal path for the above problems in $L_1$ metric. Optimal path in 3-dimensions in $L_1$ metric in the prescence of parallel planar rectangular obstacles. Optimal path in the $L_1$ metric in the prescence of moving rectangles in 2D and hyper-rectangles in 3D. In all the above problems we use the concept of shortest path map of Lee and Preparata. The moving obstacles problem is converted to a stationery obstacles problem by converting moving obstacles into frozen obstacles. We also briefly consider the motion of a point robot in the presence of a slowly rotating line segment obstacle fixed at one end and a slowly rotating convex polygon rotating about an interior point. Next we take the optimal path to be the shortest distance path. We consider the problem of finding the shortest distance path between two points avoiding collision with the moving obstacles in the plane and 3D space. The problem has to be approached using space-time representation of the position of obstacles. We also consider the problem of computing the velocity profile for a point robot moving from a start point to a destination, along a straight line joining the two, in the presence of moving obstacles with non-zero velocity modulus. The environment is a plane and the obstacles are assumed to be simple polygons. In all the above cases, the complexity of the algorithm is $O(N \log N)$ where $N$ is the total number of vertices in the scene. We consider path planning among movable obstacles. We study the problem of path planning where the obstacles are stationery but may be displaced by the robot. The special case of path planning amidst uniform sized movable obstacles in a grid is studied. The algorithm is extended to the more general case of path planning amidst rectilinear movable obstacles. We extend the problem to three dimensions and also consider the algorithms to minimise the number of pushes or the number of turns.