Method of avoiding collision of unmanned aerial vehicle

Abstract

Provided is a method of avoiding collision of an unmanned aerial vehicle with an obstacle, the method including: calculating two potential fields using ament positional information of the unmanned aerial vehicle, a target point that is set, and positional information of the obstacle measured by a sensor, computing an attractive force and a repulsive force by differentiating the computed potential fields, respectively; computing a direction of a potential force that results from adding up the computed attractive force and repulsive force; and performing control that brings about a change from the computed direction of the potential force to a direction in which the unmanned aerial vehicle moves.

Claims

1. A method of avoiding collision of an unmanned aerial vehicle with an obstacle, the method comprising: calculating two potential fields using current positional information of the unmanned aerial vehicle, a target point that is set, and positional information of the obstacle measured by a sensor; computing an attractive force and a repulsive force by differentiating the two potential fields, respectively; computing a direction of a potential force that results from adding up the attractive force and the repulsive force; and performing to control the direction of the potential force in a direction of the unmanned aerial vehicle moves, wherein the calculating two potential fields include: an attractive potential field that is computed with the current positional information of the unmanned aerial vehicle and the target point that is set, and a repulsive potential field that is computed with the current positional information of the unmanned aerial vehicle and positional information of the obstacle, wherein the repulsive potential field is proportional to a coefficient of the repulsive force that is a set coefficient, and wherein a change in a position of the unmanned aerial vehicle for a set time is computed, the coefficient of the repulsive force is reduced when a computed change in the position of the unmanned aerial vehicle is smaller than a setting value, and a case where the computed change in the position of the unmanned aerial vehicle is smaller than the setting value for the given time includes a situation where the target point is positioned within a range where the obstacle exerts an influence and the repulsive force that is generated by the obstacle is greater than the attractive force that is generated by the target point.

2. The method according to claim 1, wherein the attractive potential field is computed using following equations:
r.sub.G(p)=∥p.sub.G(t)−p(t)∥
U.sub.att=K.sub.Gr.sub.G where r.sub.G denotes a distance between the unmanned aerial vehicle and the target point, K.sub.G denotes a coefficient of the attractive force, P.sub.G(i) denotes the target point, p(t) denotes the position of the unmanned aerial vehicle, and U.sub.att denotes the attractive potential field.

3. The method according to claim 2, wherein the attractive force is computed from the attractive potential field, and the attractive force is computed using following equations: $F_{{att}_{z}} = - \frac{\partial U_{att}}{\partial x} = K_{G} \frac{(p_{Gz} - p_{z})}{r_{G}} F_{{att}_{y}} = - \frac{\partial U_{att}}{\partial y} = K_{G} \frac{(p_{Gy} - p_{y})}{r_{G}} .$

4. The method according to claim 3, wherein the repulsive potential field is computed using following equations: $U_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ K_{O} (\frac{1}{r_{O} - r_{m}} - \frac{1}{r_{s}}) & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix}$ where r.sub.O denotes a distance between the unmanned aerial vehicle and the obstacle, and v.sub.RO denotes the respective relative velocities of the unmanned aerial vehicle and the obstacle;
v.sub.RO(t)=[v(t)−v.sub.O(t)].sup.T.sub.n.sub.RO
r.sub.O(p(t),p.sub.O(t))=∥p(t)−p.sub.O(t)∥ where v′ denotes a velocity of the unmanned aerial vehicle, v.sub.O′ denotes a velocity of the obstacle, p.sub.O denotes a position of the obstacle, r.sub.m denotes a braking distance of the unmanned aerial vehicle, and r.sub.s denotes an influence range of the obstacle; and $r_{m} = \frac{v_{RO}^{2} (t)}{2 a_{m ax}}$ where a.sub.max denotes maximum acceleration of the unmanned aerial vehicle, K.sub.O′ denotes the coefficient of the repulsive force, and n.sub.RO′ denotes a direction of a v.sub.RO vector.

5. The method according to claim 4, wherein the repulsive force is computed from the repulsive potential field, and the repulsive force is computed using following equations: $F_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ F_{rep 1} + F_{rep 2} & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix} F_{rep 1} = K_{O} U_{rep}^{2} (1 + \frac{v_{RO} (t)}{a_{m ax}}) n_{OR} F_{rep 2} = \frac{K_{O} U_{rep}^{2} v_{RO} (t) v_{RO ⊥}}{a_{ma x} r_{O} (p (t), p_{O} (t))} n_{OR ⊥}$ where F.sub.rep1 denotes the repulsive force that is generated, in a direction of the obstacle, in the unmanned aerial vehicle, F.sub.rep2 denotes the repulsive force that is generated in a direction vertical to F.sub.rep1, v.sub.RO⊥ denotes a magnitude in a vertical direction, of v.sub.RO vector, n.sub.RO′ denotes a component in the vertical direction, of a v.sub.RO vector and n.sub.OR is a reverse vector of n.sub.RO′.

6. The method according to claim 1, wherein a heading of the unmanned aerial vehicle is controlled through a collision avoidance algorithm based on the potential field, the direction of the potential force is computed using an arctangent in the potential forces in horizontal and vertical axes, and the heading of the unmanned aerial vehicle is controlled with a value from multiplication of a heading error of the unmanned aerial vehicle and a heading control coefficient.

