KR20180040760A - Apparatus and method for searching path of autonomous driving vehicle - Google Patents

Abstract

A route search apparatus for an autonomous vehicle according to the present invention includes a communication module, a memory storing a program for route search, and a processor for executing a program stored in the memory, wherein the processor executes, A source link and a destination link are set from the generated precise map and the path cost corresponding to the lane length is allocated to the source link and added to the first list, Extracts neighboring lane links, adds the extracted lane links to the first list, moves the lane link with the minimum path cost from the first list to the second list, If the lane link with path cost is the destination link, Trace back the connection information to set the final route.

Description

[0001] APPARATUS AND METHOD FOR SEARCHING PATH OF AUTONOMOUS DRIVING VEHICLE [0002]

The present invention relates to a route search apparatus and method for an autonomous vehicle, and more particularly, to an apparatus and a method for searching an autonomous travel situation and a route necessary for a control using a center line of a car.

An autonomous vehicle means a vehicle that can identify the road situation by itself and arrive at its destination without the driver's operation.

The autonomous navigation technology applied to the autonomous driving vehicle searches and generates the global path-planning and the local path-planning based on the detection area of the sensor mounted on the autonomous vehicle, Thereby controlling the autonomous vehicle.

In this case, the global route refers to a route set up to a destination in consideration of a large-scale geographical characteristic such as a mountain or a lake, and a risk based on a precise map provided in advance.

And the local path extracts the topographic information such as the terrain slope and roughness and the various obstacle information from the data of the most recently obtained within several tens of meters through various sensors, Means a route set in real time in terms of safety and stability.

However, the conventional route search method in an autonomous vehicle requires a large amount of data in searching for a global route for autonomous travel, which is difficult to apply to actual travel.

In this regard, Korean Patent Laid-Open Publication No. 10-2015-0115069 (entitled " Method and apparatus for generating travel route of autonomous vehicle with autonomous vehicle ") discloses a method of locating an intermediate point between a start node and an end node And the learning range of the intermediate point is varied based on the distance between the vehicle and the center line when the running route is actually traveled so that the intermediate point is learned so that the traveling route approaches the center line Technology.

An embodiment of the present invention provides a route searching apparatus and method for an autonomous vehicle capable of searching for a route from a departure point to a destination of an autonomous vehicle using center line data at a lane level difference.

It should be understood, however, that the technical scope of the present invention is not limited to the above-described technical problems, and other technical problems may exist.

According to a first aspect of the present invention, there is provided a route search device for an autonomous vehicle including a communication module, a memory storing a program for searching for a route, and a processor for executing a program stored in the memory. . At this time, as the program is executed, the processor sets the source link and the destination link from the previously generated precise map data, assigns the path cost corresponding to the lane length to the source link, Extracting a lane link having a minimum path cost from the first list and a neighboring lane link, adding the extracted lane link to the first list, and transmitting the lane link having the minimum path cost to the first From the list to the second list. If the lane link having the minimum path cost in the first list is the destination link, the connection information of the destination link is traced back to set the final path.

According to a second aspect of the present invention, there is provided a route search method in a route search device for an autonomous vehicle, the method comprising: searching a plurality of departure place links, which are all lane links corresponding to a starting point, from pre- Searching for a plurality of destination links that are all lane links corresponding to a destination point from the accurate map data; Assigning a path cost to each of the plurality of origination links and adding the path cost to the first list; Extracting a lane link neighboring a lane link having a minimum path cost from the first list; Allocating a route cost to the extracted lane link and adding the route cost to the first list; Moving a lane link having a minimum path cost to a second list, and if the lane link having a minimum path cost among the lane links included in the first list is the destination link, And setting up a final path. At this time, the path cost is calculated based on the lane length corresponding to the lane link.

According to any of the above-mentioned objects of the present invention, it is possible to search for a route for autonomous travel using less data than in the prior art.

