Sage Journals: Discover world-class research

Abstract

This paper presents an energy and perception aware framework for path planning and navigation of unmanned aerial vehicles (UAVs) in GNSS-denied and spatiotemporal wind environments. The proposed framework mainly consists of the global and local path planning methods that respectively consider the energy consumption of an UAV and perception quality of a light detection and ranging (LiDAR) sensor mounted on the UAV. The energy consumption is estimated based on the aerodynamic model that calculates drag and lift forces on the UAV. The global planner then uses the total energy consumption in the spatiotemporal wind as the cost function to find an energy-efficient path as a set of waypoints. The local path planning navigates the UAV between the waypoints with maintaining the perception quality. The perception quality is quantified based on how well the LiDAR sensor scans feature points around the UAV that highly correlates with the navigation accuracy. Numerical simulation study for each of the global and local path planners validates their usefulness. Further, the overall framework is entirely verified in a long-range flight scenario of the photorealistic environments developed in the Gazebo simulation.

Keywords

Unmanned aerial vehicle path planning energy consumption perception quality

Introduction

Autonomous unmanned aerial vehicles (UAVs) have been widely used for various missions such as construction/infrastructure inspection and search and rescue in disaster environments. In these missions, UAVs are often limited in their flight distance/duration because of obstacle collisions, the shortage of onboard batteries, or positioning errors owing to onboard sensors and loss of signal from global navigation satellite system (GNSS).

Collision avoidance is the essential and fundamental for UAV’s motion planning. Currently, several collision avoidance approaches have been reported¹ and validated for their usefulness in actual UAV flying situations.

On the other hand, for the battery problem, UAVs should basically be as light as possible while multiple battery packs should be mounted on the UAV for long-range flight, increasing the weight of the UAV. The trade-off between the UAV weight and its batteries severely limits the flight time and range. Additionally, the increase in aerodynamic drag due to the wind effect has a significant impact on the energy consumption of UAVs.

Recent studies have proposed UAVs’ flight planning methods to reduce the energy consumption of UAVs owing to weather changes² or using battery consumption models.³ Miller et al.⁴ proposed the cost-optimal path planning that solves time and risk constraints for UAVs in 3D space. This planner, however, is computationally more expensive than grid-based algorithms such as A*.⁵ Otte et al. extended the anytime A* algorithm, enabling UAVs to fly time-efficiently and avoid dynamic obstacles in real-time.⁶ Although there have been several studies on path planning methods that reduce the energy consumption of UAVs, none have focused on global path planners in a 3D environment where wind varies in time and space.

GNSS-denied environments/conditions often seen in stormy mountainous areas, forests, and even urban canyons requires UAVs to reliably fly autonomously. Simultaneous localization and mapping (SLAM) is capable of self-pose estimation as they utilize onboard vision sensors such as cameras and light detection and ranging (LiDAR).

Numerous studies have developed the local planning and localization methods to reduce the state estimation error for UAVs in GNSS-denied environments. Camera-based pose estimation enables UAVs to reach user-specified goals with a certain level of accuracy.^7,8 However, it has severe limitations; for instance, the pose estimation does not perform well in non-landmark or texture-less areas. Most studies have shown that the accuracy of pose estimation can be improved by perception-aware paths where the camera’s field of view captures effective feature points for SLAM or visual odometry algorithms.^9–12

Another technique for UAVs’ pose estimation is the use of a LiDAR sensor, that directly measures three-dimensional distances from the sensor to the objects with a 360° field of view.^13,14 Currently, LiDAR-based SLAM algorithms (Figure 1) have been proposed to improve the accuracy of pose estimation.^15–17 However, similar to camera-based pose estimation, LiDAR-based SLAM suffers from geometric degeneration such as long straight tunnels and planar environments, where there are few valid feature points. The camera-based perception-aware path plannings^9–12 can not directly be exploited to the LiDAR-based SLAM system. This is because the feature points measured by LiDAR are more numerous than those captured by a camera, and are distributed 360° around UAVs. A few studies have addressed the degeneration problem for the LiDAR-based SLAM.^18–21 To solve the optimization problem for pose estimation, Zhang et al. only used well-conditioned constraints, and Jiao et al. selected valuable/informative features. Zhou et al. exploited the Fisher information matrix (FIM) associated with the LiDAR measurement uncertainty, detecting the degeneration degree of the sensor measurements. Zhang et al.²² proposed the perception-aware path planning method to address such degeneration problem. They introduced the idea of the Fisher information field (FIF) to efficiently calculate the FIM from a set of sparse point cloud. While the planner with FIF increases the localization success rate and accuracy, it is limited in known environment since the accurate pre-computation of the FIF is needed.

Figure 1.

Example of LiDAR-based SLAM using 3D LiDAR mounted on the UAV. The 3D LiDAR provides a 360° field of view as point cloud (small colored dots). The SLAM algorithm extracts feature points (large blue dots) from the scanned point cloud, generates a global map (white dots), and estimates the pose of the UAV (yellow line).

Thus, autonomous navigation techniques presented in the existing studies may not be able to sufficiently drive UAVs in GNSS-denied and spatiotemporal wind environments. Therefore, this paper addresses an energy and perception aware framework for planning and navigation for UAVs, enabling the UAVs to fly a path with maintaining the energy efficiency and pose estimation accuracy. The proposed framework is elaborated by combining our previous works in Aoki and Ishigami²³and Takemura and Ishigami²⁴ for achieving global and local path planning. As in the literatures,^25,26 it is common for local and global planners to solve different problems and to integrate them well. The global path planning algorithm quantifies the energy consumption of a UAV in spatiotemporal wind environment and finds an energy-efficient path.²³ The local path planner assesses the perception quality for a LiDAR-based SLAM algorithm online, enabling robust autonomous flight in GNSS-denied unknown environments.²⁴ This paper incorporates these global and local planners and elaborates a planning and navigation framework that can drive a UAV to fly along an energy-efficient and SLAM-reliable path. Our research highlights in this paper are as follows:

the integration of the energy efficient global path planner and perception-aware local path planner for a UAV,

the parameter study of the perception-aware path planner,

the validation of the energy-efficient path planner using a high-fidelity simulator, and

the verification of the proposed framework in GNSS-denied environments and spatiotemporal wind using photorealistic simulations.

The remainder of this paper is organized as follows: the second section defines the problem statement; the third section shows an overview of the proposed framework; the fourth section explains the energy-aware global path planning; the fifth section proposes the perception-aware local path planner; the sixth section discusses the results of our numerical simulation; and, finally, the seventh section draws the conclusion and presents a direction for the future studies.

Problem statement

We assume that a UAV is equipped with a 3D LiDAR sensor on its bottom, enabling 3D scanning with a 360° field of view (Figure 1). Further, a global goal is given by human operators before the UAV starts to fly. The UAV does not always see the goal; therefore, the global path planner generates a waypoint set based on a global map. While flying toward each waypoint, the UAV measures environments and generates a local map at constant intervals.

