CN113155145A - Lane-level path planning method for automatic driving lane-level navigation - 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, establishing 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, carry out a hierarchical two-way lane 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 travel in sequence from the starting point to the ending point, and effectively serve the automatic driving navigation system.

Description

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

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 are relying on digital map navigation systems on their 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 has required increasing assistance from digital maps. In the near future, digital map navigation system will play an increasingly important role in the transportation system. To extend existing navigation systems to more applications, two fundamental problems must be addressed: lane-level map models and lane-level path planning. Many smart driving functions based on digital maps have been developed. The intelligent driving features supported by these maps can be further divided into the following two categories:

1. Road-level features: These features are usually designed to assist human drivers, and the required accuracy is usually around 10 meters. The information they require is stored in road-level maps, ignoring lane details.

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

To better support autonomous driving systems, it is necessary to design a lane-level path planning system based on lane-level maps. The target application for traditional navigation systems is the human driver, who is responsible for choosing a 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. Existing mature navigation is a route planned at the road level, lacking path planning accurate to the lane level, and more like a series of driving task instructions than a specific trajectory that an autonomous vehicle can follow. Such guidance is accurate enough for a human driver. However, in order to achieve autonomous driving, it is necessary to know more about the exact position where the vehicle should continue to drive straight or turn (i.e. to know which lane the vehicle is in, for example, when the vehicle is turning left at the intersection ahead, traditional road-level navigation cannot explicitly plan the vehicle When entering the left-turn lane, it only tells the driver to turn left, while the lane-level path planning clarifies the left-turn lane that the vehicle must enter, so that the route of the global path planning is accurate to the lane level, which greatly reduces the load calculation burden and improves the whole autopilot system stability). Autonomous vehicles supported by traditional navigation must be equipped with powerful real-time perception and decision-making systems, which greatly increases the computational burden on the vehicle. In contrast, lane-level navigation provides a reference lane that autonomous vehicles can follow in the absence of other vehicles or obstacles. The key difference between lane-level navigation and road-level navigation is that the former is able to provide precise lanes as control input without the help of an environment perception 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 past methods used lanes as a unit to search, but in the case of a large road network, the number of lanes is large, the connection relationship between lanes is complex, the search efficiency is low, and it is difficult to Meet the real-time requirements of vehicle operation.

SUMMARY OF THE INVENTION

The invention provides a lane-level path planning method for automatic driving lane-level navigation, which 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 travel in sequence from the starting point to the ending point, effectively Serving in the automatic driving navigation system.

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

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

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

Step 2: According to the lane-level road network model established for automatic driving navigation in step 1, perform hierarchical bidirectional lane-level path planning based on road-lane group-lane.

The specific method of the step 1 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 intersection set

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

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

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

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

N _lg is the number of lane group set elements; q _r is the public attributes of the road, including road name, road grade, road length, road type, road speed limit, congestion degree and other attribute information; f is the intersection or road entering the road, If the intersection is specifically represented by i _f , if it is a road, it is represented by r _f ; b is the intersection or road leaving the road, if the intersection is specifically represented by i _b , and 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 lane set, N _l is the number of lane set elements; is_equal takes the value 1 or -1, 1 indicates 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 the f and b of the road respectively, 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 center line of the road, and the serial number increases sequentially from 1; pre is connected to the starting point of the lane, represented by i _pre The intersection or 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 set of points representing the lane, including the description of the geometric shape and the reflection of lane attribute changes point; q contains attributes corresponding to lanes, including lane width, length, speed limit, congestion level, left and right lane line types;

The 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 virtual lane set elements, the virtual lane is not the lane visible at the physical level, it connects the lanes entering and leaving the intersection and represents the corresponding relationship between them; sig is the intersection attribute, which includes the number and location of traffic lights , the intersection type; a single virtual lane vl is represented 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, respectively; 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 making a U-turn; p _vl is a set of discrete points describing the shape of the virtual lane.

The specific method of the second step is as follows:

21) Carry out path planning at the road layer;

The directed graph _GR used for path planning is expressed as:

G _R = (VR , _ER ) ₍ 7)

Among them, VR is the set of vertices in _GR ; _ER is the set of _{GR 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 During path planning, the intersections are used as nodes, and the roads between the intersections are used 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 _GR , using the _A * algorithm, the result VR consisting of a series of road intersections is obtained, expressed by the following equation:

_VR = (O,i ₁ ,..., _{i k} ...,in ,D) (8)

Among them, i ₁ , i _k , i _n are respectively the first, k-th and last intersection 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} …,rn ) (9)

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

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

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

