US-12618683-B2 - Methods and systems for determining safe return range

US12618683B2US 12618683 B2US12618683 B2US 12618683B2US-12618683-B2

Abstract

A method is disclosed for determining and displaying an area comprising a plurality of locations that can be reached by a person or vehicle from a departure node or current position while still reaching a destination node or home location given the initial value at the departure node or current position of a parameter that constrains the distance travelable by the person or vehicle. The method may be implemented on a mobile device such as a portable navigation device and/or on a server or computer, or may be provided as a computer program product.

Inventors

Johannes Robert Fischer
Felix Godafoss König
Pawel Karol Pszona

Assignees

TOMTOM NAVIGATION B.V.

Dates

Publication Date: 20260505
Application Date: 20230926
Priority Date: 20160511

Claims (20)

1 . A method, comprising: determining a first boundary enclosing a portion of a geographic area containing a navigable network representing an area that is reachable from a first location on the navigable network while still allowing a second location on the navigable network to be reached given a value of a parameter that limits the amount of the navigable network that can be traversed, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable elements of the navigable network, and the determining including: determining a position on a segment representative of the first location and obtaining the value of the parameter at said determined position; exploring the segments of the electronic map from the determined position representative of the first location using a search algorithm having an associated cost function; for segments that are explored and determined to be reachable, determining if the segment lies within a second boundary selected from a plurality of second boundaries based on the value of the parameter associated with the segment, wherein a segment is reachable if it is associated with a value of the parameter due to traversing an optimum cost route from the determined position representative of the first location that is less than the obtained value of the parameter, and wherein each of the plurality of second boundaries is associated with a different value of the parameter and encloses a portion of the geographic area around the second location representing an area from which the second location can be reached given the associated value of the parameter; and using the segments determined to be within the second boundary to determine the first boundary; displaying, on the electronic map, a representation of the first boundary which may be travelled within when travelling between the first location and the second location while still reaching the second location and navigating a vehicle to move from the first location to the second location based on the first boundary.
2 . The method of claim 1 , wherein the first location is a current location of a user or mobile device.
3 . The method of claim 1 , wherein the second location is a predetermined location.
4 . The method of claim 3 , wherein the predetermined location is a home location.
5 . The method of claim 1 , further comprising: receiving a selection of a selected location; and setting the selected location as the second location.
6 . The method of claim 1 , wherein: data indicative of the plurality of second boundaries is stored in a memory; and the method further comprises accessing the data indicative of the plurality of second boundaries in the memory to retrieve data indicative of the second boundary.
7 . The method of claim 1 , further comprising: determining the plurality of second boundaries, wherein the determination of a second boundary for a predetermined value of the parameter comprises: determining a position on a segment representative of the second location; and exploring the segments of the electronic map from the determined position using a search algorithm having an associated cost function, and, for segments that are explored, determining if the position representative of the second location is reachable from the segment given the predetermined value of the parameter.
8 . The method of claim 1 , further comprising at least one of: displaying, on a display, information representative of at least some of the first boundary or the area enclosed thereby; and transmitting, to a device for display thereon, information representative of at least some of the first boundary or the area enclosed thereby.
9 . The method of claim 1 , further comprising: determining a third boundary enclosing a portion of the geographic area around the first location, the third boundary representing an area that is reachable from the first location given the obtained value of the parameter at the first location.
10 . The method of claim 9 , further comprising at least one of: displaying, on a display, information representative of at least some of the third boundary or the area enclosed thereby; and transmitting, to a device for display thereon, information representative of at least some of the third boundary or the area enclosed thereby.
11 . A system, comprising: at least one processor configured to: determine a first boundary enclosing a portion of a geographic area containing a navigable network representing an area that is reachable from a first location on the navigable network while still allowing a second location on the navigable network to be reached given a value of a parameter that limits the amount of the navigable network that can be traversed, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable elements of the navigable network, and the determining including: determining a position on a segment representative of the first location and obtain the value of the parameter at said determined position; exploring the segments of the electronic map from the determined position representative of the first location using a search algorithm having an associated cost function; for segments that are explored and determined to be reachable, determining if the segment lies within a second boundary selected from a plurality of second boundaries based on the value of the parameter associated with the segment, wherein a segment is reachable if it is associated with a value of the parameter due to traversing an optimum cost route from the determined position representative of the first location that is less than the obtained value of the parameter, and wherein each of the plurality of second boundaries is associated with a different value of the parameter and encloses a portion of the geographic area around the second location representing an area from which the second location can be reached given the associated value of the parameter; and using the segments determined to be within the second boundary to determine the first boundary; displaying, on the electronic map, a representation of the first boundary which may be travelled within when travelling between the first location and the second location while still reaching the second location and navigating a vehicle to move from the first location to the second location based on the first boundary.
12 . The system of claim 11 , wherein the first location is a current location of a user or mobile device.
13 . The system of claim 11 , wherein the second location is a predetermined location.
14 . The system of claim 11 , wherein the at least one processor is further configured to: receive a selection of a selected location; and set the selected location as the second location.
15 . The system of claim 11 , wherein: data indicative of the plurality of second boundaries is stored in a memory; and the at least one processor is further configured to access the data indicative of the plurality of second boundaries in the memory to retrieve data indicative of the second boundary.
16 . The system of claim 11 , wherein the at least one processor is further configured to: determine the plurality of second boundaries, wherein the determination of a second boundary for a predetermined value of the parameter comprises: determining a position on a segment representative of the second location; and exploring the segments of the electronic map from the determined position using a search algorithm having an associated cost function, and, for segments that are explored, determining if the position representative of the second location is reachable from the segment given the predetermined value of the parameter.
17 . The system of claim 11 , wherein the at least one processor is further configured to: display, on a display, information representative of at least some of the first boundary or the area enclosed thereby; and/or transmit, to a device for display thereon, information representative of at least some of the first boundary or the area enclosed thereby.
18 . The system of claim 11 , wherein the at least one processor is further configured to: determine a third boundary enclosing a portion of the geographic area around the first location, the third boundary representing an area that is reachable from the first location given the obtained value of the parameter at the first location.
19 . The system of claim 18 , wherein the at least one processor is further configured to: display, on a display, information representative of at least some of the third boundary or the area enclosed thereby; and transmit, to a device for display thereon, information representative of at least some of the third boundary or the area enclosed thereby.
20 . A non-transitory computer readable storage medium storing instructions that, when executed by at least one processor of a system, cause the system to perform a method comprising: determining a first boundary enclosing a portion of a geographic area containing a navigable network representing an area that is reachable from a first location on the navigable network while still allowing a second location on the navigable network to be reached given a value of a parameter that limits the amount of the navigable network that can be traversed, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable elements of the navigable network, and the determining including: determining a position on a segment representative of the first location and obtaining the value of the parameter at said determined position; exploring the segments of the electronic map from the determined position representative of the first location using a search algorithm having an associated cost function; for segments that are explored and determined to be reachable, determining if the segment lies within a second boundary selected from a plurality of second boundaries based on the value of the parameter associated with the segment, wherein a segment is reachable if it is associated with a value of the parameter due to traversing an optimum cost route from the determined position representative of the first location that is less than the obtained value of the parameter, and wherein each of the plurality of second boundaries is associated with a different value of the parameter and encloses a portion of the geographic area around the second location representing an area from which the second location can be reached given the associated value of the parameter; and using the segments determined to be within the second boundary to determine the first boundary; displaying, on an electronic map, a representation of the first boundary which may be travelled within when travelling between the first location and the second location while still reaching the second location and navigating a vehicle to move from the first location to the second location based on the first boundary.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS The instant application is a continuation application of, and hereby claims priority to, pending U.S. application Ser. No. 16/096,275, which was filed on 24 Oct. 2018. The instant application also claims priority, via parent application Ser. No. 16/096,275, to PCT/EP2017/060623, which was filed on May 4, 2017. The instant application further claims priority, via grandparent application PCT/EP2017/060623, to provisional patent application 62/331,916 filed on May 4, 2016; provisional patent application 62/334,429 filed on May 10, 2016; and United Kingdom patent application 1608233.1 filed on May 11, 2016. The entire content of each of these applications is incorporated herein by reference. FIELD OF THE INVENTION The present invention relates generally to methods for determining an area which may be travelled within when travelling between a departure node and a destination node. The present invention also extends to mobile devices, optionally portable navigation systems, systems and computer program products for implementing such methods. The methods may be computer implemented. Illustrative embodiments of the invention relate to portable navigation devices (so-called PNDs), in particular PNDs that include Global Positioning System (GPS) signal reception and processing functionality. Other embodiments relate, more generally, to any type of mobile processing device that is configured to execute navigation software so as to provide route planning, and preferably also navigation, functionality. BACKGROUND OF THE INVENTION Portable navigation devices (PNDs) that include GPS signal reception and processing functionality are well known and widely employed as in-car or other vehicle navigation systems. In general terms, a modern PND comprises a processor, memory (at least one of volatile and non-volatile, and commonly both), and map data stored within the memory. The processor and memory cooperate to provide an execution environment in which a software operating system may be established, and additionally it is commonplace for one or more additional software programs to be provided to enable the functionality of the PND to be controlled, and to provide various other functions. Typically these devices further comprise one or more input interfaces that allow a user to interact with and control the device, and one or more output interfaces by means of which information may be relayed to the user. Illustrative examples of output interfaces include a visual display and a speaker for audible output. Illustrative examples of input interfaces include one or more physical buttons to control on/off operation or other features of the device (which buttons need not necessarily be on the device itself but could be on a steering wheel if the device is built into a vehicle), and a microphone for detecting user speech. In a particularly preferred arrangement the output interface display may be configured as a touch sensitive display (by means of a touch sensitive overlay or otherwise) to additionally provide an input interface by means of which a user can operate the device by touch. Devices of this type will also often include one or more physical connector interfaces by means of which power and optionally data signals can be transmitted to and received from the device, and optionally one or more wireless transmitters/receivers to allow communication over cellular telecommunications and other signal and data networks, for example Wi-Fi, Wi-Max GSM and the like. PND devices of this type also include a GPS antenna by means of which satellite-broadcast signals, including location data, can be received and subsequently processed to determine a current location of the device. The PND device may also include electronic gyroscopes and accelerometers which produce signals that can be processed to determine the current angular and linear acceleration, and in turn, and in conjunction with location information derived from the GPS signal, velocity and relative displacement of the device and thus the vehicle in which it is mounted. Typically such features are most commonly provided in in-vehicle navigation systems, but may also be provided in PND devices if it is expedient to do so. The utility of such PNDs is manifested primarily in their ability to determine a route between a first location (typically a start or current location) and a second location (typically a destination). These locations can be input by a user of the device, by any of a wide variety of different methods, for example by postcode, street name and house number, previously stored “well known” destinations (such as famous locations, municipal locations (such as sports grounds or swimming baths) or other points of interest), and favourite or recently visited destinations. Typically, the PND is enabled by software for computing a “best” or “optimum” route between the start and destination address locations from the map data. A “best” o