GPSの再考：Uberでの新世代測位システムの開発

全地球測位システム （GPS）を使用した測位とナビゲーションは、私たちの日常生活に深く浸透しており、Uberサービスにとって特に重要です。 迅速で効果的なピックを整理するために、当社のGPSテクノロジーは、関連する乗客とドライバーの位置を把握するとともに、ドライバーの現在位置から乗客を乗車する必要がある場所、そして目的地までのナビゲーションガイダンスを提供する必要があります。 このようなシステムを円滑に運用するには、乗客とドライバーの位置をできるだけ正確にする必要があります。



1973年に（文字通り）GPSを開始した後、私たちは世界をよりよく理解し始め、利用可能な計算能力が指数関数的に増加し、ロボット工学などの分野の不確実性をモデル化する強力なアルゴリズムを開発しました。 私たちの生活がGPSにますます依存するようになったという事実にもかかわらず、基本、つまりGPSの動作方法はあまり変化していないため、パフォーマンスが大幅に制限されています。 私たちの意見では、1973年にそれぞれGPSを使用する場所と方法、および計算能力と結果を改善するために使用できる追加情報に関して真実であったいくつかの初期の仮定を再考する時が来ました。



GPSは晴天下でも十分に機能しますが、その接近位置は非常に不正確（50メートル以上の誤差を伴う）である可能性があり、何よりも正確性が必要な場合があります：ユーザーの多くが住んでいる人口密集した高層都市部。 この問題を克服するために、AndroidのGPSソフトウェアのアップグレードを開発しました。これは、3Dマップを使用し、 Android GNSS APIを介して利用可能なGPSデータの複雑な確率計算を実行するクライアントサーバーアーキテクチャにより、都市環境の位置の精度を大幅に改善しました。



この記事では、都市環境でGPSがうまく機能しない理由を説明し、サーバーインフラストラクチャにスケールで展開された高度な信号処理アルゴリズムを使用してGPSを修正する方法をまとめます。





画像1：上のGIFは、サンフランシスコのUber HQからのピッキングに関する標準GPS（赤）と改善された位置近似（青）の比較を示しています。 おおよその位置は実際の乗客の経路に非常に近いことが判明し、GPSは大幅な逸脱を示しました。

少しのGPS / GNSSバックグラウンド

アプローチを詳細に説明する前に、複数階建ての都市環境でGPSが不正確になる理由を理解するために、GPSの仕組みを簡単にまとめてみましょう。



GPSは、約2万kmの高度の軌道上に位置する、米国政府によって制御される30を超える衛星のネットワークです。 （今日のほとんどのスマートフォンは、同様のロシアのGLONASS衛星から信号を受信できます。）これらの衛星は、スマートフォンのようなGPS受信機が記録できる無線周波数信号を送信します。 これらの衛星がこれらの信号を発信する時期を通知することが重要です。



受信機が信号を処理する各衛星について、捕捉時間と打ち上げ時間（飛行時間）の差に光の速度が乗算され、結果の値は擬似距離と呼ばれます。 衛星と受信機のクロックが同期しており、信号が視線に沿って移動する場合、この値は衛星までの実際の距離に等しくなります。 ただし、クロックは同期されていないため、受信機は4つの未知数の方程式、球上の独自の3D座標、およびクロックの偏差を解く必要があります。 したがって、これらの4つの未知数を取得するには、少なくとも4つの衛星（4つの方程式）が必要です。



時計のずれを無視すると、GPS受信機によって生成された位置の近似、衛星を中心とする球体の交点、および各球体の半径を与えられた擬似距離で直感的に解釈できます。 実際には、GPS受信機は非常に多くの衛星（オープンフィールドで最大20のGPSおよびGLONASS衛星）からの信号を処理し、最小数を超える方程式を取得することで、ノイズ、障害物などに対する追加の耐性が得られます。 GPSおよびGLONASSに加えて、いくつかの新しい/将来の受信機は、他の衛星システムからの信号を処理できる/できるようになります。 他のいくつかのガリレオは、欧州連合、インドのIRNSS、および中国のBeiDouが運営する衛星ナビゲーションシステムを打ち上げています。 より一般的な用語GNSS （グローバルナビゲーション衛星システム）は、これらのシステムを対象としています。 （この用語はさらに使用します。）





画像2：GPS受信機の計算のこの単純化された解釈では、球体は既知の衛星位置の中心で交差します。

都市環境でGNSSの位置が不正確な理由

