WO2017124331A1

WO2017124331A1 - Navigation apparatus and method

Info

Publication number: WO2017124331A1
Application number: PCT/CN2016/071472
Authority: WO
Inventors: Jesper Olsen; Jilei Tian; Yang Cao
Original assignee: Bayerische Motoren Werke Aktiengesellschaft
Priority date: 2016-01-20
Filing date: 2016-01-20
Publication date: 2017-07-27

Abstract

There is provided a navigation apparatus(500), comprising: a memory configured to store user's travel profile data including at least link familiarity data of links(1, 2, 3, 4, 5, 6), the link familiarity data for each link(1, 2, 3, 4, 5, 6) indicating familiarity for the user with regard to the link(1, 2, 3, 4, 5, 6); and a processor(2004) configured to generate a set of candidate routes in response to a request for navigation, compute a route score for each candidate route based at least on the user's travel profile data and output navigation information based on the route score, wherein each candidate route comprises one or more links(1, 2, 3, 4, 5, 6).

Description

A NAVIGATION APPARATUS AND METHOD

FIELD OF THE INVENTION

The present disclosure relates to a navigation apparatus and method.

BACKGROUND OF THE INVENTION

Navigation systems, such as satellite navigation systems, are commonly used to determine a general location of a user, to determine a route to a destination location, to navigate to that destination location, or to log a route that was taken by the user. One example of a navigation system uses a global navigation satellite system, such as the Global Positioning System (GPS) , and receives satellite signals broadcasted from multiple satellites. Navigation systems often include receivers carried by, for example, a user or a vehicle as the user or vehicle moves. These navigation system receivers may receive navigation signals from satellites, wireless fidelity (Wi-Fi) access points (APs) , and inertial sensors； process the navigation signals to obtain navigation data, such as estimated position of the receiver； and provide the navigation data, navigation data log, or navigation instructions based on the navigation data to the user. Navigation instructions may be provided by displaying a navigation route with an approximate receiver (i.e., user or vehicle) location on a map using a map application. The navigation data log can be provided as raw navigation data or navigation data stamped with a differential or an absolute time stamp.

GPS navigation systems for vehicles play a vital role in providing direction information and guiding a driver on the route from a start location toward a destination location. GPS navigation systems offer the route planning depending on the real time traffic, and the fastest route or the shortest route may be selected by the GPS navigation systems.

SUMMARY OF THE INVENTION

One aspect of the disclosure aims to provide a new navigation apparatus and method for providing personalized navigation service.

A navigation apparatus according to one aspect of the present disclosure is a navigation apparatus comprising：a memory configured to store user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and a processor configured to generate a set of candidate routes in response to a request for navigation, compute a route score for each candidate route based at least on the user’s travel profile data and output navigation information based on the route score, wherein each candidate route comprises one or more links.

In one aspect of the present disclosure, the link familiarity data of a certain link is based on the number of times the user has visited the certain link in history.

In one aspect of the present disclosure， the user’s travel profile data further includes node familiarity data of a node, the node familiarity data indicating familiarity for the user with regard to the node, wherein the node connects two or more links.

In one aspect of the present disclosure, the node familiarity data is calculated as a posterior probability from a prior link to a posterior link connected by the node.

In one aspect of the present disclosure, the navigation apparatus further comprises an interface for receiving the request for navigation from the user, and presenting the navigation information to the user.

In one aspect of the present disclosure, the interface does not provide voice navigation prompt for a link when the link familiarity data of the link is greater than or equal to a threshold.

In one aspect of the present disclosure, the navigation apparatus further comprises a location acquiring device for providing location data indicating a current location of the apparatus.

In one aspect of the present disclosure, the processor is further configured to update the driver’s travel profile data based on the driver’s travel history recorded during the navigation.

In one aspect of the present disclosure, the navigation information which is output includes the route with the minimum route score.

In one aspect of the present disclosure, the route score is a cost traversing through the route, and a value of the route score is in negative correlation with a value of the link familiarity data.

In one aspect of the present disclosure, it is switchable between a first mode in which the user prefers a familiar route and a second mode in which the user prefers an unfamiliar route in response to the user’s input.

In one aspect of the present disclosure, in the first mode a value of the route score is in negative correlation with a value of the link familiar data, and in the second mode a value of the route score is in positive correlation with a value of the link familiar data.

In one aspect of the present disclosure, the route score for each candidate route is computed based further on at least one of a length of the link, an estimated time of arrival, a traffic status, a distance to a desired place, and popularity of a place.

In one aspect of the present disclosure, one or more weights are determined based on the link familiarity data of the one or more links, and the route score is obtained by applying the one or more weights to one or more values computed based on at least one of a length of the link, an estimated time of arrival, a traffic status, a distance to a desired place, and popularity of a place.

A navigation method according to one aspect of the present disclosure is a navigation method comprising： obtaining user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and generating a set of candidate routes in response to a request for navigation， computing a route score for each candidate route based at least on the user’s travel profile data and outputting navigation information based on the route score, wherein each candidate route comprises one or more links.

A navigation apparatus according to one aspect of the present disclosure is a navigation apparatus comprising： a module for storing user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and a module for generating a set of candidate routes in response to a request for navigation, computing a route score for each candidate route based at least on the user’s travel profile data and outputting navigation information based on the route score, wherein each candidate route comprises one or more links.