This research aims to ensure that the UAV reaches a given global goal in GNSS-denied and spatiotemporal wind environments while reducing the energy consumption and pose estimation error. We address this challenge as global and local path planning problems. We assume that the global map only includes the spatiotemporal wind information, which can be accurately predicted based on the weather and climate forecast data²⁷ prior to the UAV’s flies. On the other hand, the detail 3D environmental information, which is acquired by onboard sensors, is subject to uncertainty until the UAV actually flies. For instance, in disaster areas, the destructed buildings are one of the uncertain information. Hence, we exploit the wind information in the global planning and use the 3D geometrical information in the local planning. The global path planning finds an energy-efficient waypoint set based on the spatiotemporal wind map. As for the local planning phase, smooth and collision-free paths toward each waypoint are generated while maintaining the perception quality in the 3D local map. Owing to the limitation of the LiDAR’s scanning range, the local planning is conducted based on the current pose and local map at each step, that is, the problem is solved in a receding horizon manner as in Tang et al.²⁸

System overview

Figure 2 illustrates an overview of the proposed navigation system, which mainly consists of offline and online processes. In the offline phase, the global path planner, which is one of the core components of our research, finds the waypoint set to steer the UAV from the start point to the goal area. The planner explicitly considers spatiotemporal wind speed based on a global map. The wind data is exploited to estimate the energy consumption of the UAV. The estimated energy is defined as the cost function in the global planner, which enables the UAV to find an energy-efficient global path. The path is generated by the extended A* algorithm⁵ that exploits a variable-resolution grid approach as in adaptive Single Time-step Search (aSTS).²⁹

Figure 2.

Schematic overview of autonomous navigation systems for UAVs.

The online process consists of a LiDAR-based SLAM, local path planner, and classical PD controller. For the LiDAR-based SLAM algorithm, advanced implementation of LiDAR odometry and mapping (A-LOAM)³⁰ was used to provide pose estimation and mapping for the UAV. A-LOAM processes the point cloud data acquired by 3D LiDARs³¹; and, extracts feature points $F$ from the point cloud to estimate the UAV’s relative motion. Further, A-LOAM generates local maps in real-time by using the point cloud stored as a 3D KD-tree.³² The local planner is one of our main contributions, which generates the perception-aware local path from a waypoint to next waypoint, which are generated by the global planner. After the UAV reaches one waypoint, it targets the next waypoint in a receding horizontal manner. The local planner exploits rapidly-exploring random tree (RRT^*)³³ and quantifies the perception quality based on the feature points scanned by the A-LOAM algorithm. The classical PD controller generates command velocities to track planned paths. The online process is repeated until the UAV reaches the global goal.

Energy-aware global planner

The proposed global planner exploits the aSTS method to account for the energy consumption of the UAV in an environment where wind velocity varies temporally and spatially. The aSTS is a graph-search-based method, which adaptively changes the resolution of the grid that divides the state space. Therefore, the method enables autonomous marine vehicles to generate energy optimal paths that match the realistic effect of 2D temporally and spatially varying flows. In our planner, the conventional aSTS method is extended by constructing a 3D graph in the path planning process, enabling the generation of 3D paths. Further, the proposed algorithm constructs a search graph based on the spatiotemporal wind map predicted by the wind speed dataset. The algorithm solves the path planning problem by calculating the cost between each node based on the UAVs’ energy consumption model.

Cost and heuristic functions

The cost function of the node $n_{i}$ is defined as in the conventional A* algorithm:

f (n_{i}) = g (n_{i}) + h (n_{i}),

(1)

where $g (n_{i})$ is the cumulative energy consumption from the start node to the node $n_{i}$ , and $h (n_{i})$ is the predicted energy consumption from $n_{i}$ to the goal node. $g (n_{i})$ and $h (n_{i})$ are defined as follows, extending the model of Thibbotuwawa et al.³⁴:

\begin{matrix} g (n_{i}) = g (n_{s}, n_{i}) \equiv E (V_{i}) \\ = \int_{t_{s}}^{t_{i}} (\frac{1}{2} C_{D} AD {(V_{i})}^{3} + \frac{m^{2} g^{2}}{D b^{2} V_{i}}) dt, \end{matrix}

(2)

\begin{matrix} h (n_{i}) \equiv min E (V_{i}) = E (V^{*}) \\ = \int_{t_{i}}^{t_{g}} (\frac{1}{2} C_{D} AD {(V^{*})}^{3} + \frac{m^{2} g^{2}}{D b^{2} V^{*}}) dt, \end{matrix}

(3)

where $D$ is the density of air, $C_{D}$ is the drag coefficient of the UAV, $V_{i}$ is the airspeed of the UAV at $n_{i}$ , $A$ , $b$ , and $m$ are the cross-sectional area, the width, and the mass of the UAV, and $g$ is the gravitational acceleration. $t_{s}$ and $t_{g}$ denote the departure time from the start node $n_{s}$ and the arrival time to the goal node $n_{g}$ , respectively. Here, $n_{j}$ node is represented as $n_{j} = (x_{j}, t_{j})$ using three-dimensional coordinates $x_{j} = (x_{j}, y_{j}, z_{j})$ and time $t_{j}$ , enabling the generation of three-dimensional paths in a time-varying environment. Note that the first and second terms in equations (2) and (3) represent the energy consumed by the aerodynamic drag and lift force, respectively. Additionally, $V^{*}$ is defined as the airspeed such that the energy consumption from a node to the goal node is minimized.

V^{*} \equiv a rg \min_{E} (V_{i}) = \sqrt[4]{\frac{2 m^{2} g^{2}}{3 C_{D} A D^{2} b^{2}}} .

(4)

Variable-resolution grid

In this study, the aSTS method is extended by varying the grid resolution based on the following equations:

∥ V_{e} ∥ \leq p ∥ V_{wind} (n_{i}) ∥,

(5)

V_{e} = {[\begin{matrix} V_{wind}^{x} \\ V_{wind}^{y} \\ V_{wind}^{z} \end{matrix}]}_{n_{j}} - {[\begin{matrix} V_{wind}^{x} \\ V_{wind}^{y} \\ V_{wind}^{y} \end{matrix}]}_{n_{i}},

(6)

where $V_{e}$ is the variation of the wind speed between the current node $n_{i}$ and the adjacent node $n_{j}$ , $V_{wind} (n_{i})$ is the wind speed at $n_{i}$ and estimated by the linear interpolation of the wind speed dataset, and $p$ is the allowable change rate. This operation adaptively determines the grid resolution so that the wind speed change rate between $n_{i}$ and $n_{j}$ is less than $p$ .

In the aSTS method, Newton’s method calculates the upper bounds of spatial resolution $d x_{max}$ and the upper bounds of temporal resolution $d t_{max}$ such that $p ∥ V_{wind} (n_{i}) ∥$ is close to $∥ V_{e} ∥$ . Using $d x_{max}$ and $d t_{max}$ , the proposed method computes the spatial resolution $Δ x$ and the temporal resolution $Δ t$ :

