TWI583925B - Path planning method and device - Google Patents

Description

Path planning method and device

Embodiments of the present invention relate to the field of map technologies, and in particular, to a path planning method and apparatus.

At present, navigation products that integrate positioning, navigation, entertainment and other functions have gradually become the basic equipment in the car. As a very important function in navigation, electronic map path planning can select the best walking path from the various destinations to the destination, so that the owner can quickly and conveniently reach the destination.

The path planning route is organized by individual links, and one path can contain multiple Link data. Link is the smallest unit in the graph data and is used to represent a road segment in the actual road network. The LinkID field is the only sign of Link data in the road network. At present, the main process of the path planning algorithm is to extend the depth or breadth from the link of the starting point, and finally traverse to the end of the Link to find one or more preferred walking paths.

In the prior art, when performing electronic map path planning, the traversing search space is usually reduced by the heuristic function reduction branching technique. However, on the one hand, the current branch reduction strategy is based on graph data, and the search space is still very large; on the other hand, the update cycle of graph data is too long, and the accuracy of graph data itself is difficult to guarantee. When a section of road is being repaired or has been abandoned, the map data is not updated, which may lead to the path planning result will be cited by the user. Leading to a path that is not smooth, resulting in a poor user experience.

The embodiment of the invention provides a path planning method and device, which optimizes the existing path planning technology, improves the planning speed and the accuracy of the planning result.

In one aspect, an embodiment of the present invention provides a path planning method, including: acquiring a path planning request including a starting point and an ending point; and obtaining an empirical weight set of the link between the starting point and the ending point according to the path planning request, wherein the experience The weight set is determined according to the historical path of the user; according to the empirical weight set of the road segment, the heuristic search algorithm is used to perform path planning on the path planning request.

On the other hand, an embodiment of the present invention further provides a path planning apparatus, where the apparatus includes: a planning request acquiring unit, configured to acquire a path planning request including a start point and an end point; and an empirical weight obtaining unit, configured to perform a request according to the path Obtaining an empirical weight set of the road segment between the starting point and the ending point, wherein the empirical weight set is determined according to a historical path of the user; the path planning unit is configured to use the heuristic search algorithm to plan the path according to the empirical weight set of the road segment Request for path planning.

The technical solution provided by the embodiment of the present invention can combine a large number of reliable user historical walking behaviors and adopt a heuristic search algorithm for path planning, so that the search space of the path planning traversal algorithm can be effectively reduced, and the path planning efficiency is improved. To a certain extent, it can also overcome the problem of low planning accuracy caused by slow update of data or partial data errors.

400‧‧‧Historical Path Category Division

405‧‧‧Statistical Learning Unit

410‧‧‧ Planning Request Acquisition Unit

420‧‧‧Experience weight acquisition unit

430‧‧‧Path Planning Unit

1 is a schematic flowchart of a path planning method according to Embodiment 1 of the present invention; FIG. 2 is a flowchart of a method for determining an offline weight of an empirical weight set for each link between a start point and an end point according to Embodiment 2 of the present invention; FIG. 3 is a schematic flowchart diagram of a path planning method according to Embodiment 3 of the present invention; FIG. 4 is a schematic structural diagram of a path planning apparatus according to Embodiment 4 of the present invention.

The present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It is understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention. It should also be noted that, for ease of description, only some, but not all, of the structures related to the present invention are shown in the drawings.

Before discussing the exemplary embodiments in more detail, it should be noted that some exemplary embodiments are described as a process or method depicted as a flowchart. Although the flowcharts describe various operations (or steps) as a sequential process, many of the operations can be implemented in parallel, concurrently or concurrently. In addition, the order of operations can be rearranged. The process can be terminated when its operation is completed, but can also have additional steps not included in the figures. This processing may correspond to methods, functions, procedures, subroutines, subroutines, and the like.

Embodiment 1

FIG. 1 is a schematic flowchart diagram of a path planning method according to Embodiment 1 of the present invention. This embodiment can be applied to the case of electronic map path planning in a navigation terminal. The method can be performed by a path planning device, which can be implemented by software, integrated to provide navigation products Navigation service in the server. Referring to FIG. 1 , the path planning method provided in this embodiment specifically includes the following operations: operation 110: acquiring a path planning request including a start point and an end point.