7. A method of avoiding collision of an unmanned aerial vehicle with an obstacle, the method comprising: calculating two potential fields using current positional information of the unmanned aerial vehicle, a target point that is set, and positional information of the obstacle measured by a sensor; computing an attractive force and a repulsive force by differentiating the two potential fields, respectively; computing a direction of a potential force that results from adding up the attractive force and the repulsive force; and performing to control the direction of the potential force in a direction of the unmanned aerial vehicle moves, wherein a repulsive potential field is computed using following equations: $U_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ K_{O} (\frac{1}{r_{O} - r_{m}} - \frac{1}{r_{s}}) & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix}$ where r.sub.O denotes a distance between the unmanned aerial vehicle and the obstacle, and v.sub.RO denotes respective relative velocities of the unmanned aerial vehicle and the obstacle;
v.sub.RO(t)=[v(t)−v.sub.O(t)].sup.Tn.sub.RO
r.sub.O(p(t),p.sub.O(t))=∥p(t)−p.sub.O(t)∥ where v′ denotes a velocity of the unmanned aerial vehicle, v.sub.O′ denotes a velocity of the obstacle, p.sub.O denotes a position of the obstacle, r.sub.m denotes a braking distance of the unmanned aerial vehicle, and r.sub.s denotes an influence range of the obstacle; $r_{m} = \frac{v_{RO}^{2} (t)}{2 a_{m a x}}$ where a.sub.max denotes maximum acceleration of the unmanned aerial vehicle, K.sub.O′ denotes a coefficient of the repulsive force, and n.sub.RO′ denotes a direction of a v.sub.RO vector.

8. The method according to claim 7, wherein the calculating two potential fields include: an attractive potential field that is computed with the current positional information of the unmanned aerial vehicle and the target point that is set, the repulsive potential field that is computed with the current positional information of the unmanned aerial vehicle and the positional information of the obstacle, and the attractive potential field is computed using following equations:
r.sub.G(p)=∥p.sub.G(t)−p(t)∥
U.sub.att=K.sub.Gr.sub.G where r.sub.G denotes a distance between the unmanned aerial vehicle and the target point, K.sub.G′ denotes a coefficient of the attractive force, p.sub.G(t) denotes the target point, p(t) denotes a position of the unmanned aerial vehicle, and U.sub.att denotes the attractive potential field.

9. The method according to claim 7, wherein the attractive force is computed from the attractive potential field, and the attractive force is computed using following equations: $F_{{att}_{x}} = \frac{\partial U_{att}}{\partial x} = K_{G} \frac{(p_{G x} - p_{x})}{r_{G}}$ $F_{{att}_{y}} = - \frac{\partial U_{att}}{\partial y} = K_{G} \frac{(p_{G y} - p_{y})}{r_{G}}$

10. The method according to claim 7, wherein the repulsive force is computed from the repulsive potential field, and the repulsive force is computed using following equations: $F_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ F_{rep 1} + F_{rep 2} & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix}$ $F_{rep 1} = K_{O} U_{rep}^{2} (1 + \frac{v_{RO} (t)}{a_{m a x}}) n_{OR}$ $F_{rep 2} = \frac{K_{O} U_{rep}^{2} v_{RO} (t) v_{RO ⊥}}{a_{m a x} τ_{O} (p (t), p_{O} (t))} n_{OR ⊥}$ where F.sub.rep1 denotes the repulsive force that is generated, in a direction of the obstacle, in the unmanned aerial vehicle, F.sub.rep2 denotes the repulsive force that is generated in a direction vertical to F.sub.rep1, v.sub.RO⊥ denotes a magnitude in a vertical direction, of v.sub.RO vector, n.sub.RO′ denotes a component in the vertical direction, of a v.sub.RO vector and n.sub.OR a reverse vector of n.sub.RO′.

11. The method according to claim 10, wherein a change in the position of the unmanned aerial vehicle is computed for a given time, the coefficient of the repulsive force is reduced when a computed change in the position of the unmanned aerial vehicle is smaller than a setting value, and a case that the computed change in the position of the unmanned aerial vehicle is smaller than the setting value for the given time, includes: a situation that the obstacle is positioned between the unmanned aerial vehicle and the target point, and the unmanned aerial vehicle, the obstacle, and the target point are on the same line, a situation that the unmanned aerial vehicle moves toward the target point and obstacles are positioned to the left and right, respectively, of a moving path, and a situation that the target point is positioned within a range where the obstacle exerts an influence and the repulsive force that is generated by the obstacle is greater than the attractive force that is generated by the target point.

12. The method according to claim 7, wherein a heading of the unmanned aerial vehicle is controlled through a collision avoidance algorithm based on the potential field, the direction of the potential force is computed using an arctangent in the potential forces in horizontal and vertical axes, and the heading of the unmanned aerial vehicle is controlled with a value from multiplication of a heading error of the unmanned aerial vehicle and a heading control coefficient.