FIG. 1A is a diagram for explaining a global path search method using hierarchical structure data.
FIG. 1B is a view for explaining a global route searching method using a virtual connection link / node between a center line of a lane.
2 is a schematic diagram of an autonomous travel system according to an embodiment of the present invention.
3 is a block diagram of a route search apparatus according to an embodiment of the present invention.
4 is a diagram showing a lane centerline data model.
5A to 5C are diagrams for explaining a method of setting a source link and a destination link.
6A to 6H are views for explaining a route search process according to an embodiment of the present invention.
7A and 7B are diagrams for explaining a method of retrieving static data using a geometric operation.
8 is a diagram for explaining a method of retrieving static data using relation information between objects.
9 is a diagram showing autonomous running map data.
10 is a flowchart of a path search method according to an embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings, which will be readily apparent to those skilled in the art. The present invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. In order to clearly explain the present invention in the drawings, parts not related to the description are omitted.

Whenever a component is referred to as "including" an element throughout the specification, it is to be understood that the element may include other elements, not the exclusion of any other element, unless the context clearly dictates otherwise.

The present invention relates to a route search device (100) and method for an autonomous vehicle.

Hereinafter, a route search apparatus 100 according to an embodiment of the present invention will be described with reference to FIGS. 1A to 9. FIG.

The global route search aims at extracting a way point list for detecting the center line of the lane level corresponding to the road for driving to the destination and following the vehicle. At this time, the way point includes information such as position (x, y), heading, vehicle speed, and the like.

In other words, unlike the conventional navigation system, in which a destination is set by POI (Point of Interest) search and a corresponding route is searched, the present invention aims at extracting a center line by car line included in the route.

A technique applied to such autonomous travel route search will be described with reference to Figs. 1A and 1B.

FIG. 1A is a diagram for explaining a global path search method using hierarchical structure data.

(A) searching for a path based on Dijkstra or A * algorithm like the method applied to existing navigation, (b) searching for a route based on a Dijkstra or A * algorithm, using 2D road network data (node / link) , And the retrieved result path (link list, (c)).

If the link is regarded as a parent, the center line data included in the link is a child, and the centerline data by the lane is searched using the attribute information (relationship by id) between the parent and the child (d).

In the case of the method using the hierarchical structure data, precise map data of the center line level is necessarily required for autonomous driving, and additional 2D road network data is necessarily required.

FIG. 1B is a view for explaining a global route searching method using a virtual connection link / node between a center line of a lane.

A global route search method using a virtual link between a center line and a node is a method of searching for a corresponding route by adding Dijkstra or A * algorithm by adding a virtual connection link P1 and a node P2 between the center lines of the lane.

The Dijkstra or A * algorithm applied to the existing navigation has a problem that the route can not be found without the link information between the links. Therefore, the route is searched by virtually creating the connectivity between the center lines.

In the case of this route search method, unlike FIG. 1A, there is an advantage that a global route (lane center line) for autonomous travel can be found without separate 2D network data (node / link) There is a disadvantage that the size of the data increases due to the necessity of the node data.

In the case of the path search technology for autonomous navigation, additional 2D road network data is required, or the size of data increases due to virtual link / node data.

On the other hand, according to an embodiment of the present invention, a global route search for autonomous driving in an autonomous vehicle is performed using the center line data of the lane, and all the lane center line data included in the result path is extracted, You can navigate the path.

2 is a schematic diagram of an autonomous travel system 1 according to an embodiment of the present invention.

The autonomous driving system 1 according to an embodiment of the present invention includes a cloud server 100a and an autonomous vehicle 100b.

At this time, the path search device 100 for searching the path of the autonomous vehicle 100b may be executed on a server computer independent of the cloud server 100a, or may be executed on the same server as the cloud server 100a, It can be loaded into a computer as a server program and executed individually. In addition, the route search device 100 may be included in a system in the autonomous vehicle 100b.

Meanwhile, the cloud server 100a and the autonomous vehicle 100b constituting the autonomic driving system 1 shown in FIG. 2 can be connected through a network A. The network A is a connection structure capable of exchanging information between nodes such as terminals and servers. An example of such a network A is a 3rd Generation Partnership Project (3GPP) network, a Long Term Evolution network, a WIMAX network, an Internet, a LAN, a wireless LAN, a WAN, a PAN, a Bluetooth, (Bluetooth) network, a satellite broadcast network, an analog broadcast network, a DMB (Digital Multimedia Broadcasting) network, and the like.

3 is a block diagram of a route search apparatus 100 according to an embodiment of the present invention.

