Patent Description:
"Points of Interest" or "Pols", also called landmarks, are elements that aid orientation and wayfinding: it is usual to use landmarks to provide path guiding instructions and to indicate them in access maps. Pols help people on the move constructing a mental representation of an unfamiliar environment in advance and prepare them cognitively to get through difficult or uncertain parts of that environment. Furthermore, for people knowing already a city, recognizing Pols on a map will help to localize the destination. It is therefore critical to properly select and integrate appropriate landmarks in navigational supports.

Given the prominent role Pols have in human communication, an important area of research has recently developed in the domain of automated navigation assistance that aims at programmatically exploiting landmarks to "humanize" navigation support. Examples of such solutions are presented in US Patent Application Publication No. <CIT> and in:<NPL>.

Navigation support to a destination may be provided by:.

Studies from the literature have confirmed the intuition that navigation support should be provided at different scales, starting from a high level (i.e., with little precision) to provide an overview on the situation of the destination, and successively moving to more detailed levels to become practical and operational. Examples of such studies are disclosed in: <NPL>, as well as in: <NPL>.

Different levels of details are therefore needed within an access map.

More details are typically needed around the destination whereas less details are required for long homogeneous segments (e.g. a long distance on a highway). While using and integrating different levels of precision is a common human practice, it is difficult to do it programmatically: access maps are generally generated from geographic maps which display a region at a single homogeneous scale. Depending on their scale, geographic maps will include selected corresponding structural elements like roads, green areas and major buildings like stadiums and churches. With increasing scale, they include more and more details and commercial Pols like restaurants or shops.

In general, it should be noted that selecting the optimal set of elements to be included in a map in order to help the user grasp the location of the destination is difficult: on the one hand, too many elements may be selected, which create clutter on the map, distracting the user from the relevant elements; on the other hand, relevant elements may not be part of the automatic selection and thus may be missing, not being included in the map.

Thus, recent efforts have gone towards the so-called humanization of navigation tools.

A typical example of such a study is for example disclosed in <NPL>, in which the authors propose to create a unique access map for a destination that integrates different levels of scale: their method automatically selects a set of relevant roads to access a destination, even if these roads would naturally belong to different scales (e.g. local road, national roads and highways). The method presented first selects these roads and then rearranges the selected roads sub network graphically such that it can be arranged into a single access map. However, this method is restricted to the road network. The resulting map does not include any elements beyond (drivable) roads. In particular, it does not include any landmarks to support directions, i.e. to help users decide where and when to keep or change directions in order to reach the destination.

There also exist approaches that attempt to add or highlight Pols that are relevant for following a route on a map. However, these approaches presume one specific origin, destination and route between the origin and the destination. One approach that considers different levels of scale is described in: <NPL>, already mentioned.

This approach begins by adding to the map some details around the origin and the destination location; then it determines a route from the origin to the destination and adds it to the map. It then analyses this route and its environment in order to augment the map with relevant wayfinding information depending on the route's characteristics: it identifies problematic parts like difficult or ambiguous intersections or monotone environments where the user needs additional wayfinding support; it then identifies, selects and adds Pols at each of these locations. Finally, to prevent any problem to reach the destination, it adds:.

This way, starting from an origin, a destination and a particular route, the approach successively creates a multi-granular map providing more or less detailed information for each location on the map according to how crucial the location is for reaching the destination from the origin. The core of this approach is to try to identify, through an a priori analysis of the route geography, problematic locations needing additional detail, and to add Pols to provide support at these locations.

A similar approach is known from <CIT>, in which a map to a destination is created, which contains more detailed information in the vicinity of the destination and which also includes relevant Points of Interest to assist in navigation.

An alternative to such an a priori approach could be an a posteriori analysis of problems observed, such as dynamically tracking users while they are moving and actually following a given route and to detect the errors they make. Such an error analysis has already been proposed (see e.g., <CIT>) with the aim of adapting on-board navigation instructions in their frequency, details, timing and location. However, it usually does not consider adding Pols, neither does the method described target access map generation.