13. A method of avoiding collision of an unmanned aerial vehicle with an obstacle, the method comprising: calculating two potential fields using current positional information of the unmanned aerial vehicle, a target point that is set, and positional information of the obstacle measured by a sensor; computing an attractive force and a repulsive force by differentiating the two potential fields, respectively; computing a direction of a potential force that results from adding up the attractive force and the repulsive force; and performing to control the direction of the potential force in a direction of the unmanned aerial vehicle moves, wherein the calculating two potential fields include: an attractive potential field that is computed with the current positional information of the unmanned aerial vehicle and the target point that is set, a repulsive potential field that is computed with the current positional information of the unmanned aerial vehicle and the positional information of the obstacle, the attractive potential field is computed using following equations:
r.sub.G(p)=∥p.sub.G(t)−p(t)∥
U.sub.att=K.sub.Gr.sub.G where r.sub.G denotes a distance between the unmanned aerial vehicle and the target point, K.sub.G′ denotes a coefficient of the attractive force, p.sub.G(t) denotes the target point, p(t) denotes a position of the unmanned aerial vehicle, and U.sub.att denotes the attractive potential field, and wherein the attractive force is computed from the attractive potential field, and the attractive force is computed using following equations: $F_{{att}_{x}} = - \frac{\partial U_{att}}{\partial x} = K_{G} \frac{(p_{G x} - p_{x})}{r_{G}}$ $F_{{att}_{y}} = - \frac{\partial U_{att}}{\partial y} = K_{G} \frac{(p_{G y} - p_{y})}{r_{G}},$ and wherein a repulsive potential field is computed using following equations: $U_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ K_{O} (\frac{1}{r_{O} - r_{m}} - \frac{1}{r_{s}}) & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix}$ where r.sub.O denotes a distance between the unmanned aerial vehicle and the obstacle, and v.sub.RO denotes respective relative velocities of the unmanned aerial vehicle and the obstacle;
vhd RO(t)=[v(t)−v.sub.O(t)].sup.Tn.sub.RO
r.sub.O(p(t),p.sub.O(t))=∥p(t)−p.sub.O(t)∥ where v′ denotes a velocity of the unmanned aerial vehicle, v.sub.O′ denotes a velocity of the obstacle, p.sub.O denotes a position of the obstacle, r.sub.m denotes a braking distance of the unmanned aerial vehicle, and r.sub.s denotes an influence range of the obstacle; $r_{m} = \frac{v_{RO}^{2} (t)}{2 a_{m a x}}$ where a.sub.max denotes maximum acceleration of the unmanned aerial vehicle, K.sub.O′ denotes a coefficient of the repulsive force, and n.sub.RO′ denotes a direction of a v.sub.RO vector.

14. The method according to claim 13, wherein the repulsive force is computed from the repulsive potential field, and the repulsive force is computed using following equations: $F_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ F_{rep 1} + F_{rep 2} & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix}$ $F_{rep 1} = K_{O} U_{rep}^{2} (1 + \frac{v_{RO} (t)}{a_{m a x}}) n_{OR}$ $F_{rep 2} = \frac{K_{O} U_{rep}^{2} v_{RO} (t) v_{RO ⊥}}{a_{m a x} τ_{O} (p (t), p_{O} (t))} n_{OR ⊥}$ where F.sub.rep1 denotes the repulsive force that is generated, in a direction of the obstacle, in the unmanned aerial vehicle, F.sub.rep2 denotes the repulsive force that is generated in a direction vertical to F.sub.rep1, v.sub.RO⊥ denotes a magnitude in a vertical direction, of v.sub.RO vector, n.sub.RO′ denotes a component in the vertical direction, of a v.sub.RO vector and n.sub.OR is a reverse vector of n.sub.RO′.

15. The method according to claim 13, wherein a heading of the unmanned aerial vehicle is controlled through a collision avoidance algorithm based on the potential field, the direction of the potential force is computed using an arctangent in the potential forces in horizontal and vertical axes, and the heading of the unmanned aerial vehicle is controlled with a value from multiplication of a heading error of the unmanned aerial vehicle and a heading control coefficient.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The patent or application file contains at least one drawing/photograph executed in color. Copies of this patent or patent application with color drawing(s)/photograph(s) will be provided by the Office upon request and payment of the necessary fee.

(2) FIGS. 1A and 1B are respectively a block diagram and a table that show an algorithm of a Kalman filter and constituent elements of the Kalman filter according to the present invention;

(3) FIG. 2 is a graph comparing an actual value and a measurement value for a path along which an obstacle moves and a result obtained by applying the Kalman filter,

(4) FIG. 3 is a graph comparing an actual velocity of an obstacle and a velocity that is estimated with the Kalman filter,

(5) FIG. 4 is a graph showing a difference between the actual velocity of the obstacle and the velocity that is estimated with the Kalman filter,

(6) FIG. 5 is a graph comparing the actual value and the measurement value for the path along which the obstacle moves and a result for the Kalman filter,

(7) FIG. 6 is a graph comparing the actual velocity of the obstacle and the velocity that is estimated with the Kalman filter,

(8) FIG. 7 is a graph showing the difference between the actual velocity of the obstacle and the velocity that is estimated with the Kalman filter,

(9) FIG. 8 is a graph illustrating a velocity estimation RMSE in toms of LiDAR accuracy;

(10) FIG. 9 is a graph illustrating a velocity estimation RMSE in toms of LiDAR resolution;

(11) FIG. 10 is a graph illustrating attractive potential field parameters;

(12) FIG. 11 is a graph illustrating an example of an attractive potential field;

(13) FIG. 12 is a graph illustrating an example of an attractive potential field contour,

(14) FIG. 13 is a graph illustrating repulsive potential field parameters;

(15) FIG. 14 is a graph illustrating an example of a repulsive potential field;

(16) FIG. 15 is a graph illustrating an example of a repulsive potential field contour,

(17) FIG. 16 is a diagram illustrating the first local minima;

(18) FIG. 17 is a diagram illustrating the second local minima;

(19) FIG. 18 is a diagram illustrating the third local minima;

(20) FIG. 19 is a flowchart illustrating a local minima algorithm; and

(21) FIG. 20 is a diagram illustrating a collision avoidance algorithm.

DETAILED DESCRIPTION OF THE INVENTION

(22) The above-described aspects of the present invention and additional aspects thereof will be apparent from a preferable embodiment that will be described with reference to the accompanying drawings. Descriptions will be provided below so in sufficient detail that a parson of ordinary skill in the art clearly can understand and implement the embodiment of the present invention.

