PATH QUERYING METHOD AND DEVICE, AN APPARATUS AND NON-VOLATILE COMPUTER STORAGE MEDIUM

• US 20190056235A1
• Filed: 12/22/2015
• Published: 02/21/2019
• Est. Priority Date: 09/30/2015
• Status: Abandoned Application

• Current Assignee: Baidu Online Network Technology (Beijing) Co., Ltd (Baidu Incorporated)
• Original Assignee: Baidu Online Network Technology (Beijing) Co., Ltd (Baidu Incorporated)
• Inventors: LIU, Feng
• Application Number:
  US15/765,204
• Publication Number:
  US 20190056235A1
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor

Abstract

Path querying method, apparatus and non-volatile computer storage medium which acquires search data having a departure and a destination location; obtains according to the search data, M road segment sequences each including at least one road segment; selecting, according to a transition probability of each road segment of the at least one road segment included in respective road segment sequences, N road segment sequences from the M road segment sequences to be a route search result, wherein the transition probability of a road segment describes the probability of reaching the destination by turning to a neighboring segment of the road segment; and outputting the route search result. The disclosure does not rely on weights of roads to perform route search operation, and thus prevents obtaining an unreasonable search result due to inability to update the road weights in a timely manner, thereby improving the reliability of the route search operation.

Claims

1-14. -14. (canceled)

15. A path querying method, wherein the method comprises:

obtaining query data which include a departure location and a destination;

obtaining M road segment sequences according to the query data, each road segment sequence in the M road segment sequences comprising at least one road segment, M being an integer larger than or equal to 2;

selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination, N being an integer larger than or equal to 1 and less than or equal to M;

outputting the path query results.

16. The method according to claim 15, wherein before selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination, the method further comprises:

obtaining at least one user historical trajectory for reaching the destination according to the destination;

obtaining a historical road segment sequence corresponding to each user historical trajectory in the at least one user historical trajectory;

according to the historical road segment sequence corresponding to said each user historical trajectory, obtaining the number of first trajectories of passing each road segment included in the historical road segment sequence, and the number of second trajectories of passing the road segment and then passing each neighboring road segment of the road segment; and

according to the number of first trajectories and the number of second trajectories, obtaining a turn probability from each road segment included in the historical road segment sequence to the road segment'"'"'s each neighboring road segment which is accessible to the destination.

17. The method according to claim 16, wherein the obtaining at least one user historical trajectory for reaching the destination according to the destination comprises:

obtaining an urban road network region to which the destination belongs according to the destination; and

according to the urban road network region to which the destination belongs, obtaining at least one user historical trajectory for reaching the urban road network region to which the destination belongs, as at least one user historical trajectory for reaching the destination.

18. The method according to claim 17, wherein before obtaining an urban road network region to which the destination belongs according to the destination, the method further comprises:

dividing the urban road network with a designated spacing to generate several urban road network regions in the urban road network.

19. The method according to claim 15, wherein the selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination comprises:

obtaining a combined probability of said each road segment sequence according to the turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination;

selecting N road segment sequences from the M road segment sequences as the path query results according to the combined probability of said each road segment sequence.

20. The method according to claim 19, wherein the selecting N road segment sequences from the M road segment sequences as the path query results according to the combined probability of said each road segment sequence comprises:

considering N road segment sequences with a maximum combined probability as the path query results;

or

considering a road segment sequence whose combined probability is larger than or equal to a preset probability threshold, as one road segment sequence in the N road segment sequences.

21. A device, comprising

one or more processors;

a memory;

one or more programs stored in the memory and configured to execute the following operation when executed by the one or more processors;

obtaining query data which include a departure location and a destination;

obtaining M road segment sequences according to the query data, each road segment sequence in the M road segment sequences comprising at least one road segment, M being an integer larger than or equal to 2;

selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination, N being an integer larger than or equal to 1 and less than or equal to M;

outputting the path query results.

22. The device according to claim 21, wherein before selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination, the operation further comprises:

obtaining at least one user historical trajectory for reaching the destination according to the destination;

obtaining a historical road segment sequence corresponding to each user historical trajectory in the at least one user historical trajectory;

