CN113155145B - A lane-level path planning method for lane-level navigation of autonomous driving - Google Patents

Abstract

The invention relates to the fields of automatic driving navigation and electronic maps, in particular to a lane-level path planning method for automatic driving lane-level navigation. Including: Step 1. Establish a lane-level road network model for automatic driving navigation. The model form is simple, intuitive and convenient for planning; Step 2. Based on the lane-level road network model established in Step 1, perform hierarchical two-way lanes based on road-lane group-lane Level path planning. The invention enables the vehicle to quickly and accurately plan the optimal lane sequence from the starting point to the ending point, that is, the lanes that the vehicle will drive sequentially from the starting point to the ending point, and effectively serves the automatic driving navigation system.

Description

A lane-level path planning method for lane-level navigation of autonomous driving

technical field

The invention relates to the fields of automatic driving navigation and electronic maps, in particular to a lane-level path planning method for automatic driving lane-level navigation.

Background technique

More and more drivers rely on digital map navigation systems in vehicles or mobile phones to choose the best driving route to save time and improve safety. Currently, most vehicle navigation systems are based on road-level maps with limited information and low accuracy. In recent years, the development of advanced driver assistance systems and autonomous driving technology requires more and more help from digital maps. In the near future, the digital map navigation system will play an increasingly important role in the transportation system. In order to extend existing navigation systems to more applications, two fundamental problems must be solved: lane-level map models and lane-level path planning. Many smart driving functions based on digital maps have been developed. The intelligent driving functions supported by these maps can be further divided into the following two categories:

1. Road-level functions: These functions are usually designed to assist human drivers, the required accuracy is usually about 10 meters, and the information they need is stored in the road-level map, ignoring the details of the lane.

2. Lane-level functions: These functions can obtain lane-level traffic environment details from digital maps, thereby improving the intelligence level of vehicles. When the map is accurate down to the lane level, the navigation system can provide more precise driving assistance.

In order to better support the automatic driving system, it is necessary to design a lane-level path planning system based on the lane-level map. The target application of traditional navigation systems is the human driver, who is responsible for selecting the trajectory in real time. However, when the target user is a self-driving car, the navigation system must provide more detailed guidance to help the vehicle complete the driving task. The existing mature navigation is a route planned at the road level, lacking accurate path planning at the lane level, and is more like a series of driving task instructions rather than a specific trajectory that an autonomous vehicle can follow. Such guidance is precise enough for human drivers. However, in order to achieve autonomous driving, it is necessary to know more about the exact location where the vehicle should continue to drive straight or turn (i.e. to know the lane the vehicle is in, for example, when the vehicle is turning left at the intersection ahead, traditional road-level navigation cannot clearly plan the vehicle Entering the left-turn lane only tells the driver the instruction to turn left, while the lane-level path planning specifies the left-turn lane that the vehicle must enter, making the route of the global path planning accurate to the lane level, greatly reducing the load calculation burden and improving stability of the entire autopilot system). Autonomous vehicles supported by traditional navigation must be equipped with powerful real-time perception and decision-making systems, which greatly increases the burden of on-board computing. In contrast, lane-level navigation provides a reference lane along which a self-driving car can drive in the absence of other vehicles or obstacles. The key difference between lane-level navigation and road-level navigation is that the former can provide precise lanes as control inputs without the help of a situational awareness system. Although the lane-level navigation system cannot replace the real-time perception and decision-making system, it can greatly reduce its computational burden and reduce the risk of system failure.

For the lane-level path planning method for lane-level navigation, the previous method used the lane as a unit to search, but in the case of a large road network, there are many lanes, the connection relationship between lanes is complicated, and the search efficiency is low. Meet the real-time requirements of vehicle operation.

Contents of the invention

The present invention provides a lane-level path planning method for lane-level navigation of automatic driving, which enables the vehicle to quickly and accurately plan the optimal lane sequence from the start point to the end point, that is, the lanes that the vehicle will drive sequentially from the start point to the end point, effectively Serving the automatic driving navigation system.

The technical scheme of the present invention is described as follows in conjunction with accompanying drawing:

A lane-level path planning method for lane-level navigation of automatic driving, comprising the following steps:

Step 1. Establish a lane-level road network model for automatic driving navigation to serve for subsequent lane-level planning;

Step 2. For the lane-level road network model established for automatic driving navigation in step 1, perform hierarchical two-way lane-level path planning based on road-lane group-lane.