According to the _{is_equal} attribute in formula (3), a set of lane groups consistent with the driving direction of the road in the set ER is obtained 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 k-th intersection, k=2,3,...,n;

23) Carry out path planning at the lane layer;

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

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

The planned lane-level path is formed by sequentially combining the nodes from the start point to the end point 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 lane The lane between the intersection and the k-th intersection, k=2,3,...,n.

The concrete method of bidirectional search in described step 22) is as follows:

221) Start the forward search from the starting point, and synchronously start the reverse search from the end point, each step searches for a lane group, according to the q containing the corresponding lane attribute information in formula (4), using the lane length, speed limit information, congestion degree The cost of each lane is generated, and the lane with the lowest cost is selected as the target lane; in the first step, 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 kth intersection, and the reverse search determines the n-k+th The optimal lane between 1 intersection and the n-k+2th intersection;

与路口

之间的最优车道时，此时

反向搜索也确定了路口

与路口

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

与路口

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

与路口

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

与路口

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

with the intersection

when the optimal lane between

The reverse search also identifies the intersection

with the intersection

At this time, the complete lane-level path can be obtained; when n is an even number, when the forward search determines the intersection

with the intersection

When the optimal lane between, the reverse search determines the intersection

with the intersection

When the optimal lane between the

with the intersection

The optimal lane between is to be determined;

与路口

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

路口

与路口

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

与路口

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

with the intersection

The lanes between are determined according to the intersection

intersection

with the intersection

The topological relationship between the vehicles is determined at the intersection

with the intersection

When driving on the road between the two intersections, it is necessary to enter the left turn, straight or right turn lane. If the optimal lane is the last entry lane determined according to the traffic rules, then directly determine the lane as the lane planned between the two intersections; otherwise, calculate Compare the total cost of the optimal lane plus lane change and the cost of entering the lane at the end, 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 automatic driving lane-level navigation and a lane-level path planning method proposed for the model, which can quickly and accurately plan the lane-level path of the 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 following briefly introduces the accompanying drawings used in the embodiments. It should be understood that the following drawings only show some embodiments of the present invention, and therefore do not It should be regarded as a limitation of the scope, and for those of ordinary skill in the art, other related drawings can also be obtained according to these drawings without any creative effort.

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

Figure 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 route in the road network.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within 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 in the same direction in the same road is defined as a lane group. The model established in the present invention involves the relationship between the road, the lane group, and the lanes. Example to illustrate: the figure depicts an intersection where four roads join, 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 a total of two different driving directions, in which the lanes with the same driving direction are located on the same side of the road centerline, that is, 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 automatic 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 intersection set

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

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

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

N _lg is the number of lane group set elements; q _r is the public attributes of the road, including road name, road grade, road length, road type, road speed limit, congestion degree and other attribute information; f is the intersection or road entering the road, If it is an intersection, it is represented by i _f , and if it is a road, it is represented by r _f ; _b is the intersection or road that leaves the road. If it is an intersection, it is represented by i _b , and it is a road. :

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

is the lane set, N _l is the number of lane set elements; is_equal takes the value 1 or -1, 1 indicates 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 the f and b of the road respectively, 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 center line of the road, and the serial number increases sequentially from 1; pre is connected to the starting point of the lane, represented by i _pre The intersection or 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 set of points representing the lane, including the description of the geometric shape and the reflection of lane attribute changes point; q contains attributes corresponding to lanes, including lane width, length, speed limit, congestion level, left and right lane line types;

The 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 virtual lane set elements, the virtual lane is not a lane visible at the physical level, it connects the lanes entering and leaving the intersection and represents the corresponding relationship between them; sig is the intersection attribute, which includes the number and location of traffic lights , the intersection type; a single virtual lane vl is represented 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 , r _b are the roads entering and leaving the intersection, respectively; w is the way of passing, including going straight, turning left, turning right, U-turn, 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 bidirectional lane-level path planning based on road-lane group-lane;

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

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

21) Carry out path planning at the road layer;

When carrying out long-distance planning at the road level, the cost of the intersection is relatively small at this time, and the intersection cost can be ignored and the intersection is regarded as a node, and the road is regarded as the edge of the directed graph.

The road layer directed graph _GR is expressed as:

G _R = (VR , _ER ) ₍ 7)

Among them, VR is the set of nodes in _GR ; _ER is the set of _{GR edges} ; the edge describes the connection relationship between vertices (including which vertex is connected to which vertex, the attributes of the edge between vertices); in the road layer During path planning, the intersections are used as nodes, and the roads between the intersections are used 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 _GR , using the _A * algorithm, the result VR consisting of a series of road intersections is obtained, expressed by the following equation:

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

