Navigator 2GIS：車両位置の外挿

2GISアプリケーションにナビゲータが追加されました。 私たちは、トラックに沿って「ドライブ」、音の操作、自動再ルーティング、移動時間の計算、フェンスや障壁を考慮して、ユーザーを建物や組織の入り口に連れて行く方法を学びました。 交通渋滞（インターネットが必要なことを除く）、長い橋、および通行止めの道路は長い間考慮されてきました。 ナビゲーターにいる間-必要最小限。 少し後で、高すぎる速度、バンプ、交通警察カメラについて警告し、夜間モードを設定し、有料道路と未舗装道路のルートをオプションにするように彼に教えます。 使用するには、スマートフォンで2GISを更新するか、 AppStoreまたはWindowsストアでダウンロードする必要があります。 Androidの場合、アップデートは8月22日から徐々にリリースされます（9月までに視聴者全員が利用できるようになります）。

今日は、2GISナビゲーターが車の位置を予測し、ルートに沿って矢印をスムーズに移動する方法を説明します。 実際、現代のナビゲーターのインターフェイスの人間工学、地上でのオリエンテーションの容易さ、および機動の適時性を決定するのは、ルートに沿ったユーザーガイダンスの品質です。

ほとんどの場合、車の運転手は道路を追わざるを得ないので、ナビゲーションプログラムを使用してデバイスの画面を一目見ただけでも、ルートおよび周囲の物体に関連する自分の位置に関する最も正確でタイムリーな情報を取得するのに十分です。 この一見シンプルな機能を実装するには、多くの技術的な問題を解決する必要があります。 それらのいくつかを検討します。

GPSマーカーとルート

地図上のユーザーの位置を示すために、多くのナビゲーター（および例外ではありません）は、矢印の形または移動の方向を直感的に示す三角形のみの特別なGPSマーカーを使用します。 さらに、マーカーはマップ上ではっきりと見えるようにする必要があります。そのため、通常、その色は背景と非常に異なり、エッジはさらに丸くなります。

最も単純なケースでは、GPSセンサーから座標を読み取り、マーカーを地図上の適切な場所に配置して、地上でのデバイスの位置を表示できます。 すでにここで最初の問題に直面しています-測定エラーです。これは、良好な信号の状態でも20〜30メートルに達する可能性があります。

「Where am I？」という通常の質問に答えるには、特に誤差推定値に等しい半径のマーカーの周りに精度の円を描く場合、この表示方法で十分です。 ただし、ナビゲーションの場合は、街路に沿って移動するドライバーが近隣の家の中、またはさらに悪いことに四半期内の車道にあるGPSマーカーに満足する可能性が低いため、より良いものを考え出す必要があります。

プログラムによって目的地までのルートが構築され、ナビゲーションスクリプトに常に存在するルートは、問題の解決に役立ちます。 いくつかのトリックの助けを借りて、マップ上のポイントをルートに「プル」して、GPSセンサーの測定誤差の一部を平準化できます。 最初の近似では、ドローはポイントをルートラインに投影することと見なすことができます。 残念ながら、ルートからの逸脱を検出する方法と同様に、ニュアンスの考慮はこの記事の範囲外です。

示された描画手法を使用して、2次元の地理座標（緯度と経度またはその他）から抽象化し、1次元の座標に移動できます。たとえば、メートル単位で測定されたルートの始点に対するオフセットです。 この移行により、理論モデルとユーザーデバイスで実行される計算の両方が簡素化されます。

経時的なジオポジショニング

GPSセンサーからのデータ受信の離散的な性質は、ルートに沿ったユーザーガイダンスを実装する際の別の問題です。 理想的には、座標は1秒に1回更新されます。 時間内に地理位置情報を表示するためのいくつかのオプションを検討し、タスクに最適なものを選択します。