The concrete method of described step one is as follows:

G=(R,I) (1)

I为路口集合

N_r为道路集合的元素数目；N_i为路口集合的元素数目；Among them, G is the entire road network; R is the road set

I is the collection of intersections

N _r is the number of elements in the road set; N _i is the number of elements in the intersection set;

r is a road composed of one or more lane groups, and a lane group is composed of lanes with the same driving direction; r is expressed as follows:

r=(LG,q _r ,f,b) (2)

N_lg为车道组集合元素数目；q_r是道路的公共属性，包括道路名称，道路等级，道路长度，道路类型，道路限速，拥堵程度这些属性信息；f是进入该道路的路口或者道路，如果是路口具体由i_f表示，是道路则由r_f表示；b为离开该道路的路口或者道路，如果是路口具体由i_b表示，是道路则由r_b表示；单个车道组lg表示如下：Among them, LG is the set of lane groups

N _lg is the number of lane group set elements; q _r is the public attribute of the road, including road name, road grade, road length, road type, road speed limit, and congestion level; f is the intersection or road entering the road, If it is an intersection, it is specifically represented by _if , and if it is a road, it is represented by r _f ; b is an intersection or road away from the road, if it is an intersection, it is represented by i _b , and if it is a road, it is represented by r _b ; a single lane group lg is represented as follows :

是车道集合，N_l为车道集合元素数目；is_equal取值1或者 -1，1表示车道组的方向与道路定义的前进方向相同，即车道组的前任和后继分别为道路的f和b，而-1为相反；l代表单个车道，表示如下：in,

is the set of lanes, N _l is the number of elements in the set of lanes; is_equal takes the value of 1 or -1, 1 means that the direction of the lane group is the same as the forward direction defined by the road, that is, the predecessor and successor of the lane group are respectively f and b of the road, and -1 is the opposite; l represents a single lane, expressed as follows:

l=(lg, seq, pre, suc, p, q) (4)

Among them, lg is the lane group to which the lane belongs; seq is the serial number of the lane in lg, starting from the side close to the centerline of the road, the serial number increases sequentially from 1; pre is connected to the starting point of the lane, represented by i _pre The intersection or the lane represented by l _pre ; suc is the intersection represented by i _suc or the lane represented by l _suc connected to the end of the lane; p contains the discrete point set representing the lane, including describing the geometric shape and reflecting the change of lane attributes point; q contains attributes corresponding to lanes, including lane width, length, speed limit, congestion level, left and right lane line types;

Intersection i is defined as:

i=(VL,sig) (5)

N_vl为虚拟车道集合元素数目，虚拟车道不是物理层面可见的车道，它连接进入和离开交叉路口的车道并表示它们之间的对应关系；sig为交叉路口属性，其中包含交通信号灯的数量和位置，路口类型；单个虚拟车道vl表示如下：Among them, VL is the set of virtual lanes

N _vl is the number of elements in the set of virtual lanes. The virtual lane is not a lane visible at the physical level. It connects the lanes entering and leaving the intersection and represents the correspondence between them; sig is the attribute of the intersection, which includes the number and location of traffic lights , intersection type; a single virtual lane vl is expressed as follows:

vl＝(l _f ,l _r ,r _f ,r _b ,w,p _vl ) (6)

Among them, l _f , l _r are the lanes entering and leaving the intersection; r _f , r _b are the roads entering and leaving the intersection respectively; w is the way of passing, including going straight, turning left, turning right, and turning around; p _vl is a set of discrete points describing the shape of the virtual lane.

The concrete method of described step 2 is as follows:

21) Path planning is performed at the road layer;

The directed graph G _R for path planning is expressed as:

G _R ＝(V _R , E _R ) (7)

Among them, V _R is the collection of vertices in G _R ; E _R is the collection of G _R edges, and the edges describe the connection relationship between vertices (including which vertex is connected to which vertex, and the attributes of the edges between vertices); in the road layer In path planning, intersections are taken as nodes, roads between intersections are taken as edges, and the directed graph described in (7) is obtained by using formulas (1)-(6).

When the starting point O and the ending point D are given in G _R , using the A* algorithm, the result V _R consisting of a series of road intersections is obtained, expressed by the following equation:

V _R ＝(O,i ₁ ,...,i _k ...,i _n ,D) (8)

Among them, i ₁ , i _k , i _n are respectively the first, kth and last intersections in a series of intersections obtained after the road layer route is determined, and n is the number of nodes (that is, the number of intersections);