Specifically, the navigation terminal may receive a path planning request triggered by the user by means of human-computer interaction, where the request includes a start point and an end point of the path that the user wants to walk. For example, a human-machine interaction interface corresponding to the path plan may be provided, where the interface includes a first input box, a second input box, and a confirmation button; if a trigger operation of the confirmation button is received by the user, a path planning request is generated and sent To the server. The request includes a starting point for the input information of the user in the first input box, and the ending point is the input information of the user in the second input box.

Operation 120: Acquire an empirical weight set of the link between the start point and the end point according to the path planning request, where the empirical weight set is determined according to the historical path of the user.

The so-called historical path refers to the path that the user has traveled. In this embodiment, before performing the operation 120, the following operations are required to be performed in advance: based on the set data mining algorithm: performing statistical learning on a plurality of historical paths having the same starting point and ending point to obtain the plurality of history The frequency of occurrence of the road segment in the path, and/or the frequency of occurrence of the associated road segment group including the road segment; determining the empirical weight set of the road segment according to the frequency of occurrence.

As a specific implementation, the empirical weight set may be only one empirical weight. For example, the empirical weight may be the frequency of occurrence of the road segment in the plurality of historical paths. Of course, the empirical weight may also be a value obtained according to the frequency of occurrence of the road segment in the plurality of historical paths and the frequency of occurrence of the associated road segment group including the road segment. This value is used to characterize the probability that the optimal path of the start and end points will pass through the road segment. The higher the frequency, the larger the value.

As another specific implementation manner, the empirical weight set may be a plurality of empirical rights reorganization The collection of the combination. The set may include: the frequency of occurrence of the associated road segment group including the road segment (considered as the first empirical weight); and/or the frequency of occurrence of the condition of the road segment in other segments of the associated road segment group (serving as the second experience) Weights). For example, the appearance frequency of the associated road segment group AB is 2/5, and the frequency of occurrence of the road segment B is 3/4, and the frequency of occurrence of the road segment A in the other road segment B in the associated road segment group AB is: 2/5÷3/4 =8/15.

Operation 130: Perform a path planning on the path planning request by using a heuristic search algorithm according to the empirical weight set of the road segment.

At present, using a heuristic search algorithm, the path planning process for the path planning request includes: starting all the segments connected to the starting point in all the segments between the starting point and the ending point that the electronic map can provide, The importance assessment of these sections is carried out, and the first set of planned sections with better evaluation results are selected; then, the extended sections connected with the first set of planned sections are continuously searched, and the importance sections of these extended sections are evaluated, and from which Select the second set of planning sections with better evaluation results; and then continue searching according to the strategy until the end point. Finally, the optimal path from the starting point to the ending point can be determined according to the obtained group planning sections. Heuristic search technology can omit a large number of unnecessary search paths and improve search efficiency. In heuristic search, it is important to evaluate the importance of each road segment. Different evaluation strategies can be used to achieve different effects.

In the prior art, it is usually based on a heuristic function to evaluate the importance of each road segment, and each road segment has a heuristic function value. For the nth road segment, the heuristic function value may be the estimated dissipation value of the lowest dissipative path (ie, the optimal path) from the nth road segment to the end point; or other inversely proportional to the estimated dissipation value. value. For the former, the value of the heuristic function is more Small, the more likely the optimal path passes through the nth road segment, the higher the importance of the road segment; for the latter, the larger the heuristic function value, the more likely the optimal path passes through the nth road segment, the road segment The higher the importance.

At present, the value of the heuristic function is often calculated only based on the map data provided by the electronic map. For example, based on the description of the length of the search section, the road segment (for example, an expressway, or an ordinary road), the search section is obtained. The value of the heuristic function. Therefore, using the existing path planning technique, although the search for partial invalid paths is subtracted based on the evaluation results, the evaluation results are not very reliable due to the limitations of the evaluation algorithm, so the search space may still be large, and the search results may be Not very accurate.

As a specific implementation manner, the existing heuristic function evaluation method can be combined with the user's road experience to perform path planning. Exemplarily, the heuristic function designed by the prior art is modified by using the empirical weight set of the road segment. Specifically, the operation 130 includes: modifying the heuristic function value F _{new of the} road segment according to the following formula: F _new = F + △

Where F is the original heuristic function value of the road segment; △ is the correction value determined based on the empirical weight set of the road segment. If F is the estimated dissipation value, the correction value should be negatively correlated with the empirical weight in the empirical weight concentration; conversely, if F is directly used to describe the magnitude of the road segment importance, then the correction value should be related to the experience weighted experience. The weights are positively related.

