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.