A machine-readable storage medium according to one aspect of the present disclosure is a machine-readable storage medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for generating navigation information, the process comprising: obtaining user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and generating a set of candidate routes in response to a request for navigation, computing a route score for each candidate route based at least on the user’s travel profile data and outputting navigation information based on the route score, wherein each candidate route comprises one or more links.

Further scope of applicability of the present disclosure will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the disclosure, are given by way of illustration only, since various changes and modifications within the spirit and scope of the disclosure will become apparent to those skilled in the art from the following detailed description.

BRIEF DESCRIPTION OF THE DRAWINGS

The above and other aspects and advantages of the present invention will become apparent from the following detailed description of exemplary embodiments taken in conjunction with the accompanying drawings which illustrate, by way of example, the principles of the invention.

FIG. 1 is a simplified schematic diagram illustrating a hardware example of a computing device that can work in accordance with an implementation of the present disclosure；

FIG. 2 is a flowchart showing the navigation method in accordance with an exemplary implementation of the present disclosure；

FIG. 3 is a schematic view showing an exemplary example of a map including links according to an exemplary implementation of the present disclosure；

FIG. 4 illustrates an exemplary example of a map including links and nodes according to an exemplary implementation of the present disclosure；

FIG. 5 illustrates an exemplary example of a navigation apparatus according to an exemplary implementation of the present disclosure.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

In the following detailed description, numerous specific details are set forth to provide a thorough understanding of the described exemplary embodiments. It will be apparent, however, to one skilled in the art that the described embodiments can be practiced without some or all of these specific details. In other exemplary embodiments, well known structures or process steps have not been described in detail in order to avoid unnecessarily obscuring the concept of the present disclosure.

With reference to FIG. 1, a computing device 2000, which is an example of the hardware device that may be applied to the aspects of the present disclosure, will now be described. The computing device 2000 may be any machine configured to perform processing and/or calculations, may be but is not limited to a work station, a server, a desktop computer, a laptop computer, a tablet computer, a personal data assistant, a smart phone, an on-vehicle computer or any combination thereof. A navigation apparatus to be described in the following may be wholly or at least partially implemented by the computing device 2000 or a similar device or system.

The computing device 2000 may comprise elements that are connected with or in communication with a bus 2002, possibly via one or more interfaces. For example, the computing device 2000 may comprise the bus 2002, and one or more processors 2004, one or more input devices 2006 and one or more output devices 2008. The one or more processors 2004 may be any kinds of processors, and may comprise but are not limited to one or more general-purpose processors and/or one or more special-purpose processors (such as special processing chips) . The input devices 2006 may be any kinds of devices that can input information to the computing device, and may comprise but are not limited to a mouse, a keyboard, a touchscreen, a microphone and/or a remote control. The output devices 2008 may be any kinds of devices that can present information, and may comprise but are not limited to display, a speaker, a video/audio output terminal, a vibrator and/or a printer. The computing device 2000 may also comprise or be connected with non-transitory storage devices 2010 which may be any storage devices that are non-transitory and can implement data stores, and may comprise but are not limited to a disk drive, an optical storage device, a solid-state storage, a floppy disk, a flexible disk, hard disk, a magnetic tape or any other magnetic medium, a compact disc or any other optical medium, a ROM (Read Only Memory) , a RAM (Random Access Memory) , a cache memory and/or any other memory chip or cartridge, and/or any other medium from which a computer may read data, instructions and/or code. The non-transitory storage devices 2010 may be detachable from an interface. The non-transitory storage devices 2010 may have data/instructions/code for implementing the methods and steps which are described. The computing device 2000 may also comprise a communication device 2012. The communication device 2012 may be any kinds of device or system that can enable communication with external apparatuses and/or with a network, and may comprise but are not limited to a modem, a network card, an infrared communication deviFH， a wireless communication device and/or a chipset such as a Bluetooth^TM device， 1302.11 device, WiFi device, WiMax device, cellular communication facilities and/or the like.

The computing device 2000 (and therefore the navigation apparatus) may be used in a vehicle as an on-vehicle device, so it may be connected to an external device which may be, for example, at least one of a GPS receiver, sensors for sensing different environmental data such as an acceleration sensor, a wheel speed sensor, a gyroscope and so on.In this way, the computing device 2000 may, for example, receive location data and sensor data indicating the traveling situation of the vehicle. When the computing device 2000 is used as an on-vehicle device, it may also be connected to other facilities (such as an engine system, a wiper, an anti-lock Braking System or the like) for controlling the traveling and operation of the vehicle.

In addition, the non-transitory storage devices 2010 may have map information and software elements so that the processor 2004 may perform route guidance processing. In addition, the output device 2006 may comprise a display for displaying the map, the location mark of the vehicle and also images indicating the traveling situation of the vehicle. The output device 2006 may also comprise a speaker or interface with an ear phone for audio guidance.

The bus 2002 may include but is not limited to Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus. Particularly, for anon-vehicle device, the bus 2002 may also include a Controller Area Network (CAN) bus or other architectures designed for application on an automobile.

The computing device 2000 may also comprise a working memory 2014, which may be any kind of working memory that may store instructions and/or data useful for the working of the processor 2004, and may comprise but is not limited to a random access memory and/or a read-only memory device.

Software elements may be located in the working memory 2014, including but are not limited to an operating system 2016, one or more application programs 2018, drivers and/or other data and codes.

FIG. 2 is a flowchart showing the navigation method in accordance with an exemplary implementation of the present disclosure.

