Algorithmen für Geographische Informationssysteme 3. Vorlesung: 29. April 2015 Thomas van Dijk basiert auf Folien von Jan-Henrik Haunert Map Matching Problemformulierung Gegeben: Das Straßennetz als planar eingebetteter Graph πΊ = π, πΈ Die GPS-Trajektorie als Folge π = π1 , π2 , β¦ , ππ von Punkten Gesucht: Weg in πΊ, der minimale Distanz zu π hat. Map Matching Hausdorff-Distanz πhdorff π1 , π2 = max πhdorff π1 , π2 , πhdorff π2 , π1 mit πhdorff π1 , π2 = max π π1 , π2 und π π1 , π2 = min π π1 , π2 π1 β π1 π2 β π2 π1 πhdorff π1 , π2 π2 Fréchet-Distanz Herrchen läuft entlang π1 ohne jemals umzukehren. Hund läuft entlang π2 ohne jemals umzukehren. Herrchen und Hund sind über Hundeleine verbunden. Wie lang ist die Hundeleine mindestens? π2 π1 Fréchet-Distanz Definition: π fréchet = min πΌ: 0,1 β 0,πβ1 π½: 0,1 β 0,πβ1 max π‘β 0,1 π π1 πΌ π‘ , π2 π½ π‘ wobei πΌ und π½ monoton wachsende und stetige Funktionen sind und πΌ 0 = π½ 0 = 1, πΌ 1 = π β 1, π½ 1 = π β 1. π2 π1 Fréchet-Distanz Berechnung: Löse Entscheidungsproblem: Ist πfréchet β€ π? dann parametrische Suche... π2 π1 Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: π1 π1 0.6 π2 π2 0.75 π Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: π1 π1 0.6 Zuordnung 0.6,0.75 ist zulässig! π2 π2 0.75 π Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: π1 Zuordnung 0.1,0.9 ist nicht zulässig! π2 π2 0.9 π1 0.1 π Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: π1 π1 π2 π 1 1 π2 Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: π1 Zuordnung 0.6,0.75 ist zulässig! π1 π2 π 1 1 π2 Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: π1 Zuordnung 0.6,0.75 ist zulässig! Zuordnung 0.1,0.9 ist nicht zulässig! π1 π2 π 1 1 π2 Fréchet-Distanz Ist πfréchet β€ π? Spezialfall: Freiraum πΉπ = π , π‘ β 0,1 2 π π1 π , π2 π‘ hat die Form einer Ellipse! π1 β€π Zuordnung 0.6,0.75 ist zulässig! Zuordnung 0.1,0.9 ist nicht zulässig! π1 π2 1 πΉπ π 1 π2 Fréchet-Distanz Freiraum πΉπ = π , π‘ β 0,1 2 π π1 π , π2 π‘ hat die Form einer Ellipse! πfréchet β€ π β Es gibt einen Pfad von 0,0 nach 1,1 im inneren von πΉπ , der in beide Richtungen monoton ist. π1 1 πΉπ 1 π2 β€π Fréchet-Distanz Freiraum πΉπ = π , π‘ β 0,1 2 π π1 π , π2 π‘ hat die Form einer Ellipse! πfréchet β€ π β Es gibt einen Pfad von 0,0 nach 1,1 im inneren von πΉπ , der in beide Richtungen monoton ist. β€π π1 1 πΉπ 1 π2 Hier gibt es ihn nicht, da 0,0 β πΉπ ! Fréchet-Distanz Freiraum πΉπ = π , π‘ β 0,1 2 π π1 π , π2 π‘ hat die Form einer Ellipse! πfréchet β€ π β Es gibt einen Pfad von 0,0 nach 1,1 im inneren von πΉπ , der in beide Richtungen monoton ist. β€π π1 1 πΉπ 1 π2 Für größeres π gibt es einen Pfad! Fréchet-Distanz Freiraum πΉπ = π , π‘ β 0, π β 1 × 0, π β 1 π π1 π , π2 π‘ β€π π2 πfréchet β€ π β Es gibt einen Pfad von 0,0 nach π, π im inneren von πΉπ , der in beide Richtungen monoton ist. π1 π π2 π1 Fréchet-Distanz Freiraum πΉπ = π , π‘ β 0, π β 1 × 0, π β 1 π π1 π , π2 π‘ β€π π2 πfréchet β€ π β Es gibt einen Pfad von 0,0 nach π, π im inneren von πΉπ , der in beide Richtungen monoton ist. πΉπ kann in π ππ Zeit berechnet werden. π1 π π2 π1 Fréchet-Distanz Freiraum πΉπ = π , π‘ β 0, π β 1 × 0, π β 1 π π1 π , π2 π‘ β€π π2 πfréchet β€ π β Es gibt einen Pfad von 0,0 nach π, π im inneren von πΉπ , der in beide Richtungen monoton ist. πΉπ kann in π ππ Zeit berechnet werden. π1 π π2 Finde zulässigen Pfad in πΉππ1. Fréchet-Distanz Kanten einer Freiraumzelle: πΉ πΉ πΉ πΉ π΅π,π , π΅π,π+1 , πΏπ,π , πΏπ+1,π π©πΉ π,π+π π³πΉ π+π,π π³πΉ π,π Teile dieser Kanten, die von (0,0) aus erreichbar sind: π π π π π΅π,π , π΅π,π+1 , πΏπ,π , πΏπ+1,π π π π΅π,π , πΏπ,π π©πΉ π,π = β bekannt π β π΅π,π+1 , πΏπ π+1,π Fréchet-Distanz Algorithmus Fréchet-Distanz Berechnung: Löse Entscheidungsproblem: Ist πfréchet β€ π? π2 π1 Fréchet-Distanz Berechnung: Löse Entscheidungsproblem: Ist πfréchet β€ π? dann parametrische Suche... π ππ log ππ Zeit (hier ohne Details) π2 π1 Map Matching Problemformulierung Gegeben: Das Straßennetz als planar eingebetteter Graph πΊ = π, πΈ Die GPS-Trajektorie als Folge π = π1 , π2 , β¦ , ππ von Punkten Gesucht: Weg in πΊ, der minimale Distanz zu π hat. Map Matching Map Matching Problemformulierung Gegeben: Das Straßennetz als planar eingebetteter Graph πΊ = π, πΈ Die GPS-Trajektorie als Folge π = π1 , π2 , β¦ , ππ von Punkten Gesucht: Weg in πΊ, der minimale Fréchet-Distanz zu π hat. Map Matching Map Matching Entscheidungsproblem Gegeben: Das Straßennetz als planar eingebetteter Graph πΊ = π, πΈ Die GPS-Trajektorie als Folge π = π1 , π2 , β¦ , ππ von Punkten Zulässige Distanz π Gibt es einen Weg in πΊ, dessen Fréchet-Distanz zu π kleiner ist als π? Map Matching Map Matching Entscheidungsproblem Freiraumdiagramm für zwei Polygonzüge π2 π1 Map Matching Entscheidungsproblem Freiraumdiagramm für zwei Polygonzüge π2 π1 Idee: Freiraumdiagramm für Polygonzug und Graph Map Matching Idee: Freiraumdiagramm für Polygonzug und Graph Map Matching Idee: Freiraumdiagramm für Polygonzug und Graph Map Matching Freiraumdiagramm für Polygonzug und eine Kante Idee: Freiraumdiagramm für Polygonzug und Graph Map Matching Suche einen zulässigen Pfad von links nach rechts. Idee: Freiraumdiagramm für Polygonzug und Graph Map Matching Entscheidbar in πΆ π¬ π· π₯π¨π π¬ Suche einen zulässigen Pfad von links nach rechts. Alt et al. 2003: Matching Planar Maps J. Algorithm. Zeit. Map Matching Lösbar in πΆ π¬ π· π₯π¨π π¬ π₯π¨π π¬ π· Finde einen zulässigen Pfad mit minimaler Fréchet-Distanz Alt et al. 2003: Matching Planar Maps J. Algorithm. Zeit. Map Matching Problemformulierung Gegeben: Das Straßennetz als planar eingebetteter Graph πΊ = π, πΈ Die GPS-Trajektorie als Folge π = π1 , π2 , β¦ , ππ von Punkten VIDEO Gesucht: Weg in πΊ, der minimale Fréchet-Distanz zu π hat. Lösbar in πΆ π¬ π· π₯π¨π π¬ π₯π¨π π¬ π· Map Matching Zeit. Map Matching Problem: GPS-Punkte der Trajektorie weisen einen relativ großen Abstand zueinander auf. Map Matching Problem: GPS-Punkte der Trajektorie weisen einen relativ großen Abstand zueinander auf. β Direkte Verbindung zwischen Punkten ist schlechte Näherung Map Matching Problem: GPS-Punkte der Trajektorie weisen einen relativ großen Abstand zueinander auf. Ergebnis mit minimaler Fréchet-Distanz Idee: Fahrer wählen bevorzugt kürzeste Wege im Straßennetz. Map Matching Problem: GPS-Punkte der Trajektorie weisen einen relativ großen Abstand zueinander auf. kürzeste Route Idee: Fahrer wählen bevorzugt kürzeste Wege im Straßennetz. Map Matching Ansatz über kürzeste Wege Lou et al.: Map-Matching for Low-Sampling-Rate GPS Trajectories, Proc. ACM GIS 2009. Ein Punkt etwa alle zwei Minuten (z.B. zur Aufzeichnung & Analyse von P. Newson und J. Krum: Taxirouten) Hidden Markov Map Matching Through Noise and Sparseness, Proc. ACM GIS 2009 Eisner et al.: Algorithms for Matching and Predicting Trajectories, Proc. ALENEX 2011 Map Matching Ansatz über kürzeste Wege Lou et al.: Map-Matching for Low-Sampling-Rate GPS Trajectories, Proc. ACM GIS 2009. P. Newson und J. Krum: Hidden Markov Map Matching Through Noise and Sparseness, Proc. ACM GIS 2009 = Maximum-likelihood estimation + Markov Chains + Hidden Markov Models Eisner et al.: Algorithms for Matching and Predicting Trajectories, Proc. ALENEX 2011 Maximum-likelihood estimation Probability versus Likelihood β’ Flipping a coin: β π[βππππ ] = π β π π‘ππππ = 1 β π β’ Do three independent flips. β’ The coin is fair (p = ½). Model Parameter value Outcome? β’ What is the probability of getting outcome x=(H,H,T)? π π₯ = π», π», π ; π = 1 2 π is not a random variable! π π₯ = π», π», π | π = 1 2 = 1 2 β 1 2 β 1 β 1 2 = 0.125 Maximum-likelihood estimation Probability versus Likelihood β’ Flipping a coin: β π[βππππ ] = π β π π‘ππππ = 1 β π β’ Did three independent flips. β’ The result was x=(H,H,T). Model Parameter value? Outcome β’ What is the likelihood that the coin is fair (p = ½)? Maximum-likelihood estimation Likelihood functions β’ Given the outcome π₯, how βlikelyβ is a certain parameter value π? β’ Assuming parameter value π, what is the probability of outcome π₯? β’ Define likelihood function β π π₯ = π[π₯; π] Not a probability! β’ The result was (H,H,T). β’ What is the likelihood that the coin is fair (p = ½)? β’ β π = π π | π₯ = π», π», π = 1 2 β 1 2 β 1 2 = 0.125 β’ β π = π. π | π₯ = π», π», π = 0.1 β 0.1 β 0.9 = 0.009 β’ β π = π π | π₯ = π», π», π = 2 3 β 2 3 β 1 3 = 0. 148 Maximum-likelihood estimation Predictions versus Estimates β’ Most probable outcome β Given parameter π = 2 3β¦ β β¦ the most probably outcome is (π», π», π»). β’ Maximum-Likelihood Estimate (βMLEβ) β β β β Given outcome (π, π», π)β¦ β¦maximum-likelihood estimate is π = 1 3. This value of π βbest explains the observed outcome.β This value of π makes the outcome βleast surprising.β Maximum-likelihood estimation Maximum-likelihood map matching? β’ Model? Parameter? Outcome? β’ Most probable outcome β Given a path in a road network β¦ β β¦ what is the most probable GPS trajectory to observe? (Noisy.) β’ Maximum-Likelihood Estimate (MLE) β Given the observed GPS trajectory (noisy) β¦ β β¦ what is the most likely path through the road network? β βWhich path through the network best explains the observed GPS trajectory?β ΠΠ°ΡΠ½ΡΜΡΠΈΠΉ Π§Π΅Π±ΡΡΡΠ² 1821 - 1894 ΠΠ°ΜΡΠΊΠΎΠ² Chains ΠΠ½Π΄ΡΠ΅ΜΠΉ ΠΠ°ΜΡΠΊΠΎΠ² 1856 - 1922 ΠΠ΅ΠΎΡΠ³ΡΠΉ ΠΠΎΡΠΎΠ½ΠΈΠΉ 1868 - 1908 ΠΠΎΡΠΈΜΡ ΠΠ΅Π»ΠΎΠ½Π΅Μ 1890 - 1980 WacΕaw SierpiΕski 1882 - 1969 Chebyshev 1821 - 1894 ΠΠ°ΜΡΠΊΠΎΠ² Chains Markov 1856 - 1922 Voronoi 1856 - 1922 Delaunay 1890 - 1980 Sierpinski 1882 - 1969 Markov Chains β’ Sequence of random variables π1 , π2 , π3 , β¦ β’ Markov Property: Pr πn+1 ππ = π₯π , ππβ1 = π₯πβ1 , β¦ , π1 = π₯1 ] = Pr ππ+1 ππ = π₯π ] β’ βGiven the present, the future is independent of the past.β β’ Represent as Pr[π1 ], Pr[π2 |π1 ], Pr π3 π2 , β¦ Markov Chains Example β’ Possible states π = πππππ, π ππππ β’ Pr[ π1 = π ππππ ] = 0.3 β’ Pr π1 = πππππ = 0.7 β’ β’ β’ β’ Pr Pr Pr Pr ππ+1 = π ππππ ππ+1 = πππππ ππ+1 = π ππππ ππ+1 = πππππ ππ = π ππππ ] = 0.7 ππ = π ππππ ] = 0.3 ππ = πππππ ] = 0.2 ππ = πππππ ] = 0.8 Markov Chains Example β’ Possible states π = πππππ, π ππππ β’ Pr[ π1 = π ππππ ] = 0.3 β’ Pr π1 = πππππ = 0.7 Pr π2 = πππππ ? 0.2 0.8 0.7 Sonne Regen 0.3 Markov Chains Example β’ Possible states π = πππππ, π ππππ β’ Pr[ π2 = π ππππ ] = 0.35 β’ Pr π2 = πππππ = 0.65 Pr π3 = π ππππ ? 0.2 0.8 0.7 Sonne Regen 0.3 Hidden Markov Models β’ Markov Chain β At every time step, it has a certain state β’ But the states are hidden β We cannot βseeβ its state β’ Emission (βoutputβ) β At every time step, get an observation β Probability distribution depends on state β Emission at each step is independent This slide intentionally left blank. Using maximum likelihood estimation Map Matching 1. Für jeden GPS-Punkt ππ suche Menge von Kandidatenkanten ππ1 , β¦ , πππ , die (teilweise) innerhalb eines Kreises mit Radius π um ππ liegen. Map Matching 1. Für jeden GPS-Punkt ππ suche Menge von Kandidatenkanten ππ1 , β¦ , πππ , die (teilweise) innerhalb eines Kreises mit Radius π um ππ liegen. 2. Suche Menge von Kandidatenpunkten π ππ1 , β¦ , πππ , wobei ππ der nächste Punkt π auf ππ zu ππ ist. Map Matching 1. Für jeden GPS-Punkt ππ suche Menge von Kandidatenkanten ππ1 , β¦ , πππ , die (teilweise) innerhalb eines Kreises mit Radius π um ππ liegen. 2. Suche Menge von Kandidatenpunkten π ππ1 , β¦ , πππ , wobei ππ der nächste Punkt π auf ππ zu ππ ist. π 3. Bewerte jeden Kandidatenpunkt ππ mit π einer Wahrscheinlichkeit π ππ π π ππ = 1 2ππ π 2 π β π ππ ,ππ 2π 2 (Normalverteilung) π = 20 m Map Matching 1. Für jeden GPS-Punkt ππ suche Menge von Kandidatenkanten ππ1 , β¦ , πππ , die (teilweise) innerhalb eines Kreises mit Radius π um ππ liegen. 2. Suche Menge von Kandidatenpunkten π ππ1 , β¦ , πππ , wobei ππ der nächste Punkt π auf ππ zu ππ ist. π 3. Bewerte jeden Kandidatenpunkt ππ mit π einer Wahrscheinlichkeit π ππ 4. Bewerte jedes Paar aufeinander folgender Kandidatenpunkte mit einer Übergangswahrscheinlichkeit π ππβ1 , ππ π π π ππβ1 , ππ = π πshortestβpath ππβ1 , πππ Länge des kürzesten Weges von π ππβ1 nach πππ im Straßennetz Map Matching 1. Für jeden GPS-Punkt ππ suche Menge von Kandidatenkanten ππ1 , β¦ , πππ , die (teilweise) innerhalb eines Kreises mit Radius π um ππ liegen. 2. Suche Menge von Kandidatenpunkten π ππ1 , β¦ , πππ , wobei ππ der nächste Punkt π auf ππ zu ππ ist. π 3. Bewerte jeden Kandidatenpunkt ππ mit π einer Wahrscheinlichkeit π ππ 4. Bewerte jedes Paar aufeinander folgender Kandidatenpunkte mit einer Übergangswahrscheinlichkeit π π ππβ1 , πππ Map Matching 1. Für jeden GPS-Punkt ππ suche Menge von Kandidatenkanten ππ1 , β¦ , πππ , die (teilweise) innerhalb eines Kreises mit Radius π um ππ liegen. 2. Suche Menge von Kandidatenpunkten π ππ1 , β¦ , πππ , wobei ππ der nächste Punkt π auf ππ zu ππ ist. π 3. Bewerte jeden Kandidatenpunkt ππ mit π einer Wahrscheinlichkeit π ππ 4. Bewerte jedes Paar aufeinander folgender Kandidatenpunkte mit einer Übergangswahrscheinlichkeit π π ππβ1 , πππ Ziel: Wähle für jeden Punkt ππ einen Kandidatenpunkt ππ aus der Menge ππ1 , β¦ , πππ , so dass π π1 β π π1 , π2 β π π2 β π π2 , π3 β β¦ β π ππ maximal ist. Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 ... + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 Modellierung als Graph-Problem: ... π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. π22 π12 π π11 π33 π32 π21 Kandidatenmenge für π1 π31 π‘ Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 Modellierung als Graph-Problem: ... π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. π22 π12 π π11 π33 π32 π21 π31 Kandidatenmenge für π2 π‘ Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 Modellierung als Graph-Problem: ... π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. π22 π12 π π11 π33 π32 π21 π31 Kandidatenmenge für π3 π‘ Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 Modellierung als Graph-Problem: ... π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. π22 π12 π π11 π33 π32 π21 Dummy-Knoten π31 π‘ Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 Modellierung als Graph-Problem: ... π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. π22 π12 π π11 π33 π32 π21 π‘ π31 Jeder π -π‘-Pfad steht für eine Lösung des Map-Matching-Problems Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 ... Modellierung als Graph-Problem Definiere Kantenlängen: π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ π22 π12 maximal ist. π π11 π33 π32 π21 π‘ π31 log π π31 0 log π π11 β π π11 , π21 Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 ... Modellierung als Graph-Problem Definiere Kantenlängen: π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ π12 maximal ist. π Lösung: Längster π -π‘-Pfad π22 π11 π33 π32 π21 π‘ π31 log π π31 0 log π π11 β π π11 , π21 Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 ... Modellierung als Graph-Problem Definiere Kantenlängen: π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. π22 π12 π π11 Lösung: Längster π -π‘-Pfad Allgemein ist das Longest-Path-Problem NP-schwer! π33 π32 π21 π31 π‘ Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 ... Modellierung als Graph-Problem Definiere Kantenlängen: π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. Lösung: Längster π -π‘-Pfad π22 π12 π π11 π33 π32 π21 π‘ π31 Für gerichtete azyklische Graphen mit π Kanten und π Ecken ist das Longest-Path-Problem in π ππ Zeit lösbar! Map Matching Ziel: Wähle für jeden Punkt ππ einen Kandidaten-punkt ππ aus der Menge ππ1 , β¦ , πππ , so dass log π π1 β π π1 , π2 + log π π2 β π π2 , π3 ... Modellierung als Graph-Problem Definiere Kantenlängen: π13 + log π ππβ1 β π ππβ1 , ππ + log π ππ maximal ist. Lösung: Längster π -π‘-Pfad π22 π12 π π11 π33 π32 π21 π‘ π31 Für gerichtete azyklische Graphen mit π Kanten und π Ecken ist das Longest-Path-Problem in π ππ Zeit lösbar! Wie? Map Matching Aufgabe: Finde längsten Pfad in gerichtetem azyklischen Graphen. Lösung: 1. Bringe die Ecken in topologische Ordnung β π£1 β¦ π£π 2. Löse das Problem durch dynamische Programmierung: π π£1 , π£1 = 0 for π = 2 to π // Berechne π π£1 , π£π = Länge eines längsten π£1 -π£π -Pfades πππ₯ = ββ for π£π , π£π β π΄ if π π£1 , π£π + β π£π , π£π > πππ₯ then // β π£π , π£π = Länge der Kante π£π , π£π πππ₯ = π π£1 , π£π + β π£π , π£π π π£1 , π£π = πππ₯ ππππππππ π ππ π = π
© Copyright 2025 ExpyDoc
