This chapter proposes a new trajectory planning approach by improving A* algorithm, which is a widely-used, path-planning algorithm. This algorithm is a heuristic method used in maps such as the occupancy grid map. As the resolution increases in these maps, obstacles can be defined more precisely. However, the cell/grid size must be larger than the size of the mobile robot to prevent the robot from crashing into the borders of the working environment or obstacles. The second constraint of the algorithm is that it does not provide continuous headings. In this study, an avoidance area is calculated on the map for the mobile robot to avoid collisions. Then curve-fitting methods, general polynomial and b-spline, are applied to the path calculated by traditional A* algorithm to obtain smooth rotations and continuous headings by staying faithful to the original path calculated. Performance of the proposed trajectory planning method is compared to others for different target points on the grid map by using a software developed in Labview Environment.
TopIntroduction
Scientific studies on mobile robots have increased considerably in recent years. These studies can be summarized in four main sections; localization, mapping, path or trajectory planning and control. The path planning topic from these four main headings is the main theme of this paper. Over the years, many methods have been proposed for path planning. Calculation time, path length and path characteristics are the focus of improvements in path planning.
Many different algorithms have been developed for the mobile robot path planning task and the improvements for these algorithms are focused on factors such as calculation time, path length and path characteristics. In addition, these algorithms are mainly divided into classical methods and heuristic methods. A survey (Mac, Copot, Tran, & De Keyser, 2016) was concentrated on heuristic algorithms based on neural network, fuzzy logic, nature-inspired algorithms and hybrid algorithms. Also Buniyamin et al. (Buniyamin, Ngah, Sariff, & Mohamad, 2011) introduced a new approach called PointBug as a local path planning algorithm and compared the proposed approach with traditional Bug algorithms, Distbug and TangenBug, in terms of path length and reachability performance to the target. Čikeš et al. (Čikeš, Đakulović, & Petrović, 2011) presented a comparative study of D*, TWD* (Two Way D*) and E* algorithms on the occupancy grid map of the environment in terms of path characteristics, searching time and the number of iterations. Subramanian et al. (Subramanian, Sudhagar, & RajaRajeswari, 2014) presented Breadth First Search (BFS) algorithm as a path planning method to search for the shortest path faster than heuristic methods. Also in another study they (Subramanian, Sudhagar, & Rajarajeswari, 2015) presented a dynamic pathfinding approach in an unknown environment using vector field histogram for obstacle avoidance and A* algorithm for a heuristic path planning.
In addition, many studies have been made on A* algorithm which is a basic but powerful path planning approach and various improvements are presented to optimize the algorithm. Guruji et al. (Guruji, Agarwal, & Parsediya, 2016) proposed a method to provide efficiency in processing time of A* algorithm. Yin and Yang (2013) proposed a multi-path algorithm based A* comparing with a K-Dijkstra-based algorithm to use in route navigation systems. Pala et al. (Pala et al., 2013) proposed a path planning algorithm called HCTNav which is focused on minimum use of computing and energy resources and they compared their method with Dijkstra's algorithm.
The A* path planning algorithm is not only used for wheeled mobile robots. The algorithm can be also used for navigation planning of water and air vehicles. For this reason, studies on the development of the method have been made for various platforms and tasks. Masudur Rahman Al-Arif et al. (Al-Arif, Ferdous, & Nijami, 2012) proposed a path planning algorithm using artificial intelligence technique considering to be used for a water vehicle during a rescue operation and presented a comparative study of Dijkstra and A* algorithms. Tseng et al. (Tseng, Liang, Lee, Chou, & Chao, 2014) proposed A* algorithm to plan flight path of a civil unmanned aerial vehicle to provide a better quality on 3G communication during flight. Cheng et al. (Cheng, Liu, & Yan, 2014) presented an improved hierarchical A* algorithm that takes into account shortest distance and time to calculate optimal parking path in a large parking guidance system.
This paper is organized as follows: In Section 2, occupancy grid map and A* algorithm are introduced. In Section 3, calculating avoidance area on grid map and curve fitting process for calculated path points are explained. After that, simulation results for the proposed approach compared with other methods are given in Section 4. Finally, discussions on the performance of improvements and suggestions for future studies are made in Section 5.