In an exemplary implementation, the navigation method shown in FIG. 2 may be performed by a navigation apparatus which is or includes the computing device 2000 as shown in FIG. 1.

As shown in FIG. 2, the flow starts at step S201, wherein user’s travel profile data is obtained. The user’s travel profile can be learnt, for example, from the user’s travel history.

In an exemplary implementation, the user’s travel profile data may be stored in the storage device 2010, and in operation, the memory 2014 may obtain the user’s travel profile data from the storage device 2010. Alternatively, the user’s travel profile data may also be obtained from a network via the communication device 2012.

In an exemplary implementation, the non-transitory storage devices 2010 may also store map information and software elements so that the processor 2004 may perform route processing. Alternatively, the map information or software elements can also be stored in other storage devices or be provided via the bus 2002 or other interfaces.

The user’s travel profile data at least includes link familiarity data.

A link may indicate a road segment. For example, a link may indicate a road segment between two consecutive road intersections. The term “road intersection” herein is not limited to an intersection with a shape of cross, but any point with branches so that a driver must make a choice as to which branch he would proceed is a road intersection mentioned in the present disclosure. According to an implementation, different links may also be determined depending on, for example, road segments with different traffic constraints, e.g. different speed limits.

In an exemplary implementation, the storage devices 2010 may also store at least a map including a plurality of links, and each link is described by using a link ID. It is possible to store the links with GPS coordinates of their starts and ends of the respective road segments. FIG. 3 is a schematic view showing an exemplary example of a map including links (link (1) - link (6) ) according to an exemplary implementation of the present disclosure. It can be seen from FIG. 3 that link (1) , for example, may be a road segment between road intersection 1 and road intersection 2, and link (3) , for example, may be a road segment between a road intersection 1 and a point where a traffic constraint changes (e.g. a speed change point 1) . A map may also store other attributes of the links (e.g. public facilities such as restaurants, gas stations, or the like) .

As attribute data for each link, the link familiarity data for each link indicates familiarity for the user with regard to the link.

The link familiarity data can be relative values and may have numerical ranges as desired. For example, the more familiar the user is with a certain link (road segment) , the larger the value of the link familiarity data will be. The link familiarity data of a link may be defined based at least on the times the user has traversed through the link. Only as examples, the link familiarity data of a link may be defined as the number of times the user has traversed through the link or a value obtained by dividing the number of times the user has visited the link by the sum of visits to all links in history. It is also possible that the link familiarity data of a link may be based further on the times the user has traversed through adjacent or connected links.

In an exemplary implementation, for a link the user has never traversed through, the link familiarity data of a link can be set to a non-zero value. For example, the link familiarity data of a non-visited link may be set to a small positive floor value, may be set based on the distance to home (e.g.,

where L is a positive predetermined value and distance (link，home) represents the distance between the link and the user’s home. The closer the link is to the user’s home， the larger the value of link familiarity data is) , or may be set based on the link familiarity data of the closest link which has been visited and the distance thereto. Here the distance may be a distance normalized by a predetermined distance.

In the example of FIG. 3, the times for which links (1) - (6) have been visited may, for example, be 12, 20, 8, 8, 24 and 28. If the link familiarity data of a certain link is defined as a value obtained by dividing the number of times the user has visited the certain link by the sum of visits to all links in history, the link familiarity data for links (1) - (6) may be calculated as 0.12, 0.20, 0.08, 0.08, 0.24 and 0.28.

Then in step S203, a set of candidate routes are generated in response to a request for navigation. Each of the generated candidate routes includes one or more links. Step S203 may be performed by the processor 2004 by executing program codes corresponding to step S203 which are loaded from the storage device 2010 into the working memory 2014.

In an exemplary implementation, the request for navigation may, for example, comprise a start location and a destination location, and each of the generated candidate routes is a connected sequence of links from the start location toward the destination location. In an exemplary implementation, the navigation apparatus may comprise a location acquiring device such as a GPS receiver or the like configured to provide location data indicating a current location of the navigation apparatus. In this case, it is also possible that the request for navigation includes only the destination location, and the start location is generated by the location acquiring device. According to another exemplary implementation, the request for navigation may only include an intended activity (for example, dining, gas filling, or the like) . In this case, the destination may be automatically generated according to the intended activity (for example, the closest restaurant, the closest gas station, or the like) and no specific destination location is necessary to be input by the user.

In an exemplary implementation, as an example, the set of candidate route may be determined by exhausting all possibilities, i.e., starting from the given node and iterating over all potential paths until reaching the destination node, such as breadth-first and depth-first search. Alternatively, the set of candidate route may also be determined by strategically eliminate impossible path, such as A-star and Dijkstra's algorithm.

In the example shown in FIG. 3, supposing the start location is the road intersection 1, and the destination location is the road intersection 4, then a set of candidate routes including three candidate routes may be generated as follows:

Candidate route (1) : link (1) , link (2) ；

Candidate route (2) : link (3) , link (4) ；

Candidate route (3) : link (5) , link (6) .

Then in step S205, a route score is computed for each candidate route based at least on the user’s travel profile data. Step S205 may be performed by the processor 2004 by executing program codes corresponding to step S205 which are loaded from the storage device 2010 into the working memory 2014.