1.最も簡単な方法は、センサーからの新しい読み取り値が受信されるたびに、すぐにルートを描画し、マップ上の対応する場所を表示することです。 利点の中でも、非常に簡単な実装、ある意味での高精度（結局、ここでは衛星データに重大な変更を加えることなく単に表示する）、および計算の複雑さが最小限であることは注目に値します。 主な欠点は、この場合のマーカーは通常の意味では地図上を移動せず、ポイントからポイントへ「テレポート」されることです。 主なナビゲーションシナリオでは、カメラ（仮想オブザーバー-コンピューターグラフィックスの用語）はGPSマーカーに関連付けられているため、このようなテレポーテーションは、ルートに沿ったマップの鋭い「ローリング」につながり、その結果、特に高速での運転者の見当識障害につながります車両は、ジオロケーション測定値の間にかなりの距離を移動します。 私たちの仕事はユーザーを助けることであり、ユーザーを混乱させることではありません。したがって、この欠陥はすでにこのオプションを考慮から除外するのに十分です。

見当識障害を回避する唯一の方法は、GPSマーカーを「テレポーテーション」なしでスムーズに移動することです。つまり、位置情報の読み取りよりもはるかに頻繁に移動する必要があります。 このような動きを保証するには、センサーからの実際の読み取り値の中間点を何らかの方法で計算し、次の読み取り値が受信されるまでそれらを使用する必要があります。 これらの中間点を計算するための特定のアプローチは、ナビゲータプログラムの全体的な人間工学に最終的に大きく影響するため、特別な注意を払う必要があります。

2.ユーザーの位置を表示する2番目の方法は、中間点の生成に対する最も明白なアプローチ-最後の実際のGPS測定値間の補間に関連しています。 ポイントは、マーカーを最後から2番目のカウントから最後まで一定の時間移動し、既知の数学関数の1つを使用して必要な頻度で中間ポイントを計算することです（最も単純なオプションは線形補間です ）。 この方法でナビゲータを使用する方がはるかに便利ですが、欠点もあります。

最も無害なのは、事前に補間時間を設定する必要があることです。 1秒でインストールすると、GPSの読み取りと読み取りの間に正確に多くの時間が経過する上記の理想的な場合にのみうまく機能します。 経過時間が短い場合-問題ではありませんが、現在の位置から新しいターゲットへの移動を開始できます。 しかし、それ以上の場合、マーカーは静止してセンサーからの新しい座標を待つ必要がありますが、その時点ではユーザーの車が動く可能性があります。

さらに深刻な問題があります。 新しい参照を受信した時点で、マーカーはせいぜい前の実際のポイントに位置しています。 ユーザーの観点から、別の位置決め誤差を導入します。この値は、読み取りと読み取りの間の時間に車が移動した距離以上です。 速度が100 km / hの場合、この値はほぼ28メートルに達します。これは、考えられる測定エラーと相まって、ユーザーに提供される情報の信頼性が低くなります。

巨大なサイズのGPSマーカーを作成し、画面の4分の1をブロックして、説明した位置決め方法の欠点を慎重に覆い隠すこともできますが、直接の偽造を行うことはユーザーにとっても私たち自身にとっても無礼です。 表示されたデータの精度と適時性は、ナビゲーターの開発において、外部の美しさと動きの滑らかさほど重要な基準ではありません。

3.位置精度の新たな要件を考慮すると、新しいGPS基準が到着する少し前に、この新しい基準に可能な限り近い位置にマーカーを配置する必要があります。 それは実際、長い間ではありませんが、未来を垣間見るものです。 タイムマシンの発明により、人類は私たちのためにひどくやっていますが、私たちにはまだ救いがあります。 車の動きは不活性であるため、その動きの速度と方向を即座に変更することはできません。その場合、ユーザーが最後の位置基準と未来の間にある場所をある程度正確に予測することができます。 ほとんどの場合、予測誤差が2番目の方法の誤差よりも小さくなることを達成できれば、ナビゲーターのユーザーの生活を大幅に促進します。

正確な科学におけるこの種の予測は、外挿と呼ばれます。 このようにして、上記のすべての基準を満たす3つ目のルートガイダンス方法の開発を試みます。 次に、数学的モデルに焦点を当てるので、より形式的な表現言語に頼らなければなりません。

位置推定を使用した経路案内

