SEVAK ZANKAR UPENDRAKUMAR (GB)
ARSLAN TUGHRUL SATI (GB)
WO2011077166A1 | 2011-06-30 | |||
WO2011077166A1 | 2011-06-30 |
US8634359B2 | 2014-01-21 | |||
US20140243025A1 | 2014-08-28 | |||
US20150119071A1 | 2015-04-30 | |||
US20140243015A1 | 2014-08-28 | |||
US20140365488A1 | 2014-12-11 | |||
US20150189467A1 | 2015-07-02 | |||
US20150195810A1 | 2015-07-09 | |||
US20150172872A1 | 2015-06-18 | |||
US20150309183A1 | 2015-10-29 | |||
US20140379476A1 | 2014-12-25 | |||
US201615014393A | 2016-02-03 | |||
GB2015052799W | 2015-09-25 | |||
GB2015052798W | 2015-09-25 | |||
US20160129908A1 | 2016-05-12 |
THOMAS H.; LEISERSON, CHARLES E.; RIVEST, RONALD L.; STEIN, CLIFFORD: "Introduction to Algorithms (Second ed.).", 2001, MIT PRESS AND MCGRAW-HILL, article "Section 24.3: Dijkstra's algorithm", pages: 595 - 601
MICHAEL GUNTHER ET AL.: "Int'l Workshop on Dynamic Aspects in Dependability Models for Fault-Tolerant Systems (DYADEM-FTS)", 2010, ACM PRESS, article "Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA", pages: 13 - 18
Claims 1. A method of maintaining a database of positioning data, the positioning data specifying location data concerning each of a plurality of electromagnetic signal sources or signals from electromagnetic signal sources, the method comprising determining that a mobile device is travelling along a path, the mobile device comprising at least one detector for signals from the electromagnetic signal sources, the method comprising detecting a plurality of electromagnetic signal sources at a plurality of locations along the path and storing parameters indicative of the variation in the strength of signals from the electromagnetic signal sources along the path and/or adjacent the path. 2. A method of maintaining a database of positioning data, the positioning data specifying location data concerning each of a plurality of electromagnetic signal sources or signals from electromagnetic signal sources, the method comprising determining that a mobile device is travelling along a path, the mobile device comprising at least one detector for signals from the electromagnetic signal sources, the method comprising detecting a plurality of electromagnetic signal sources and determining on which side of the path of the mobile device each of the electromagnetic signal sources are located. 3. A method of maintaining a database of positioning data, the positioning data specifying location data concerning each of a plurality of electromagnetic signal sources or signals from electromagnetic signal sources, the method comprising determining that a mobile device is travelling along a path, the mobile device comprising at least one detector for signals from the electromagnetic signal sources, the method comprising detecting a plurality of electromagnetic signal sources at a plurality of locations along the path and storing parameters indicative of the variation in the strength of signals from the electromagnetic signal sources along the path and/or adjacent the path, determining on which side of the path of the mobile device each of the electromagnetic signal sources are located and processing pre-existing estimates of the location of the electromagnetic signal sources or the strength of signals from the electromagnetic signal sources at locations, and the determined side of the path of the mobile device on which each electromagnetic signal source is located, to generate or improve estimates of the position of the electromagnetic signal sources. 4. A method of maintaining a database of positioning data, the positioning data specifying location data concerning each of a plurality of electromagnetic signal sources or signals from electromagnetic signal sources, the method comprising determining that a mobile device is travelling along a path, the mobile device comprising at least one detector for signals from the electromagnetic signal sources, the method comprising detecting a plurality of electromagnetic signal sources at a plurality of locations along the path and processing estimates of the location of each of the plurality of electromagnetic signal source and measurements by the detector of signals from the electromagnetic signal sources to improve estimates of the location of each of the plurality of electromagnetic signal sources. 5. A method according to any one preceding claim, wherein the mobile device is, or is located within, a vehicle and the path is a road or a roadway or lane of a road. 6. A method according to any one preceding claim, comprising estimating the position, in two or three dimensions, of an electromagnetic signal source which is detected at a plurality of locations along the path, taking into account path data which specifies the path. 7. A method according to any one preceding claim, wherein the mobile device is, or is located in, a vehicle and the path is the path of a road, or roadway or a lane thereof and the method comprise the step of determining on which road, or roadway or lane thereof, the mobile device, or the vehicle in which it is located, is travelling. 8 A method according to any one preceding claim, comprising estimating the position of the mobile device, querying geographical data specifying the path of a plurality of roads, roadways or lanes thereof, and thereby determining which road, roadway or lane thereof the path of the mobile device is following. 9. A method according to claim 8, further comprising determining the direction of movement of the mobile device along the road, roadway or lane thereof. 10. A method according to any one preceding claim, comprising the step of estimating the speed of movement of the mobile device along the path. 1 1. A method according to any one preceding claim, comprising the step of estimating the position of the mobile device using a global navigation satellite system receiver of the mobile device before and after the path of the mobile device passes through an underground region where measurements of position using the global navigation satellite system receiver are of low accuracy or not available. 12. A method according to any one preceding claim, comprising estimating whether each electromagnetic signal source is indoors or outdoors and storing that estimate. 13. A method according to any one preceding claim, comprising estimating whether each electromagnetic signal source is or is not located between a road facing wall of a building and the road, or estimating whether each electromagnetic signal source is located on or above a sidewalk. 14. A method according to any one preceding claim, wherein the path is the path of a road, roadway or lane thereof, the method further comprising determining a location for a pick up of a user by a passenger vehicle, the user having a mobile electronic device having an electromagnetic signal receiver, the method comprising detecting electromagnetic signals from an electromagnetic signal source at the electromagnetic signal receiver, determining on which side of the road or roadway the mobile electronic device is currently located and determining a location for a pick up of a user by a passenger vehicle on the respective side of the road or roadway. 15. A method according to claim 14, further comprising the step of calculating a route for the passenger vehicle to follow to pick up the user at the pick up location, which route takes into account the determined side of the road or roadway. 16. A method according to any one preceding claim further comprising the step of selecting a passenger vehicle to pick up a user from amongst a plurality of passenger vehicles, comprising calculating a route for each of the plurality of passenger vehicles to follow to pick up the user at their current location, which route takes into account the estimate of whether the current position of the mobile user device is on the first or second side of the road, or the side of road of the estimated geographical location of the current position of the mobile user device, and selecting the passenger vehicle for which the calculated route is shortest to pick up the user. |
- A measure of the accuracy of the estimates of the position of the vehicle, which is also output by typical GNSS receivers
- Measurements of signals received from radio beacons from both sensors 152 and 154, for example their MAC code or other identifier (which is typically broadcast by radio beacons) and the strength of signals received from the radio beacons.
- Measurements of acceleration of the vehicle from the accelerometer
- Measurements of the orientation of the vehicle from the magnetometer - Measurement of the orientation or changes in orientation of the vehicle from the gyroscope. In some embodiments estimates of the position are also derived from the measurement of signals received from radio beacons, with reference to positioning data specifying the location of those radio beacons, where available. The received estimates of the position of the vehicle are used to query the database of route data and therefore to determine 52 that the vehicle is on a specific road and heading in a specific direction. Where there is sufficient data available, it may be determined that the vehicle is in a specific roadway or even a specific lane. Thus, the path along which the vehicle is moving can be determined as the path of that road, roadway or lane. The measurement data is analysed at different time steps to estimate 54 the progress of the vehicle along the path formed by the road, roadway or lane. Position estimates from the GNSS module and acceleration data from the accelerometer are especially useful to determine where the vehicle is along the path at a given time. Data from the first and second radio receivers (152, 154) (or a directional radio receiver) is used to determine on which side of the road individual signal sources are located. This is stored in the database of positioning data. Still further, measurements of the strength of signals from individual signal sources are stored as the vehicle progresses along the path. These measurements are stored, typically separated by side of the road. They are typically stored with reference to the path. This data is useful for later estimates of position to estimate the position of mobile user devices which later detect the signal sources, and to facilitate further or improved estimates of the position of the signal sources by estimating the position of mobile user device which later detect the signal sources and processing the strength of the detected signals to generate further or improved estimates of the position of the signal sources. In some embodiments, that data which is stored takes the form of parameters of equations (e.g polynomials or wavelets) which best fit the measurements of the strengths of the signals along the path. These can be stored with reference to the path to later estimate the location along the path of mobile user devices which detect signals from the same signal sources. Furthermore, it is estimated 58 whether individual radio beacons are indoors or outdoors from the variation in the strength of signals from those radio beacons along the path of the vehicle. Signals from radio beacons which are indoors will be more attenuated and may vary in a way which is significantly different from the attenuation of radio signals in air. However, radio beacons which are outdoors, on surfaces facing the road, will typically be detectable from a relatively wide range of orientations and the strength of signals from them will typically vary along the path of travel in a way which is consistent with the typical attenuation of radio signals in air. Where it can be determined that a radio beacon is Iocated on or above a sidewalk, from the distribution of signals around the radio beacon, it may also be stored in the database of positioning data that the radio beacon is Iocated on a sidewalk. Estimates are typically also made of the position of the radio beacons 62, using triangulation given estimates of the distance to the respective radio beacons at different points along the path and this may also be stored in the database of positioning data or used to improve estimates of the position of the respective radio beacons. In a further example shown in Figure 5, the path of a vehicle is along a lane of a road which extends through a tunnel 198 (which has a sidewalk within the tunnel on one side but not the other). This means that the estimates of the position of the vehicle by the GNSS receiver Iocated in the vehicle (integral to the vehicle or in a mobile user device Iocated within the vehicle) are not available for part of the path. Nevertheless, it remains possible to estimate the side of the road of the radio beacons within the tunnel using the path of the road. It is also possible to estimate the path of the vehicle (where reliable GNSS signals are not available) by making measurements of the position of the vehicle where available and using measurements form the sensors on the vehicle, notably the accelerometer and magnetometer and/or gyroscope, to infer the path of the vehicle between a location before the tunnel or other region where an accurate estimate of the position of the vehicle using a GNSS receiver is not available to another location after that region. Indeed, as vehicles generally change course only gradually their path can usually be estimated relatively accurately by this method and this can provide a good basis for measuring the position of signal sources located in regions where GNSS measurements of position are not available or are of poor accuracy. As well as covered regions, this may apply in built up areas, for example between high buildings. As the side of the road on which individual electromagnetic signal sources are located has been identified, it is possible to estimate on which side of a road a mobile user device (and therefore a user) is located by using a radio receiver (or other electromagnetic signal detector) of the mobile user device to detect signal sources. It is then assumed that the user is located on the side of the road of the signal source which is closest to the mobile user device. The closest signal source may be determined as the signal source from which the strongest signal is received, or from which the least attenuated signal is received (which requires knowledge of the transmit power of the signal source) or in some embodiments, which is determined to be closest from round trip time calculations or other signal timing based distance measurement techniques. It is helpful to determine on which side of a road a mobile user device (and therefore a user) is located for a number reasons. Firstly, this can assist with estimating the location of the user as it would be unusual for a user to be standing in a roadway. Secondly, the side of the road on which the mobile user device (and therefore the user) is located is used to route a passenger vehicle to the user. The passenger vehicle may be a taxi (with a human driver) or autonomous vehicle, which may be directed to pick up the user on the side of the road on which they are currently located. It is helpful to determine the correct side of the road for a user to be picked up because this can avoid a requirement for the vehicle to make a turn in the road, or the user to cross the road, and can enable the vehicle to be more efficiently routed to the user. Figure 5 is a schematic diagram of a road network, comprising a plurality of two way roads 200A through 200F, which join at various intersections 250A through 250D. Assuming that this represents a country in which vehicles drive on the right hand side of the road (in the direction of travel), If a user is found to be on the side of the road 200B shown with the letter A when they request a pick up by a vehicle 150, it would be best for the vehicle to turn right at junction 250D and left at junction 250B to be on the correct side of the road to pick up the user. If however the user is found to be on the side of the road 200B shown with the letter A when they request a pick up by a vehicle, it would be best for the vehicle to turn left at junction 250D and right at junction 250A, to be on the correct side of the road to pick up a user. Thus, a vehicle can be routed to the user for a pick up in dependence on the determined side of the road. In order to enable routing, the road network of Figure 5 can be represented in electronic form in a graph data structure shown in Figure 6, with nodes 300A through 300G, coinciding with junctions and bends, and data specifying which nodes are connected with roadways 302 and in which directions traffic may pass (e.g. a single direction 302, or bidirectional 304). More sophisticated data structures representing road networks, known in the art, include data concerning the path of individual roadways and lanes, the speed limit of road sections between nodes, measured average, current or predicted speeds of traffic on road sections between nodes, the location of speed cameras, traffic lights and so forth. Routing can be carried out by executing known algorithms for finding paths through graphs, for example Dijkstra's algorithm (Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik 1 : 269-271., and Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. pp. 595-601 , each of which is incorporated herein by virtue of this reference) or the Bellman Ford algorithm, or (to obtain multiple options), the K shortest path routing algorithm (Michael Gunther et al.: "Symbolic calculation of K- shortest paths and related measures with the stochastic process algebra tool CASPA". In: Int'l Workshop on Dynamic Aspects in Dependability Models for Fault- Tolerant Systems (DYADEM-FTS), ACM Press (2010) 13-18, incorporated herein by virtue of this reference). Once a pick up has been requested, a passenger vehicle is allocated to make the pick up (or predetermined, for example if a specific passenger vehicle is allocated to or property of the user), a route for the passenger vehicle to travel to the user to make a pick up on the appropriate side of the road is calculated, and the route is transmitted to the passenger vehicle to enable the vehicle to pick up the user. The position of the passenger vehicle may also be transmitted to a mobile electronic device of the user, for example along with map data, to enable the user to view the approach of the passenger vehicle. The position of the user and in particular their side of the road may be updated and the route changed dynamically while the passenger vehicle is travelling to make a pick up. The estimate of the side of the road on which the mobile user device (and so the user) is located may also be used to select a passenger vehicle from amongst a plurality of passenger vehicles to direct to pick up the user. A vehicle which is closest to the user, or even closest to the centre of the road adjacent the user, may not be the vehicle which can most quickly pick up the user at side of the road on which they are located. In order to implement this, a plurality of vehicles in a region around the current position of the user are identified and estimates are made of the time (or in some embodiments distance) which would be required for the vehicle to travel to a user to pick up the user at the estimated side of the road of their current location. The vehicle which would require the shortest time (or distance) to travel to pick up the user at the respective side of the road is selected to pick up the user and directed to pick them up at their current location on the respective side of the road. Estimates of the position of electromagnetic signal sources obtained by the methods above may be used to later estimate the position of mobile user devices with electromagnetic (typically radio) receivers to detect the signal sources, and these estimates of the position of mobile user devices can be used to improve estimates of the position of the electromagnetic signal sources and/or newly detected electromagnetic signal sources, for example as set out in WO 201 1/0771666 (Arslan et al.) Further, the measurements which are made as a passenger vehicle proceeds along a path are useful to estimate the location of signal sources where there is already data available in the form of existing estimates of the location of those signal sources (e.g. of relatively poor quality) or other stored measurements of signals from the signal sources made by mobile user devices which have already detected those signal sources. For example, it may be that there are regions in which existing estimates of the position of signal sources are of low accuracy and/or contain large systematic errors. However, by determining that a vehicle is proceeding along a path and that signal sources are located to the right or the left of the vehicle as it proceeds along the path, this enables estimates of the position of these signal sources to be corrected to better fit the additional data. Furthermore, it can be assumed that a vehicle will proceed along the path at a constant or smoothly changing speed. Accordingly, by measuring this speed or change of speed using periodic measurements of the speed of the vehicle (and/or accelerometer data) it is possible to accurately estimate the distance between the locations where the vehicle was located when measurements that are spaced apart in time (e.g. in a time series ever 1 , 5 or 10 seconds etc.) This provides an additional constraint enabling improvements in the estimates of the relative spacing between and therefore the position of the electromagnetic signal sources which are detected from the vehicle. As the invention facilitates the estimation of the position of electromagnetic signal sources adjacent a road it also facilitates the estimation of the path of lanes in a road, or roadway (or boundaries therebetween), and the path of centre line or a road or roadway. This can be carried out by estimating the position of subsequent vehicles travelling along a road using measurements of the strength of signals from the signal sources identified in the steps set out above, and the estimates of the position of those signal sources, to determine the paths along which vehicles move in particular directions, and to use this data to determine boundaries between lanes and roadways and also to estimate the position of the centre line of a road or roadway. An estimate of the path of the centre line of a road or roadway can also be obtained by fitting a curve through the estimated positions of electromagnetic signal sources which have been found to be on either side of the road.