Herein the route score is a score computed for each route. The route score for a certain route is based at least on the user’s travel profile data, which includes at least the link familiarity data of the links included in the certain route. The route score may be designed so that a higher score is preferred (which may be called “positive score” ) , or may be designed so that a lower score is preferred (usually called “cost” ) . In an exemplary implementation, the route score for a certain route may be simply calculated by taking an opposite of the average value of all link familiarity data of the links included in the certain route. In this case, a minimum route score may be preferred if the user prefers a more familiar route, or a maximum route score may be preferred if the user prefers a less familiar route.

In the example shown in FIG. 3, the route score of each of the candidate route may be calculated for example as follows.

Route score of candidate route (1) ＝ - (familiarity data of link (1) + familiarity data of link (1) ) /2 ＝ (0.12+0.20) /2＝ -0.16；

Route score of candidate route (2) ＝ - (familiarity data of link (3) + familiarity data of link (4) ) /2 ＝ (0.08+0.08) /2 ＝ -0.08；

Route score of candidate route (3) ＝ - (familiarity data of link (5) + familiarity data of link (6) ) /2 ＝ (0.24+0.28) /2 ＝ -0.26.

Then in step S207, navigation information is output based on the route score. Step S207 may be performed by the processor 2004 by executing program codes corresponding to step S207 which are loaded from the storage device 2010 into the working memory 2014.

Herein the ways for outputting the navigation information is not limited to any specific way. For example, it is possible that the navigation information which is output includes the route with the minimum route score if the route score is in negative correlation with the user’s preference (in this case, the route score may also be referred to as a route cost) . For example, it is also possible to output, as the navigation information, the optimal route which is the route with a maximum route score if the route score is in positive correlation with the user’s preference. In either case, the processor 2004 may find out an optimal route which means a route that may be preferred by the user, and output the optimal route. It is not necessary to output only one optimal route. For example, it is also possible to output, as the navigation information, a plurality of candidate routes sorted according to their respective route scores. For example, it is also possible to output, as the navigation information, a plurality of candidate routes sorted according to other factors (for example, the lengths of the respective candidate routes, the estimated times spent for the respective candidate routes, the traffic conditions of the respective candidate routes, or the like) , and the route score data is output along with each of the candidate routes. In a case where a plurality of candidate routes are output, the user may select one route according to his preferred route score data.

In an exemplary implementation, when the navigation information which is output includes the route with the minimum route score and the route score is in negative correlation with the user’s preference， Dijkstra’s algorithm， A-star algorithm or the like can be used to obtain the route with the minimum route score.

In the example shown in FIG. 3, as the navigation information, it is possible to output only candidate route (3) with the minimum route score as the recommended optimal route. It is also possible to output all candidate routes (1) - (3) in the order from the lowest route score to the highest route score. It is also possible to output all candidate routes (1) - (3) in the order from the shortest length to the longest length and each candidate route comes with its route score or its representation which reflects the familiarity of the link for the user.

In this way, the present application provides a new idea in which the user’s travel profile data (user’s travel history data) is considered during navigation. Therefore, the user may drive in a route which he feels comfortable.

More specifically, every user may have his own regular pattern of traveling. For example, a user may be particularly familiar with some links but does not like some other links. Generally speaking, driving in familiar areas is more relaxing, more multi-task-flexible, and/or safer. In addition, a user may particularly like some links because there are user’s favorable places in the midway of the links and therefore these links will have higher familiarity data.

Objective factors such as arrival time or length of the route cannot reflect such a potential preference relating to the user’s experience. On the other hand, by virtue of the method according to the present disclosure, familiarity data of links which are determined, for example, from the travel history of the user, may reflect the user’s travel experience, and therefore may help find out a route which may more accurately meet the user’s preference.

Examples of a basic navigation method according to some implementations of the present disclosure have been described with reference to FIG. 2. Nevertheless, the examples which have been described are not restrictive, but other implementations are also possible according to the concept of the present disclosure.

In an exemplary implementation, in step S205, the route score for each candidate route may be computed not only based on the link familiarity data of the links included in the candidate route, but also based further on at least one of lengths of the links, an estimated time of arrival, a traffic status, a distance to a desired place during the midway, and popularity of a place during the midway. These further factors may be considered in combination with the link familiarity data in any manner. In one example, one or more weights may be determined based on the link familiarity data of the one or more links, and the route score may be obtained by applying the one or more weights to one or more values computed based on at least one of a length of the link, an estimated time of arrival, a traffic status, a distance to a desired place, and popularity of a place.

In this case, the route score of each candidate route may be computed as a route cost for traversing through the candidate route. Usually, a candidate with a lower cost will be preferred by the user. If the user prefers a more familiar route, a value of the route score may be in negative correlation with a value of the link familiarity data. In other words, if the user prefers a more familiar route, then the higher the link familiarity data of a link is, the lower the route score for traversing through a candidate route including the link will be.

According to an exemplary implementation, a preliminary route score of traversing a candidate route, for example, an estimated time to be spent on a candidate route, may be computed according to any known method, and a weight calculated based on the familiarities of the links included in the candidate route may be applied to the preliminary route score to obtain the final route score. Still taking the example shown in FIG. 3, if the estimated time to be spent on each of the candidate route (1) - (3) is 2 hours, 1 hour, and 1.5 hours, and a weight is calculated based on the inverse of the average of the familiarity data of the links included in each of the candidate routes, then the route score (route cost) of each of the candidate routes will be calculated as:

Route score of candidate route (1) ＝ 2 /0.16 ＝ 12.5；

