ABSTRACT

We consider the problem of planning curvatureconstrained paths amidst polygonal obstacles, connect­ ing given start and target configurations. This problem has been extensively studied in the automatic control and in the computational geometry communities, and has applications e.g. in flight path planning and in mo­ tion planning for car-like robots. In this paper, we present an approximation algorithm which is able to find an admissible path with curvature R _1 which is not longer than ( l +ε) times the length of the shortest admissible path with curvature (R + ε)-1 and clearance e from the obstacles. Assuming that the planning space is the unit cube [0 , l]2, the algorithm has running time 0 ( e ~ 3). Unlike previous approaches [8, 18], the presented algorithm discretizes state-space and can also be used for motion planning in weighted regions. Based on this algorithm, we describe a procedure to de­ termine if there exists an admissible path that satis­ fies a given curvature-constraint. This algorithm has the ability to solve intuitively easy problem instances quickly, i.e., in polynomial time, but does not termi­ nate for one critical value of the curvature-constraint. In contrast, the best known complete decision scheme [19] is exponential.