The path search apparatus 100 according to an embodiment of the present invention includes a communication module 110, a memory 120, and a processor 130. The path search apparatus 100 according to an embodiment of the present invention can be implemented on the system of the cloud server 100a or the separate server or autonomous vehicle 100b as described above, 100a. ≪ / RTI >

The communication module 110 transmits and receives data between the cloud server 100a and the autonomous vehicle 100b.

The communication module 110 may include both a wired communication module and a wireless communication module. The wired communication module may be implemented by a power line communication device, a telephone line communication device, a cable home (MoCA), an Ethernet, an IEEE1294, an integrated wired home network, and an RS-485 control device. In addition, the wireless communication module can be implemented with a wireless LAN (WLAN), Bluetooth, HDR WPAN, UWB, ZigBee, Impulse Radio, 60 GHz WPAN, Binary-CDMA, wireless USB technology and wireless HDMI technology.

In the memory 120, a program for path search is stored. At this time, the memory 120 is collectively referred to as a non-volatile storage device and a volatile storage device which keep the stored information even when power is not supplied.

For example, the memory 120 may be a compact flash (CF) card, a secure digital (SD) card, a memory stick, a solid-state drive (SSD) A magnetic computer storage device such as a NAND flash memory, a hard disk drive (HDD) and the like, and an optical disc drive such as a CD-ROM, a DVD-ROM, etc. .