Route score of candidate route (2) ＝ 1/0.08＝12.5；

Route score of candidate route (3) ＝ 1.5/0.26＝5.77.

It can be seen that although the candidate route (2) has the lowest preliminary score (estimated time to be spent) , after the familiarities of the links are taken into consideration, the candidate route (3) turns out to have the lowest score because user is more familiar with the links included in the candidate route (3) . If an optimal route is to be recommended in step S207, it is possible to output the candidate route (3) which has the minimum route score, which reflects a best balance between the time to be spent and the familiarity of the route.

According to an exemplary implementation, a plurality of weights may be determined based on each of the link familiarity data of the links included in a certain candidate route, and each of the weights is applied to one value determined according to one further factor of a link.

In this case, the total route score for a candidate route is calculated by summing up all the score of the links included in the candidate route. The total route score of the candidate route may, for example, be represented as

score_route (route (n) ) ＝Σ_iscore_link (link (i) ) ...expression (1)

In the above expression, score_routs (route (n) ) is the total route score of the n-th candidate route, score_link (link (i) ) is a link score of the i-th link denoted by link (i) , and i represents the index of the links included in the route.

As an example, the score of link (i) can be defined as

score_link (link (i) ) ＝f_p (link (i) ) ， ...expression (2)

where f_p may be a personalized cost function for link (i) .

In the above expression, f_p (link (i) ) can be defined as, for example but is not limited to

f_p (link (i) ) ＝time (link (i) ) *e^{-α*familiarity (link (i) )}, ...expression (3)

where *represents the multiplication sign, time (link (i) ) is an estimated time to be spent on the i-th link, e is the natural logarithm, familiarity (link (i) ) is the link familiarity data for the i-th link, e^{-α*familiarity (link (i) )} is a weight determined based on the link familiarity data for the i-th link, and α is the weight coefficient to control the strength of the weighting by the link familiarity data and therefore to control the balance between the familiarity factor and other factors.

It is apparent that f_p (link (i) ) can also be defined similarly as:

f_p (link (i) ) ＝length (link (i) ) *e^{-α*familiarity (link (i) )}, ...expression (4)

where length (link (i) ) is the length of the i-th link.

It is apparent that f_p (link (i) ) can also be defined similarly as the following so that both times and lengths may be considered in the route score:

f_p (link (i) ) ＝time (link (i) ) *length (link (i) ) *e^{-α*familiarity (link (i) )}

...expression (5)

By virtue of the above exemplary implementation, in calculation of the route score for each candidate route, each link is considered not only in terms of time to be spent and/or length, but also in terms of whether the user is familiar with the link. In this way, the balance between the user’s preference on other factors (for example, a shorter driving time) , and the user’s preference on a more familiar route may be achieved.

In the above, implementations and examples are described in which the user’s travel profile includes link familiarity data of links included in a route, and a route score is computed based at least on the link familiarity data.

In an exemplary implementation of the present disclosure, the user’s travel profile data (stored in the storage device 2010, for example) may further include node familiarity data of a node. FIG. 4 illustrates an exemplary example of a map including links and nodes according to an exemplary implementation of the present disclosure. As shown in FIG. 4, a node herein means a point which connects two or more links. For example, a node may be a road intersection at which links (road sections) intersect. For example, a node may also be a point where a traffic constraint changes (e.g. a speed change point) .

The node familiarity data indicate familiarity for the user with regard to the node. In an exemplary implementation, the node familiarity data may be calculated as, for example, a posterior probability from a prior link to a posterior link connected by the node.

More specifically, each node has a personal transition probability from one link to another link. The node familiarity data can be learnt from the user’s travel history and calculated as, for example but are not limited to, a posterior probability from a prior link (link (a) ) to a posterior link (link (b) ) connected by the node. The posterior probability represents the transition possibility when the user chooses which link the user prefers to traverse through at the node.

In an exemplary implementation, in computing a route score in step S205, for each candidate route, the total route score of the candidate route may include a term of a node score calculated based on the node familiarity data of the nodes of the candidate route and a term of a link score calculated based on the link familiarity data of the links of the candidate route. The term of a node score and the term of a link score may be summed or may be multiplied with each other, or may be combined in other ways.

As a example, the total route score of the candidate route can be represented as

score_route (route (n) ) ＝Σ_i [score_link (link (i) ) +w*score_node (node (j) ) ] ,

...expression (6)

where score_link (link (i) ) is a link score of the i-th link denoted by link (i) , score_node (node (j) ) is a node score of the j-th node denoted by node (j) , node (j) is a node connecting link (i) and the link (k) which is a link prior to link (i) , w is a coefficient to adjust the contribution of the link score (score_link) and the contribution of the node score (score_node) to the total route score of the route (score_route) , i represents the index of the links included in the route, and j represents the index of the nodes included in the route.

According to an exemplary example, the transition score of the node (j) can be defined as

score (node (j) ， link (k) →link (i) ) ＝f_n (p (link (i) |link (k) ) )

...expression (7)

where link (k) and link (i) are connected by node (j) , and p (link (i) |link (k) ) represents the transition probability from link (k) to link (i) of the user according to the user’s travel history.

In a case where the route score is in negative correlation with the link familiarity data, the route score may be designed also in negative correlation with the node familiarity data.

As an example, score_link (link (i) ) may be defined as，for example but is not limited to

score_link (link (i) ) ＝e^{-link familiarity data}, ...expression (8)