ナビゲーションルートへのユーザーの地理的位置の魅力により、2次元の地理座標から1次元の座標に移動できることは以前に言及しました-ルートの開始点に対してオフセットします（簡潔にするために、明確にすることなく「オフセット」という用語を使用します）。

私たちに届いたデータを思い出して、それらの表記法を紹介します。

-GPS位置をルートラインに描画することで得られる実際のオフセット測定値。
-対応するオフセットサンプルの到着時間。
これで、実際には、入力データのリストは終了します。 それらから最大限の有用な情報を絞り出さなければなりません。

最終的に、バイアス外挿関数を構築する必要があります 、これは車の実際のダイナミクスに近く、同時にルート全体に沿ったGPSマーカーのスムーズな移動を保証します（ルートの完了は個別に処理されるため、その長さは何にも影響しません。したがって、ルートは無限であると見なします）。 視覚的な滑らかさを確保するには、滑らかさの条件で十分です。 、つまり、マーカーの位置も速度も急激に変化することはありません。 言い換えれば、関数 定義領域全体で、その一次導関数（以降-時間内）とともに連続している必要があります。

各実際のオフセットカウントには、実質的に新しいモーション情報が含まれることに注意してください。 たとえば、長時間にわたって車が均一に運転され、その後加速し始めた場合、ナビゲーターは次のカウントダウンの到来時にのみ加速を「感じる」ことができます。 arbitrarily意的に長い期間未来を見ることはできないため、着信する新しいGPSの読み取り値はすべて、通常、目的の機能の動作を変更します 、1つの分析式で設定することはできません。 代わりに、関数を区分的に定義してみてください。 これを行うには、最初に簡単な問題を解決します。

直接区分的外挿

変位の外挿のような関数を構築します そのように 1番目のカウントの値は、到着前に十分な時間にわたってユーザーの実際の位置を予測しました カウントダウン。 私たちが持っているすべての有用なデータは、最大で一連の読み取り値です 包括的にそれらのそれぞれの受信時間と一緒に。

有限の違いを覚えて、我々は車の速度を評価する機会があることに注意する -最後の変位と最後から2番目の変位との間のセグメントの長さを、対応する時間間隔で除算した時点。


どこで -カウントに応じた速度の推定、および -外挿関数の導関数 構築しようとしています。

同様に、高次の派生物-加速度、ジャークなど：


これらの式からわかるように、変位のますます上位の導関数の推定値を取得するには、現在のものに先行するますます多くのサンプルを考慮する必要があります：速度を決定するには、加速-3、ジャーク-4などのために2つのサンプルが必要です。 一方では、予測で考慮する動きの動的特性が大きいほど、モデリング能力が向上します。 一方、「古い」カウントに含まれる有用な情報は、関連性を劇的に失います。 たとえば、毎分30 km / hの速度で運転したという事実は、現時点では役に立ちません。それ以降、数回加速したり、減速したり、停止することさえできました。 このため、バイアスのますます古い派生物の推定値は現実から遠ざかりつつあります。 さらに、変位の一般的な分析モデルに対する特定の導関数の計算における誤差の寄与も、この導関数の次数の増加とともに増加します。 その場合、ある順序から始めて、明確にするのではなく、有限差分を使用して推定した動的特性は、モデルを損なうだけです。

実際のデータをチェックした結果によると、ジャークスコアは 、特にGPS信号の「平均的な」品質の場合、それはすでにそれよりも多くの害を与えるほど十分に悪いです。 一方、幸いなことに、車のダイナミクスの最も頻繁なシナリオは、それぞれ0度、1度、および2度の多項式の方程式で記述される、静止、均一、および可変の運動です。

一様に変化する動きの2次モデルは、ほとんどの交通状況を説明するのに十分であり、動的特性（速度と加速度）の定性的推定値は多かれ少なかれあります。 物理学のコースを思い出して、目的の外挿関数の分析式を作成することができます。


ただ一つのステップを踏むだけです：スコープ ある時点から始まります したがって、この瞬間から計算で時間を計算する方が便利です。

その結果、関数は次の形式を取ります。


