Research And Implementation Of Navigation Path Planning Algorithm Based On Embedded Platform

The automotive navigation can accurately suggest the driver the best routine that leads to the destination from the given analyzed routes, and then addresses the problems of weary round-trip or even delay caused by being not familiar with the traffic conditions. Path planning—as the core of automotive navigation—is usually confined by the embedded environment and path planning algorithm, makes the effect of automotive navigation unsatisfactory.This paper aims at presenting an improvement by giving a detailed analysis of conventional algorithm such as Dijkstra, Bellman-Ford-Moore, Floyd and heuristics Search, especially the path planning A* which frequently applied to A* and suggesting some approaches to impose the algorithm in bid to resolve the slow speed of solver and the low precision of optimum solution which are upon questions in the typical algorithm of Shortest Path Problem. Based on the careful analysis of the suiting case, fundamental principles and concrete steps of A* algorithm, optimizes and improve the path planning—which is based on the A* algorithm—to fulfill high efficiency, correctness and real-time request of the vehicle navigation equipment.First of all, we adopt in a layered-decomposed organized way to and use different complex data structure to different-level section and nodes. Different data structure in stratified data occupies different data space, and it could simplify the complexity of node data structure. Combined with hierarchical ordering ways and adopt rising-search tactics make search can cut over among different stages.That is also the advantage of layer data store—reduces candidate item of searching-carry on nodes and searching time, node access time and internal storage usage amount. In addition, bidirectional searching strategy not only prevents over searching problem but also avoids the problems that efficiency and time rising complexity because up-and-down levels frequent switchover when use the rising level strategy.Through a large number of tests and comparison between the pre-and post-algorithm are made to show that either the efficiency or the real-time satisfies the user's requirements. Besides, this system has made a full account of expansibility, say the reduction of complexity of data structure and usage amount of memory will be a large number, which completely avoids the external memory data I/O while putting data into memory at the moment of starting server, given that the expansion of enough memory.