Path planning in polygonal domains for robots with limited turning abilities

摘要

Path planning among polygonal obstacles is a well-known problem in robotics. In this paper, we consider the problem of planning a collision-free path for a robot in a polygonal domain from a given source point to a given target point. The robot has two basic limitations: an upper bound on the angle of rotation and a lower bound on the distance between two consecutive turns. We describe an algorithm that runs in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ) time and finds a path in accordance with the above limitations. As shown by experiments, the output of the algorithm is much close to the shortest path with the requirements. We further demonstrate how to decompose the algorithm into two phases, preprocessing time and query time. In this way, given a fixed start point and a set of obstacles, we can preprocess a data-structure of size O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ) in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ) time, such that for any query target point we can find the above-mentioned path in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) time.