この関数の注目すべき特徴は、定義のドメイン全体での滑らかさです。これは、前述のように、問題のステートメントに含まれています。

次に、デバイスからいくつかの実際のバイアスサンプルを取得し、各間隔でそれらを外挿しようとします（ただし、 前に決定 カウントダウン時 次の機能に直接行きます 、より新しいデータがあるため）



明確にするために、比較的低品質のGPS信号でデータを取得したことを予約しますが、図の状況は非常に現実的であり、どのユーザーでも発生する可能性があります。

各外挿多項式の滑らかさ 対応する時間間隔ではっきりと見えますが、問題は、間隔の接合部で一般的な灰色の曲線にギャップがあり、時には非常に目立つことです。

ギャップを 外挿誤差による時間の瞬間 。 確かに、この値は、各予測がその時間間隔の終わりに向かってどのような不正確さを持っているかを示しています。 エラー値は、次の式を使用して計算できます。


悲しいかな、関数自体を変えることでエラーをゼロに減らします 、将来のビジョンの100％の精度に相当するため、それを行うことはできません。 したがって、単一の関数を構築するという最初の問題を解決するには 区分的外挿多項式を何らかの方法で「接着」する必要があります。つまり、ジョイントで発生するエラーを修正する必要があります。

エラー修正アプローチ

上記で選択した表記に従って、新しい参照が到着するまでに非公式に言うことができます 私たちはポイントにいます 、つまり エラーの量だけ実際の位置に対してシフト 時間までに蓄積 前の外挿多項式 。

一方では、ユーザーに与えられたデータと現実との対応という観点から、エラーを修正する最良の方法 機能のギャップがあります 次の多項式の開始点まで ただし、この場合は地図上のマーカーを再び「テレポート」し、ドライバーを混乱させるため、これを行うことはできません。

明らかに、値の瞬間的な変化 無効な場合、エラー修正にはゼロ以外の時間がかかります。 また、エラーの蓄積を防ぐために、次のカウントが到着する前にエラー修正を完了することをお勧めします。

バイアスサンプル間の時間間隔の確率的性質により、正確な補正時間を確実に決定することはできません。 したがって、最初の近似として、特定の定数値の形式でエラー修正時間を修正します。 将来的に経験的に選択します。

再び非公式の言語で話すと、その時点からエラーの修正が必要です 時間内に 次の外挿多項式-曲線にスムーズに「戻る」 。

エラー修正プロセスを説明するために、個別の修正機能を導入すると便利です。 ある時点で 対応する補正関数が値を引き継ぎました 、そしてその瞬間から ゼロに等しくなりました：


そのような補正関数を対応する補間多項式で追加すると、キーポイントで そして バイアス補正を提供します。


調整済みオフセット関数を呼び出します 外挿多項式と対応する補正関数の合計：


上記の補正関数の特性により、関数の非常に重要な特性が得られていることに注意してください。 -それらはすでに「オフセットでステッチ」されています。 ポイントのギャップを許容しない ：


調整された機能のセット 望ましい変位モデルの役割を主張できます 1つの状況ではない場合、すべての時点で定義されます：点で不連続変位が存在しないにもかかわらず 、一般的な場合のこの関数セットの導関数はまだ引き裂かれています。

具体的には、初期要件には普遍的な滑らかさの条件が含まれているため、一次導関数の不連続性である速度に関心があります。 、つまり 速度の広範な連続性のための条件。 これを念頭に置いて、補正機能の要件を拡張する必要があります 調整された関数の導関数も「ステッチ」する ：


この方程式は、調整された関数の全体の滑らかさの条件です。 方程式の両側の修正された関数の定義を代入すると、次のようになります。


先に修正時間が経過した後 補正関数はゼロ値を取ります。 修正関数にもう1つの要件を追加します-修正時間が経過した後、その導関数もゼロ値を取るようにします。


次に、補正時間は常にサンプル間の間隔よりも短いと仮定すると、導関数は 次のカウントダウン時の修正関数 すでにゼロになります。 次に、滑らかさの状態に戻ると、次のようになります。


ここから急行 ：



に注意してください は有限差分を使用して行われた速度の推定値であり、これを代入します。


