# How to use trams to make it easier for the taxi driver to find you

In the continuation of the discussion around articles on the method of increasing the accuracy of positioning , developed in Uber, I would like to share about the research conducted in my small company and tell about the technology with which we are trying to solve a similar problem. Just note that there will be no mathematical calculations and deep technical details, I will try to make all the explanations as accessible as possible in the language. If it became interesting to know, and where the actual trams, then please under the cut.

So, I think no one will have any problems imagining that we are all surrounded by countless mobile devices - smartphones, tablet computers, GPS-trackers, car navigators and even on-board computers in cars. As a rule, in

Such devices are built-in receivers of global satellite navigation systems (GPS, GLONASS, Baidu). These receivers are quite budgetary and, unlike expensive professional equipment, do not support differential operation in which they could take a correction correction and thus determine the location of the device with centimeter accuracy. The accuracy of determining the coordinates, unfortunately, still leaves much to be desired.

But before moving on to the essence of our technology, let us remind ourselves of the causes of errors in positioning. In real conditions, the accuracy of determining the coordinates of the device is affected by many factors. However, all sources of calculation errors can be divided into the following groups by their origin:

And now, I ask you to pay attention to the key point, which in its essence is the theoretical justification of the method described below -

To make it more clear what is a single space-time area, and what not, I will give examples. Consumers who are simultaneously in Moscow on Leningradsky Prospekt and Entuziastov highway will be in such a unified area - the navigation field, that is, the composition and location of the satellites in the sky, and the state of the ionosphere and the troposphere above them will be approximately the same, since the distance between them will be substantially less distance to satellites and sizes of inhomogeneities in the ionosphere. In turn, consumers from Moscow and Kazan will be located in different spatio-temporal areas, since positioning errors will depend on different parts of the troposphere and ionosphere. And even if you are in one place, but take measurements with a time interval of 1 or 2 hours, your measurements will correspond to different areas, since during this time there are changes not only in the ionosphere and the troposphere, but also the navigation field itself changes. I note that for various variants of differential subsystems, the typical spatial dimensions of such regions range from several units to hundreds of kilometers.

After a brief discussion of the theoretical basis for the method, let us turn to the description of the hypothesis as to how a set of "simple" devices in a single space-time domain can help improve the accuracy of positioning of each.

We take two trams (let there be, conditionally, 43 and 56 routes) with the receivers of satellite navigation systems installed on them. Let the tram 43 at a given time move from south to north, and tram 56 - from west to east. At the same time or with some slight difference in time comes a mark with the coordinates of the current location of trams. But, since differential subsystems are not used in their devices, the accuracy of the determination is not high enough for precise positioning - the marks are most likely in both cases will be located outside the tramway rails.

But we know that the receivers are on trams, physical limitations are imposed on the actual position in space. In fact, the variability of the location of trams is determined by the location of the rail - the real position of tram 43 is west of the observation point, and tram 5? in turn, is to the south. And now let's imagine a lucky coincidence that in the procedure of calculating the location in both cases the same navigation satellites (the so-called working constellation) were used. And for simplicity we assume that the accuracy of the determination was the same - the radii of the circles depicted coincide. Let's mentally fit these circles into one and find a virtual point at the intersection of the two paths. It is this point and will be a potential candidate for the role of the desired - the correction vectors from the observation points to the real situation of trams in this case will be the same.