(23) A potential field generates a repulsive force against an obstacle and thus achieves avoidance. Because of this, an algorithm is not complicated, and computation is simple. Thus, collision is sufficiently avoidable in a downtown area where obstacles are tightly packed together. A collision avoidance algorithm based on the potential field generates the potential field with respect to a surrounding situation. The avoidance is achieved on the basis of the generated potential field. Because of this, the collision is avoidable in a manner that is suitable for the surrounding situation.

(24) According to the present invention, as an obstacle detection sensor, LiDAR which can recognize a specific object and can be mounted in an unmanned aerial vehicle is used.

(25) A general potential field is given as a function of a distance to an obstacle, and thus has poor performance in avoiding a moving obstacle. According to the present invention, a velocity relative to the obstacle is taken into consideration when generating the potential field. Thus, the performance in avoiding the moving obstacle is improved.

(26) In addition, according to the present invention, in order to compensate for a disadvantage of the general potential field, the potential field is generated considering the velocity relative to the obstacle. Furthermore, performance of a proposed collision avoidance algorithm is verified through modeling and simulation of an urban environment, and an analysis is made in comparison with an existing potential field.

(27) The collision avoidance algorithms according to the present invention are broadly divided into three parts. First, various obstacles, such as buildings in a downtown area and other unmanned aerial vehicles including an intruding unmanned aerial vehicle, are detected, and a potential collision with the detected obstacle is recognized. According to the present invention, LiDAR that is used as a detection sensor detects an obstacle. Obstacle detection that uses LiDAR omnidirectionally detects an obstacle using Radar-LiDAR, and, when the detected object comes within a fixed range, determines it as an obstacle. Second, in a case where a potential collision of the unmanned aerial vehicle is recognized, a collision avoidance direction is determined, taking into consideration a distance between the unmanned aerial vehicle and the obstacle, a direction and velocity of the obstacle, and a velocity of the unmanned aerial vehicle. The collision avoidance algorithm according to the present invention determines a direction in which the unmanned aerial vehicle can avoid collision. Last, the unmanned aerial vehicle moves in the direction of avoiding a collision. While avoiding the collision in a downtown area, the unmanned aerial vehicle may experience a local minima phenomenon where an unmanned aerial vehicle flies repeatedly within a fixed section. According to the present invention, when determined as experiencing the local minima phenomenon, the unmanned aerial vehicle can overcome the local minima phenomenon by adjusting a potential gain.

(28) Obstacle detection sensors for avoiding the collision of the unmanned aerial vehicle are broadly categorized into collaborative sensors that exchange pieces of data on an obstacle by communicating with a counterpart aircraft and a control system using transponders such as TCAS and ADSB, and non-collaborative sensors, such as an image sensor, a radar, and LiDAR, that determine an obstacle using measurement information.

(29) LiDAR can acquire information on a distance to a detection target in a 2D or 3D coordinate frame while a laser-based module rotates. According to a method of modulating a laser signal, LiDAR comes in two types: a time-of-flight (TOF) type and a phase-shift type. According to the present invention, as illustrated above, among non-collaborative sensors, LiDAR that can measure the distance to the obstacle and the direction thereof is utilized as a sensor for determining the obstacle.

(30) Particularly, in measuring the distance to the obstacle, LiDAR according to the present invention is capable of making a measurement by a total of 30° at intervals of 2° using a total of 16 channels, with respect to the vertical axis, and is capable of making a measurement by 360° at operator-set intervals around the unmanned aerial vehicle, with respect to the horizontal axis.

(31) A selected obstacle detection sensor (LiDAR), which is a sensor that measures the direction of the obstacle and the distance thereto, can know a relative position of the obstacle, but cannot measure a velocity of the obstacle. It is determined that velocity information on the obstacle is necessary for avoidance of collision with a mobile obstacle. According to the present invention, the velocity of the obstacle is estimated based on a change in a position of the obstacle. As a filter for estimation, a Kalman filter is used that can predict a state of the obstacle on the basis of the previous state thereof, in a case where the velocity of the obstacle cannot be estimated and the obstacle cannot be measured due to a limitation of the sensor.

(32) The Kalman filter performs two phases, a prediction phase and a connection phase. The first phase is a phase in which, for prediction, the next estimation value is computed from a previous estimation value through a system model. The second phase is a phase in which, for correction, the predicted state is corrected by applying data measured in the sensor to the computed estimation value.

(33) In the prediction phase, the next state is predicted from an initial state (x.sub.o) or a correction value (x.sub.k) through the system model (A). Then, a change in Kalman filter error covariance (P.sub.k) due to the prediction of the next state is computed. Equation 1 and Equation 2 are equations that correspond to the prediction phase. x.sub.k.sup.− and P.sub.k.sup.− mean the predicted sate and the error covariance, respectively. w.sub.k and Q mean noise and system nose covariance, respectively, which are generated by the prediction.
x.sub.k.sup.−=Ax.sub.(k-1)+w.sub.k Equation 1
P.sub.k.sup.−=AP.sub.(k-1)A.sup.T+Q Equation 2

(34) where k denotes a step that is used for a Kalman filter variable. A variable of the next step is computed by utilizing a variable of the previous step.

