CLAUDIA%OZ.AI.MIT.EDU@XX.LCS.MIT.EDU (Claudia Smith) (11/18/86)
TRAJECTORY PLANNING IN TIME VARYING ENVIRONMENTS Kamal Kant Gupta McGill University Montreal,Canada ABSTRACT: We present a novel approach to solving the trajectory planning problem (TPP) in time-varying environments. The essence of our approach lies in a heuristic but natural decomposition of TPP into two subproblems: (1) planning a path to avoid collision with static obstacles and (2) planning the velocity along the path to avoid collision with moving obstacles. We call the first subproblem the path planning problem (PPP) and the second the velocity planning problem (VPP). Thus, our decomposition is summarized by the equation TPP \rightarrow PPP + VPP. The symbol \rightarrow indicates that the decomposition holds under certain assumptions, e.g., when obstacles are moving independently of (i.e. not tracking) the robot. Furthermore, we pose the VPP in path-time space, where time is explicitly represented as an extra dimension, and reduce it to a graph search in this space. In fact, VPP is transformed to a two-dimensional PPP in path-time space with some additional constraints. Algorithms are then presented to solve the VPP with different optimality criteria: minimum length in path-time space, and minimum time. DATE: Tuesday, Nov. 18th TIME: 3pm PLACE: NE43-773 (7th floor conference room) HOST: Prof. Brooks