Applying this correction vector to the marks, we easily calculate the position of both trams with more accuracy relative to the original. Of course, there will remain measurement errors related to the reflection of radio signals or the error of receivers.

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 that travel along our roads with navigators and ERA-GLONASS devices on board. And here is the next thought that I would like to convey: a car on the road is a 95% tram. In the sense that all cars in the aggregate do not move along the roads chaotically. If you look closely at the flow of cars on a straight section of the road, you can see that most of the time they travel along strips, as if tied to invisible rails. Only a small fraction of the time is occupied by rebuilding, overtaking and other maneuvers. In addition, unlike a pedestrian, the actual location of the vehicle is limited to a relatively small area of space - carriageways, the total area of which in major cities does not exceed 1-5% of the total territory. Moving at a speed of more than 20-30 kilometers per hour, a car can not suddenly be outside the carriageway (on the sidewalk, lawn or in the 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 traveling to the oncoming lane is negligible.

Thus, it can be assumed that the coordinates of vehicles that are recorded using satellite navigation systems outside the "permitted" areas, that is, contradicting the existing elements of the road infrastructure, are a good information signal when calculating the correction correcting these measurements towards the real location of the 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 permissible (the car can actually travel in neighboring bands or be rearranged from one row to another). On the other hand, a mark from a car on a single-lane forest road will give much more information.

More clearly understand the essence of the method can be using a conventional paper large-scale map and transparent paper. In your mind, put the transponder on the map and put the marks from the vehicles so that they correspond to the received observations. The more the marks, the better. Then it is necessary to move the transparency left-right and up-down to different values of the displacements so that the maximum number of points gets into "their" sections of the roads (they were not on the opposite lane, roadside, etc.). Solving the optimization problem in this way, we find the most probable real location of these cars, simultaneously revealing 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 - with the help of computer calculations, without the use of additional expensive equipment, to analyze a large number of observations from one space-time domain, to extract from each observation a piece of necessary information, comparing the mark with the "map" and calculate the total correction correction , which can be used for all devices in the area.

To calculate the general correction corrections, it is necessary to use the most detailed digital marking of as many sections of the road network as possible, with which you can more accurately localize the real situation of consumers. And not only drivers themselves, but also "horseless" pedestrians, including, of course, potential taxi customers. Devices of pedestrians, of course, should be excluded from the analysis and calculation of correctional corrections, but the calculated corrections can be applied to them on equal terms with motorists.

And what is digital marking? We define it as a mathematical model that describes the actual location of certain elements of the road infrastructure in space with the accuracy necessary and sufficient for solving various navigation tasks. Such elements of the road infrastructure include curbs, dividing lines, road markings, tram rails, etc. Simply put, digital marking should tell by coordinates (latitude and longitude) what this point corresponds to and how far it is removed from other road elements. For example, how close is the point to the curb, whether it belongs to the opposite strip or pedestrian sidewalk, etc.

It seems that the more accurately we manage to create digital markup, the more accurately we can make predictions. Unfortunately, the creation of accurate digital markup is an extremely complex and expensive task. However, its availability is also important for the development of unmanned vehicles, so its appearance sooner or later, I hope, will become inevitable. In the framework of creating the technology described above, we study and investigate approaches based on the same principles of cooperative observation and aimed at solving this problem, but this is a slightly different story

So, I think no one will have any problems imagining that we are all surrounded by countless mobile devices - smartphones, tablet computers, GPS-trackers, car navigators and even on-board computers in cars. As a rule, in

Such devices are built-in receivers of global satellite navigation systems (GPS, GLONASS, Baidu). These receivers are quite budgetary and, unlike expensive professional equipment, do not support differential operation in which they could take a correction correction and thus determine the location of the device with centimeter accuracy. The accuracy of determining the coordinates, unfortunately, still leaves much to be desired.

But before moving on to the essence of our technology, let us remind ourselves of the causes of errors in positioning. In real conditions, the accuracy of determining the coordinates of the device is affected by many factors. However, all sources of calculation errors can be divided into the following groups by their origin:

**Introduced by the control and measuring complex.**This includes errors due to a slight discrepancy between the time scales of navigation satellites and the errors due to the inaccuracy in the calculation of their locations relative to real orbits at the time of radiolocation to all consumers.**The navigation satellites themselves are introduced by the equipment**.**Emerging in the path of propagation of radio signals**. The main source here is the refraction of radio signals in the troposphere and the ionosphere of the Earth, caused by the inhomogeneities existing in them, which introduce additional propagation delays.**Introduced by the customer's receiver**(internal "noise" of the device).**Multipath propagation of the signal**(reflection from the surface of the Earth and surrounding buildings).And now, I ask you to pay attention to the key point, which in its essence is the theoretical justification of the method described below -

**The first three groups of error sources are common (i.e., 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, it is this idea that underlies the work of differential subsystems. In the areas of the so-called space-time correlation of errors, the error parameters calculated at an arbitrary point can be used during the correlation time to correct the measurements at other points in the region.To make it more clear what is a single space-time area, and what not, I will give examples. Consumers who are simultaneously in Moscow on Leningradsky Prospekt and Entuziastov highway will be in such a unified area - the navigation field, that is, the composition and location of the satellites in the sky, and the state of the ionosphere and the troposphere above them will be approximately the same, since the distance between them will be substantially less distance to satellites and sizes of inhomogeneities in the ionosphere. In turn, consumers from Moscow and Kazan will be located in different spatio-temporal areas, since positioning errors will depend on different parts of the troposphere and ionosphere. And even if you are in one place, but take measurements with a time interval of 1 or 2 hours, your measurements will correspond to different areas, since during this time there are changes not only in the ionosphere and the troposphere, but also the navigation field itself changes. I note that for various variants of differential subsystems, the typical spatial dimensions of such regions range from several units to hundreds of kilometers.

After a brief discussion of the theoretical basis for the method, let us turn to the description of the hypothesis as to how a set of "simple" devices in a single space-time domain can help improve the accuracy of positioning of each.

We take two trams (let there be, conditionally, 43 and 56 routes) with the receivers of satellite navigation systems installed on them. Let the tram 43 at a given time move from south to north, and tram 56 - from west to east. At the same time or with some slight difference in time comes a mark with the coordinates of the current location of trams. But, since differential subsystems are not used in their devices, the accuracy of the determination is not high enough for precise positioning - the marks are most likely in both cases will be located outside the tramway rails.

But we know that the receivers are on trams, physical limitations are imposed on the actual position in space. In fact, the variability of the location of trams is determined by the location of the rail - the real position of tram 43 is west of the observation point, and tram 5? in turn, is to the south. And now let's imagine a lucky coincidence that in the procedure of calculating the location in both cases the same navigation satellites (the so-called working constellation) were used. And for simplicity we assume that the accuracy of the determination was the same - the radii of the circles depicted coincide. Let's mentally fit these circles into one and find a virtual point at the intersection of the two paths. It is this point and will be a potential candidate for the role of the desired - the correction vectors from the observation points to the real situation of trams in this case will be the same.

Applying this correction vector to the marks, we easily calculate the position of both trams with more accuracy relative to the original. Of course, there will remain measurement errors related to the reflection of radio signals or the error of receivers.

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 that travel along our roads with navigators and ERA-GLONASS devices on board. And here is the next thought that I would like to convey: a car on the road is a 95% tram. In the sense that all cars in the aggregate do not move along the roads chaotically. If you look closely at the flow of cars on a straight section of the road, you can see that most of the time they travel along strips, as if tied to invisible rails. Only a small fraction of the time is occupied by rebuilding, overtaking and other maneuvers. In addition, unlike a pedestrian, the actual location of the vehicle is limited to a relatively small area of space - carriageways, the total area of which in major cities does not exceed 1-5% of the total territory. Moving at a speed of more than 20-30 kilometers per hour, a car can not suddenly be outside the carriageway (on the sidewalk, lawn or in the 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 traveling to the oncoming lane is negligible.

Thus, it can be assumed that the coordinates of vehicles that are recorded using satellite navigation systems outside the "permitted" areas, that is, contradicting the existing elements of the road infrastructure, are a good information signal when calculating the correction correcting these measurements towards the real location of the 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 permissible (the car can actually travel in neighboring bands or be rearranged from one row to another). On the other hand, a mark from a car on a single-lane forest road will give much more information.

More clearly understand the essence of the method can be using a conventional paper large-scale map and transparent paper. In your mind, put the transponder on the map and put the marks from the vehicles so that they correspond to the received observations. The more the marks, the better. Then it is necessary to move the transparency left-right and up-down to different values of the displacements so that the maximum number of points gets into "their" sections of the roads (they were not on the opposite lane, roadside, etc.). Solving the optimization problem in this way, we find the most probable real location of these cars, simultaneously revealing 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 - with the help of computer calculations, without the use of additional expensive equipment, to analyze a large number of observations from one space-time domain, to extract from each observation a piece of necessary information, comparing the mark with the "map" and calculate the total correction correction , which can be used for all devices in the area.

To calculate the general correction corrections, it is necessary to use the most detailed digital marking of as many sections of the road network as possible, with which you can more accurately localize the real situation of consumers. And not only drivers themselves, but also "horseless" pedestrians, including, of course, potential taxi customers. Devices of pedestrians, of course, should be excluded from the analysis and calculation of correctional corrections, but the calculated corrections can be applied to them on equal terms with motorists.

And what is digital marking? We define it as a mathematical model that describes the actual location of certain elements of the road infrastructure in space with the accuracy necessary and sufficient for solving various navigation tasks. Such elements of the road infrastructure include curbs, dividing lines, road markings, tram rails, etc. Simply put, digital marking should tell by coordinates (latitude and longitude) what this point corresponds to and how far it is removed from other road elements. For example, how close is the point to the curb, whether it belongs to the opposite strip or pedestrian sidewalk, etc.

It seems that the more accurately we manage to create digital markup, the more accurately we can make predictions. Unfortunately, the creation of accurate digital markup is an extremely complex and expensive task. However, its availability is also important for the development of unmanned vehicles, so its appearance sooner or later, I hope, will become inevitable. In the framework of creating the technology described above, we study and investigate approaches based on the same principles of cooperative observation and aimed at solving this problem, but this is a slightly different story