GNSSベースのポジショニングには、受信機が擬似距離を計算する各衛星への見通し線があるという非常に強い主張があります。 このメカニズムは、オープンエリアではうまく機能しますが、下の図3に示すように、都市環境ではうまく機能しません。





画像3：視界の制限と強い反射により、大きなGPSエラーが発生する可能性があります。



多くの場合、建物は衛星の直視を制限するため、受信機は他の建物からの反射に対応する信号を処理します。 この現象から生じる擬似距離の大幅な不正確さ（正のバイアス）は、位置の近似誤差につながる可能性があり、都市の峡谷で50メートル以上に達する可能性があります。 徒歩や車で旅行したり、大都市でUberを注文した私たちのほとんどは、自分でこれらの問題を経験しました。

救助する信号強度

位置を決定する精度を高めるためのアプローチは、各GNSS信号制限から機能を作成し、標準の受信機に問題を引き起こします。 どうやって？ Android電話機の場合、LocationManager APIは電話機のおおよその位置だけでなく、表示されている各GNSS衛星の信号対雑音比（SNR）も提供します。 「信号強度」に関する情報を3Dマップと比較すると、位置に関する非常に貴重な情報を取得できます。 下の画像4は、SNR衛星と3Dマップを使用して、道路のどちら側にいるのかを推測する方法の簡略版を示しています。





画像4：3Dマップと組み合わせた衛星信号強度は、非常に貴重な位置情報を提供します。



詳細に突入すると、私たちのアプローチは、数学的な枠組みに次の仮定を置くことに基づいています。衛星のSNRが低い場合、見通し線が制限されるか、影になる場合があります。 SNRが高い場合、LOS（見通し線）はおそらくきれいです。 ここでは「多分」指定子が重要です。受信機がシャドウゾーンにある場合でも、強く反射した信号が届く可能性があり、クリーンなエリアにある場合でも、受信信号は弱い場合があります（LOSと反射パス間の破壊的な干渉のため） マルチパス減衰 ）。 また、ほとんどの場合、3Dマップは完全に正確ではなく、トラックのようにマップに反映されていない大きな移動オブジェクトにランダムな制限を送信することはありません。 これにより、プロセスに不確実性が追加されます。

レイトレーシングを使用した確率的シャドウマッピング

衛星の信号強度が有用な位置情報を運ぶという直感的な仮定は良いように聞こえるという事実にもかかわらず、それは確率フレームを使用して具体化されるべきです。 受信機の可能な位置については、3Dマップでこの位置から衛星へのビームがブロックされているかどうかを確認できます。 次に、モデルを使用して、LOSおよびシャドー条件の下でSNRの確率を分布させ、この衛星のSNRの最も可能性の高い値を決定します。 たとえば、位置に影が付いている場合、SNRが高くなる可能性は低くなります。 衛星のSNRに基づく特定の位置の全体的な確率は、さまざまな衛星に関連付けられた確率の積です。 可能な位置のグリッドでこれを行うことにより、確率的な表面、または衛星の信号強度のみに基づいて受信機の可能な位置のヒートマップを取得します。 この手順を確率的シャドウマッチングと呼びます。





画像5：確率的なシャドウマッチングのために、1つの可能な場所から各衛星までのレイトレーシング。 これは、数千の可能性のある場所で行われます。



確率的シャドウマッピングからの確率的表面またはヒートマップは、衛星SNR測定からの情報を結合します。 下の画像6に見られるように、このヒートマップは非常に複雑になる可能性があります。 多くの場合、道路の特定の側面に対応する多くの個別の強く分離されたホットスポット（局所的最大値）がありますが、誤った位置（ファントムなど）に対応することもあります。 アプローチを絞り込み、ファントムを回避するには、この情報をさらに多くの情報と組み合わせる必要があります。





画像6.衛星の信号強度を使用して計算された位置のヒートマップには、多くのホットスポットが含まれる場合があります。 上記の例では、改善された位置近似（不確かさのある青いパス、黒い楕円）は実際のパス（黄色のパス）に従いますが、従来のGPS（不確かな赤いパス、灰色の楕円）は不正確です。

部分フィルターを介して情報を結合する