Preferably, if the obtained empirical weight set is multiple weights, the obtained planned road segments in the path planning may be used to filter the obtained empirical weight set, and the occurrence of the specific associated road segment group is extracted. The frequency, and/or the frequency at which the condition of the road segment appears in other sections of the particular associated road segment group; then, the correction value is determined only based on the extraction result. its The specific associated road segment group is: a road segment group composed of the currently searched road segment and the determined planned road segment. For example, if the determined planned road segments are A and F, and the road segment K is being searched for as the extended road segment of the road segment F, then when the heuristic function value of the road segment K is corrected, the corresponding specific associated road segment group is FK, AK, and AFK.

Since the experience weight of the road segment is obtained based on the experience of a large number of users, the reliability is strong. Therefore, as another implementation manner of the embodiment, the importance degree evaluation result of the road segment can be generated only according to the empirical weight set of the road segment. For example, the result is the above-described correction value Δ.

The technical solution provided by the embodiment can combine a large number of reliable user historical walking behaviors and adopt a heuristic search algorithm for path planning, so that the search space of the path planning traversal algorithm can be effectively reduced, and the path planning efficiency is improved, and To a certain extent, it can also overcome the problem of low planning accuracy caused by slow update of data or some data errors.

Embodiment 2

This embodiment introduces the offline determination method of the empirical weight set of each road segment between the starting point and the end point on the basis of the above-mentioned first embodiment. Referring to FIG. 2, the determining method specifically includes the following operations: Operation 210: Obtain a plurality of historical paths that multiple users have traveled in the most recent preset time period to form a path set.

Since the embodiment of the present invention performs path planning according to the user's road experience, the user's historical path should also be the path that the user has traveled in the most recent period of time. If the historical path is too long from the current time, it will reduce the accuracy of learning. The preset time period can be the most recent month or half year, and can be set by the developer.

The historical path may be triggered by the navigation user after the navigation user completes a trip, or may be automatically monitored by the server through the path monitoring component set in the navigation terminal.

Operation 220: classify the historical path in the path set according to the same starting point and end point.

Each history path can be represented using a Link set L = {L1, L2, L3 ... Ln}, where L1, L2, L3 ... Ln represent different links in the line, respectively. All the historical paths obtained in the past week (time controllable) are taken as the path set Tw, and Tw is classified according to the criteria of the starting point, and Tw can be divided into path subsets composed of different starting points {Ts1e1, Ts2e2, Ts3e3 ...Tsnen}, where the path subset Tsnen represents a set of multiple history paths in the path set Tw whose starting point is sn and whose end point is en.

Operation 230: Perform statistical learning on the plurality of historical paths having the same starting point and the ending point based on the set data mining algorithm, and obtain an empirical weight set of the road segments in the learned plurality of historical paths.

The specific learning process may be: based on the set data mining algorithm: performing statistical learning on multiple historical paths having the same starting point and ending point to obtain the frequency of occurrence of the segments in the plurality of historical paths, and/or including The frequency of occurrence of the associated link group of the road segment; determining the empirical weight set of the road segment according to the frequency of occurrence.

The frequency of occurrence of the so-called road segment refers to the probability that the road segment appears in the plurality of historical paths; the frequency of occurrence of the associated road segment group refers to the probability that all the road segments in the associated road segment group appear simultaneously in the same historical path.

For example, there are five historical paths between a starting point and an ending point: A-B-C-D, A-B-C-G, B-C-E-G, C-E-F-G, D-E-F-G. The five historical paths share seven sections of sections A, B, C, D, E, F, and G. For the road segment B, it appears in three historical paths, so the frequency of occurrence is 3/7; the associated road segment group AB including the road segment B appears in two historical paths, so the frequency of occurrence is 2/7: The associated link group BC containing the link B appears in three historical paths, so the frequency of occurrence is 3/7.

As a preferred embodiment of the present embodiment, the set data mining algorithm is a frequent item set algorithm (that is, an apriori algorithm). Specifically, based on the algorithm, statistical learning is performed on multiple historical paths having the same starting point and ending point, and the empirical weight set of each road segment in the learned plurality of historical paths is obtained, including: 1. The same starting point and ending point are to be obtained. Multiple historical paths form a collection, and each element in the collection is a historical path.

