Research And Implementation Of Dynamic Network Path Planning Algorithm Based On Reconfigurable Architecture

The shortest path planning problem is a classical mathematical problem, and the path planning technology is widely used in many fields. For example, driverless cars, unmanned aerial vehicle, intelligent robot, the cruise missile and missile defense system in the field of science and technology; Intelligent vehicle navigation, geographic information system applications in the field of daily life; Marginal problems and rational allocation of resources in the field of logistics planning in the field of decision control. Routing planning in the field of communication technology, etc. With the development of human society and the continuous progress of science and technology, society for nearly a hundred years of scientific and technological achievements greatly exceed the human society in the past few thousand years of the sum of achievements. The scale of modern cities is huge, the complexity of the road network, the amount of data processing is also increased; For example, the New York City road network map we used in experiments contains 260,000 nodes and 730,000 edges. In the face of large amount of data network, the shortest path planning algorithm is time-consuming to solve, fail to satisfy the real-time requirements in applicationCompared with general purpose processor, reconfigurable systems can deal with parallel operation more efficiently because it depends on the data-stream process instead of the sequence instruction method. When comparing to ASIC, reconfigurable system is more highly flexible at hardware resources as the system can reconfigure the hardware to different functions according to the high level software, adapting to different algorithms.This thesis, according to the reconfigurable technology of hardware architecture, from the classic route network planning algorithm characteristics of system reconfigurable of basic mechanisms for the array form by task partitioning mapping of the classical algorithm, obtains the corresponding data flow graph and scheduling table. In this way, the mapping implementation of the algorithm on the reconfigurable hardware array processing unit is realized. Finally, the optimized algorithm is implemented on the reconfigurable hardware platform, and its performance is verified. This design can be achieved for different algorithm hardware reuse, and the design process can also be applied to other areas of the diagrams.The main work involved in this thesis are:(1) A path planning algorithm based on reconfigurable technology is proposed; Taking advantage of the dynamic configuration and parallelism of the reconfigurable hardware platform, a new method for the path planning algorithm based on the classical Dijkstra algorithm and the TSP algorithm is obtained.(2) The Dijkstra algorithm and TSP algorithm are realized and verified on the reconfigurable hardware architecture platform. Compared with the common computing platform, the 2.1 times and 3.2 times speed up. The dependence of the internal data structures, divided into suitable for execution of array reconfiguration, greatly reducing the original algorithm of time complexity and space complexity, so as to obtain a speedup by the classical Dijkstra and TSP algorithm parallel optimization analysis.