(35) In the correction phase, a Kalman gain (K) is computed from the Kalman filter error covariance and a measurement error covariance (R). A state predicted with a measurement value and the Kalman gain is connected. Then, the Kalman filter error covariance changed due to the connection is computed. Equations 3 to 5 are equations that correspond to the connection phase. H is a matrix representing a relationship between a measurement value and a state variable.
K=P.sub.k.sup.−H.sup.T(HP.sub.k.sup.−H.sup.T+R).sup.−1 Equation 3
x.sub.k=x.sub.k.sup.−+K(z.sub.k−Hx.sub.k.sup.−) Equation 4
P.sub.k=(I−KH)P.sub.k.sup.− Equation 5

(36) According to the present invention, measurement values are an angle with the obstacle and a distance relative thereto, which are obtained from LiDAR. As measurement values, an x-axis distance and a y-axis distance (x.sub.0, y.sub.0) to the obstacle, which result from conversion, are used instead of an angle (θ.sub.O) with the obstacle and a distance (d.sub.0) thereto.
x.sub.0=cos θ.sub.0×d.sub.0 Equation 6
y.sub.0=sin θ.sub.0×d.sub.0 Equation 7

(37) In the prediction phase, the next state is estimated from the previous estimation value and the system model, and the changed covariance is estimated while the next state is estimated, hi the collection phase, the Kalman gain is computed on the basis of the estimated covariance and a covariance of the measurement value, and the estimated state is corrected on the basis of a difference between a measurement value of the sensor and a prediction value. Then, a pre-correction covariance is again computed.

(38) FIGS. 1A and 1B are a block diagram and a table that show an algorithm of the Kalman filter and constituent elements of the Kalman filter, respectively, according to the present invention.

(39) In order to verify an algorithm for estimating the velocity of the obstacle, which is realized with the Kalman filter, a simulation for detection of the obstacle and estimation of the velocity thereof is realized. The simulation is realized in such a manner that performance of the algorithm in terms of LiDAR accuracy and performance of the algorithm in terms of the horizontal-axis LiDAR resolution are comparable. Through the simulation, the performances of the algorithms for estimation of the velocity of the obstacle in terms of LiDAR accuracy and in terms of the horizontal-axis LiDAR resolution were verified. Simulation environments for comparison of the performances of the algorithms in terms of LiDAR accuracy are illustrated as in Table 1.

(40) TABLE-US-00001 TABLE 1 Case 1 Case 2 Case 3 Simulation time 500 sec 500 sec 500 sec Step size 0.01 sec 0.01 sec 0.01 sec Object velocity about 5 m/s about 5 m/s about 5 m/s LiDAR accuracy ±3 cm ±10 cm ±20 cm Resolution 1° 1° 1° (Horizontal)

(41) The obstacle moved in the form of a sine wave. The velocity of the obstacle that moved at a velocity of 5 m/s to 5.1 m/s was estimated. The simulation was performed for 500 seconds. LiDAR accuracies woe set to 3 cm, 10 cm, and 20 cm, respectively, and LiDAR resolution was set to 1°. Cases 1 to 3 in each of FIGS. 2 to 4 are results of performing the simulation when the LiDAR accuracies woe set to 3 cm, 10 cm, and 20 cm, respectively.

(42) FIG. 2 is a graph comparing an actual value and a measurement value for a path along which the obstacle moves and a result obtained by applying the Kalman filter. FIG. 3 is a graph comparing an actual velocity of the obstacle and a velocity that is estimated with the Kalman filter. FIG. 4 is a graph showing a difference between the actual velocity of the obstacle and the velocity that is estimated with the Kalman filter.

(43) As a result of the simulation, root mean square errors (RMSE) and maximum errors of measurement values and obstacle velocity estimation results are as shown in Table 2.

(44) TABLE-US-00002 TABLE 2 Case 1 Case 2 Case 3 Position measurement 0.0240 m 0.0805 m 0.0805 m RMSE Position measurement 0.1059 m 0.4098 m 0.6725 m maximum error Position Kalman 0.0237 m 0.0797 m 0.6725 m result RMSE Position Kalman 0.1046 m 0.4062 m 0.6700 m result maximum error Velocity Kalman 0.0141 m/s 0.0396 m/s 0.0728 m/s result RMSE Velocity Kalman 0.0595 m/s 0.1632 m/s 0.3759 m/s result maximum error

(45) As a result of the simulation, RMSEs of LiDAR measurement values in Case 1, Case 2, and Case 3, were 0.0240 m, 0.0805 m, and 0.0805 m, respectively. From this, it can be understood that the greater the LiDAR accuracy, the more RMSE increases. It is shown that RMSEs of estimation velocities of the obstacle are 0.0141 m/s, 0.0396 m/s and 0.0728 m/s, respectively, and that maximum errors of estimation velocities of the obstacle are 0.0595 m/s, 0.1632 m/s, and 0.3759 m/s, respectively. From this, it can be understood that estimations are made with errors of 1.2%, 32%, and 15%, respectively.

(46) Simulation environments for the comparison of the performances of the algorithms in toms of LiDAR resolution are as shown in Table 3.

(47) TABLE-US-00003 TABLE 3 Case 4 Case 5 Case 6 Simulation time 500 sec 500 sec 500 sec Step size 0.01 sec 0.01 sec 0.01 sec Object velocity about 5 m/s about 5 m/s about 5 m/s LiDAR accuracy ±3 cm ±3 cm ±3 cm Resolution 1° 5° 10° (Horizontal)

(48) Simulation time and a moving pattern and velocity of an obstacle were set to be the same as those in the previous simulation. A unit expressing the LiDAR accuracy was set to, cm. The LiDAR resolutions in Cases, 1,2, and 3 were set to 1°, 5°, and 10°, respectively. Cases 4 to 6 in FIGS. 5 to 7 are the results of the simulation that was performed when the LiDAR resolutions were set to 1°, 5°, and 10°, respectively.

