ReinforcedRimJump: Tangent-Based Shortest-Path Planning for Two-Dimensional Maps

Abstract

Path planning under two-dimensional maps is a fundamental problem in mobile robotics and other real-world applications (unmanned vehicles, navigation applications for mobile phones, and so forth). However, traditional algorithms (graph searching, artificial potential field, genetic, and so forth) rely on grid-by-grid searching. Thus, these methods generally do not find the global optimal path, and as the map scale increases, their time cost increase sharply, except artificial potential field. A few algorithms that do not rely on grid-by-grid searching (rapidly-exploring random tree, visibility graph, and tangent graph) have special requirements for maps. Considering that the shortest path is composed of tangents between obstacles, in this paper, we propose a method called ReinforcedRimJump (RRJ) that does not rely on the point-by-point traversal but rather obtains the shortest path by finding the tangent multiple times between obstacles. The first improvement of this method is the precomputation of tangents, which causes the method to have a lower time cost than traditional methods. The second improvement of RRJ is edge segmentation, which allows RRJ to be used when the target is in the depression of the obstacle. To verify the theoretical advantages of RRJ, some comparative experiments under various maps are performed. The experimental results show that RRJ can always find the shortest path in the shortest time. Furthermore, the time cost of RRJ is insensitive to the map size compared to other methods. The experimental results presented herein demonstrate that RRJ meets the theoretical expectations.