Among them, i ₁ , i _k , i _n are respectively the first, k-th and last intersection 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} …,rn ) (9)

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

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

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

According to the _{is_equal} attribute in formula (3), a set of lane groups consistent with the driving direction of the road in the set ER is obtained 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 k-th intersection, k=2,3,...,n;

24) Carry out path planning at the lane layer;

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

Then, constraints introduced by traffic rules or road conditions should be considered. Imagine that at an intersection, a left turn is 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 account for 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 nodes is to find the best lane layer node according to the lane level cost in the determined set of lane groups V _lg =(lg _O-1 ,...,lg _(k-1)-k ,...,lg _nD ) , perform a two-way search from the starting point and the ending 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 the forward search from the starting point, and synchronously start the reverse search from the end point, each step searches for a lane group, according to the q containing the corresponding lane attribute information in formula (4), using the lane length, speed limit information, congestion degree The cost of each lane is generated, and the lane with the lowest cost is selected as the target lane; in the first step, 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 kth intersection, and the reverse search determines the n-k+th The optimal lane between 1 intersection and the n-k+2th intersection;

与路口

之间的最优车道时，此时

反向搜索也确定了路口

与路口

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

与路口

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

与路口

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

与路口

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

with the intersection

when the optimal lane between

The reverse search also identifies the intersection

with the intersection

At this time, the complete lane-level path can be obtained; when n is an even number, when the forward search determines the intersection

with the intersection

When the optimal lane between, the reverse search determines the intersection

with the intersection

When the optimal lane between the

with the intersection

The optimal lane between is to be determined;

与路口

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

路口

与路口

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

与路口

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

with the intersection

The lanes between are determined according to the intersection

intersection

with the intersection

The topological relationship between the vehicles is determined at the intersection

with the intersection

When driving on the road in between, you should finally enter the left-turn, straight-turn or right-turn lane. If the optimal lane is the last entry lane determined according to the traffic rules (turn left, then directly determine that the lane is the one planned between the two intersections. Lane; otherwise, calculate and compare the total cost of the optimal lane plus lane change and the final cost of entering the lane, and select the smaller one as the planned lane.

The planned lane-level path is formed by sequentially combining the nodes from the start point to the end point 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 lane The lane between the intersection and the k-th intersection, k=2,3,...,n.

In order to illustrate the effectiveness of the present invention, a road network is established as shown in Figure 3. There are 16 vertices and 24 edges in the figure. The vertices represent intersections, the edges represent roads, and the vertices are the intersections of the edges. The x-axis A total of four vertices are located at x-coordinates 0, 2, 9, and 15, respectively, and a total of four vertices on the y-axis are located at y-coordinates of 0, 3, 7, and 12. The horizontal roads of a single intersection are parallel to the x-axis, the three lowermost roads are coincident with the x-axis, the longitudinal roads are parallel to the y-axis, and the three leftmost roads are coincident with the y-axis. The circle on the right side of the figure depicts the interior of the intersection (intersection) at the circle on the left side of the road network. 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. The driving direction, the dotted line represents 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. Go straight in the lane, 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 in 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 horizontal length of 15km and a vertical total length of 12km. For the average driving speed V _lane in the lane, we set the V lane of the two lanes closest to the road centerline (lanes 3 and 4 in the right circle in the figure) as V _road +10, and the middle _lane of each lane group The V _lane (lanes 2 and 5 in the circle on the right in the figure) is V _road , and the V _lanes of the two lanes farthest from the road centerline (lanes 1 and 6 in the circle on the right in the figure) are V _roa d-10.

Taking the shortest total time as the goal, the lane-level path planning method of the present invention is used to plan the shortest time path from the lower left vertex A to the upper right vertex B. As shown in Figure 4, the planned paths are represented by bold lines.

As can be seen from FIG. 4 , using the lane-level path planning method described in the present invention, the average speed of the road traversed by the planned path is relatively high, which can be verified by dividing the road distance by the average speed. The planning represented by the thick black line The path satisfies the goal of the shortest time. The circle on the right in Figure 4 is an enlarged view of the indicated intersection, and the arrows represented by dotted lines are the planned lanes. Therefore, when entering the intersection, it is planned to take the middle lane, which meets the requirements of the traffic rules to go straight to the middle lane. The 4 lanes near the centerline of the road meet the goal of the shortest travel time.

With reference to 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 embodiments of the present invention have been described in detail above in conjunction with the accompanying drawings, however, the protection scope of the present invention is not limited to the specific details in the above-mentioned embodiments. Within the technical scope disclosed by the present invention, equivalent replacements or changes are made according to the technical solutions and the inventive concept 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 specific technical features described in the above-mentioned specific embodiments can be combined in any suitable manner unless they are inconsistent. In order to avoid unnecessary repetition, the present invention provides The combination method will not be specified otherwise.

In addition, the various embodiments of the present invention can also be combined arbitrarily, as long as they do not violate the spirit of the present invention, they should also be regarded as the contents disclosed in the present invention.

Claims (4)

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;

and step two, aiming at the lane-level road network model established in the step one for the automatic driving navigation, performing the hierarchical bidirectional lane-level path planning based on the road, the lane group and the lane.

2. The lane-level path planning method for the automatic driving lane-level navigation according to claim 1, wherein the specific method of the first step is as follows:

G＝(R,I) (1)

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

I is a crossing set

N_rNumber of elements that are a set of roads; n is a radical of_iNumber of elements that are an intersection set;

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_lgAggregating the number of elements for the lane group; q. q.s_rThe 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_fIndicates that the road is represented by r_fRepresents; b is the intersection or road leaving the road, if the intersection is specifically composed of i_bIndicates that the road is represented by r_bRepresents; the lane group lg to which this lane belongs is represented as follows:

wherein,

is a set of lanes; n is a radical of_lThe number of elements is set for the lane; the is _ equivalent takes a value of 1 or-1, wherein 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 one side close to the center line of the road; pre is connected with the start of the lane_preAn intersection represented by_preThe lane represented; suc is a unit of i connected to the end of the lane_sucAn intersection represented by_sucThe lane represented; 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_vlThe 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_rLanes entering and leaving the intersection, respectively; r is_f,r_bRoads entering and leaving the intersection, respectively; w is by way of passage, including straightGoing, turning left, turning right, turning around; p is a radical of_vlA discrete set of points describing the shape of a virtual lane.

3. The lane-level path planning method for the automatic driving lane-level navigation according to claim 2, wherein the specific method of the second step is as follows:

21) planning a path on a road layer;