Accordingly, f_n (x) can be defined as, for example but is not limited to

f_n (x) ＝e^-x, ...expression (9)

According to such an implementation of the present disclosure, not only statistic familiarity data of each link is considered, but also a dynamic transition probability from a prior link to the present link is considered. Therefore, the user’s travel experience may be better reflected, and may help find out a route which may more accurately meet the user’s preference.

In the following, a specific example of determining the route score in step S205 will be described in detail. It is to be noted that the specific example is only exemplary and does not intend to constitute any limitation.

According to the example, the expression (6) is adopted, and is recalled as follows:

...expression (6)

In this example, the link score for the i-th link (link (i) ) , that is, score_link (link (i) ) , may be calculated according to the following expression:

score_link (link (i) )

＝μ₁*f_p (link (i) ) +μ₂*length (link (i) ) +μ₃*time (link (i) ) +μ₄ *f_o (other factors)

...expression (10)

where, f_p (link (i) ) is the personalized cost for link (i) and may be calculated according to expression (3) , (4) or (5) , length (link (i) ) is the length of link (i) (which may be stored in the storage device 2010 in advance) , time (link (i) ) is the estimated traversing time of link (i) , f_o (other factors) is a cost associated with other attributes such as whether there is a toll in the link (i) , the safety of link (i) , etc, and parameters μ₁～μ₄ can be set according to the navigation scheme as the user selects. For the scheme in which the user prefers the shortest route, μ₁, μ₃ and μ₄ may be set to a value smaller than 1 (0 for example) , and μ₂ may be set to 1. For the scheme in which the user prefers the fastest route, μ₁, μ₂ and μ₄ may be set to a value smaller than 1 (0 for example) , and μ₃ may be set to 1. For the scheme in which the user would like to take the familiarity of the route into consideration, μ₂, μ₃ and μ₄ may be set to a value smaller than 1 (0 for example) , and μ₁ may be set to 1.

For example, time (link (i) ) may be a predetermined empirical value for traveling through link (i) which is stored in the storage device 2010 in advance.

According to an exemplary implementation, time (link (i) ) can be defined as follows.

...expression (11)

In expression (11) , traffic (link (i) ) represents the predicted or real-time traffic condition of the link (i) . If the traffic condition for link (i) is very good, traffic (link (i)) is set to a lower limit such as 1. If there is a serious traffic jam for link (i) , traffic (link (i) ) is set to an upper limit such as 10. For other traffic conditions, link (i) may be set between 1 and 10. In addition, type (link (i) ) represents the parameter for the road type of the link (i) , such as city road, highway, country road, ramp or the like. As an example, type (link (i) ) may be set to1 for high way, and may be set to a larger value for a city road. The values of type (link (i)) may be determined according to the historical data.

In addition, f₀ (other attributes) can be defined as follows:

f₀＝c1*I (toll (link (i) ) ) +c2*I (unsafety (link (i) ) )

where

... expression (12)

In the above expression (12) , toll (link (i) ) is set to 1 if there is a toll in the midway of the link (i) , and is set to 0 if there is no toll in the midway of the link (i) . In addition, unsafery (link (i) ) is set to 1 if there link (i) is unsafe, and is set to 0 if link (i) is safe. The value of c1 and c2 can be set by the user according to the user’s needs. For example, if the safety is not a concern, c2 ＝ 0 otherwise c2 ＝ 1； and if the toll free is a concern, c1 ＝ 1 otherwise c1＝0.

Moreover, as an example, the transition score_node (node (j) ) in expression (6) can be defined as

Score (node (j) ， link (k) →link (i) ) ＝γ1*f_n (p (link (i) |link (k) ) ) +γ2*f_a (angle (link (i) |link (k) ) ) +γ3*f_o (other attribute)

...expression (13)

In expression (13) , link (k) and link (i) are connected by node (j) , p (link (i) |link (k) ) represents the personal transition probability the user traverses link (k) and turns to link (i) at node (j) , f_n is the personalized cost and may be calculated according to expression (9) , f_a measures the cost due to angle change of two links, f_b measures the cost of other attribute such as traffic light signal, angle (link (i) |link (k) ) indicates the angle formed between link (i) and link (k) , and may for example be 90°, 180° or 270°, and γ1, γ2, γ3 are coefficient which can be set according to the navigation scheme as the user selects.

As an example, f_n (x) , f_a (x) , f_b (x) can be defined but are not limited to as

f_n (x) ＝e^-x ...expression (13)

...expression (14)

...expression (15)

where dur_red represents the average duration the red light is on, dur_green represent the average duration the green light is on. f_b represents the average time cost for the vehicle to wait from link (k) to link (i) due to the red light.

In the above, implementations have been described with respect to the situation in which the user prefers more familiar routes.

Nevertheless, it is also possible that the user may want to try a less familiar route.

In particular, efficient unfamiliar routes or low-cost detours from “optimal” familiar routes may well exist. Sometimes the user may prefer to challenge some unfamiliar route to explore more routes or just for an exciting experience.

According to an implementation, it is switchable between a first mode (standard mode) in which the user prefers a familiar route and a second mode (challenge mode) in which the user prefers an unfamiliar route in response to the user’s input. The switching may be made by user inputs via input devices 2006 to change the mode of the navigation to the second mode (challenge mode) , in which unfamiliar route will obtain a relatively low cost and thus will be recommended to the user.