右側は、速度の外挿誤差を表します。これは、前の外挿多項式から取得した速度と「実際の」速度基準との差です。 これで、補正関数の境界条件をまとめることができます。


これらは次のような言葉で説明できます-修正関数を見つける必要があります：

• 補正間隔の開始時に、その値はバイアス外挿誤差と一致しました。
• 補正間隔の開始時に、その導関数の値は速度外挿誤差と一致しました。
• 補正間隔の終わり以降では、関数自体の値とその導関数はゼロでした。

エラー訂正機能の選択

補正関数の単一の分析式を取得することに注意してください 上記の4つの条件を完全に満たすことは非常に困難です。 問題は、修正時間が経過した後の定義領域の一部です。 、-数値軸の残り全体で関数とその導関数のゼロ値を達成する必要があります。 タスクを簡素化するために、補正関数の目的の分析式のドメインを補正間隔に減らします 、およびその上限の後に、関数の値とその導関数を自明にゼロと見なします（幸い、プログラムコードのレベルでは、分岐の存在によりこのような機会があります）。

形式的には、この手法を考慮すると、区分的補正関数は補正間隔の式であり、定数0はさらにポイントでの境界条件に従います 補正関数自体もその1次導関数も壊れません。高階微分の不連続性は私たちには興味がないので（望ましい関数の滑らかさを損なうことはありません）、将来の補正関数のゼロ「テール」については言及せず、より便利な形で境界条件を再定式化します。


速度の外挿の誤差を ：


次に、次の分析式を定義する必要があります 。プログラムの人間工学的な要件により、境界条件に加えて、GPSマーカーが「けいれん」しないように、補正関数は補正間隔で極値とキンクをできるだけ少なくする必要があります。

これらの要件に適合する最も単純な関数は、多項式です-可能な限り時間の最小の多項式です（理論的には、たとえば、正弦も基本関数間で同様の特性を持っていますが、その値の計算はプロセッサ時間の観点から複雑です）。

境界条件は4つの自明でない方程式のシステムであるため、補正関数の十分なパラメーター化を提供する多項式の3次は3次です。そのための分析式を構築する場合-thカウントダウンの瞬間から時間をとる方が便利です（定義とまったく同じ方法で、必要な多項式は次の形式を取ります）。


この式を境界条件のシステムに代入し、定数に関して解く そして 次の値を取得します。


その結果、説明した方法で補正関数を決定した場合、補正された関数は常に滑らかな単一の外挿関数にマージされます。かさばるので、完全な表現はしません。

注：修正時間を選択するとき、最後の不正確さは仮定に残っていました-私たちの推論は、常にサンプル間の間隔よりも短いという条件に基づいていました：


構築されたモデルの優れた機能は、サンプル間の平均時間を超えないように選択するのに十分であることです：個々の間隔が短い場合、短すぎる間隔で修正する時間がなかったエラーの一部が1つ修正されます以下から。これを行うには、外挿誤差を通常の外挿関数ではなく、調整された ：


次の図は、実際のデータに基づいて構築された最終外挿関数のグラフの例を示しています。



形式的な問題は解決され、結果の曲線はすべての規定された条件を満たします。これでリラックスすることは可能ですが、現実の世界の特徴は、構築された理想的なシステムに特定の困難をもたらします。

それらのいくつかをより詳細に検討し、以下で行われるすべての決定が数学モデルの外部のプログラムコードで直接実装されることを予約します。

数学モデルの実際の条件への適応

反対方向へのマーカーの移動の禁止

最後のグラフでは、実際の数に応じて、ユーザーがルートに沿って排他的に前方に移動しても、場合によっては機能が低下し始めることがわかります。これは、予測によって移動速度が大幅に過大評価されている場合に発生します。一方、実際には、車が反対方向に移動するのは、ドライバーが本当にリバースギアを入れて戻った（非常にまれなケース）、またはUターンを完了したという2つの理由だけです。

Uターンの場合、交通状況が大幅に変化するため、ナビゲーションルートの再構築が必要です。これは別のトピックであり、この記事の範囲に当てはまりません。

