Path Planning Based On Grid For Automobile

The path planning is that a mobile robot searches an optimal path or a sub-optimal path from the initial state to the target state in accordance with a performance index (such as distance, time, energy, etc.). In this thesis, taking automobile allocation and transportation assistant decision-making system as background , we discuss the path planning application in engineering.The objectives of this project are providing a certain number of optimized path for some typical distributed maps and some typical tasks and sorting possible path. The main difficulties are environmental modeling for system and the requirement of meeting real-time in path search.Firstly, this thesis introduces the current research status about path planning from the environmental modeling and path search, and gives the main contents and the organizational structure.Secondly, combining with characteristics of the project, we propose improved grid method for environmental modeling. And we propose to use the ALA method for fitting and smoothing lines between grids.Thirdly, we propose two search methods based on improved grid method. One global search algorithm takes breadth-first search algorithm as base. We use hash table to prevent the duplication of states in this method. And this method greatly improves searching speed. In this thesis we research how to create hash table, and we propose to use two methods to settle hash collision. Another approximate search method bases on Dijkstra algorithm. Taking certain performance as premise, this method can realize faster searching speed. In this thesis, we give detailed programming for two search methods. And we use these two methods to calculate the path for moving car in accordance with some typical distributed maps. In the end we compare the two methods from the searching speed and the results.Finally, the development project, functions and some interfaces of the software are introduced.