Optimal maneuver-based motion planning over terrain and threats using a dynamic hybrid PSO algorithm

https://doi.org/10.1016/j.ast.2012.02.014Get rights and content

Abstract

Motion planning is a key factor in enhancing the autonomy level of unmanned flying vehicles. A new dynamic hybrid algorithm is developed to solve the motion planning problem in real-time using a heuristic optimization approach. The proposed algorithm effectively combines desired features such as rapid convergence to an optimal path with reduced computational effort. In addition to the terrain obstacles, the proposed algorithm is able to avoid random threats that may arise sporadically in the terrain. Using the maneuver automaton concept, nonlinear dynamic model and performance constraints are also considered in the process of motion planning to further ensure feasible trajectories. Evaluation of the proposed algorithm against several simulated scenarios has effectively demonstrated its potential for generating optimal contour-matching trajectories that succeed in avoiding stochastic obstacles.

Introduction

Increasing complexity and advances in hardware and software technologies in the realms of control, robotics, electronics and artificial intelligence have led to the enhanced design, development and utility of unmanned air vehicles (UAV) with a wide range of applications. Improvements in the level of autonomy, in effective decision-making with reduced workload and in reducing human user/operator errors, as well as an increase in the operating range of UAVs, are highly desirable.

Motion planning generally refers to the derivation of a plan to steer the vehicle from an initial point to a target destination while avoiding obstacles. It is desirable to optimally generate such a plan using existing resources while minimizing certain cost functions. In practice, the motion planning problem requirements are faced in real-time and in a dynamic and non-definite environment. Therefore, to perform the mission correctly, one needs to observe and utilize all maneuvering capabilities of the UAV.

Motion planning algorithms can be evaluated against two criteria: completeness and complexity. In a complete algorithm, feasible solutions are found, and if there is no feasible solution, lack of success is announced. The computational complexity of the motion planning algorithm is classified as a PSPACE-hard problem in which the complexity grows exponentially by the dimension of the configuration space [19].

The behavioral model of a vehicle in flight can be described by a series of coupled, nonlinear differential equations. In this case, the only possible solution for this set of nonlinear equations is found through numerical integration. Adding the constraints of the motion planning to the motion equations will further complicate this set of equations. This level of complexity of the equations cannot be easily overcome by numerical optimization algorithms. Even if one is able to optimally solve this set of complex equations, the corresponding solution cannot be used in real-time. Because of this fact, most of the trajectory planning schemes such as variation-based optimal control schemes [26], [1], configuration space-based methods [21], [17] and heuristic optimization methods [10], [8], [9] have used simplified dynamic models of the vehicle or the kinematics equations. On the other hand, UAV system dynamic constraints and performance limitations should be considered to ensure a practical path.

The maneuver automaton (MA) idea, first proposed by Frazzoli [5], [7], [4], is a maneuver-based approach. MA utilizes distinctive portions of the vehicleʼs overall motion, called motion primitives. The motion primitives include a set of trim states and maneuver paths that transfer the vehicle from one trim state (TS) to another. Thus, by generating a library of finite trim states (TSs) and their corresponding transition maneuvers, the problem of motion planning turns into a hybrid optimization problem with discrete and continuous design variables.

Frazzoli [4] has used the RRT search method to solve the motion planning problem. An added advantage of the RRT method is its ability to handle non-holonomic constraints [19]. However, a basic drawback of this method is its inability to uniformly search the state space, especially in the presence of obstacles [16]. In addition, RRT solutions are often far from optimal due to its random exploration of the space [28].

A time-varying hybrid model for dynamic motion planning has also been proposed [14] to overcome some limitations of the MA method initially proposed by Frazzoli. These limitations are due to restrictions, limiting vehicle motion to a finite set of motion primitives. Even though the finite search space is desirable in terms of efficiency and feasibility, it is restricted. Therefore, these authors have tried to improve MA by using more motion primitives to cover a wider portion of the search space, whereas in each portion of the mission, only a small number of motion primitives are utilized. The disadvantages of this work are as follows: solving the problem in 2D space utilizing a simple kinematics model and neglecting the dynamic nature of the motion planning problem.