The processor 130 executes the program stored in the memory 120. [ When the destination point is input by the driver's operation of the autonomous vehicle 100b to be autonomous, the processor 130 determines whether or not the autonomous vehicle 100a is autonomous for autonomous travel from the starting point (the current position or the point entered by the driver) From the autonomous vehicle 100b via the communication module.

The processor 130 that receives the request retrieves the pre-built precision map data and determines whether or not the autonomous vehicle 100b is in the autonomous driving map including the driving route and the guidance information for reaching the autonomous vehicle from the starting point to the destination point Data (routing data) to be transmitted to the autonomous vehicle 100b.

At this time, the pre-established precision map data is transmitted to the cloud server 100a in real time and can be constructed in the cloud server 100a when raw data for generating a precise map used in autonomous traveling by the collection vehicle is collected have. Here, the raw data may basically be image data for the front of the collection vehicle or feature data extracted from the image data. At this time, the feature data may be data including geometry information (dotted line, solid line, etc.) of the load mark extracted from the image data and position information of the landmark.

The autonomous vehicle 100b receiving the autonomous running map data can reach the target point by autonomous running according to the received routing data.

In this way, for the path search of the autonomous vehicle 100b, the processor 130 shown in FIG. 4 can use the lane centerline data model.

4 is a diagram showing a lane centerline data model.

The centerline data model applied to the present invention is similar to the road network data model applied to the general navigation route search method, but it has separate turn information (straight line, direct line, straight line, U-turn, right and left).

As shown in Figs. 4A to 4C, the lane center line is a lane-link information (lane-link) that linearly represents the lane of the road, a crossing point, a U-turn point, The linkage information is maintained by a lane-node indicating a point, and the processor 130 searches for the path using the lane-node information.

Specifically, the processor 130 establishes a source link and a destination link from the generated and stored precision map. At this time, the processor 130 may search for all the lane links corresponding to the start point and the destination point, respectively, and set the source link and the destination link.

5A to 5C are diagrams for explaining a method of setting a source link and a destination link.

The route search method using road network data (link / node) in existing navigation uses Dijkstra or A * algorithm. It finds one lane link corresponding to the starting point and repeats it until it reaches the destination link while searching for the lane link connected to it. Then, when the destination link is reached, the entire path is searched while searching for a link linked backward from the destination link.

On the other hand, when using the multi-lane center line, since there is no connectivity information between the center lines of the left turn / right turn, the route to the destination can not be searched by using the above conventional technique. That is, in order to travel in the actual autonomous vehicle 100b, it is necessary to change the lane for left turn / right turn or overtake. Therefore, the center line should be extracted together with the lane of the preceding lane.

Therefore, in one embodiment of the present invention, as shown in FIG. 5A, not the one link closest to the departure point is set as the departure link but all the lane links of the road are set as the departure link S.

The destination link (D) similarly sets all lane links corresponding to the destination point to the destination link (D).

In this case, when the left turn or right turn event occurs, the lane link may not reach the destination link D. That is, in FIG. 5A, the next lane link connected to the 'L1' lane link may not reach the lane link corresponding to the destination link D.

To this end, in an embodiment of the present invention, when the 'L1' lane link is an intersection link by turning right and searches for the next link, the above problem is solved by searching and extending all the neighboring links P4 of the corresponding lane link can do.

Specifically, the processor 130 searches for a first lane link, which is the lane link closest to the departure point, and a second lane link, which is the lane link closest to the destination point, respectively, and searches for the first and second lane links, The first neighbor lane link and the second neighbor lane link, respectively. Then, the searched first lane link and the first neighbor lane link can be set as the departure link S, and the second lane link and the second neighbor lane link can be set as the destination link D.

At this time, the processor 130 generates arbitrary virtual lines on the roads corresponding to the starting point and the destination point, respectively, based on the geometric calculation, and searches the first intersection and the second neighboring lane link can do.

Alternatively, the processor 130 may search the first and second neighbor lane links based on the connectivity information of the first and second lane links, respectively, based on the phase operation, as shown in Fig. 5B. Here, the connectivity information is a concept including the lane link information and the lane node information corresponding to each lane link as described above.

That is, the processor 130 can search for neighboring lane links of each lane link by the relation attribute between the lane link and the node. For example, as shown in FIG. 5B, 'L2-1' is linked to 'N2-1' as an end node in the case of the 'L1-1' lane link and 'L1-2' as a lane link located on the right. 130 can search neighboring lane links.

According to the above procedure, the source link and the destination link can be set as shown in FIG. 5C. That is, if the first lane link is' L1-1 'and the second lane link is' L100-1', the first neighbor lane link is' L1-2 ', the second neighbor lane link is' L100 The destination link S can be set to 'L1-1' and 'L1-2', and the destination link D can be set to 'L100-1' and 'L100-2'.

When the source link S and the destination link D are set, the processor 130 allocates the path cost corresponding to the lane length to the source link S and adds them to the first list, and adds Dijkstra or A Extracts a lane link neighboring the lane link having the minimum path cost of the first list based on the algorithm.

That is, the processor 130 selects the lane link having the smallest path cost among the lane links included in the first list sorted based on the path cost, and extracts all the lane links connected thereto. Then, each of the extracted lane links can be assigned a path cost of its own and a minimum path cost of the parent lane link, and the lane link having the minimum path cost can be allocated to the parent lane link of the extracted lane link.

After performing this process, the processor 130 moves the lane link with the minimum path cost assigned to the parent lane link to the second list.

Here, the first list may be a public list (Openlist), and the second list may be a closed list (closed list). That is, the public list is a list including lane links that have not yet been investigated, and the closed list is a list including the lane links whose investigation is completed. When the algorithm is initially started, And only the lane link set to the departure link S is included in the public list.

Again, the processor 130 selects the lane link having the minimum path cost among the lane links included in the first list, extracts all the lane links connected thereto, and repeats the above process in the same manner.

If the lane link having the minimum path cost of the first list is the destination link D, the processor 130 may set the final path by tracing back the connection information of the destination link D. [ That is, the processor 130 may set the final path by backtracking the parent lane link assigned to the destination link D.

This process will be described in detail with reference to Figs. 6A to 6H.

6A to 6H are views for explaining a route search process according to an embodiment of the present invention. 6A to 6H show the case where the lane is a two-lane line, but the present invention is not limited thereto.

First, the processor 130 sets the source link S as L1-1 and L1-2 as shown in (a) of FIG. 6A, sets L100-1 and L100 as the destination link D, -2 '. Then, 'L1-1' and 'L1-2' which are the source link S are added to the first list as shown in (b) of FIG. 6A. At this time, it is assumed that the path costs of the source link 'L1-1' and 'L1-2' are both '100'.

Next, when 'L1-1' is selected as the lane link having the minimum path cost as shown in (a) of FIG. 6B, the processor 130 extracts it from the first list and links it with the lane link 'L2-1' 'L2-2' is extracted.

As shown in (b) of FIG. 6B, the processor 130 adds '100', which is the path cost of the own path cost '40' and the path cost of the parent lane link 'L1-1' to the lane link 'L2-1' 140 'is allocated to the route cost, and the route cost' 45 'of the own route cost' 45 'and the route cost of the parent lane link' L1-1 'are added to the lane link' L2-2 ' do.

Then, the processor 130 connects the extracted lane links L2-1 and L2-2 with the parent lane link L1-1 and adds them to the first list, and the parent lane link L1 -1 'move to the second list.

Next, the processor 130 extracts a lane link 'L1-2' having a minimum path cost among the lane links included in the first list as shown in (a) of FIG. 6, and transmits the lane link 'L3-1' And 'L3-2' are extracted.

As shown in (b) of FIG. 6C, the route cost of 'L3-1' and the route cost of 'L1-2', which is the parent lane link, are added to the route cost of L3-1 and L3-2, respectively.

Then, the processor 130 connects the extracted lane links' L3-1 'and' L3-2 'to the parent lane link' L1-2 'and adds them to the first list, and the parent lane link' L1 -2 'move to the second list.

Next, the processor 130 extracts 'L3-2', which is the lane link having the minimum path cost '110', of the lane links included in the first list as shown in (a) of 6d, 1 '.

Then, the lane link 'L4-1' is added to the first list, the parent lane link 'L3-2' is linked with the 'L4-1' lane link, and the list is moved to the second list as shown in FIG. .

Next, the processor 130 determines whether the parent lane link 'L3-2' of the lane link 'L4-1' is a lane link corresponding to the right turn at the intersection as shown in (a) -1 'and neighboring lane links. At this time, the method of extracting the neighboring lane link can be applied in the same manner as the neighbor lane extracting method when the source link S and the destination link D are set.

Accordingly, the processor 130 adds the route cost '70' of the extracted lane link 'L4-2' and the route cost '110' of the parent lane link 'L4-1' to the extracted lane link 'L4-2' And then added to the first list.

If the above process is repeated to add 'L100-1' (or 'L100-2') set to the destination link D as shown in FIGS. 6A and 6B to the first list, L3-2, L4-2, L5-2, L100-1, L5-1, L5-1, L5-1, L5-1, ) Can be set.

On the other hand, the processor 130 searches all the neighboring lane links of each lane link included in the final path based on the geometric calculation or the operation based on the phase relation, and determines that each lane link included in the final path and the corresponding neighbor lane link The lane change information can be extracted. At this time, the lane change information is information necessary for changing the lane when the actual autonomous vehicle 100b turns left or right.

Thus, the source link S and the destination link D corresponding to the final route are connected to each other based on the lane change information and the lane change information of each route, as shown in Figs. 6 (a) and 6 .

On the other hand, in the autonomous vehicle 100b, static data located on the road besides the lane change information and the lane change information searched in the final path are added to enable self-running. Accordingly, an embodiment of the present invention may allow the processor 130 to search for static data included in the final path and generate the autonomous driving map data by reflecting the static data on the final path.

At this time, the static data may include at least one of a stop line, a stop line, a traffic light, a speed bump, and a crosswalk, and may include road mark data, traffic signs, road markings, and the like.

For example, stop line data is required for a stop position for recognizing a traffic light located at an intersection or a pedestrian crossing, and the traffic light data means position data of a traffic light for recognizing a traffic light through a sensor in the autonomous vehicle 100b .

In the case of pedestrian crossing data, it is necessary to detect and track obstacles such as other vehicles through a sensor. On the other hand, in the case of the pedestrian crossing data, The presence of pedestrians can be more accurately recognized by the coverage area.

On the other hand, the stop line data may be represented by a line component, the traffic light data may be represented by a point component, the oversistance data may be represented by a line or a polygon component, and the pedestrian data may be represented by a polygon component.

In order to detect such static data, the processor 130 may use a geometry operation or use an inter-object relationship.

First, the case of using a geometric calculation will be described with reference to Figs. 7A and 7B.

7A and 7B are diagrams for explaining a method of retrieving static data using a geometric operation.

The processor 130 can retrieve the static data based on the geometric object intersection operation between the line or face corresponding to the static data and the lane node if the static data and the lane link included in the final path are separated and a lane node is created have.

Alternatively, if the lane link included in the final path and the static data are separated and the lane node is not created, the processor 130 searches the static data based on the geometric object intersection operation between the line corresponding to the static data and the lane link .

For example, when the lane links 'L1-1' and 'L1-2' exist as shown in FIG. 7A and the lane node P6 is generated by separating the stop line P5 from the lane link, The control unit 130 may perform a geometric object intersection operation between the line P5 corresponding to the stop line and the lane node P6 to search for the stop line.

Alternatively, if the lane links 'L1-1' and 'L1-2' exist as shown in FIG. 7A and the lane node P6 is not generated by the lane link at the stop line P5, the processor 130 Can perform a geometric object intersection operation between a line P5 corresponding to a stop line and a line P7 corresponding to a lane link to search for a stop line.

As another example, in the case of a pedestrian crossing, when the pedestrian crosswalk and the lane link are separated as shown in FIG. 7B (a), and the lane node P9 is generated, the processor 130 determines whether the cross- The intersection can be searched by performing a geometric object intersection operation between the node P9 and the node P9.

Alternatively, when the lane node P9 is not generated by the pedestrian crossing and the lane link as shown in (b) of FIG. 7B, the processor 130 determines that the line P8 corresponding to the crosswalk and the line 0.0 > P10) < / RTI >

