طراحی جاده خاکی بر اساس الگوریتم کلونی مورچه Off-road Path Planning Based on Improved Ant Colony Algorithm

1 Introduction The path planning algorithm in off-road environment faces a lot of challenges [1–4]: the terrain slope is varied which limits or influences vehicle movement severely; the soil types are complicated and inevitably affected by climate and rainfall [5], the strength of soft or solid soil causes multiple block or delay for vehicle trafficability [6]. To plan an off-road path, if real car and driver are applied to test, it will be costly in manpower, material and financial resources. Moreover, the safety of vehicles and personnel can not be guaranteed. As a result, it’s necessary to investigate an optimized path planning method accommodating real terrain and soil conditions well. The essence of present optimal path planning problem [7–9] is planning out a reasonable path from start point to end point under known limitation of road network topological structure. A large number of experts and scholars have carried out the research on this question and proposed numerous algorithms [10], such as genetic algorithm, particle swarm optimization, neural network, visibility graph and colony optimization. The offroad path planning problem in this paper is different from above work in two aspects: First of all, in off-road environment, there is no road. Any point in given terrain is available as part of path which means the choice space of path planning algorithm is tremendous. Secondly, considering terrain slope as one important influence factor for vehicle’s movement, the search space of path planning problem in this paper is 3-Dimensional. To achieve quick movement and efficiently fulfil kinds of tasks, the optimal off-road path planning problem in 3-Dimensional space not only requires finding a least-cost trafficable path of vehicle, but also requires computation time is as short as possible, i.e. in real-time. Ant colony algorithm [11–13] is a new kind of evolutionary algorithm which plays an important role in solving the traveling salesman problem [14], the shortest path search problem [15], etc. The main problem of ant colony algorithm is how to improve global search ability and convergence speed. To find the global optimal path, the search space of algorithm should be as large as possible, however to reduce computation time, the random search should converge to best solution quickly. In this paper, to solve contradictions between the algorithm’s randomness and the pheromone update intensity, an improved ant colony algorithm is proposed.