Utilizing the MA concept and an Ant Colony Optimization (ACO) algorithm, the problem of motion planning in the presence of deterministic threats is investigated by Krenzke [16]. The disadvantage of this work is that the maneuvers within the library are formed using the kinematics equations. Additionally, only one constant time span has been assigned to all maneuvers. While in practice, different transition maneuvers may have different time spans, due to their initial and final conditions. The threats are also assumed to be deterministic rather than random. In addition, the ACO algorithm is employed to solve the motion planning problem, which is a discrete optimization scheme. Therefore, it cannot efficiently handle the motion planning problem with discrete and continuous design variables.

Considering the various schemes mentioned above, maneuver-based methods are able to fully consider the vehicle dynamics, whereas the other basic methods utilize only simplified versions of dynamics such as the kinematics equations or the point-mass model. Furthermore, only a few performance constraints are considered in the previous studies, such as velocity, turn rate and turn radius. Therefore, the maneuver-based generated trajectories will be feasible and can be implemented and tracked by the vehicle control system.

There are also various approaches proposed for the real-time path planning in the literature. Frazzoli et al. [6] have utilized the MA idea and four varieties of RRT that vary in complexity and completeness for the motion planning problem. Saunders et al. [23] have combined the RRT, as a priori planner that plans waypoint paths, with a reactive planner that dynamically avoids obstacles. Kothari [15] has utilized the RRT, for the waypoints generation along with an anytime algorithm for dynamic obstacles avoidance. The RRT algorithm and the cubic Bezier spiral curves have been used for 3D smooth path planning of a UAV in cluttered natural environments [28]. An improved Heuristic A Algorithm is also implemented for a UAV path planning in real-time [20].

More recently, different dynamic heuristic optimization algorithms have been developed and tested in contrast with complex dynamic optimization bench mark problems. The dynamic hybrid particle swarm optimization (DHPSO) algorithm [13], also developed by the authors, is among one of these schemes.

The current study implements a dynamic heuristic optimization approach to the motion planning problem, for the first time. This study is also based on the MA approach. This way, a complete model of the full motion planning problem is presented for a UAV, concentrating on all aspects that include the vehicle capabilities, the environmental constraints and the real-time requirements. To this end, a trim-maneuver library for the TSs and their corresponding transition maneuver trajectories are generated and stored in an offline fashion. TSs are determined using a heuristic constrained optimization algorithm [12]. The transition maneuvers of the library are generated using a nonlinear control system design approach [11] that allows for a smooth trajectory between the TSs. Because of a high volume of terrain data, the Catmull–Rom surfaces [22] that give a rapid and smooth interpolation are used to model the terrain profile. To handle the real motion planning problem, pop-up threats are added to the scenery. After organizing the trim-maneuver library, the DHPSO algorithm is empowered to solve the resulting hybrid optimization problem. In addition, a segmented approach and a look-ahead strategy are followed in the utility of the design vector that enables the proposed DHPSO algorithm to perform real-time optimal motion planning in the presence of terrain and random threats. Evaluating the algorithm, through different scenarios, demonstrates its satisfactory performance and its capability of being implemented in practice.

The arrangement of this paper is as follows. Section 2 describes the main parts of the motion planning problem. The organization of the trim-maneuver library and the schemes that are used to form the trim and maneuver trajectories are presented in Section 3. Section 4 is devoted to the new proposed algorithm for motion planning. In Section 5, different scenarios are simulated, and the efficiency and real-time capability of the algorithm are evaluated. Conclusions are drawn and presented in Section 6.

Section snippets

The motion planning problem

The motion planning problem formulation consists of four parts: the system dynamics, internal constraints, external constraints and the cost function. These parts are covered in the following subsections. See Fig. 1 for motion planning flowchart.

Organization of the trim-maneuver library

To form the basis for motion planning, a set of trim and maneuver paths is initially determined based on the performance and dynamic capabilities of the UAV under study. These off-line generated paths can be selected through the operational flight envelope and will construct the so-called trim-maneuver library. The trim paths characteristics include the velocity, altitude, turn rate and rate of climb information. Maneuver characteristics include the 3D trajectory of maneuvers and their