Next, a case of using relation information between objects will be described with reference to FIG.

8 is a diagram for explaining a method of retrieving static data using relation information between objects.

The path search apparatus 100 according to an embodiment of the present invention stores relationship information between objects including lane link and static data in advance. Accordingly, the processor 130 may generate the autonomous running map data by reflecting the relationship information between the objects of the static data corresponding to the final path.

The method of retrieving the static data using the relation information between the objects can store the relation information between the objects in the step of constructing the data in advance in order to improve the retrieval performance.

Thus, as shown in Figs. 8A and 8B, the stop line sl1 and the overspeed inhibition sp1 are related to the lane links L1-1 and L1-2, tl1 and tl2 and the pedestrian crossing cr1 are set to be related to the stop line sl1 and the autonomous travel map data can be generated by reflecting the relation information between the objects.

9 is a diagram showing autonomous running map data.

The autonomous driving map data finally generated according to the above process is transmitted from the source link S to the destination link S L1-1 and L1-2 as shown in FIGS. 9 (a) and 9 (b) D, L100-1, and L100-2 as well as static data such as lane change information, rotation information, overspeed suppression, and traffic lights.

When the autonomous driving vehicle 100b receives the autonomous driving map data, the autonomous driving vehicle 100b can determine and control the situation for the autonomous driving based on the data.