according to the historical road segment sequence corresponding to said each user historical trajectory, obtaining the number of first trajectories of passing each road segment included in the historical road segment sequence, and the number of second trajectories of passing the road segment and then passing each neighboring road segment of the road segment; and

according to the number of first trajectories and the number of second trajectories, obtaining a turn probability from each road segment included in the historical road segment sequence to the road segment'"'"'s each neighboring road segment which is accessible to the destination.

23. The device according to claim 22, wherein the operation of obtaining at least one user historical trajectory for reaching the destination according to the destination comprises:

obtaining an urban road network region to which the destination belongs according to the destination; and

according to the urban road network region to which the destination belongs, obtaining at least one user historical trajectory for reaching the urban road network region to which the destination belongs, as at least one user historical trajectory for reaching the destination.

24. The device according to claim 23, wherein before obtaining an urban road network region to which the destination belongs according to the destination, the operation further comprises:

dividing the urban road network with a designated spacing to generate several urban road network regions in the urban road network.

25. The device according to claim 21, wherein the operation of selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination comprises:

obtaining a combined probability of said each road segment sequence according to the turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination;

selecting N road segment sequences from the M road segment sequences as the path query results according to the combined probability of said each road segment sequence.

26. The device according to claim 25, wherein the operation of selecting N road segment sequences from the M road segment sequences as the path query results according to the combined probability of said each road segment sequence comprises:

considering N road segment sequences with a maximum combined probability as the path query results;

or

considering a road segment sequence whose combined probability is larger than or equal to a preset probability threshold, as one road segment sequence in the N road segment sequences.

27. A non-volatile computer storage medium in which one or more programs are stored, an apparatus being enabled to execute the following operation when said one or more programs are executed by the apparatus:

obtaining query data which include a departure location and a destination;

obtaining M road segment sequences according to the query data, each road segment sequence of the M road segment sequences comprising at least one road segment, M being an integer larger than or equal to 2;

selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination, N being an integer larger than or equal to 1 and less than or equal to M;

outputting the path query results.

28. The non-volatile computer storage medium according to claim 27, wherein before selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination, the operation further comprises:

obtaining at least one user historical trajectory for reaching the destination according to the destination;

obtaining a historical road segment sequence corresponding to each user historical trajectory in the at least one user historical trajectory;

according to the historical road segment sequence corresponding to said each user historical trajectory, obtaining the number of first trajectories of passing each road segment included in the historical road segment sequence, and the number of second trajectories of passing the road segment and then passing each neighboring road segment of the road segment; and

according to the number of first trajectories and the number of second trajectories, obtaining a turn probability from each road segment included in the historical road segment sequence to the road segment'"'"'s each neighboring road segment which is accessible to the destination.

29. The non-volatile computer storage medium according to claim 28, wherein the operation of obtaining at least one user historical trajectory for reaching the destination according to the destination comprises:

obtaining an urban road network region to which the destination belongs according to the destination; and

according to the urban road network region to which the destination belongs, obtaining at least one user historical trajectory for reaching the urban road network region to which the destination belongs, as at least one user historical trajectory for reaching the destination.

30. The non-volatile computer storage medium according to claim 29, wherein before obtaining an urban road network region to which the destination belongs according to the destination, the operation further comprises:

dividing the urban road network with a designated spacing to generate several urban road network regions in the urban road network.

31. The non-volatile computer storage medium according to claim 27, wherein the operation of selecting N road segment sequences from the M road segment sequences as path query results according to a turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination comprises:

obtaining a combined probability of said each road segment sequence according to the turn probability from each road segment in the at least one road segment included in said each road segment sequence to the road segment'"'"'s neighboring road segment which is accessible to the destination;

selecting N road segment sequences from the M road segment sequences as the path query results according to the combined probability of said each road segment sequence.

32. The non-volatile computer storage medium according to claim 31, wherein the operation of selecting N road segment sequences from the M road segment sequences as the path query results according to the combined probability of said each road segment sequence comprises:

considering N road segment sequences with a maximum combined probability as the path query results;

or

considering a road segment sequence whose combined probability is larger than or equal to a preset probability threshold, as one road segment sequence in the N road segment sequences.