Solving the motion planning problem

After constructing the trim-maneuver library, the proposed algorithm to solve the motion planning problem is introduced. In this regard, it is important to note the following points:

  • In our MA strategy, the vehicle starts its mission from a starting point at a predefined TS with a known time span. During the flight, it can select other TSs within the trim-maneuver library and use maneuver trajectories within the library. Therefore, the motion planning involves the optimal selection of a sequence

Verification of the proposed algorithm

The DHPO routine is developed in the MATLAB environment and runs on a PC with a 2.0 GHz CPU and 1.0 GB of RAM. Two models, including virtual and real terrain, are considered for case studies. In a virtual terrain model, the following mathematical function is utilized to represent the terrain height:elev(x,y)=a0+a1sin(a2+y)+a3sin(x)+a4cos(a5x2+y2)+a6cos(y)+a7sin(a7x2+y2)+a8cos(y) The operating area is assumed to be 0x40000 and 0y40000. By the proper selection of the constant parameters of

Conclusions

The motion planning problem in the presence of terrain and random threats is investigated here. To simulate a more complicated and realistic case of motion planning, it is assumed that the terrain data are previously saved in the onboard computer of the UAV (or ground control station), but the threat zones are considered to be random, both in terms of number and location. The large number of DEM terrain data is handled by utilizing cardinal spline surfaces. Application of Catmull–Rom surface

References (29)

  • W. Du et al.

    Multi-strategy ensemble particle swarm optimization for dynamic optimization

    Journal of Information Sciences

    (2008)
  • J. Karimi et al.

    A new hybrid approach for dynamic continuous optimization problems

    Applied Soft Computing

    (2012)
  • A. Babaie et al.

    Optimal trajectory planning for a UAV in presence of terrain and threats

    Aerospace and Mechanics Journal of Imam Hossein University

    (2011)
  • A.P. Engelbrecht

    Fundamentals of Computational Swarm Intelligence

    (2005)
  • E. Frazzoli, Robust hybrid control for autonomous vehicle motion planning, Ph.D. thesis, Massachusetts Institute of...
  • E. Frazzoli, F. Bullo, On quantization and optimal control of dynamical systems with symmetries, in: Proceedings of...
  • E. Frazzoli et al.

    Real-time motion planning for agile autonomous vehicles

    AIAA Journal of Guidance, Control, and Dynamics

    (2002)
  • E. Frazzoli et al.

    Maneuver-based motion planning for nonlinear systems with symmetries

    IEEE Trans. on Robotics

    (2005)
  • M. Guanjun et al.

    Improved ant colony algorithm for global trajectory planning of UAV under complex environment

    International Journal of Computer Science & Application

    (2007)
  • M. Hao et al.

    A hybrid ant colony optimization algorithm for path planning of robot in dynamic environment

    International Journal of Information Technology

    (2006)
  • D. Jian, J. Vagners, Parallel evolutionary algorithms for UAV path planning, in: Proceedings of AIAA 1st Intelligent...
  • J. Karimi, S.H. Pourtakdoust, Integrated motion planning and trajectory control system for unmanned air vehicles,...
  • J. Karimi et al.

    Trim and maneuverability analysis of a UAV using a new constrained PSO approach

    Journal of Aerospace Science and Technology (JAST)

    (2011)
  • J.J. Kehoe, A.S. Watkins, R. Lind, A time-varying hybrid model for dynamic motion planning of an unmanned air vehicle,...
  • Cited by (66)

    • Control-oriented UAV highly feasible trajectory planning: A deep learning method

      2021, Aerospace Science and Technology
      Citation Excerpt :

      Unfortunately, the UAV closed-loop model is described by a series of coupled, nonlinear differential equations [17] that need to be integrated continuously over each sampling step; thus, its computational burden is too heavy and planning efficiency is very low. Karimi et al. [17] planned a trajectory based on a UAV closed-loop model. By generating a trim-maneuver library off-line, the complicated path planning is transformed into a simple hybrid optimization problem.

    View all citing articles on Scopus
    View full text