3 may be implemented in hardware such as software or an FPGA (Field Programmable Gate Array) or ASIC (Application Specific Integrated Circuit), and may perform predetermined roles can do.

However, 'components' are not meant to be limited to software or hardware, and each component may be configured to reside on an addressable storage medium and configured to play one or more processors.

Thus, by way of example, an element may comprise components such as software components, object-oriented software components, class components and task components, processes, functions, attributes, procedures, Routines, segments of program code, drivers, firmware, microcode, circuitry, data, databases, data structures, tables, arrays, and variables.

The components and functions provided within those components may be combined into a smaller number of components or further separated into additional components.

Hereinafter, a path search method in the path search apparatus 100 according to an embodiment of the present invention will be described with reference to FIG.

10 is a flowchart of a path search method according to an embodiment of the present invention.

In the path search method according to an exemplary embodiment of the present invention, first, a plurality of source links, which are all lane links corresponding to the starting point, are searched for from the preliminarily generated precise map (S110).

Then, a plurality of destination links, which are all lane links corresponding to the destination point, are searched from the precision map (S110).

In this case, the step of searching for the source link and the destination link may include selecting a first lane link and a second lane link, which are lanes closest to the starting point and the destination point, respectively, The first neighboring lane link and the second neighboring lane link are searched respectively and then the first lane link and the first neighbor lane link are determined to be the departure link and the second lane link and the second neighbor lane link to the destination link respectively Can be set.

The steps S110 and S120 for searching the source link and the destination link may be performed sequentially or two steps may be performed at the same time.

Next, the route cost is allocated to each of the plurality of source links and added to the first list (S130). Then, a lane link neighboring the lane link having the minimum path cost among the lane links included in the first list is extracted (S140).