For example, the route score is a route cost traversing the candidate route, and a route with a minimum route score is preferred by the user. For example, in the first mode (standard mode) , a value of the route score is in negative correlation with a value of the link familiar data so that a higher familiar data will result in a lower route score and therefore will be preferred by the user. In addition, in the second mode (challenge mode) , a value of the route score is in positive correlation with a value of the link familiar data so that a lower familiar data will result in a lower route score and therefore will be preferred by the user.

According to an exemplary implementation, all other steps are the same between the first mode and the second mode except for that the negative and the positive correlations may be switched by inverting the sign of the link familiarity data and the node familiarity data.

For example, in the second mode, the minus sign in the exponent in expression (3) may be removed and expression (3) may be changed to the following form:

f_p (link (i) ) ＝time (link (i) ) *e^{α*familiarity (link (i) )} ...expression (16)

In addition, in the second mode, the minus sign in the exponent in expression (9) may be removed and expression (9) may be changed to the following form:

f_n (x) ＝e^x ...expression (17)

By inverting the sign of the link familiarity data and the node familiarity data, the higher the value of the familiarity data is, the higher the cost will be. Therefore, the navigation apparatus tends to recommend the route with lower familiarity.

According to another exemplary implementation, all other steps are the same between the first mode and the second mode except for that the negative and the positive correlations may be switched by inverting the value of the link familiarity data and the node familiarity data.

For example, in the second mode, the exponent in expression (3) may be inverted and expression (3) may be changed to the following form:

...expression (18)

In addition, in the second mode, the exponent in expression (9) may be inverted and expression (9) may be changed to the following form:

...expression (19)

By inverting the value of the link familiarity data and the node familiarity data, the higher the value of the familiarity data is, the higher the cost will be. Therefore, the navigation apparatus tends to recommend the route with lower familiarity.

According to these embodiments of the disclosure, the user can get some excitement by avoiding the same boring route and expand his knowledge of the local area.

In any of the above mentioned implementation, the navigation apparatus may, for example, further comprise an interface for receiving the request for navigation from the user, and presenting the navigation information to the user. The interface may be implemented with the input device 2006 and the output device 2008.

In any of the above mentioned implementation, a navigation voice prompt may, for example, be automatically turned on and off depending on user’s need.

In general, user turns on the navigation system only when driver does not know how to drive to the destination location. Drivers usually do not like to hear a voice prompt when they are taking a regular route. For example, when a user drives home from a restaurant to which the user had never been before, the user expects to have the navigation voice prompt to lead him to the road or area he is familiar with, and then to drive home directly by himself without any navigation voice prompt. In other words, a voice navigation prompt may be unnecessary when the user is driving on a familiar road segment.

Therefore, the output device 2008 may not provide voice navigation prompt for a link whose link familiarity data is greater than or equal to a threshold and thus the navigation apparatus may cause less distraction to the user.

In any of the above mentioned implementation, the processor may, for example, be further configured to update the driver’s travel profile data based on the driver’s travel history recorded during the navigation. For example, after the current travel, the link familiarity data for all the links included in the actually traveled route may be updated. More specifically, the link familiarity data for the actually traveled links will be increased. In addition, the node familiarity data for all the nodes which connect the actually traveled links may be updated. More specifically, the node familiarity data for the nodes with the actually made transitions between the links may be increased. In this way, the driver’s travel profile data may be evolved as the user travels, and the user may experienced the personalized navigation according to the driver’s travel profile data up to date.

Another embodiment of the present invention provides a navigation apparatus 500. The navigation apparatus 500

comprise module

510 and 520. The module 510 stores user’s travel profile data including at least link familiarity data of links. The link familiarity data for each link indicates familiarity for the user with regard to the link. The module 520 generates a set of candidate routes in response to a request for navigation, computes a route score for each candidate route based at least on the user’s travel profile data and outputs navigation information based on the route score, wherein each candidate route comprises one or more links.

Another embodiment of the present invention provides a navigation machine-readable storage medium encoded with instructions. When executed by one or more processors, the instructions cause the processor to carry out a process for generating navigation information， the process comprising： obtaining user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and generating a set of candidate routes in response to a request for navigation, computing a route score for each candidate route based at least on the user’s travel profile data and outputting navigation information based on the route score, wherein each candidate route comprises one or more links.

Instructions for performing the methods and steps described in the above may be comprised in the one or more application programs 2018, and the modules510 and 520 of the aforementioned navigation apparatus 500 may be implemented by the processor 2004 reading and executing the instructions of the one or more application programs 2018. More specifically, the module510 of the aforementioned navigation apparatus 500 may, for example, be implemented by the processor 2004 when executing an application 2018 having instructions to perform the step S201. In addition, the module 520 of the aforementioned navigation apparatus 500 may, for example, be implemented by the processor 2004 when executing an application 2018 having instructions to perform the step S203, S205 and S207. Other modules of the aforementioned navigation apparatus may also, for example, be implemented by the processor 2004 when executing an application 2018 having instructions to perform one or more of the aforementioned respective steps. The executable codes or source codes of the instructions of the software elements may be stored in a non-transitory computer-readable storage medium, such as the storage device (s) 2010 described above, and may be read into the working memory 2014 possibly with compilation and/or installation. The executable codes or source codes of the instructions of the software elements may also be downloaded from a remote location.