2. Mining the frequent K item sets in the set based on the preset minimum support threshold.

Specifically, the frequent 1 item set includes: each of the road segments whose frequency appears to be greater than the minimum support degree critical value; for example, the frequent 1 item set includes: A, C, D, and E; the frequent 2 item set includes: the frequency of occurrence in the set is greater than The minimum support degree threshold is an associated link group consisting of two road segments; for example, the frequent 2 item set includes: AC, CD, and AE; the frequent 3 item set includes: three occurrences in the set are greater than the minimum support degree threshold by three The associated link group composed of the road segments; for example, the frequent 3 item sets include: ACE.

Wherein, the size of K can be determined by the minimum support threshold and the set. Each element in the frequent K item set is regarded as a frequent item, for example, A, C, D, E, AC, CD, AE, and ACE are all frequent items. The frequency of occurrence is also the degree of support.

3. Based on the preset minimum confidence threshold, the strong association rules of frequent K items are mined.

Each strong association rule obtained includes: a left road segment and a right road segment. The frequent items composed of the two road segments are strongly associated road segment groups. The left road segment can be one road segment or multiple road segments, while the right road segment is only one road segment. There is a strong correlation between the right road segment of each strong association rule and the left road segment. The meaning is that if the user walks the left road segment, the right road segment is largely taken.

The support degree of the strong association rule is greater than the minimum support degree threshold, and the confidence is greater than the minimum confidence threshold. The support degree of the strong association rule is: the strong associated link group composed of the two road segments in the rule is composed of the plurality of historical paths. The frequency of appearance in the set; the confidence level of the strong association rule is: the frequency of occurrence of the condition in the set of the plurality of historical paths in the left road segment on the left road segment.

For example, if a frequent item is the associated road segment group AE, the frequency of occurrence of the associated road segment group AE is greater than the minimum support degree threshold value, and the frequency of the condition that the road segment E appears under the road segment A is greater than the minimum confidence threshold value, then A->E is A strong association rule. Among them, the road segment A is the left road segment, and the road segment E is the right road segment.

For example, if a frequent item is the associated road segment group DJK, the frequency of occurrence of the associated road segment group DJK is greater than the minimum support degree threshold value, and the condition occurrence frequency of the road segment K in the road segment DJ is greater than the minimum confidence threshold value, then DJ->K Is a strong association rule. Among them, the road section DJ is the left road section, and the road section K is the right road section.

4. Determine the empirical weight set of the corresponding road segments in the learned plurality of historical paths according to the support degree and confidence of the strong association rule.

Specifically, if the road segment is the right road segment in the strong association rule, the empirical weight set of the road segment includes: the support degree and the confidence level of the strong association rule.

In this embodiment, by analyzing the user history path, a frequent set of frequent Link items of the same starting point is mined, which is used to further reduce the search space of the graph traversal. At the same time, because of the user's recent real user experience, the correctness of the data can be guaranteed, which can make up for the problem that the image data update time is long and the data is inaccurate.

Embodiment 3

FIG. 3 is a schematic flowchart diagram of a path planning method according to Embodiment 3 of the present invention. This embodiment provides a preferred embodiment based on all of the above embodiments. Referring to FIG. 3, the method specifically includes the following operations: Operation 310: Obtain a plurality of historical paths that multiple users have traveled in the most recent preset time period to form a path set.

Operation 320: classify the historical paths in the path set according to the same starting point and end point.

Operation 330: Perform a strong association rule mining learning on the set of multiple historical paths having the same starting point and the ending point based on the frequent item set algorithm.

In this embodiment, in the mining learning process, only the frequent 2 item sets may be first mined; then the strong association rules are mined from the frequent 2 items. Thus, the left and right segments in the rule are one segment.

Operation 340: Determine, according to the support degree and the confidence level of the strong association rule, the empirical weight set of the corresponding road segment in the learned plurality of historical paths, and store the same.

For example, excavating a frequent set of 2 items: AB, BE, BD, CE, DK Associated link groups, and excavate the following three strong association rules: A->B, B->E, C->E. Then, the learned plurality of historical paths may be determined: the empirical weight set of the road segment B includes the following two empirical weights: the frequency of occurrence of the associated road segment group AB in the plurality of historical paths; the condition that the road segment B appears under the road segment A Frequency; the empirical weight set of the road segment E includes the following four empirical weights: the frequency of occurrence of the associated road segment group BE in the plurality of historical paths; the frequency at which the road segment E appears under the road segment B; the associated road segment group CE is in the multiple The frequency of occurrence in the historical path; the frequency at which the condition of the road segment E appears in the road segment C occurs.