A road between a series of intersections is represented as:

E _R ＝(r ₀ ,r ₁ ,…,r _k …,r _n ) (9)

Among them, r ₀ is the road where point O is located; r _n is the road where point D is located; r ₁ is the road between the first intersection i ₁ and the second intersection i ₂ ; r _k is the intersection i _k and i _k Roads between ₊₁ ;

22) Carry out path planning at the lane group layer;

Path planning at the lane group level uses the correspondence between lane groups and roads to refine the planning results at the road level into lane group-based results;

According to the is_equal attribute in formula (3), obtain a set of lane groups consistent with the driving direction of the road in the set E _R as shown in the following formula:

V _lg ＝(lg _O-1 ,…,lg _(k-1)-k ,…,lg _nD ) (10)

Among them, lg _O-1 is the lane group between the starting point O and the first intersection; lg _nD is the lane group between the nth intersection and the destination D; lg _(k-1)-k is the (k- 1) the lane group between the intersection and the kth intersection, k=2,3,...,n;

23) Path planning is performed at the lane level;

According to the path planning result of equation (3) and lane group layer, determine the lane layer node to be selected;

The determination of the lane layer node is to find the best lane layer node according to the lane-level cost in the determined group of lanes V _lg = (lg _O-1 ,...,lg _(k-1)-k ,... ,lg _nD ) , start a two-way search from the starting point and the end point respectively, and find the node with the least cost in each lane group;

Combine the nodes sequentially from the start point to the end point to form the planned lane-level path as follows:

V _l ＝(l _o-1 ,…,l _(k-1)-k ,…,l _nD ) (11)

Among them, l _O-1 is the lane between the starting point O and the first intersection; l _nD is the lane between the nth intersection and the destination D; l _(k-1)-k is the (k-1)th The lane between the intersection and the kth intersection, k=2,3,...,n.

The concrete method of two-way search in described step 22) is as follows:

221) Start forward search from the starting point, and synchronize reverse search from the end point, each step searches for a lane group, according to the q that contains the corresponding lane attribute information in formula (4), using the lane length, speed limit information, and congestion level Generate the cost of each lane, and select the lane with the lowest cost as the target lane; step 1, the forward search determines the optimal lane between the starting point O and the first intersection, and the reverse search determines the distance between the nth intersection and the destination D. from the kth step (k>1), the forward search determines the optimal lane between the k-1th intersection and the k-th intersection, and the reverse search determines the n-k+ The optimal lane between 1 intersection and the n-k+2th intersection;

与路口

之间的最优车道时，此时

反向搜索也确定了路口

与路口

之间的最优车道，此时可以得到完整的车道级路径；当n为偶数时，当正向搜索确定路口

与路口

之间的最优车道时，反向搜索确定路口

与路口

之间的最优车道时，此时还剩路口

与路口

之间的最优车道待定；222) When n is an odd number, when the forward search determines the intersection

with intersection

When the optimal lane between

The reverse search also identifies intersections

with intersection

The optimal lane between , at this time a complete lane-level path can be obtained; when n is an even number, when the forward search determines the intersection

with intersection

When the optimal lane between , reverse search to determine the intersection

with intersection

When the optimal lane between , there are still intersections

with intersection

The optimal lane between is to be determined;

与路口

之间的车道确定，根据路口

路口

与路口

之间的拓扑关系，确定车辆在路口

与路口

之间的道路行驶时最后要进入左转，直行还是右转车道，若最优车道为根据交通规则确定的最后进入车道，则直接确定该车道为这两个路口间规划出的车道；否则计算比较最优车道加上换道的总代价与最后进入车道的代价，选取较小者为规划的车道。223) When n is an even number, for the intersection

with intersection

The lanes between are determined according to the intersection

intersection

with intersection

The topological relationship between to determine the vehicle at the intersection

with intersection

When driving on the road between the two intersections, it is necessary to enter the left-turn, straight-going or right-turning lane at the end. If the optimal lane is the last entering lane determined according to the traffic rules, it is directly determined that the lane is the planned lane between the two intersections; otherwise, calculate Compare the total cost of the optimal lane plus lane change with the cost of entering the last lane, and select the smaller one as the planned lane.

The beneficial effects of the present invention are:

The present invention includes a lane-level road network model for lane-level navigation of automatic driving and a lane-level path planning method proposed for the model, which can quickly and accurately plan the lane-level path of a vehicle from the starting point to the end point, and effectively serve the automatic driving Lane level navigation.