To improve an access map with a set of Pols, once the critical locations are identified the optimal set of Pols that best disambiguate these locations must be selected and added to the map. To this aim, many parameters may be used, like the Pol typicality, unicity, durability, visibility, or relevance with respect to the particular transportation mode or user. Some approaches try to identify these Pols based on detailed information about each instance (e.g. visuals); others try to compute for each candidate Pol close to the location a suitability based on its position with respect to the decision point and its configuration and to the Pol category. Typical examples are described in: <NPL> and in:<NPL>.

Despite these various approaches, none combine route simplification and relevant Pol selection based on, proximity to the destination and automatic recognition of decision points and their complexity.

One general aim of the invention is to provide a method to generate an access map to a destination.

The access map can be used by anyone, with no need of any indication on the origin where the user starts and with a large range of possible distances to the destination.

The method proposed addresses all or parts of the drawbacks of the approaches proposed in the prior art.

It allows both route simplification and the use of relevant Pols selected.

It facilitates orientation for the user and disambiguates complex crossings.

The above and other objects, features and advantages of this invention will be apparent in the following detailed description of an illustrative embodiment thereof, which is to be read in connection with the accompanying drawings wherein:.

The access map generation method presented hereunder provides the user with an access map to reach a given destination point. Said access map allows a zoom effect on a focus zone around the destination point. With said zoom effect, the user is provided with enough information to help his guidance in said focus zone (i.e., an area around a travel destination, e.g. for the last mile or miles of pedestrian, bike, or car navigation), while at the same time keeping the context across the full map.

This method may be implemented within a system architecture such as that illustrated in <FIG>, which comprises two servers <NUM> and <NUM> and a user device <NUM>. Said servers <NUM>, <NUM> and said device <NUM> communicate over a network <NUM> (which may be wireless and/or wired) such as the Internet for data exchange. Each server <NUM> and <NUM> and the user device <NUM> include a data processor (11a, 11c, and 11b, respectively) and memory (12a, 12c, and 12b, respectively) such as a hard disk.

Server <NUM> is a map server, which can be for example an external service accessible by an application programming interface (API) such as Open Street Map.

Server <NUM> is a processing server, using data received from the map server <NUM> over the communication network <NUM> to compute an access map.

User device <NUM> may be any device that communicates with the server <NUM>, including a desktop computer, a laptop computer, a cell phone, a navigation system (e.g., that may be installed in a car or on a bike), a digital watch or other user wearable device. It is used by a user (user <NUM> on <FIG>) to request the generation of a given access map as well as to possibly store it and administer its diffusion to final end users which are to use the map to reach a destination point.

User <NUM> can be an individual wishing to generate an access map for the guidance up to a given destination point. The user can work an entity, such as a store, a company, a museum, etc. which needs to provide access maps to end users (e.g., clients or visitors).

In one embodiment, the access map generation method presented hereunder operates on server <NUM>, and/or on user device <NUM>. Alternatively, the access map generation may operate on user device <NUM>.

In another embodiment, it is noted that the two servers <NUM> and <NUM> may be merged. In yet another embodiment, the functionality of the two servers <NUM> and <NUM> may be merged into a standalone user device <NUM>.

The access map is generic for all users. That is, it can be used by any user, independent of a user's starting location and independent of a user's travel distance (i.e., from a user's starting location to the user's final destination).

A method <NUM> is outlined in <FIG> to generate access maps, which in one embodiment is performed by server <NUM>.

In what follows and in all the present text:.

At step <NUM>, the destination is received and the map around the destination is retrieved.

A destination point is provided to server <NUM> by user <NUM>.

The request is formulated through device <NUM>. When receiving a request, server <NUM> obtains from server <NUM> a map comprising the destination point, as well as map data.

Said map is then partitioned by server <NUM> to divide it into two areas:.

The focus zone is determined as an area of a given radius around the destination.

Typically, for an access map for an urban district, the focus zone would correspond to a "walking distance" around the destination (e.g. of a few hundred meters to a few kilometers around said destination). Alternate access maps, may cover locations of interest such as a national park, a historical village, an amusement park, a ski resort, and bike trails. The radius of a focus zone may thus vary depending on the activity and the anticipated mode of transportation a user may experience within a focus zone.