(49) FIG. 5 is a graph comparing the actual value and the measurement value for the path along which the obstacle moves and a result obtained by applying the Kalman filter. FIG. 6 is a graph comparing the actual velocity of the obstacle and the velocity that is estimated with the Kalman filter. FIG. 7 is a graph showing the difference between the actual velocity of the obstacle and the velocity that is estimated with the Kalman filter.

(50) As a result of the simulation, root mean square errors (RMSE) and maximum errors of measurement values and obstacle velocity estimation results are as shown in Table 4.

(51) TABLE-US-00004 TABLE 4 Case 4 Case 5 Case 6 Position measurement 0.0242 m 0.0243 m 0.0251 m RMSE Position measurement 0.1140 m 0.1040 m 0.0971 m maximum error Position Kalman 0.0240 m 0.0240 m 0.0248 m result RMSE Position Kalman 0.1129 m 0.1035 m 0.0964 m result maximum error Velocity Kalman 0.0146 m/s 0.0183 m/s 0.0250 m/s result RMSE Velocity Kalman 0.0606 m/s 0.0553 m/s 0.0627 m/s result maximum error

(52) As a result of the simulation, RMSEs of LiDAR measurement values in Case 1, Case 2, and Case 3, were 0.0242 m, 0.0243 m, and 0.0251 m, respectively. From this, it can be understood that a great influence is not exerted on the LiDAR resolutions. RMSEs of estimation velocities of the obstacle are 0.0146 m/s, 0.0183 m/s, and 0.0250 m/s. From this, it can be understood that the greater the resolution, the more imprecise the velocity estimation of the obstacle. However, the maximum errors of the estimation velocities of the obstacle are 0.0606 m/s, 0.0553 m/s, and 0.0627 m/s, respectively. From this, it can be understood that an error of approximately 12% occurs and that the LiDAR resolution does not exert a great influence.

(53) Potential is a scalar field and is computed as a minus gradient of a vector field of a conservative force. A potential field according to the present invention is formed by a force that is generated by a target point and an obstacle in a plane field. An attractive force of the potential field is generated by the target point, and a repulsive force is generated by the obstacle. The potential field is formed by adding up all attractive and repulsive forces. A force that is received by the unmanned aerial vehicle in flight is a result of adding up the attractive force ({right arrow over (F)}.sub.att) and the repulsive force ({right arrow over (F)}.sub.rep) that are generated by all target points and obstacles. A force ({right arrow over (F)}.sub.total) at work that is position-dependent is a force representing a resultant force that results from adding up the attractive force of the target object and the repulsive force of the obstacle.

(54) $\begin{matrix} {\overset{.fwdarw.}{F}}_{total} (p, v) = {\overset{.fwdarw.}{F}}_{att} (p, v) + {.Math.}_{i = 1}^{n} {\overset{.fwdarw.}{F}}_{rep}^{i} (p, v) & Equation 8 \end{matrix}$

(55) where n denotes the number of detected obstacles. A total repulsive force is computed by adding up repulsive forces of the detected obstacles.

(56) An obstacle avoidance motion by the potential field depends heavily on a component and direction of a force that vary according to a position of the unmanned aerial vehicle. A differential equation of the potential field (U) that varies according to a position and a relative velocity is the same as Equation 9.

(57) $\begin{matrix} \overset{.fwdarw.}{\nabla} U (p, v) = {[\frac{\partial U}{\partial x} \frac{\partial U}{\partial y}]}^{T} & Equation 9 \end{matrix}$

(58) A flight trajectory of the unmanned aerial vehicle is formed along the most-steeply-descending direction of the potential field at a current position. This occurs due to a direction of a force at a current position, of the unmanned aerial vehicle, and is regarded as an optimization problem of finding a minimum value of a magnitude of the potential.

(59) According to the present invention, the potential field is configured with an attractive potential field that is generated by the target point and represents an attractive force, and a repulsive potential field that is generated by each obstacle and represents a repulsive force.

(60) Generally, the attractive potential field is defined as a function of a relative distance (r.sub.G) between the unmanned aerial vehicle and the target point, and the target point is defined as a point fixed in space. According to the present invention, the attractive potential field is in proportion to the distance (r.sub.G) between the unmanned aerial vehicle and the target point, and a coefficient (K.sub.G) for an attractive force.
r.sub.G(p)=∥p.sub.G(t)−p(t)∥
U.sub.att=K.sub.Gr.sub.G Equation 10

(61) where p.sub.G(t) and p(t) denote the target point and the position of the unmanned aerial vehicle, respectively, and U.sub.att denotes the attractive potential field. An attractive force in the x- and y-directions that is obtained through partial differentiation of the attractive potential field in Equation 10 is summarized as in Equation 11.

(62) $\begin{matrix} F_{{att}_{z}} = - \frac{\partial U_{att}}{\partial x} = K_{G} \frac{(p_{Gx} - p_{x})}{r_{G}} F_{{att}_{y}} = - \frac{\partial U_{att}}{\partial y} = K_{G} \frac{(p_{Gy} - p_{y})}{r_{G}} & Equation 11 \end{matrix}$ $\begin{matrix} e_{Gx} = \frac{p_{Gx} - p_{x}}{r_{G}}, e_{Gy} = \frac{p_{Gy} - p_{y}}{r_{G}} & Equation 12 \end{matrix}$ $\begin{matrix} F_{{att}_{s}} = K_{G} e_{Gx}, F_{{att}_{t}} = K_{G} e_{Gy} & Equation 13 \end{matrix}$