For a road segment such as A, C, D, or K, since the right road segment of any of the above-mentioned strong association rules does not include the road segment, the empirical weight set of the road segment in the learned plurality of historical paths is empty.

The above operation 310-operation 340 can be performed in advance offline.

Operation 350: Acquire a path planning request including a target starting point and a target ending point.

The operation 360 is configured to acquire the stored empirical weights of the stored segments in the plurality of target historical paths corresponding to the target starting point and the target ending point according to the path planning request; operation 370, using a heuristic search algorithm according to the empirical weight set of the obtained road segments. Path planning for the path planning request.

Specifically, if the currently searched road segment is an extended road segment of the planned road segment that has been determined in the path planning, and the road segment belongs to one of the plurality of target historical paths, the inspiration of the road segment is corrected according to the following formula. Function value F _new : F _new = F + α ×( β × S + γ × C )

Where F is the original heuristic function value of the road segment; α is the first adjustment factor, β is the second adjustment factor, and γ is the third adjustment factor; S is the road segment and the planned road segment in the plurality of target historical paths. The frequency of occurrence of the target associated road segment group, and C is the frequency of occurrence of the condition of the road segment in the planned target road segment in the plurality of target historical paths.

In this embodiment, the difference between the heuristic function values between the road segments can be opened by the empirical weight, and the extended path with poor evaluation of some importance degrees can be directly removed, and the search range can be directly reduced. At the same time, the empirical weights are introduced to plan the correct road segments. Sex is guaranteed and can effectively alleviate the inconsistency of graph data.

Embodiment 4

FIG. 4 is a schematic structural diagram of a path planning apparatus according to Embodiment 4 of the present invention. Referring to FIG. 4, the specific structure of the device is as follows: a planning request obtaining unit 410 is configured to acquire a path planning request including a start point and an end point; and an experience weight obtaining unit 420 is configured to obtain the start point and the end point according to the path planning request. The empirical weight set of the intermediate road segment, wherein the empirical weight set is determined according to the historical path of the user; the path planning unit 430 is configured to perform path planning on the path planning request by using a heuristic search algorithm according to the empirical weight set of the road segment.

Exemplarily, the apparatus provided in this embodiment further includes a statistical learning unit 405, configured to: perform statistical learning on the plurality of historical paths having the same starting point and the ending point to obtain the plurality of historical records based on the set data mining algorithm The frequency of occurrence of the road segment in the path, And/or, the frequency of occurrence of the associated road segment group including the road segment; determining the empirical weight set of the road segment according to the frequency of occurrence.

Exemplarily, the data mining algorithm is a frequent item set algorithm; if the road segment is a right road segment in the strong association rule obtained based on the frequent item set algorithm, the empirical weight set of the road segment includes: the strong association rule Support and confidence.

Exemplarily, the device provided in this embodiment further includes a historical path class dividing unit 400, configured to: acquire a plurality of historical paths that multiple users have traveled in the most recent preset time period, and form a path set; according to the same starting point and end point, Classify the historical paths in the path set.

Exemplarily, the path planning unit 430 is specifically configured to: modify the heuristic function value F _{new of} the road segment according to the following formula: F _new = F + △

Wherein F is the original heuristic function value of the road segment; the Δ is a correction value determined based on the empirical weight set of the road segment.

Illustratively, the road segment is an extended road segment of the planned road segment that has been determined in the path planning; the Δ is calculated according to the following formula: Δ = α × ( β × S + γ × C )

Wherein, the α is a first adjustment factor, the β is a second adjustment factor, and the γ is a third adjustment factor; the S is an appearance frequency of the target associated road segment group composed of the road segment and the planned road segment in the plurality of historical paths The C is the frequency of occurrence of the condition that the road section appears in the planned road section in the plurality of historical paths.

The above products can perform the method provided by any embodiment of the present invention, and have the corresponding functional modules and beneficial effects of the execution method.

Note that the above are only the preferred embodiments of the present invention and the technical principles applied thereto. Those skilled in the art will appreciate that the present invention is not limited to the specific embodiments described herein, and that various modifications, changes and substitutions may be made without departing from the scope of the invention. Therefore, the present invention has been described in detail by the above embodiments, but the present invention is not limited to the above embodiments, and other equivalent embodiments may be included without departing from the inventive concept. The scope is determined by the scope of the attached patent application.