Next, the path cost is allocated to the extracted lane link (S150), added to the first list (S160), and the lane link having the minimum path cost is moved to the second list (S170).

At this time, the path cost is calculated based on the lane length corresponding to the lane link. Then, the route cost of the own lane link and the route cost of the lane link having the minimum cost are allotted to the extracted lane link. And the least cost lane link is assigned to the parent lane link of the extracted lane link.

Next, it is determined whether the lane link having the lowest cost among the lane links included in the first list is the same as the destination link (S180). If the lane link has the lowest cost, the connection information of the destination link included in the first list To the final path (S190). That is, the parent lane link assigned to the destination link can be traced back to the final path.

On the other hand, the autonomous vehicle 100b needs to perform lane change during actual driving. Accordingly, the route search method according to an embodiment of the present invention includes searching all the neighboring lane links of each lane link included in the final route, and extracting lane change information between each lane link and a corresponding neighbor lane link . Thus, the source link and the destination link corresponding to the final path can be connected to each other based on the lane change information.

In addition, the route search method according to an embodiment of the present invention searches static data including at least one of a stop line, a traffic light, a speed limit bump, and a pedestrian crossing included in the final route in addition to the final route and lane change information, So that autonomous running map data can be generated.

The autonomous driving vehicle 100b receives the generated autonomous driving map data and can determine and control the situation necessary for autonomous driving.

Meanwhile, in the above description, steps S110 to S190 may be further divided into additional steps or combined into fewer steps, according to an embodiment of the present invention. Also, some of the steps may be omitted as necessary, and the order between the steps may be changed. In addition, even if other contents are omitted, the contents already described in Figs. 1A to 9 can also be applied to the path search method of Fig.

According to any one of the embodiments of the present invention as described above, the global path for autonomous travel can be searched using less data than in the prior art.

Meanwhile, the path search method in the path search apparatus 100 according to an embodiment of the present invention may be embodied also in the form of a computer program stored in a medium executed by a computer or a recording medium including instructions executable by the computer . Computer readable media can be any available media that can be accessed by a computer and includes both volatile and nonvolatile media, removable and non-removable media. In addition, the computer-readable medium may include both computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Communication media typically includes any information delivery media, including computer readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave, or other transport mechanism.

While the methods and systems of the present invention have been described in connection with specific embodiments, some or all of those elements or operations may be implemented using a computer system having a general purpose hardware architecture.

It will be understood by those skilled in the art that the foregoing description of the present invention is for illustrative purposes only and that those of ordinary skill in the art can readily understand that various changes and modifications may be made without departing from the spirit or essential characteristics of the present invention. will be. It is therefore to be understood that the above-described embodiments are illustrative in all aspects and not restrictive. For example, each component described as a single entity may be distributed and implemented, and components described as being distributed may also be implemented in a combined form.

The scope of the present invention is defined by the appended claims rather than the detailed description and all changes or modifications derived from the meaning and scope of the claims and their equivalents are to be construed as being included within the scope of the present invention do.

100: Path search device
110: communication module
120: Memory
130: Processor

Claims (19)

