Research On Parallel Route Planning Algorithm For Air Vehicle

Route planning is a novelty of information times, which is on the upgrade with the development of information technology, computer, automation control and artificial intelligence technology. Because the flying environment aircraft confronted with is very large and complex, and many kinds of constraints should be considered in the process of route planning, route search algorithm becomes the most challenging problem in route planning. Now , the route planning arithmetics include optimization planning algorithm, deterministic planning algorithm and random planning algorithm. There are always such-and-such problems when using these arithmetics. Many route constraints are over simplified in optimization, particularly the aircraft constraints. And also the search time of this kind of algorithms increases rapidly with the extension of planning environment. The deterministic algorithms may encounter combination-exploding problem. The random arithmetics cannot repeat the planning result and its convergence time is not determinate. For large planning space, huge data and complex constraints, most planning methods have two shortcomings. One is planning time is too long, another is their expansibility isn't sufficient. Therefore, This paper will research parallel route planning to decrease the planning time and improve the applicability. The time complexity of 3D Sparse A* Search (SAS) arithmetic show its practicality is not enough good, Though this approach efficiently prunes the search space and shorten the search time by incorporating route constraints into search algorithm. After analyzing parallelism of 3-D SAS completely, we find how to deal with the OPEN list and CLOSED list is crucial. If the OPEN and CLOSED lists are global, there is a bottleneck of shared resource. This paper established an applied formula to reduce the influence of this bottleneck. When parallel arithmetic uses distributed OPEN and CLOSED lists, it should prune duplicate nodes in different processors and balance processors'load. This paper also presented solution, but the experiment result is not satisfacfory because the SAS arithmetic is a local search process. The experiment results also demonstrated parallel planning using global OPEN and CLOSED lists shorten the search time obviously, but the expansibility needs to be improved. Further more, this paper presented an approach of route planning based on artificial neural network. This approach has great potential for parallelism and built a neural network for every route constraint. The neural networks are used for energy punishment of constraits. If a route satisfies route constraints, its energy is low, otherwise the energy is high. A motion equation was difined for route nodes and decreased the energy of the planning route. Finally, the result route satisfies all the constraints. A series of nodes were studied, the motion process of these nodes only need local information. Thus, these nodes can be divided into several segments in parallel arithmetic. The experiment results indicated the neural network algorithm can avoid terrain and threat. Its parallel arithmetic is with strong expansibility and satisfies the requirement in application.