Claims (10)

A path planning method, comprising: acquiring a path planning request including a starting point and an ending point; setting a data mining algorithm, wherein the data mining algorithm is a frequent item set algorithm, and if the road segment is based on the frequent item set calculation The right weight segment of the strong association rule obtained by the method, the empirical weight set of the road segment includes: the support degree and the confidence degree of the strong association rule; and the empirical weight set of the road segment between the start point and the end point is obtained according to the path planning request, wherein The empirical weight set is determined according to the historical path of the user; according to the empirical weight set of the road segment, the heuristic search algorithm is used to perform path planning on the path planning request. The method of claim 1, wherein before acquiring the empirical weight set of the link between the start point and the end point according to the path planning request, the method further includes: based on the set data mining algorithm, having Performing statistical learning on the plurality of historical paths of the same starting point and the ending point to obtain the frequency of occurrence of the road segment in the plurality of historical paths, and/or the frequency of occurrence of the associated road segment group including the road segment; determining the frequency according to the frequency of occurrence The empirical weight of the road segment. The method of claim 2, wherein before the statistical learning is performed on the plurality of historical paths having the same starting point and the ending point, the method further includes: acquiring, by the plurality of users in the most recent preset time period, A plurality of historical paths constitute a path set; according to the same starting point and end point, the historical path of the path set is classified. The method of claim 2, wherein the method according to the empirical weight set of the road segment uses a heuristic search algorithm to perform path planning on the path planning request, including: The following function is modified to modify the heuristic function value F _new : F _new = F + Δ of the road segment, where F is the original heuristic function value of the road segment; the Δ is a correction value determined based on the empirical weight set of the road segment. The method of claim 4, wherein the road segment is an extended road segment of the planned road segment that has been determined in the path planning; the Δ is calculated according to the following formula: Δ = α × ( β × S + γ × C ) wherein the α is a first adjustment factor, the β is a second adjustment factor, and the γ is a third adjustment factor; the S is a target associated segment of the road segment and the planned road segment in the plurality of historical paths The frequency of occurrence of the group, where C is the frequency of occurrence of the condition in which the section of the plurality of historical paths appears under the planned section. A path planning device, comprising: a planning request obtaining unit, configured to acquire a path planning request including a starting point and an ending point; and an empirical weight obtaining unit, configured to acquire a path segment between the starting point and the ending point according to the path planning request An empirical weight set, wherein the empirical weight set is determined according to a user historical path, and wherein the data mining algorithm is set, the data mining algorithm is a frequent item set algorithm, if the road segment is obtained based on the frequent item set algorithm The right link in the strong association rule, the empirical weight set of the road segment includes: the support degree and the confidence of the strong association rule; the path planning unit is configured to use the heuristic search algorithm according to the empirical weight set of the road segment. The path planning request performs path planning. The device of claim 6, further comprising: a statistical learning unit, configured to: perform statistical learning on the plurality of historical paths having the same starting point and the ending point based on the set data mining algorithm; Obtaining an appearance frequency of the road segment in the plurality of historical paths, and/or an appearance frequency of the associated road segment group including the road segment; determining an empirical weight set of the road segment according to the frequency of occurrence. The device of claim 7, further comprising: a historical path class dividing unit, configured to: acquire a plurality of historical paths that multiple users have traveled in the most recent preset time period, and form a path set; The same starting point and ending point are used to classify the historical path in the path set. The apparatus according to any one of claims 7 to 8, wherein the path planning unit is specifically configured to: modify the heuristic function value F _new : F _new = according to the following formula: F + Δ where F is the original heuristic function value of the road segment; the Δ is a correction value determined based on the empirical weight set of the road segment. The device of claim 9, wherein the road segment is an extended road segment of the planned road segment that has been determined in the path planning; the Δ is calculated according to the following formula: Δ = α × ( β × S + γ × C ) wherein the α is a first adjustment factor, the β is a second adjustment factor, and the γ is a third adjustment factor; the S is a target associated segment of the road segment and the planned road segment in the plurality of historical paths The frequency of occurrence of the group, where C is the frequency of occurrence of the condition in which the section of the plurality of historical paths appears under the planned section.