directed graph G for path planning_RExpressed as:

G_R＝(V_R,E_R) (7)

wherein, V_RIs G_RA set of medium vertices; e_RIs G_RA set of edges, the edges describing a connection relationship between vertices; when path planning is carried out on a road layer, intersections are used as nodes, roads between the intersections are used as edges, and a directed graph described in the formula (7) is obtained by using the formulas (1) - (6);

when in G_RWhen 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_RExpressed by the following equation:

V_R＝(O,i₁,…,i_k…,i_n,D) (8)

wherein i_kIs 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_nIs the road on which point D is located; r is₁Is the 1 st intersection i₁And 2 nd intersection i₂The road therebetween; r is_kIs intersection i_kAnd i_k+1The road therebetween;

22) planning a path on a lane group layer;

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)_RThe set of lanes in which the driving directions of the roads are consistent is shown as follows:

V_lg＝(lg_O-1,…,lg_(k-1)-k,…,lg_n-D) (10)

wherein, lg_O-1Is a lane group between the starting point O and the first intersection; lg_n-DA lane group between the nth crossing and the destination D; lg_(k-1)-kIs a lane group between the (k-1) th intersection and the k-th intersection, and k is 2,3, …, n;

23) planning a path on a lane layer;

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 V_lg＝(lg_O-1,…,lg_(k-1)-k,…,lg_n-D) 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-1Is a lane between the starting point O and the first intersection; l_n-DA lane between the nth crossing and the destination D; l_(k-1)-kA lane between the (k-1) th intersection and the k-th intersection, where k is 2,3, …, n.

4. The method for planning a lane-level path for automatic driving lane-level navigation according to claim 3, wherein 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 step k (k >1), determining the optimal lane between the k-1 st intersection and the k-th intersection by forward search, and determining the optimal lane between the n-k +1 th intersection and the n-k +2 th intersection by reverse search;

222) when n is odd number, the intersection is determined by forward search

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 number, for the intersection

Crossing with

According to the intersection

Crossing

Crossing with

Determine the vehicle is at the intersection

Crossing with

When the road between the two roads runs, the road is to enter a left-turn lane, a straight-going lane or a right-turn lane at last, if the optimal lane is the last lane to enter determined according to the traffic rules, the lane is directly determined to be the lane planned between the two intersections; otherwise calculateAnd 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