Description of drawings

In order to illustrate the technical solutions of the embodiments of the present invention more clearly, the accompanying drawings used in the embodiments will be briefly introduced below. It should be understood that the following drawings only show some embodiments of the present invention, and thus It should be regarded as a limitation on the scope, and those skilled in the art can also obtain other related drawings based on these drawings without creative work.

Figure 1 is a schematic diagram of a lane-level road network model;

Fig. 2 is a block diagram of the lane-level planning system;

Figure 3 is a schematic diagram of the established test road network;

FIG. 4 is a display diagram of the planned path in the road network.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

The present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments.

Step 1. First, establish a lane-level road network model for automatic driving navigation;

In the present invention, the set of lanes on the same road in the same direction is defined as a lane group. The model established by the present invention involves the relationship between roads, lane groups, and lanes. Example to illustrate: the figure depicts a crossroad where four roads converge, the straight line in the middle of each road represents the road centerline, the three lines on the left and right sides of the road centerline represent three lanes respectively, and the arrows represent the driving direction of the lanes. It can be seen that the lanes of each road have two different driving directions in total, and the lanes with the same driving direction are located on the same side of the road centerline, that is to say, each road has two lane groups located on both sides of the centerline, each A lane group has three lanes. At the same time, at the intersection, there are multiple virtual lanes represented by dotted lines, which connect the lanes entering the intersection and the lanes leaving the intersection to express their connection relationship.

A lane-level road network model for autonomous driving lane-level navigation is established. The model is simple and intuitive, and can be used for efficient lane-level path planning. details as follows:

G = (R, I) (1)

I为路口集合

N_r和 N_i分别为道路集合和路口集合的元素数目。r为由一个或多个车道组组成的道路，而车道组则由相同行驶方向的车道组成；r表示如下：Among them, G is the entire road network; R is the road set

I is the collection of intersections

N _r and N _i are the number of elements in the road set and intersection set respectively. r is a road composed of one or more lane groups, and a lane group is composed of lanes in the same driving direction; r is expressed as follows:

r = (LG, q _r , f, b) (2)

N_lg为车道组集合元素数目；q_r是道路的公共属性，包括道路名称，道路等级，道路长度，道路类型，道路限速，拥堵程度这些属性信息；f是进入该道路的路口或者道路，如果是路口具体由i_f表示，是道路则由r_f表示；b为离开该道路的路口或者道路，如果是路口具体由i_b表示，是道路则由r_b表示；单个车道组lg表示如下：Among them, LG is the set of lane groups

N _lg is the number of lane group set elements; q _r is the public attribute of the road, including road name, road grade, road length, road type, road speed limit, and congestion level; f is the intersection or road entering the road, If it is an intersection, it is specifically represented by _if , and if it is a road, it is represented by r _f ; b is an intersection or road away from the road, if it is an intersection, it is represented by i _b , and if it is a road, it is represented by r _b ; a single lane group lg is represented as follows :

是车道集合，N_l为车道集合元素数目；is_equal取值1或者 -1，1表示车道组的方向与道路定义的前进方向相同，即车道组的前任和后继分别为道路的f和b，而-1为相反；l代表单个车道，表示如下：in,

is the set of lanes, N _l is the number of elements in the set of lanes; is_equal takes the value of 1 or -1, 1 means that the direction of the lane group is the same as the forward direction defined by the road, that is, the predecessor and successor of the lane group are respectively f and b of the road, and -1 is the opposite; l represents a single lane, expressed as follows:

l=(lg, seq, pre, suc, p, q) (4)

Among them, lg is the lane group to which the lane belongs; seq is the serial number of the lane in lg, starting from the side close to the centerline of the road, the serial number increases sequentially from 1; pre is connected to the starting point of the lane, represented by i _pre The intersection or the lane represented by l _pre ; suc is the intersection represented by i _suc or the lane represented by l _suc connected to the end of the lane; p contains the discrete point set representing the lane, including describing the geometric shape and reflecting the change of lane attributes point; q contains attributes corresponding to lanes, including lane width, length, speed limit, congestion level, left and right lane line types;

Intersection i is defined as:

i=(VL,sig) (5)

N_vl为虚拟车道集合元素数目，虚拟车道不是物理层面可见的车道，它连接进入和离开交叉路口的车道并表示它们之间的对应关系；sig为交叉路口属性，其中包含交通信号灯的数量和位置，路口类型；单个虚拟车道vl表示如下：Among them, VL is the set of virtual lanes

