Grid based path search method for UAV delivery operations in urban environment

Abstract

The present invention provides a method for planning a shortest possible three-dimensional path for autonomous flying robots to traverse from one location to the other in a geographical region, including translating a three-dimensional (3D) environment, discretizing the 3D environment into a graph of many grid cells or nodes, employing a modified any-angle path planning algorithm to calculate non-uniform traversal cost of each grid cell and by averaging the total traversal costs along the path to shorten the corresponding computation time, whilst incorporating operational costs other than the traversal cost specific to the autonomous flying robots to be traversed. The shortest possible path found by the present method does not only consider the path length, but also takes different costs of traversing and operating the flying robots into account, which increases its feasibility and flexibility to be applied in a wide variety of situations and technological areas.

Claims

1. A computer-implemented method for planning an optimal three-dimensional path for autonomous flying robots to traverse from one location to the other in a geographical region and for controlling the autonomous flying robots to fly along the optimal three-dimensional path, including: translating the geographical region into a three-dimensional environment, by a computer processor; discretizing the three-dimensional environment into a graph comprising a plurality of three-dimensional cells or nodes, by the computer processor; deriving a path between a first node and a last node in the graph to be traversed by the autonomous flying robots, by the computer processor; assigning a weighting factor to each of the nodes, the weighting factor being associated with traversal cost of the autonomous flying robots in each of the nodes, and calculating the traversal cost of the autonomous flying robots from one node to the other along the path, by the computer processor; checking line-of-sight between the first node and the last node of the path, by the computer processor; adding other costs into an any-angle path planning algorithm and approximating thereof to generate a natural and smooth path compatible with vehicle dynamics of the autonomous flying robots in order to obtain the optimal three-dimensional path of the autonomous flying robots between two locations in the geographical region, by the computer processor, wherein the optimal three-dimensional path is stored in computer-readable storage media, wherein the other costs of the path include turning costs of the autonomous flying robots between two consecutive segments within the path, as well as climbing costs and descending costs of the autonomous flying robots at one or more segments within the path, respectively, wherein the turning costs of the autonomous flying robots comprise the costs involved in adjusting, meeting or overcoming horizontal turning angle, adjacent turning distance, and consecutive turning decay of the autonomous flying robots, wherein the climbing or descending costs comprise the costs involved in adjusting, meeting or overcoming climbing or descending angle, linear weight cost multiplier, climbing or descending angle threshold of the autonomous flying robots; and controlling an objective autonomous flying robot to fly along the optimal three-dimensional path by the method.

2. The method of claim 1, wherein the autonomous flying robots comprise unmanned aerial vehicles (UAVs), micro aerial vehicles (MAS), and alike used in unmanned aerial system (UAS).

3. The method of claim 1, wherein the calculation of the traversal cost is based on an approximation method that the traversal cost of a path is an average cost of the traversed cells on the path.

4. The method of claim 1, wherein the cell size is assumed to substantially zero when calculating the traversal cost.

5. The method of claim 1, wherein the other costs of the path is calculated by converting the path into a plurality of segments each representing a partial path to be traversed by the autonomous flying robots, determining relative horizontal and/or vertical orientations of the autonomous flying robots between every two consecutive segments, and calculating the costs in addition to the traversal cost of the path on changing the autonomous flying robots from one orientation to the other according to the determined relative horizontal and/or vertical orientations between the two consecutive segments.

6. The method of claim 1, wherein the other costs of the path are added into the any-angle path planning algorithm as corresponding terms to heuristics of the algorithm.

