tim@LINC.CIS.UPENN.EDU.UUCP (02/28/87)
COLLOQUIUM
Computer and Information Science
University of Pennsylvania
Philadelphia PA
10:30am 3/2/87, 307 Towne Bldg.
Motion Planning in Time-varying Environment
Kamal Kant Gupta
Computer Vision and Robotics Lab
McGill University
Motion Planning Problem is to determine the motion of an object,
from a start position to a goal position, while avoiding collision
with other objects (obstacles) in its enviroment. Most Motion Planning
research, up until very recently, has considered static obstacles, i.e.,
plan the path to avoid the static obstacles, called the path planning
problem, or, the PPP. We consider the problems of planning collision-
free trajectories (path as a function of time) for an object among
moving as well as static obstacles. We call it the Trajectory Planning
Problem (TPP) in time-varying enviroments.
Our approach to formulating the TPP is to consider space-time, where
time is represented explicitly. Such a representation leads to a
geometric view of trajectory - as a curve in space-time-and lends itself
to use of computational geometric techniques in space-time. Such techniques
are quite novel in the sense that they do not occur in the case of only
static obstacles.
We propose a heuristic but natural decomposition of the TPP into two
sub-problems: (i) plan a path to avoid the static obstacles, i.e.
solve the PPP, and (ii) plan the velocity of the robot along the
path to avoid collision with the moving obstacles. We call the
second sub-problem the velocity planning problem, the VPP. The
main motivation behind the decomposition is to reduce the
complexity of the full problem, and present efficient algorithms
for collision-free trajectories.
Standard algorithms may be used to sovle the PPP. We then present
fast, efficient and complete algorithms to solve the VPP. The essence
of these algorithms lies in forulating the VPP in 2-dimensional path-
time. In the process, we also explore some properties of the path-
time space.
These algorithms have applications in several domains of robotics. In
particular, we shall illustrate the use of these algorithms in two
domains: i) for autonomous navigation of a mobile robot, and ii)
for motion co-ordination of multiple robots.