SIA Researchers Proposed New UAVs on-line Active Path Planning Algorithm

Aug 14, 2014     Email"> PrintText Size

Unmanned Aerial Vehicles (UAVs) path planning in cluttered environment has been one of the most significant elements in mission definition. For better use of UAVs in complex environment, a fast-optimal convergence path planning algorithm is urgently needed. General UAVs path planning algorithms include Visibility Graph, which is developed from computer science, optimal search algorithms like Dijsktra’s algorithms, A*, D*, bio-inspired planning algorithms and so on. However, almost none of the algorithms mentioned above can guarantee fast convergence in outdoor complex environment, let alone implement real time with uncertainty in outdoor clustering environment.

In order to solve the problem, researchers from Shenyang Institute of Automation of the Chinese Academy of Sciences focused on UAVs on-line path planning problem in outdoor cluttered environment, and proposed a new UAV on-line active path planning algorithm, called Guiding Attraction based Random Tree (GART). This algorithm seeks the metrics of general Rapidly-exploring Random Tree method, and pioneeringly introduces obstacle’s attraction and goal attraction to support guiding to RRT random generated nodes (Fig.1).

 

 

Fig.1. GART attraction to random nodes toward safe (Image by YANG Liang et al.)

Where the obstacle’s attraction is proportional to the distance from the random node to the surface of the obstacles, and the goal attraction is adaptively adjusted with obstacle condition. The force support by obstacles and the goal is called ‘Attraction’ is what SIA researches firstly proposed, and which means that the wider the distance to obstacle’s surface, the safer it guarantees (Fig.1).

 

  Fig. 2 . The attraction supported by obstacles (Image by YANG Liang et al.)

Thus the attraction combination generally pull the UAV path nodes towards safe. And here defines a trick that the if the turning angle of attraction combination and goal attraction exceeds , then reverse the attraction combination.

GART is compared with RRT* to prove is efficiency as shows in Figure 3, and a map is illustrated to show the convergence speed (Figure 4) of GART is much faster than RRT*, let alone RRT is cluttered environment.

 

 (a)                                  (b)                               (c)                             (d)

 

    (e)                                 (f)                                    (g)                               (h)

Fig. 3. A comparison of GART and RRT* algorithms on a simulation example with ten obstacles. They run in the same map. The edges formed by GART are shown in (a)-(d), whereas those formed by RRT* are shown in (e)-(h). The tree snapshots (a),(e) contains 1000vertics, (b),(f) 10000 vertices, (c),(g) 20000 vertices, and (d),(h) 30000 vertices.(Image by YANG Liang et al.)

 

                                                                                         (a) Convergence performance

 

                                                                                         (b) Searching ability

Fig. 4 A detail comparison of algorithm’s efficiency in (a) and (b). In (a), the cost variance means the difference value between current cost to the shortest cost. (b)shows number of iterations that reaching the goal node in ten maps. (Image by YANG Liang et al.)

 

Fig. 5 GART find the goal for the first time, and only needs 2400 iterations.(Image by YANG Liang el al.)

GART is also tested works well in 3D environment (Fig. 5) and still SIA researchers tested the algorithm in real mountainous area, the results show that GART works well is cluttered environments.

This work is presented in 2014 IEEE International Conference on Mechatronics and Automation (ICMA 2014) held in Tianjin, China. This work is selected as the ‘Best Student Paper Award’. It is partially supported by NSFC under Grant #61203334, National Key Technology Research and Development Program of China, under Grant #2013BAK03B01, and U.S. Army Research Office under grant No. W911NF-09-1-0565.

Contact:
YANG Liang Ph.D Candidate
Shenyang Institute of Automation, the Chinese Academy of Sciences
E-mail: yangliang1@sia.cn or yangliang0128@163.com