Robotic Path Planning Based on a Triangular Mesh Map
- PDF / 2,586,956 Bytes
- 9 Pages / 594.77 x 793.026 pts Page_size
- 84 Downloads / 220 Views
ISSN:1598-6446 eISSN:2005-4092 http://www.springer.com/12555
Robotic Path Planning Based on a Triangular Mesh Map Yanbin Liu and Yuanyuan Jiang* Abstract: Aiming at the problem of robot path planning in complex maps, an algorithm of robot path planning based on triangular grid graph is proposed. Firstly, a weighted undirected loop graph and a feasible domain of nodes are obtained by discretizing the triangular mesh map. Next, the Dijkstra search algorithm is applied to find the feasible shortest path from an initial to a final configuration. Finally, The Douglas-Peucker algorithm is applied to remove duplicate and redundant nodes in the feasible path, and the waypoint are extracted. The final path is a curve that is obtained by connecting the several extracted waypoint. The proposed algorithm is tested for various maps. Compared with probabilistic roadmap method, the experimental results show that the proposed method can overcome the shortcomings of the random sampling method. Furthermore, the experimental result of triangular mesh map method used in two labyrinth maps show that the triangular mesh map method can solve the robot path planning problem in complex map very well, and it is an excellent algorithm for robot path planning. Keywords: PRM method, robotic path planning, triangular mesh map, waypoint.
1.
INTRODUCTION
Robot path planning is an important research field in robotics. It can be applied to various practical problems and has important practical significance. For example, in accident rescue, the robot path planning can predict the future trajectory in unknown environment, and plan the safest and most efficient path to reduce casualties [1, 2]. The objective of path planning is to identify collision-free paths from an initial configuration to a final configuration. A significant amount of research has been devoted to this problem in recent years. The algorithms of path planning can be divided into the following 5 different categories [3]: 1) exact roadmap methods, 2) cell decomposition, 3) potential field methods, 4) intelligent algorithms, and 5) sampling-based planning. Exact roadmap methods represent a class of motion planning algorithms that assess the connectivity of the robot search space. The existing methods mainly involve two steps. First, a map is constructed in which each node is a point in the configuration space; then, a graph search algorithm, such as the A* algorithm or Dijkstra algorithm, is used to obtain a path that connects the initial and final configurations. There are 4 famous exact roadmaps methods: visibility graphs [4], Voronoi diagrams [5], Delaunay
triangulation [6], and adaptive roadmaps [7]. These methods work reasonably well in low-dimensional spaces and when multiple queries of the same map are performed. However, the major drawback with roadmap planners is that they require explicit representations of the shapes of obstacles in the configuration space. Thus, map construction can become intractable as the number of dimensions increases. Cell decomposition methods ar
Data Loading...
