author ： 19 the lz

date ：2021-11-14

The paper ：《Online Safe Trajectory Generation For Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial》

problem :

(a) The first problem is the time allocation of piecewise trajectory , Improper time allocation can easily lead to low-quality trajectories .
(b) The second problem is how to effectively constrain the whole trajectory and its derivatives in free space in hard constrained feasible space .

contribution :

(1) A fast propulsion method based on Euclidean distance field is proposed , Used to search the time indicator path , Provide reasonable time allocation for trajectory optimization .
(2) A trajectory optimization framework , utilize bernstein Base generation smoothing 、 Security 、 Dynamically feasible trajectory .
(3) The proposed motion planning method and system are integrated into a complete four rotor platform for real-time implementation .

One 、 background ：

In this paper , We propose a four rotor motion planning method , It can not only generate safe , And it can generate feasible trajectory in the dynamic range .

Two 、 Related work ：

3、 ... and 、 Research process and results ：

Front end trajectory generation

Fast marching algorithm :
Is a method of simulating wave propagation , By assuming the wavefront to f The velocity of the wave propagates along its normal direction to calculate the time when the wave first reaches a certain point . Suppose the propagation speed f > 0, That is, the wave front only develops outward , And sometimes invariable , And only depends on the location in space .

For path search , We can define a speed map of robot navigation . By simulating the wave spreading from the starting point , Get the arrival time of each point on the map . By tracing the path from the target point to the starting point along the descending direction of the arrival time gradient , Got a path with the shortest arrival time . This is the main idea of applying fast marching algorithm in path search .

Different from other potential field based methods , Fast marching algorithm has no local minimum .

vm Is the maximum speed , d Is the distance from the nearest obstacle


Represents the distribution of velocity in the map , Euclidean symbolic distance field
(d) Indicates... In the map , Time of arrival at each point

heuristic

d*(x): Express x Euclidean distance to the target point

Flight corridor

After obtaining the minimum arrival path of the time index , Extract the free space in the environment , Form a flight corridor optimized at the back end . Make full use of free space , Because finding the solution space and obtaining the optimal solution are equally important for trajectory generation .

First, through the Euclidean symbolic distance field , Get a safe space ball , Initialize the flight corridor as the inscribed cube of the sphere . Then we query the axis alignment direction x,y,z Maximize the free direction of the neighbor mesh to enlarge each cube

analysis : Why initialize an inscribed cube first ?
Maybe to improve the expansion speed , If the scope is too large , There is no need to expand layer by layer

Back end trajectory optimization

Bessel trajectory optimization

Bessel curve

nature :
(1) Pass through the first and last control points
(2) Fixed interval property . Parameters t Belong to [0, 1]
(3) Convex hull property .
(4) Derivative is still Bezier curve .

Loss function

Because it's minimization jerk( Speed up ), therefore k=3

si: The scaling factor , Used for track scaling

constraint

For each Bezier curve , Its higher derivative can be expressed by the linear combination of the corresponding lower order control points

l: Order
i: Which control points
u:x,y,z Axis
j: Number of control points ( rank )

Waypoint constraint

The path point that the four rotor aircraft needs to pass , Because the trajectory must pass through the first and last control points , So through the waypoint constraint , Ensure the connection between each curve

Continuity constraints

Ensure that the connection between each two tracks is continuous

Security constraints

As mentioned above , If it is ensured that the control point is located in the safe flight corridor ( Convex hull property ) in , Then you can ensure that the trajectory is collision free

Motion feasibility constraints

result

and chen Method difference :
(a) The fast travel algorithm in the velocity field is used to provide a natural time index path , Instead of searching paths and allocating time according to some heuristic algorithms .
(b) The Bernstein polynomial basis is directly used to obtain safety and dynamic feasibility , This avoids the risk of collision .

conclusion

This paper presents an online motion planning framework for four rotor autonomous navigation . This method adopts a fast path search method based on travel , Find a path based on time exponential in the velocity field adapting to the environment . Flight corridors are based on path generation and expansion , To make full use of the free space in the environment . Last , We use the method of dynamic optimization based on Bernstein's polynomials to generate safe and feasible trajectories .