We have been building hiking trails along paths, through gates and with the ability to take a shortcut through the courtyard since April 2017. More recently, we have added a full-fledged navigator for pedestrians to 2GIS - with a turn-by-turn mode and voice acting of important points on the route.
Under the cut is a story about how we wanted to solve this problem quickly, relying on the expertise in navigation for cars, and as a result, we came up with new scenarios, fought for the size of the bases and learned to give the correct instructions.
New scenarios
We planned to solve the problem “in a couple of weeks” by slightly altering the logic of car maneuvers. For the first tests, we made an assembly with the voice acting of foot maneuvers, "wound" on the algorithms of car navigation. The result was amazing.
I plotted a route from home and put my phone in my pocket. Focused only on voice guidance. When I realized that I was starting to wander pointlessly, and the voice prompts only lead me away from the end point, I decided to rebuild the route. When the problem was repeated for the eighth time, it became clear that we had a huge layer of work ahead.
Voice instructions are based on the scenario of their use. The standard scenario template is how exactly a pedestrian approaches an intersection, how fast he moves and where he will go later. Automotive instructions did not work, as the conditions for their reproduction are too different from those for pedestrians. It is trite - the speed of a pedestrian is several times less, and this affects the moment of voice acting of the maneuver.
At the same time, it is important to take into account the nuances: pedestrian crossings, traffic lights, gates, stairs, ground and underground crossings, since information about these objects helps a pedestrian to find his bearings faster.
We have collected and described new practical scenarios and formulated new rules so that when approaching an underpass we say “Go down into the underpass”, and not just “Cross the road”.
Old algorithm
The quality of routing directly depends on the completeness of the data that is used to build the route: basic knowledge of the road graph, the location of edges and their additional attributes.
The completeness of the data is achieved in two stages: first, we collect information, and then we improve it using pre-calculation algorithms.
Based on the basic information, algorithms can enrich knowledge about the graph with additional attributes, for example, car instructions.
So for car routes we generate in advance all possible options for driving through an intersection, and for each option we calculate the required instruction and add attributes to it. This approach has a number of advantages:
Verifiability
Even at the pre-calculation stage, you can implement various algorithms for checking common cases. Correctly calculated, verified instructions will no longer change. This makes it possible to check the correctness of the instructions received before we deliver the data and algorithms to the user.
Updating data
Data in the 2GIS application is updated separately from the application itself. And we release them more often than changes in the algorithms of our libraries for mobile phones - this makes it possible to correct or add instructions without waiting for application releases.
Efficiency of the pre-generation algorithm
The algorithm for issuing instructions along the route actually boils down to comparing the instructions already in the database for all the edges that make up the route and issuing them to the user. Using the algorithm, this is much easier and faster than analyzing possible situations in runtime and generating instructions from them.
But there are two big drawbacks - this approach forces you to allocate additional resources for storing new information and creates a dependence on updating data packets. If the data is not updated or is not there, then the user does not get access to the feature even if he has an algorithm.
New algorithm
Even at the stage of creating the first prototype, we saw that due to pedestrian instructions, the size of the local base used for finding routes was growing. On average, the routing package has grown by 20% - this is an unacceptable amount, as it will lead to an increase in the size of offline databases on the phones of our audience.
Compared to car intersections, pedestrian crossings allow much more options for the passage. A standard intersection has 56 options for walking, depending on the position of the start (8 sides of the intersection) and end (7 sides) points. And in each version - up to three pedestrian maneuvers.
And the pedestrian intersections themselves, due to the whole variety of pedestrian paths and their intersections in the graph, are many times greater than the automobile ones. Taking into account the fact that we noticed growth only at the initial stage of working out the instructions and there were still many unresolved cases, the tendency was frightening.
Because of this, we abandoned the idea of pre-calculating pedestrian instructions and moved the logic of their generation to runtime. If there is Internet, then instructions are calculated on our servers, and if there is no Internet or the server's response did not meet the timeout, then on the mobile application. In fact, we rewrote the algorithm from scratch.
We have become less dependent on the version of the data. And in combination with the fact that most of the scripts are built through our online server, it became possible to quickly refine the algorithm for all users at once.
New instructions
I repeat that pedestrian walkways through intersections are much more variable compared to automobile ones.
Each intersection is an opportunity to change the route
At the stage of elaboration of instructions, we faced the problem of their compact, unambiguous and timely presentation. The asterisk to the task was added by the fact that the phone can be in the pocket, and the user does not see the guide line and arrows. You can only focus on voice guidance. In addition, a pedestrian, unlike a car, can easily turn around at almost any angle in a very narrow area. And it is important to explain to a person as accurately as possible how and where exactly to cross the road, turn or go down.
At first I went around and wrote down the errors. Sometimes I passed the intersections several dozen times to understand what the options might be. Then they made an emulator, on which they launched a virtual pedestrian, and listened to what was voiced to him and at what moment.
We checked the voice acting of forest paths, courtyard roads, crossings through wide intersections, unregulated and regulated pedestrian crossings with traffic lights.
The collected practical experience was analyzed, discussed, divided into groups of improvements, united by common solutions. For each of them, algorithmic scenarios were invented.
At this stage, it was understood that one-component instructions, such as automobile ones, were not enough - in walking routes, two separate instructions were so close that, due to inaccurate GPS, they might sound out of time and confuse a person.
We made composite voice instructions to orient ourselves before the transition, in which direction to move after it.
From the user's point of view, such an instruction is no different from the usual automobile one. So, the phrase "Turn left, then after 100 meters turn right" for a car is two one-component instructions
“Turn left” + “after 100 meters, turn right”. And for pedestrians, the phrase for crossing the road “Turn left into a pedestrian crossing and then turn right” is completely one instruction.
In fact, such instructions are bunches of any elementary turn instructions, but in the form of a single spoken instruction. This approach made it possible to significantly increase the information content and convenience of background maintenance. Especially when crossing non-trivial intersections.
At the nearest pedestrian crossing, turn left,
and immediately after the crossing, turn right
What else
"Tuning" geo-positioning
Walking routes often include relatively shallow passages - the edges of the graph. And in urban conditions, when the signal is unstable and / or shielded by high-rise objects, positioning errors can interfere with the correct calculation of instructions and guidance along the route. In order not to accidentally throw the current point to the other side of the street, we slightly "tuned up" the algorithm - we take into account the nuances of the error and adjust the algorithm for drawing to the route up to 30 meters.
Vibro
Voice guidance is the solution when the phone is in your pocket. But in order to avoid the situation when the voice will not be heard in a noisy city, we added vibration, which is triggered together with the voice acting before the desired maneuver. The vibration pattern itself was made different from the usual one when communicating in a messenger.
What happened
As a result, the first public version of the navigator for pedestrians took us about six months. Now it is available in 2GIS version for iOS and Android.
We have done a great job, but we ourselves are well aware that we missed tricky options. Send through the mobile application the cases that we showed and voiced incorrectly - each will be considered and taken into account in the algorithm.