How to use trams to make it easier for a taxi driver to find you
Continuing the discussion around the article on the method of improving the positioning accuracy developed in Uber, I would like to share about the research conducted in my small company and talk about the technology with which we are trying to solve a similar problem. Immediately, I note that there will not be any mathematical calculations and deep technical details, I will try to make all explanations possible in the most accessible language. If it became interesting to know, and where the actual trams are here, then I ask for a cat.
So, I think no one will have problems imagining that we are all surrounded by an uncountable set of mobile devices - smartphones, tablet computers, GPS trackers, car navigators and even on-board computers in cars. Usually in
such devices are built-in receivers of global satellite navigation systems (GPS, GLONASS, Baidu). These receivers are quite low-cost and, unlike expensive professional equipment, do not support work in a differential mode, in which they could accept a correction correction and thus determine the location of the device with centimeter accuracy. The accuracy of determining the coordinates, unfortunately, leaves much to be desired.
But before we get to the essence of our technology, let us remind ourselves of the causes of errors in positioning. In reality, many factors affect the accuracy of determining the coordinates of a device. However, all sources of calculation errors can be divided into the following groups according to their origin:
And now, please pay attention to the key point, which is in its essence the theoretical justification of the method described below - the first three groups of sources of errors are common (that is, correlated) for devices that are at the same time at a relatively close distance from each other. Only errors associated with internal device noise and multipath signal propagation are individual. By the way, this idea underlies the work of differential subsystems. In the areas of the so-called space-time error correlation, the error parameters calculated at an arbitrary point can be used during the correlation time to correct measurements at other points in the area.
')
To make it clearer what is a single space-time domain, and what is not, I will give examples. Consumers that are simultaneously in Moscow on Leningradsky Avenue and Enthusiasts Highway will be located in such a single area - the navigation field, that is, the composition and location of satellites in the sky, and the state of the ionosphere and the troposphere above them will be approximately the same less distance to satellites and sizes of irregularities in the ionosphere. In turn, consumers from Moscow and Kazan will be located in different space-time areas, as positioning errors will depend on different sections of the troposphere and ionosphere. And even if you are in the same place, but you take measurements with a time interval of 1 or 2 hours, your measurements will correspond to different areas, because during this time there are changes not only in the ionosphere and troposphere, but the navigation field itself changes. I note that for different variants of the differential subsystems, the typical spatial dimensions of such areas range from a few to hundreds of kilometers.
After a brief review of the theoretical justification of the method, we proceed to the description of the hypothesis, as to how a set of “simple” devices located in a single space-time domain can help improve the accuracy of positioning of each of them.
Let's take two trams (let it be, conditionally, 43 and 56 routes) with satellite navigation systems receivers installed on them. Let tram 43 at this moment of time move from south to north, and tram 56 from west to east. At the same time or with some small time difference comes the mark with the coordinates of the current location of the trams. But, since the differential subsystems in their devices are not used, the determination accuracy is not high enough for accurate positioning - marks, most likely, in both cases will be located outside the tram rails.
But we know that the receivers are on trams, the physical position of which is imposed on the real position in space. In fact, the variability of the position of trams is determined by the location of the rails - the actual position of the tram on route 43 is located to the west of the mark with observation, and tram 56, in turn, to the south. Now let us imagine a lucky coincidence that in the procedure for calculating the location in both cases the same navigation satellites were used (the so-called working constellation). And for simplicity, we assume that the accuracy of the determination was the same - the radii of the depicted circles are the same. Let's mentally combine these circles into one and find a virtual point at the intersection of two paths. It is this point that will be a potential candidate for the role of the required one - the correction vectors from the observation points to the actual position of the trams in this case will be the same.
By applying this correction vector to the marks, we can easily calculate the position of both trams with greater accuracy relative to the original one. Of course, the measurement errors associated with the reflection of radio signals or the error of the receivers will remain.
And now let's take not two trams, but tens, hundreds of thousands and even millions. And not just trams, but all kinds of vehicles, traveling on our roads with navigators and ERA-GLONASS devices on board. And here is the next thought that I would like to convey this: a car on the road is a 95% tram. In the sense that all cars in the aggregate do not move along the roads randomly. If you look closely at the flow of cars on a straight stretch of road, you will notice that most of the time they drive along lanes, as if attached to invisible rails. Rebuilds, overtakings and other maneuvers take up only a small fraction of the time. In addition, unlike a pedestrian, the real location of a motor vehicle is limited to a relatively small area of ​​space — by carriageways, the total area of ​​which in large cities does not exceed 1–5% of the total area. A car moving at a speed of more than 20-30 kilometers per hour cannot suddenly find itself out of the roadway (on the sidewalk, lawn or in an open field, etc.) and continue its movement there with the same or higher speed. And on the road with a separation fence, the probability of going into the oncoming lane is dismissively small.
Thus, it can be assumed that the coordinates of motor vehicles recorded outside the “permitted” areas recorded with the use of satellite navigation systems, that is, contrary to the existing road infrastructure elements, are a good information signal in the calculation of the correction correcting these measurements towards the real location of objects. In this case, not all observations will be useful. For example, a mark from a car moving in the middle lane along the Moscow Ring Road carries very little information, since all potential points within a radius of 5-6 meters are quite acceptable (the car can actually go to neighboring lanes or be rearranged). On the other hand, a mark from a car on a single lane forest road will give much more information.
You can more clearly understand the essence of the method with the help of an ordinary large-scale paper map and transparent paper. Mentally place the transparent sheet on the map and mark the marks from the vehicles so that they correspond to the observations obtained. The more marks the better. Then it is necessary to move the transparent left-right and up-down to different offset values ​​so that the maximum number of points falls into “their” sections of the road (not on the opposite lane, on the side, etc.). Solving the optimization problem in this way, we find the most likely real location of these cars, simultaneously identifying potential violators from among those whose marks after such painstaking work fell into the “forbidden” areas for them.
This is the essence of our method - using computer calculations, without using additional expensive equipment, analyze a large number of observations from one space-time region, select a piece of necessary information from each observation, compare the mark with the "map" and calculate the total correctional correction that can be used for all devices in a given area.
In order to calculate the general correctional corrections, it is necessary to use the most detailed digital marking of the largest possible number of sections of the road network, with the help of which one can more accurately localize the real situation of consumers. And not only the drivers of the vehicles themselves, but also the “horseless” pedestrians, including, of course, potential taxi customers. Pedestrian devices, of course, should be excluded from the analysis and calculation of correctional corrections, but the calculated corrections can be applied to them on an equal footing with motorists.
And what is the digital markup? We ourselves define it as a mathematical model that describes the actual location of some elements of the road infrastructure in space with the accuracy necessary and sufficient for solving various kinds of navigation problems. Such elements of road infrastructure include curbs, dividing lanes, road markings, tram rails, etc. In simple terms, the digital marking should, according to the coordinates (latitude and longitude), indicate what this point corresponds to and how far it is from other road elements. For example, how close is the point to the curb, if it does not belong to the oncoming lane or pedestrian pavement, etc.
It seems that the more accurately you can create a digital markup, the more accurately you can make predictions. Unfortunately, creating accurate digital markup is an extremely difficult and expensive task. However, its presence is important for the development of unmanned vehicles, so its appearance sooner or later, I hope, will become inevitable. As part of the creation of the technology described above, we are studying and exploring approaches based on the same principles of cooperativity of observations and aimed at solving this problem, but this is a slightly different story ...
So, I think no one will have problems imagining that we are all surrounded by an uncountable set of mobile devices - smartphones, tablet computers, GPS trackers, car navigators and even on-board computers in cars. Usually in
such devices are built-in receivers of global satellite navigation systems (GPS, GLONASS, Baidu). These receivers are quite low-cost and, unlike expensive professional equipment, do not support work in a differential mode, in which they could accept a correction correction and thus determine the location of the device with centimeter accuracy. The accuracy of determining the coordinates, unfortunately, leaves much to be desired.
But before we get to the essence of our technology, let us remind ourselves of the causes of errors in positioning. In reality, many factors affect the accuracy of determining the coordinates of a device. However, all sources of calculation errors can be divided into the following groups according to their origin:
- Brought by a control and measuring complex. These include errors due to a slight discrepancy between the time scales of navigation satellites and errors caused by the inaccuracy of the calculation of their locations relative to real orbits at the time of emission of a radio signal to all consumers.
- Introduced by the equipment of the navigation satellites themselves .
- Emerging on the path of radio signals . The main source here is the refraction of radio signals in the Earth’s troposphere and ionosphere, due to the inhomogeneities existing in them, which introduce additional signal propagation delays.
- Brought by the consumer receiver (internal "noise" of the device).
- Multipath propagation of the signal (reflection from the surface of the Earth and surrounding buildings).
And now, please pay attention to the key point, which is in its essence the theoretical justification of the method described below - the first three groups of sources of errors are common (that is, correlated) for devices that are at the same time at a relatively close distance from each other. Only errors associated with internal device noise and multipath signal propagation are individual. By the way, this idea underlies the work of differential subsystems. In the areas of the so-called space-time error correlation, the error parameters calculated at an arbitrary point can be used during the correlation time to correct measurements at other points in the area.
')
To make it clearer what is a single space-time domain, and what is not, I will give examples. Consumers that are simultaneously in Moscow on Leningradsky Avenue and Enthusiasts Highway will be located in such a single area - the navigation field, that is, the composition and location of satellites in the sky, and the state of the ionosphere and the troposphere above them will be approximately the same less distance to satellites and sizes of irregularities in the ionosphere. In turn, consumers from Moscow and Kazan will be located in different space-time areas, as positioning errors will depend on different sections of the troposphere and ionosphere. And even if you are in the same place, but you take measurements with a time interval of 1 or 2 hours, your measurements will correspond to different areas, because during this time there are changes not only in the ionosphere and troposphere, but the navigation field itself changes. I note that for different variants of the differential subsystems, the typical spatial dimensions of such areas range from a few to hundreds of kilometers.
After a brief review of the theoretical justification of the method, we proceed to the description of the hypothesis, as to how a set of “simple” devices located in a single space-time domain can help improve the accuracy of positioning of each of them.
Let's take two trams (let it be, conditionally, 43 and 56 routes) with satellite navigation systems receivers installed on them. Let tram 43 at this moment of time move from south to north, and tram 56 from west to east. At the same time or with some small time difference comes the mark with the coordinates of the current location of the trams. But, since the differential subsystems in their devices are not used, the determination accuracy is not high enough for accurate positioning - marks, most likely, in both cases will be located outside the tram rails.
But we know that the receivers are on trams, the physical position of which is imposed on the real position in space. In fact, the variability of the position of trams is determined by the location of the rails - the actual position of the tram on route 43 is located to the west of the mark with observation, and tram 56, in turn, to the south. Now let us imagine a lucky coincidence that in the procedure for calculating the location in both cases the same navigation satellites were used (the so-called working constellation). And for simplicity, we assume that the accuracy of the determination was the same - the radii of the depicted circles are the same. Let's mentally combine these circles into one and find a virtual point at the intersection of two paths. It is this point that will be a potential candidate for the role of the required one - the correction vectors from the observation points to the actual position of the trams in this case will be the same.
By applying this correction vector to the marks, we can easily calculate the position of both trams with greater accuracy relative to the original one. Of course, the measurement errors associated with the reflection of radio signals or the error of the receivers will remain.
And now let's take not two trams, but tens, hundreds of thousands and even millions. And not just trams, but all kinds of vehicles, traveling on our roads with navigators and ERA-GLONASS devices on board. And here is the next thought that I would like to convey this: a car on the road is a 95% tram. In the sense that all cars in the aggregate do not move along the roads randomly. If you look closely at the flow of cars on a straight stretch of road, you will notice that most of the time they drive along lanes, as if attached to invisible rails. Rebuilds, overtakings and other maneuvers take up only a small fraction of the time. In addition, unlike a pedestrian, the real location of a motor vehicle is limited to a relatively small area of ​​space — by carriageways, the total area of ​​which in large cities does not exceed 1–5% of the total area. A car moving at a speed of more than 20-30 kilometers per hour cannot suddenly find itself out of the roadway (on the sidewalk, lawn or in an open field, etc.) and continue its movement there with the same or higher speed. And on the road with a separation fence, the probability of going into the oncoming lane is dismissively small.
Thus, it can be assumed that the coordinates of motor vehicles recorded outside the “permitted” areas recorded with the use of satellite navigation systems, that is, contrary to the existing road infrastructure elements, are a good information signal in the calculation of the correction correcting these measurements towards the real location of objects. In this case, not all observations will be useful. For example, a mark from a car moving in the middle lane along the Moscow Ring Road carries very little information, since all potential points within a radius of 5-6 meters are quite acceptable (the car can actually go to neighboring lanes or be rearranged). On the other hand, a mark from a car on a single lane forest road will give much more information.
You can more clearly understand the essence of the method with the help of an ordinary large-scale paper map and transparent paper. Mentally place the transparent sheet on the map and mark the marks from the vehicles so that they correspond to the observations obtained. The more marks the better. Then it is necessary to move the transparent left-right and up-down to different offset values ​​so that the maximum number of points falls into “their” sections of the road (not on the opposite lane, on the side, etc.). Solving the optimization problem in this way, we find the most likely real location of these cars, simultaneously identifying potential violators from among those whose marks after such painstaking work fell into the “forbidden” areas for them.
This is the essence of our method - using computer calculations, without using additional expensive equipment, analyze a large number of observations from one space-time region, select a piece of necessary information from each observation, compare the mark with the "map" and calculate the total correctional correction that can be used for all devices in a given area.
In order to calculate the general correctional corrections, it is necessary to use the most detailed digital marking of the largest possible number of sections of the road network, with the help of which one can more accurately localize the real situation of consumers. And not only the drivers of the vehicles themselves, but also the “horseless” pedestrians, including, of course, potential taxi customers. Pedestrian devices, of course, should be excluded from the analysis and calculation of correctional corrections, but the calculated corrections can be applied to them on an equal footing with motorists.
And what is the digital markup? We ourselves define it as a mathematical model that describes the actual location of some elements of the road infrastructure in space with the accuracy necessary and sufficient for solving various kinds of navigation problems. Such elements of road infrastructure include curbs, dividing lanes, road markings, tram rails, etc. In simple terms, the digital marking should, according to the coordinates (latitude and longitude), indicate what this point corresponds to and how far it is from other road elements. For example, how close is the point to the curb, if it does not belong to the oncoming lane or pedestrian pavement, etc.
It seems that the more accurately you can create a digital markup, the more accurately you can make predictions. Unfortunately, creating accurate digital markup is an extremely difficult and expensive task. However, its presence is important for the development of unmanned vehicles, so its appearance sooner or later, I hope, will become inevitable. As part of the creation of the technology described above, we are studying and exploring approaches based on the same principles of cooperativity of observations and aimed at solving this problem, but this is a slightly different story ...
Source: https://habr.com/ru/post/354512/
All Articles