N _vl is the number of elements in the set of virtual lanes. The virtual lane is not a lane visible at the physical level. It connects the lanes entering and leaving the intersection and represents the correspondence between them; sig is the attribute of the intersection, which includes the number and location of traffic lights , intersection type; a single virtual lane vl is expressed as follows:

vl＝(l _f ,l _r ,r _f ,r _b ,w,p _vl ) (6)

Among them, l _f and l _r are the lanes entering and leaving the intersection respectively; r _f and r _b are the roads entering and leaving the intersection respectively; w is the way of passing, including going straight, turning left, turning right, turning around, etc.; p _vl is a set of discrete points describing the shape of the virtual lane.

Step 2. Based on the lane-level road network model established in step 1, perform hierarchical two-way lane-level path planning based on road-lane group-lane;

The method can leverage mature navigation techniques developed on road networks for fast and efficient path planning. Through the correspondence between roads, lane groups, and lanes, lane-level path planning can be accelerated, thereby reducing the complexity of direct lane-level path planning.

Referring to Fig. 2, on the basis of the lane-level road network model established in step 1, the specific method of said step 2 is as follows:

21) Path planning is performed at the road layer;

When performing long-distance planning at the road level, the cost of intersections has relatively little influence at this time, and the intersection cost can be ignored and the intersections can be regarded as nodes and roads as edges of the directed graph.

The road layer directed graph G _R is expressed as:

G _R ＝(V _R , E _R ) (7)

Among them, V _R is the set of nodes in _GR ; E _R is the set of _GR edges; the edge describes the connection relationship between vertices (including which vertex is connected to which vertex, and the attributes of the edges between vertices); in the road layer In path planning, intersections are taken as nodes, roads between intersections are taken as edges, and the directed graph described in (7) is obtained by using formulas (1)-(6). When the starting point O and the ending point D are given in G _R , using the A* algorithm, the result V _R consisting of a series of road intersections is obtained, expressed by the following equation:

V _R =(O,i ₁ ,...,i _k ...,i _n ,D) (8)

Among them, i ₁ , i _k , i _n are respectively the first, kth and last intersections in a series of intersections obtained after the road layer route is determined, and n is the number of nodes (that is, the number of intersections);

A road between a series of intersections is represented as:

E _R ＝(r ₀ ,r ₁ ,…,r _k …,r _n ) (9)

Among them, r ₀ is the road where point O is located; r _n is the road where point D is located; r ₁ is the road between the first intersection i ₁ and the second intersection i ₂ ; r _k is the intersection i _k and i _{k +1} for the road between.

22) Carry out path planning at the lane group layer;

Path planning at the lane group level uses the correspondence between lane groups and roads to refine the planning results at the road level into lane group-based results;

According to the is_equal attribute in formula (3), obtain a set of lane groups consistent with the driving direction of the road in the set E _R as shown in the following formula:

V _lg ＝(lg _O-1 ,…,lg _(k-1)-k ,…,lg _nD ) (10)

Among them, lg _O-1 is the lane group between the starting point O and the first intersection; lg _nD is the lane group between the nth intersection and the destination D; lg _(k-1)-k is the (k- 1) the lane group between the intersection and the kth intersection, k=2,3,...,n;

24) Carry out path planning at the lane level;

According to the path planning result of equation (3) and lane group layer, determine the lane layer node to be selected;

Then, constraints introduced by traffic rules or road conditions should be considered. Imagine an intersection where left turns are determined by a sequence of lane group nodes, and that lane group node includes three lane layer nodes. According to traffic rules, the leftmost lane layer node is the only feasible lane layer node. To consider similar situations in path planning, it is necessary to eliminate infeasible nodes based on information about traffic rules and lane connectivity.

The determination of the lane layer node is to find the best lane layer node according to the lane-level cost in the determined group of lanes V _lg = (lg _O-1 ,...,lg _(k-1)-k ,... ,lg _nD ) , start a two-way search from the starting point and the end point respectively, and find the node with the least cost in each lane group;

The specific method of the two-way search is as follows:

221) Start forward search from the starting point, and synchronize reverse search from the end point, each step searches for a lane group, according to the q that contains the corresponding lane attribute information in formula (4), using the lane length, speed limit information, and congestion level Generate the cost of each lane, and select the lane with the lowest cost as the target lane; step 1, the forward search determines the optimal lane between the starting point O and the first intersection, and the reverse search determines the distance between the nth intersection and the destination D. from the kth step (k>1), the forward search determines the optimal lane between the k-1th intersection and the k-th intersection, and the reverse search determines the n-k+ The optimal lane between 1 intersection and the n-k+2th intersection;