A route search device for an autonomous vehicle, comprising:
Communication module,
A memory for storing a program for searching for a path and
And a processor for executing a program stored in the memory,
The processor sets the departure link and the destination link from the preliminarily generated and stored precise map according to the execution of the program and adds the path cost corresponding to the lane length to the departure link and adds the route cost to the first list, Extracting a lane link neighboring a lane link having a minimum path cost from the first list,
Adds the extracted lane link to the first list, moves the lane link with the minimum path cost from the first list to the second list,
And when the lane link having the minimum path cost among the first lists is the destination link, tracing back the connection information of the destination link to set the final path. The method according to claim 1,
Wherein the processor searches each of the lane links corresponding to the starting point and the destination point, respectively, and sets the starting link and the destination link. The method according to claim 1,
Wherein the first list is an open list and the second list is a closed list. The method according to claim 1,
The processor searches for a first lane link and a second lane link that are closest lane links to the departure point and the destination point, respectively, and the first lane link and the first neighbor lane link, which is all the lane links neighboring the first and second lane links, Each of the first neighboring lane links and the second neighboring lane links, respectively, to set the searched first lane link and the first neighbor lane link as a departure link, and to set the second lane link and the second neighbor lane link as a destination link, Search device. 5. The method of claim 4,
Wherein the processor is configured to generate an arbitrary virtual line on the road corresponding to the departure point and the destination point respectively and to search the first and second neighboring lane links for a link intersecting the virtual line, . 5. The method of claim 4,
The processor searches for the first and second neighbor lane links based on connectivity information of each of the first and second lane links,
Wherein the connectivity information includes lane link information and lane node information corresponding to each lane link. The method according to claim 1,
The processor adds and allocates to each of the extracted lane links a path cost corresponding to the extracted lane link and a path cost of a lane link having the minimum path cost and assigns the lane link having the minimum path cost to the extraction To the parent lane link of the second lane link. 8. The method of claim 7,
Wherein the processor traces the parent lane link assigned to the destination link to set the final path. 8. The method of claim 7,
When the parent lane link allocated to the extracted lane link is a lane link corresponding to a left turn or a right turn at an intersection, extracts a neighbor lane link that is an adjacent lane link from the extracted lane link, And adds the path cost of the link and the path cost of the parent lane link, and adds the neighbor lane link to the first list. The method according to claim 1,
The processor retrieves all neighbor lane links of each lane link included in the final path, extracts lane change information between each lane link included in the final path and the corresponding neighbor lane link,
Wherein the departure link and the destination link corresponding to the final route are connected to each other based on the lane change information. The method according to claim 1,
The processor retrieves static data included in the final path and generates autonomous running map data by reflecting the static data to the final path,
Wherein the static data comprises at least one of a stop line, a traffic light, an overbraking bike, and a crosswalk. 12. The method of claim 11,
Wherein when the static data and the lane link included in the final path are separated and a lane node is generated, the processor generates the static data based on a geometric object intersection operation between a line or a face corresponding to the static data and the lane node Search,
And searching the static data based on a geometric object intersection operation between the line corresponding to the static data and the lane link when the static data and the lane link included in the final path are separated and the lane node is not created, Search device. 12. The method of claim 11,
The link information between the lane link and the object including the static data is preset and stored,
Wherein the processor generates the autonomous running map data by reflecting relationship information between objects of the static data corresponding to the final path. A route search method in a route search device for an autonomous vehicle,
Searching for a plurality of origin links that are all lane links corresponding to the starting point from the generated precise map;
Searching a plurality of destination links that are all lane links corresponding to a destination point from the precision map;
Assigning a path cost to each of the plurality of origination links and adding the path cost to the first list;
Extracting a lane link neighboring a lane link having a minimum path cost from the first list;
Allocating a route cost to the extracted lane link and adding the route cost to the first list;
Moving the lane link with the minimum path cost to a second list; and
If the lane link having the minimum path cost among the lane links included in the first list is the destination link, setting the final path by tracing back the connection information of the destination link included in the first list,
Wherein the route cost is calculated based on a lane length corresponding to a lane link. 15. The method of claim 14,
Wherein the step of searching for the source link and the destination link comprises:
Searching for a first lane link and a second lane link which are lane links closest to the start point and the destination point, respectively;
Searching a first neighbor lane link and a second neighbor lane link that are all lane links neighboring the first and second lane links,
Setting the searched first lane link and the first neighbor lane link as a departure link and setting the second lane link and the second neighbor lane link as a destination link. 15. The method of claim 14,
Adding the extracted lane link to the first list and adding a lane link with the minimum path cost to the second list,
Summing and allocating to each of the extracted lane links a path cost of a lane link having its own path cost and the minimum path cost;
And linking the lane link having the minimum path cost to the parent lane link of the extracted lane link. 17. The method of claim 16,
Wherein the step of tracing back the connection information of the destination link and setting a final path comprises:
And traversing the parent lane link assigned to the destination link to extract the final path. 15. The method of claim 14,
Searching all neighbor lane links of each lane link included in the final path and
Further comprising extracting lane change information between each lane link and a corresponding neighbor lane link,
Wherein the departure link and the destination link corresponding to the final route are connected to each other based on the lane change information. 15. The method of claim 14,
Retrieving static data contained in the final path; and
Further comprising generating autonomous driving map data reflecting the static data in the final path,
Wherein the static data includes at least one of a stop line, a traffic light, an overspeed barrier, and a crosswalk.

Images