位置を外挿した結果を使用する場合直接、マーカーがルートの開始に向かって移動するすべての動きのうち、消失する少数派は、同じ方向の車の実際の動きに対応します。これを踏まえて、ユーザーを誤解させないように、ルートを再構築せずにマーカーを完全に禁止することが決定されました。

このような厳しい条件は、数学の言語で説明することは困難ですが、プログラムコードで実装することは比較的簡単です。まず、モデル時間の離散的な性質を考慮します-コンピューターの機能の特徴により、いずれの場合でも、選択されたいくつかの時点で外挿の結果を受け取ります。

その場合、外挿バイアスが減少しないことを確認することは難しくありません。取得した新しい値を前の値と比較するだけで十分であり、現在の値が小さい場合は前の値に置き換えます。この手法の明らかな無礼さにもかかわらず、外挿関数の滑らかさに違反することはありません。滑らかな関数に沿って後方に移動を開始するには、最初に完全に停止する必要があるためです。
将来的には、逆方向の移動を防ぐために数学的に正しい値を古い値に置き換える操作モードは、強制停止モードと呼ばれます。

外挿誤差が大きすぎ、サンプル間の間隔が長すぎる

ある意味で定性関数を構築したという事実にもかかわらず、外挿誤差は許容できない値に達することがあります。これらの場合、プログラムは通常の方法でエラーを修正しようとするのをやめるべきです。何らかの理由で新しいオフセットカウントが長すぎて到着しない場合、外挿データが関連しなくなる別の状況が発生します。最後のカウントを受信した瞬間からモデリング機能が劇的に低下します。予測の試みと悪意のある嘘の間の境界線を越えないために、通常、モデルに依存するコストは3秒以内です。

簡単にするために、最初の否定的な状況を修正不可能なバイアスエラーと呼び、2番目の状況を修正不可能な時間エラーと呼びます。

これらのタイプのエラーにはそれぞれ2つの方法で対処できます。

• 上記の強制停止モードに入ります。このアプローチの利点は、エリアの地図上でジオロケーションマーカーのスムーズな移動を維持することです。ただし、強制停止モードが長ければ長いほど、ユーザーに実際の位置を知らせるのが悪くなります。
• GPSマーカーを瞬時に最後のカウントの場所にテレポートします。ここでは、逆に、ユーザーに提供される情報の正確さのために人間工学を犠牲にします。

私たちのアプリケーションでは、スムーズな注意が特に細心の注意を払われているため、最初の方法が選択されました。

長期強制停止モード

強制停止モードへの移行は、GPSマーカーの逆方向移動を禁止するために、精度の低い位置データの発行に関連付けられます。特に不利な場合にユーザーに誤解を与えないように、モデルには、モードに入る理由に関係なく、指定された期間後にマーカーを最後の実際の位置に「テレポート」することで強制停止モードを中断する機能が追加されています（外挿または修正不可能なオフセット/時間エラーの数学的結果） 。この時点で、動きの滑らかさでさえ、正確さの「残り」のために犠牲にしなければなりません。

結論

行われた作業の結果、出力データの精度と表示の視覚的人間工学のバランスが取れるように、ルートガイダンスを改善することができました。特に、良好な信号のためにGPSセンサーから高品質のデータを受信する場合、ユーザーは非常に快適に感じるでしょう。

説明した外挿システムは、ジオロケーションを使用する他のアプリケーションで使用できます。経路の概念、したがって開始点からの変位が存在しない場合、1次元スカラーからの数学モデルを多次元ベクトルに一般化できます。モデル自体をコードに実装しても、一般的なプログラミング言語では問題は発生しません。これには単純な算術演算のみが必要です。

さらなる開発パスに関しては、記事の冒頭で述べたセンサーからの「生の」位置データの測定誤差に注意する価値があります。予測のエラーをすでに修正しようとしている場合、測定エラーとの闘いは、将来の作業の別のレイヤーであり、困難ですが、そこからはそれほど興味深いものではありません。表示される情報の正確性に関するこの分野での潜在的な成功の利点を過大評価することは困難です。