与路口

之间的最优车道时，此时

反向搜索也确定了路口

与路口

之间的最优车道，此时可以得到完整的车道级路径；当n为偶数时，当正向搜索确定路口

与路口

之间的最优车道时，反向搜索确定路口

与路口

之间的最优车道时，此时还剩路口

与路口

之间的最优车道待定；222) When n is an odd number, when the forward search determines the intersection

with intersection

When the optimal lane between

The reverse search also identifies intersections

with intersection

The optimal lane between , at this time a complete lane-level path can be obtained; when n is an even number, when the forward search determines the intersection

with intersection

When the optimal lane between , reverse search to determine the intersection

with intersection

When the optimal lane between , there are still intersections

with intersection

The optimal lane between is to be determined;

与路口

之间的车道确定，根据路口

路口

与路口

之间的拓扑关系，确定车辆在路口

与路口

之间的道路行驶时最后要进入左转，直行还是右转车道，若最优车道为根据交通规则确定的最后进入车道(左转，则直接确定该车道为这两个路口间规划出的车道；否则计算比较最优车道加上换道的总代价与最终进入车道的代价，选取较小者为规划的车道。223) When n is an even number, for the intersection

with intersection

The lanes between are determined according to the intersection

intersection

with intersection

The topological relationship between to determine the vehicle at the intersection

with intersection

If the optimal lane is the last entry lane determined according to the traffic rules (turn left, then it is directly determined that the lane is the lane planned between the two intersections) ; Otherwise, calculate and compare the optimal lane plus the total cost of changing lanes and the final cost of entering the lane, and select the smaller one as the planned lane.

Combine the nodes sequentially from the start point to the end point to form the planned lane-level path as follows:

V _l = (l _O-1 , ..., l _(k-1)-k , ..., l _nD ) (11)

Among them, l _O-1 is the lane between the starting point O and the first intersection; l _nD is the lane between the nth intersection and the destination D; l _(k-1)-k is the (k-1)th The lane between the intersection and the kth intersection, k=2,3,...,n.

In order to illustrate the effectiveness of the present invention, a road network has been established as shown in Figure 3, in which there are 16 vertices and 24 edges in total, wherein the vertices represent intersections, and the edges represent roads, and the vertices are all intersections of edges, and the x axis A total of four vertices on the above are located at the x coordinates of 0, 2, 9, and 15, and a total of four vertices on the y axis are located at the y coordinates of 0, 3, 7, and 12 respectively. The horizontal roads of a single intersection are parallel to the x-axis, the three bottommost roads coincide with the x-axis, the vertical roads are parallel to the y-axis, and the three leftmost roads coincide with the y-axis. The circle on the right side of the figure depicts the situation inside the intersection (intersection) at the road network circle on the left. It can be seen that there are four roads entering this intersection. The serial numbers 1-6 represent the lane numbers, and the arrows represent the lanes. Driving direction, the dotted line indicates the center line of the road. It can be seen that each road entering the intersection has two lane groups, and each lane group has three lanes. We set the driving rules of the lanes as follows: left lane turn left, middle lane Go straight in the lane and turn right in the right lane.

The value on the right side of each longitudinal side (road) and the value above each horizontal side (road) are the average road speed V _road , and the unit is km/h. The length of each road can be known from the scale value on the coordinate system. The entire road is square, with a total length of 15km in the horizontal direction and 12km in the vertical direction. For the average driving speed V _lane in the lane, we set the V _lane of the two lanes closest to the centerline of the road (the 3 and 4 lanes in the circle on the right in the figure) as V _road +10, and the middle lane of each lane group (Lane 2 and Lane 5 in the circle on the right in the figure) is V _road , and the V _lane of the two lanes farthest from the centerline of the road (lane ₁ and 6 in the circle on the right in the figure) is V _roa d-10.

Aiming at the shortest total time, use the lane-level path planning method of the present invention to plan the shortest path from the lower left vertex A to the upper right vertex B. As shown in Figure 4, the planned path is represented by a bold line.