7. The method of claim 1, wherein the shortest possible three-dimensional path is calculated according to the following equations: $\begin{array}{cc}f\left(\mathrm{cell}\right)=\frac{1}{\mathrm{size}\left(S\right)}{.Math.\mathrm{lineSegment}\left(\mathrm{cell},\mathrm{parent}\left(\mathrm{cell}\right)\right).Math.}_2& \left(4\right)\end{array}$ $\begin{array}{cc}\underset{cS}{.Math.}(\mathrm{costCoef}\left(c\right)& \left(5\right)\end{array}$ $\begin{array}{cc}S=\mathrm{voxelTraversal}\left(\mathrm{cell},\mathrm{parent}\left(\mathrm{cell}\right)\right)& \left(6\right)\end{array}$ wherein f(cell) is an estimate of the length of a shortest path from a parent grid cell to a grid cell on a line segment of the path in the graph.

8. The method of claim 7, further comprising penalizing paths inducing unnecessary or excessive turns for the autonomous flying robots according to the following equations: $\begin{array}{cc}f\left(s\right)+g\left(s\right)+h\left(s\right)+t\left(s\right)& \left(7\right)\end{array}$ $\begin{array}{cc}t\left(s\right)={}_{t}t\left(\mathrm{parent}\left(s\right)\right)+\left(s\right)\left(1+e^{\frac{.Math.{}_1.Math.}{d_0}}\right)& \left(8\right)\end{array}$ $\begin{array}{cc}\left(s\right)=.Math.\arccos \left(\frac{l_1.Math.l_2}{.Math.l_1.Math..Math.l_2.Math.}\right).Math.& \left(9\right)\end{array}$ $\begin{array}{cc}{l}_1=s-\mathrm{parent}\left(s\right)& \left(10\right)\end{array}$ $\begin{array}{cc}{l}_2=\mathrm{parent}\left(s\right)-\mathrm{parent}\left(\mathrm{parent}\left(s\right)\right)& \left(11\right)\end{array}$ wherein (s) represents a linear function of the turning angle between every two consecutive line segments of the path; is the linear weight which is tunable as a trade-off between path length and turning cost of the autonomous flying robots, and wherein assuming each turn is very close to a consecutive turn, if previous segment length l.sub.1 is sufficiently short, it will be penalized, and wherein a decay factor .sub.t is added to the calculation of the turning cost in the parent cell when there is/are consecutive turn(s).

9. The method of claim 8, wherein the other costs are calculated by the following equations: $\begin{array}{cc}f\left(s\right)+g\left(s\right)+h\left(s\right)+t\left(s\right)+c\left(s\right)& \left(12\right)\end{array}$ $\begin{array}{cc}c\left(s\right)={}_c\left(s\right).Math.l_1.Math.& \left(13\right)\end{array}$ $\begin{array}{cc}\left(s\right)=\{\begin{array}{cc}.Math.\arcsin \left(\frac{l_1.Math.n}{.Math.l_1.Math.}\right).Math.& \mathrm{penalize}\mathrm{climbing}\mathrm{and}\mathrm{descending}\\ \arcsin \left(\frac{l_2.Math.n}{.Math.l_1.Math.}\right)& \mathrm{penalize}\mathrm{climbing}\end{array}& \left(14\right)\end{array}$ $\begin{array}{cc}{l}_1=s-\mathrm{parent}\left(s\right)& \left(15\right)\end{array}$ $\begin{array}{cc}n=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]& \left(16\right)\end{array}$ wherein g(s) represents the length of the shortest path from start vertex parent(s) to vertex s, and thereby being an estimated start distance of vertex s; h(s) represents an estimated goal distance of vertex s; t(s) represents the traversal cost obtained from Eq. (8); c(s) represents other costs in addition to t(s) during operation of the autonomous flying robots.

10. The method of claim 9, wherein the cost function obtained by Eq. (13) is changed to a piece-wise function as follows: $\begin{array}{cc}c\left(s\right)=\{\begin{array}{cc}{}_c\left(s\right).Math.l_1.Math.& \left(s\right){}_c\\ +& \left(s\right)>{}_c\end{array}& \left(17\right)\end{array}$ wherein the other costs involved in adjusting climb or descending angle of the autonomous flying robots c(s) traversing from the start vertex to vertex s do not exceed an absolute threshold .sub.c, and wherein s and parent(s) are considered to be located in two different terminal areas where the autonomous flying robots takes off from and lands to, respectively, in order not to overwhelm the other costs.

11. The method of claim 1, wherein objects and/or obstacles with a uniform shape and location in the geographical region are converted into convex polyhedrons or polygons in the graph after said translating and prior to said discretizing into the plurality of cells or nodes.

12. A computer-implemented method for planning an optimal three-dimensional path for autonomous flying robots to traverse from one location to the other in a geographical region and for controlling the autonomous flying robots to fly along the optimal three-dimensional path, including: translating the geographical region into a three-dimensional environment, by a computer processor; discretizing the three-dimensional environment into a graph comprising a plurality of three-dimensional cells or nodes, by the computer processor; deriving a path between a first node and a last node in the graph to be traversed by the autonomous flying robots, by the computer processor; assigning a weighting factor to each of the nodes, the weighting factor being associated with traversal cost of the autonomous flying robots in each of the nodes, and calculating the traversal cost of the autonomous flying robots from one node to the other along the path, by the computer processor; checking line-of-sight between the first node and the last node of the path, by the computer processor; adding other costs into an any-angle path planning algorithm and approximating thereof to generate a natural and smooth path compatible with vehicle dynamics of the autonomous flying robots in order to obtain the optimal three-dimensional path of the autonomous flying robots between two locations in the geographical region, by the computer processor, wherein the optimal three-dimensional path is stored in computer-readable storage media, wherein the other costs of the path include costs at least associated with turning costs of the autonomous flying robots between two consecutive segments within the path and involved in adjusting, meeting or overcoming horizontal turning angle, adjacent turning distance, and consecutive turning decay of the autonomous flying robots; and controlling an objective autonomous flying robot to fly along the optimal three-dimensional path by the method.

13. The method of claim 12, wherein the cell size is assumed to substantially zero when calculating the traversal cost.

14. The method of claim 12, wherein the other costs of the path are added into the any-angle path planning algorithm as corresponding terms to heuristics of the algorithm.

15. A computer-implemented method for planning an optimal three-dimensional path for autonomous flying robots to traverse from one location to the other in a geographical region and for controlling the autonomous flying robots to fly along the optimal three-dimensional path, including: translating the geographical region into a three-dimensional environment, by a computer processor; discretizing the three-dimensional environment into a graph comprising a plurality of three-dimensional cells or nodes, by the computer processor; deriving a path between a first node and a last node in the graph to be traversed by the autonomous flying robots, by the computer processor; assigning a weighting factor to each of the nodes, the weighting factor being associated with traversal cost of the autonomous flying robots in each of the nodes, and calculating the traversal cost of the autonomous flying robots from one node to the other along the path, by the computer processor; checking line-of-sight between the first node and the last node of the path, by the computer processor; adding other costs into an any-angle path planning algorithm and approximating thereof to generate a natural and smooth path compatible with vehicle dynamics of the autonomous flying robots in order to obtain the optimal three-dimensional path of the autonomous flying robots between two locations in the geographical region, by the computer processor, wherein the optimal three-dimensional path is stored in computer-readable storage media, wherein the other costs of the path include costs at least associated with climbing costs and descending costs of the autonomous flying robots at one or more segments within the path, respectively, wherein the climbing or descending costs comprise the costs involved in adjusting, meeting or overcoming climbing or descending angle, linear weight cost multiplier, climbing or descending angle threshold of the autonomous flying robots; and controlling an objective autonomous flying robot to fly along the optimal three-dimensional path by the method.

16. The method of claim 15, wherein the cell size is assumed to substantially zero when calculating the traversal cost.

17. The method of claim 15, wherein the other costs of the path are added into the any-angle path planning algorithm as corresponding terms to heuristics of the algorithm.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Embodiments of the invention are described in more details hereinafter with reference to the drawings, in which:

(2) FIG. 1 schematically depict how path is found by Theta* and Lazy Theta* on expanded grids and how many line-of-sight is/are checked by each of the algorithms;

(3) FIG. 2 illustrates how to check line-of-sight between two expanded cells according to three-dimensional voxel traversal (top panel) and corresponding projections onto two-dimensional plane (bottom left panel represents x-y plane; bottom right panel represents x-z plane) of the path found by Theta* or Lazy Theta*;

(4) FIG. 3 illustrates a modified any-angle path planning method incorporated with non-uniform traversal cost of each traversed cells for optimal path finding;

(5) FIG. 4 schematically depicts a conventional method to segment a known path for calculation of the total traversal cost along the path;

(6) FIG. 5 shows path comparison by Theta* algorithm to compare the two adjacent paths with the new path as shown in FIG. 3;

(7) FIG. 6 shows path comparison by Lazy Theta* algorithm to approximate cost of the new path by using the longer adjacent path instead of the shorter adjacent path as shown in FIG. 3;

(8) FIG. 7 illustrates how large is the area of an urban environment where a test is conducted according to an embodiment of the present invention;

(9) FIG. 8 illustrates what elements in a three-dimensional environment and how they are abstracted and approximated in a test of the present method according to an embodiment of the present invention; and

(10) FIG. 9 illustrates a layer of a plurality of grids discretized from the three-dimensional environment similar to that as shown in FIG. 8, where different colors (gradings) represent different traversal cost of each grid cell.

DETAILED DESCRIPTION OF THE INVENTION

(11) In the following description, systems and methods for path planning for traversal of autonomous and unmanned vehicles and the likes are set forth as preferred examples. It will be apparent to those skilled in the art that modifications, including additions and/or substitutions may be made without departing from the scope and spirit of the invention. Specific details may be omitted so as not to obscure the invention; however, the disclosure is written to enable one skilled in the art to practice the teachings herein without undue experimentation.

(12) It should be apparent to practitioner skilled in the art that the foregoing examples of the system and method are only for the purposes of illustration of working principle of the present invention. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed.

(13) As compared to A* algorithm, by using some any-angle path planning algorithms like Theta*, paths can be found without constrains to headings of the paths; Lazy Theta* can even reduce the time of line-of-sight checks and generate substantially identical result to that from Theta*, only the path length may be longer by using Lazy Theta*. As shown in FIG. 1, the key difference between Theta* (left panel) and Lazy Theta* (right panel) can be found in terms of the number of line-of-sight checks, which is defined by the number of neighboring cells the solid arrows have crossed, where the corresponding path found by each of the algorithms is represented by the broken arrow. The total number of line-of-sight checks by Theta* is 15 while that by Lazy Theta* is just 4 in this example because Lazy Theta* adopts lazy evaluation to only perform one line-of-sight check per expanded grid cell, as compared to Theta* which performs line-of-sight check for each of the unexpanded visible neighboring grid cells of the currently expanded grid cell. However, Lazy Theta* increases the number of cell expansions, and thereby potentially lengthens the resulting path.

(14) Incorporation of Non-Uniform Traversal Cost of Flying Robots into Path Finding

(15) FIG. 3 illustrates how to determine an optimal path from one node to the other based on calculating the non-uniform traversal cost. Theta* basically finds paths on grids that contain unblocked cells with uniform traversal costs. In that case, the true shortest path found by Theta* have heading changes only at the corners of the blocked cells and the triangle inequality holds. If non-uniform traversal cost is incorporated into the calculation of the path finding, it will no longer unconditionally choose the true shortest path based on path length but will be based on the path costs. To do so, the algorithm needs to compare the non-uniform traversal cost in each grid which overlap with the path and those with its adjacent paths. In this example, three different paths are compared: a first one from parent (adj) to adj; a second one from parent (current) to current to adj; a third one from parent (current) to adj. However, by computing and calculating non-uniform traversal cost as such, the true shortest paths may still have heading changes at the boundaries between unblocked cells having different traversal costs, and therefore the triangle inequality no longer holds.

(16) FIG. 4 shows an example of how a path is segmented for calculation of the traversal cost during line-of-sight check by Theta*. The calculation uses Cohen-Sutherland clipping algorithm (Foley et al., 1992) from computer graphics. The straight line in this figure represents the path, and it is segmented into several line segments (I.sub.0, I.sub.1, I.sub.2, . . . ) at the points where it intersects with the boundaries of the cells from C1 to A6 vertices. The path cost of the path along C1A6 based on this calculation method is the sum of the costs of each line segment I.sub.iI.sub.i+1 and the cost of each line segment is the product of its length and the traversal cost of the corresponding unblocked cell.

(17) Approximation of Average Non-Uniform Traversal Cost

(18) Both Theta* and Lazy Theta* have to perform line-of-sight check, they have to go through a voxel traversal process between two examined cells and to check whether every traversed cell is accessible to the flying robots (FIG. 2). Also, because special areas in an urban environment such as densely populated area and desired flying zones within where the cost of every cell overlapping with the path also need to be considered, if the non-uniform traversal costs of each of the blocks on the line segments had to be calculated, the computation would have been very time-consuming, as follows:

(19) $\begin{array}{cc}f\left(\mathrm{cell}\right)=\underset{cS}{.Math.}\mathrm{costCoef}\left(c\right)& \left(1\right)\end{array}$$\begin{array}{cc}{.Math.\mathrm{lineSegment}\left(\mathrm{cell},\mathrm{parent}\left(\mathrm{cell}\right)\right).Math.c.Math.}_2& \left(2\right)\end{array}$$\begin{array}{cc}S=\mathrm{voxelTraversal}\left(\mathrm{cell},\mathrm{parent}\left(\mathrm{cell}\right)\right).& \left(3\right)\end{array}$

(20) Therefore, the present invention incorporates an approximation method to calculate the traversal cost into the existing algorithm to result in a modified Lazy Theta*, as follows:

(21) $\begin{array}{cc}f\left(\mathrm{cell}\right)=\frac{1}{\mathrm{size}\left(S\right)}{.Math.\mathrm{lineSegment}\left(\mathrm{cell},\mathrm{parent}\left(\mathrm{cell}\right)\right).Math.}_2& \left(4\right)\end{array}$$\begin{array}{cc}\underset{cS}{.Math.}(\mathrm{costCoef}\left(c\right)& \left(5\right)\end{array}$$\begin{array}{cc}S=\mathrm{voxelTraversal}\left(\mathrm{cell},\mathrm{parent}\left(\mathrm{cell}\right)\right).& \left(6\right)\end{array}$

(22) Instead of calculating the product of the precise length of each segment and the associated traversal cost, the present invention proposes calculating an average cost of the traversed cells on the path and thereby defining the average cost as the path cost. By this approximation method, the computation time is significantly reduced, and the cost on overlapping calculation is not saved. However, the path length may be increased or accuracy may be reduced. To alleviate the negative effect of these shortcomings, grid size is significantly reduced to substantially zero during computation.

(23) Turning Cost

(24) UAVs consume more energy when performing turns, thus, the present invention further incorporates penalty to penalize paths with unnecessary or excessive turns, in addition to the average non-uniform traversal cost among the traversed cells along the path as path cost, as follows:

(25) $\begin{array}{cc}f\left(s\right)+g\left(s\right)+h\left(s\right)+t\left(s\right)& \left(7\right)\end{array}$$\begin{array}{cc}t\left(s\right)={}_{t}t\left(\mathrm{parent}\left(s\right)\right)+\left(s\right)\left(1+e^{\frac{.Math.{}_1.Math.}{d_0}}\right)& \left(8\right)\end{array}$$\begin{array}{cc}\left(s\right)=.Math.\arccos \left(\frac{l_1.Math.l_2}{.Math.l_1.Math..Math.l_2.Math.}\right).Math.& \left(9\right)\end{array}$$\begin{array}{cc}{l}_1=s-\mathrm{parent}\left(s\right)& \left(10\right)\end{array}$$\begin{array}{cc}{l}_2=\mathrm{parent}\left(s\right)-\mathrm{parent}\left(\mathrm{parent}\left(s\right)\right)& \left(11\right)\end{array}$

(26) The turning cost is considered as a linear function of the turning angle (s) between every two consecutive segments; the linear weight is tunable to trade-off between path length and path turning; assuming turns are very close to each other, short previous segment length l.sub.1 is penalized; a decay factor .sub.t is added to the turning cost of the parent cell in consideration of consecutive turns.

(27) Climbing or Descending Cost:

(28) Climb cost is calculated for en-route section because take-off and landing from or to a terminal area by some of the flying robots such as UAV require a large absolute climb/descending angle, resulting in a large climb/descending cost. Hence, in the following equations, both s and parent(s) are considered to be located in different terminal areas in order not to overwhelm the other costs, in addition to the non-uniform traversal cost for optimal path finding:

(29) $\begin{array}{cc}f\left(s\right)+g\left(s\right)+h\left(s\right)+t\left(s\right)+c\left(s\right)& \left(12\right)\end{array}$$\begin{array}{cc}c\left(s\right)={}_c\left(s\right).Math.l_1.Math.& \left(13\right)\end{array}$$\begin{array}{cc}\left(s\right)=\{\begin{array}{cc}.Math.\arcsin \left(\frac{l_1.Math.n}{.Math.l_1.Math.}\right).Math.& \mathrm{penalize}\mathrm{climbing}\mathrm{and}\mathrm{descending}\\ \arcsin \left(\frac{l_2.Math.n}{.Math.l_1.Math.}\right)& \mathrm{penalize}\mathrm{climbing}\end{array}& \left(14\right)\end{array}$$\begin{array}{cc}{l}_1=s-\mathrm{parent}\left(s\right)& \left(15\right)\end{array}$$\begin{array}{cc}n=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]& \left(16\right)\end{array}$
where g(s) is the length of the shortest path from start vertex to vertex s found so far, and thereby is an estimate of the start distance of vertex s; h(s) is an estimate of the goal distance of vertex s; t(s) is the traversal cost obtained from Eq. (8); c(s) is other costs in addition to t(s) en route.

(30) To ensure that no route segment has climb or descending angle exceeding an absolute threshold .sub.c, the cost function in Eq. (13) is changed to a piece-wise function as follows:

(31) $\begin{array}{cc}c\left(s\right)=\{\begin{array}{cc}{}_c\left(s\right).Math.l_1.Math.& \left(s\right){}_c\\ +& \left(s\right)>{}_c\end{array}.& \left(17\right)\end{array}$

Examples

(32) Taking the geographical region as shown in FIG. 7 as an example of how different structural elements/obstacles are adjusted to reflect the actual height an UAV needs to fly (about 90 m to 120 m above the ground level). As shown in FIG. 8, buildings, non-fly zones and special traversal cost areas in a geographical region are abstracted/approximated by convex polyhedrons or polygons before discretization.

(33) By the present invention, the tested geographical region is discretized into a plurality of grid cells or nodes. Different traversal cost is assigned to each of the grid cells depending on whether the cell is within a free space, desired moving space, or not. According to a preferred embodiment of the present invention, the three-dimensional environment of the tested geographical region is converted into a two-dimensional graph, and each grid cell corresponds to a node in the graph, where each node connects with the nodes which have line-of-sight with. A path planning problem from an origin to a destination in a three-dimensional environment is converted into a graph-based path planning problem from a first node to a last node on the graph as-converted according to the method of the present invention. FIG. 9 shows a layer of the discretized three-dimensional grids, where different colors or gradings represent different traversal costs among different grid cells. During UAV operation, the other costs such as turning, climb/descending costs of the UAV will be added into the modified algorithm used in the present invention as a heuristic function, and the approximation of average non-uniform traversal cost instead of the product of the path length and the non-uniform traversal cost of each unblocked cell is used to speed up the line-of-sight check between every two nodes.

(34) The foregoing description of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to the practitioner skilled in the art.

(35) All or portions of the embodiments disclosed herein may be implemented using one or more of specially configured computing devices, computer processors, or electronic circuitries including but not limited to graphics processing units (GPUs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), and other programmable logic devices configured or programmed according to the teachings of the present disclosure. Computer instructions or codes running in the computing devices, computer processors, or programmable logic devices can readily be prepared by practitioners skilled in the software or electronic art based on the teachings of the present disclosure. The aforesaid one or more computing devices may include one or more of server computers, personal computers, laptop computers, mobile computing devices such as smartphones and tablet computers.

(36) The electronic embodiments include computer-readable storage media having the computer instructions or codes stored therein, which can be used to configure or program the computing devices, computer processors, or electronic circuitries to perform any of the processes of the present invention; and to store data generated by any of the processes of the present invention. The computer-readable storage media include, but are not limited to, floppy disks, optical discs, Blu-ray Disc, DVD, CD-ROMs, magneto-optical disks, solid-state discs, ROMs, RAMs, SRAMs, DRAMs, flash memory devices, electrically programmable read-only memories (EPROMs), electrically erasable programmable read-only memories (EEPROMs), or any type of media or devices suitable for storing instructions, codes, and/or data.

(37) The foregoing description of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to the practitioner skilled in the art.

(38) The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications that are suited to the particular use contemplated.

INDUSTRIAL APPLICABILITY

(39) The present invention is not just limited to the use in unmanned vehicles, but also in all possible transportations or moving objects requiring time- and cost-saving path planning and/or on-the-journey search, in particular, the designated vehicles need to travel from one location to the other in a highly variable and/or unpredictable environment. Approximation method of the non-uniform traversal cost proposed in the present invention is also applicable in other graph-based path planning algorithms, and should not be restricted to the algorithms mentioned as examples in the present disclosure. Addition and approximation of other costs specific to unmanned aerial vehicle into the calculation of the optimal path according to certain embodiments of the present invention also provides a solution to other unmanned vehicles which their corresponding operation cost is largely dependent on the vehicle dynamics. Also described herein as one of the aspects, the present invention is also applicable to any other fields requiring path planning not just limited to the shortest possible path but also taking non-uniform traversal cost into account when computing the optimal path.