Seit April 2017 bauen wir Wanderwege entlang von Wegen, durch Tore und mit der Möglichkeit, eine Abkürzung durch den Innenhof zu nehmen. In jüngerer Zeit haben wir 2GIS um einen vollwertigen Navigator für Fußgänger erweitert - mit einem Turn-by-Turn-Modus und Sprachausgabe wichtiger Punkte auf der Route.
Unter dem Schnitt steht eine Geschichte darüber, wie wir dieses Problem schnell lösen wollten, indem wir uns auf das Know-how in der Navigation von Autos stützten. Als Ergebnis entwickelten wir neue Szenarien, kämpften um die Größe der Basen und lernten, die richtigen Anweisungen zu geben .
Neue Szenarien
Wir wollten das Problem „in ein paar Wochen“ lösen, indem wir die Logik der Auto-Manöver leicht änderten. Für die ersten Tests haben wir eine Baugruppe mit der Sprachausgabe von Fußmanövern erstellt, die auf den Algorithmen der Autonavigation "verwundet" ist. Das Ergebnis war unglaublich.
Ich plante eine Route von zu Hause aus und steckte mein Handy in die Tasche. Konzentriert sich nur auf die Sprachführung. Als ich merkte, dass ich anfing, sinnlos zu wandern, und die Sprachansagen mich nur vom Endpunkt wegführten, beschloss ich, die Route neu aufzubauen. Als das Problem zum achten Mal wiederholt wurde, wurde klar, dass wir eine große Arbeitsebene vor uns hatten.
Sprachanweisungen basieren auf dem Szenario ihrer Verwendung. Die Standardszenario-Vorlage gibt an, wie genau sich ein Fußgänger einer Kreuzung nähert, wie schnell er sich bewegt und wohin er später gehen wird. Kfz-Anweisungen funktionierten nicht, da sich die Bedingungen für ihre Reproduktion zu stark von denen für Fußgänger unterscheiden. Es ist banal - die Geschwindigkeit eines Fußgängers ist um ein Vielfaches geringer, und dies beeinflusst den Moment der Sprachausgabe des Manövers.
Gleichzeitig ist es wichtig, die Nuancen zu berücksichtigen: Fußgängerüberwege, Ampeln, Tore, Treppen, Boden- und Untergrundübergänge, da Informationen über diese Objekte einem Fußgänger helfen, sich schneller zu orientieren.
Wir haben neue praktische Szenarien gesammelt und beschrieben und neue Regeln formuliert, sodass wir bei Annäherung an eine Unterführung sagen: „Geh in die Unterführung hinunter“ und nicht nur „Überquere die Straße“.
Alter Algorithmus
Die Qualität des Routings hängt direkt von der Vollständigkeit der Daten ab, die zum Erstellen der Route verwendet wurden: Grundkenntnisse des Straßendiagramms, die Position der Kanten und ihre zusätzlichen Attribute.
Die Vollständigkeit der Daten wird in zwei Schritten erreicht: Zuerst sammeln wir Informationen und dann verbessern wir sie mithilfe von Vorberechnungsalgorithmen.
Basierend auf den Basisinformationen können Algorithmen das Wissen über das Diagramm mit zusätzlichen Attributen erweitern, z. B. Fahrzeuganweisungen.
Für Autorouten generieren wir im Voraus alle möglichen Optionen für das Fahren durch eine Kreuzung. Für jede Option berechnen wir die erforderlichen Anweisungen und fügen ihr Attribute hinzu. Dieser Ansatz hat eine Reihe von Vorteilen:
Überprüfbarkeit
Bereits in der Vorberechnungsphase können Sie verschiedene Algorithmen zur Überprüfung häufiger Fälle implementieren. Richtig berechnete, überprüfte Anweisungen ändern sich nicht mehr. Dies ermöglicht es, die Richtigkeit der erhaltenen Anweisungen zu überprüfen, bevor wir die Daten und Algorithmen an den Benutzer liefern.
Aktualisieren von Daten
Daten in der 2GIS-Anwendung werden getrennt von der Anwendung selbst aktualisiert. Und wir veröffentlichen sie häufiger als Änderungen in den Algorithmen unserer Bibliotheken für Mobiltelefone - dies ermöglicht es, Anweisungen zu korrigieren oder hinzuzufügen, ohne auf Anwendungsfreigaben zu warten.
Effizienz des Vorgenerierungsalgorithmus
Der Algorithmus zum Ausgeben von Anweisungen entlang der Route besteht darin, die bereits in der Datenbank vorhandenen Anweisungen für alle Kanten, aus denen die Route besteht, zu vergleichen und an den Benutzer auszugeben. Mit dem Algorithmus ist dies viel einfacher und schneller als die Analyse möglicher Situationen zur Laufzeit und das Generieren von Anweisungen daraus.
Es gibt jedoch zwei große Nachteile: Dieser Ansatz zwingt Sie dazu, zusätzliche Ressourcen zum Speichern neuer Informationen zuzuweisen, und führt zu einer Abhängigkeit von der Aktualisierung von Datenpaketen. Wenn die Daten nicht aktualisiert werden oder nicht vorhanden sind, erhält der Benutzer keinen Zugriff auf die Funktion, selbst wenn er über einen Algorithmus verfügt.
Neuer Algorithmus
Bereits bei der Erstellung des ersten Prototyps stellten wir fest, dass aufgrund von Fußgängeranweisungen die Größe der lokalen Basis, die zum Auffinden von Routen verwendet wurde, zunahm. Im Durchschnitt ist das Routing-Paket um 20% gewachsen - dies ist eine inakzeptable Menge, da dies zu einer Vergrößerung der Offline-Datenbanken auf den Telefonen unserer Zielgruppe führen wird.
Im Vergleich zu Autokreuzungen bieten Fußgängerüberwege viel mehr Möglichkeiten für die Überfahrt. Eine Standardkreuzung bietet je nach Position der Start- (8 Seiten der Kreuzung) und Endpunkte (7 Seiten) 56 Optionen zum Gehen. Und in jeder Version - bis zu drei Fußgängermanöver.
Und die Fußgängerkreuzungen selbst sind aufgrund der Vielzahl von Fußgängerwegen und ihrer Kreuzungen in der Grafik um ein Vielfaches größer als die von Automobilen. Angesichts der Tatsache, dass wir erst in der Anfangsphase der Ausarbeitung der Anweisungen ein Wachstum bemerkten und es immer noch viele ungelöste Fälle gab, war die Tendenz beängstigend.
Aus diesem Grund haben wir die Idee der Vorberechnung von Fußgängeranweisungen aufgegeben und die Logik ihrer Generierung auf die Laufzeit verschoben. Wenn es Internet gibt, werden Anweisungen auf unseren Servern berechnet, und wenn es kein Internet gibt oder die Antwort des Servers das Zeitlimit nicht erreicht hat, dann auf der mobilen Anwendung. Tatsächlich haben wir den Algorithmus von Grund auf neu geschrieben.
Wir sind weniger abhängig von der Version der Daten geworden. In Kombination mit der Tatsache, dass die meisten Skripte über unseren Online-Server erstellt werden, wurde es möglich, den Algorithmus für alle Benutzer gleichzeitig schnell zu verfeinern.
Neue Anweisungen
Ich wiederhole, dass Fußgängerwege durch Kreuzungen im Vergleich zu Automobilen viel variabler sind.
Jede Kreuzung ist eine Gelegenheit, die Route zu ändern.
Bei der Ausarbeitung der Anweisungen standen wir vor dem Problem ihrer kompakten, eindeutigen und zeitnahen Darstellung. Das Sternchen zur Aufgabe wurde durch die Tatsache hinzugefügt, dass sich das Telefon in der Tasche befinden kann und der Benutzer die Hilfslinie und die Pfeile nicht sieht. Sie können sich nur auf die Sprachführung konzentrieren. Darüber hinaus kann sich ein Fußgänger im Gegensatz zu einem Auto in einem sehr engen Bereich in nahezu jedem Winkel leicht drehen. Und es ist wichtig, einer Person so genau wie möglich zu erklären, wie und wo genau sie die Straße überqueren, abbiegen oder hinunterfahren soll.
Zuerst ging ich herum und schrieb die Fehler auf. Manchmal passierte ich die Kreuzungen mehrere Dutzend Mal, um zu verstehen, welche Optionen es geben könnte. Dann machten sie einen Emulator, auf dem sie einen virtuellen Fußgänger starteten, und hörten zu, was zu welchem Zeitpunkt zu ihm geäußert wurde.
Wir überprüften die Sprachausgabe von Waldwegen, Hofstraßen, Kreuzungen durch breite Kreuzungen, unregulierten und regulierten Fußgängerüberwegen mit Ampeln.
Die gesammelten praktischen Erfahrungen wurden analysiert, diskutiert und in Gruppen von Verbesserungen unterteilt, die durch gemeinsame Lösungen vereint wurden. Für jedes von ihnen wurden algorithmische Szenarien erfunden.
Zu diesem Zeitpunkt wurde festgestellt, dass einkomponentige Anweisungen, wie z. B. Anweisungen für Automobile, nicht ausreichten. Auf Laufrouten waren zwei separate Anweisungen so nahe beieinander, dass sie aufgrund von ungenauem GPS möglicherweise zu spät klingen und eine Person verwirren.
Wir haben zusammengesetzte Sprachanweisungen erstellt, um uns vor dem Übergang zu orientieren und in welche Richtung wir uns danach bewegen sollen.
Aus Sicht des Benutzers unterscheidet sich eine solche Anweisung nicht von der üblichen Automobilanweisung. Der Satz "Biegen Sie links ab und dann nach 100 Metern rechts ab" für ein Auto besteht aus zwei Einkomponentenanweisungen
"Biegen Sie links ab" + "Biegen Sie nach 100 Metern rechts ab". Und für Fußgänger ist der Satz zum Überqueren der Straße „Am Zebrastreifen links abbiegen und dann rechts abbiegen“ nur eine Anweisung.
Tatsächlich sind solche Anweisungen Bündel von Elementarumdrehungsanweisungen, jedoch in Form einer einzelnen gesprochenen Anweisung. Dieser Ansatz ermöglichte es, den Informationsgehalt und die Benutzerfreundlichkeit der Hintergrundpflege erheblich zu verbessern. Besonders beim Überqueren nicht trivialer Kreuzungen.
Biegen Sie am nächsten Fußgängerüberweg links
und unmittelbar nach dem Übergang rechts ab
Was sonst
Geo-Positionierung "Tuning"
Fußgängerrouten enthalten häufig relativ flache Passagen - die Kanten des Diagramms. Und unter städtischen Bedingungen, wenn das Signal instabil und / oder durch Hochhäuser abgeschirmt ist, können Positionierungsfehler die korrekte Berechnung von Anweisungen und Anweisungen entlang der Route beeinträchtigen. Um den aktuellen Punkt nicht versehentlich auf die andere Straßenseite zu werfen, haben wir den Algorithmus leicht "abgestimmt" - wir berücksichtigen die Nuancen des Fehlers und passen den Algorithmus für das Zeichnen auf die Route bis zu 30 Metern an.
Vibro
Sprachführung ist die Lösung, wenn sich das Telefon in Ihrer Tasche befindet. Um jedoch zu vermeiden, dass die Stimme in einer lauten Stadt nicht gehört wird, haben wir Vibrationen hinzugefügt, die zusammen mit der vor dem gewünschten Manöver wirkenden Stimme ausgelöst werden. Das Vibrationsmuster selbst wurde bei der Kommunikation in einem Messenger von dem üblichen Muster unterschieden.
Was ist passiert
Infolgedessen dauerte die erste öffentliche Version des Navigators für Fußgänger ungefähr sechs Monate. Jetzt ist es in der 2GIS-Version für iOS und Android verfügbar.
Wir haben großartige Arbeit geleistet, aber wir sind uns bewusst, dass wir knifflige Optionen verpasst haben. Senden Sie über die mobile Anwendung die Fälle, die wir falsch angezeigt und geäußert haben - jeder Fall wird berücksichtigt und im Algorithmus berücksichtigt.