As can be seen from Fig. 4, using the lane-level path planning method described in the present invention, the average speed of the roads passed by the planned path is all higher, which can be verified by dividing the road distance by the average speed, and the planning represented by the thick black line The path satisfies the goal of the shortest time. The circle on the right of Figure 4 is an enlarged view of the indicated intersection, and the arrow indicated by a dotted line is the planned lane. It can be seen that since the road from the bottom to the top road has to go straight through, Therefore, when entering the intersection, it is planned to use the middle lane, which satisfies the requirement of the traffic rules to go straight. The 4 lanes close to the centerline of the road meet the goal of the shortest driving time.

Combining the embodiments, it can be seen that a lane-level path planning method for automatic driving lane-level navigation proposed by the present invention includes a lane-level road network model for automatic driving lane-level navigation and a lane-level path planning method proposed for the model It can effectively and accurately plan the lane-level path of the vehicle from the starting point to the ending point, and effectively serve the automatic driving navigation system.

The preferred implementation of the present invention has been described in detail above in conjunction with the accompanying drawings, but the protection scope of the present invention is not limited to the specific details of the above-mentioned implementation. Within the scope of the technical concept of the present invention, any person skilled in the art Within the technical scope disclosed in the present invention, equivalent replacements or changes are made according to the technical solutions and the inventive concepts of the present invention, and these simple modifications all belong to the protection scope of the present invention.

In addition, it should be noted that the various specific technical features described in the above specific embodiments can be combined in any suitable way if there is no contradiction. The combination method will not be described separately.

In addition, various combinations of different embodiments of the present invention can also be combined arbitrarily, as long as they do not violate the idea of the present invention, they should also be regarded as the disclosed content of the present invention.

Claims (1)

1. A lane-level path planning method for automatic driving lane-level navigation is characterized by comprising the following steps:

firstly, establishing a lane-level road network model facing automatic driving navigation to serve subsequent lane-level planning;

step two, aiming at a lane level road network model established in the step one and facing the automatic driving navigation, performing hierarchical bidirectional lane level path planning based on roads, lane groups and lanes;

the specific method of the step one is as follows:

G＝(R,I) (1)

wherein G is the whole road network; r is road set

I is a crossing set

N _r Number of elements that are a set of roads; n is a radical of hydrogen _i Number of elements aggregated for intersections;

r is a road composed of one or more lane groups, and the lane groups are composed of lanes with the same driving direction;

r is represented as follows:

r＝(LG,q _r ,f,b) (2)

wherein LG is a set of lane groups

N _lg Gathering the number of elements for the lane group; q. q.s _r The public attributes of the road comprise attribute information such as road name, road grade, road length, road type, road speed limit and congestion degree; f is the intersection or road entering the road, if the intersection is specifically defined by i _f Indicates that the road is represented by r _f Represents; b is the intersection or road leaving the road, if the intersection is specifically composed of i _b Indicates that the road is represented by r _b Represents; the lane group lg to which this lane belongs is represented as follows:

wherein,

is a set of lanes; n is a radical of hydrogen _l The number of elements is set for the lane; the is _ equivalent value is 1 or-1, 1 indicates that the direction of the lane group is the same as the advancing direction defined by the road, namely the former and the latter of the lane group are f and b of the road respectively, and-1 is opposite; l represents a single lane, as follows:

l＝(lg,seq,pre,suc,p,q) (4)

wherein lg is a lane group to which the lane belongs; seq is the serial number of the lane in lg, and the serial numbers increase from 1 from the side close to the center line of the road(ii) a pre is connected with the start of the lane _pre An intersection represented by _pre The indicated lane; suc is a unit of i connected to the end of the lane _suc An intersection represented by _suc The indicated lane; p contains a set of discrete points representing the lane, including points describing the geometry and reflecting changes in lane properties; q contains attributes corresponding to the lanes, including the width, length, speed limit, congestion level, left and right lane line types of the lanes;

intersection i is defined as:

i＝(VL,sig) (5)

where VL is a set of virtual lanes

N _vl The number of elements of the virtual lane set is the number of the virtual lane set elements, the virtual lane is not a physical layer visible lane, and the virtual lane is used for connecting lanes entering and leaving the intersection and representing the corresponding relation between the lanes; sig is the attribute of the intersection, including the number and position of traffic lights and the type of the intersection; the single virtual lane vl is represented as follows:

vl＝(l _f ,l _r ,r _f ,r _b ,w,p _vl ) (6)