(63) e.sub.Gx and e.sub.Gy in Equation 12 denote the respective directions of the unmanned aerial vehicle and the target point as unit vector components. For expression in toms of a unit vector, Equation 11 is summarized as the product of a unit vector and the coefficient of the attractive force as Equation 13. Therefore, a magnitude of the attractive force is fixed regardless of a distance between the unmanned aerial vehicle and the target point, and it can be understood that the attractive force also has a fixed influence regardless of the position of the unmanned aerial vehicle.

(64) A general repulsive potential field is defined as a function of a distance between the unmanned aerial vehicle and the obstacle. However, in a downtown area, it is necessary to avoid collision not only with a stationary obstacle, but also with a moving obstacle, such as a vehicle, a bird, and another unmanned aerial vehicle. When the repulsive potential field is defined only as the function of the distance, the velocity of the obstacle is not taken into consideration, thereby increasing the risk of collision. According to the present invention, the collision with obstacles, including a moving obstacle and a stationary obstacle, is avoidable by applying not only the distance between the unmanned aerial vehicle and the obstacle, but also the relative velocity.

(65) The repulsive potential field according to the present invention is generated by utilizing the distance between the unmanned aerial vehicle and the obstacle, the relative velocity, and the like. An equation for applying the distance (r.sub.O) to the obstacle and the relative velocity (v.sub.RO) is the same as Equation 14.
v.sub.RO(t)=[v(t)−v.sub.O(t)].sup.Tn.sub.RO
r.sub.O(p(t),p.sub.O(f))=∥p(t)−p.sub.O(t)∥ Equation 14

(66) where v, v.sub.O denotes the respective velocities of the unmanned aerial vehicle and the obstacle and p.sub.O denotes a position of the obstacle. In addition, n.sub.RO denotes a direction of a v.sub.RO vector. In order to efficiently avoid collision of the unmanned aerial vehicle, a braking distance (r.sub.m) of the unmanned aerial vehicle and an influence range (r.sub.s) of the obstacle are applied. The influence range of the obstacle may vary according to an operating environment. Generally, an operator sets the influence range of the obstacle in such a manner as to have a value suitable for the operating environment.

(67) The repulsive potential field that results from applying the braking distance of the unmanned aerial vehicle and the influence range of the obstacle is as in Equation 15. In a case where the unmanned aerial vehicle falls out of the influence range of the obstacle, or in a case where the distance to the obstacle is constant or increases, the repulsive potential field is not generated. In a case where the distance to the obstacle increases, but falls within the influence range of the obstacle, the repulsive potential field is not defined.

(68) $\begin{matrix} r_{m} = \frac{v_{RO}^{2} (t)}{2 a_{ma x}} & Equation 15 \end{matrix}$ $\begin{matrix} U_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ K_{O} (\frac{1}{r_{O} - r_{m}} - \frac{1}{r_{s}}) & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix} & Equation 16 \end{matrix}$

(69) a.sub.max in Equation 15 denotes maximum acceleration of the unmanned aerial vehicle. K.sub.O In Equation 16 denotes a coefficient of a repulsive force. Application of a general potential field to the unmanned aerial vehicle makes it necessary to adjust the coefficient of the repulsive force according to a change in the velocity of the unmanned aerial vehicle. According to the present invention, the relative velocity of the unmanned aerial vehicle with respect to the obstacle is applied. Thus, the potential field changes when the velocity of the unmanned aerial vehicle changes. Therefore, the velocity of the unmanned aerial vehicle is changeable during the flight of the unmanned aerial vehicle.

(70) Like the attractive force, the repulsive force is obtained through the differentiation of the repulsive potential field, and it can be summarized as in Equation 17. In the case where the unmanned aerial vehicle falls out of the influence range of the obstacle or in the case where the distance to the obstacle is constant or increases, the repulsive force is not generated. In the case where the distance to the obstacle increases but falls within the influence range of the obstacle, the repulsive force is not defined,

