(57)【要約】  本開示は、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するための人工知能システムおよび方法を含む。地図は、複数のグリッドにグリッド化され、複数の区画に分割される。本方法は、地図におけるジオフェンスの情報を取得するステップと、複数のグリッドからジオフェンスの境界グリッド系列を判定するステップと、を含む。本方法は、地理的領域における少なくとも1つの囲繞エリアを識別するステップと、囲繞エリアが2つ以上の区画を横切ると判定すると、囲繞エリアを2つ以上のサブエリアにセグメント化するステップと、を含む。本方法はまた、各サブエリアについて境界グリッドを判定するステップと、各サブエリアについてサブエリアにおける内部グリッドを識別するステップと、を含む。本方法は、境界グリッドおよび内部グリッドを収集することにより、地理的領域におけるグリッドを識別するステップをさらに含む。
2021508856.tif 000002
【特許請求の範囲】
【請求項１】
複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された人工知能システムであって、
地図と地理的領域を識別するための1セットの命令とを記憶する、少なくとも1つの記憶媒体と、
前記少なくとも1つの記憶媒体と通信する少なくとも1つのプロセッサであって、前記1セットの命令を実行すると、前記少なくとも1つのプロセッサは、
前記地図の少なくとも一部を前記少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードし、
前記地図の前記少なくとも一部の表示を生成し、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、独立にインデックス付けされ、
前記地図における地理的領域のジオフェンスの情報を取得し、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定し、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別し、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化し、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定し、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別し、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別する、
ように指示される、少なくとも1つのプロセッサと、
を備える、人工知能システム。
【請求項２】
前記ジオフェンスの前記情報は、複数の境界点に対応する1セットの座標対を含み、
前記ジオフェンスの前記境界グリッド系列を判定するために、前記少なくとも1つのプロセッサは、前記複数のグリッドから前記複数の境界点に対応する前記境界グリッド系列を識別し、
以下のステップ、すなわち、
前記複数の境界点から2つの隣接する境界点を取得するステップと、
前記2つの隣接する境界点が同じグリッドに対応するか否かを判定するステップと、
前記2つの隣接する境界点が同じグリッドに対応するという判定に応じて、前記2つの隣接する点のうちの1つを除去するステップと、
前記2つの隣接する境界点が2つの異なるグリッドに対応するという判定に応じて、前記2つの隣接する境界点の間で境界点を補間するステップと、
前記複数の境界点に対応する前記境界グリッド系列を更新するステップと、
を含む1つまたは複数の動作を実行するようにさらに指示される、請求項1に記載の人工知能システム。
【請求項３】
前記境界グリッド系列は、前記ジオフェンスが通過する、前記地図の前記複数のグリッドからのグリッドを含み、
前記少なくとも1つの囲繞エリアを識別するために、前記少なくとも1つのプロセッサは、
前記境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定し、ピボットグリッドが少なくとも2つの同じグリッドインデックスに対応し、
前記境界グリッド系列が1つまたは複数のピボットグリッドを含むという判定に応じて、前記1つまたは複数のピボットグリッドのそれぞれについて、前記ピボットグリッドの一方の側にある前記地理的領域におけるエリアを、第1の囲繞エリアとして、また前記ピボットグリッドの他方の側にある前記地理的領域におけるエリアを、前記第1の囲繞エリアとは異なる第2の囲繞エリアとして識別する、
ようにさらに指示される、請求項1に記載の人工知能システム。
【請求項４】
前記少なくとも1つの囲繞エリアを識別するために、前記少なくとも1つのプロセッサは、
空のスタックおよび空の補助地図を生成し、
前記境界グリッド系列の各グリッドについて、
前記境界グリッド系列からグリッドを順次取得し、
前記グリッドに対応するグリッドインデックスが前記補助地図にあるか否かを判定し、
前記グリッドインデックスが前記補助地図にないという判定に応じて、前記グリッドインデックスを前記スタックにプッシュし、前記グリッドインデックスを前記補助地図に入力し、
前記グリッドインデックスが前記補助地図にあるという判定に応じて、前記グリッドインデックスに対応する前記グリッドを前記1つまたは複数のピボットグリッドのうちのピボットグリッドとして指定し、前記グリッドインデックスをピボットグリッドインデックスとして指定し、前記スタックの一番上にある前記グリッドインデックスが前記ピボットグリッドインデックスと同じになるまで、前記スタックから前記スタックにあるグリッドインデックスをポップし、前記ポップされたグリッドインデックスに対応するグリッドを前記第1の囲繞エリアの境界グリッドとして指定し、
前記スタックに残っているグリッドインデックスに対応するグリッドを、前記第2の囲繞エリアの境界グリッドとして指定する、
ようにさらに指示される、請求項3に記載の人工知能システム。
【請求項５】
前記ジオフェンスは、中心および半径によって定義される円に基づいて判定され、
前記地理的領域において前記少なくとも1つの囲繞エリアを識別するために、前記少なくとも1つのプロセッサは、
前記円上で複数のサンプル点を所定のサンプル間隔でサンプリングし、
前記複数のサンプル点に基づいて前記地理的領域における前記少なくとも1つの囲繞エリアの境界グリッドを判定する、
ようにさらに指示される、請求項1に記載の人工知能システム。
【請求項６】
前記所定のサンプル間隔は、前記円の前記半径および前記複数のグリッドのうちのグリッドに関連する解像度に関連付けられる、請求項5に記載の人工知能システム。
【請求項７】
前記少なくとも1つのプロセッサは、
前記複数のサンプル点のうちの2つ以上のサンプル点が同じグリッドに対応すると判定すると、1つのサンプル点のみが前記グリッドに対応するように、前記2つ以上のサンプル点から1つまたは複数のサンプル点を除去する
ようにさらに指示される、請求項5または6に記載の人工知能システム。
【請求項８】
前記少なくとも1つの囲繞エリアを2つ以上のサブエリアにセグメント化した後、前記少なくとも1つのプロセッサは、
前記2つ以上のサブエリアが前記複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定し、
前記重複辺グリッドを前記2つ以上のサブエリアの境界グリッドとして前記2つ以上のサブエリアに追加する、
ように指示される、請求項1に記載の人工知能システム。
【請求項９】
前記複数のグリッドから前記サブエリアにおける内部グリッドを識別するために、前記少なくとも1つのプロセッサは、
スキャニング行列を初期化し、前記スキャニング行列は複数のセルを含み、前記スキャニング行列の各セルは第1の値を有し、
前記スキャニング行列の第1の複数のセルのそれぞれに第2の値を入力することによって、前記スキャニング行列に対して第1の更新を実行し、前記第1の複数のセルは、前記サブエリアの前記境界グリッドに対応し、
前記第1の値を有する、前記第1の更新後の前記スキャニング行列の各セルについて、前記セルに対応する前記グリッドが前記地理的領域にあるか否かを判定し、
前記セルに対応する前記グリッドが前記地理的領域にあるという判定に応じて、
前記スキャニング行列の前記セルに第3の値を入力することによって、前記スキャニング行列に対して第2の更新を実行し、
前記第3の値を有する前記セルに対応するグリッドを前記サブエリアにおける前記内部グリッドとして指定する、
ように指示される、請求項1に記載の人工知能システム。
【請求項１０】
前記第2の値と前記第3の値とは互いに同じである、請求項9に記載の人工知能システム。
【請求項１１】
地図と地理的領域を識別するための1セットの命令とを記憶する少なくとも1つの記憶媒体と、前記少なくとも1つの記憶媒体と通信する少なくとも1つのプロセッサと、を有するコンピューティングデバイス上で実施される、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するための方法であって、前記方法は、
前記地図の少なくとも一部を前記少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードするステップと、
前記地図の前記少なくとも一部の表示を生成するステップであって、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、独立にインデックス付けされる、ステップと、
前記地図における地理的領域のジオフェンスの情報を取得するステップと、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定するステップと、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別するステップと、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化するステップと、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定するステップと、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別するステップと、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別するステップと、
を含む、方法。
【請求項１２】
前記ジオフェンスの前記情報は、複数の境界点に対応する1セットの座標対を含み、
前記ジオフェンスの前記境界グリッド系列を判定する前記ステップは、
前記複数のグリッドから前記複数の境界点に対応する前記境界グリッド系列を識別するステップと、
以下のステップ、すなわち、
前記複数の境界点から2つの隣接する境界点を取得するステップと、
前記2つの隣接する境界点が同じグリッドに対応するか否かを判定するステップと、
前記2つの隣接する境界点が同じグリッドに対応するという判定に応じて、前記2つの隣接する点のうちの1つを除去するステップと、
前記2つの隣接する境界点が2つの異なるグリッドに対応するという判定に応じて、前記2つの隣接する境界点の間で境界点を補間するステップと、
前記複数の境界点に対応する前記境界グリッド系列を更新するステップと、
を含む1つまたは複数の動作を実行するステップと、
をさらに含む、請求項11に記載の方法。
【請求項１３】
前記境界グリッド系列は、前記ジオフェンスが通過する、前記地図の前記複数のグリッドからのグリッドを含み、
前記少なくとも1つの囲繞エリアを識別する前記ステップは、
前記境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定するステップであって、ピボットグリッドが少なくとも2つの同じグリッドインデックスに対応する、ステップと、
前記境界グリッド系列が1つまたは複数のピボットグリッドを含むという判定に応じて、前記1つまたは複数のピボットグリッドのそれぞれについて、前記ピボットグリッドの一方の側にある前記地理的領域におけるエリアを、第1の囲繞エリアとして、また前記ピボットグリッドの他方の側にある前記地理的領域におけるエリアを、前記第1の囲繞エリアとは異なる第2の囲繞エリアとして識別するステップと、
をさらに含む、請求項11に記載の方法。
【請求項１４】
前記少なくとも1つの囲繞エリアを識別する前記ステップは、
空のスタックおよび空の補助地図を生成するステップと、
前記境界グリッド系列の各グリッドについて、
前記境界グリッド系列からグリッドを順次取得するステップと、
前記グリッドに対応するグリッドインデックスが前記補助地図にあるか否かを判定するステップと、
前記グリッドインデックスが前記補助地図にないという判定に応じて、前記グリッドインデックスを前記スタックにプッシュし、前記グリッドインデックスを前記補助地図に入力するステップと、
前記グリッドインデックスが前記補助地図にあるという判定に応じて、前記グリッドインデックスに対応する前記グリッドを前記1つまたは複数のピボットグリッドのうちのピボットグリッドとして指定し、前記グリッドインデックスをピボットグリッドインデックスとして指定し、前記スタックの一番上にある前記グリッドインデックスが前記ピボットグリッドインデックスと同じになるまで、前記スタックから前記スタックにあるグリッドインデックスをポップし、前記ポップされたグリッドインデックスに対応するグリッドを前記第1の囲繞エリアの境界グリッドとして指定するステップと、
前記スタックに残っているグリッドインデックスに対応するグリッドを、前記第2の囲繞エリアの境界グリッドとして指定するステップと、
をさらに含む、請求項13に記載の方法。
【請求項１５】
前記ジオフェンスは、中心および半径によって定義される円に基づいて判定され、
前記地理的領域において前記少なくとも1つの囲繞エリアを識別する前記ステップは、
前記円上で複数のサンプル点を所定のサンプル間隔でサンプリングするステップと、
前記複数のサンプル点に基づいて前記地理的領域における前記少なくとも1つの囲繞エリアの境界グリッドを判定するステップと、
をさらに含む、請求項11に記載の方法。
【請求項１６】
前記所定のサンプル間隔は、前記円の前記半径および前記複数のグリッドのうちのグリッドに関連する解像度に関連付けられる、請求項15に記載の方法。
【請求項１７】
前記複数のサンプル点のうちの2つ以上のサンプル点が同じグリッドに対応すると判定すると、1つのサンプル点のみが前記グリッドに対応するように、前記2つ以上のサンプル点から1つまたは複数のサンプル点を除去するステップ
をさらに含む、請求項15または16に記載の方法。
【請求項１８】
前記少なくとも1つの囲繞エリアを2つ以上のサブエリアにセグメント化する前記ステップの後、前記方法は、
前記2つ以上のサブエリアが前記複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定するステップと、
前記重複辺グリッドを前記2つ以上のサブエリアの境界グリッドとして前記2つ以上のサブエリアに追加するステップと、
をさらに含む、請求項11に記載の方法。
【請求項１９】
前記複数のグリッドから前記サブエリアにおける前記内部グリッドを識別する前記ステップは、
スキャニング行列を初期化するステップであって、前記スキャニング行列は複数のセルを含み、前記スキャニング行列の各セルは第1の値を有する、ステップと、
前記スキャニング行列の第1の複数のセルのそれぞれに第2の値を入力することによって、前記スキャニング行列に対して第1の更新を実行するステップであって、前記第1の複数のセルは、前記サブエリアの前記境界グリッドに対応する、ステップと、
前記第1の値を有する、前記第1の更新後の前記スキャニング行列の各セルについて、前記セルに対応する前記グリッドが前記地理的領域にあるか否かを判定するステップと、
前記セルに対応する前記グリッドが前記地理的領域にあるという判定に応じて、
前記スキャニング行列の前記セルに第3の値を入力することによって、前記スキャニング行列に対して第2の更新を実行するステップと、
前記第3の値を有する前記セルに対応するグリッドを前記サブエリアの前記内部グリッドとして指定するステップと、
をさらに含む、請求項11に記載の方法。
【請求項２０】
地理的領域を識別するための1セットの命令を含む非一時的コンピュータ可読媒体であって、少なくとも1つのプロセッサによって実行されると、前記少なくとも1セットの命令は、
少なくとも1つの記憶媒体からの地図にアクセスする動作と、
前記地図の表示を生成する動作であって、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、独立にインデックス付けされる、動作と、
前記地図における地理的領域のジオフェンスの情報を取得する動作と、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定する動作と、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別する動作と、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化する動作と、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定する動作と、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別する動作と、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別する動作と、
を実行するように前記少なくとも1つのプロセッサに指示する、非一時的コンピュータ可読媒体。
【請求項２１】
ジオフェンスのグリッドを識別するための第1のアプリケーションをインストールした少なくとも1つのジオフェンス識別サーバと、
前記ジオフェンス識別サーバに対して遠隔にあり、かつ第2のアプリケーションをインストールした少なくとも1つのユーザ端末であって、前記少なくとも1つのユーザ端末が前記第2のアプリケーションを動作させると、前記少なくとも1つのユーザ端末が、
前記第1のアプリケーションを介して前記ジオフェンス識別サーバとの有線または無線通信を確立し、
前記少なくとも1つのユーザ端末のユーザからジオフェンスの形状を受信し、
前記ジオフェンスの前記形状を有線または無線通信を介して前記少なくとも1つのジオフェンス識別サーバに送信する、
ように指示される、少なくとも1つのユーザ端末と、
前記少なくとも1つのジオフェンス識別サーバと通信し、地図と地理的領域を識別するための1セットの命令とを記憶する少なくとも1つの記憶媒体であって、
前記少なくとも1つのジオフェンス識別サーバは、前記1セットの命令を実行すると、
前記地図の少なくとも一部を前記少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードし、
前記地図の前記少なくとも一部の表示を生成し、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、独立にインデックス付けされ、
前記地図における地理的領域のジオフェンスの情報を取得し、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定し、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別し、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化し、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定し、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別し、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別し、
前記地理的領域における前記グリッドの情報を含む信号を前記少なくとも1つのユーザ端末に送信し、前記少なくとも1つのユーザ端末に対して前記地理的領域における前記グリッドの表示を生成する、
ように指示される、少なくとも1つの記憶媒体と、
を備える、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された人工知能システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、グラフィック識別システムに関し、具体的には、広大な地理的領域を識別するためのユーザの要求に応答するシステムおよび方法に関する。
【背景技術】
【０００２】
地理的領域におけるグリッドを効果的に判定することは、自動運転やオンラインタクシー配車サービスなどのインターネットオンラインツーオフラインサービスなどの複数の最先端技術にとって非常に重要である。この技術は、ユーザが地図において自身のグリッドをすばやく識別し、それによりグリッドに関連した対応する情報にアクセスするのに役立つ。例えば、グリッド識別技術により、オンラインツーオフラインプラットフォームが、タクシー運転手の近くのグリッドに関するサービス需要情報を取得し、それに応じてタクシー運転手にサービス需要情報を提供することができる。観光客の場合では、グリッド識別技術は、オンラインツーオフラインサービスプラットフォームが、観光客が位置するグリッドを識別し、それにより、関心をもたれる可能性のある地点（Point of Interest、POI）またはサービス（飲食もしくはレクリエーションサービス、または観光客のスマートフォン用の通信基地局）を観光客にプッシュ配信するのに役立ち得る。自動運転では、グリッド識別技術は、自律車両が自身の位置に基づいて自身のグリッドを識別し、それにより情報通信のために基地局と通信するのに役立ち得る。グリッドを探索するための地図の規模が大きすぎる場合、すなわちグリッドの数が多すぎる場合、グリッドをすばやく見つけることが難しくなる。例えば、ルートまたはジオフェンスの境界が大陸規模または大陸間規模の地図に広がっている場合、地図におけるグリッドの数は天文学的なものになり得る。したがって、ルートまたはジオフェンスが通過するグリッドを識別することは難しい場合がある。これは、世界のグリッドが地域の区画に基づいてインデックス付けされている場合に特に当てはまり、つまり、世界地図における区画が異なると、そこでのグリッドのインデックスが完全に異なる。したがって、ルートまたはジオフェンスが地域の区画のうちの1つまたは複数を横切る場合、対応するグリッドを探索するための作業負荷が特に難しいものになり得る。よって、地図における地理的領域においてグリッドを判定するための効果的なシステムおよび方法を提供することが望ましい。
【発明の概要】
【課題を解決するための手段】
【０００３】
本開示の一態様では、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された人工知能システムが提供される。人工知能システムは、少なくとも1つの記憶媒体と、少なくとも1つの記憶媒体と通信する少なくとも1つのプロセッサと、を備え得る。少なくとも1つの記憶媒体は、地図と地理的領域を識別するための1セットの命令とを記憶し得る。1セットの命令を実行すると、少なくとも1つのプロセッサは、地図の少なくとも一部を少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードし、地図の少なくとも一部の表示を生成するように指示され得る。地図は、複数のグリッドにグリッド化され、複数の区画に分割され得る。地図における複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ得、各区画におけるグリッドが、独立にインデックス付けされ得る。少なくとも1つのプロセッサはまた、地図における地理的領域のジオフェンスの情報を取得し、複数のグリッドからジオフェンスの境界グリッド系列を判定するように指示され得る。少なくとも1つのプロセッサは、境界グリッド系列に基づいて地理的領域における少なくとも1つの囲繞エリアを識別するようにさらに指示され得る。少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、少なくとも1つのプロセッサは、2つ以上のサブエリアの各サブエリアが複数の区画のうちの1つの区画にのみ位置するように、囲繞エリアを2つ以上のサブエリアにセグメント化するように指示され得る。少なくとも1つのプロセッサはまた、2つ以上のサブエリアのそれぞれについて境界グリッドを判定するように指示され得る。2つ以上のサブエリアのそれぞれについて、少なくとも1つのプロセッサはまた、サブエリアの境界グリッドおよびサブエリアが位置する区画のインデックスに基づいて、複数のグリッドからサブエリアにおける内部グリッドを識別するように指示され得る。少なくとも1つのプロセッサは、2つ以上のサブエリアの境界グリッドおよび2つ以上のサブエリアにおける内部グリッドを収集することにより、地理的領域におけるグリッドを識別するようにさらに指示され得る。
【０００４】
本開示の別の態様では、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するための方法が提供される。本方法は、地図と地理的領域を識別するための1セットの命令とを記憶する少なくとも1つの記憶媒体と、少なくとも1つの記憶媒体と通信する少なくとも1つのプロセッサと、を有するコンピューティングデバイス上で実施され得る。本方法は、地図の少なくとも一部を少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードするステップと、地図の少なくとも一部の表示を生成するステップと、を含み得る。地図は、複数のグリッドにグリッド化され、複数の区画に分割され得る。地図における複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ得、各区画におけるグリッドが、独立にインデックス付けされ得る。本方法はまた、地図における地理的領域のジオフェンスの情報を取得するステップと、複数のグリッドからジオフェンスの境界グリッド系列を判定するステップと、を含み得る。本方法は、境界グリッド系列に基づいて地理的領域における少なくとも1つの囲繞エリアを識別するステップをさらに含み得る。少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、本方法は、2つ以上のサブエリアの各サブエリアが複数の区画のうちの1つの区画にのみ位置するように、囲繞エリアを2つ以上のサブエリアにセグメント化するステップを含み得る。本方法はまた、2つ以上のサブエリアのそれぞれについて境界グリッドを判定するステップを含み得る。2つ以上のサブエリアのそれぞれについて、本方法は、サブエリアの境界グリッドおよびサブエリアが位置する区画のインデックスに基づいて、複数のグリッドからサブエリアにおける内部グリッドを識別するステップを含み得る。本方法は、2つ以上のサブエリアの境界グリッドおよび2つ以上のサブエリアにおける内部グリッドを収集することにより、地理的領域におけるグリッドを識別するステップをさらに含み得る。
【０００５】
本開示の別の態様では、非一時的コンピュータ可読媒体が提供される。非一時的コンピュータ可読媒体は、地理的領域を識別するための少なくとも1セットの命令を含み得る。少なくとも1つのプロセッサによって実行されると、少なくとも1セットの命令は、少なくとも1つの記憶媒体からの地図にアクセスする動作と、地図の表示を生成する動作と、を実行するように少なくとも1つのプロセッサに指示し得る。地図は、複数のグリッドにグリッド化され、複数の区画に分割され得る。地図における複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ得、各区画におけるグリッドが、独立にインデックス付けされ得る。少なくとも1セットの命令はまた、地図における地理的領域のジオフェンスの情報を取得する動作と、複数のグリッドからジオフェンスの境界グリッド系列を判定する動作と、を実行するように少なくとも1つのプロセッサに指示し得る。少なくとも1セットの命令は、境界グリッド系列に基づいて地理的領域における少なくとも1つの囲繞エリアを識別する動作を実行するように少なくとも1つのプロセッサにさらに指示し得る。少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、少なくとも1セットの命令は、2つ以上のサブエリアの各サブエリアが複数の区画のうちの1つの区画にのみ位置するように、囲繞エリアを2つ以上のサブエリアにセグメント化する動作を実行するように少なくとも1つのプロセッサに指示し得る。少なくとも1セットの命令はまた、2つ以上のサブエリアのそれぞれについて境界グリッドを判定する動作を実行するように少なくとも1つのプロセッサに指示し得る。2つ以上のサブエリアのそれぞれについて、少なくとも1セットの命令はまた、サブエリアの境界グリッドおよびサブエリアが位置する区画のインデックスに基づいて、複数のグリッドからサブエリアにおける内部グリッドを識別する動作を実行するように少なくとも1つのプロセッサに指示し得る。少なくとも1セットの命令は、2つ以上のサブエリアの境界グリッドおよび2つ以上のサブエリアにおける内部グリッドを収集することにより、地理的領域におけるグリッドを識別する動作を実行するように少なくとも1つのプロセッサにさらに指示し得る。
【０００６】
本開示の別の態様では、地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された人工知能システムが提供される。地図は、複数の独立にインデックス付けされたグリッドの領域を含み得る。人工知能システムは、ジオフェンスのグリッドを識別するための第1のアプリケーションをインストールした少なくとも1つのジオフェンス識別サーバと、ジオフェンス識別サーバに対して遠隔にあり、かつ第2のアプリケーションをインストールした少なくとも1つのユーザ端末と、を備え得る。少なくとも1つのユーザ端末が第2のアプリケーションを動作させ得る場合、少なくとも1つのユーザ端末は、第1のアプリケーションを介してジオフェンス識別サーバとの有線または無線通信を確立するように指示され得る。少なくとも1つのユーザ端末はまた、少なくとも1つのユーザ端末のユーザからジオフェンスの形状を受信し、ジオフェンスの形状を有線または無線通信を介して少なくとも1つのジオフェンス識別サーバに送信するように指示され得る。人工知能システムはまた、少なくとも1つのジオフェンス識別サーバと通信し、地図と地理的領域を識別するための1セットの命令とを記憶する少なくとも1つの記憶媒体を備え得る。1セットの命令を実行すると、少なくとも1つのジオフェンス識別サーバは、地図の少なくとも一部を少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードし、地図の少なくとも一部の表示を生成するように指示され得る。地図は、複数のグリッドにグリッド化され、複数の区画に分割され得る。地図における複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ得、各区画におけるグリッドが、独立にインデックス付けされ得る。少なくとも1つのジオフェンス識別サーバはまた、地図における地理的領域のジオフェンスの情報を取得し、複数のグリッドからジオフェンスの境界グリッド系列を判定するように指示され得る。少なくとも1つのジオフェンス識別サーバは、境界グリッド系列に基づいて地理的領域における少なくとも1つの囲繞エリアを識別するようにさらに指示され得る。少なくとも1つの囲繞エリアのうちの囲繞エリアが2つ以上の区画を横切ると判定すると、少なくとも1つのジオフェンス識別サーバは、2つ以上のサブエリアの各サブエリアが複数の区画のうちの1つの区画にのみ位置するように、囲繞エリアを2つ以上のサブエリアにセグメント化するように指示され得る。少なくとも1つのジオフェンス識別サーバはまた、2つ以上のサブエリアのそれぞれについて境界グリッドを判定するように指示され得る。2つ以上のサブエリアのそれぞれについて、少なくとも1つのジオフェンス識別サーバはまた、サブエリアの境界グリッドおよびサブエリアが位置する区画のインデックスに基づいて、複数のグリッドからサブエリアにおける内部グリッドを識別するように指示され得る。少なくとも1つのジオフェンス識別サーバは、2つ以上のサブエリアの境界グリッドおよび2つ以上のサブエリアにおける内部グリッドを収集することにより、地理的領域におけるグリッドを識別するようにさらに指示され得る。少なくとも1つのジオフェンス識別サーバは、地理的領域におけるグリッドの情報を含む信号を少なくとも1つのユーザ端末に送信し、少なくとも1つのユーザ端末に対して地理的領域におけるグリッドの表示を生成するようにさらに指示され得る。
【０００７】
いくつかの実施形態では、ジオフェンスの情報は、複数の境界点に対応する1セットの座標対を含み得る。ジオフェンスの境界グリッド系列を判定するために、少なくとも1つのプロセッサは、複数のグリッドから複数の境界点に対応する境界グリッド系列を識別するようにさらに指示され得る。少なくとも1つのプロセッサは、複数の境界点から2つの隣接する境界点を取得する動作と、2つの隣接する境界点が同じグリッドに対応するか否かを判定する動作と、2つの隣接する境界点が同じグリッドに対応するという判定に応じて、2つの隣接する点のうちの1つを除去する動作と、2つの隣接する境界点が2つの異なるグリッドに対応するという判定に応じて、2つの隣接する境界点の間で境界点を補間する動作と、複数の境界点に対応する境界グリッド系列を更新する動作と、を含む1つまたは複数の動作を実行するようにさらに指示され得る。
【０００８】
いくつかの実施形態では、境界グリッド系列は、ジオフェンスが通過する、地図の複数のグリッドからのグリッドを含み得る。少なくとも1つの囲繞エリアを識別するために、少なくとも1つのプロセッサは、境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定するようにさらに指示され得、ピボットグリッドが少なくとも2つの同じグリッドインデックスに対応する。境界グリッド系列が1つまたは複数のピボットグリッドを含むという判定に応じて、1つまたは複数のピボットグリッドのそれぞれについて、少なくとも1つのプロセッサは、ピボットグリッドの一方の側にある地理的領域におけるエリアを、第1の囲繞エリアとして、またピボットグリッドの他方の側にある地理的領域におけるエリアを、第1の囲繞エリアとは異なる第2の囲繞エリアとして識別するように指示され得る。
【０００９】
いくつかの実施形態では、少なくとも1つの囲繞エリアを識別するために、少なくとも1つのプロセッサは、空のスタックおよび空の補助地図を生成するようにさらに指示され得る。境界グリッド系列の各グリッドについて、少なくとも1つのプロセッサは、境界グリッド系列からグリッドを順次取得し、グリッドに対応するグリッドインデックスが補助地図にあるか否かを判定するように指示され得る。グリッドインデックスが補助地図にないという判定に応じて、少なくとも1つのプロセッサは、グリッドインデックスをスタックにプッシュし、グリッドインデックスを補助地図に入力するように指示され得る。グリッドインデックスが補助地図にあるという判定に応じて、少なくとも1つのプロセッサは、グリッドインデックスに対応するグリッドを1つまたは複数のピボットグリッドのうちのピボットグリッドとして指定し、グリッドインデックスをピボットグリッドインデックスとして指定し、スタックの一番上にあるグリッドインデックスがピボットグリッドインデックスと同じになるまで、スタックからスタックにあるグリッドインデックスをポップし、ポップされたグリッドインデックスに対応するグリッドを第1の囲繞エリアの境界グリッドとして指定するように指示され得る。少なくとも1つのプロセッサは、スタックに残っているグリッドインデックスに対応するグリッドを、第2の囲繞エリアの境界グリッドとして指定するようにさらに指示され得る。
【００１０】
いくつかの実施形態では、ジオフェンスは、中心および半径によって定義される円に基づいて判定され得る。地理的領域において少なくとも1つの囲繞エリアを識別するために、少なくとも1つのプロセッサは、円上で複数のサンプル点を所定のサンプル間隔でサンプリングし、複数のサンプル点に基づいて地理的領域における少なくとも1つの囲繞エリアの境界グリッドを判定するようにさらに指示され得る。
【００１１】
いくつかの実施形態では、所定のサンプル間隔は、円の半径および複数のグリッドのうちのグリッドに関連する解像度に関連付けられ得る。
【００１２】
いくつかの実施形態では、少なくとも1つのプロセッサは、複数のサンプル点のうちの2つ以上のサンプル点が同じグリッドに対応すると判定すると、1つのサンプル点のみがグリッドに対応するように、2つ以上のサンプル点から1つまたは複数のサンプル点を除去するようにさらに指示され得る。
【００１３】
いくつかの実施形態では、少なくとも1つの囲繞エリアを2つ以上のサブエリアにセグメント化した後、少なくとも1つのプロセッサは、2つ以上のサブエリアが複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定し、重複辺グリッドを2つ以上のサブエリアの境界グリッドとして2つ以上のサブエリアに追加するように指示され得る。
【００１４】
いくつかの実施形態では、複数のグリッドからサブエリアにおける内部グリッドを識別するために、少なくとも1つのプロセッサは、スキャニング行列を初期化するように指示され得る。スキャニング行列は複数のセルを含むことができ、スキャニング行列の各セルは第1の値を有することができる。少なくとも1つのプロセッサは、スキャニング行列の第1の複数のセルのそれぞれに第2の値を入力することによって、スキャニング行列に対して第1の更新を実行するように指示され得る。第1の複数のセルは、サブエリアの境界グリッドに対応し得る。第1の値を有する、第1の更新後のスキャニング行列の各セルについて、少なくとも1つのプロセッサは、セルに対応するグリッドが地理的領域にあるか否かを判定するように指示され得る。セルに対応するグリッドが地理的領域にあるという判定に応じて、少なくとも1つのプロセッサは、スキャニング行列のセルに第3の値を入力することによって、スキャニング行列に対して第2の更新を実行するようにさらに指示され得る。少なくとも1つのプロセッサは、第3の値を有するセルに対応するグリッドをサブエリアにおける内部グリッドとして指定するようにさらに指示され得る。
【００１５】
いくつかの実施形態では、第2の値と第3の値とは互いに同じであってもよい。
【００１６】
追加の特徴は、一部は以下の説明に記載され、一部は以下および添付の図面を検討することにより当業者には明らかになり得る、または例を製造すること動作させることによって知ることができる。本開示の特徴は、以下で論じられる詳細な例に示される方法論、手段、および組み合わせの様々な態様の実践または使用によって実現および達成され得る。
【００１７】
本開示は、例示的な実施形態に関してさらに説明される。これらの例示的な実施形態は、図面を参照して詳細に説明される。図面は縮尺通りではない。これらの実施形態は、非限定的な例示的な実施形態であり、図面のいくつかの図を通して、同様の参照番号は同様の構造を表す。
【図面の簡単な説明】
【００１８】
【図１】本開示のいくつかの実施形態による例示的な人工知能システムのブロック図である。
【図２】本開示のいくつかの実施形態による例示的なコンピューティングデバイスの例示的なハードウェアおよび／またはソフトウェア構成要素を示す概略図である。
【図３】本開示のいくつかの実施形態による例示的なデバイスを示す概略図である。
【図４Ａ】本開示のいくつかの実施形態による例示的な処理エンジンを示すブロック図である。
【図４Ｂ】本開示のいくつかの実施形態による例示的なジオフェンス境界判定モジュールを示すブロック図である。
【図４Ｃ】本開示のいくつかの実施形態による例示的な囲繞エリア判定モジュールを示すブロック図である。
【図４Ｄ】本開示のいくつかの実施形態による例示的なサブエリア判定モジュールを示すブロック図である。
【図４Ｅ】本開示のいくつかの実施形態による例示的な内部グリッド判定モジュールを示すブロック図である。
【図４Ｆ】本開示のいくつかの実施形態による例示的なグリッドインデックス判定モジュールを示すブロック図である。
【図５】本開示のいくつかの実施形態による、地理的領域におけるグリッドを判定するための例示的なプロセスを示す流れ図である。
【図６Ａ】本開示のいくつかの実施形態による、ジオフェンスの初期境界グリッド系列を判定するための例示的なプロセスを示す流れ図である。
【図６Ｂ】本開示のいくつかの実施形態による、ジオフェンスの初期境界グリッド系列を判定するための例示的なプロセスを示す流れ図である。
【図７Ａ】本開示のいくつかの実施形態による、座標対に対応するグリッドインデックスを判定するための例示的なプロセスを示す流れ図である。
【図７Ｂ】本開示のいくつかの実施形態による、地球を表す八面体を示す概略図である。
【図７Ｃ】本開示のいくつかの実施形態による、八面体の区画を細分化するための例示的な細分化操作を示す概略図である。
【図７Ｄ】本開示のいくつかの実施形態による、八面体の区画を細分化するための例示的な細分化操作を示す概略図である。
【図７Ｅ】本開示のいくつかの実施形態による、八面体の区画を細分化するための例示的な細分化操作を示す概略図である。
【図７Ｆ】本開示のいくつかの実施形態による、八面体の区画上の例示的な投影座標系を示す概略図である。
【図７Ｇ】本開示のいくつかの実施形態による、八面体の区画上の例示的な投影座標系を示す概略図である。
【図７Ｈ】本開示のいくつかの実施形態による、デカルト座標から投影座標への変換を示す概略図である。
【図７Ｉ】本開示のいくつかの実施形態による、六角形のグリッドのターゲット中心点を示す概略図である。
【図７Ｊ】本開示のいくつかの実施形態による、菱形のグリッドのターゲット共通点を示す概略図である。
【図７Ｋ】本開示のいくつかの実施形態による、クロスオーバーグリッドのターゲット中心点の帰属を示す概略図である。
【図８】本開示のいくつかの実施形態による、初期境界グリッド系列に基づいてジオフェンスの最終的な境界グリッド系列を判定するための例示的なプロセスを示す流れ図である。
【図９Ａ】本開示のいくつかの実施形態による、地理的領域に関連付けられた1つまたは複数の囲繞エリアを判定するための例示的なプロセスを示す流れ図である。
【図９Ｂ】本開示のいくつかの実施形態による、地理的領域に関連付けられた1つまたは複数の囲繞エリアを判定するための例示的なプロセスを示す流れ図である。
【図１０】本開示のいくつかの実施形態による、サブエリアの境界グリッドを判定するための例示的なプロセスを示す流れ図である。
【図１１Ａ】本開示のいくつかの実施形態による、サブエリアにおける内部グリッドを判定するための例示的なプロセスを示す流れ図である。
【図１１Ｂ】本開示のいくつかの実施形態による、区画上の例示的なサブエリアを示す図である。
【図１２Ａ】本開示のいくつかの実施形態による例示的なジオフェンスを示す図である。
【図１２Ｂ】本開示のいくつかの実施形態による例示的なジオフェンスを示す図である。
【図１３Ａ】北京市の地理的領域におけるグリッドを示す概略図である。
【図１３Ｂ】本開示のいくつかの実施形態による円形の地理的領域を示す概略図である。
【発明を実施するための形態】
【００１９】
以下の説明は、当業者が本開示を作成および使用できるようにするために提示され、特定の用途およびその要件の文脈で提供される。本開示の実施形態に対する様々な修正は、当業者には容易に明らかになるはずであり、本明細書で定義された一般原理は、本開示の趣旨および範囲から逸脱することなく、他の実施形態および用途に適用され得る。よって、本開示は、示される実施形態に限定されず、特許請求の範囲と一致する最も広い範囲が与えられるべきである。
【００２０】
本明細書で使用される用語は、特定の例示的な実施形態を説明することのみを目的としており、限定するものであることは意図されていない。本明細書で使用される場合、単数形「a」、「an」、および「the」は、文脈上、明確な別段の指示のない限り、複数形も含むことが意図され得る。本開示で使用される場合、「備える（comprises）」、「備える（comprising）」、「含む（includes）」、および／または「含む（including）」という用語は、述べられた特徴、整数、ステップ、動作、要素、および／または構成要素の存在を指定するが、1つまたは複数の他の機能、整数、ステップ、動作、要素、構成要素、および／またはそれらのグループの存在または追加を排除するものではないことをさらに理解されたい。
【００２１】
本開示の上記および他の特徴および性質、ならびに関連する構成要素および各部分の組み合わせの動作方法および機能、ならびに製造の経済性は、いずれも本開示の一部を構成する添付の図面（複数可）を参照しながら以下の説明を検討することにより、さらに明らかになり得る。ただし、図面（複数可）は、例示および説明のみを目的とするものであり、本開示の範囲を限定することは意図されていないことを明確に理解されたい。図面は縮尺通りではないことを理解されたい。
【００２２】
本開示で使用される流れ図は、本開示のいくつかの実施形態による、システムが実施する動作を示している。流れ図の動作は順序通りに実施されなくてよいことを明確に理解されたい。逆に、動作は、逆の順序で、または同時に実施されてもよい。さらに、1つまたは複数の他の動作が流れ図に追加されてもよい。1つまたは複数の動作が流れ図から除去されてもよい。
【００２３】
さらに、本開示で開示されるシステムおよび方法は、エリアのグリッドを識別することに関して主に説明されるが、これは1つの例示的な実施形態に過ぎないことを理解されたい。本開示のシステムまたは方法は、任意の他の種類のオンラインツーオフラインサービスプラットフォームのユーザに適用され得る。例えば、本開示のシステムまたは方法は、陸上、海洋、航空宇宙など、またはそれらの任意の組み合わせを含む様々な輸送システムにおけるユーザに適用され得る。輸送システムの航走体は、タクシー、自家用車、ヒッチ、バス、列車、新幹線、高速鉄道、地下鉄、船舶、航空機、宇宙船、熱気球、自動運転車など、またはそれらの任意の組み合わせを含み得る。輸送システムはまた、管理および／または流通を適用する任意の輸送システム、例えば、至急便を送るおよび／または受け取るためのシステムを含み得る。本開示のシステムまたは方法の適用シナリオは、ウェブページ、ブラウザのプラグイン、クライアント端末、カスタムシステム、内部分析システム、人工知能ロボットなど、またはそれらの任意の組み合わせを含み得る。
【００２４】
本開示におけるサービス開始点は、無線デバイス（例えば、乗客の端末、運転者の端末など）に埋め込まれた測位技術によって取得され得る。本開示において用いられる測位技術は、全地球測位システム（GPS）、全地球航法衛星システム（GLONASS）、コンパス測位システム（COMPASS）、ガリレオ測位システム、準天頂衛星システム（QZSS）、ワイヤレスフィデリティ（Wi−Fi）測位技術など、またはそれらの任意の組み合わせを含み得る。上記の測位技術のうちの1つまたは複数は、本開示において交換可能に使用され得る。例えば、GPSベースの方法とWiFiベースの方法とが、無線デバイスの位置を特定するための測位技術として一緒に使用され得る。
【００２５】
DGGSは、世界をシームレスで重複しない多解像度の階層グリッド構造に分割し、世界の領域においてグリッドを均一に符号化するための特定の方法を使用する新しいグローバルモデリングソリューションである。誰でも、これらのグリッドの緯度および経度の座標IDに基づいて、外部からグリッドにアクセスでき、グリッドIDに従って、グリッドの頂点および中心座標ならびに他のインターフェースにアクセスできる。グリッドを識別することは重要であり、これは、エリアの商業的運用状況をより適切に反映し得る、グリッドのエリアからのデータを集約および処理するのに役立つためである。例えば、北京市海淀区での1日のタクシーの用命がどのように集約されるかというデータがあれば、オンラインのタクシー配車プラットフォームは、海淀区にさらに綿密な輸送サービスを提供できる。加えて、エリア内（特定の基準を満たす用命など）で探索する場合、エリアがグリッドに変換され、グリッドにおける探索がより効率的になり得る。
【００２６】
本開示の一態様は、地図における地理的領域のジオフェンスにおいてグリッドを識別するための人工知能システムおよび／または人工知能による方法に関する。この目的のために、人工知能システムは、地理的領域のジオフェンスに関連する情報を含む、ユーザデバイスからの要求をまず受信し得る。地理的領域が2つ以上の囲繞エリアを含む場合、各囲繞エリアについて、人工知能システムは、囲繞エリアが2つ以上の独立したグリッドインデックス区画を横切るか否かを判定し得る。囲繞エリアが2つ以上の区画を横切る場合、人工知能システムは、各サブエリアが1つの区画のみに位置するように囲繞エリアを2つ以上のサブエリアにセグメント化し、サブエリアのそれぞれにおいてグリッドを識別し得る。最後に、人工知能システムは、サブエリアにおけるすべてのグリッドを、判定対象の最終的なグリッドとして収集し得る。同じ区画にあるグリッドは同じ区画インデックスに関連付けられるため、同じ区画にあるグリッドの相対位置を判定することが容易になる。したがって、人工知能システムは、決定するためのすべてのサブエリアのグリッドに関連するデータを収集し得る。
【００２７】
本開示の人工知能システムおよび方法は、ジオフェンスのグリッドを識別するためのオンラインツーオフラインサービスの要求に応答することを例にとる。ただし、グリッドが単一のインデックスシステムでインデックス付けされていない場合に、形状の境界をグリッドにスナップする操作など、他の形状および／または境界の識別シナリオにも適用され得る。
【００２８】
本解決策は、ポストインターネット時代にのみ根差した新しい形式のデータ収集手段である、人工知能システムに登録されたユーザ端末（例えば、乗客の端末、運転者の端末）に関連するデータ（例えば、位置情報）の収集に依拠することに留意されたい。ポストインターネット時代にしか登場しなかった、ユーザ端末の詳細情報を提供する。インターネット以前の時代には、GPSは利用できず、リアルタイムおよび／または実質的にリアルタイムで数十億のユーザ端末の位置を取得することは不可能である。しかしながら、オンラインツーオフラインサービスにより、人工知能システムは、GPSを使用して数十億のユーザ端末の位置をリアルタイムおよび／または実質的にリアルタイムで監視し、ユーザ端末の位置に基づいてより良いサービススキームを提供できる。したがって、本解決策は、ポストインターネット時代にのみ発生する問題に深く根差しており、これを解決することを目的としている。
【００２９】
図1は、本開示のいくつかの実施形態による、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された例示的な人工知能システムのブロック図である。例えば、人工知能システム100は、自律航法サービス、高速列車通信サービス、タクシー配車サービス、運転代行サービス、小荷物車サービス、相乗りサービス、車両スケジュールサービス、バスサービス、運転者手配、およびシャトルサービスなどの輸送サービスのためのオンライン輸送サービスプラットフォームとすることができる。人工知能システム100は、サーバ110と、ネットワーク120と、乗客の端末130と、運転者の端末140と、ストレージデバイス150と、を備え得る。サーバ110は、処理エンジン112を備え得る。
【００３０】
動作中、乗客の端末130、運転者の端末140、ストレージ150、サーバ110の他の構成要素などの人工知能システム100の1つまたは複数の構成要素は、（例えば、有線または無線通信を介して）通信し、かつ地理的領域を識別するための要求をサーバ110に送信するなど、本開示で開示される方法を動作させるように構成されたアプリケーションをインストールし得る。ユーザは、地理的領域のジオフェンスの形状を判定し得る。例えば、アプリケーションを通じて、ユーザは、サーバ110と通信している自身のスマートフォンのタッチスクリーン上において、領域を横切って円または線を描き、線が横切るか円が囲むグリッドを識別しようとする場合がある。別の例として、ユーザは、自身のスマートフォンを介していくつかの点を入力（例えば、いくつかの点の座標対を入力、または中心および半径により定義される円を設定）し、点で定義された領域または円で囲まれた領域であるグリッドを識別しようとする場合がある。ユーザの操作に応じて、スマートフォンは、サービス要求を符号化するか含む無線信号を、ネットワーク（例えば、ネットワーク120）を介してサーバ110に送信し得る。サーバ110はまた、サービス要求に関連する情報および／またはデータを処理するように構成されたアプリケーション（人工知能システム100の1つまたは複数の構成要素にインストールされたアプリケーションと同じまたは異なるアプリケーション）をインストールし得る。例えば、サーバ110は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、運転者の端末140、ストレージデバイス150、サーバ110の他の構成要素）から取得した円または線の情報に基づいて、地理的領域におけるグリッドを識別し得る。次に、サーバ110は、グリッド情報を符号化するか含む信号をユーザのスマートフォンに送り返し得る。信号は、スマートフォンによって受信された後、スマートフォンをグリッドに関してさらなる動作で応答させ得る。例えば、スマートフォンは、自身の画面にグリッドのうちの1つまたは複数を表示したり、グリッドのうちの1つまたは複数でPOI情報をさらに要求したり、1つまたは複数のグリッドで無線局に通信要求を送信したりし得る。
【００３１】
いくつかの実施形態では、サーバ110は、単一のサーバであってもサーバグループであってもよい。サーバグループは、集中型であっても分散型であってもよい（例えば、サーバ110は分散型システムであってもよい）。いくつかの実施形態では、サーバ110はローカルであってもリモートであってもよい。例えば、サーバ110は、ネットワーク120を介して、乗客の端末130、運転者の端末140、および／またはストレージデバイス150に記憶された情報および／またはデータにアクセスしてもよい。別の例として、サーバ110は、情報および／またはデータにアクセスするために、乗客の端末130、運転者の端末140、および／またはストレージデバイス150に直接接続されてもよい。いくつかの実施形態では、サーバ110は、クラウドプラットフォーム上に実施されてもよい。単なる例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散クラウド、インタークラウド、マルチクラウドなど、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、サーバ110は、本開示の図2に示されている1つまたは複数の構成要素を有するコンピューティングデバイス上で実施され得る。
【００３２】
いくつかの実施形態では、サーバ110は処理エンジン112を備え得る。処理エンジン112は、本開示で説明されるサーバ110の1つまたは複数の機能を実行するためのサービス要求に関連する情報および／またはデータを処理することができる。例えば、処理エンジン112は、少なくとも1つの記憶媒体からの地図にアクセスし、地図における地理的領域のジオフェンスの情報を取得することができる。ジオフェンスの情報は、複数の境界点に対応する1セットの座標対を含んでもよいし、地理的領域の中心および半径を含んでもよい。別の例として、処理エンジン112は、ジオフェンスの情報に基づいて地理的領域におけるグリッドを識別することができる。さらに別の例として、処理エンジン112は、例えば車両スケジュールなどのさらなる処理のために、識別されたグリッドに関連する情報を抽出することができる。いくつかの実施形態では、処理エンジン112は、1つまたは複数の処理エンジン（例えば、シングルコア処理エンジン（複数可）またはマルチコアプロセッサ（複数可））を備え得る。単なる例として、処理エンジン112は、中央処理ユニット（CPU）、特定用途向け集積回路（ASIC）、特定用途向け命令セットプロセッサ（ASIP）、グラフィック処理ユニット（GPU）、物理処理ユニット（PPU）、デジタルシグナルプロセッサ（DSP）、フィールドプログラマブルゲートアレイ（FPGA）、プログラマブルロジックデバイス（PLD）、コントローラ、マイクロコントローラユニット、縮小命令セットコンピュータ（RISC）、マイクロプロセッサなど、またはそれらの任意の組み合わせを含み得る。
【００３３】
ネットワーク120は、情報および／またはデータの交換を容易にし得る。いくつかの実施形態では、人工知能システム100の1つまたは複数の構成要素（例えば、サーバ110、乗客の端末130、運転者の端末140、および／またはストレージデバイス150）は、情報および／またはデータをネットワーク120を介して人工知能システム100の他の構成要素（複数可）に送信することができる。例えば、サーバ110は、ネットワーク120を介して乗客の端末130からサービス要求データを取得することができる。いくつかの実施形態では、ネットワーク120は、任意のタイプの有線もしくは無線ネットワーク、またはそれらの組み合わせであってもよい。単なる例として、ネットワーク120は、ケーブルネットワーク、有線ネットワーク、光ファイバネットワーク、電気通信ネットワーク、イントラネット、インターネット、ローカルエリアネットワーク（LAN）、ワイドエリアネットワーク（WAN）、ワイヤレスローカルエリアネットワーク（WLAN）、メトロポリタンエリアネットワーク（MAN）、ワイドエリアネットワーク（WAN）、公衆電話交換網（PSTN）、Bluetooth（登録商標）ネットワーク、ZigBee（商標）ネットワーク、近距離無線通信（NFC）ネットワーク、汎欧州デジタル移動体通信システム（GSM（登録商標））ネットワーク、符号分割多元接続（CDMA）ネットワーク、時分割多元接続（TDMA）ネットワーク、汎用パケット無線サービス（GPRS）ネットワーク、GSM（登録商標）進化型高速データレート（EDGE）ネットワーク、広帯域符号分割多元接続（WCDMA（登録商標））ネットワーク、高速ダウンリンクパケットアクセス（HSDPA）ネットワーク、ロングタームエボリューション（LTE）ネットワーク、ユーザデータグラムプロトコル（UDP）ネットワーク、伝送制御プロトコル／インターネットプロトコル（TCP／IP）ネットワーク、ショートメッセージサービス（SMS）ネットワーク、ワイヤレスアプリケーションプロトコル（WAP）ネットワーク、超広帯域無線（UWB）ネットワーク、赤外線など、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、サーバ110は、1つまたは複数のネットワークアクセスポイントを含み得る。例えば、サーバ110は、基地局および／またはインターネットエクスチェンジポイント120−1、120−2、．．．などの有線または無線ネットワークアクセスポイントを含むことができ、それを通じて人工知能システム100の1つまたは複数の構成要素がデータおよび／または情報を交換するためにネットワーク120に接続され得る。
【００３４】
乗客の端末130は、オンラインツーオフラインサービスを要求するために乗客によって使用され得る。オンラインツーオフラインサービスは、オンデマンド輸送サービスを含み得る。例えば、乗客の端末130のユーザは、自分自身もしくは別のユーザのためのサービス要求を送信するために、あるいはサーバ110からサービスおよび／もしくは情報または命令を受信するために、乗客の端末130を使用し得る。運転者の端末140は、オンラインツーオフラインサービスに返信するために運転者によって使用され得る。例えば、運転者の端末140のユーザは、乗客の端末130からのサービス要求、および／またはサーバ110からの情報もしくは命令を受信するために運転者の端末140を使用し得る。いくつかの実施形態では、「ユーザ」および「乗客の端末」という用語が交換可能に使用される場合があり、「ユーザ」および「運転者の端末」という用語が交換可能に使用される場合がある。
【００３５】
いくつかの実施形態では、乗客の端末130は、モバイルデバイス130−1、タブレットコンピュータ130−2、ラップトップコンピュータ130−3、自動車の組み込みデバイス130−4など、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、モバイルデバイス130−1は、スマートホームデバイス、ウェアラブルデバイス、スマートモバイルデバイス、仮想現実デバイス、拡張現実デバイスなど、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、スマートホームデバイスは、スマート照明デバイス、インテリジェント電気器具の制御デバイス、スマートモニタリングデバイス、スマートテレビ、スマートビデオカメラ、インターホンなど、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、ウェアラブルデバイスは、スマートブレスレット、スマートフットギア、スマートグラス、スマートヘルメット、スマートウォッチ、スマート衣類、スマートバックパック、スマートアクセサリなど、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、スマートモバイルデバイスは、スマートフォン、携帯情報端末（PDA）、ゲームデバイス、ナビゲーションデバイス、販売時点情報管理（POS）デバイスなど、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、仮想現実デバイスおよび／または拡張現実デバイスは、仮想現実ヘルメット、仮想現実グラス、仮想現実パッチ、拡張現実ヘルメット、拡張現実グラス、拡張現実パッチなど、またはそれらの任意の組み合わせを含み得る。例えば、仮想現実デバイスおよび／または拡張現実デバイスは、Google Glass、Oculus Rift、HoloLens、Gear VRなどを含み得る。いくつかの実施形態では、自動車の組み込みデバイス130−4は、車載コンピュータ、車載テレビなどを含み得る。いくつかの実施形態では、乗客の端末130は、ユーザおよび／または乗客の端末130の位置を特定するための測位技術を備えた無線デバイスであり得る。
【００３６】
いくつかの実施形態では、運転者の端末140は、モバイルデバイス140−1、タブレットコンピュータ140−2、ラップトップコンピュータ140−3、自動車の組み込みデバイス140−4など、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、モバイルデバイス140−1は、スマートホームデバイス、ウェアラブルデバイス、スマートモバイルデバイス、仮想現実デバイス、拡張現実デバイスなど、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、運転者の端末140は、乗客の端末130と同様または同じデバイスであり得る。いくつかの実施形態では、運転者の端末140は、運転者および／または運転者の端末140の位置を特定するための測位技術を備えた無線デバイスであり得る。いくつかの実施形態では、乗客の端末130および／または運転者の端末140は、乗客、乗客の端末130、運転者、および／または運転者の端末140の位置を判定するために他の測位デバイスと通信し得る。いくつかの実施形態では、乗客の端末130および／または運転者の端末140は、測位情報をサーバ110に送信し得る。
【００３７】
ストレージデバイス150は、データおよび／または命令を記憶することができる。いくつかの実施形態では、ストレージデバイス150は、乗客の端末130および／または運転者の端末140から取得されたデータを記憶することができる。いくつかの実施形態では、ストレージデバイス150は、本開示で説明される例示的な方法を実行するためにサーバ110が実行または使用し得るデータおよび／または命令を記憶することができる。いくつかの実施形態では、ストレージデバイス150は、大容量ストレージデバイス、リムーバブルストレージデバイス、揮発性読み書きメモリ、読み取り専用メモリ（ROM）など、またはそれらの任意の組み合わせを含み得る。例示的な大容量ストレージデバイスは、磁気ディスク、光ディスク、ソリッドステートドライブなどを含み得る。例示的なリムーバブルストレージデバイスは、フラッシュドライブ、フロッピー（登録商標）ディスク、光ディスク、メモリカード、ジップディスク、磁気テープなどを含み得る。例示的な揮発性読み書きメモリは、ランダムアクセスメモリ（RAM）を含み得る。例示的なRAMは、ダイナミックRAM（DRAM）、ダブルデータレート同期ダイナミックRAM（DDR SDRAM）、スタティックRAM（SRAM）、サイリスタRAM（T−RAM）、およびゼロキャパシタRAM（Z−RAM）などを含み得る。例示的なROMは、マスクROM（MROM）、プログラマブルROM（PROM）、イレーサブルプログラマブルROM（PEROM）、エレクトリカリーイレーサブルプログラマブルROM（EEPROM）、コンパクトディスクROM（CD−ROM）、およびデジタル多用途ディスクROMなどを含み得る。いくつかの実施形態では、ストレージデバイス150は、クラウドプラットフォーム上で実施され得る。単なる例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散クラウド、インタークラウド、マルチクラウドなど、またはそれらの任意の組み合わせを含み得る。
【００３８】
いくつかの実施形態では、ストレージデバイス150は、人工知能システム100の1つまたは複数の構成要素（例えば、サーバ110、乗客の端末130、運転者の端末140など）と通信するためにネットワーク120に接続され得る。人工知能システム100の1つまたは複数の構成要素は、ネットワーク120を介してストレージデバイス150に記憶されたデータまたは命令にアクセスすることができる。いくつかの実施形態では、ストレージデバイス150は、人工知能システム100の1つまたは複数の構成要素（例えば、サーバ110、乗客の端末130、運転者の端末140など）に直接接続されてもよいし、1つまたは複数の構成要素と通信し得る。いくつかの実施形態では、ストレージデバイス150は、サーバ110の一部であり得る。
【００３９】
いくつかの実施形態では、人工知能システム100の1つまたは複数の構成要素（例えば、サーバ110、乗客の端末130、運転者の端末140など）は、ストレージデバイス150にアクセスするための許可を有し得る。いくつかの実施形態では、人工知能システム100の1つまたは複数の構成要素は、1つまたは複数の条件が満たされたときに、乗客、運転者、および／または公衆に関連する情報を読み取りおよび／または変更することができる。例えば、サーバ110は、サービス後に1人または複数のユーザの情報を読み取りおよび／または変更することができる。別の例として、運転者の端末140は、乗客の端末130からサービス要求を受信すると、乗客に関連する情報にアクセスすることができるが、運転者の端末140は、乗客の関連情報を変更できない。
【００４０】
いくつかの実施形態では、人工知能システム100の1つまたは複数の構成要素の情報交換は、サービスを要求することによって達成され得る。サービス要求の対象は、任意の製品であり得る。いくつかの実施形態では、製品は有形の製品である場合もあれば無形の製品である場合もある。有形の製品は、食品、医薬品、日用品、化学製品、電化製品、衣類、自動車、住宅、高級品など、またはそれらの任意の組み合わせを含み得る。無形の製品は、サービス製品、金融製品、知識製品、インターネット製品など、またはそれらの任意の組み合わせを含み得る。インターネット製品は、個人向けホスト製品、ウェブ製品、モバイルインターネット製品、業務用ホスト製品、埋め込み製品など、またはそれらの任意の組み合わせを含み得る。モバイルインターネット製品は、モバイル端末のソフトウェア、プログラム、システムなど、またはそれらの任意の組み合わせで使用され得る。モバイル端末は、タブレットコンピュータ、ラップトップコンピュータ、携帯電話、携帯情報端末（PDA）、スマートウォッチ、販売時点情報管理（POS）デバイス、車載コンピュータ、車載テレビ、ウェアラブルデバイスなど、またはそれらの任意の組み合わせを含み得る。例えば、製品は、コンピュータまたは携帯電話で使用される任意のソフトウェアおよび／またはアプリケーションとすることができる。ソフトウェアおよび／またはアプリケーションは、社交、買い物、輸送、娯楽、学習、投資など、またはそれらの任意の組み合わせに関係し得る。いくつかの実施形態では、輸送に関連するソフトウェアおよび／またはアプリケーションは、旅行ソフトウェアおよび／またはアプリケーション、車両スケジューリングソフトウェアおよび／またはアプリケーション、地図作成ソフトウェアおよび／またはアプリケーションなどを含み得る。車両スケジューリングソフトウェアおよび／またはアプリケーションでは、車両は、馬、馬車、人力車（例えば、手押し車、自転車、三輪車など）、自動車（例えば、タクシー、バス、自家用車など）、列車、地下鉄、船舶、航空機（例えば、飛行機、ヘリコプター、スペースシャトル、ロケット、熱気球など）など、または任意のそれらの組み合わせを含み得る。
【００４１】
当業者は、人工知能システム100の要素が作動するとき、要素が電気信号および／または電磁信号を通して作動し得ることを理解されよう。例えば、乗客の端末130が地理的領域のジオフェンス（例えば、1セットの座標対）に関連する情報を入力するなどのタスクを処理するとき、乗客の端末130は、そのようなタスクを実行するために自身のプロセッサの論理回路を動作させ得る。乗客の端末130がサービス要求をサーバ110に送信すると、サーバ110のプロセッサが、要求を符号化する電気信号を生成し得る。次に、サーバ110のプロセッサは、電気信号を出力ポートに送信し得る。乗客の端末130が有線ネットワークを介してサーバ110と通信する場合、出力ポートはケーブルに物理的に接続され得、ケーブルは電気信号をサーバ110の入力ポートにさらに送信する。乗客の端末130が無線ネットワークを介してサーバ110と通信する場合、サービスリクエスタの端末130の出力ポートは、電気信号を電磁信号に変換する1つまたは複数のアンテナであり得る。同様に、運転者の端末140は、自身のプロセッサの論理回路の動作を通じてタスクを処理し、電気信号または電磁石信号を介してサーバ110からの命令および／またはサービス要求を受信し得る。乗客の端末130、運転者の端末140、および／またはサーバ110などの電子デバイス内で、電子デバイスのプロセッサが命令を処理する、命令を送信する、および／またはアクションを実行すると、命令および／またはアクションが電気信号を介して行われる。例えば、プロセッサが記憶媒体からデータを取得または保存するとき、プロセッサは、記憶媒体において構造化データを読み取りまたは書き込むことができる記憶媒体の読み取り／書き込みデバイスに電気信号を送信することができる。構造化データは、電気信号の形で、電子デバイスのバスを介してプロセッサに送信され得る。ここで、電気信号は、1つの電気信号、一連の電気信号、および／または複数の離散的な電気信号を指し得る。
【００４２】
図2は、本開示のいくつかの実施形態による、サーバ110、乗客の端末130、および／または運転者の端末140が実施され得るコンピューティングデバイスの例示的なハードウェアおよびソフトウェア構成要素を示す概略図である。例えば、処理エンジン112は、コンピューティングデバイス200上に実施され、本開示で開示される処理エンジン112の機能を実行するように構成され得る。
【００４３】
コンピューティングデバイス200は、本開示におけるオンラインツーオフラインシステムを実施するために使用され得る。コンピューティングデバイス200は、本明細書で説明されるオンラインツーオフラインサービスの任意の構成要素を実施し得る。図2では、純粋に便宜上の目的のために、そのようなコンピュータデバイスが1つだけ示されている。当業者は、本出願の出願時に、本明細書に記載されるオンラインツーオフラインサービスに関連するコンピュータ機能が、処理負荷を分散するために複数の同様のプラットフォーム上に分散して実施され得ることを理解されよう。
【００４４】
コンピューティングデバイス200は、例えば、データ通信を容易にするためにネットワークに接続された通信ポート250を備え得る。コンピューティングデバイス200はまた、プログラム命令を実行するための1つまたは複数のプロセッサの形態の中央プロセッサ220を備え得る。例示的なコンピュータプラットフォームは、様々なデータファイルをコンピュータによって処理および／または送信させるために、内部通信バス210と、異なる形態のプログラムストレージデバイスおよびデータストレージデバイス、例えばディスク270と、読み取り専用メモリ（ROM）230またはランダムアクセスメモリ（RAM）240と、を備え得る。例示的なコンピュータプラットフォームはまた、ROM 230、RAM 240、および／またはプロセッサ220によって実行される他のタイプの非一時的記憶媒体に記憶されたプログラム命令を含み得る。本開示の方法および／またはプロセスは、プログラム命令として実施され得る。コンピューティングデバイス200はまた、コンピュータとコンピューティングデバイス200内の他の構成要素との間の入出力をサポートする入出力コンポーネント260を備え得る。コンピューティングデバイス200はまた、ネットワーク通信を介してプログラミングおよびデータを受信し得る。
【００４５】
単に説明のために、コンピューティングデバイス200には1つのプロセッサ220のみが記載されている。しかしながら、本開示におけるコンピューティングデバイス200はまた、複数のプロセッサを備えることができ、よって、本開示に記載されるように1つのプロセッサ220によって実行される動作および／または方法ステップもまた、複数のプロセッサによって一緒または別々に実行され得ることに留意されたい。例えば、本開示においてコンピューティングデバイス200のプロセッサ220がステップAおよびステップBの両方を実行する場合、ステップAおよびステップBはまた、コンピューティングデバイス200において2つの異なるプロセッサによって一緒または別々に実行され得ることを理解されたい（例えば、第1のプロセッサがステップAを実行し、第2のプロセッサがステップBを実行する、または第1のプロセッサおよび第2のプロセッサが一緒にステップAおよびステップBを実行する）。
【００４６】
図3は、本開示のいくつかの実施形態による、乗客の端末130および／または運転者の端末140が実施され得る例示的なデバイスの例示的なハードウェアおよび／またはソフトウェア構成要素を示す概略図である。デバイスは、乗客または運転者の携帯電話などのモバイルデバイスであり得る。デバイスはまた、運転者が運転する車両に搭載された電子デバイスであってもよい。図3に示されるように、デバイス300は、通信プラットフォーム310と、ディスプレイ320と、グラフィック処理ユニット（GPU）330と、中央処理ユニット（CPU）340と、入出力350と、メモリ360と、ストレージデバイス390と、を備え得る。いくつかの実施形態では、システムバスまたはコントローラ（図示せず）を含むがこれらに限定されない他の任意の適切な構成要素もまたデバイス300に含まれ得る。いくつかの実施形態では、モバイルオペレーティングシステム370（例えば、iOS（商標）Android（商標）、Windows Phone（商標）など）および1つまたは複数のアプリケーション380が、CPU 340によって実行されるために、ストレージデバイス390からメモリ360にロードされ得る。アプリケーション380は、オンラインツーオフラインサービスに関連する情報または他の情報をサーバ110から受信およびレンダリングし、オンラインツーオフラインサービスに関連する情報または他の情報をサーバ110に送信するためのブラウザまたは任意の他の適切なモバイルアプリを含み得る。情報ストリームとのユーザ対話は、入出力350を介して達成され、ネットワーク120を介してサーバ110および／または人工知能システム100の他の構成要素に提供され得る。いくつかの実施形態では、デバイス300は、マイクロフォン315などの、音声情報を取り込むためのデバイスを備え得る。
【００４７】
図4Aは、本開示のいくつかの実施形態による、地理的領域におけるグリッドを識別するための例示的な処理エンジンを示すブロック図である。処理エンジン112は、ストレージデバイス（例えば、ストレージデバイス150、乗客の端末130、または運転者の端末140）と通信することができ、ストレージデバイスに記憶された命令を実行することができる。いくつかの実施形態では、処理エンジン112は、ジオフェンス情報取得モジュール410と、ジオフェンス境界判定モジュール420と、囲繞エリア判定モジュール430と、サブエリア判定モジュール440と、内部グリッド判定モジュール450と、グリッドインデックス判定モジュール460と、ターゲットグリッド判定モジュール470と、を備え得る。
【００４８】
ジオフェンス情報取得モジュール410は、地図における地理的領域のジオフェンスの情報を取得するように構成され得る。いくつかの実施形態では、ジオフェンス情報取得モジュール410は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、プロバイダの端末140、サーバ110、ストレージデバイス150）からジオフェンスの情報を取得し得る。いくつかの実施形態では、ジオフェンスは、地理的座標系の1セットの座標対に基づいて判定され得る。各座標対は、経度および緯度を含み得る。各座標対は、ジオフェンスの境界点に関連し得る。ジオフェンス情報取得モジュール410は、ジオフェンスに関連する1セットの座標対を同時にまたは順番に取得し得る。代替的または追加的に、ジオフェンスは、中心および半径によって定義される円に基づいて判定され得る。中心は、経度および緯度を含む座標対に対応し得る。半径は、例えば、数メートル、数十メートル、数百メートルなどの長さに対応し得る。
【００４９】
ジオフェンス境界判定モジュール420は、地図の複数のグリッドからジオフェンスの境界グリッド系列を判定するように構成され得る。いくつかの実施形態では、境界グリッド系列は、一次元ベクトルとして表され得る。ジオフェンスの境界グリッド系列は、ジオフェンスによって通過される1セットの境界グリッドを含み得る。いくつかの実施形態では、ジオフェンスの境界グリッド系列には1つまたは複数のピボットグリッドがある。ピボットグリッドは、境界グリッド系列に2回以上現れ得る。1つのピボットグリッドが現れる回数は、ジオフェンスがピボットグリッドを通過する回数と同じであり得る。いくつかの実施形態では、境界グリッド系列にはピボットグリッドはない。
【００５０】
囲繞エリア判定モジュール430は、地理的領域における少なくとも1つの囲繞エリアを識別するように構成され得る。いくつかの実施形態では、ジオフェンスによって囲まれた地理的領域は、1つまたは複数の囲繞エリアを含み得る。各囲繞エリアは、地理的領域に含まれ、かつジオフェンスの境界グリッド系列（最終的な境界グリッド系列）の一連の境界グリッドで囲まれたエリアを指し得る。囲繞エリア判定モジュール430は、ジオフェンスの境界グリッド系列に基づいて、地理的領域における少なくとも1つの囲繞エリアを識別し得る。
【００５１】
サブエリア判定モジュール440は、囲繞エリアを2つ以上のサブエリアにセグメント化するように構成され得る。いくつかの実施形態では、囲繞エリアが2つ以上の区画を横切ると判定すると、サブエリア判定モジュール440は、囲繞エリアを2つ以上のサブエリアにセグメント化し得る。セグメント化後、2つ以上のサブエリアの各サブエリアは、1つの区画にのみ位置し得る。サブエリア判定モジュール440はまた、2つ以上のサブエリアのそれぞれについて境界グリッドを判定するように構成され得る。いくつかの実施形態では、サブエリア判定モジュール440は、2つ以上のサブエリアが複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定し得る。サブエリア判定モジュール440は、重複辺グリッドを2つ以上のサブエリアの境界グリッドとして、2つ以上のサブエリアにさらに追加し得る。
【００５２】
内部グリッド判定モジュール450は、サブエリアの境界グリッドおよびサブエリアが位置する区画のインデックスに基づいて、地図の複数のグリッドからサブエリアにおける内部グリッドを識別するように構成され得る。サブエリアにおける内部グリッドは、サブエリアの境界グリッドによって囲まれたグリッドを指し得る。いくつかの実施形態では、内部グリッド判定モジュール450は、光線法を使用してサブエリアにおける内部グリッドを判定し得る。
【００５３】
グリッドインデックス判定モジュール460は、地理的位置に対応するグリッドのインデックスを判定するように構成され得る。グリッドインデックス判定モジュール460は、地理的位置に対応する地理的座標系の座標対をまず取得し得る。地理的位置は、特定のグリッドに関連し得る。次に、グリッドインデックス判定モジュール460は、座標対を投影座標系の投影座標に変換し得る。最後に、グリッドインデックス判定モジュール460は、特定のグリッドのグリッドインデックスを判定し得る。
【００５４】
ターゲットグリッド判定モジュール470は、地理的領域におけるグリッド（本明細書では地理的領域のターゲットグリッドとも呼ばれる）を識別するように構成され得る。いくつかの実施形態では、各サブエリアについて、ターゲットグリッド判定モジュール470は、サブエリアにおける内部グリッドおよびサブエリアの境界グリッドを、サブエリアに対応するターゲットグリッドとして指定し得る。ターゲットグリッド判定モジュール470は、地理的領域におけるサブエリアのそれぞれに対応するすべてのターゲットグリッドを収集することによって、地理的領域のターゲットグリッドを判定し得る。
【００５５】
処理エンジン112の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することは意図されていないことに留意されたい。当業者であれば、本開示の教示の下で複数の変更および修正を行い得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱するものではない。いくつかの実施形態では、モジュールのうちの2つ以上が単一のモジュールに組み合わされ得る。例えば、グリッドインデックス判定モジュール460は、ジオフェンス境界判定モジュール420に統合されてもよい。別の例として、内部グリッド判定モジュール450は、サブエリア判定モジュール440に統合されてもよい。サブエリア判定モジュール440は、サブエリアの境界グリッドおよび内部境界グリッドの両方を判定することができる。いくつかの実施形態では、モジュールのうちのいずれか1つが2つ以上のサブモジュールに分割され得る。例えば、サブエリア判定モジュール440は、第1のサブモジュールと第2のサブモジュールとに分割され得る。第1のサブモジュールは、2つ以上のサブエリアの各サブエリアが1つの区画のみに位置するように、囲繞エリアを2つ以上のサブエリアにセグメント化するように構成され得る。第2のサブモジュールは、サブエリアの境界グリッドを判定するように構成され得る。
【００５６】
図4Bは、本開示のいくつかの実施形態による例示的なジオフェンス境界判定モジュール420を示すブロック図である。ジオフェンス境界判定モジュール420は、識別ユニット421と、選択ユニット422と、判定ユニット423と、除去ユニット424と、補間ユニット425と、更新ユニット426と、を備え得る。
【００５７】
識別ユニット421は、複数の境界点に対応する境界グリッド系列（例えば、初期境界グリッド系列）を識別するように構成され得る。いくつかの実施形態では、初期境界グリッド系列は、複数のグリッド（本明細書では境界グリッドとも呼ばれる）を含み得る。各グリッドは境界点に対応し得る。境界点は、グリッドにおける任意の点、例えば、グリッドの中心点、グリッドの頂点などであり得る。いくつかの実施形態では、2つ以上の境界点が同じグリッドに対応し得るため、初期境界グリッドは2つ以上の同じグリッドを含み得る。いくつかの実施形態では、2つの隣接する境界点に対応する2つのグリッドが地図において隣接していない場合があるため（例えば、線分を使用して2つの境界点を接続する場合、線分は3つ以上のグリッドを占有する）、ジオフェンスを表すために境界点を使用するだけでは完全ではない。したがって、初期境界グリッド系列は、任意の2つの隣接する境界点によって占有されるすべてのグリッドが最終的な境界グリッド系列に含まれるように、最終的な境界グリッド系列を生成するために更新され得る。
【００５８】
選択ユニット422は、複数の境界点から2つの隣接する境界点を選択するように構成され得る。複数の境界点は、1つまたは複数の点を補間または除去することによって更新され得る。選択された2つの隣接する境界点は、（更新された）複数の境界点における任意の2つの隣接する点を指し得る。
【００５９】
判定ユニット423は、2つの隣接する境界点が同じグリッドに対応するか否かを判定するように構成され得る。例えば、2つの隣接する境界点に対応するグリッドインデックスが互いに同じである場合、判定ユニット423は、2つの隣接する境界点が同じグリッドに対応すると判定し得る。別の例として、2つの隣接する境界点に対応するグリッドインデックスが異なる場合、判定ユニット423は、2つの隣接する境界点が2つの異なるグリッドに対応すると判定し得る。
【００６０】
除去ユニット424は、複数の境界点から境界点を除去するように構成され得る。具体的には、2つの隣接する境界点が同じグリッドに対応する場合、除去ユニット424は、2つの隣接する境界点のうちの1つを除去し得る。除去される境界点は、2つの隣接する境界点のうちの任意の1つであり得る。いくつかの実施形態では、除去ユニット424は、複数の境界点を横断することによって1つまたは複数の境界点を除去し得る。
【００６１】
補間ユニット425は、2つの隣接する境界点の間にある点を補間するように構成され得る。いくつかの実施形態では、補間ユニット425は、2つの隣接する境界点の間の点を選択し得る。選択された点は、2つの隣接する境界点の間の任意の点、例えば、2つの隣接する境界点の中点、2つの隣接する境界点のうちの1つ付近の点、または2つの隣接する境界点の間の他の任意の点であり得る。補間ユニット425はまた、補間条件が満たされているか否かを判定し得る。補間条件は、選択された点に対応するグリッドが、2つの隣接する境界点に対応するグリッドのいずれとも異なることであり得る。補間条件が満たされた場合、補間ユニット425は、2つの隣接する境界点の間にある選択された点を補間し、選択された点をジオフェンスの境界点として指定し得る。いくつかの実施形態では、補間ユニット425は、複数の境界点を横断することによって1つまたは複数の境界点を補間し得る。
【００６２】
更新ユニット426は、境界グリッド系列を更新するように構成され得る。いくつかの実施形態では、更新ユニット426は、1つまたは複数の除去された境界点に対応する1つまたは複数のグリッドを除去することによって、境界グリッド系列を更新し得る。いくつかの実施形態では、更新ユニット426は、1つまたは複数の補間された境界点に対応する1つまたは複数のグリッドを補間することによって、境界グリッド系列を更新し得る。更新後、最終的な境界グリッド系列が判定され得る。
【００６３】
図4Cは、本開示のいくつかの実施形態による例示的な囲繞エリア判定モジュール430を示すブロック図である。囲繞エリア判定モジュール430は、グリッド取得ユニット431と、ピボットグリッド判定ユニット432と、囲繞エリア判定ユニット433と、を備え得る。
【００６４】
グリッド取得ユニット431は、地理的領域に関連する境界グリッド系列を取得するように構成され得る。いくつかの実施形態では、境界グリッド系列は、ジオフェンスが通過するすべてのグリッドを含み得る。境界グリッド系列のグリッドは、ジオフェンスによって通過される順序で配置され、順番に番号が付けられ得る。各グリッドは、一意のシーケンス番号に対応し得る。例えば、境界グリッド系列のグリッドの数がnの場合、グリッドのシーケンス番号は、それに応じて「1」、「2」、「3」、．．．、「n」とマークされ得る。いくつかの実施形態では、グリッド取得ユニット431は、例えば、ジオフェンス境界判定モジュール420またはストレージデバイス（例えば、ストレージデバイス150）から、境界グリッド系列におけるグリッドを順次取得し得る。単なる例として、グリッド取得ユニット431は、シーケンス番号1に対応するグリッドを取得し、次にシーケンス番号2に対応するグリッドを取得し、．．．、最後にシーケンス番号nに対応するグリッドを取得し得る。
【００６５】
ピボットグリッド判定ユニット432は、境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定するように構成され得る。ピボットグリッドは、ジオフェンスが2回以上通過するグリッドを指し得、ピボットグリッドは境界グリッド系列に2回以上現れ得る。いくつかの実施形態では、ピボットグリッド判定ユニット432は、探索技法を使用して、境界グリッド系列が2つ以上の同じグリッドを含むか否かを判定し得る。例えば、ピボットグリッド判定ユニット432は、グリッドの相対位置に基づいて境界グリッド系列のグリッドについてリンクリストまたは地図を作成することができ、次にピボットグリッド判定ユニット432は、リンクリストまたは地図を探索することを通して、境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定することができる。
【００６６】
囲繞エリア判定ユニット433は、1つまたは複数の囲繞エリアを判定するように構成され得る。いくつかの実施形態では、地理的領域に関連する境界グリッド系列がピボットグリッドを含まない場合、囲繞エリア判定ユニット433は、地理的領域を囲繞エリアとして指定し得る。代替的または追加的に、地理的領域に関連する境界グリッド系列が1つまたは複数のピボットグリッドを含む場合、囲繞エリア判定ユニット433は、1つまたは複数のピボットグリッドに基づいて1つまたは複数の囲繞エリアを判定し得る。各ピボットグリッドについて、囲繞エリア判定ユニット433は、ピボットグリッドの一方の側にある地理的領域におけるエリアを、第1の囲繞エリアとして、またピボットグリッドの他方の側にある地理的領域におけるエリアを、第2の囲繞エリアとして識別し得る。ピボットグリッドに関連付けられた囲繞エリアの数は、境界グリッド系列に現れるピボットグリッドの回数に基づいて判定され得る。
【００６７】
図4Dは、本開示のいくつかの実施形態による例示的なサブエリア判定モジュール440を示すブロック図である。サブエリア判定モジュール440は、重複辺グリッド判定ユニット441と、境界グリッド判定ユニット442と、を備え得る。
【００６８】
重複辺グリッド判定ユニット441は、サブエリアが複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定するように構成され得る。重複辺グリッド判定ユニット441は、辺上のサブエリアの境界グリッドに基づいて、1つまたは複数の重複辺グリッドを判定し得る。
【００６９】
境界グリッド判定ユニット442は、サブエリアの境界グリッドを判定するように構成され得る。いくつかの実施形態では、サブエリアについて、境界グリッド判定ユニット442は、サブエリアに関連する囲繞エリア（本明細書ではサブエリアの初期境界グリッドとも呼ばれる）の重複辺グリッドおよび境界グリッドに基づいて、サブエリアの境界グリッドを判定し得る。具体的には、境界グリッド判定ユニット442は、サブエリアの境界グリッド（本明細書では最終的な境界グリッドとも呼ばれる）を判定するために、サブエリアの初期境界グリッドとサブエリアに関連する重複辺グリッドとを組み合わせ得る。
【００７０】
図4Eは、本開示のいくつかの実施形態による例示的な内部グリッド判定モジュール450を示すブロック図である。内部グリッド判定モジュール450は、行列初期化ユニット451と、行列更新ユニット452と、内部グリッド判定ユニット453と、を備え得る。
【００７１】
行列初期化ユニット451は、行列を初期化するように構成され得る。行列は、複数のセルを含むスキャニング行列であり得る。いくつかの実施形態では、スキャニング行列は、サブエリアの境界グリッドに基づいて判定され得る。行列初期化ユニット451は、スキャニング行列の各セルに第1の値を入力することによってスキャニング行列を初期化し得る。スキャニング行列に入力される第1の値は、任意の形式、例えば、数字、文字にすることができる。いくつかの実施形態では、第1の値はゼロであり得る。
【００７２】
行列更新ユニット452は、行列（例えば、スキャニング行列）に対しての1回または複数回の更新を実行するように構成され得る。いくつかの実施形態では、行列更新ユニット452は、スキャニング行列の第1の複数のセルのそれぞれに第2の値を入力することによって、スキャニング行列に対して第1の更新を実行し得る。第1の複数のセルは、サブエリアの境界グリッドに対応し得る。第2の値は、第1の値とは異なる任意の値（または数）、例えば1とすることができる。第1の更新後、一部のセル（例えば、第1の複数のセル）は第2の値を有し得、一部のセルは依然として第1の値を有し得る。いくつかの実施形態では、第1の値を有するセルに対応するグリッドが地理的領域にある場合、対応するセルは、スキャニング行列の第2の複数のセルと呼ばれ得る。行列更新ユニット452は、スキャニング行列の第2の複数のセルに第3の値を入力することによって、スキャニング行列に対して第2の更新を実行し得る。第3の値は、第1の値以外の任意の値（または数）であり、第2の値と同じであっても異なっていてもよい。例えば、第3の値は2であり得る。
【００７３】
内部グリッド判定ユニット453は、サブエリアにおける内部グリッドを判定するように構成され得る。例えば、内部グリッド判定ユニット453は、第3の値を有するセルに対応するグリッドを、サブエリアにおける内部グリッドとして指定し得る。
【００７４】
内部グリッド判定モジュール450の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することは意図されていないことに留意されたい。当業者であれば、本開示の教示の下で複数の変更および修正を行い得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱するものではない。いくつかの実施形態では、内部グリッド判定モジュール450はまた、セル判定ユニット（図4Eには示さず）を備え得る。第1の値を有するセルについては、セル判定ユニットは、セルに対応するグリッドが地理的領域にあるか否かを判定し、次に、スキャニング行列の第2の複数のセルを判定し得る。
【００７５】
図4Fは、本開示のいくつかの実施形態による例示的なグリッドインデックス判定モジュール460を示すブロック図である。グリッドインデックス判定モジュール460は、座標取得ユニット461と、座標変換ユニット462と、グリッドインデックス判定ユニット463と、を備え得る。
【００７６】
座標取得ユニット461は、座標対を取得するように構成され得る。いくつかの実施形態では、座標取得ユニット461は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、運転者の端末140、サーバ110、ストレージデバイス150、またはサーバ110の他の構成要素）から座標対を取得し得る。座標対は、地理的座標系の地理的座標であり得る。いくつかの実施形態では、座標対は、ジオフェンス上の座標対（例えば、1セットの座標対のうちの1つであり、座標対はサンプル点に対応する）を指し得る。いくつかの実施形態では、座標対は、ユーザ（例えば、乗客、運転者）の地理的位置に対応する座標対を指し得る。
【００７７】
座標変換ユニット462は、地理的座標系の座標対を投影座標系の投影座標に変換するように構成され得る。いくつかの実施形態では、座標変換ユニット462は、1つまたは複数の座標変換演算に基づいて、投影座標系の投影座標を判定し得る。具体的には、座標変換ユニット462は、座標対を球座標系の球座標にまず変換し得る。次に、座標変換ユニット462は、球座標をデカルト座標に変換し得る。座標変換ユニット462は、デカルト座標を投影座標系の投影座標にさらに変換し得る。
【００７８】
グリッドインデックス判定ユニット463は、投影座標に基づいて、座標対に対応するグリッドインデックスを判定するように構成され得る。具体的には、グリッドインデックス判定ユニット463は、細分化レベル、DGGSに関連する多面体の形状、座標対が含まれる対応する区画のインデックス、および／または対応するグリッドの投影座標（例えば、第2の投影座標）に基づいて、座標対に対応するグリッドインデックスを判定し得る。いくつかの実施形態では、グリッドインデックスは地図における区画上のグリッドを一意に識別するために使用され得る。グリッドインデックスは、1つまたは複数の数字、1つまたは複数の文字、1つまたは複数の記号などの組み合わせとして表され得る。
【００７９】
図5は、本開示のいくつかの実施形態による、地図の地理的領域におけるグリッドを識別するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス500は、図1に示される人工知能システム100において実施され得る。例えば、プロセス500は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス500は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図5に示され、以下で説明されるプロセス500の動作の順序は、限定するものであることは意図されていない。
【００８０】
地理的領域は、国、省、州、都市、または地球上の特定の領域であり得る。地理的領域に関連する情報を取得するために、処理エンジン112は、地理的領域におけるグリッドをまず判定し得る。例えば、北京市に関連する情報を取得するために、処理エンジン112は、北京市に関連するすべてのグリッドをまず識別し得る。図13Aは、北京市の地理的領域におけるグリッドを示す概略図である。別の例として、特定の位置の周りの特定の範囲を有する地理的領域に関連する情報を取得するために、処理エンジン112は、特定の位置の周りの地理的領域におけるグリッドをまず判定し得る。図13Bは、円形の地理的領域1350におけるグリッドを示す概略図である。円形の地理的領域1350の中心は、地理的座標系における（116．39712800000001，39．915663499999994）の座標対として表される。座標対の第1の項は、特定の位置の経度である。座標対の第2の項は、特定の位置の緯度である。円形の地理的領域1350の半径は81640．2155113325メートルである。図13Aおよび図13Bに示されるように、地理的領域は複数のグリッドを含む。いくつかの実施形態では、処理エンジン112は、複数のグリッドに関連するデータを抽出し、データに基づいて1つまたは複数の戦略を作ることができる。例えば、処理エンジン112は、異なるグリッドにおけるサービス要求に関連する情報を抽出することができる。より多数のサービス要求のある領域の場合、処理エンジン112は、より多くのサービスプロバイダをその領域に送り込む必要があると判定し得る。より少数のサービス要求のある領域の場合、処理エンジン112は、領域における一部のサービスプロバイダをその領域から送り出す必要があると判定し得る。510において、処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、地図における地理的領域のジオフェンスの情報を取得し得る。
【００８１】
いくつかの実施形態では、処理エンジン112は、ストレージデバイス（例えば、ストレージデバイス150、ROM 230、RAM 240）からの地図を評価し得る。例えば、処理エンジン112は、地図の少なくとも一部をストレージデバイスから少なくとも1つのキャッシュ回路にロードし得る。処理エンジン112は、人工知能システム100の構成要素（例えば、乗客の端末130、運転者の端末140、またはサーバ110）上に地図の表示を事前にさらに生成し得る。いくつかの実施形態では、地図は、離散グローバルグリッドシステム（DGGS）で地球を表し得る。地図は、複数の区画、例えば、4つの区画、6つの区画、8つの区画、12の区画、20の区画に分割され得る。複数の区画は、実質的に同じサイズおよび形状を有し得る。区画は、多面体、例えば、四面体、立方体、八面体、十二面体、二十面体を構成することができる。多面体はおおよそ地球を表し得る。いくつかの実施形態では、地球を表す多面体は、図7Bに示される八面体であってもよい。図示のように、八面体は6つの頂点を有する。地理的座標系の6つの頂点の座標は、（0，90）、（0，−90）、（0，0）、（90，0）、（−90，0）、および（180，0）であり得る。頂点のうちの2つ（例えば、AおよびF）は、それぞれ地球の2つの極を表し得る。他の4つの頂点（例えば、B、C、D、およびE）は、地球の赤道を4つの等しい部分に分割し得る。点Gは地球の中心点を表し得る。八面体は、地球の表面の8つの部分に対応し得る8つの区画（例えば、ΔABC、ΔACD、ΔADE、ΔAEB、ΔFBC、ΔFCD、ΔFDE、ΔFEB）を含む。例えば、ΔABC、ΔACD、ΔADE、およびΔAEBは、それぞれ、地球の北半球表面の四分の一に対応し得る。別の例として、ΔFBC、ΔFCD、ΔFDE、およびΔFEBは、それぞれ、地球の南半球表面の四分の一に対応し得る。
【００８２】
いくつかの実施形態では、区画は独立にインデックス付けされ得る。各区画は、インデックス（本明細書では区画インデックスとも呼ばれる）に関連付けられ得る。
【００８３】
単なる例として、図7Bに示されるように、八面体の8つの区画は、0から7まで番号付けされ得る。八面体の区画のインデックスは、地理的座標系における地理的座標の経度および緯度の範囲に基づいて判定され得る。八面体の区画のインデックスは、式（1）に従って判定され得る。
【数１】
2021508856.tif 000003
fは、八面体の区画のインデックスを指し、latは、地理的座標系の座標対の緯度を指し、lonは、地理的座標系の座標対の経度を指し得る。
【００８４】
図7Kに示されるように、八面体の8つの区画は、平面に展開され得る。8つの区画のインデックスは、0、1、2、3、4、5、6、および7であり得る。
いくつかの実施形態では、処理エンジン112は、式（1）による座標対に基づいて、地理的位置における多面体の対応する区画を判定し得る。例えば、図7Bに示されるように、頂点Aの地理的座標対が（0，90）であると仮定すると、頂点Cの地理的座標は（0，0）であり、頂点Dの地理的座標対は（90，0）である。地理的座標対の第1の項は、点の経度である。地理的座標対の第2の項は、点の緯度である。座標対の経度が0〜90であり、座標対の緯度が0〜90の場合、対応する区画はΔACDになる。
【００８５】
地図（または地図の1つもしくは複数の区画）はまた、DGGSを生成するために複数のグリッドにグリッド化され得る。各グリッドは、地球上の地理的エリアに対応し得る。いくつかの実施形態では、グリッドは、正多角形の形状、例えば、三角形、長方形、正方形、菱形、六角形を有し得る。いくつかの実施形態では、グリッドは不規則な形状を有し得る。いくつかの実施形態では、グリッドの全部または一部が、同じまたは異なるサイズ（複数可）および形状（複数可）を有し得る。例えば、同じ区画にあるグリッドは同じサイズおよび同じ形状を有し、異なる区画にあるグリッドは異なるサイズおよび異なる形状を有し得る。別の例として、同じ区画にあるグリッドが、異なるサイズおよび異なる形状を有し得る。区画にある各グリッドは、インデックス（本明細書ではグリッドインデックスとも呼ばれる）に関連付けされ得る。いくつかの実施形態では、グリッドインデックスは、複数のフィールドを含み得る。グリッドインデックスの各フィールドは、グリッドインデックスに対応するグリッドがある区画に関連する細分化レベルに関連する情報、DGGSに関連する多面体の形状、グリッドインデックスに対応するグリッドがある区画の形状、グリッドインデックスに対応するグリッドがある区画のインデックス、グリッドインデックスに対応するグリッドの投影座標など、またはそれらの任意の組み合わせを含み得る。細分化レベルは、グリッドインデックスに対応するグリッドがある区画に対する細分化の回数を指し得、区画におけるグリッドの解像度を反映し得る。グリッドインデックスに関連するフィールドの順序は、事前に判定され得る。グリッドインデックスが判定されると、細分化レベル、多面体の形状、グリッドインデックスに対応するグリッドが位置する区画、または投影座標のうちの少なくとも1つが判定され得る。グリッドインデックスの判定に関する詳細は、本開示の他の場所（例えば、図7Aおよびその関連する説明）において見出され得る。いくつかの実施形態では、本開示では、「グリッド」および「グリッドインデックス」という用語は、別段の記載のない限り、交換可能に使用され得る。例えば、本開示がグリッドが判定されると説明する場合、それはまた、グリッドのグリッドインデックスが判定されることを意味する。
【００８６】
処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、運転者の端末140、サーバ110、ストレージデバイス150）から、地図における地理的領域のジオフェンスの情報を取得し得る。ジオフェンスは、地理的領域の境界を表し得る。いくつかの実施形態では、ジオフェンスは、1セットの座標対、例えば図12Aのジオフェンス1210に基づいて判定され得る。図12Aは、本開示のいくつかの実施形態による例示的なジオフェンスを示す。ジオフェンス（例えば、図12Aのジオフェンス1210）は、点（例えば、点A、点B、点C、．．．、点K）を順に接続することによって判定され得る。いくつかの実施形態では、点は境界点と呼ばれ得る。境界点は、グリッドにおける任意の点、例えば、グリッドの中心点、グリッドの頂点などであり得る。代替的または追加的に、ジオフェンスは、中心および半径によって定義される円、例えば図12Bのジオフェンス1220に基づいて判定され得る。図12Bは、本開示のいくつかの実施形態による別の例示的なジオフェンスを示す。ジオフェンス1220は円である。円の中心は点Oとして表される。円の半径はrとして表される。半径は、例えば、数メートル、数十メートル、数百メートルの長さに対応し得る。ジオフェンスの情報の取得に関する詳細は、本開示の他の場所（例えば、プロセス610のステップ611またはプロセス650のステップ651、およびそれらの関連する説明）において見出され得る。
【００８７】
520において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420）は、地図の複数のグリッドからジオフェンスの境界グリッド系列を判定し得る。いくつかの実施形態では、境界グリッド系列は、一次元ベクトルとして表され得る。ジオフェンスの境界グリッド系列は、ジオフェンスが通過する1セットの境界グリッドを含み得る。図12Aおよび図12Bでは、ジオフェンス1210またはジオフェンス1220が通るグリッドは、線分で塗りつぶされている。処理エンジン112は、図12Aの線分で塗りつぶされたグリッドをジオフェンス1210の境界グリッドとして指定し、図12Bの線分で塗りつぶされたグリッドをジオフェンス1220の境界グリッドとして指定し得る。いくつかの実施形態では、ジオフェンスの境界グリッド系列には1つまたは複数のピボットグリッドがある。ピボットグリッドは、ジオフェンスが2回以上通過するグリッドを指し得る。1つのピボットグリッドが境界グリッド系列に現れる回数は、ジオフェンスがピボットグリッドを通過する回数と同じであり得る。境界グリッド系列では、ピボットグリッドは、境界グリッド系列に2回以上現れ得、かつ2つの隣接していない境界点に対応するグリッドを指し得る。例えば、図12Aに示されるように、グリッド1214は点Gおよび点Aに対応するが、点Gと点Aとは隣接していないため、ジオフェンス1210がグリッド1214を2回通過することを示し得るため、処理エンジン112は、グリッド1214をピボットグリッドとして指定し得る。しかしながら、グリッド1213は点Cおよび点Dに対応するが、点Cと点Dとは隣接しているため、処理エンジン112は、グリッド1214をピボットグリッドとして指定しない。いくつかの実施形態では、境界グリッド系列にはピボットグリッドはない。例えば、ジオフェンスが円によって定義されている場合、ジオフェンスの境界グリッド系列はピボットグリッドを含まない。図12Bに示されるように、ジオフェンス1220は円であり、ジオフェンス1220は境界グリッドのそれぞれを1回だけ通過する。したがって、ジオフェンス1220の境界グリッド系列は、ピボットグリッドを含まない。
【００８８】
いくつかの実施形態では、処理エンジン112は、ジオフェンスの情報に基づいて、ジオフェンスの初期境界グリッド系列をまず判定し得る。いくつかの実施形態では、初期境界グリッド系列は、ジオフェンスが通過するグリッドの一部を含み得る。いくつかの実施形態では、初期境界グリッド系列は、ジオフェンスが通過するグリッド全体を含むことができるが、初期境界系列には重複グリッドがある（重複グリッドはピボットグリッドである場合もない場合もある）。初期境界グリッド系列の判定は、本開示の他の場所（例えば、図6Aおよび図6Bおよびそれらの関連する説明）において見出され得る。次に、処理エンジン112（例えば、ジオフェンス境界判定モジュール420）は、各2つの隣接する境界点が2つの隣接グリッドに確実に対応するように、初期境界グリッド系列を繰り返し更新することによりジオフェンスの境界グリッド系列を判定し得る。初期境界グリッド系列に基づくジオフェンスの最終的な境界グリッド系列の判定は、本開示の他の場所（例えば、図8およびその関連説明）において見出され得る。
【００８９】
いくつかの実施形態では、ジオフェンスによって囲まれた地理的領域は、1つまたは複数の囲繞エリアを含み得る。
【００９０】
530において、処理エンジン112（例えば、囲繞エリア判定モジュール430）は、少なくとも1つの囲繞エリアのそれぞれについて境界グリッドを判定するために、境界グリッド系列に基づいて、地理的領域における少なくとも1つの囲繞エリアを識別し得る。各囲繞エリアは、地理的領域に含まれるエリアを指し得ると同時に、囲繞エリアは、ジオフェンスの境界グリッド系列の一連の境界グリッドで囲まれる。例えば、図12Aに示されるように、ジオフェンス領域は、ピボットグリッド1214によって囲繞エリア1216と囲繞エリア1218とに分割される。囲繞エリア1216は、ピボットグリッド1214の一方の側にあり、囲繞エリア1218は、ピボットグリッド1214の他方の側にある。少なくとも1つの囲繞エリアの識別は、図9Aおよび図9Bに記載されている1つまたは複数の動作を実行することによって取得され得る。いくつかの実施形態では、少なくとも1つの囲繞エリアが識別された後、境界グリッド系列の形が行列として表され得る。行列の各行は、1つの囲繞エリアにのみ対応する境界グリッドを含み得る。
【００９１】
いくつかの実施形態では、囲繞エリアが1つの区画に位置し得る。いくつかの実施形態では、囲繞エリアは、2つ以上の区画を横切り得る。区画のそれぞれが独立にインデックス付けされるため、エリアが1つの区画のみにある場合、エリアにおけるグリッドを判定することは容易である。したがって、2つ以上の区画を横切るエリアに含まれるグリッドを判定するには、各サブエリアが1つの区画のみに位置するように、エリアを2つ以上のサブエリアにセグメント化するとより良い。
【００９２】
いくつかの実施形態では、少なくとも1つの囲繞エリアのうちの囲繞エリアについて、処理エンジン112は、囲繞エリアの境界グリッドのグリッドインデックスに従って、囲繞エリアが2つ以上の区画を横切るか否かを判定し得る。510で説明されるように、グリッドのグリッドインデックスは、グリッドがある対応する区画のインデックス（本明細書では対応する区画インデックスとも呼ばれる）を示すフィールドを含み得るため、処理エンジン112は、2つのグリッドに関連する対応する区画インデックスに基づいて、2つのグリッドが同じ区画にあるか否かを判定し得る。囲繞エリアが2つ以上の区画を横切るか否かを判定するために、処理エンジン112は、囲繞エリアの境界グリッドの区画インデックスが同じであるか否かを判定し得る。囲繞エリアの境界グリッドに関連する区画インデックスが同じであるという判定に応じて、処理エンジン112は、囲繞エリアが1つの区画に位置すると判定し得る。処理エンジン112は、囲繞エリアをセグメント化しない。
【００９３】
囲繞エリアの境界グリッドに関連する区画インデックスが異なるという判定に応じて、処理エンジン112は、囲繞エリアが2つ以上の区画を横切ると判定し得る。囲繞エリアが2つ以上の区画を横切ると判定すると、処理エンジン112（例えば、サブエリア判定モジュール440）は、540において、2つ以上サブエリアの各サブエリアが1つの区画のみにあるように、囲繞エリアを2つ以上のサブエリアにセグメント化し得る。セグメント化後、2つ以上のサブエリアの各サブエリアは、1つの区画にのみ位置し得る。
【００９４】
いくつかの実施形態では、1つの囲繞エリアが2つ以上のサブエリアにセグメント化された後、処理エンジン112は、2つ以上のサブエリアのそれぞれの境界グリッドを行列に記憶することができ、行列では、行のグリッドが1つのサブエリアにのみ関連する。
【００９５】
550において、処理エンジン112（例えば、サブエリア判定モジュール440）は、2つ以上のサブエリアのそれぞれについて境界グリッドを判定し得る。いくつかの実施形態では、処理エンジン112は、2つ以上のサブエリアが複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定し得る。処理エンジン112は、重複辺グリッドを2つ以上のサブエリアの境界グリッドとして、2つ以上のサブエリアに追加し得る。境界グリッドの判定に関するさらなる詳細は、本開示の他の場所（例えば、図10およびその関連する説明）において見出され得る。
【００９６】
560において、各サブエリアについて、処理エンジン112（例えば、内部グリッド判定モジュール450）は、サブエリアの境界グリッドおよびサブエリアが位置する区画のインデックスに基づいて、複数のグリッドからサブエリアにおける内部グリッドを識別し得る。
【００９７】
サブエリアにおける内部グリッドは、サブエリアの境界グリッドによって囲まれたグリッドを指し得る。いくつかの実施形態では、処理エンジン112が1つの区画のみに位置するサブエリアの境界グリッドを取得するとき、処理エンジン112（例えば、内部グリッド判定モジュール450）は、光線法を使用してサブエリアにおける内部グリッドを判定し得る。いくつかの実施形態では、内部グリッドの識別は、図11Aに記載されている1つまたは複数の動作によって実行することによって取得され得る。
【００９８】
570において、処理エンジン112（例えば、ターゲットグリッド判定モジュール470）は、2つ以上のサブエリアの境界グリッドおよび2つ以上のサブエリアにおける内部グリッドを収集することにより、地理的領域（本明細書ではターゲットグリッドとも呼ばれる）におけるグリッドを識別し得る。いくつかの実施形態では、人工知能システム100は、いくつかの情報を地図における複数のグリッドのそれぞれに関連付けることができる。グリッドに関連する情報は、サービスプロバイダに関連する情報、サービスリクエスタに関連する情報などを含み得る。サービスプロバイダに関連する情報は、グリッドのそれぞれにおけるサービスプロバイダの数、運転者の分布、利用可能なサービスプロバイダの数、利用可能なサービスプロバイダの分布など、またはそれらの任意の組み合わせを含み得る。サービスリクエスタに関連する情報は、特定の期間におけるグリッドに関連するサービスリクエスタの数、特定の期間におけるサービスリクエスタの分布、サービスリクエスタに関連する開始時間、サービスリクエスタに関連する開始位置、サービスリクエスタに関連する目的位置など、またはそれらの任意の組み合わせを含み得る。いくつかの実施形態では、地理的領域におけるターゲットグリッドの判定後、処理エンジン112は、さらなる処理、例えば車両スケジュールのために、ターゲットグリッドに関連する情報を抽出し得る。
【００９９】
プロセス500の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することは意図されていないことに留意されたい。当業者であれば、本開示の教示の下で複数の変更および修正を行い得る。例えば、ジオフェンスが円によって判定される場合、ジオフェンスは1つの囲繞エリアのみを含む場合があり、その場合、ステップ530は省略され得る。別の例として、各囲繞エリアが1つの区画のみに位置する場合、囲繞エリアをセグメント化する必要がない場合があり、その場合、ステップ540が省略され得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱するものではない。
【０１００】
図6Aは、本開示のいくつかの実施形態による、ジオフェンスの初期境界グリッド系列を判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス610は、図1に示される人工知能システム100において実施され得る。例えば、プロセス610は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス610は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図6Aに示され、以下で説明されるプロセス610の動作の順序は、限定するものであることは意図されていない。
【０１０１】
611において、処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、ジオフェンスに関連する1セットの座標対を取得することができる。1セットの座標対のそれぞれは、ジオフェンスの境界点に関連し得る。各座標対は、経度および緯度を含み得る。図12Aに示されるように、ジオフェンス1210には、例えば、点A、点B、点C、．．．、点Kの点があり、これらの点は、ジオフェンスの境界点である。いくつかの実施形態では、処理エンジン112は、1セットの座標対（例えば、点A、点B、．．．、点K）を同時に取得することができる。例えば、処理エンジン112は、1セットの座標対からなるベクトルを取得することができ、1セットの座標対の相対位置は、ジオフェンス上の対応する点の相対関係を示すことができる。いくつかの実施形態では、処理エンジン112は、1セットの座標対を順番に取得することができ、座標対を取得する順番は、ジオフェンス上の対応する点の相対関係を示すことができる。例えば、処理エンジン112は、最初に点A、次に点B、次に点C、．．．、最後に点Kを取得することができる。
【０１０２】
いくつかの実施形態では、処理エンジン112は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、運転者の端末140、サーバ110、ストレージデバイス150、またはサーバ110の他の構成要素）から1セットの座標対を取得し得る。例えば、ユーザ（例えば、乗客）が特定の地理的領域においてサービスプロバイダの分布を知りたい場合、ユーザは、地理的領域を定義するために、ユーザインターフェースに表示された地図に示されている点選択アイコンをいくつかの点にドラッグし得、次に、サーバ110または乗客の端末130は、1セットの座標対を生成するために点を分析し得る。別の例として、人工知能システム100のオペレータが地理的領域におけるサービスプロバイダ（例えば、運転者）の分布を知りたい場合、人工知能システム100のオペレータは、サーバ110に関連するコントローラまたはコンソールを介して、地理的領域のジオフェンスを定義するために特定の順序で1セットの座標対を入力し得る。さらに別の例として、1セットの座標対は、ストレージデバイス（例えば、ストレージデバイス150）に記憶され得、処理エンジン112は、ストレージデバイスにアクセスして1セットの座標対を取得し得る。
【０１０３】
612において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420）は、1セット座標対に基づいて、ジオフェンスの初期境界グリッド系列を判定し得る。初期境界グリッド系列は、複数のグリッド（本明細書では境界グリッドとも呼ばれる）を含み得る。初期境界グリッド系列の各グリッドは、1セットの座標対の座標対に対応し得る。座標対に関連するグリッドインデックス（またはグリッド）の判定に関する詳細は、本開示の他の場所（例えば、図7Aから図7Kおよびその関連する説明）において見出され得る。いくつかの実施形態では、2つ以上の境界点が同じグリッドに対応し得るため、初期境界グリッド系列は2つ以上の同じグリッドを含み得る。いくつかの実施形態では、2つの隣接する境界点に対応する2つのグリッドが地図において隣接していない場合があるため（例えば、線分を使用して2つの境界点を接続する場合、線分は3つ以上のグリッドを占有する）、ジオフェンスを表すために境界点を使用するだけでは完全ではない。したがって、処理エンジン112は、任意の2つの隣接する境界点によって占有される2つのグリッドの間のすべてのグリッドが最終的な境界グリッド系列に含まれるように、最終的な境界グリッド系列を生成するために初期境界グリッド系列を更新し得る。いくつかの実施形態では、最終的な境界グリッド系列は、図8に関連して説明された1つまたは複数の動作を実行することによって判定され得る。
【０１０４】
図6Bは、本開示のいくつかの実施形態による、ジオフェンスの初期境界グリッド系列を判定するための別の例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス650は、図1に示される人工知能システム100において実施され得る。例えば、プロセス650は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス650は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図6Bに示され、以下で説明されるプロセス650の動作の順序は、限定するものであることは意図されていない。
【０１０５】
651において、処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、ジオフェンスに関連する中心および半径ならびにサンプル間隔を取得し得る。いくつかの実施形態では、中心は座標対に対応し得る。半径は、例えば、数メートル、数十メートル、数百メートルなどの長さに対応し得る。円は、中心および半径に基づいて定義され得る。次に、処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、円によって表されるジオフェンスを判定し得る。いくつかの実施形態では、サンプル間隔は、サーバ110による所定の値であり得る。いくつかの実施形態では、処理エンジン112は、あるステップで中心および半径をまず取得し、次に別のステップでサンプル間隔を取得し得る。いくつかの実施形態では、中心および半径を取得した後、処理エンジン112は、円の半径およびDGGSのグリッドに関連する解像度（例えば、DGGSに関連する細分化レベル）に基づいてサンプル間隔を計算し得る。いくつかの実施形態では、サンプル間隔は、サンプル角度に対応し得る。単なる例として、サンプル角度は、以下のように式（2）に従って判定され得る。
【数２】
2021508856.tif 000004
αは、サンプル間隔に対応するサンプル角度を指し、Rは地球の半径を指し、rは円の半径を指し、nはDGGSに関連する細分化レベルを指し得る。
【０１０６】
いくつかの実施形態では、処理エンジン112は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、運転者の端末140、ストレージデバイス150、サーバ110、またはサーバ110の他の構成要素）からジオフェンス（例えば、中心および半径、ならびにサンプル間隔）に関連する情報を取得し得る。例えば、乗客の端末130／運転者の端末140のユーザは、乗客の端末130／運転者の端末140を介して地理的領域を判定するために、中心および半径を入力し得る。別の例として、人工知能システム100のオペレータが地理的領域におけるサービスプロバイダ（例えば、運転者）の分布を知りたい場合、人工知能システム100のオペレータは、サーバ110に関連するコントローラまたはコンソールを介して、地理的領域のジオフェンスを定義するために中心および半径を入力し得る。さらに別の例として、中心および半径は、ストレージデバイス（例えば、ストレージデバイス150）に記憶され得、処理エンジン112は、ストレージデバイスにアクセスしてジオフェンスに関連する中心および半径を取得し得る。
【０１０７】
652において、処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、サンプル間隔に基づいて、中心および半径によって定義される円上で複数のサンプル点を判定し得る。図12Bに示されるように、ジオフェンス1220には、例えば、点A’、点B’、点C’、．．．、点L’の点があり、サンプル点は、ジオフェンス1220の境界点である。いくつかの実施形態では、処理エンジン112は、円上で第1のサンプル点、例えば図12Bに示される点A’をまず判定し得る。処理エンジン112は、所定のサンプル間隔（例えば、サンプル角度）および第1のサンプル点に基づいて、円上で第2のサンプル点（例えば、図12Bに示される点B’）をサンプリングし得る。したがって、処理エンジン112は、サンプル間隔に基づいて、円上で第3、第4、．．．、および第Nのサンプル点をサンプリングし得る。いくつかの実施形態では、第1のサンプル点およびサンプル間隔が判定されると、処理エンジン112（例えば、ジオフェンス情報取得モジュール410）は、第1のサンプル点およびサンプル間隔に基づいて他のサンプル点を同時に取得し得る。処理エンジン112は、時計回りまたは反時計回りに複数のサンプル点をサンプリングし得る。
【０１０８】
653において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420）は、複数のサンプル点に基づいて、ジオフェンスの初期境界グリッド系列を判定し得る。サンプル点に基づくグリッド（またはグリッドインデックス）の判定に関する詳細は、本開示の他の場所（例えば、図7Aから図7Kおよびその関連する説明）において見出され得る。いくつかの実施形態では、初期境界グリッド系列は、複数のグリッドを含み得る。サンプル間隔が特定のサンプル値よりも小さい場合、初期境界グリッド系列は重複グリッドを含み得る。サンプル間隔が特定のサンプル値より大きい場合、ジオフェンスを表すために初期境界グリッド系列のグリッドのみを使用することは完全ではない。したがって、処理エンジン112は、円によって占有されるすべてのグリッドが最終的な境界グリッド系列に含まれるように、最終的な境界グリッド系列を生成するために初期境界グリッド系列を更新し得る。いくつかの実施形態では、最終的な境界グリッド系列は、図8に関連して説明された1つまたは複数の動作を実行することによって判定され得る。
【０１０９】
図7Aは、本開示のいくつかの実施形態による、座標対に対応するグリッドインデックスを判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス700は、図1に示される人工知能システム100において実施され得る。例えば、プロセス700は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス700は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図7Aに示され、以下で説明されるプロセス700の動作の順序は、限定するものであることは意図されていない。いくつかの実施形態では、プロセス610のステップ612およびプロセス650のステップ653は、プロセス700に従って実行され得る。
【０１１０】
710において、処理エンジン112（例えば、グリッドインデックス判定モジュール460の座標取得ユニット461）は、地理的位置に対応する座標対を取得し得る。座標対は、地理的座標系の経度および緯度を含み得る。いくつかの実施形態では、座標対は、図6Aで説明される1セットの座標対、図6Bで説明されるサンプル点に対応する座標対、ユーザ（例えば、乗客、運転者）の地理的位置に対応する座標対のうちの1つを指し得る。
【０１１１】
いくつかの実施形態では、処理エンジン112は、人工知能システム100の1つまたは複数の構成要素（例えば、乗客の端末130、運転者の端末140、サーバ110、ストレージデバイス150、またはサーバ110の他の構成要素）からユーザの地理的位置に対応する座標対を取得し得る。例えば、処理エンジン112は、乗客の端末130／運転者の端末140からユーザ（例えば、乗客、運転者）によって入力された座標対を取得し得る。別の例として、ユーザ（例えば、乗客、運転者）の地理的位置は、端末（例えば、乗客の端末130、運転者の端末140）に取り付けられたGPS受信機によって判定され得る。処理エンジン112は、GPS受信機を介してユーザの地理的位置に対応する座標対を取得し得る。さらなる例として、座標対は、ストレージデバイス（例えば、ストレージデバイス150）に送信され得る。処理エンジン112は、ストレージデバイスにアクセスし、座標対を取得することができる。
【０１１２】
720において、処理エンジン112（例えば、グリッドインデックス判定モジュール460の座標変換ユニット462）は、地理的位置に対応する座標対を投影座標系の投影座標に変換し得る。いくつかの実施形態では、地図における各区画について、投影座標系が構築され得る。図7Hに示されるように、例として区画ΔACDを取り上げると、ACおよびADは、I軸およびJ軸として指定され得る。頂点Aを通り、区画ΔACDに垂直な軸は、K軸として指定され得る。いくつかの実施形態では、処理エンジン112は、1つまたは複数の座標変換演算に基づいて、投影座標系の投影座標を判定し得る。
【０１１３】
いくつかの実施形態では、処理エンジン112は、座標対を球座標系の球座標に変換し得る。球座標系では、地理的位置に対応する球座標はP（r，φ，θ）として表され得る。地理的座標系の座標対と球座標系の球座標とは相互変換可能であり得る。いくつかの実施形態では、処理エンジン112は、式（3）に従って、座標対（例えば、P（lon，lat））を球座標（例えば、P（1，φ，θ））に変換することができる。代替的または追加的に、処理エンジン112は、式（4）に従って球座標を座標対に変換することができる。
【数３】
2021508856.tif 000005
【数４】
2021508856.tif 000006
latは地理的座標系の座標対の緯度を指し、lonは、地理的座標系の座標対の経度を指し、φは、球座標の極角を指し、θは、球座標の方位角を指し、「rad2deg」は、ラジアンを角度に変換する関数を指し、「deg2rad」は、角度をラジアンに変換する関数を指し得る。
【０１１４】
いくつかの実施形態では、処理エンジン112はまた、球座標をデカルト座標に変換することもできる。デカルト座標（直交座標とも呼ばれる）は、二次元（2D）表面上または三次元（3D）空間内の点の位置を示し得る。球座標とデカルト座標とは相互変換可能であり得る。いくつかの実施形態では、処理エンジン112は、式（5）に従って、球座標系における球座標（例えば、P（r，φ，θ））をデカルト座標（例えば、（x，y，z））に変換することができる。代替的または追加的に、処理エンジン112は、式（6）に従ってデカルト座標を球座標に変換することができる。
【数５】
2021508856.tif 000007
【数６】
2021508856.tif 000008
xは、地理的位置のX軸への垂直投影の位置を指し、yは、地理的位置のY軸への垂直投影の位置を指し、zは、地理的位置のZ軸上への垂直投影の位置を指し得る。
【０１１５】
方位角θは［−π，π］の範囲にあるが、arctan関数の値は
【数７】
2021508856.tif 000009
の範囲にあり、方位角θの範囲とは異なることに留意されたい。この差を補償するために、方位角θは、座標（x，y）の象限に基づいて判定され得る。具体的には、x＝0である場合、方位角θは式（7）に基づいて判定され得る。
【数８】
2021508856.tif 000010
【０１１６】
x＜0の場合、方位角θは式（8）に基づいて判定され得る。
【数９】
2021508856.tif 000011
【数１０】
2021508856.tif 000012
である。
【０１１７】
x＞0の場合、方位角θは、
【数１１】
2021508856.tif 000013
として判定され得る。
【０１１８】
関数arccosの値は［0，π］の範囲にあり、極角φの範囲と一致している。
【０１１９】
処理エンジン112は、デカルト座標を投影座標系の投影座標にさらに変換し得る。デカルト座標と投影座標とは相互変換可能であり得る。図7Hに示されるように、GD、GA、およびGCは、それぞれ、デカルト座標系のX軸、Y軸、およびZ軸に対応し得る。点Gはデカルト座標系の原点であり得る。地球の半径が1単位の長さであると仮定すると、点A、C、D、およびP（上記の地理的位置）のデカルト座標は（0，1，0）、（0，0，1）、（1，0，0）、およびP（x，y，z）であり得る。投影座標系では、ACおよびADはI軸およびJ軸に対応し得る。点Aを通り、区画ΔACDに垂直な軸は、K軸に対応し得る。点P’は、区画ΔACD上の地理的位置Pの投影点であり得る。本明細書で使用される場合、投影点P’は、線と区画ΔACDとの交点を指し、線は、地球上の地理的位置と地球の中心点とを接続し得る。投影点P’は、投影座標P’（i，j，k）を有し得る。
【０１２０】
ベクトルAP’は、式（9）に基づいて判定され得る。
【数１２】
2021508856.tif 000014
【数１３】
2021508856.tif 000015
はベクトルAP’を指し、
【数１４】
2021508856.tif 000016
はベクトルACを指し、
【数１５】
2021508856.tif 000017
はベクトルADを指し得る。
【０１２１】
ベクトルAPは、式（10）に基づいて判定され得る。
【数１６】
2021508856.tif 000018
【数１７】
2021508856.tif 000019
はベクトルAPを指し、
【数１８】
2021508856.tif 000020
はベクトルGPを指し得る。
【０１２２】
デカルト座標P（x，y，z）と投影座標P’（i，j，k）とは、式（11）に示される関係を有し得る。
【数１９】
2021508856.tif 000021
【０１２３】
式（11）は、式（12）として表され得る。
【数２０】
2021508856.tif 000022
【０１２４】
s＝x＋y＋zと仮定すると、投影座標P’（i，j，k）は式（13）に基づいて判定され得る。
【数２１】
2021508856.tif 000023
【０１２５】
投影座標系における投影点P’の投影座標P’（i，j，k）が判定され得る。
【０１２６】
730において、処理エンジン112（例えば、グリッドインデックス判定モジュール460のグリッドインデックス判定ユニット463）は、投影座標に基づいて地理的位置の座標対に対応するグリッドインデックスを判定し得る。
【０１２７】
いくつかの実施形態では、地図における各区画は、複数のグリッドに分割され得る。各グリッドは、三角形、長方形、正方形、菱形、六角形などの形状を有し得る。分割により形成されたグリッドは、同じまたは異なるサイズ（複数可）および形状（複数可）を有し得る。いくつかの実施形態では、各区画は、グリッドに関連する比較的細かい解像度を実現するために、より小さい面積を有するより多くのグリッドに分割されてもよい。細分化操作が、より細かいグリッドを生成するために区画を細分割することに適用され得、これは、1セットの比較的粗いグリッドを比較的細かいグリッドに変換することを指し得る。
【０１２８】
いくつかの実施形態では、細分化操作は、細分化係数mに基づいて実行され得る。細分化係数mは、グリッドが単一の細分化操作でどのくらい細かく分割され得るかを指し得る。いくつかの実施形態では、地図における複数のグリッドは、1対mの細分化に基づいて生成され得る  具体的には、1対mの細分化によれば、面積Aのグリッド（または多面体の区画）は、面積A／mのm個のグリッドに分割され得る。例えば、1対4の細分化では、面積Aの各グリッドが面積がA／4の4つのグリッドに分割され得る。よって、グリッドの数は、1つの解像度から次の解像度まで4倍に指数関数的に増加し得る。いくつかの実施形態では、細分化操作は1回または複数回実行され得る。細分化操作の回数は、細分化レベルと呼ばれ得る。いくつかの実施形態では、細分化レベルは、処理エンジン112によって判定されるデフォルト値とすることができる、または端末（例えば、乗客の端末130、運転者の端末140）を介してユーザによって設定または調整され得る。いくつかの実施形態では、異なる回数で2回以上の細分化操作は、同じ細分化係数に基づいて実行され得る。いくつかの実施形態では、異なる回数で2回以上の細分化操作は、異なる細分化係数に基づいて実行され得る。例えば、1対4の細分化が第1の細分化操作で実行され、その後、1対2の細分化が第2の細分化操作で実行され得る。
【０１２９】
いくつかの実施形態では、区画の複数のグリッドは、1つまたは複数の細分化係数および細分化レベルに従って細分化操作の1つまたは複数の繰り返しを実行することによって生成され得る。図7Cから図7Eは、本開示のいくつかの実施形態による、八面体の区画を細分化するための例示的な細分化操作を示す概略図である。ΔHIJは、八面体の例示的な区画を表し得る。図7Cに示されるように、第1の細分化操作において、1対4．5の細分化が実行され得、菱形の形状を有する4．5個の第1のグリッドが生成され得る。具体的には、処理エンジン112は、解像度1で複数の第1の点を取得するために、区画ΔHIJの各側に沿って3分割の2つの点を判定し得る。解像度1では、3つの頂点H、I、およびJが第1の点と見なされ得る。単なる例として、第1の点は、点g、j、k、m、n、およびiを含み得る。本開示では、「第1の点」および「第1のレベルの等分点」という用語は、交換可能に使用される。複数の第1のグリッドは、第1の点に基づいて形成され得る。第1のグリッドは、3つの完全な菱形（例えば、菱形「Hghi」、「gjkh」、「ihmn」）と3つの不完全な菱形（例えば、半菱形「jIk」、「hkm」、「nmJ」）を含み得る。第1のグリッドは、解像度1のグリッドと見なされ得る。解像度1のグリッドの細分化レベルは1であり得る。
【０１３０】
より細かい解像度のグリッドを得るために、処理エンジン112は、異なる解像度でグリッドを生成するために、細分化操作の1回または複数回の繰り返しを実行し得る。図7Dに示されるように、第2の細分化操作において、1対4の細分化が実行され得、各第1のグリッドについて菱形の形状を有する4個の第1のグリッドが生成され得る。具体的には、処理エンジン112は、解像度2で複数の第2の点を取得するために、区画ΔHIJの各側に沿った複数の第1の点のそれぞれ2つの間の二等分点を判定し得る。解像度2では、3つの頂点H、I、およびJが第2の点と見なされ得る。本開示では、「第2の点」および「第2のレベルの等分点」という用語は、交換可能に使用される。複数の第2のグリッドは、第2の点に基づいて形成され得る。第2のグリッドは、解像度2のグリッドと見なされ得る。解像度2のグリッドの細分化レベルは2であり得る。図7Eに示されるように、第3の細分化操作において、1対4の細分化が実行され得、各第2のグリッドについて菱形の形状を有する4個の第1のグリッドが生成され得る。具体的には、処理エンジン112は、解像度3で複数の第3の点を取得するために、区画ΔHIJの各側に沿った複数の第2の点のそれぞれ2つの間の二等分点を判定し得る。解像度3では、3つの頂点H、I、およびJが第3の点と見なされ得る。本開示では、「第3の点」および「第3のレベルの等分点」という用語は、交換可能に使用される。複数の第3のグリッドは、第3の点に基づいて形成され得る。第3のグリッドは、解像度3のグリッドと見なされ得る。解像度3のグリッドの細分化レベルは3であり得る。同様に、さらなる細分化操作（例えば、1対4の細分化）が複数のグリッドをさらに細分化するために実行され得る。より低い解像度（複数可）の各グリッドは、比較的高い解像度で表され得る。例えば、図7Eに示されるように、解像度1のグリッドおよび解像度2のグリッドは、解像度3のグリッドによって表され得る。
【０１３１】
複数のグリッドの形状は、多面体の区画の形状、1つもしくは複数の細分化係数、および／または細分化レベルに基づいて判定され得ることに留意されたい。八面体を例にとると、グリッドの形状は菱形に加えて三角形または六角形であり得る。同じ細分化操作が、異なる細分化係数で異なる形状のグリッドを生成し得る。例えば、図7Cに示されるように、菱形については細分化係数が4．5であるが、六角形については9／7であり、六角形は形成されない。破線で示される準六角形は、頂点a、b、c、d、e、およびfによって定義され、中心点hを持つ。別の例として、図7Dに示されるように、細分化係数は、菱形については4であるが、六角形については3．5である。さらなる例として、図7Eに示されるように、細分化係数は、菱形については4であるが、六角形については3．5である。六角形は、図7Dおよび図7Eでは破線で示されている。いくつかの実施形態では、複数のグリッドの形状は、手動で設定され得る、または異なる状況に応じて人工知能システム100の1つまたは複数の構成要素によって判定され得る。
【０１３２】
いくつかの実施形態では、グリッドの形状に関係なく、図7Cから図7Eに示すように、細分化操作によって生成される多面体の区画上の点（例えば、第1の点、第2の点、第3の点）の数は、次のように判定され得る。
Ve（Tn）＝3＊2n−1＋1、（14）
Me（Tn）＝Ve（Tn）−1＝3＊2n−1、（15）
V（Tn）＝9＊2n−2（2n−1＋1）＋1、（16）
E（Tn）＝9＊2n−2（3＊2n−1＋1）、（17）
F（Tn）＝9＊4n−1、（18）
Ve（Tn）は、八面体の区画の1つの側にある点の数を指し、nは、細分化レベルを指し、Me（Tn）は、八面体の区画の1つの側にある等しいセグメントの数を指し、V（Tn）は、八面体の1つの区画上のすべての点の数を指し、E（Tn）は、八面体の区画上の2つの隣接する点の間のセグメントの数を指し、F（Tn）は、八面体の区画上の最も細かい三角形の数を指し得る。図7Cに示されるように、4つの点H、g、j、およびIは、八面体の1つの側（例えば、側「HI」）にあり得る。10の点H、g、j、I、k、m、J、n、i、およびhは、八面体の1つの区画（例えば、区画「HIJ」）上にあり得る。
【０１３３】
地図における区画は、グリッドの頂点とグリッド内の点とを含む複数の点を有し得る。複数の点のそれぞれは、地図における区画上に対応する投影座標を有し得る。区画上の点の投影座標は、区画上の投影座標系の原点および図7Fおよび図7Gに示すような1つまたは複数の基底ベクトルに基づいて判定され得る。図7Fおよび図7Gは、本開示のいくつかの実施形態による、八面体の区画上の例示的な投影座標系を示す概略図である。いくつかの実施形態では、八面体の区画上の点の投影座標は、区画の頂点の投影座標および細分化レベルに基づいて判定され得る。単なる例として、図7Fに示されるように、区画「KLM」は、八面体の区画の1つであり得る。区画「KLM」の1つの側の点の数は、式（14）に従って判定され得る。
【０１３４】
いくつかの実施形態では、頂点（例えば、頂点K）は、投影座標系の原点と見なされ得る。次に、2つの基底ベクトル（例えば、第1の基底ベクトル
【数２２】
2021508856.tif 000024
および第2の基底ベクトル
【数２３】
2021508856.tif 000025
）は、ベクトル
【数２４】
2021508856.tif 000026
、ベクトル
【数２５】
2021508856.tif 000027
、および／または区画「KLM」の1つの側の点の数Veに基づいて判定され得る。第1の基底ベクトルは、原点Kと、
【数２６】
2021508856.tif 000028
方向に沿って隣接する第nのレベルの等分点とによって形成されるベクトルを指し得る。第2の基底ベクトルは、原点Kと、
【数２７】
2021508856.tif 000029
方向に沿って隣接する第nのレベルの等分点によって形成されるベクトルを指し得る。基底ベクトルは、式（19）に基づいて判定され得る。
【数２８】
2021508856.tif 000030
【０１３５】
区画「KLM」上の点の投影座標は、2つの基底ベクトルに基づいて判定され得る。例えば、区画「KLM」上の任意の点（例えば、点X）は、ベクトル
【数２９】
2021508856.tif 000031
により表され、ベクトル
【数３０】
2021508856.tif 000032
は、
【数３１】
2021508856.tif 000033
として表され、よって、区画「KLM」上の点Xの投影座標は（i，j）として表され、iは0，1，．．．，またはVe−1に等しい整数であり、jは0，1，．．．，またはVe−1に等しい整数であり、i＋jはVe−1以下であり得る。
【０１３６】
異なる細分化レベルでの菱形のグリッドにおける点の投影座標は相互変換可能であり得ることに留意されたい。例えば、式（20）に示されるように、細分化レベルnにおける第1の菱形のグリッドの投影座標は、細分化レベルq（q＞n）における第2の菱形のグリッドの投影座標に基づいて判定され得る。
【数３２】
2021508856.tif 000034
（ii，jj）は、投影座標系における細分化レベルnでの第1の菱形のグリッドの投影座標を指し、（i，j）は、投影座標系における細分化レベルqでの第2の菱形のグリッドの投影座標を指し得る。
【０１３７】
いくつかの実施形態では、投影点P’は、細分化操作によって生成された点に属さない場合があり、よって、投影点P’に対応する（細分化操作によって生成された）ターゲット点が判定され得る。いくつかの実施形態では、区画ΔACD上の投影点P’の投影座標は、第1の投影座標と呼ばれ得る。
【０１３８】
単なる例として、図7Iは、本開示のいくつかの実施形態による六角形のグリッドのターゲット中心点を示す概略図である。図7Iに示されるように、区画ΔACD上に複数のレベル2の六角形のセルがある。点R1、R2、R3、R4、R5、R6、およびR7は、六角形のグリッドの中心点である。処理エンジン112は、投影点P’に最も近い中心点をターゲット中心点として判定し得る。いくつかの実施形態では、処理エンジン112は、投影点P’の投影座標と区画ΔACD上の中心点とに基づいて投影点P’と六角形のグリッドの中心点（例えば、点R1、R2、R3、R4、R5、R6、およびR7）との間の距離を判定し得る。処理エンジン112は、点P’といくつかの周囲の中心点との間の距離に基づいて、投影点P’に最も近い中心点を判定し得る。図7Iに示されるように、点R7はターゲット中心点であり得る。処理エンジン112は、区画ΔACD上のターゲット中心点の投影座標を第2の投影座標として指定し得る。
【０１３９】
いくつかの実施形態では、六角形のグリッドは、八面体の2つ以上の区画を横切る場合がある。八面体の2つ以上の区画を横切る六角形のグリッドは、クロスオーバーグリッドと呼ばれ得る。例えば、図7Kに示されるように、4つの1／6六角形のグリッドAK1K2、AK2K3、AK3K4、およびAK4K1は、同じ六角形のグリッドに属し得る。したがって、ターゲット中心点は、対応する区画の頂点に配置され得る。別の例として、図7Kに示されるように、2つの隣接する面の境界が六角形のグリッドを半分に分割し得る、つまり、2つの異なる区画上の2つの1／2六角形グリッドが同じ六角形グリッドに属し得る。したがって、ターゲット中心点は、対応する区画の側に配置され得る。したがって、クロスオーバーグリッドのターゲット中心点がどの区画に属するかを判定することが望ましい場合がある。
【０１４０】
図7Kは、本開示のいくつかの実施形態による、クロスオーバーグリッドのターゲット中心点の帰属を示す概略図である。説明のために、八面体の8つの区画は、平面に展開され得る。8つの区画のインデックスは、0、1、2、3、4、5、6、および7であり得る。八面体の6つの頂点は、点A、B、C、D、E、およびFであり得る。いくつかの実施形態では、処理エンジン112は、1つまたは複数のルールに基づいて、クロスオーバーグリッドのターゲット中心点の帰属を判定し得る。1つまたは複数のルールは、処理エンジン112によって判定されるデフォルト値とすることができる、または端末（例えば、乗客の端末130、運転者の端末140など）を介してユーザによって設定または調整され得る。
【０１４１】
いくつかの実施形態では、対応する区画上のクロスオーバーグリッドのターゲット中心点の投影座標は、（0，0）であり得る。したがって、処理エンジン112は、式（21）に基づいてターゲット中心点の帰属を判定することができる。
【数３３】
2021508856.tif 000035
fはターゲット中心点の対応する区画の初期インデックスを指し、f’は、ターゲット中心点の対応する区画のルールドインデックスを指し得る。
【０１４２】
例えば、投影点P’が面「2」に配置されると仮定すると、ターゲット中心点は点Aであり、ターゲット中心点の対応する区画の初期インデックスは「2」であり得る。初期インデックスが4未満であるため、対応する区画のルールドインデックスは0と判定され得る。
【０１４３】
いくつかの実施形態では、クロスオーバーグリッドのターゲット中心点の投影座標は、2つの隣接する区画の境界上にあり、2つの隣接する区画は、境界の北側および南側にそれぞれ配置されている。すなわち、ターゲット中心点（i，j）の投影座標は、i＋j＝Nの関係を有し、Nは、境界上の等しいセグメントの数を指し、したがって、特定の実施形態では、処理エンジン112は、式（22）に基づいて、ターゲット中心点の帰属を判定し得る。
【数３４】
2021508856.tif 000036
【０１４４】
つまり、処理エンジン112は、ターゲット中心点が境界の北側に配置される区画に属すると判定することができる。例えば、ターゲット中心点は、BC、CD、DE、またはEBの側に配置されてもよく、処理エンジン112は、ターゲット中心点を区画「3」、「0」、「1」、または「2」にそれぞれ属すると指定し得る。
【０１４５】
いくつかの実施形態では、クロスオーバーグリッドのターゲット中心点の投影座標は、2つの隣接する区画の境界上にあり、2つの隣接する区画は、境界の東側および側にそれぞれ配置されている。すなわち、ターゲット中心点のI座標またはJ座標は0であり得、したがって、特定の実施形態では、処理エンジン112は、ターゲット中心点が境界の東側に配置される区画に属すると判定し得る。例えば、ターゲット中心点は、AB、AC、AD、またはAEの側に配置されてもよく、処理エンジン112は、ターゲット中心点を区画「3」、「0」、「1」、または「2」にそれぞれ属すると指定し得る。
【０１４６】
別の例として、図7Jは、本開示のいくつかの実施形態による、菱形のグリッドのターゲット共通点を示す概略図である。区画は、複数の菱形のグリッドを有し得、3つ以上の隣接するグリッドが共通の点を有し得る。菱形のグリッドの各頂点は、2つ以上の他の菱形のグリッドの頂点でもあり得、したがって、菱形のグリッドの各頂点は、共通点であり得る。
【０１４７】
図7Jに示されるように、例としてグリッド「STUV」を取り上げると、グリッド「STUV」は、4つの共通点S、T、U、およびVを有し得る。菱形のグリッドの各辺は、1単位の長さを有し得る。点Sの投影座標が（i，j）である仮定とすると、点T、V、およびUの投影座標は、それぞれ、（i＋1，j）、（i，j＋1）、および（i＋1，j＋1）であり得る。グリッド「STUV」内の各点は、（i，i＋1）の範囲内のI座標を持つことができる。グリッド「STUV」内の各点は、（j，j＋1）の範囲内のJ座標を持つことができる。いくつかの実施形態では、処理エンジン112は、第1の投影座標の整数座標を有する共通点をターゲット共通点として判定し得る。例えば、点P’の第1の投影座標は、（i＋x，j＋y）であり得、ここで、xおよび／またはyは、1未満、かつ0よりも大きいものであり得る。これに対応して、第1の投影座標の整数座標は、（i，j）であり得、すなわち、点Sは、ターゲット共通点として判定され得る。処理エンジン112は、区画上のターゲット共通点の投影座標を第2の投影座標として指定し得る。
【０１４８】
いくつかの実施形態では、処理エンジン112は、細分化レベル、DGGSに関連する多面体の形状、座標対が含まれる対応する区画のインデックス、および第2の投影座標に基づいて、座標対に対応するグリッドインデックスを判定し得る。
【０１４９】
いくつかの実施形態では、グリッドインデックスは、地図における区画上のグリッドを一意に識別し得る。1つまたは複数の座標対を含む領域は、多面体の区画上の少なくとも1つのグリッドにインデックス付けされ得る。例えば、1つまたは複数の座標対は、同じグリッドに配置され、同じグリッドインデックスによってインデックス付けされ得る。別の例として、1つまたは複数の座標対は、異なるグリッドに配置され、異なるグリッドインデックスによってインデックス付けされ得る。いくつかの実施形態では、グリッドインデックスは、上記の細分化レベル、多面体の形状、対応する区画のインデックス、および／または第2の投影座標に関連する情報を含み得る。
【０１５０】
グリッドインデックスは、1つまたは複数の数字、1つまたは複数の文字、1つまたは複数の記号などの組み合わせとして表され得る。単なる例として、処理エンジン112は、文字列「OL［］F［］i［］j［］」の形でグリッドインデックスを判定することができ、「O」は、多面体が八面体であることを指し、「L」は細分化レベルを指し、「F」は座標対が含まれる八面体の対応する区画のインデックスを指し、「i」および「j」は第2の投影座標を指し、「［］」は、文字列の現在の位置に1つまたは複数の数値を入力できることを指し得る。例えば、細分化レベルが13であり、対応する区画のインデックスが1であり、第2の投影座標が（12．34，56．78）の場合、グリッドインデックスは「OL13F1i1234j5678」になり得る。
【０１５１】
プロセス700の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することは意図されていないことに留意されたい。当業者であれば、本開示の教示の下で複数の変更および修正を行い得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱するものではない。いくつかの実施形態では、変換操作を容易にするために、座標対は、参照区画に対応する対応する座標対に変換され得る。任意の区画が参照区画として指定され得る。例えば、「0」としてインデックス付けされた区画が、参照区画として指定され得る。座標対が参照区画上にない場合、処理エンジン112は、座標対を参照区画「0」に変換することができる。図7Kに示されるように、「4」でインデックス付けされた区画は、逆三角形として表され得、変換後、「4」でインデックス付けされた区画は、参照区画「0」にマッピングされ得る。したがって、点Fは、投影座標系の（投影座標（0，0）の）原点と見なされ、ベクトルFDは、投影座標系のI軸に対応し、ベクトルFCは、投影座標系のJ軸に対応し得る。
【０１５２】
図8は、本開示のいくつかの実施形態による、初期境界グリッド系列に基づいてジオフェンスの（最終的な）境界グリッド系列を判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス800は、図1に示される人工知能システム100において実施され得る。例えば、プロセス800は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス800は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図8に示され、以下で説明されるプロセス800の動作の順序は、限定するものであることは意図されていない。いくつかの実施形態では、プロセス500のステップ520は、プロセス800に従って実行され得る。
【０１５３】
810において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の識別ユニット421）は、複数の境界点に対応する境界グリッド系列（例えば、612で判定された初期境界グリッド系列、653で判定された初期境界グリッド系列）を識別し得る。
【０１５４】
820において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の選択ユニット422）は、複数の境界点から2つの隣接する境界点を選択し得る。例示の目的で、2つの隣接する境界点は、本明細書では点対と呼ばれ得る。N個の境界点に対応する境界グリッド系列の場合、N個の境界点の各2つの隣接する境界点は、点対と呼ばれ得る。処理エンジン112は、N個の境界点についてN個の点対を判定し得る。境界グリッド系列の最初のグリッドに対応する境界点と、境界グリッド系列の最後のグリッドに対応する境界点も、隣接していると見なされ、2つの隣接する境界点または点対と呼ばれ得ることに留意されたい。いくつかの実施形態では、複数の境界点は、1つまたは複数の点を補間または除去することによって更新され得る。
【０１５５】
830において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の判定ユニット423）は、2つの隣接する境界点が同じグリッドに対応するか否かを判定し得る。例えば、処理エンジン112は、2つの隣接する境界点に対応するグリッドインデックスが互いに同じであるか否かを判定し得る。2つの隣接する境界点に対応するグリッドインデックスが互いに同じである場合、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の判定ユニット423）は、2つの隣接する境界点同じグリッド、例えば図12Aの点CおよびDがに対応すると判定し得る。2つの隣接する境界点に対応するグリッドインデックスが異なる場合、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の判定ユニット423）は、2つの隣接する境界点が2つの異なるグリッドに対応すると判定し得る。
【０１５６】
2つの隣接する境界点が同じグリッドに対応するという判定に応じて、これは、境界グリッド系列が重複グリッドを含み、重複グリッドが境界グリッド系列において隣接していることを示し得るため、プロセス800は840に進み得る。840において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の除去ユニット424）は、2つの隣接する境界点のうちの1つを除去し得る。除去される境界点は、2つの隣接する境界点のうちの任意の1つであり得る。次に、880において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の更新ユニット426）は、除去された境界点に対応するグリッドを除去することにより、境界グリッド系列を更新し得る。
【０１５７】
2つの隣接する境界点が2つの異なるグリッドに対応するという判定に応じて、プロセス800は850に進むことができる。850において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の補間ユニット425）は、2つの隣接する境界点の間の点を選択し得る。選択された点は、2つの隣接する境界点の間の任意の点、例えば、2つの隣接する境界点の中点、2つの隣接する境界点のうちの1つ付近の点、または2つの隣接する境界点の間の他の任意の点であり得る。本開示は、例として、選択された点が2つの隣接する境界点の中点であると見なすが、これは限定するものではない。いくつかの実施形態では、処理エンジン112（例えば、補間ユニット425）は、境界グリッド系列を更新するために、境界グリッド系列の選択された点に対応するグリッドを直接補間し得る。いくつかの実施形態では、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の補間ユニット425）は、補間条件が満たされているか否かをさらに判定し得る。補間条件は、選択された点に対応するグリッドが、2つの隣接する境界グリッドに対応するグリッドのいずれとも異なることであり得る。
【０１５８】
補間条件が満たされた場合、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の補間ユニット425）は、870において、2つの隣接する境界点の間にある選択された点を補間し得る。補間された点は、ジオフェンスの境界点として指定され得る。次に、880において、処理エンジン112（例えば、ジオフェンス境界判定モジュール420の更新ユニット426）は、2つの隣接する境界点に対応する2つのグリッド間の補間された境界点に対応するグリッドを補間することにより、境界グリッド系列を更新し得る。
【０１５９】
補間条件が満たされない場合、処理エンジン112は、選択された点を補間しない。いくつかの実施形態では、境界グリッド系列に関連するすべての点対について、処理エンジン112は、2つの隣接する境界点の間の1つまたは複数の点を補間し得る、または2つの隣接する境界点の点を並行して除去し得る。いくつかの実施形態では、境界グリッド系列に関連するすべての点対について、処理エンジン112は、2つの隣接する境界点の間の1つまたは複数の点を補間し得る、または2つの隣接する境界点の点を順に除去し得る。例えば、処理エンジン112は、820において複数の境界点から2つの隣接する境界点を順次取得し、ステップ320から870を実行し、次にプロセス800はステップ820に戻って別の2つの隣接する境界点を取得する。したがって、ジオフェンスによって占有されているすべてのグリッドを取得するために、処理エンジン112は、上記の動作（例えば、ステップ820からステップ880に説明されている動作）の実行を繰り返すことができる。各点対について、補間条件が満たされていると判定すると、処理エンジン112は、（初期境界グリッド系列に対応する境界点と補間された境界グリッドとを含む）2つの隣接する境界グリッド点間の補間が2つの隣接する境界点の1つとして同じグリッドに対応する点を生成するまで、点を再帰的に補間し得る。次に、処理エンジン112は、除去された境界点および／または補間された境界点に基づいて、ジオフェンスの最終的な境界グリッド系列を判定し得る。
【０１６０】
図9Aは、本開示のいくつかの実施形態による、地理的領域に関連付けられた1つまたは複数の囲繞エリアを判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス900は、図1に示される人工知能システム100において実施され得る。例えば、プロセス900は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス900は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図9Aに示され、以下で説明されるプロセス900の動作の順序は、限定するものであることは意図されていない。いくつかの実施形態では、プロセス500のステップ530は、プロセス900に従って実行され得る。
【０１６１】
910において、処理エンジン112（例えば、囲繞エリア判定モジュール430のグリッド取得ユニット431）は、地理的領域に関連する境界グリッド系列を取得し得る。いくつかの実施形態では、境界グリッド系列は、図5のステップ520で判定された境界グリッド系列であり得る。境界グリッド系列は、ジオフェンスが通過するすべてのグリッドを含み得る。境界グリッド系列のグリッドは、ジオフェンスによって通過される順序で配置され得る。
【０１６２】
920において、処理エンジン112（例えば、囲繞エリア判定モジュール430のピボットグリッド判定ユニット432）は、境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定し得る。上記のように、ピボットグリッドは、ジオフェンスが2回以上通過するグリッドを指し得、ピボットグリッドは境界グリッド系列に2回以上現れ得る。したがって、処理エンジン112は、探索技法を使用して、境界グリッド系列が2つ以上の同じグリッドを含むか否かを判定し得る。例えば、処理エンジン112は、グリッドの相対位置に基づいて境界グリッド系列のグリッドについてリンクリストまたは補助地図を作成することができ、次に処理エンジン112は、リンクリストまたは補助地図を探索することを通して、境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定することができる。いくつかの実施形態では、ピボットグリッドの判定は、図9に記載されている1つまたは複数の動作を実行することによって取得され得る。
【０１６３】
境界グリッド系列がピボットグリッドを含まないという判定に応じて、プロセス900は930に進むことができる。930において、処理エンジン112（例えば、囲繞エリア判定モジュール430の囲繞エリア判定ユニット433）は、地理的領域を囲繞エリアとして指定し得る。
【０１６４】
境界グリッド系列が1つまたは複数のピボットグリッドを含むという判定に応じて、プロセス900は940に進むことができる。940において、処理エンジン112（例えば、囲繞エリア判定モジュール430の囲繞エリア判定ユニット433）は、1つまたは複数のピボットグリッドに基づいて1つまたは複数の囲繞エリアを判定し得る。例えば、1つまたは複数のピボットグリッドのそれぞれについて、処理エンジン112は、ピボットグリッドの一方の側にある地理的領域におけるエリアを、第1の囲繞エリアとして、またピボットグリッドの他方の側にある地理的領域におけるエリアを、第2の囲繞エリアとして識別し得る。いくつかの実施形態では、ピボットグリッドに関連付けられた囲繞エリアの数Nは、境界グリッド系列に現れるピボットグリッドの回数Mに基づいて判定され得る。1つの実施形態では、特定のピボットグリッドが境界グリッド系列でM回（例えば、2、3、4．．．）現れる場合、特定のピボットグリッドに関連付けられたN＝M個の囲繞エリアがあり得る。別の実施形態では、特定のピボットグリッドが境界グリッド系列でM回（例えば、3、4．．．）現れる場合、特定のピボットグリッドに関連付けられたN個（NはMより小さく、例えばN＝M−1）の囲繞エリアがあり得る。
【０１６５】
図9Bは、本開示のいくつかの実施形態による、スタック操作を使用して地理的領域に関連付けられた1つまたは複数の囲繞エリアを判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス950は、図1に示される人工知能システム100において実施され得る。例えば、プロセス950は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス950は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図9Bに示され、以下で説明されるプロセス950の動作の順序は、限定するものであることは意図されていない。いくつかの実施形態では、プロセス500およびプロセス900のステップ530は、プロセス950に従って実行され得る。
【０１６６】
951において、処理エンジン112（例えば、囲繞エリア判定モジュール430）は、空のスタックおよび空の補助地図を生成し得る。いくつかの実施形態では、処理エンジン112は、地理的領域のジオフェンスに関連する情報（例えば、本開示で説明される境界点、グリッド、グリッドインデックス）を記憶または処理するために、空のスタックおよび空の補助地図を生成し得る。補助地図は、キー部分と値部分とを含む2つの部分を含み得る。キーおよび対応する値は、＜キー，値＞として表されるキーと値との対と呼ばれ得る。補助地図のキーは一意であり得、各キーは1つの値にのみ関連付けされ得る。いくつかの実施形態では、境界グリッド系列におけるグリッドは、連続的に番号を付けされ得る。各グリッドは、一意のシーケンス番号に対応し得る。例えば、境界グリッド系列のグリッド（または対応するグリッドインデックス）の総数がnの場合、グリッドのシーケンス番号は、それに応じて「1」、「2」、「3」、．．．、「n」とマークされ得る。シーケンス番号が補助地図の1つの部分に入力され得、グリッドの対応するグリッドインデックスが補助地図の他の部分に入力され得る。いくつかの実施形態では、補助地図のキーと値との対は、＜シーケンス番号，グリッドインデックス＞として表され得る、すなわち、シーケンス番号はキーであり、グリッドインデックスはキーに関連する値である。あるいは、補助地図のキーと値との対は、＜グリッドインデックス，シーケンス番号＞として表され得る、すなわち、グリッドインデックスはキーであり、シーケンス番号はキーに関連する値である。952において、処理エンジン112（例えば、囲繞エリア判定モジュール430のグリッド取得ユニット431）は、境界グリッド系列（例えば、地理的領域のジオフェンスに関連する最終的な境界グリッド系列）からグリッドを取得し得る。いくつかの実施形態では、処理エンジン112は、例えば、ジオフェンス境界判定モジュール420またはストレージデバイス（例えば、ストレージデバイス150）から、境界グリッド系列におけるグリッドを順次取得し得る。処理エンジン112は、シーケンス番号1に対応するグリッドをまず取得し、次にシーケンス番号2に対応するグリッドを取得し、次にシーケンス番号3に対応するグリッドを取得し、．．．、最後にシーケンス番号nに対応するグリッドを取得し得る。
【０１６７】
953において、処理エンジン112（例えば、囲繞エリア判定モジュール430のピボットグリッド判定ユニット432）は、補助地図を探索することにより、グリッドに対応するグリッドインデックスが補助地図にあるか否かを判定し得る。
【０１６８】
グリッドに対応するグリッドインデックスが補助地図にないという判定に応じて、プロセス950は954に進むことができる。954において、処理エンジン112（例えば、囲繞エリア判定モジュール430）は、グリッドインデックスをスタックにプッシュすることができる。いくつかの実施形態では、処理エンジン112は、グリッドインデックスをスタックに、また対応するシーケンス番号をスタックまたは別のスタックに、同時にプッシュすることができる。処理エンジン112は、954において、グリッドインデックスを補助地図に入力し得る。具体的には、処理エンジン112は、グリッドインデックスを補助地図の1つの部分（例えば、値部分）に入力し、対応するシーケンス番号を補助地図の他の部分（例えば、キー部分）に入力することができる。グリッドをスタックにプッシュすること、およびグリッドを地図に入力することは、同じステップで実行されてもよいし異なるステップで実行されてもよいことに留意されたい。ステップ954の後、プロセス950は、次のシーケンス番号に対応するグリッドを取得するために952に進むことができる。
【０１６９】
グリッドに対応するグリッドインデックスが補助地図にあるという判定に応じて、プロセス950は955に進むことができる。955において、処理エンジン112（例えば、囲繞エリア判定モジュール430のピボットグリッド判定ユニット432）は、グリッドをピボットグリッドとして指定し得る。処理エンジン112はまた、ピボットグリッドに対応するグリッドインデックスをピボットグリッドインデックスとして指定し得る。
【０１７０】
956において、処理エンジン112（例えば、囲繞エリア判定モジュール430の囲繞エリア判定ユニット433）は、スタックの一番上にあるグリッドインデックスがピボットグリッドインデックスと同じになるまで、スタックからスタックのグリッドインデックスをポップし得る。いくつかの実施形態では、処理エンジン112はまた、スタックの一番上からピボットグリッドインデックスと同じグリッドインデックスをポップすることもできる。次に、957において、処理エンジン112（例えば、囲繞エリア判定モジュール430の囲繞エリア判定ユニット433）は、ポップされたグリッドインデックスに対応するグリッドを、ピボットグリッド（またはピボットグリッドインデックス）に関連する囲繞エリアの境界グリッドとして指定し得る。いくつかの実施形態では、954でグリッドおよび対応するシーケンス番号がスタックにプッシュされると、956において、処理エンジン112は、スタックインデックスの一番上からグリッドインデックスおよび対応するシーケンス番号を同時にポップすることができる。
【０１７１】
プロセス950の上記の説明は、例示の目的で提供されており、本開示の範囲を限定することは意図されていないことに留意されたい。当業者であれば、本開示の教示の下で複数の変更および修正を行い得る。しかしながら、それらの変形および修正は、本開示の範囲から逸脱するものではない。いくつかの実施形態では、グリッドインデックスおよび対応するシーケンス番号は、2つのスタックにプッシュされ得る。例えば、951において、処理エンジン112は2つの空のスタックを生成し得る。954において、グリッドインデックスおよび対応するシーケンス番号がそれぞれ2つのスタックにプッシュされ得る。956において、処理エンジン112は、2つのスタックからそれぞれグリッドインデックスおよび対応するシーケンス番号をポップし得る。いくつかの実施形態では、956において、処理エンジン112は、スタックからピボットグリッドインデックスと同じグリッドインデックスをポップしない。
【０１７２】
いくつかの実施形態では、第1の囲繞エリアが判定された後、プロセス950は952に進むことができる。952において、処理エンジン112は、境界グリッド系列からグリッドを取得し続けることができる。ステップ953からステップ957を実行することにより、処理エンジン112は、次の囲繞エリアを判定することができる。いくつかの実施形態では、1つまたは複数の囲繞エリアを判定するために、ステップ952からステップ957が繰り返されてもよい。ステップ952からステップ957を実行することを繰り返すことにより、境界グリッド系列におけるすべてのグリッドのグリッドインデックスが処理され得る（例えば、スタックにプッシュされる、またはスタックからポップされる）。いくつかの実施形態では、スタックにプッシュする最初のグリッドがピボットグリッドではない場合、処理エンジン112がすべてのピボットグリッドを判定した後、スタックにいくつかのグリッド（またはグリッドインデックス）が残っている場合があり、処理エンジン112は、スタックに残っているグリッドインデックスに対応するグリッドを別の囲繞エリアの境界グリッドとして指定し得る。プロセス950のすべての動作が実行されると、処理エンジン112は、地理的領域のすべての囲繞エリアを識別し得る（例えば、囲繞エリアのそれぞれの境界グリッドを識別し得る）。
【０１７３】
図10は、本開示のいくつかの実施形態による、2つ以上のサブエリアの境界グリッドを判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス1000は、図1に示される人工知能システム100において実施され得る。例えば、プロセス1000は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス1000は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図10に示され、以下で説明されるプロセス1000の動作の順序は、限定するものであることは意図されていない。いくつかの実施形態では、プロセス500のステップ550は、プロセス1000に従って実行され得る。
【０１７４】
1010において、処理エンジン112（例えば、サブエリア判定モジュール440の重複辺グリッド判定ユニット441）は、サブエリアが複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定し得る。いくつかの実施形態では、区画の「辺」、「境界」、および「側」という用語は、交換可能に使用され得る。いくつかの実施形態では、囲繞エリアが2つ以上の区画を横切る場合、処理エンジン112（例えば、サブエリア判定モジュール440）は、（プロセス500の540で説明される動作に関連して）囲繞エリアを2つ以上のサブエリアにセグメント化し得る。いくつかの実施形態では、サブエリアについては、サブエリアは、地図の区画の1つまたは複数の辺と交差し得る。処理エンジン112は、1つまたは複数の辺上のサブエリアの境界グリッドに基づいて、1つまたは複数の重複辺グリッドを判定し得る。例えば、図11Bに示されるように、複数の例示的な長方形のグリッド1167を含む例示的な長方形の区画1166がある。区画および／またはグリッドは、他の形状および数を有し得ることに留意されたい。処理エンジン112（例えば、サブエリア判定モジュール440）は、囲繞エリア1161に関連するサブエリアの1つとして、サブエリア1162（斜めの点線を有するエリア）を判定し得る。いくつかの実施形態では、区画1166上のサブエリア1162の1つまたは複数の重複辺グリッドを判定するために、処理エンジン112（例えば、重複グリッド判定ユニット441）は、囲繞エリア1161の境界が区画1166と交差する点（例えば、点Aおよび点B）をまず判定し得る。次に、処理エンジン112（例えば、重複グリッド判定ユニット441）は、点Aがあるグリッドのグリッドインデックスおよび区画1166のインデックスに基づいて、辺EC上の点Aと点Cとの間のグリッドを第1の重複辺グリッドとして判定し得る。処理エンジン112（例えば、重複グリッド判定ユニット441）は、点Bがあるグリッドのグリッドインデックスおよび区画1166のインデックスに基づいて、辺FC上の点Bと点Cとの間のグリッドを第2の重複辺グリッドとして判定し得る。点Aおよび点Bは囲繞エリア1162の境界上にあり、したがって、点Aがあるグリッドおよび点Bがあるグリッドは、サブエリア1162の重複グリッドの代わりにサブエリア1162の境界グリッド（本明細書では初期境界グリッドとも呼ばれる）に属し得ることに留意されたい。
【０１７５】
1020において、処理エンジン112（例えば、サブエリア判定モジュール440の境界グリッド判定ユニット442）は、重複辺グリッドと、2つ以上のサブエリアに関連する囲繞エリアの境界グリッドとに基づいて、サブエリアの境界グリッドを判定し得る。いくつかの実施形態では、サブエリアについて、処理エンジン112は、サブエリアの境界グリッド（本明細書では最終的な境界グリッドとも呼ばれる）を判定するために、サブエリアの初期境界グリッドとサブエリアに関連する重複辺グリッドとを組み合わせ得る。540で判定された各サブエリアについて、処理エンジン112は、サブエリアの境界グリッドを判定するために図10に記載された動作を実行することができることに留意されたい。
【０１７６】
図11Aは、本開示のいくつかの実施形態による、サブエリアにおける内部グリッドを判定するための例示的なプロセスを示す流れ図である。いくつかの実施形態では、プロセス1100は、図1に示される人工知能システム100において実施され得る。例えば、プロセス1100は、命令の形式としてストレージデバイス150および／または他のストレージデバイス（例えば、ROM 230、RAM 240）に記憶され得、サーバ110（例えば、サーバ110の処理エンジン112、サーバ110の処理エンジン112のプロセッサ220、サーバ110の処理エンジン112の1つまたは複数のモジュール）によって呼び出され得る、および／または実行され得る。以下に提示され例示されるプロセスの動作は、例示のためのものとして意図されている。いくつかの実施形態では、プロセス1100は、説明されていない1つまたは複数の追加の動作を用いて、および／または論じられた1つまたは複数の動作なしで達成され得る。加えて、図11Aに示され、以下で説明されるプロセス1100の動作の順序は、限定するものであることは意図されていない。いくつかの実施形態では、プロセス500のステップ560は、プロセス1100に従って実行され得る。
【０１７７】
1110において、処理エンジン112（例えば、内部グリッド判定モジュール450の行列初期化ユニット451）は、スキャニング行列を初期化することができる。スキャニング行列は、複数のセルを含み得る。スキャニング行列の各セルは、第1の値を有し得る。スキャニング行列に入力される値は、任意の形式、例えば、数字、文字とすることができる。例示の目的で、本開示の他の場所で説明されるスキャニング行列に入力される値は、数値形式、例えば0、1、2、3であり得る。いくつかの実施形態では、第1の値はゼロであり得る。いくつかの実施形態では、処理エンジン112（例えば、内部グリッド判定モジュール450）は、サブエリアの境界グリッドのスパンに基づいてスキャニング行列のサイズを判定することができる。
【０１７８】
単なる例として、図11Bに示されるように、OEおよびOFは、長方形の区画OECFのI軸およびJ軸として指定され得る。（例えば、円形の形状の）囲繞エリア1161は、2つ以上の区画を横切る。サブエリア1162は、長方形の区画OECFのI軸方向に3つのグリッドを横切り、長方形の区画OECFのJ軸方向に6つのグリッドを横切る。処理エンジン112は、サブエリア1162のスパンがI軸方向に3であり、J軸方向に6であると判定することができる。次に、処理エンジン112（例えば、内部グリッド判定モジュール450）は、3×6のサイズを有するスキャニング行列を判定することができる。処理エンジン112（例えば、内部グリッド判定モジュール450の行列初期化ユニット451）は、スキャニング行列の各セルに第1の値（例えば、ゼロ）を入力することによってスキャニング行列を初期化することができる。単なる例として、初期化されたスキャニング行列Zは、式（23）として表され得る。
【数３５】
2021508856.tif 000037
【０１７９】
1120において、処理エンジン112（例えば、内部グリッド判定モジュール450の行列更新ユニット452）は、スキャニング行列の第1の複数のセルのそれぞれに第2の値を入力することによって、スキャニング行列に対して第1の更新を実行し得る。第1の複数のセルは、サブエリアの境界グリッドに対応し得る。第2の値は、第1の値とは異なる任意の値（または数）とすることができる。例えば、第2の値は1であり得る。
【０１８０】
例示の目的で、第1の更新後のスキャニング行列は、本明細書では第1の更新されたスキャニング行列と呼ばれ得る。単なる例として、第1の値が0であり、第2の値が1である場合、第1の更新されたスキャニング行列Z’は、式（24）として表され得る。
【数３６】
2021508856.tif 000038
【０１８１】
ステップ1120の後、一部のセルは第1の値を有することができ、一部のセル（例えば、第1の複数のセル）は第2の値を有することができる。次に、1130において、処理エンジン112（例えば、内部グリッド判定モジュール450）は、第1の値を有するセルについて、そのセルに対応するグリッドが地理的領域にあるか否かを光線法を使用して判定することができる。いくつかの実施形態では、スキャニング行列内のすべてのセルのそれぞれについて、処理エンジン112は、1130の光線法を使用して、セルに対応するグリッドが地理的領域にあるか否かを判定することができる。
【０１８２】
セルに対応するグリッドが地理的領域にあるという判定に応じて、プロセス1100は1140に進むことができる。1140において、処理エンジン112（例えば、内部グリッド判定モジュール450の行列更新ユニット452）は、スキャニング行列のセルに第3の値を入力することによって、スキャニング行列に対して第2の更新を実行し得る。第3の値は、第1の値以外の任意の値（または数）であり、第2の値と同じであっても異なっていてもよい。例えば、第3の値は2であり得る。いくつかの実施形態では、第1の値を有するセルに対応する1つまたは複数のグリッドが地理的領域にある場合、処理エンジン112は、第3の値を1つまたは複数の対応するセルに入力することによってスキャニング行列に対して第2の更新を実行することができる。
【０１８３】
例示の目的で、第2の更新後のスキャニング行列は、本明細書では第2の更新されたスキャニング行列と呼ばれ得る。単なる例として、第3の値が2である場合、第2の更新されたスキャニング行列Z’’は、式（25）として表され得る。
【数３７】
2021508856.tif 000039
【０１８４】
1150において、処理エンジン112（例えば、内部グリッド判定モジュール450の内部グリッド判定ユニット453）は、第3の値（例えば、2）を有するセルに対応するグリッドを、サブエリア1162における内部グリッドとして指定し得る。
【０１８５】
いくつかの実施形態では、処理エンジン120は、第1の複数のセルによって囲まれる1つまたは複数のセルを識別し、第1の複数のセルによって囲まれるセルに対応するグリッドをサブエリアの内部グリッドとして判定することができる。
【０１８６】
処理エンジン112は、第2（または第3）の値を有するセルを選択するためにスキャニング行列を横断し得る。処理エンジン112は、第2（または第3）の値を有するセルに対応するグリッドを、サブエリアに対応するターゲットグリッドとして指定することができる。処理エンジン112が地理的領域におけるサブエリアのそれぞれに対してプロセス1100の動作を実行するとき、処理エンジン112は、地理的領域におけるサブエリアのそれぞれに関連するすべてのターゲットグリッド（境界グリッドおよび内部グリッドを含む）を収集することによって、地理的領域のターゲットグリッド（境界グリッドおよび内部グリッドを含む）を判定することができる。
【０１８７】
基本概念を説明してきたが、当業者には、この詳細な開示を読んだ後には、上記の詳細な開示は、単なる例として提示されているに過ぎず、限定するものではないことは明らかであろう。本明細書には明示的に述べられていないが、様々な変更、改良、および修正が当業者には想起され、意図され得る。これらの変更、改良、および修正は、本開示によって示唆されることが意図されており、かつ本開示の例示的な実施形態の趣旨および範囲内にある。
【０１８８】
さらに、所定の用語が本開示の実施形態を説明するために使用されている。例えば、「1つの実施形態」、「一実施形態」、および／または「いくつかの実施形態」という用語は、実施形態に関連して説明される特定の特徴、構造、または特性が本開示の少なくとも1つの実施形態に含まれることを意味する。したがって、本明細書の様々な部分における「一実施形態」または「1つの実施形態」または「代替的な実施形態」への2つ以上の言及は、必ずしもすべてが同じ実施形態を指しているわけではないことを重要視し、理解されたい。さらに、特定の特徴、構造、または特性は、本開示の1つまたは複数の実施形態において適切に組み合わされてもよい。
【０１８９】
さらに、当業者には理解されるように、本開示の態様は、本明細書において、任意の新規かつ有用なプロセス、機械、製造、または組成物、またはそれらの任意の新規かつ有用な改善を含む、複数の特許性のある種類または文脈のいずれかで例示および説明され得る。したがって、本開示の態様は、完全にハードウェア、完全にソフトウェア（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、またはソフトウェアとハードウェアとの組み合わせによる実施により実施されてよく、実施はすべて、本明細書では「ユニット」、「モジュール」、または「システム」と総称され得る。さらに、本開示の態様は、具現化されたコンピュータ可読プログラムコードを有する1つまたは複数のコンピュータ可読媒体に具現化されたコンピュータプログラム製品の形態をとることができる。
【０１９０】
非一時的コンピュータ可読信号媒体は、例えば、ベースバンドにおいて、または搬送波の一部として具現化されたコンピュータ可読プログラムコードを有する伝播データ信号を含み得る。このような伝播信号は、電磁気、光など、またはそれらの任意の適切な組み合わせを含む様々な形態のいずれかをとることができる。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではないが、命令実行システム、装置、またはデバイスによって使用される、または組み合わせて使用されるためのプログラムを伝達、伝播、または伝送できる任意のコンピュータ可読媒体であり得る。コンピュータ可読信号媒体上に具現化されたプログラムコードは、無線、有線、光ファイバケーブル、RFなど、またはこれらの任意の適切な組み合わせを含む任意の適切な媒体を用いて送信され得る。
【０１９１】
本開示の態様の動作を実行するためのコンピュータプログラムコードは、Java、Scala、Smalltalk、Eiffel、JADE、Emerald、C＋＋、C＃、VB．NET、Pythonなどのオブジェクト指向プログラミング言語、「C」プログラミング言語、Visual Basic、Fortran 2003、Perl、COBOL 2002、PHP、ABAPなどの従来の手続き型プログラミング言語、Python、Ruby、Groovyなどの動的プログラミング言語、または他のプログラミング言語を含む、1つまたは複数のプログラミング言語の任意の組み合わせで書き込まれ得る。プログラムコードは、スタンドアロンのソフトウェアパッケージとして、ユーザのコンピュータ上で完全に実行されてもよいし、ユーザのコンピュータ上で部分的実行されてもよいし、ユーザのコンピュータ上で部分的にかつリモートコンピュータ上で部分的に実行されてもよいし、完全にリモートコンピュータもしくはサーバ上で実行されてもよい。後者のシナリオでは、リモートコンピュータは、ローカルエリアネットワーク（LAN）またはワイドエリアネットワーク（WAN）を含む任意のタイプのネットワークを介してユーザのコンピュータに接続されてよいし、接続は、外部コンピュータ（例えば、インターネットサービスプロバイダを用いてインターネットを介して）もしくはクラウドコンピューティング環境で行われてもよいし、サービスとしてのソフトウェア（SaaS）などのようなサービスとして提供されてもよい。
【０１９２】
さらに、処理要素もしくはシーケンス、またはそれに対する数、文字、もしくは他の名称の使用の、列挙された順序は、特許請求の範囲に指定され得るものを除き、特許請求の範囲に記載された処理および方法をいかなる順序にも限定することを意図するものではない。上記の開示は、本開示の様々な有用な実施形態であると現在考えられる様々な例を通して論じているが、そのような細部はその目的のためだけのものに過ぎず、添付の特許請求の範囲は、開示される実施形態に限定されず、むしろ、開示される実施形態の趣旨および範囲内にある修正および均等な構成を包含するように意図されていることを理解されたい。例えば、上記の様々な構成要素の実施は、ハードウェアデバイスで具現化され得るが、ソフトウェアのみの解決策として、例えば既存のサーバまたはモバイルデバイス上にインストールされたものとして実施されてもよい。
【０１９３】
同様に、本開示の実施形態の上記の説明では、様々な本発明の実施形態のうちの1つまたは複数の実施形態の理解を助ける開示を合理化する目的で、様々な特徴が単一の実施形態、図、またはその説明にまとめられていることを理解されたい。しかしながら、本開示の方法は、特許請求の範囲に記載された主題が各請求項に明確に記載されたものよりも多くの特徴を必要とするという意図を反映するものとして解釈されるべきではない。むしろ、本発明の実施形態は、上記の単一の開示された実施形態のすべての特徴よりも少ない。
【０１９４】
いくつかの実施形態では、本出願の特定の実施形態を記載して主張するために使用される量、特性などを表す数は、いくつかの場合では、用語「約」、「おおよそ」、または「実質的に」によって修飾されると理解されたい。例えば、「約」、「おおよそ」、または「実質的」は、別段の記載のない限り、それらが記載する値の±20％の変動を示し得る。したがって、いくつかの実施形態では、明細書または添付の特許請求の範囲に記載される数値パラメータは、特定の実施形態によって取得されようとする所望の特性に応じて変化し得る近似値である。いくつかの実施形態では、数値パラメータは、報告された有効数字の数に照らして、通常の丸めの技法を適用することによって解釈されるべきである。本出願のいくつか実施形態の広い範囲を記載している数値の範囲またはパラメータが近似値であるにもかかわらず、特定の例に記載される数値は、実行可能な程度に正確に報告されている。
【０１９５】
本明細書で参照された特許、特許出願、特許出願公開、および記事、本、仕様書、出版物、文書、および／または物などの他の資料のそれぞれは、関連した任意の起訴ファイル履歴、本明細書と矛盾もしくは競合するもの、または本明細書に現在または後に関連する特許請求の範囲の最も広い範囲に関して限定的な影響を及ぼし得るものを除いて、すべての目的のためにその全体がこの参照により本明細書に組み込まれる。例として、本明細書に組み込まれる任意の資料に関連した用語の説明、定義および／または使用と、本明細書に関連した用語の説明、定義、および／または使用との間に矛盾または競合が存在する場合、本明細書における用語の説明、定義、および／または使用が優先されるものとする。
【０１９６】
最後に、本明細書に開示された本出願の実施形態は、本出願の実施形態の原理を例示するものであることを理解されたい。採用され得る他の修正は、本出願の範囲内にあり得る。よって、限定するものではないが例として、本出願の実施形態の代替的な構成は、本明細書の教示に応じて利用され得る。したがって、本出願の実施形態は、示されて説明されたものに厳密に限定されない。
【符号の説明】
【０１９７】
100  人工知能システム
110  サーバ
112  処理エンジン
120  ネットワーク
120−1，120−2，．．．  ネットワークアクセスポイント
130  乗客の端末
130−1  モバイルデバイス
130−2  タブレットコンピュータ
130−3  ラップトップコンピュータ
130−4  自動車の組み込みデバイス
140  運転者の端末
140−1  モバイルデバイス
140−2  タブレットコンピュータ
140−3  ラップトップコンピュータ
140−4  自動車の組み込みデバイス
150  ストレージデバイス
200  コンピューティングデバイス
210  内部通信バス
220  中央プロセッサ
230  読み出し専用メモリ
240  ランダムアクセスメモリ
250  通信ポート
260  入出力コンポーネント
270  ディスク
300  デバイス
310  通信プラットフォーム
315  マイクロフォン
320  ディスプレイ
330  グラフィック処理ユニット
340  中央処理ユニット
350  入出力
360  メモリ
370  モバイルオペレーティングシステム
380  アプリケーション
390  ストレージデバイス
410  ジオフェンス情報取得モジュール
420  ジオフェンス境界判定モジュール
421  識別ユニット
422  選択ユニット
423  判定ユニット
424  除去ユニット
425  補間ユニット
426  更新ユニット
430  囲繞エリア判定モジュール
431  グリッド取得ユニット
432  ピボットグリッド判定ユニット
433  囲繞エリア判定ユニット
440  サブエリア判定モジュール
441  重複辺グリッド判定ユニット、重複グリッド判定ユニット
442  境界グリッド判定ユニット
450  内部グリッド判定モジュール
451  行列初期化ユニット
452  行列更新ユニット
453  内部グリッド判定ユニット
460  グリッドインデックス判定モジュール
461  座標取得ユニット
462  座標変換ユニット
463  グリッドインデックス判定ユニット
470  ターゲットグリッド判定モジュール
500  プロセス
610  プロセス
650  プロセス
700  プロセス
800  プロセス
900  プロセス
950  プロセス
1000  プロセス
1100  プロセス
1161  囲繞エリア
1162  サブエリア
1166  長方形の区画
1167  長方形のグリッド
1210  ジオフェンス
1213  グリッド
1214  グリッド、ピボットグリッド
1216  囲繞エリア
1218  囲繞エリア
1220  ジオフェンス
1350  円形の地理的領域
【図１】
2021508856.tif 000040
【図２】
2021508856.tif 000041
【図３】
2021508856.tif 000042
【図４Ａ】
2021508856.tif 000043
【図４Ｂ】
2021508856.tif 000044
【図４Ｃ】
2021508856.tif 000045
【図４Ｄ】
2021508856.tif 000046
【図４Ｅ】
2021508856.tif 000047
【図４Ｆ】
2021508856.tif 000048
【図５】
2021508856.tif 000049
【図６Ａ】
2021508856.tif 000050
【図６Ｂ】
2021508856.tif 000051
【図７Ａ】
2021508856.tif 000052
【図７Ｂ】
2021508856.tif 000053
【図７Ｃ】
2021508856.tif 000054
【図７Ｄ】
2021508856.tif 000055
【図７Ｅ】
2021508856.tif 000056
【図７Ｆ】
2021508856.tif 000057
【図７Ｇ】
2021508856.tif 000058
【図７Ｈ】
2021508856.tif 000059
【図７Ｉ】
2021508856.tif 000060
【図７Ｊ】
2021508856.tif 000061
【図７Ｋ】
2021508856.tif 000062
【図８】
2021508856.tif 000063
【図９Ａ】
2021508856.tif 000064
【図９Ｂ】
2021508856.tif 000065
【図１０】
2021508856.tif 000066
【図１１Ａ】
2021508856.tif 000067
【図１１Ｂ】
2021508856.tif 000068
【図１２Ａ】
2021508856.tif 000069
【図１２Ｂ】
2021508856.tif 000070
【図１３Ａ】
2021508856.tif 000071
【図１３Ｂ】
2021508856.tif 000072
【手続補正書】
【提出日】令和2年6月30日(2020.6.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された人工知能システムであって、
前記地図と地理的領域を識別するための1セットの命令とを記憶する、少なくとも1つの記憶媒体と、
前記少なくとも1つの記憶媒体と通信する少なくとも1つのプロセッサであって、前記1セットの命令を実行すると、前記少なくとも1つのプロセッサは、
前記地図の少なくとも一部を前記少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードし、
前記地図の前記少なくとも一部の表示を生成し、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、それぞれ独立にインデックス付けされ、
前記地図における地理的領域のジオフェンスの情報を取得し、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定し、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別し、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが前記複数の区画の2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化し、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定し、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別し、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別する、
ように指示される、少なくとも1つのプロセッサと、
を備える、複数の独立にインデックス付けされたグリッドの領域を含む地図におけるエリアにおいてジオフェンスのグリッドを識別するように構成された人工知能システム。
【請求項２】
前記ジオフェンスの前記情報は、複数の境界点に対応する1セットの座標対を含み、
前記ジオフェンスの前記境界グリッド系列を判定するために、前記少なくとも1つのプロセッサは、前記複数のグリッドから前記複数の境界点に対応する前記境界グリッド系列を識別し、
以下のステップ、すなわち、
前記複数の境界点から2つの隣接する境界点を取得するステップと、
前記2つの隣接する境界点が同じグリッドに対応するか否かを判定するステップと、
前記2つの隣接する境界点が前記同じグリッドに対応するという判定に応じて、前記2つの隣接する境界点のうちの1つを除去するステップと、
前記2つの隣接する境界点が2つの異なるグリッドに対応するという判定に応じて、前記2つの隣接する境界点の間で境界点を補間するステップと、
前記複数の境界点に対応する前記境界グリッド系列を更新するステップと、
を含む1つまたは複数の動作を実行するようにさらに指示される、請求項1に記載の人工知能システム。
【請求項３】
前記境界グリッド系列は、前記ジオフェンスが通過する、前記地図の前記複数のグリッドからのグリッドを含み、
前記少なくとも1つの囲繞エリアを識別するために、前記少なくとも1つのプロセッサは、
前記境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定し、ピボットグリッドが少なくとも2つの同じグリッドインデックスに対応し、
前記境界グリッド系列が前記1つまたは複数のピボットグリッドを含むという判定に応じて、前記1つまたは複数のピボットグリッドのそれぞれについて、前記ピボットグリッドの一方の側にある前記地理的領域におけるエリアを、第1の囲繞エリアとして、また前記ピボットグリッドの他方の側にある前記地理的領域におけるエリアを、前記第1の囲繞エリアとは異なる第2の囲繞エリアとして識別する、
ようにさらに指示される、請求項1または2に記載の人工知能システム。
【請求項４】
前記少なくとも1つの囲繞エリアを識別するために、前記少なくとも1つのプロセッサは、
空のスタックおよび空の補助地図を生成し、
前記境界グリッド系列の各グリッドについて、
前記境界グリッド系列から前記グリッドを順次取得し、
前記グリッドに対応するグリッドインデックスが前記補助地図にあるか否かを判定し、
前記グリッドインデックスが前記補助地図にないという判定に応じて、前記グリッドインデックスを前記スタックにプッシュし、前記グリッドインデックスを前記補助地図に入力し、
前記グリッドインデックスが前記補助地図にあるという判定に応じて、前記グリッドインデックスに対応する前記グリッドを前記1つまたは複数のピボットグリッドのうちのピボットグリッドとして指定し、前記グリッドインデックスをピボットグリッドインデックスとして指定し、前記スタックの一番上にある前記グリッドインデックスが前記ピボットグリッドインデックスと同じになるまで、前記スタックから前記スタックにあるグリッドインデックスをポップし、前記ポップされたグリッドインデックスに対応するグリッドを前記第1の囲繞エリアの境界グリッドとして指定し、
前記スタックに残っているグリッドインデックスに対応するグリッドを、前記第2の囲繞エリアの境界グリッドとして指定する、
ようにさらに指示される、請求項3に記載の人工知能システム。
【請求項５】
前記ジオフェンスは、中心および半径によって定義される円に基づいて判定され、
前記地理的領域において前記少なくとも1つの囲繞エリアを識別するために、前記少なくとも1つのプロセッサは、
前記円上で複数のサンプル点を所定のサンプル間隔でサンプリングし、
前記複数のサンプル点に基づいて前記地理的領域における前記少なくとも1つの囲繞エリアの境界グリッドを判定する、
ようにさらに指示される、請求項1から4のいずれか一項に記載の人工知能システム。
【請求項６】
前記所定のサンプル間隔は、前記円の前記半径および前記複数のグリッドのうちのグリッドに関連する解像度に関連付けられる、請求項5に記載の人工知能システム。
【請求項７】
前記少なくとも1つのプロセッサは、
前記複数のサンプル点のうちの2つ以上のサンプル点が同じグリッドに対応すると判定すると、1つのサンプル点のみが前記グリッドに対応するように、前記2つ以上のサンプル点から1つまたは複数のサンプル点を除去する
ようにさらに指示される、請求項5または6に記載の人工知能システム。
【請求項８】
前記少なくとも1つの囲繞エリアを2つ以上のサブエリアにセグメント化した後、前記少なくとも1つのプロセッサは、
前記2つ以上のサブエリアが前記複数の区画の1つまたは複数の辺と交差する重複辺グリッドを判定し、
前記重複辺グリッドを前記2つ以上のサブエリアの前記境界グリッドとして前記2つ以上のサブエリアに追加する、
ように指示される、請求項1から7のいずれか一項に記載の人工知能システム。
【請求項９】
前記複数のグリッドから前記サブエリアにおける内部グリッドを識別するために、前記少なくとも1つのプロセッサは、
スキャニング行列を初期化し、前記スキャニング行列は複数のセルを含み、前記スキャニング行列の各セルは第1の値を有し、
前記スキャニング行列の第1の複数のセルのそれぞれに第2の値を入力することによって、前記スキャニング行列に対して第1の更新を実行し、前記第1の複数のセルは、前記サブエリアの前記境界グリッドに対応し、
前記第1の値を有する、前記第1の更新後の前記スキャニング行列の各セルについて、前記セルに対応する前記グリッドが前記地理的領域にあるか否かを判定し、
前記セルに対応する前記グリッドが前記地理的領域にあるという判定に応じて、
前記スキャニング行列の前記セルに第3の値を入力することによって、前記スキャニング行列に対して第2の更新を実行し、
前記第3の値を有する前記セルに対応するグリッドを前記サブエリアにおける前記内部グリッドとして指定する、
ように指示される、請求項1から8のいずれか一項に記載の人工知能システム。
【請求項１０】
地図と地理的領域を識別するための1セットの命令とを記憶する少なくとも1つの記憶媒体と、前記少なくとも1つの記憶媒体と通信する少なくとも1つのプロセッサと、を有するコンピューティングデバイス上で実施される、複数の独立にインデックス付けされたグリッドの領域を含む前記地図におけるエリアにおいてジオフェンスのグリッドを識別するための方法であって、前記方法は、
地図の少なくとも一部を前記少なくとも1つの記憶媒体から少なくとも1つのキャッシュ回路にロードするステップと、
前記地図の前記少なくとも一部の表示を生成するステップであって、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、それぞれ独立にインデックス付けされる、ステップと、
前記地図における地理的領域のジオフェンスの情報を取得するステップと、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定するステップと、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別するステップと、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが前記複数の区画の2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化するステップと、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定するステップと、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別するステップと、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別するステップと、
を含む、方法。
【請求項１１】
前記ジオフェンスの前記情報は、複数の境界点に対応する1セットの座標対を含み、
前記ジオフェンスの前記境界グリッド系列を判定する前記ステップは、
前記複数のグリッドから前記複数の境界点に対応する前記境界グリッド系列を識別するステップと、
以下のステップ、すなわち、
前記複数の境界点から2つの隣接する境界点を取得するステップと、
前記2つの隣接する境界点が同じグリッドに対応するか否かを判定するステップと、
前記2つの隣接する境界点が前記同じグリッドに対応するという判定に応じて、前記2つの隣接する境界点のうちの1つを除去するステップと、
前記2つの隣接する境界点が2つの異なるグリッドに対応するという判定に応じて、前記2つの隣接する境界点の間で境界点を補間するステップと、
前記複数の境界点に対応する前記境界グリッド系列を更新するステップと、
を含む1つまたは複数の動作を実行するステップと、
をさらに含む、請求項10に記載の方法。
【請求項１２】
前記境界グリッド系列は、前記ジオフェンスが通過する、前記地図の前記複数のグリッドからのグリッドを含み、
前記少なくとも1つの囲繞エリアを識別する前記ステップは、
前記境界グリッド系列が1つまたは複数のピボットグリッドを含むか否かを判定するステップであって、ピボットグリッドが少なくとも2つの同じグリッドインデックスに対応する、ステップと、
前記境界グリッド系列が前記1つまたは複数のピボットグリッドを含むという判定に応じて、前記1つまたは複数のピボットグリッドのそれぞれについて、前記ピボットグリッドの一方の側にある前記地理的領域におけるエリアを、第1の囲繞エリアとして、また前記ピボットグリッドの他方の側にある前記地理的領域におけるエリアを、前記第1の囲繞エリアとは異なる第2の囲繞エリアとして識別するステップと、
をさらに含む、請求項10または11に記載の方法。
【請求項１３】
前記少なくとも1つの囲繞エリアを識別する前記ステップは、
空のスタックおよび空の補助地図を生成するステップと、
前記境界グリッド系列の各グリッドについて、
前記境界グリッド系列から前記グリッドを順次取得するステップと、
前記グリッドに対応するグリッドインデックスが前記補助地図にあるか否かを判定するステップと、
前記グリッドインデックスが前記補助地図にないという判定に応じて、前記グリッドインデックスを前記スタックにプッシュし、前記グリッドインデックスを前記補助地図に入力するステップと、
前記グリッドインデックスが前記補助地図にあるという判定に応じて、前記グリッドインデックスに対応する前記グリッドを前記1つまたは複数のピボットグリッドのうちのピボットグリッドとして指定し、前記グリッドインデックスをピボットグリッドインデックスとして指定し、前記スタックの一番上にある前記グリッドインデックスが前記ピボットグリッドインデックスと同じになるまで、前記スタックから前記スタックにあるグリッドインデックスをポップし、前記ポップされたグリッドインデックスに対応するグリッドを前記第1の囲繞エリアの境界グリッドとして指定するステップと、
前記スタックに残っているグリッドインデックスに対応するグリッドを、前記第2の囲繞エリアの境界グリッドとして指定するステップと、
をさらに含む、請求項12に記載の方法。
【請求項１４】
前記ジオフェンスは、中心および半径によって定義される円に基づいて判定され、
前記地理的領域において前記少なくとも1つの囲繞エリアを識別する前記ステップは、
前記円上で複数のサンプル点を所定のサンプル間隔でサンプリングするステップと、
前記複数のサンプル点に基づいて前記地理的領域における前記少なくとも1つの囲繞エリアの境界グリッドを判定するステップと、
をさらに含む、請求項10から13のいずれか一項に記載の方法。
【請求項１５】
地理的領域を識別するための1セットの命令を含む非一時的コンピュータ可読媒体であって、少なくとも1つのプロセッサによって実行されると、前記少なくとも1セットの命令は、
少なくとも1つの記憶媒体からの地図にアクセスする動作と、
前記地図の表示を生成する動作であって、前記地図は、複数のグリッドにグリッド化され、複数の区画に分割され、前記地図における前記複数のグリッドの各グリッドが、グリッドインデックスに関連付けられ、各区画におけるグリッドが、それぞれ独立にインデックス付けされる、動作と、
前記地図における地理的領域のジオフェンスの情報を取得する動作と、
前記複数のグリッドから前記ジオフェンスの境界グリッド系列を判定する動作と、
前記境界グリッド系列に基づいて前記地理的領域における少なくとも1つの囲繞エリアを識別する動作と、
前記少なくとも1つの囲繞エリアのうちの囲繞エリアが前記複数の区画の2つ以上の区画を横切ると判定すると、2つ以上のサブエリアの各サブエリアが前記複数の区画のうちの1つの区画にのみ位置するように、前記囲繞エリアを前記2つ以上のサブエリアにセグメント化する動作と、
前記2つ以上のサブエリアのそれぞれについて境界グリッドを判定する動作と、
前記2つ以上のサブエリアのそれぞれについて、前記サブエリアの前記境界グリッドおよび前記サブエリアが位置する前記区画のインデックスに基づいて、前記複数のグリッドから前記サブエリアにおける内部グリッドを識別する動作と、
前記2つ以上のサブエリアの前記境界グリッドおよび前記2つ以上のサブエリアにおける前記内部グリッドを収集することにより、前記地理的領域におけるグリッドを識別する動作と、
を実行するように前記少なくとも1つのプロセッサに指示する、非一時的コンピュータ可読媒体。
【国際調査報告】
2021508856.tif 000073
2021508856.tif 000074