The method hereunder described allows to take account higher level of details in the focus zone.

For the rest of the map, outside of the focus zone, a smaller level of details is needed since the end user would be not be walking, but would be traveling through public transportation, or by car or bike for example.

In the present text, access points are facilities that allow a change of transportation mode, which may be considered waypoints, and which are used for guiding users (e.g., visitors).

For these applications, users travel with various transportation means (e.g., bus, tram, subway, car, bike, pedestrian, plane, waterbus, ferry etc.) and through the corresponding access points (e.g., bus stops, tram stops, subway stops, airports, car parking lots, bike parking lots, ferry landings, etc.).

In these applications, a change of mode of transport can for example be a change from one transportation mode, whether public (subway, train, tram, bus, plane, ferry, etc.), semi-private (e.g., taxi, carpool, etc.), or private (e.g., car, bike, pedestrian, etc.), to another transportation mode.

Applications other than urban district guidance can also be contemplated, such as the generation of access maps in the countryside. In such a case, an access point can be a noticeable place that the end-user can reach, for example by car. The access map provides to the end-user preferred paths to reach the destination points from such access points.

The selection of the access points is performed by server <NUM> and involves:.

An example of an access map generated using the method outlined in <FIG> is illustrated in <FIG>. The access map <NUM> includes the focus zone <NUM>, the destination <NUM>, crossings denoted by letters A to F (e.g., crossing <NUM>), the selected Pols denoted by numbers from <NUM> to <NUM> (e.g., Pol <NUM>), and wherein the access paths are highlighted by black lines (e.g., access path <NUM>).

Steps <NUM> to <NUM> are hereunder further detailed in the case of an urban district access map.

A list of access points is retrieved by server <NUM> within the map data received from server <NUM>.

Two different processes are performed by server <NUM> to determine the access points to be kept for the map for the focus zone and for the rest of the map.

One method performed by server <NUM> for determining the access points 102a to be selected for the focus zone shown in <FIG> is set out in detail in <FIG>:.

Types of access points are defined by the public transportation lines to which they belong.

For example, in merging related access points of the same type, such as two bus stops on the same road, one for each direction, are merged if they would appear close to each other on the visual map; and in merging related access points of different types of transportation, such as a bus stop and a tram stop in the same area, where a connection may be readily made between these two types of transportation, are merged to indicate a connection on the visual map (e.g., similar to a transportation hub).

To this aim, the distance between two or more access points detected by server <NUM> as belonging to the same type or different types of transportation and located on the same road, crossing or area is compared to a threshold distance. The two access points are merged if this distance is less than said threshold.

The threshold distance can for example depend on the actual zoom level of the map.

<NUM>) Evaluating, in step <NUM>, relevancy of access points by computing a quality score for each access point that is a function of the following parameters that may be based on user preferences or learned from user behavior (e.g., using location information, transportation methods, etc.):.

In alternate embodiments, the formula for calculating a relevancy score includes the number of transportation lines and/or the capacity of the lines.

For each type of access point, the selected access point is that with the highest score. Other access points of the same type can be added depending on their score, until a maximum number of selected access points is reached. The maximum number of selected access points can be different from one type to the other and can for example be limited for less relevant types of transportation (car parking for example);
<NUM>) In step <NUM>, adjusting, the focus zone to be displayed to the end-users to correspond with the farthest selected access point, with a margin of <NUM>% for example.

Additional access points may be selected by the server <NUM> outside the focus zone (step 102b). Indeed, users traveling long distances to a destination often go through principal access points that are farther away, like railway stations or airports.

The access map may need to integrate support for users traveling from farther away and through these principal transportation access points to reach and enter the focus zone, the last mile(s) near the destination. In order to select these access points, the method can simply find the closest train stations, airport and highways. However, contrary to access points in the focus zone, these access points are selected mainly just to be represented on the access map but are not used for the determination of access paths, except if they are in the focus zone.

Returning to <FIG>, during step <NUM> all access paths from access points to the destination in the focus zone are calculated.

This can be done through a classical trip planning algorithm, such as Open Source Routing Machine (OSRM) for Open Street Map, implemented on server <NUM>.