(71) $\begin{matrix} F_{rep} (p, v) = {\begin{matrix} 0, & if r_{O} - r_{m} \geq r_{s} or v_{RO} \leq 0 \\ F_{rep 1} + F_{rep 2} & if 0 < r_{O} - r_{m} < r_{s} and v_{RO} > 0 \\ not defined & v_{RO} < 0 and r_{O} - r_{m} < r_{s} \end{matrix} F_{rep 1} = K_{O} U_{rep}^{2} (1 + \frac{v_{RO} (t)}{a_{m ax}}) n_{OR} F_{rep 2} = \frac{K_{O} U_{rep}^{2} v_{RO} (t) v_{RO ⊥}}{a_{ma x} r_{O} (p (t), p_{O} (t))} n_{OR ⊥} & Equation 17 \end{matrix}$

(72) where F.sub.rep1 denotes a repulsive force that is generated, in the direction of the obstacle, in the unmanned aerial vehicle, F.sub.rep2 denotes a repulsive force that is generated in a direction vertical to F.sub.rep1, v.sub.RO ⊥ is a component in the vertical direction, of a v.sub.RO vector, n.sub.RO ⊥ is a component in the vertical direction, v.sub.RO of a vector and n.sub.RO is a reverse vector of n.sub.RO.

(73) FIGS. 14 and 15 illustrate the respective examples, respectively, of the repulsive potential field and a repulsive potential field contour that result when it is assumed that there is no motion of the obstacle. Coordinates of the obstacle are (3,3), (8,6), and (8,9).

(74) A local minimum in analytics means a function value at a minimum point. That is, various local minimums may be present as function values that are minimized at all points in the vicinity, in a high-order function.

(75) The collision avoidance algorithm based on the potential field is an algorithm for avoiding the obstacle while moving in a gradient descent direction of a potential force. The collision avoidance based on the potential field may lead to the local minima phenomenon where a minimum value of the potential field is reached locally before reaching a target point. In this potential field, there are three types of situations where a minimum value occurs locally instead of occurring at a final target point.

(76) First in a case where the unmanned aerial vehicle, the obstacle, and the target point are on the same line and where the obstacle is positioned between the unmanned aerial vehicle and the target point the local minima phenomenon may occur. In such a case, when the attractive force and the repulsive force are the same, the unmanned aerial vehicle can hover at a fixed position without moving to the target point. FIG. 16 illustrates in the first local minima.

(77) Second, in a case where the unmanned aerial vehicle moves toward the target point and obstacles are positioned to the left and right, respectively, of a moving path, the local minima phenomenon may also occur. When the repulsive force that is generated by the respective obstacles on the left and right of the path to the target point and the attractive force that is generated by the target point are balanced, the unmanned aerial vehicle may not move to the target point. FIG. 17 illustrates the second local minima.

(78) Third, in a case where the target point is positioned within the range where the obstacle exerts an influence and where the repulsive force generated by the obstacle is greater than the attractive force generated by the target point, the local minima phenomenon where the unmanned aerial vehicle cannot reach the target point may occur. FIG. 18 illustrates the third local minima.

(79) When the attractive force generated by the target point and the repulsive force generated by the obstacle are balanced, the local minima phenomenon occurs. Therefore, in an environment where obstacles are present, such as in a downtown area, there is a high likelihood that the local minima phenomenon will occur.

(80) According to the present invention, in a case where an amount of change in the position of the unmanned aerial vehicle is below a threshold, it is determined that the local minima phenomenon occurs. Then, an attempt was made to overcome the local minima by changing the coefficient of the repulsive force. d in FIG. 19 denotes a distance the unmanned aerial vehicle moves for a fixed time, and α denotes the time for determining the local minima. K.sub.O denotes a coefficient of the repulsive force. s is a variable for setting an amount of change in the coefficient of the repulsive force in a case where it is determined that the local minima occurs. According to the present invention, s is set to a number that is greater than 1 in such a manner that the coefficient of the repulsive force is reduced in a case where an amount of motion is small.

(81) The collision avoidance algorithm based on the potential field uses a method in which the collision with the obstacle is avoided by moving in the direction of the potential force computed through the differentiation of the potential field.

(82) As in Equation 10, the attractive potential field that is used for the collision avoidance algorithm is generated in proportion to the distance between the unmanned aerial vehicle and the target point. As in Equation 16, the repulsive potential field is generated by reflecting not only the distance between the unmanned aerial vehicle and the obstacle but also the relative velocity. The respective characteristics of the unmanned aerial vehicle and the obstacle are reflected by utilizing parameters such as the braking distance and the influence of the obstacle. The potential force is obtained by differentiating the sum of the generated attractive potential field and repulsive potential field, and the obtained potential force is utilized for guided navigation of the unmanned aerial vehicle. An equation for the potential force and an equation for heading control of the unmanned aerial vehicle in the direction of the potential force are the same as Equations 18 to 20.

(83) $\begin{matrix} F_{x} = F_{attx +} F_{1 repx} + F_{2 repx} + .Math. + F_{nrepx} F_{y} = F_{atty} + F_{1 repy} + F_{2 repy} + .Math. + F_{nrepy} & Equation 18 \end{matrix}$ $\begin{matrix} ψ_{CMD} = \tan^{- 1} (\frac{F_{y}}{F_{x}}) & Equation 19 \end{matrix}$ $\begin{matrix} β = K_{C} (ψ_{CMD} - ψ) & Equation 20 \end{matrix}$

(84) In Equation 20, K.sub.C denotes a control coefficient, and β denotes a direction control value of the unmanned aerial vehicle. FIG. 20 is a flowchart for the collision avoidance algorithm based on the potential field. The potential forces in the horizontal and vertical axes, which are generated by the potential field, are computed based on a current position and a target point that are measured and set, respectively, in the unmanned aerial vehicle and information on the obstacle measured in LiDAR. The direction of the potential force is computed using an arctangent in the potential forces in the horizontal and vertical axes, and a heading command of the unmanned aerial vehicle is determined in the direction of the potential force. The heading of the unmanned aerial vehicle is controlled with a value that results from multiplying a heading error of the unmanned aerial vehicle by a heading control coefficient FIG. 20 illustrates a collision avoidance algorithm according to the present invention.

(85) The embodiment of the present invention is described only in an exemplary manner referring to the drawings. It will be apparent to a person of ordinary skill in the art to which the present invention pertains that various other modifications and equivalents are possible from this description.

Method of avoiding collision of unmanned aerial vehicle

Assignee

Inventors

Cpc classification

Classification Explorer

G08G5/045

PHYSICS

Classification Explorer

G08G5/0078

PHYSICS

Classification Explorer

G08G5/0069

PHYSICS

Classification Explorer

G05D1/1064

PHYSICS

Classification Explorer

B64U2101/00

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

B64U2201/10

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G08G5/0039

PHYSICS

Classification Explorer

B64C39/024

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G08G5/0021

PHYSICS

Classification Explorer

G08G5/0052

PHYSICS

International classification

Classification Explorer

G08G5/04

PHYSICS

Classification Explorer

B64C39/02

PERFORMING OPERATIONS; TRANSPORTING

Classification Explorer

G08G5/00

PHYSICS

Abstract

Claims

Description