(Δ x, Δ t) = {\begin{matrix} (d x_{max}, \frac{d x_{max}}{\hat{V}}), d x_{max} < \hat{V} d t_{max} \\ (\hat{V} d t_{max}, d t_{max}), otherwise, \end{matrix}

(7)

where $\hat{V}$ represents the target flight speed of the UAV. Both resolution is determined based on the wind dataset so that the wind speed does not change significantly. In this study, when $Δ x$ is more or less than the threshold, $Δ x$ and $Δ t$ are modified as follows:

(Δ x, Δ t) = {\begin{matrix} (Δ x, Δ t), Δ x_{th}^{-} < Δ x < Δ x_{th}^{+} \\ (Δ x_{th}^{-}, \frac{Δ x_{th}^{-}}{\hat{V}}), Δ x_{th}^{-} > Δ x \\ (Δ x_{th}^{+}, \frac{Δ x_{th}^{+}}{\hat{V}}), Δ x_{th}^{+} < Δ x . \end{matrix}

(8)

Equation (8) avoids a large mismatch between the spatial resolution and the resolution of the wind speed data. Basically, the wind data is discretely given; and hence, the wind speed at each node is interpolated. When the resolution of the wind map is too discrete, and $Δ x$ and $Δ t$ are too small, the wind speed may be inaccurately interpolated. This can be caused in the case that the wind speed changes drastically. The time-spatial resolution becomes too small because equation (5) maintains that the wind change is less than $p$ . Therefore, $Δ x_{th}^{-}$ is introduced to adequately consider realistic wind effects. Further, $Δ x_{th}^{+}$ limits the distance between two nodes. Too large $Δ x$ possibly makes the local navigation difficult. Therefore, $Δ x$ is limited by the threshold values.

Search graph structure

In the proposed global planner, the graph for the A* algorithm is iteratively constructed based on a hypersphere with radius $Δ x$ and inscribed regular dodecahedron as shown in Figure 3. The graph construction extends the conventional aSTS method, enabling the UAV to plan paths in 3D space with time. In such high-dimensional space, the number of search nodes exponentially increases during graph construction, resulting in a trade-off between the computational burden and the optimality of the generated paths. Additionally, the neighbor nodes searched from the current node should be isotropically set to consider the realistic effect of the wind. Hence, we selects 32 adjacent nodes as shown in Figure 3, where the point $(x_{i}, t_{i})$ depicts the current node. 20 adjacent nodes are chosen from the vertices of the regular dodecahedron; and, the rest of the adjacent nodes are set on the surface of the hypersphere so that each node is placed at the center of each face of the dodecahedron. The proposed graph structure limits the number of adjacent nodes and makes the node’s distances nearly uniform. This enables efficient space search with less computational burden and the optimal path generation based on the realistic effect of the wind. It should be noted that 32 adjacent nodes have the same $t_{j}$ in Figure 3 because the UAV can reach each adjacent node in $Δ t$ . This is derived from the relationship between $Δ x$ and $Δ t$ , which are based on $d t_{max}$ or $d x_{max}$ as defined in equation (7).

Figure 3.

Graph construction based on a hypersphere and inscribed regular dodecahedron.

Algorithm 1 Energy-Aware Global Path Planner
Require: Start $n_{s}$ , Goal $x_{g}$ , $δ x$ , $p$ , Wind map $M$ , $V_{th}$ , $Δ x_{th}^{+}$ , $Δ x_{th}^{-} \hat{V},$ Obstacle $O$ 1: $Q$ = ${n_{s}}$ , graph $G$ = $ϕ$ 2: while $Q! = ϕ$ do 3: $n_{i} \leftarrow Q$ .extractMin() 4: $(‖ x_{i} - x_{g} ‖ < δ x)$ then 5: return BestPath( $n_{i}$ ), break; 6: $V_{wind} = getWindSpeed (n_{i}, M)$ 7: $V_{i} = getAirSpeed (V_{wind}, \hat{V})$ 8: $r_{\max} = getMaxErrDir (n_{i})$ 9: $n_{q}$ = ( $x_{q}$ , $t_{q}$ ) = getDispLimits $(n_{i}, r_{\max}, p)$ 10: $d x_{max} = \| x_{i} - x_{q} \|$ 11: $d t_{max} = \| t_{i} - t_{q} \|$ 12: $(Δ x, Δ t) =$ getDxDt $(d x_{max}, d t_{max}, \hat{V})$ 13: $N =$ constGraph $(Δ x, Δ t, n_{i})$ 14: for each Neighbor $n_{j}$ in $N$ do 15: if $(n_{j} \in O) OR (∥ V_{wind} (n_{j}) ∥ \geq V_{th})$ then 16: conitnue 17: if $n_{j} \in G$ then 18: if $cost (n_{j}) > g (n_{s}, n_{i}) + g (n_{i}, n_{j}) + h (n_{j})$ then 19: $G$ .addEdge $(n_{i} n_{j}), Q . update (n_{j})$ 20: else 21: $G .$ addEdge $(n_{i} n_{j})$ , $Q .$ addNode $(n_{j})$

Algorithm 1 Energy-Aware Global Path Planner

Require: Start

n_{s}

, Goal

x_{g}

δ x

p

, Wind map

M

V_{th}

Δ x_{th}^{+}

Δ x_{th}^{-} \hat{V},

Obstacle

O

Q

{n_{s}}

, graph

G

ϕ

2: while

Q! = ϕ

do
3:

n_{i} \leftarrow Q

.extractMin()
4:

(‖ x_{i} - x_{g} ‖ < δ x)

then
5: return BestPath(

n_{i}

), break;
6:

V_{wind} = getWindSpeed (n_{i}, M)

V_{i} = getAirSpeed (V_{wind}, \hat{V})

r_{\max} = getMaxErrDir (n_{i})

n_{q}

= (

x_{q}

t_{q}

) = getDispLimits

(n_{i}, r_{\max}, p)

10:

d x_{max} = | x_{i} - x_{q} |

11:

d t_{max} = | t_{i} - t_{q} |

12:

(Δ x, Δ t) =

getDxDt

(d x_{max}, d t_{max}, \hat{V})

13:

N =

constGraph

(Δ x, Δ t, n_{i})

14: for each Neighbor

n_{j}

N

do
15: if

(n_{j} \in O) OR (∥ V_{wind} (n_{j}) ∥ \geq V_{th})

then
16: conitnue
17: if

n_{j} \in G

then
18: if

cost (n_{j}) > g (n_{s}, n_{i}) + g (n_{i}, n_{j}) + h (n_{j})

then
19:

G

.addEdge

(n_{i} n_{j}), Q . update (n_{j})

20: else
21:

G .

addEdge

(n_{i} n_{j})

Q .

addNode

(n_{j})

Search algorithm

The procedure of the proposed global planner is shown in Alg. 1. The algorithm begins the loop procedure (Line 2). As the first step of the loop, the cost-minimum node $n_{i}$ is fetched from the open node list $Q$ (Line 3). $n_{i}$ is checked if its distance to the goal is less than $δ x$ , meaning $n_{i}$ reaches the goal $x_{g}$ (Lines 4–5). Basically, the wind map is given as discrete information; and hence, the aSTS method interpolates the discrete wind data to obtain the wind speed at each node $V_{wind} (n_{i})$ (Line 6). In Line 7, the airspeed $V_{i}$ is calculated to maintain the target speed $\hat{V}$ by the following equations:

V_{i} = \sqrt{{(V_{i}^{xy})}^{2} + {({\hat{V}}^{z} - V_{wind}^{z} + V_{n})}^{2}},

(9)

V_{i}^{xy} = \sqrt{{({\hat{V}}^{xy} - V_{wind}^{xy} \cos θ)}^{2} + {(V_{wind}^{xy} \sin θ)}^{2}},

(10)

where ${\hat{V}}^{xy}$ and ${\hat{V}}^{z}$ are each target flight speed in each axis, $θ$ is the angle formed by $V_{i}^{xy}$ and $V_{wind}^{xy}$ as shown in Figure 4(a), and $V_{n}$ represents the velocity of the air that the UAV discharges vertically downward to support its weight:

V_{n} = (\frac{mg}{{\overset{\cdot}{m}}_{exh}}),

(11)

Figure 4.

Auxiliary illustration for the proposed global planner: (a) relationship between target velocity, wind velocity, and air speed in the xy plane. (b) How to calculate the bounds of the spatial and temporal resolutions.

where ${\overset{\cdot}{m}}_{exh}$ is the mass flow rate of the air and is defined by the following equation:

{\overset{\cdot}{m}}_{exh} = \frac{1}{2} D b^{2} V_{i} .

(12)

Euations (9)–(12) are solved in conjunction. The function getMaxErrDir(-) calculates the direction with the largest wind velocity change around $n_{i}$ (Line 8). Subsequently, getDispLimits(-) returns the node $n_{q}$ as shown in Figure 4(b) so that the variation of the wind speed satisfies the constraint in equation (5). Based on $n_{q}$ , the upper bounds of spatial and temporal resolutions are calculated (Line 10–11). In Line 12, $Δ x$ and $Δ t$ are calculated based on equation (7). Using the resolutions, Line 13 iteratively constructs the graph structure $N$ of Figure 3. For each neighbor node $n_{j}$ in $N$ , the collision check and wind speed check are executed, enabling the UAV to fly safely (Line 15). The procedures in Lines 17–21 are similar to the conventional A* algorithm. Note that equations (2) and (3) are used in the cost calculation (Line 18).

Perception-aware local planner

Figure 5 illustrates the detailed diagram of the online process in Figure 2. The local path planning consists of a tree generation module based on RRT* and a path selection module. The planner exploits the RRT* algorithm to generate a library of candidate paths based on the current pose and map. The path selection module evaluates each path based on two metrics: the perception quality and goal progress. Based on the evaluation, the local path planning selects the best path to execute with the low-level controller. The path planning is iteratively conducted in a receding horizon manner until the UAV reaches the specified waypoint. For each planning step, the planner searches a path in a user-defined cubic area (Figure 6) based on the map and pose estimated by A-LOAM.

Figure 5.

Schematic overview of online process.

Figure 6.

Receding horizon path planning using the RRT* algorithm. The algorithm extends the tree (lines) and stores nodes (black circles) in the tree. In the proposed path planning, the branches of the tree are pruned (dotted lines) and a library of candidate paths $P$ (yellow lines) is acquired. The tip nodes of each candidate path are described (red circles). The final path $p^{*}$ is selected among candidate paths. The path is planned in a receding horizon manner until the UAV reaches the goal designated by the global planner as a waypoint: (a) random node sampling, (b) tree extension, (c) completion of tree extension, (d) branch pruning, (e) path selection, and (f) receding horizon manner.

Tree generation

The RRT* algorithm, which can generate a cost-optimal and collision-free path,³³ was exploited as the tree generation module. In this study, RRT* extends the tree as a library of candidate paths. This approach is similar to,²⁸ where a UAV efficiently explored unknown areas. Given that the generated tree may not be smooth for the UAV’s tracking, dynamic models¹¹ or smoothing techniques^35,36 are necessary. However, this point is not the core of our contribution and will be ignored here.

The procedures of the tree generation are summarized as follows:

1. Sample a random node (blue circle) from the user-defined cubic area (Figure 6(a)).

2. Obtain the parent node that minimizes the total distance from an initial node to the sampled node.

3. Extend the tree from the parent node (small red circle) to the sampled node (small blue circle) with a collision check (Figure 6(b)).

• If the distance between them is shorter than $ϵ$ , the algorithm directly extends the tree from the chosen node toward the sampled node.

• If the distance is larger than $ϵ$ , the algorithm extends the tree from the chosen node toward the sampled node at the distance $ϵ$ .

4. Perform the node rewiring process as the conventional RRT* algorithm does.

5. Repeat the procedures 1–4 until the number of sampling a node reaches $N_{sample}$ (Figure 6(c)).

6. Prune branches of the tree to have only $N_{node}$ number of nodes, which is receding horizon steps (Figure 6(d)).

Eventually, we obtain a library of candidate paths $P$ (the tree colored in yellow in Figure 6(d)).

Path selection

The path selection module determines the final path $p^{*}$ among candidate paths (Figure 6(e)) such that the following equation is satisfied:

p^{*} = \underset{p \in p}{a rg \min} [α (1 - R_{perc} (p)) + (1 - α) c_{goal} (p)],

(13)

where $R_{perc}$ is the reward related to the perception quality, $c_{goal}$ is the cost function for goal progress, and $α$ is the weighting factor to prioritize the perception quality. In this study, $R_{perc}$ and $c_{goal}$ are calculated only for the tip node of each candidate path to decrease the computational cost of $R_{perc}$ .

Reward for perception quality

Given candidate paths, the path selection module evaluates the perception quality based on the information about whether the feature points extracted in LiDAR-based SLAM can improve pose estimation accuracy. First, at each tip node of candidate paths, the path selection module chooses valid feature point that the UAV can see. We define the feature points scanned at a start node for every path planning as $F$ . As depicted in Figure 7, the valid feature points $K$ are subject to the following constraint:

(β_{\min} < β_{k} < β_{\max}) \land (r_{\min} < r_{k} < r_{\max}), k \in K \in F,

(14)

Figure 7.

Reliable measurement range of the 3D LiDAR sensor. The LiDAR-based SLAM algorithm extracts feature points (stars). In the local planning, the points are separated into valid (yellow) or invalid (gray).

where $β_{k}$ is the angle of the feature point $k$ from the LiDAR sensor, $β_{\min}$ and $β_{\max}$ are the minimum and maximum angle given by a vertical field of view of the 3D LiDAR, $r_{k}$ is the distance from the UAV to the feature point, and $r_{\min}$ and $r_{\max}$ are the minimum and maximum distances of a valid feature point, respectively. $r_{\min}$ is for the use of obstacle avoidance. $r_{\max}$ is based on the reliable measurement range of LiDAR because the accuracy of LiDAR decreases with increasing distance to the feature point.³⁷

Subsequently, we introduce a circular grid graph as in Figure 8 to consider the perception quality using the valid feature points. The grid graph enables the planner to handle sparse point cloud set efficiently similar to the FIF.²² The graph contains grids in radial and angular directions; and, each grid is true when it contains at least one valid feature point. The perception quality is calculated based on the number of true grids close to the UAV and the degrees of their scattering. The derivation of the circular grid is based on the following two core facts:

LiDAR measurement uncertainty decreases as the point cloud is scanned closer to the UAV, and

scattered feature points enable the LiDAR-based SLAM algorithm to decrease the localization error.

Figure 8.

Circular grid graph for the perception quality calculation. A grid in the graph becomes true (orange) if it contains at least one valid feature point (yellow stars).

According to the work,³⁷ the LiDAR uncertainty is subject to an large error for distance measurement. Hence, the feature points close to the UAV may be robust to pose estimation for the SLAM algorithm. In addition, as reported in,¹⁸ the features/constraints distributed in different directions, may avoid the degeneration of the SLAM algorithm. Certainly, based on the flight simulation in Figure 9, evenly-distributed feature points contribute to more accurate pose estimation than the feature points biased to one side as shown in Figure 10.

Figure 9.

UAV flight simulation in Gazebo with the PX4 Software. The simulation was performed for several seconds along with the red arrows. Left and right figures show an environment with scattered and gathered obstacles, respectively.

Figure 10.

Pose estimation error of the A-LOAM algorithm with respect to increasing traveling time.

Then, the reward related to the perception quality is defined as follows:

R_{perc} = \frac{\sum_{i = 0}^{N_{r} - 1} w_{i} Q_{i}}{\sum_{i = 0}^{N_{r} - 1} w_{i}},

(15)

where $N_{r}$ is the number of grids in the radial direction, $w_{i}$ is the constant weight to prioritize grids close to the UAV as LiDAR can accurately scan close feature points, and $Q_{i}$ is the perception quality for each concentric circle in the circular grid graph. They are given as follows:

w_{i} = N_{r} - i,

(16)

Q_{i} = \frac{\sum_{p, q} d_{p, q}}{2 r_{i} N_{θ}},

(17)

where $N_{θ}$ is the number of grids in the angular direction, and $d_{p, q}$ is the distance between two grids $p$ and $q$ in each concentric circle, where only all combinations of true grids are calculated. $d_{p, q}$ increases as one true grid is away from the other. Thus, $Q_{i}$ , which is the sum of $d_{p, q}$ , indicates how evenly distributed each true grid in circular grid graph is. $r_{i}$ is the radius of a concentric circle and is given by the following equation:

r_{i} = r_{\min} + \frac{r_{\max} - r_{\min}}{N_{r} - 1} i .

(18)

Note that we can calculate the FIM on each grid as in^9,21,22; however, to account for the degree of scattering of feature points, we introduced equations (15)–(18).

An example of the reward is shown in Figure 11 and Table 1. Comparing Figure 11(a) and (b), we can observe that the reward $R_{perc}$ is large as the number of true grids increases. The reward also increases when true grids are evenly-distributed through comparison between Figure 11(b) and (c). Furthermore, the perception quality $Q_{i}$ closer to the UAV contributes to biasing the reward based on Figure 11(d) to (f).

Figure 11.

Examples of the calculation of $R_{perc}$ when $N_{r} = 3$ and $N_{θ} = 8$ . Feature points (black dots) are given for each case. True (magenta) and false (blue) grids are shown: (a) Three grids are true, (b) Four grids are true, (c) Four scattered grids are true, (d) All grids in the circle of $r_{0}$ are true, (e) All grids in the circle of $r_{1}$ are true, and (f) All grids in the circle of $r_{2}$ are true.

Table 1.

Examples of the reward for the perception quality.

Case	$Q_{0}$	$Q_{1}$	$Q_{2}$	$R_{perc}$
Figure 11(a)	0.22	0.0	0.0	0.11
Figure 11(b)	0.41	0.0	0.0	0.20
Figure 11(c)	0.50	0.0	0.0	0.25
Figure 11(d)	1.0	0.0	0.0	0.50
Figure 11(e)	0.0	1.0	0.0	0.33
Figure 11(f)	0.0	0.0	1.0	0.17

Cost for goal progress

The cost function for goal progress expresses how close a path approaches a destination. First, we define the distance decrease to the goal as follows:

Δ l = l - l_{nom},

(19)

where $l$ is the distance between the goal and the tip node of a candidate path and $l_{nom}$ is the current distance between the goal and the start node for every path planning. In this study, the cost function is gradually varied from zero to one based on $Δ l$ , which is implemented using a sigmoid function. Additionally, the goal progress should be evaluated based on $l_{nom}$ as in the previous work.⁹ Therefore, we define the cost function for goal progress as follows:

c_{goal} = \frac{1}{1 + e^{- a Δ l}} {(\frac{l_{ref}}{l_{nom}})}^{k},

(20)

where $l_{ref}$ controls the area to be strongly attracted to the goal, $k$ controls how significantly the cost depends on the current distance, and $a$ tunes the form of the sigmoid function. An example of $c_{goal}$ at different $l_{nom}$ is shown in Figure 12.

Figure 12.

Cost function for goal progress when $l_{nom} = 5, 15, 100$ m. For the same $Δ l$ , the cost is higher when the UAV is close to the goal.

Simulation study and discussion

The offline and online processes in the proposed framework were implemented using MATLAB and the robot operating system,³⁸ respectively. An actual UAV in an experimental setup would be a promising approach for its demonstration; however, it is subject to the uncertainties in the sensing and control performance. Therefore, to verify the proposed framework, we prepared simulation environments in Gazebo supported with the PX4 software in the Loop simulation.³⁹ The UAV model is an extension of PX4 Vision,⁴⁰ replacing its camera with a 3D LiDAR (VLP-16) simulation model.⁴¹ Table 2 summarizes the parameters used for the simulation.

Table 2.

Parameters used in the numerical simulation.

Parameter	Section 7.1 and 7.2	Section 7.3	Unit
$C_{D}$	0.16		–
$A$	0.0627		$m^{2}$
$b$	0.286		m
$m$	1.5		kg
$D$	1.28		$kg / m^{3}$
$\| v_{0} \|$	2.0		m/s
$V_{th}$	3.0		m/s
$\hat{V}$	3.0		m/s
$Δ x_{th}^{-}$	50		m
$Δ x_{th}^{+}$	100		m
$p$	0.30		–
$g$	9.81		$m / s^{2}$
$X_{plan}$	10.0		m
$Y_{plan}$	10.0		m
$Z_{plan}$	10.0		m
$ϵ$	1.0		m
$N_{sample}$	500		–
$N_{node}$	5
$k$	0.5		–
$a$	1		–
$l_{ref}$	15.0	0.5 $l_{nom}$	m
$β_{\min}$	−5.0	−5.0	degrees
$β_{\max}$	15.0	15.0	degrees
$α$	0.8	0.7	–
$r_{\max}$	25.0	39.0	m
$r_{\min}$	4.0		m
$N_{θ}$	8		–
$N_{r}$	3	4	–

This section first shows the simulation result for the perception-aware local path planner. Subsequently, the result of the energy-aware global path planning is introduced. Finally, the practicality of the proposed framework is shown in a long-range flight scenario.

Local path planning result

According to the previous study,⁹ we highlight the effect of the proposed local planner through a comparison with a purely-reactive path planner ( $α = 0$ in equation (13)). Hence, we tested the reactive and proposed planners for three different scenarios; one of them are photorealistic 3D models referred from⁴² as in (12). Additionally, the path planning result was varied between different runs of the same setup because of the initialization procedure of the LiDAR-based SLAM module and randomness of the RRT^* algorithm. Therefore, we simulated five times for each scenario.

We evaluated each planner using two metrics: final position error and flight success rate. The final position error was calculated based on the result of A-LOAM and a true value obtained from the Gazebo simulator. The error was averaged without any obstacle collision and large position error (of more than 15 m). The success rate indicates that the UAV can fly the planned path without the flight failure.

The simulation results are summarized in Table 3. The flown path and time history of the position error are also shown in Figures 13 and 14. For simplicity, only three flight paths are depicted in the figures.

Table 3.

Results of final position error and flight success rate.

	Reactive		Proposed
Model	Avg. pos. err. [m]	Success rate	Avg. pos. err. [m]	Success rate
Scenario 1	6.12 ± 6.24	3/5	0.46 ± 0.14	5/5
Scenario 2	0.33 ± 0.06	5/5	0.62 ± 0.20	5/5
Scenario 3	3.57 ± 0.66	4/5	1.16 ± 0.70	5/5
Scenario 4	6.63 ± 1.12	2/5	2.64 ± 2.22	5/5

Figure 13.

Results of Gazebo simulation for Scenario 1–4. Flown paths overlaid on the top view of the environment. The results of the proposed planner (blue) and a purely-reactive path planner (red) are depicted. We illustrate the start and goal areas as yellow and orange circles, respectively: (a) Scenario 1, (b) Scenario 2, (c) Scenario 3, and (d) Scenario 4.

Figure 14.

Time history of the position error in Scenario 1–4: (a) Scenario 1, (b) Scenario 2, (c) Scenario 3, and (d) Scenario 4.

Scenarios 1 and 2 were the identical environments; however, we specified different goals for each scenario. In Scenario 1, the goal was specified beyond the objectless area in the upper part of the environment. While the UAV with the purely-reactive path planner attempted to move directly to the destination, our proposed planner encouraged the UAV to approach the obstacle-rich area. This implies that the proposed planner let the UAV to scan many feature points throughout the flight as equation (13) satisfies. Therefore, we observed the remarkable improvement of the position error as shown in Table 3.

In Scenario 2, the purely-reactive planner was also able to generate paths without the loss of pose estimation accuracy. Based on the result of the position error, it outperformed the proposed path planner. This is because the proposed planner encouraged the UAV to fly in the obstacle-rich area, resulting in a long flight distance. Essentially, the position error in the SLAM algorithm grows cumulatively as the flight distance increases. This point can be improved by dynamically tuning $α$ based on the environment; and, this is verified later on.

Scenario 3 consisted of an uneven mountainous terrain and riverside in the upper and middle parts of the environment, respectively. Although the purely-reactive planner successfully completed almost every flight, two trials of the simulation resulted in poor performance: one failed and the other caused a large position error. Conversely, the proposed planner steered the UAV to move along the riverside as shown in Figure 13(c), maintaining a small position error throughout the flight. We deduce that this is because the UAV can preferentially scan the mountainous area, where feature points are rich, rather than the riverside.

Scenario 4 consisted of the foot of a mountainous area with a flat texture-less area. The purely-reactive path planner failed in three trials of the simulation and the position error even in the successful cases was large. The proposed planner encouraged the UAV to fly along the foot of the mountain and succeeded in all trials. This result implies that the perception quality can be evaluated so that the accuracy of the pose estimation can be maintained even if the feature points are biased in a certain direction.

To verify the performance of the weighting factor, we tune $α$ to 0.27 and 0.53 for Scenario 2. Table 4 and Figure 15 show the result of the parameter turning. According to the result in the table, the positional error is reduced as the weighting factor decreases. We conclude the local planner works well in Scenario 2 when $α$ is less than 0.27. Further, the planner with lower $α$ generates a more straight path as shown in the figure. This implies that the tuning of the weighting factor reduced flight time and distance, resulting in the improved performance of the perception-aware planning. Hence, the proposed local planner can appropriately consider the perception quality for each environment by adjusting $α$ . Practically, this tuning is needed before UAV’s flight; however, the on-line planning can not adjust the best parameter for unknown environment. Future work would address how to automatically set the parameter.

Table 4.

Results of final position error and flight success rate for each value of $α$ .

$α$	Average positional error [m]	Success rate
0.0	0.33 ± 0.06	5/5
0.27	0.37 ± 0.07	5/5
0.53	0.47 ± 0.15	5/5
0.8	0.62 ± 0.20	5/5

Figure 15.

Result of Gazebo simulation for parameter tuning in Scenario 2. Flown paths overlaid on the top view of the environment. The results of $α = 0.8$ (blue), $α = 0.53$ (green), $α = 0.27$ (yellow), and $α = 0.0$ (red) are depicted. For simplicity, one flight path for each $α$ is only depicted in the figure. We illustrate the start and goal areas as yellow and orange circles, respectively.

Overall, the simulation results confirmed the performance of the proposed local path planning. The planner was able to fly the UAV with an 73% higher accuracy than the purely-reactive planner on average, except for Scenario 2. In every scenario, the UAV was able to reach the destination without any flight failures. Further, the parameter tuning can improve the performance of the local planning, resulting in the reduction of flight time and distance.

Global path planning result

For the global planning, we generated the wind map based on the deterministic method used by Mollov et al.⁴³ The spatiotemporal wind speed is modeled as follows:

v_{wind} = [v_{wind}^{x} v_{wind}^{y} v_{wind}^{z}]^{T},

(21)

\begin{matrix} v_{wind}^{i} (x, y, z, t) = v_{g}^{i} + v_{0}^{i} \\ + v_{0}^{i} \sum_{j = 1}^{3} A_{j}^{i} \sin (Ω_{j}^{i, x} x + Ω_{j}^{i, y} y + Ω_{j}^{i, z} z + ϕ_{j}^{i} t), \\ i = x, y, z, \end{matrix}

(22)

v_{0} = [v_{0}^{x} v_{0}^{y} v_{0}^{z}]^{T},

(23)

where $v_{0}^{i}$ is the average of the wind speed, $A_{j}^{i}$ is the amplitude of the $j$ -th harmonic, and $Ω_{j}^{i}$ and $ϕ_{j}^{i}$ are the frequencies of the $j$ -th harmonic for the space and time. $v_{g}^{i}$ describes the gust speed and is defined by the following equation:

v_{g}^{i} (t) = \frac{2 v_{g_{\max}}^{i}}{1 + \exp (- 4 \sin ϕ_{g}^{i} t + 4)},

(24)

where $v_{g_{\max}}^{i}$ is the maximum of the gust speed, and $ϕ_{g}^{i}$ is the frequency of the gust. We generated three different data sets: downward, upward, and sideways winds. Note that the wind speed data $v_{wind}$ is discretely acquired with the resolution $(200 m, 200 m, 50 m, 900 s)$ as in.²⁷

The global path planning results are shown in Figure 16(a) to (c). The energy consumption and flight time of the energy-aware path are also summarized in Table 5. The table also includes the result of the direct path, where the UAV directly flies from the start to the goal. As shown in Figure 16(a), we observed that the path is generated along the wind vector, resulting in the minimum values of the energy consumption and flight time among three cases. On the other hand, the UAV cannot fly along the wind vector in the upward and sideways scenarios. In the upward wind data, the proposed planner generated a nearly direct path to the goal area, enabling the UAV to reduce flight time and energy consumption. This can be confirmed through a comparison of the flight time of the proposed and direct paths. For the sideways wind, the vector from the start to the goal is in the opposite direction of the wind vector. Hence, the planned path deviates from the headwind and detours the area around $(x, y) = (400, 200)$ even with a longer flight time, which leads to a reduction in energy consumption.

Figure 16.

Results of the global path planning in three types of wind: (a) downward wind, (b) upward wind, and (c) sideways wind.

Table 5.

Estimated energy consumption and flight time for the proposed and direct paths.

	Energy consumption [kJ]		Flight time [s]
Wind type	Proposed path	Direct path	Proposed path	Direct path
Downward	28.7	30.0	209	217
Upward	29.8	31.4	222	220
Sideways	29.4	30.3	234	220

While the usefulness of the energy-efficient global planner is shown in the previous work,²³ this paper verifies the planner using the high-fidelity simulator. The Gazebo simulation framework was employed again to evaluate the global path in the sideways wind, which is the most critical scenario among the three types of wind environments. The wind plugin was exploited to express the wind effect in the Gazebo simulator. The UAV directly tracked each waypoint at 3.0 m/s. The energy consumption was calculated based on the thrust force of four motors of the UAV.⁴⁴ Each thrust was measured by the Gazebo force sensor plugin.⁴⁵ Table 6 shows the result of the simulation.

Table 6.

Result of the verification test in the sideways wind.

Energy consumption [kJ]		Power consumption [kW]
Proposed path	Direct path	Proposed path	Direct path
82.8	82.9	353.8	376.8

We can observe only a slight reduction of the energy consumption as compared with the improvement of Table 5. We deduce that this is because equation (2) does not accurately estimate the energy consumption in UAV’s actual motions. For instance, the proposed path required the UAV to turn around $(x, y) = (400, 200)$ . Such turn motions involve the acceleration and deceleration of the UAV’s motors, resulting in the underestimation of the energy consumption in equation (2). On the other hand, the power consumption is significantly improved. This result implies that the global planner enables the UAV to avoid the headwind effect, which leads to the energy-efficient flight in the wind environment. Further decrease in energy consumption is expected on long flights.

Long-range flight demonstration

This subsection demonstrates the practicality of the local and global path planners in a long-range flight scenario. The simulation assumes the mountainous area and the sideways wind scenario. The UAV flies toward each waypoint generated by the energy-aware global planner (Figure 16(c)). The perception-aware local planner sequentially performed for each waypoint. However, during the flight simulation, each waypoint was relocated to avoid the area where the SLAM algorithm fails. Intuitively, the SLAM algorithm would work well when the onboard LiDAR can adequately scan and cover terrain surfaces. For that, we controlled the altitude of the waypoints upward and downward. The planned and modified waypoint sets are shown in Figure 17. The local planner generated the local path toward the modified waypoints (red circles) in the figure. Figure 18 and Table 7 show the result of the simulation.

Figure 17.

Relationship between the modified waypoint set and the global path planning result. The start point is (600, 600, 190) and the goal point is (200, 200, 60).

Figure 18.

Result of Gazebo simulation for a long-range flight scenario. Flown paths overlaid on the top view of the environment. We illustrate the start and goal areas as yellow and red pinpoints, respectively.

Table 7.

Results of Gazebo simulation in a long-range flight scenario.

Energy consumption [kJ]	455
Actual flight time [s]	1278
Actual flight time – Expected flight time (Table 5) [s]	1044

We can observe that the proposed navigation framework enables the UAV to reach the global goal without flight failure. The simulation result verified that the local path planner sequentially works well. According to Table 7, however, the energy consumption is six times larger than that of Table 6. We deduce that this is because the UAV flew along the perception-aware local paths, thus increasing the flight distance and time. The UAV intended to deviate from the straight path between two waypoints to maintain the perception quality without large positional errors. Comparing the global planning and Gazebo simulation results, the difference between the actual and expected flight time is about 1000 s. The trade-off of perception-awareness and flight distance would be improved by tuning $α$ as shown in the local path planning result accordance with an environment.

We tune the weighting factor $α$ for the long-range flight scenario as well. For each flight between two waypoints, $α$ is changed in the range [0.1, 0.4, 0.7]. Figure 19 shows the relationship between $α$ and energy consumption for each waypoint. Between the waypoint #1 and #2, the perception-aware planner with $α = 0.7$ kept the UAV maintaining the perception quality, resulting in an increase of energy consumption. When $α$ is 0.1, the energy consumption is minimized. This implies that tuning $α$ contributes to not only the accuracy of pose estimation but also UAV’s energy consumption. Between the waypoint #2 and #3, the planner with $α = 0.1$ failed the flight owing to the localization error. Alternatively, we can observe that the planner with $α = 0.4$ improved the energy consumption 27% as compared with that with $α = 0.7$ . However, between the waypoint #3 and #4, the planner with $α = 0.4$ failed its flight. Therefore, to avoid the flight failure, $α$ should be determined based on the environment around a waypoint. For instance, lower $α$ is preferable for landmark-rich areas, enabling the UAV to save energy consumption. On the other hand, higher $α$ maintains the perception quality even in a feature-less area. As long as we tune this sensitive parameter, the proposed framework can plan the energy-efficient path regarding on the local planning while maintaining the perception-quality.

Figure 19.

Energy consumption for each value of the weighting factor $α$ in a long-range flight scenario.

Conclusion

In this study, we have presented the energy and perception aware planning and navigation framework for UAVs in GNSS-denied environments and spatiotemporal wind. The proposed framework integrates the energy efficient global path planner with the perception-aware local path planner. We validated the local and global planners in the simulation study. The proposed local planning performed the improvement of pose estimation accuracy, except for Scenario 2. The parameter study showed the weighting factor for the perception quality can be adjust for each environment, which leads to optimize the pose accuracy and flight time. The global path planner generated the energy efficient waypoint set, which can be along the wind vector and deviate from the headwind. The high-fidelity simulator with the wind plugin validated that the global planner performed well even in the critical environment. Finally, the overall framework was entirely verified in a long-range flight scenario, where the local path planner sequentially worked well without flight failure. Additionally, we found that the sensitive parameter for our framework, which is not only critical for the perception quality, but also for the energy consumption. Once the parameter is preferably adjusted according to each flight environment (i.e. lower $α$ is preferable for landmark-rich areas), our navigation framework can optimize the energy consumption in terms of local planning without losing pose estimation accuracy.

Future work would include the automation of the parameter tuning. A possible solution is a machine learning approach, which models the relationship between the optimal $α$ and environment. In on-line path planning, the learned model outputs the optimal parameter.

The extension of the global planner is also of interest so that the LiDAR can scan feature-rich area. Although the 3D environmental information cannot be obtained prior to the UAV’s flight, the global map can be updated based on the feedback information from the online control. The global path is then replanned using the updated map with 3D geometrical information, allowing the UAV to approach more perceptible areas. This would improve our poor way to relocate waypoint set for the local path planner.

Footnotes

Handling Editor: Chenhui Liang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Reiya Takemura

References

Huang

Teo

RSH

Tan

KK.

Collision avoidance of multi unmanned aerial vehicles: a review. Annu Rev Control 2019; 48: 147–164.

Thibbotuwawa

Bocewicz

Radzki

, et al. UAV mission planning resistant to weather uncertainty. Sensors 2020; 20: 515.

Yacef

Rizoug

Degaa

, et al. Energy-efﬁciency path planning for quadrotor UAV under wind conditions. In: 7th international conference on control, decision and information technologies (CoDIT), Prague, Czech Republic, 2020, pp. 1133–1138. New York: IEEE.

Miller

Stepanyan

Miller

, et al. 3D path planning in a threat environment. In: IEEE conference on decision and control (CDC-ECC), Orlando, FL, USA, 2011, pp. 6864–6869. New York: IEEE.

Hart

Nilsson

Raphael

A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 1968; 4: 100–107.

Otte

Silva

Frew

Any-time path-planning: time-varying wind field + moving obstacles. IEEE International Conference on Robotics and Automation (ICRA), 2016, pp. 2575–2582. https://ieeexplore.ieee.org/document/7487414

Teixeira

Alzugaray

Chli

Autonomous aerial inspection using visual-inertial robust localization and mapping. Field Serv Robot Springer Proc Adv Robot 2018; 5: 191–204.

Qin

Shen

VINS-mono: a robust and versatile monocular visual-inertial state estimator. IEEE Trans Robot 2018; 34: 1004–1020.

Zhang

Scaramuzza

. Perception-aware receding horizon navigation for MAVs. In: IEEE international conference on robotics and automation (ICRA), 2018, pp. 2534–2541. New York: IEEE.

10.

Murali

Spasojevic

Guerra

, et al. Perception-aware trajectory generation for aggressive quadrotor ﬂight using differential ﬂatness. In: IEEE American Control Conference (ACC). Institute of Electrical and Electronics Engineers Inc., Philadelphia, PA, USA, 2019, pp. 3936–3943. New York: IEEE.

11.

Spasojevic

Murali

Karaman

. Perception-aware time optimal path parameterization for quadrotors. In: IEEE international conference on robotics and automation (ICRA), 2020, pp. 3213–3219. New York: IEEE.

12.

Bartolomei

Teixeira

Chli

. Perception-aware path planning for UAVs using semantic segmentation. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020, pp. 5808–5815. New York: IEEE.

13.

Zhang

Singh

Laser-visual-inertial odometry and mapping with high robustness and low drift. J Field Robot 2018; 35: 1242–1264.

14.

Milijas

Markovic

Ivanovic

, et al. A comparison of LiDAR-based SLAM systems for control of unmanned aerial vehicles. In: International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 2021, pp. 1148–1154. New York: IEEE.

15.

Zhang

Singh

LOAM: lidar Odometry and mapping in real-time. Robot Sci Syst 2014; 2: 1–9.

16.

Chen

Liu

Tightly coupled 3D lidar inertial odometry and mapping. In: International conference on robotics and automation (ICRA), Montreal, QC, Canada, 2019, pp. 3144–3150. New York: IEEE.

17.

Shan

Englot

Meyers

, et al. LIO-SAM: tightly-coupled lidar inertial odometry via smoothing and mapping. In: 2020 IEEE/RSJ international conference on intelligent robots and systems (IROS), Las Vegas, NV, USA, 2020, pp. 5135–5142. New York: IEEE. https://ieeexplore.ieee.org/document/9341176

18.

Zhang

Kaess

Singh

. On degeneracy of optimization-based state estimation problems. In: IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016. pp. 809–816.

19.

Zhen

Scherer

. Estimating the localizability in tunnel-like environments using LiDAR and UWB. In: IEEE international conference on robotics and automation (ICRA)2019; 4903–4908. New York: IEEE.

20.

Jiao

Zhu

, et al. Greedy-based feature selection for efﬁcient LiDAR SLAM. In: IEEE international conference on robotics and automation (ICRA), 2021. pp. 5222–5228. New York: IEEE.

21.

Zhou

Yao

Lidar/UWB fusion based SLAM with anti-degeneration capability. IEEE Trans Vehicular Technol 2021; 70: 820–830.

22.

Zhang

Chadha

, et al. Falco: fast likelihood-based collision avoidance with extension to human-guided navigation. J Field Robot 2020; 37: 1300–1313.

23.

Aoki

Ishigami

Energy-efficient path planning for UAV using Spatiotemporal Wind Model. J Rob Soc Jpn 2022; 40: 255–258.

24.

Takemura

Ishigami

Computationally efficient and sub-optimal trajectory planning framework based on trajectory-quality growth rate analysis. Front Rob AI 2022; 9: 1–15.

25.

Bai

Jiang

Cui

, et al. UAV path planning based on improved A* and DWA Algorithms. Int J Aerosp Eng 2021; 2021: 1–12.

26.

Tang

Miao

Barnawi

, et al. A joint global and local path planning optimization for UAV task scheduling towards crowd air monitoring. Comput Netw 2021; 193: 1–15.

27.

National Oceanic and Atmospheric Administration. 2023. https://psl.noaa.gov/data/gridded/ (accessed 10 May 2022).

28.

Park

Receding-horizon RRT-Infotaxis for autonomous source search in urban environments. Aerosp Sci Technol 2022; 120: 1–13.

29.

Kularatne

Bhattacharya

Hsieh

MA.

Optimal path planning in time-varying flows using adaptive discretization. IEEE Robot Autom Lett 2018; 3: 458–465.

30.

Qin

Cao

. Advanced implementation of loam, 2018. https://github.com/HKUST-Aerial-Robotics/A-LOAM (accessed 7 February 2022).

31.

Velodyne Lidar Inc. Velodyne LiDAR PUCK, 2019. https://velodynelidar.com/products/puck/ (accessed 8 February 2022).

32.

De Berg

Cheong

Van Kreveld

, et al. Computational geometry: Algorithms and applications. 3rd ed. Heidelberg: Springer, 2008.

33.

Karaman

Frazzoli

Sampling-based algorithms for optimal motion planning. Int J Rob Res 2011; 30: 846–894.

34.

Thibbotuwawa

Nielsen

Zbigniew

, et al. Energy consumption in unmanned aerial vehicles: a review of energy consumption models and their relation to the UAV routing. In: International conference on information systems architecture and technology, 2019, vol. 853, pp. 173–184. Cham: Springer.

35.

Lee

Song

Shim

. Optimal path planning based on spline-RRT* for fixed-wing UAVs operating in three-dimensional environments. In: 2014 14th International conference on control, automation and systems (ICCAS 2014), Gyeonggi-do, Korea (South), 2014, pp. 835–839. New York: IEEE.

36.

Mechali

Wei

, et al. A rectiﬁed RRT* with efﬁcient obstacles avoidance method for UAV in 3D environment. In: IEEE international conference on cyber technology in automation, control and intelligent systems, 2019, pp. 480–485. New York: IEEE.

37.

Tanaka

Ishigami

. Modeling of LiDAR Measurement Uncertainty for Rover Path Planning. In: The international symposium on artiﬁcial intelligence, robotics and automation in space, Beijing, China, June 20–22, 2016. https://www.esa.int/Enabling_Support/Space_Engineering_Technology/Automation_and_Robotics/i-SAIRAS

38.

Quigley

Gerkey

Conley

, et al. ROS: an open-source robot operating system. In: ICRA Workshop on Open Source Software, Kobe, Japan, 2009. New York: IEEE.

39.

PX4 Development Team, “PX4 Autopilot User Guide,” 2023. https://docs.px4.io/master/en/ (accessed 8 February, 2022).

40.

PX4 Development Team, “Airframes Reference,” 2022. https://docs.px4.io/main/en/airframes/airframe_reference.html (accessed 10 February 2022).

41.

Dataspeed INC. “velodyne simulator,”2022. https://bitbucket.org/DataspeedInc/velodyne_simulator/src/master/ (accessed 10 February 2022).

42.

Sketchfab. “Sketchfab 3d-models.”2018. https://sketchfab.com/feed (accessed 10 February 2022).

43.

Mollov

Kralev

Slavov

, et al. μ-Synthesis and hardware-in-the-loop simulation of miniature helicopter control system. J Intell Robot Syst 2014; 76: 315–351.

44.

T-MOTOR, “F60 PRO III”. 2019. https://uav-en.tmotor.com/2019/Motor_0109/197.html (accessed 30 May 2022).

45.

Open Source Robotics Foundation, “Force/Torque Sensor.” 2020. https://classic.gazebosim.org/tutorials?tut=force_torque_sensor&cat=sensors (accessed 28 May 2022).

Energy-and-perception-aware planning and navigation framework for unmanned aerial vehicles

Abstract

Keywords

Introduction

Problem statement

System overview

Energy-aware global planner

Cost and heuristic functions

Variable-resolution grid

Search graph structure

Search algorithm

Perception-aware local planner

Tree generation

Path selection

Reward for perception quality

Cost for goal progress

Simulation study and discussion

Local path planning result

Global path planning result

Long-range flight demonstration

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References