When said trip planning algorithm is able to compute more than one access paths from an access point to the destination, and said more than one access paths have equal lengths within a margin, either in terms of distance or in terms of travel time, these multiple access paths can be used all together in the subsequent steps.

These generated access paths serve two purposes:.

The goal of this method is to give Pol information to support future navigation by adding Pol information to crossings along access paths. Thus, the number of Pols across the map must be limited to avoid cluttering it. For this purpose, it is necessary to select which crossings must be clarified on the map as a priority. This is done according to the following steps:.

For each crossing in at least one the access paths, the server <NUM> computes the probability that said crossing is passed through. Considering each path as equally probable, this probability is computed as the number of paths traveling through said crossing divided by the total number of paths considered: <MAT>.

It is also possible to weight these probabilities according to the type of access point from which the access path originates. For instance, end users might come more often by tram and car, and less by bus or bike. Thus, a predefined weight can be assigned to a specific type of access point.

Every crossing has a level of difficulty linked on one hand to its physical configuration and on the other hand to the traversal of the crossing in terms of inbound and outbound roads. To compute a crossing's complexity score, the server <NUM> relies on the following parameters:.

Using these parameters, the server <NUM> computes a crossing complexity for each crossing in at least one access paths as follow: <MAT>.

In the case of public transportation access points, since there is no incoming road, an automatic direction change is considered, so the associated indicator is set to <NUM>. The other parameters are still consistent.

In order to select the most relevant Pols to disambiguate crossing, all the Pols are given a quality score as illustrated in <FIG> in step <NUM> by server <NUM> according to the following procedure for each crossing with a non-zero probability:.

From the list of Pols obtained the desired number of Pols can then be selected. This number is a parameter set by default or by the user. Since the main goal is to clarify the access map, it can also depend of the size of the focus zone area, as a density parameter. Since a crossing may have multiple complexity scores and associated Pols with different quality scores according to traversal configuration (in/out path), the method considers crossing & traversal association where the probability to go through a transversal is the crossing probability divided by the number of transversals.

The selection of Pols is done in step <NUM> by iterating over the following steps as illustrated in <FIG>, where the list of remaining crossing is initially the list of all crossings passed through in at least one access path, and the candidate list is the list of Pols:.

These steps are repeated until the desired number of selected Pol is reached at test <NUM>.

This procedure limits the number of Pols per crossing to one; it is also possible to adjust this choice to multiple Pols per crossing. In this case, it is possible to maintain a crossing in the candidate list if the number of Pol for this crossing is not reached and possibly reduce the crossing complexity.

Additionally, some exceptional Pols can be added to the access map, these are particular Pols well known at the scale of the considered region and that are particularly visible. Such an exceptional Pol can be for example the Eiffel Tower in the city of Paris. When one of these Pols is present in a particular region it is always included in the map, whether it belongs to an access path or not, as it allows the user to orient himself.

Claim 1:
A method, using a data processor, to generate an access map for reaching, independent of origin, a travel destination (<NUM>), said method comprising the following steps:
a) Selecting (<NUM>), within a focus zone (<NUM>) identifying an area around the travel destination, a set of access points, where access points are facilities that allow a change of transportation mode;
b) Computing (<NUM>) access paths (<NUM>) to the travel destination (<NUM>) from one or more access points in the set of selected access points;
c) Listing crossings (<NUM>) that at least one of the computed access paths pass through;
d) For each listed crossing:
i/ evaluating (<NUM>) the probability that the listed crossing is passed through by an access path and calculating at least one complexity score evaluating a complexity of the listed crossing;
ii/ determining (<NUM>) a set of Points of Interest, Pols (<NUM>), along the roads passing through the listed crossing and calculating a quality score for each Pol in the set of Pols, the quality score of a Pol in the set of Pols evaluating a relevancy of the Pol to facilitate orientation;
iii/ selecting the most relevant (<NUM>) Pols from the set of Pols based on their quality scores;
e) Generating (<NUM>) the access map including the access paths and the selected Pols;
f) Outputting (<NUM>) the generated access map.