wherein l _f ，l _r Lanes entering and leaving the intersection, respectively; r is _f ,r _b Roads entering and leaving the intersection, respectively; w is a passing mode, including straight going, left turning, right turning and turning around; p is a radical of formula _vl A set of discrete points describing a virtual lane shape;

the specific method of the second step is as follows:

21 Path planning at road level;

directed graph G for path planning _R Expressed as:

G _R ＝(V _R ,E _R ) (7)

wherein, V _R Is G _R A set of medium vertices; e _R Is G _R A set of edges, the edges describing a connection relationship between vertices; when the path planning is carried out on the road layer, the intersection is taken as a node,taking roads between intersections as edges, and obtaining a directed graph described by (7) by using formulas (1) - (6);

when in G _R When the starting point O and the end point D are given, the result V consisting of a series of road intersections is obtained by using an A-x algorithm _R Expressed by the following equation:

V _R ＝(O,i ₁ ,…,i _k …,i _n ,D) (8)

wherein i _k Is the kth intersection in a series of intersections obtained after the road layer route is determined, and n is the number of nodes, namely the number of intersections;

the roads between a series of intersections are represented as:

E _R ＝(r ₀ ,r ₁ ,…,r _k …,r _n-1 ,r _n ) (9)

wherein r is ₀ Is the road on which the point O is located; r is _n Is the road on which point D is located; r is a radical of hydrogen ₁ Is the 1 st intersection i ₁ And 2 nd intersection i ₂ The road therebetween; r is a radical of hydrogen _k Is intersection i _k And, i _k+1 The road therebetween;

22 Path planning at lane group level;

the path planning of the lane group level uses the corresponding relation between the lane group and the road, and the planning result of the road level is refined into a result based on the lane group;

obtaining and collecting E according to the is _ equivalent attribute in the formula (3) _R The set of lanes in which the driving directions of the roads are consistent is shown as follows:

wherein,

is a lane group between the starting point O and the first intersection;

a lane group between the nth intersection and the destination D;

k =2,3, \ 8230for the lane group between the (k-1) th intersection and the k-th intersection, n;

23 Path planning at the lane level;

determining a lane layer node to be selected according to equation (3) and a path planning result of a lane group layer;

the lane layer nodes are determined in a determined set of lane groups

Finding the optimal lane layer node according to the lane level cost, respectively carrying out bidirectional search from a starting point and an end point, and finding the node with the minimum cost in each lane group;

the nodes are sequentially combined from the starting point to the end point to form a planned lane-level path as follows:

V _l ＝(l _O-1 ,…,l _(k-1)-k ,…,l _n-D ) (11)

wherein l _O-1 Is a lane between the starting point O and the first intersection; l _n-D A lane between the nth crossing and the destination D; l. the _(k-1)-k Is a lane between the (k-1) th intersection and the k-th intersection, k =2,3, \ 8230;, n;

the specific method of bidirectional search in step 22) is as follows:

221 Starting forward search from a starting point, synchronously starting reverse search from a terminal point, searching a lane group in each step, generating the cost of each lane by using the length of the lane, speed limit information and congestion degree according to q containing corresponding lane attribute information in a formula (4), and selecting the lane with the lowest cost as a target lane; step 1, forward searching to determine an optimal lane between a starting point O and a first intersection, and backward searching to determine an optimal lane between an nth intersection and a destination D; from the kth step, k is greater than 1, the optimal lane between the kth crossing and the kth crossing is determined by forward search, and the optimal lane between the (n-k + 1) th crossing and the (n-k + 2) th crossing is determined by reverse search;

222 When n is odd, when the forward search determines the intersection

Crossing with

When the optimal lane in between, at this time

Reverse search also determines intersections

Crossing with

The optimal lane between the two can obtain a complete lane-level path; when n is even number, crossing is determined by forward search

Crossing with

When the optimal lane is in between, the reverse search is carried out to determine the intersection

Crossing with

When the optimal lane is in between, the left road junction is still at the time

Crossing with

The optimal lane between is undetermined;

223 When n is even, for intersections

Crossing with

According to the crossing, determining the lane between

Crossing

Crossing with

Determine the vehicle is at the intersection

Crossing with

When the road between the two roads is driven, the vehicle finally enters a left-turn lane, a straight-going lane or a right-turn lane, and if the optimal lane is the last lane entering the road determined according to the traffic rules, the lane is directly determined as the lane planned between the two intersections; otherwise, calculating and comparing the total cost of the optimal lane plus lane change with the cost of entering the lane at last, and selecting the smaller one as the planned lane.

Images