It should also be appreciated that variations may be made in accordance with specific requirements. For example, customized hardware might also be used, and/or particular elements might be implemented in hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. Further, connection to other navigation apparatus such as network input/output devices may be employed. For example, some or all of the disclosed methods and devices may be implemented by programmable hardware (for example, a programmable logic circuitry including field-programmable gate arrays (FPGA) and/or programmable logic arrays (PLA) ) with an assembler language or a hardware programming language (such as VERILOG, VHDL, C++) by using the logic and algorithm according to the present disclosure. In particular, the modules510 and 520 of the aforementioned navigation apparatus 500 may also be implemented with the programmable hardware as described in the above.

It should further be understood that the components and/or modules of navigation apparatus (for example, the navigation apparatus 500, or the navigation system implemented by the computing device 2000) can be distributed across a network. For example, some processing may be performed using one processor while other processing may be performed by another processor remote from the one processor. Other components of computing system 2000 may also be similarly distributed. As such, navigation apparatus (for example, the navigation apparatus 500, or the navigation system implemented by the computing device 2000) may be interpreted as a distributed computing system that performs processing in multiple locations.

Another embodiment of the present invention provides a navigation apparatus, which functionality can be implemented with a number of means, such as software (e.g., executable instructions encoded on one or more computer-readable mediums) , hardware (e.g., gate level logic or one or more ASICs) , firmware (e.g., one or more microcontrollers with I/O capability and embedded routines for carrying out the functionality described herein) , or some combination thereof.

Although aspects of the present disclosures have been described by far with reference to the drawings, the methods, systems, and devices described above are merely exemplary examples, and the scope of the present invention is not limited by these aspects, but is only defined by the appended claims and equivalents thereof. Various elements may be omitted or may be substituted by equivalent elements. In addition, the steps may be performed in an order different from what is described in the present disclosures. Furthermore, various elements may be combined in various manners. What is also important is that as the technology evolves, many of the elements described may be substituted by equivalent elements which emerge after the present disclosure.

Claims

A navigation apparatus, comprising:

a memory configured to store user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and

a processor configured to generate a set of candidate routes in response to a request for navigation， compute a route score for each candidate route based at least on the user’s travel profile data and output navigation information based on the route score, wherein each candidate route comprises one or more links.
The navigation apparatus of claim 1, wherein the link familiarity data of a certain link is based on the number of times the user has visited the certain link.
The navigation apparatus of claim 1 or 2， wherein the user’s travel profile data further includes node familiarity data of a node, the node familiarity data indicating familiarity for the user with regard to the node, wherein the node connects two or more links.
The navigation apparatus of claim 3, wherein for each candidate route, the route score of the candidate route includes a term of a node score calculated based on the node familiarity data of the nodes of the candidate route and a term of a link score calculated based on the link familiarity data of the links of the candidate route.
The navigation apparatus of claim 3, wherein the node familiarity data is calculated as a posterior probability from a prior link to a posterior link connected by the node.
The navigation apparatus of any of claim 1-5, further comprising an interface for receiving the request for navigation from the user, and presenting the navigation information to the user.
The navigation apparatus of claim 6, wherein the interface does not provide voice navigation prompt for a link when the link familiarity data of the link is greater than or equal to a threshold.
The navigation apparatus of claim 1, further comprising a location acquiring device for providing location data indicating a current location of the apparatus.
The navigation apparatus of claim 1, wherein the processor is further configured to update the driver’s travel profile data based on the driver’s travel history recorded during the navigation.
The navigation apparatus of claim 1, wherein the navigation information which is output includes the route with the minimum route score.
The navigation apparatus of claim 1, wherein the route score is a cost traversing through the route, and a value of the route score is in negative correlation with a value of the link familiarity data.
The navigation apparatus of claim 1, wherein it is switchable between a first mode in which the user prefers a familiar route and a second mode in which the user prefers an unfamiliar route in response to the user’s input.
The navigation apparatus of claim 12, wherein in the first mode a value of the route score is in negative correlation with a value of the link familiar data, and in the second mode a value of the route score is in positive correlation with a value of the link familiar data.
The navigation apparatus of claim 1, wherein the route score for each candidate route is computed based further on at least one of a length of the link, an estimated time of arrival, a traffic status, a distance to a desired place, and popularity of a place.
The navigation apparatus of claim 14, wherein one or more weights are determined based on the link familiarity data of the one or more links, and the route score is obtained by applying the one or more weights to one or more values computed based on at least one of a length of the link, an estimated time of arrival, a traffic status, a distance to a desired place, and popularity of a place.
A navigation method, comprising:

obtaining user’s travel profile data including at least link familiarity data of links， the link familiarity data for each link indicating familiarity for the user with regard to the link； and

generating a set of candidate routes in response to a request for navigation, computing a route score for each candidate route based at least on the user’s travel profile data and outputting navigation information based on the route score, wherein each candidate route comprises one or more links.
A navigation apparatus, comprising:

a module for storing user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and

a module generate a set of candidate routes in response to a request for navigation, compute a route score for each candidate route based at least on the user’s travel profile data and output navigation information based on the route score, wherein each candidate route comprises one or more links.
A machine-readable storage medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for generating navigation information, the process comprising:

obtaining user’s travel profile data including at least link familiarity data of links, the link familiarity data for each link indicating familiarity for the user with regard to the link； and generating a set of candidate routes in response to a request for navigation, computing a route score for each candidate route based at least on the user’s travel profile data and outputting navigation information based on the route score, wherein each candidate route comprises one or more links.