The studies of motion planning with acceleration constraints

Abstract

A graph approach to motion planning. Given a set of rectangular obstacles expressed in space-time, an initial and a destination locations, a deadline time T, the velocity limit C on a point-like robot, the reachability problem under those conditions is solved by reducing it to a path existence problem in a combinatorial digraph. The running time of the algorithm is $O$($n\sp2$), where n is the complexity of obstacles. The A-hull of an obstacle. We show how to compute, for some simple obstacles, the set of points (the hull) in space-time such that given the robot's acceleration constraint A, as soon as the robot enters this set, it is doomed to crash later. It is shown that the robot's initial velocity is a main factor that makes the computation of A-hull non-trivial even for simple obstacles in 1-dimensional space. Reachability problems with acceleration constraints. We study the reachability problem with acceleration constraint. If the combinatorial strategy is predetermined, i.e., for each particular obstacle, whether the robot escapes from 'above' or from 'below' is predetermined, then it takes linear time to determine the reachability for every query ($x\sb{q},v\sb{q},t\sb{q}$) with preprocessing time $O$($n\sp2$), where n is the complexity of polygonal obstacles. The safest path among obstacles. We define and solve the safest path problem, stated as follows: Given an initial position $p\sb{\rm 0}$ = ($x\sb{\rm 0}$,$v\sb{\rm 0}$,$t\sb{\rm 0}$), a collection of obstacles in space-time and a bound A on the robot's acceleration, for a target position $p$ = ($x,v,t$), $t>t\sb{\rm 0}$, what is the safest path from $p\sb{\rm 0}$ to $p$, i.e., a path that maximizes the minimum distance to the obstacles? Our solution to this problem is based on repeatedly solving reachability problem. For the acceleration constrained robot, finding that safety takes $O$($n\sp3$log$\sb{2}n$), where n is the complexity of polygonal obstacles. With the computed safety, we can trace back to compute the safest path. The situation where the robot has both acceleration and velocity limits is also studied.