Androidフォンの場合、衛星の信号強度に加えて使用する情報は通常、標準のGNSS位置補正ですが、Wi-Fiベースの測位を含むAndroid融合位置もあります。 この場所は非常に不正確になる可能性があるため、標準のGNSS修正と確率的シャドウマッチングを一度だけ組み合わせてしまうと、通常パフォーマンスが低下します。 衛星信号の強度に関する情報を活用するために、私たちは市街地でのGPSの信頼性を低くしています（画像6の灰色のGPS不確実性楕円は使用する通常のモデルであり、GPSを改善するための黒い不確実性楕円はアルゴリズムの結果です）。 次に、以前の測定値を使用し、アプリケーションに適合したモデル（たとえば、車に対する歩行者）を使用して、時間の経過に伴う位置の変化に制限を課します。 パーシャルフィルターを使用してこれを実現します 。これは、一連の浮遊粒子によって、任意の時点でのレシーバー位置の分布の確率を近似します。 言い換えれば、電話がどこにあるかを想定し、数千の可能な場所（つまり、パーティクル）を使用します。



時間の経過とともに、粒子の確率的な重みと位置は、測定値と動きのパターンに基づいて進行します。 確率的シャドウマッチングからのヒートマップには非常に多くの局所的最大値があり、GNSS補正にはそのような大きな外れ値があるため、カルマンフィルターや拡張カルマンフィルターのような通常の手法を使用することはできません。ベル。 部分フィルターを使用すると、複雑さを増す代わりに、任意の分布を近似することができ、ここでサーバーアーキテクチャが機能します。





画像7：部分フィルターによって提供されるホットスポットの重心として取得された位置の近似値は、非常に大きなGPSエラーを修正することがよくあります。 改善されたGPSの不正確な半径（白い円）は、一連の粒子のカットに基づいており、通常、位置誤差が大きい場合でも純粋なGPSによって返される小さな不正確な半径（黒い円）よりも現実的な測定値です。

信号処理から大規模ソフトウェアまで

部分フィルターとレイトレーシングの組み合わせにより、非常にステートフルなサービスを備えたサーバーのバックエンドエコシステムが複雑になります。





画像8：強化されたUber GPSシステムは、部分フィルターサービス、3Dタイルマップ管理サービス、マネージャーサービス、Uber HTTP API、クラウドストレージで構成され、他のUberサービスと統合されます。



ゲームには2つのタイプの状態があります。各ユーザーの部分フィルターの状態と、領域ごとのレイトレーシングに使用される3Dマップです。 部分フィルターを使用するには、サーバーアフィニティレベルが必要です。 正しい部分フィルターを更新するには、サービスへの新しいリクエストをそれぞれ同じバックエンドサーバーに送信して処理する必要があります。 さらに、3Dカードのサイズが大きいため、各バックエンドサーバーにはRAMに少量の3Dワールドが含まれている場合があります。



各サーバーには数平方キロメートルの地図データしか含めることができないため、すべてのサーバーがすべてのユーザーにサービスを提供できるわけではありません。 ソリューションのバックエンドシステムの実装には、3Dサーバーマップを考慮したセッションルーティングレイヤーの作成が必要でした。 内部テストとパフォーマンス評価に加えて、以下の図9に示すように、ドライバー用のUberアプリケーションの内部バージョンを使用して、独自のAndroidデバイスでテストを開始しました。





画像9：ドライバーアプリの内部バージョンの赤と青のドットの比較により、Uberの従業員は世界中のどこでもソリューションをテストできました。

前進する

乗客とドライバーの位置を正確に決定することは、どこでも、すべての人に水を供給するのと同じ信頼性で輸送を提供するというユーバーの使命を果たすための非常に重要な条件です。 私たちの使命を達成するために、私たちのセンシング、インテリジェンス、および研究チームは、サーバーインフラストラクチャの処理能力と組み合わせて、モバイルデバイスでセンサーとコンピューティングの創造的な使用を使用して位置決定を改善するためのさまざまなアプローチに取り組んでいます。 高度な信号処理、機械学習アルゴリズム、ソフトウェアの大規模な組み合わせは大きな可能性を秘めています。私たちは常に、才能と意欲の高い個人（ソフトウェアおよびアルゴリズムエンジニア、データ視覚化エンジニア、機械学習エンジニア）を探して、この可能性の実現を支援しています。



ダニー・アイランド、アンドリュー・アイリッシュ、ウパマニュ・マドハウ、ブライアン・サンドラーは、ユーバーのセンシング、推論、研究チームのメンバーです。 ダニー、アンドリュー、ウパマニュは、カリフォルニア大学サンタバーバラ校でこの研究を行った元のグループの一員でした。 スタートアップとしてこの作業を開始した後、彼らは、Air LiDARの公開データを使用して作成された3Dマップを使用して、サンフランシスコでの位置決定を改善するサーバー側部分フィルタリングを実証しました。 彼らは2016年7月にUberに参加しました。