(57)【要約】  符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための、様々な方法、装置、および／または製造物品において実装され得る技法が提供される。
2014530370.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティングプラットフォームによって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得することと、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てることとを備える、方法。
【請求項２】
転換の前記可能性を割り当てることがさらに、
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てることを備える、請求項１に記載の方法。
【請求項３】
前記コンピューティングプラットフォームによって、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定することをさらに備える、請求項２に記載の方法。
【請求項４】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項２に記載の方法。
【請求項５】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項４に記載の方法。
【請求項６】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項２に記載の方法。
【請求項７】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項６に記載の方法。
【請求項８】
前記コンピューティングプラットフォームによって、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えることをさらに備える、請求項２に記載の方法。
【請求項９】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項２に記載の方法。
【請求項１０】
前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、請求項９に記載の方法。
【請求項１１】
前記コンピューティングプラットフォームによって、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定することをさらに備える、請求項２に記載の方法。
【請求項１２】
転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、請求項１に記載の方法。
【請求項１３】
前記演繹的な方向確率値が、前記符号化された経路指定可能性グラフに関する前記モバイルデバイスの配置に関して可能性のある行先を推定するための、モバイルデバイス中の測位エンジンによる使用のために設定される、請求項１２に記載の方法。
【請求項１４】
前記コンピューティングプラットフォームによって、
転換の前記可能性の少なくとも１つを少なくとも１つのモバイルデバイスに提供することをさらに備える、請求項１に記載の方法。
【請求項１５】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項１に記載の方法。
【請求項１６】
コンピューティングプラットフォームにおいて使用するための装置であって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得するための手段と、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための手段とを備える、装置。
【請求項１７】
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てるための手段をさらに備える、請求項１６に記載の装置。
【請求項１８】
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定するための手段をさらに備える、請求項１７に記載の装置。
【請求項１９】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項１７に記載の装置。
【請求項２０】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項１９に記載の装置。
【請求項２１】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項１７に記載の装置。
【請求項２２】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項２１に記載の装置。
【請求項２３】
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるための手段をさらに備える、請求項１７に記載の装置。
【請求項２４】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項１７に記載の装置。
【請求項２５】
前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するための手段をさらに備える、請求項１７に記載の装置。
【請求項２６】
転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、請求項１６に記載の装置。
【請求項２７】
少なくとも転換の前記可能性を少なくとも１つのモバイルデバイスに提供するための手段をさらに備える、請求項１６に記載の装置。
【請求項２８】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項１６に記載の装置。
【請求項２９】
メモリと、
１つまたは複数の処理ユニットとを備え、前記１つまたは複数の処理ユニットが、
前記メモリから、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるためのものである、コンピューティングプラットフォーム。
【請求項３０】
前記１つまたは複数の処理ユニットがさらに、
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てるためのものである、請求項２９に記載のコンピューティングプラットフォーム。
【請求項３１】
前記１つまたは複数の処理ユニットがさらに、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定するためのものである、請求項３０に記載のコンピューティングプラットフォーム。
【請求項３２】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項３０に記載のコンピューティングプラットフォーム。
【請求項３３】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項３２に記載のコンピューティングプラットフォーム。
【請求項３４】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項３０に記載のコンピューティングプラットフォーム。
【請求項３５】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項３４に記載のコンピューティングプラットフォーム。
【請求項３６】
前記１つまたは複数の処理ユニットがさらに、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるためのものである、請求項３０に記載のコンピューティングプラットフォーム。
【請求項３７】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項３０に記載のコンピューティングプラットフォーム。
【請求項３８】
前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、請求項３７に記載のコンピューティングプラットフォーム。
【請求項３９】
前記１つまたは複数の処理ユニットがさらに、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するためのものである、請求項３０に記載のコンピューティングプラットフォーム。
【請求項４０】
転換の前記可能性が演繹的な方向確率値を備える、請求項２９に記載のコンピューティングプラットフォーム。
【請求項４１】
ネットワークインターフェースと、
前記１つまたは複数の処理ユニットとをさらに備え、前記１つまたは複数の処理ユニットがさらに、
転換の前記可能性の少なくとも１つの、少なくとも１つのモバイルデバイスへの送信を開始するためのものである、請求項２９に記載のコンピューティングプラットフォーム。
【請求項４２】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項２９に記載のコンピューティングプラットフォーム。
【請求項４３】
コンピューティングプラットフォームにおいて使用するための物品であって、
コンピュータ実施可能命令を記憶した非一時的コンピュータ可読媒体を備え、前記コンピュータ実施可能命令が、１つまたは複数の処理ユニットによって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるように実行可能である、物品。
【請求項４４】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てるように実行可能である、請求項４３に記載の物品。
【請求項４５】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定するように実行可能である、請求項４４に記載の物品。
【請求項４６】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項４４に記載の物品。
【請求項４７】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項４６に記載の物品。
【請求項４８】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項４４に記載の物品。
【請求項４９】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項４８に記載の物品。
【請求項５０】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるように実行可能である、請求項４４に記載の物品。
【請求項５１】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項４４に記載の物品。
【請求項５２】
前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、請求項５１に記載の物品。
【請求項５３】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するように実行可能である、請求項４４に記載の物品。
【請求項５４】
転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、請求項４３に記載の物品。
【請求項５５】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
転換の前記可能性の少なくとも１つの、少なくとも１つのモバイルデバイスへの送信を開始するように実行可能である、請求項４３に記載の物品。
【請求項５６】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項４３に記載の物品。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本願は、参照によって全体が本明細書に組み込まれる、２０１１年１０月１７日に出願された米国仮特許出願第６１／５４８，６１５号と、２０１１年１２月１日に出願された米国特許出願第１３／３０９，３０４号とに対する優先権を主張する、ＰＣＴ出願である。
【０００２】
本明細書で開示される主題は、電子デバイスに関し、より具体的には、構造物の少なくとも一部分に関する符号化された地図とともに使用する符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を決定する際に使用する、方法と、装置と、製造物品とに関する。
【背景技術】
【０００３】
全地球測位システム（ＧＰＳ）は、他のタイプの衛星測位システム（ＳＰＳ）とともに、モバイルデバイスにおいて、特に屋外環境において、信号ベースの位置特定機能（たとえば、測位機能）を与え、または別様に支援する、全地球航法衛星システム（ＧＮＳＳ）の１つのタイプを表す。しかしながら、いくつかの衛星信号は、屋内環境内または他の同様の屋内／屋外混合環境内のモバイルデバイスによって確実に受信および／または獲得されないことがあるので、位置特定サービスを可能にするために異なる技法が採用され得る。
【０００４】
たとえば、モバイルデバイスは、既知の場所に位置する３つ以上の地上波送信機（たとえば、ワイヤレスアクセスポイント、ビーコン、セルタワーなど）までの距離を測定することによって位置決定を取得しようと試みることがある。そのような距離は、たとえば、そのような送信機から受信された信号からＭＡＣ  ＩＤアドレスを取得することと、たとえば、そのような送信機から受信された信号の１つまたは複数の特性、たとえば、信号強度、往復遅延時間などを測定することによって送信機までの距離測定値を取得することとによって測定され得る。
【０００５】
これらおよび他の同様の位置特定および／またはナビゲーション技法は、地図に示されたいくつかの特徴とともに提示された場合、ユーザにとってさらに有益である傾向がある。たとえば、地図に示された地物(ｆｅａｔｕｒｅｓ)は、いくつかの物理的な物体、特性、あるいは建物または複合施設の内部の関心地点（ｐｏｉｎｔ  ｏｆ  ｉｎｔｅｒｅｓｔ）などに関係し、または別様にそれを識別し得る。したがって、いくつかの事例では、屋内の測位／ナビゲーションシステムは、ある特定の屋内領域に入ると、符号化された地図をモバイルデバイスに提供することができる。そのような地図は、扉、通路、入口、壁などのような屋内の地物、化粧室、公衆電話、部屋名、店舗などのような関心地点を示し得る。そのような符号化された地図は、たとえば、モバイルデバイスによってＵＲＬの選択を通じてアクセス可能であるように、サーバに記憶され得る。そのような地図を取得し、表示することによって、モバイルデバイスは、追加のコンテキストをユーザに与えるために、表示された地図上にモバイルデバイス（およびユーザ）の現在の場所を重畳し得る。
【０００６】
さらに、符号化された地図に関連する符号化された経路指定可能性グラフを生成すること、または別様に取得することによって、モバイルデバイスの測位エンジンまたは他の同様の機能が、屋内構造物内を移動するために使用され得る。しかしながら、いくつかの事例では、符号化された経路指定可能性グラフは、かなり大きいことがあり、かつ／または、別様に計算上複雑であることがあるので、一部のモバイルデバイスには大きな負荷となり得る。したがって、そのような符号化されたファイルのサイズおよび／または複雑さを低減し、かつ／または、そのようなファイルを処理する負荷を低減することに対する要求が依然としてある。
【発明の概要】
【０００７】
一態様によれば、コンピューティングプラットフォームによって、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得することと、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てることとを備える方法が、提供され得る。
【０００８】
別の態様によれば、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得するための手段と、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための手段とを備える、コンピューティングプラットフォームにおいて使用するための装置が提供され得る。
【０００９】
さらに別の態様によれば、メモリと、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフをメモリから取得し、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための、１つまたは複数の処理ユニットとを備える、コンピューティングプラットフォームが提供され得る。
【００１０】
さらに別の態様によれば、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための、１つまたは複数の処理ユニットによって実行可能なコンピュータ実施可能命令を記憶した非一時的コンピュータ可読媒体を備える、コンピューティングプラットフォームにおいて使用するための製造物品が提供され得る。
【００１１】
次の図を参照して、非限定的かつ非網羅的な態様が説明され、別段規定されない限り、様々な図の全体を通して、同様の参照番号は同様の部分を指す。
【図面の簡単な説明】
【００１２】
【図１】ある例示的な実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性が生成され、送信され、記憶され、かつ／または別様に処理され得る、コンピューティングおよび通信環境を示す、概略的なブロック図。
【図２】ある例示的な実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を生成し得るコンピューティングデバイスのいくつかの特徴を示す、概略的なブロック図。
【図３】ある例示的な実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を生成し得る、または別様に取得し得る、モバイルデバイスのいくつかの特徴を示す、概略的なブロック図。
【図４】ある例示的な実装形態による、ｖ字状のオフィスのフロアの図における縮小された分岐点のセットを示す、説明のための図。
【図５】ある例示的な実装形態による、互いに接続され、かつ複数の入口エッジと出口エッジに接続されるノードの形式の２つの分岐点を、それらに対応する複数のあり得る経路とともに示す、説明のための図。
【図６】ある実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を生成するための、コンピューティングデバイスおよび／またはモバイルデバイスによって全体または一部が実施され得る、例示的な方法を示す流れ図。
【発明を実施するための形態】
【００１３】
符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を生成するための、１つまたは複数のコンピューティングプラットフォームにおいて実装され得る、様々な技法が本明細書において説明される。いくつかの例示的な事例では、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を事前に生成することで、モバイルデバイスの処理負荷を減らすことができ、かつ／または、屋内構造物の中をユーザが移動するのを助けるためにモバイルデバイスが使用されているときのモバイルデバイスの性能を場合によっては改善することができる。
【００１４】
本明細書で提供される技法を支援する際に処理され得る様々なデータファイルおよび／または命令ファイルに関する、「符号化された」という用語の本明細書での使用。符号化されたデータファイルおよび／または命令ファイルは、たとえば、１つまたは複数のコーディング方式を介して、１つまたは複数の物体、動作、能力、機能など、または何らかの題材に関するそれらの何らかの組合せを示し得る、複数の論理値またはビットを備え得る。たとえば、いくつかの事例では、構造物の地図中に出現し得るとともに、そのような構造物内のユーザが関心をもち得る、または別様にユーザの動きに影響を与え得る、いくつかのモデル化された物体および／もしくは現実世界の物体、ならびに／または他の同様の地物、ならびに／または構造物の領域を表すために、符号化された地図が生成され得る。別の例では、ある特定の構造物内のユーザのいくつかの可能な動きに関連し得る、いくつかの分岐点と相互接続するエッジとを表すための符号化された地図に少なくとも一部基づいて、符号化された経路指定可能性グラフが生成され得る。いくつかの例では、データ圧縮、暗号化、誤り訂正など、またはこれらの何らかの組合せを行うために、１つまたは複数の符号化されたデータファイルおよび／または命令ファイルがさらに処理され得る。
【００１５】
符号化された経路指定可能性グラフの表現は、たとえば、屋内構造物の符号化された地図に関連し、屋内構造物内で人がたどり得る経路を示し得る。たとえば、符号化された経路指定可能性グラフの表現は、ある屋内空間の入口から、１つまたは複数の部屋、または、他の空間および／もしくは他の空間中の物体へとつながる、１つまたは複数の経路を示し得る。ここで、たとえば、経路は、人がその間を移動し得る複数の相互接続された分岐点に基づいて示され得る。そのような経路は、たとえば、１つまたは複数の通路／廊下、１つまたは複数の出入口、１つまたは複数の階段室、および／または、電子地図（たとえば、平面図、オフィスレイアウトなど）から示され得る、もしくは別様にそれから決定され得る、他の同様の地物を通過し得る。しかしながら、たとえば、そのような経路は、固定された壁、床、天井、机、および／または、人が通過できない、または通常は通過しないであろう他の同様の物体もしくは地物を通過できない。
【００１６】
単純な屋内構造物は、人がたどり得る使用可能な経路を、１つまたは場合によってはわずか数個しか備えないことがあるが、ある（たとえば、より大きなまたはより複雑な）屋内構造物は、人がたどり得る使用可能な経路を大量に提供し得ることを認識されたい。このことに留意すると、本明細書でより詳しく説明されるように、いくつかの事例では、人がたどり得る使用可能な経路の数を減らすことが有益であり得る。たとえば、いくつかの事例では、グリッドまたは他の同様のノードのパターンにおいて相互接続された分岐点の数を大きく減らし得る、符号化された経路指定可能性グラフの縮小されたバージョンが利用され得る。たとえば、符号化された経路指定可能性グラフ、符号化された経路指定可能性グラフの縮小されたバージョンなど、またはこれらの何らかの組合せによって、複数の使用可能な経路の中から人がたどり得るいくつかのあり得る経路を、たとえば、屋内構造物の１つまたは複数の特定の地物、１つまたは複数の特定の関心地点など、またはこれらの何らかの組合せに関連する、最短のまたは他の可能性のある進路に少なくとも一部基づいて決定することが、さらに有益であり得る。したがって、いくつかの事例では、あり得る経路のセットは、使用可能な経路のセットのすべてまたは一部を表し得る。したがって、いくつかの事例では、あり得る経路は、複数の使用可能な経路を通過し得る。言い換えると、あり得る経路は、たとえば、ある関心地点から別の関心地点へと延びる、一連の使用可能な経路を備え得る。
【００１７】
予想されるように、いくつかの経路は、異なる方向へと分岐する前に、同じ通路または出入口を通過し得る。その結果、人は、ある特定の分岐点において、またはその近くで、移動の方向（経路の１つに従った）を変え得る。たとえば、通路の終わりにおいて、通路の両側に位置する２つの部屋があることがある。したがって、分岐点は、通路の終わりにおいて、またはその近くで表されてよく、２つの部屋の中に位置するそれぞれの分岐点へとエッジによって接続されてよい。よって、通路中の分岐点にいる、またはその近くにいるユーザは、（たとえば、通路の終わりにおいて左または右に曲がることによって）エッジの１つに沿った部屋の１つへの特定の経路をたどり得る。いくつかの事例では、ユーザはまた、そのような分岐点において引き返し、または別様に方向を反転させて、前の経路を引き返すことがある。この例では、人が通路の終わりの分岐点またはその近くにおいて移動の経路を終了させないと仮定すると、３つのあり得る方向転換、すなわち、左折、右折、または引き返しがある。
【００１８】
他の（終端しない）分岐点は、より少数または多数のあり得る方向転換を提供し得ることを認識されたい。たとえば、単純な終端しない分岐点は、２つのエッジによって２つの他の分岐点の間で接続され得る。したがって、経路に応じて、エッジの一方は入口エッジを表すことができ、もう一方はその特定の分岐点に関する出口エッジを表すことができる。たとえば、１つの経路は、そのような特定の分岐点に向かう入口エッジと、その特定の分岐点から離れる出口エッジとをたどり得る。人がそのような特定の分岐点またはその近くで引き返すことを決めると、そのような反転された経路は、その特定の分岐点に向かう入口エッジと、その特定の分岐点から離れる同じエッジとをたどることができ、この場合、入口エッジが出口エッジになっている。したがって、分岐点は、たとえば、１つまたは複数の入口エッジと１つまたは複数の出口エッジとを備えてよく、（使用可能なかつ／またはあり得る）経路は、２つの分岐点の間の１つまたは複数のエッジをたどり得る。
【００１９】
よって、本明細書で使用される場合、エッジとは、符号化された経路指定可能性グラフ中のある分岐点に対応するある場所から、符号化された経路指定可能性グラフ中の別の分岐点に対応する別の場所への、構造物の屋内環境の中でモバイルデバイスのユーザがたどることが可能であると考えられる経路を表す。したがって、ユーザの移動の方向に応じて、エッジは、ある特定の分岐点へとつながる場合、その特定の分岐点に関する入口エッジという形態をとり得る。逆に、ユーザの移動の方向に応じて、エッジは、ある特定の分岐点から離れる場合、その特定の分岐点に関する出口エッジという形態をとり得る。当然、いくつかの事例では（たとえば、ユーザが引き返す、または方向を反転する場合）、エッジは、最初は出口エッジという形態をとり、結局は入口エッジとなる。
【００２０】
符号化された経路指定可能性グラフ中の２つの分岐点がエッジによって接続されない場合、そのようなエッジがないことは、符号化された経路指定可能性グラフと関連付けられる構造物の屋内環境の中でモバイルデバイスのユーザがたどることが可能ではないと考えられる経路を表す。よって、たとえば、モバイルデバイスのユーザは、たとえば壁のような障害物を通る経路をたどることは不可能である可能性が高いので、関連する符号化された経路指定可能性グラフは、そのような障害物の両側に位置する２つの分岐点の間にエッジを含まない。
【００２１】
本明細書でより詳しく指摘されるように、１つまたは複数の分岐点と関連付けられる１つまたは複数のエッジに対して転換の可能性を割り当てることが有用であり得る。たとえば、モバイルデバイス中の測位エンジンが、転換のそのような可能性に関する１つまたは複数の値（たとえば、方向的な確率、重みなど）を考慮して、モバイルデバイスを持ち運ぶ、または別様にそれとともに移動する人（ユーザ）の移動の方向を推定することが有用であり得る。したがって、たとえば、測位エンジンの粒子フィルタ、カルマンフィルタなどは、ある分岐点から入口エッジに沿って別の分岐点に移動するユーザが、移動の経路を続ける際にある特定の出口エッジへと転換し得るもしくは転換し得ない確率値、または他の同様の尺度を考慮することができる。
【００２２】
いくつかの態様によれば、転換の１つまたは複数の可能性は、たとえば、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前もって（演繹的に）決定されてよい。その上、そのような転換の可能性のすべてまたは一部は、たとえば、モバイルデバイスの内部および／または外部に位置する、１つまたは複数のコンピューティングプラットフォームによって決定され得る。
【００２３】
たとえば、本明細書でより詳しく説明されるように、コンピューティングプラットフォームは、符号化された地図によって表される屋内環境中の使用可能な経路の少なくとも一部分を表す、符号化された経路指定可能性グラフを取得することができる。コンピューティングプラットフォームは、たとえば、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、入口エッジを出口エッジに接続する分岐点を通る転換の可能性を割り当てることができる。
【００２４】
いくつかのさらなる例示的な実装形態では、コンピューティングプラットフォームは、入口エッジを通り分岐点に接続される符号化された経路指定可能性グラフ中のあり得る出発側経路と、出口エッジを通り分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の可能性を割り当てることができる。たとえば、コンピューティングプラットフォームは、分岐点から離れる出口エッジを通るあり得る経路の数と、分岐点に向かう入口エッジを通るあり得る経路の数との比に少なくとも一部基づいて、入口エッジから出口エッジの１つへの転換の少なくとも１つの可能性を決定することができる。
【００２５】
いくつかの例示的な実装形態では、あり得る出発側経路および／またはあり得る行先側経路は、符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づき得る。たとえば、いくつかの事例では、符号化された経路指定可能性グラフの縮小されたバージョン中のノードは、ノードによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられ得る。たとえば、いくつかの事例では、巨視的な使用可能な経路を示す符号化された経路指定可能性グラフの縮小されたバージョン中のノードは、比較的より細かい微視的な使用可能な経路を示し得る符号化された接続グラフの複数のノードを備え／使用し、または別様に表し得る。
【００２６】
いくつかの例示的な実装形態では、あり得る出発側経路および／またはあり得る行先側経路は、符号化された経路指定可能性グラフに沿って符号化された地図によって表される屋内環境中の関心地点を表すノード間の地点間接続に少なくとも一部基づき得る。いくつかの例示的な事例では、少なくとも１つの関心地点を表すノードは、少なくとも１つの別の関心地点を表す少なくとも１つの他のノードに対する重み値を割り当てられ得る。いくつかの例示的な実装形態では、コンピューティングプラットフォームは、全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、符号化された経路指定可能性グラフ中の少なくとも１つのあり得る出発側経路を決定することができる。
【００２７】
いくつかの例示的な実装形態では、コンピューティングプラットフォームは、少なくとも１つの分岐点に対応する符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる、少なくとも１つの重み値に影響を与え得る。
【００２８】
いくつかの例示的な実装形態では、転換の可能性は、入口エッジが出口エッジをさらに表す、分岐点におけるあり得る引き返しの転換を表し得る。いくつかの事例では、あり得る引き返しの転換を表す転換の可能性は、たとえば、所定の値（たとえば、ノミナル値、ヌル値など）を備え得る。
【００２９】
図１は、ある例示的な実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性１１６を表す１つまたは複数の値が生成され、送信され、記憶され、かつ／または別様に処理され得る、コンピューティングおよび通信環境１００を示す、概略的なブロック図である。
【００３０】
例示的な環境１００は、転換の可能性１１６のすべてまたは一部を生成する際に使用するための装置１０４を有する、コンピューティングデバイス１０２を備え得る。以下でより詳しく説明されるように、装置１０４は、たとえば、モバイルデバイス１０６のユーザによって何らかの方式で移動され得る屋内領域を含む構造物の符号化された地図（たとえば、平面図、オフィスレイアウト、ＣＡＤ図面などに関する１つまたは複数の電子ファイル）に対する、符号化された経路指定可能性グラフの表現を取得することができる。符号化された地図は、たとえば、何らかの方式で構造物内のユーザの移動に影響を与え得る、様々な地物を示し得る。たとえば、いくつかの地物は、屋内領域内に存在する様々なタイプの進路障害物を示し得る。たとえば、いくつかの地物は、ユーザによって移動され得るまたは移動され得ない、空間の領域を示し得る。たとえば、いくつかの地物は、１人または複数のユーザが時として関心をもち得る、いくつかの場所、物体、サービスなどを示し得る。
【００３１】
符号化された経路指定可能性グラフの表現は、たとえば、屋内領域の符号化された地図の一部分に割り当てられ得るとともに、ユーザが移動し得る使用可能な経路を表すために相互接続され得る、グリッド点（たとえば、ノード、分岐点）のセットを示し得る。いくつかの事例では、符号化された経路指定可能性グラフの表現は、たとえば、グリッド点のセットを減らすためにいくつかのグリッド点が選択的に統合されている、符号化された経路指定可能性グラフの縮小されたバージョンを示し得る。よって、たとえば、いくつかの実装形態では、符号化された経路指定可能性グラフの表現は、選択的に統合されたグリッド点を備えることがあり、この場合、グリッド点の場所の間に進路障害物がないことを考慮していくつかの隣接するグリッド点が他のグリッド点を吸収した可能性がある。相互接続されたグリッド点のセットが減らされ得る、種々の方法がある。したがって、グリッド点の完全なセットおよび／または何らかの縮小されたセットの一部のすべてが、本明細書で説明されるような転換の可能性１１６のすべてまたは一部を生成する際に使用するための、符号化された経路指定可能性グラフとして、装置１０４において特定され得る。
【００３２】
示されるように、コンピューティングデバイス１０２は、通信リンク１１２を介して１つまたは複数の有線ネットワークおよび／またはワイヤレスネットワーク１１０に接続され得る。モバイルデバイス１０６は、たとえば、通信リンク１１４を介してネットワーク１１０に結合され得る。したがって、いくつかの例示的な実装形態では、転換の可能性１１６を表す１つまたは複数の値は、コンピューティングデバイス１０２によってモバイルデバイス１０６に送信され、または別様に提供され得る。たとえば、転換の可能性１１６のすべてまたは一部は、移動の可能性の高い経路を推定するためにモバイルデバイス中の測位エンジンによって使用され得る、演繹的な方向的確率値などを表し得る。
【００３３】
いくつかの例示的な実装形態では、モバイルデバイス１０６は、たとえば、転換の可能性１１６を表す値のすべてまたは一部のすべてまたは一部を自身で生成することができる、装置１０８を備え得る。本明細書で示されるように、転換の可能性１１６を表す値のすべてまたは一部のすべてまたは一部を生成するために、１つまたは複数のコンピューティングプラットフォームが、１つまたは複数のデバイスにおいて提供され得る。装置１０８はさらに、または代替的に、転換の可能性１１６を表す値のすべてまたは一部を、取得し、送信し、かつ／または別様に処理することができる。
【００３４】
ネットワーク１１０は、たとえば、通信リンク１１８を介して、たとえば、１つまたは複数の他のリソース（デバイス）１２０にさらに 接続されてよい。いくつかの例示的な実装形態では、コンピューティングデバイス１０２および／またはモバイルデバイス１０６は、他のリソース（デバイス）１２０から、１つまたは複数の符号化された地図および／もしくは他の同様の図、ならびに／または、１つまたは複数の符号化された経路指定可能性グラフおよび／もしくは他の同様のデータファイルなどのすべてまたは一部を取得することができ、これらは、構造物に対する転換の可能性１１６を表す値のすべてまたは一部のすべてまたは一部を生成し、または別様に処理する際に有用であり得る。
【００３５】
いくつかの例示的な実装形態では、環境１００はさらに、モバイルデバイス１０６によって受信され、信号ベースの測位機能および／または他の同様のナビゲーション機能を支援するために少なくとも一部使用され得る、１つまたは複数の信号１３２を送信することができる１つまたは複数の送信デバイス１３０を備え得る。例として、１つまたは複数の送信デバイス１３０は、全地球航法衛星システム（ＧＮＳＳ）、地域測位／ナビゲーションシステムなどのような、衛星測位システム（ＳＰＳ）の一部であってよく、または別様にそれを支援してよい。いくつかの例では、１つまたは複数の送信デバイス１３０は、地上波ベースの位置情報サービス（ＬＢＳ）などの一部であってよく、または別様にそれを支援してよく、地上波ベースのＬＢＳなどは、１つまたは複数のセルラー通信ネットワーク、１つまたは複数のワイヤレス通信ネットワーク、１つまたは複数の専用ビーコン送信デバイスなど、またはこれらの何らかの組合せを介して実装され得る。いくつかの事例では、１つまたは複数の送信デバイス１３０は、追加の通信サービスをモバイルデバイス１０６に提供することができ、したがってモバイルデバイス１０６は、ネットワーク１１０および／またはその一部に結合され得る。たとえば、１つまたは複数の送信デバイス１３０は、たとえば、送信デバイス１３０とネットワーク１１０を接続する点線によって図において表されるような、ワイヤレスローカルエリアネットワークなどの中のアクセスポイントを備え得る。その結果、いくつかの事例では、信号１３２は、ワイヤレス送信デバイス１３０とモバイルデバイス１０６との間の双方向ワイヤレス通信を備え得る。
【００３６】
理解され得るように、いくつかの事例では、１つまたは複数の送信デバイス１３０からの１つまたは複数の信号１３２は、モバイルデバイス１０６によって獲得され、何らかの方式で位置決定を推定するために使用され得る。モバイルデバイス１０６が構造物の中にある間、いくつかの事例では、送信デバイス１３０のいくつかからの信号および３２のいくつかは、構造物を構成する様々な物体および／または構造物内の物体によって引き起こされる、干渉および／または他の信号伝搬要因により、獲得されないことがある。したがって、たとえば、いくつかの構造物の中では、モバイルデバイス１０６は、軌道衛星によって送信されるＳＰＳ信号を適切に獲得することが不可能であることがある。しかしながら、いくつかの事例では、構造物の中にある間、モバイルデバイス１０６は、ＳＰＳ信号を補強し、かつ／または位置情報サービスなどと関連付けられる信号を表し得る、地上ベースの送信を適切に獲得することが可能であり得る。よって、たとえば、いくつかの構造物の中にある間、モバイルデバイス１０６は、１つまたは複数の送信デバイス１３０から取得された１つまたは複数の信号１３２に基づいて、位置決定を推定しようと試みることができ、いくつかの事例では、そのような送信デバイス１３０の１つまたは複数は、構造物内で適切なカバレッジを提供するように、構造物の中で、かつ／または構造物に関して配置され得る。そのような技法およびシステムはよく知られており、普及しつつある。
【００３７】
「構造物」という用語は、たとえば、物体の１つまたは複数の自然な物理的配置および／または人工的な物理的配置（のすべてまたは一部）に適用されてよく、それに関する知識はモバイルデバイス１０６のユーザにとって有用であり得る。たとえば、構造物は、１つまたは複数の建物またはその一部分を備え得る。「地物」は、たとえば、物体または障害物（たとえば、壁、扉、エレベータ、階段室、像など）、エンティティおよび／またはサービス（たとえば、事業所、タクシー乗り場、休憩所、診療所、遺失物取扱所、警備室など）、および／または、電子地図の１つまたは複数のファイル中の表現データを介して特定され得る、任意の他の測位／ナビゲーションに関する位置情報サービス特性を、特定し得る。いくつかの事例では、たとえば、地物は、それを避けて移動すべき何か（たとえば、進路障害物のような）、それに向かってまたはそれを通って移動すべき何か（たとえば、出入口、エレベータなど）、または場合によっては、それから離れるように移動すべき何か（たとえば、階段室）を表し得る。当然、これらは単にいくつかの例であり、本明細書で提示される例のすべてがそうであるように、特許請求される主題は必ずしもそのように限定されることを意図されない。
【００３８】
次に図２に対して参照が行われ、図２は、ある例示的な実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を表す１つまたは複数の値を生成し得るコンピューティングプラットフォーム２００の形態の、たとえば図１のようなコンピューティングデバイス１０２のいくつかの地物を示す概略的なブロック図である。
【００３９】
示されるように、コンピューティングプラットフォームは、（たとえば、本明細書で提供される技法による）データ処理を実行するための、１つまたは複数の接続２０６を介してメモリ２０４に結合された１つまたは複数の処理ユニット２０２を備え得る。処理ユニット２０２は、たとえば、ハードウェアまたはハードウェアとソフトウェアの組合せで実装され得る。処理ユニット２０２は、たとえば、データ計算手順または処理の少なくとも一部を実行するように構成可能な１つまたは複数の回路を表し得る。限定ではなく例として、処理ユニットは、１つまたは複数のプロセッサ、コントローラ、マイクロプロセッサ、マイクロコントローラ、特定用途向け集積回路、デジタル信号プロセッサ、プログラマブル論理デバイス、フィールドプログラマブルゲートアレイなど、またはこれらの任意の組合せを含み得る。
【００４０】
メモリ２０４は、任意のデータ記憶機構を表し得る。たとえば、メモリ２０４は、１次メモリ２０４−１および／または２次メモリ２０４−２を含み得る。たとえば、１次メモリ２０４−１は、ランダムアクセスメモリ、読取り専用メモリなどを備え得る。この例では処理ユニットとは別個なものとして示されるが、１次メモリのすべてまたは一部は、処理ユニット２０２またはコンピューティングデバイス１０２内の他の同様の回路内に設けられてよく、または場合によっては、そのような回路と共設／結合されてよいことを理解されたい。たとえば、２次メモリ２０４−２は、１次メモリと同じまたは同様のタイプのメモリ、および／または１つまたは複数のデータ記憶デバイスもしくはシステム、たとえば、ディスクドライブ、光ディスクドライブ、テープドライブ、ソリッドステートメモリドライブなどを備え得る。いくつかの実装形態では、２次メモリは、（非一時的）コンピュータ可読媒体２５０を動作可能に受容することができ、またはそうでなければそれに結合するように構成され得る。メモリ２０４および／またはコンピュータ可読媒体２５０は、本明細書で提供されるようないくつかの例示的な技法のための、コンピュータ実装可能命令２５２を備え得る。
【００４１】
図２に示されるように、様々な時点で、メモリ２０４は、本明細書で提供されるようないくつかの例示的な技法のために、データおよび／またはコンピュータ実施可能命令を表すいくつかの信号を記憶することができる。たとえば、メモリ２０４は、装置１０４のためのデータおよび／またはコンピュータ実施可能命令を記憶することができる。例として、メモリ２０４は、様々な時点において、転換の１つまたは複数の可能性１１６を表す１つまたは複数の値に対する表現データ、１つまたは複数の符号化された地図２１０またはその一部、符号化された経路指定可能性グラフの表現２１２のすべてまたは一部、１つまたは複数の使用可能な経路および／またはあり得る経路２１４、１つまたは複数のエッジ２１６、１つまたは複数の分岐点２１８、１つまたは複数の地物２２０、１つまたは複数の関心地点２２２、全対最短経路（ＡＰＳＰ）アルゴリズム２２４など、１つまたは複数の比２２６、１つまたは複数の重み値２２８など、またはこれらの何らかの組合せを記憶することができる。
【００４２】
示されるように、コンピューティングデバイス１０２は、たとえば、ネットワークインターフェース２０８を備え得る。ネットワークインターフェース２０８は、たとえば、ネットワーク１１０（図１）を介して通信するために、有線信号および／またはワイヤレス信号を受信および／または送信する能力を提供することができる。
【００４３】
いくつかの例示的な実装形態では、コンピューティングプラットフォーム２００は、サーバまたは他の同様のデバイスの形態をとることができる。いくつかの例示的な実装形態では、コンピューティングプラットフォーム２００は、ワイヤレスネットワーク要素、または他の位置情報サービス要素の形態をとることができる。いくつかの例示的な実装形態では、コンピューティングプラットフォーム２００は、クラウドコンピューティング構成の一部分の形態をとることができる。いくつかの例示的な実装形態では、コンピューティングプラットフォーム２００は、ワイヤレスアクセスポイントまたは他の同様のローカルエリアコンピューティングリソースの形態をとることができる。
【００４４】
次に図３に対して参照が行われ、図３は、ある例示的な実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を表す１つまたは複数の値を生成し得る、または別様に取得し得る、コンピューティングプラットフォーム３００の形態の、たとえば図１のモバイルデバイス１０６のいくつかの地物を示す概略的なブロック図である。
【００４５】
示されるように、コンピューティングプラットフォーム３００は、（たとえば、本明細書で提供される技法による）データ処理を実行するための、１つまたは複数の接続３０６を介してメモリ３０４に結合された１つまたは複数の処理ユニット３０２を備え得る。処理ユニット３０２は、たとえば、ハードウェアまたはハードウェアとソフトウェアの組合せで実装され得る。処理ユニット３０２は、たとえば、データ計算手順または処理の少なくとも一部を実行するように構成可能な１つまたは複数の回路を表し得る。限定ではなく例として、処理ユニットは、１つまたは複数のプロセッサ、コントローラ、マイクロプロセッサ、マイクロコントローラ、特定用途向け集積回路、デジタル信号プロセッサ、プログラマブル論理デバイス、フィールドプログラマブルゲートアレイなど、またはこれらの任意の組合せを含み得る。
【００４６】
メモリ３０４は、任意のデータ記憶機構を表し得る。たとえば、メモリ３０４は、１次メモリ３０４−１および／または２次メモリ３０４−２を含み得る。たとえば、１次メモリ３０４−１は、ランダムアクセスメモリ、読取り専用メモリなどを備え得る。この例では処理ユニットとは別個なものとして示されるが、１次メモリのすべてまたは一部は、処理ユニット３０２またはモバイルデバイス１０６内の他の同様の回路内に設けられてよく、または場合によっては、そのような回路と共設／結合されてよいことを理解されたい。たとえば、２次メモリ３０４−２は、１次メモリと同一または同様のタイプのメモリ、および／または１つまたは複数のデータ記憶デバイスもしくはシステム、たとえば、ディスクドライブ、光ディスクドライブ、テープドライブ、ソリッドステートメモリドライブなどを備え得る。いくつかの実装形態では、２次メモリは、（非一時的）コンピュータ可読媒体３２０を動作可能に受容することができ、またはそうでなければそれに結合するように構成され得る。メモリ３０４および／またはコンピュータ可読媒体３２０は、本明細書で提供されるようないくつかの例示的な技法のための、コンピュータ実装可能命令３２２を備え得る。
【００４７】
図３に示されるように、様々な時点で、メモリ３０４は、本明細書で提供されるようないくつかの例示的な技法のために、データおよび／またはコンピュータ実施可能命令を表すいくつかの信号を記憶することができる。たとえば、メモリ３０４は、装置１０８のためのデータおよび／またはコンピュータ実施可能命令を記憶することができる。例として、メモリ３０４は、様々な時点において、転換の１つまたは複数の可能性１１６を表す１つまたは複数の値に対する表現データ、１つまたは複数の符号化された地図２１０またはその一部、符号化された経路指定可能性グラフの表現２１２のすべてまたは一部、１つまたは複数の使用可能な経路および／またはあり得る経路２１４、１つまたは複数のエッジ２１６、１つまたは複数の分岐点２１８、１つまたは複数の地物２２０、１つまたは複数の関心地点２２２、全対最短経路（ＡＰＳＰ）アルゴリズム２２４など、１つまたは複数の比２２６、１つまたは複数の重み値２２８、測位エンジン３１４、１つまたは複数の推定される行先３１６など、またはこれらの何らかの組合せを記憶することができる。
【００４８】
示されるように、モバイルデバイス１０６は、たとえば、ワイヤレスインターフェース３０８を備え得る。ワイヤレスインターフェース３０８は、たとえば、ネットワーク１１０および／または１つまたは複数の送信機デバイス１３０（図１）を介して通信するために、有線信号および／またはワイヤレス信号を受信および／または送信する能力を提供することができる。ワイヤレスインターフェース３０８は、限定はされないが、ＧＳＭ（登録商標）、ＵＭＴＳ、ＣＤＭＡ、ＬＴＥ、ＷＣＤＭＡ（登録商標）、およびＣＤＭＡ２０００のようなワイドエリアネットワーク（ＷＡＮ）のためのインターフェース、ならびに、ＷｉＦｉ（登録商標）およびＢｌｕｅｔｏｏｔｈ（登録商標）のようなパーソナルエリアネットワーク（ＰＡＮ）のためのインターフェースを場合によっては含む、１つまたは複数のインターフェースから成っていてよい。同時に、または個別に使用され得る、複数のワイヤレスインターフェース３０８が存在し得ることも、理解される。ワイヤレスインターフェース３０８は、いくつかの実装形態では、たとえば、セルラーネットワーク、ＷｉＦｉネットワークなどによって少なくとも一部提供され得る１つまたは複数のＬＢＳのような、地上の測位サービスによってたとえば支援され得る、位置特定および／または他の測位／ナビゲーションサービスにおいて使用するための、１つまたは複数の送信デバイス１３０からの信号１３２（図１）を獲得するための受信機デバイス（および／または送受信機デバイス）として、同時に、かつ／または代替的に動作することができる。いくつかの例示的な実装形態では、ワイヤレスインターフェース３０８はまた、１つまたは複数の有線ネットワークインターフェースを表し得る。
【００４９】
示されるように、モバイルデバイス１０６は、たとえば、ＳＰＳ受信機３１０を備えることができ、受信機３１０は、１つまたは複数の送信デバイス１３０によって送信されるいくつかの信号１３２に基づく位置特定および／または他のナビゲーションサービスを提供することができる。たとえば、ＳＰＳ受信機３１０は、１つまたは複数のＧＮＳＳまたは他の同様の衛星測位システムおよび／もしくは地上測位システムを受信し処理することが可能な、ＳＰＳ受信機を備え得る。ＳＰＳ受信機３１０は、様々な目的で、たとえば、モバイルデバイスの測位／ナビゲーションのために、かつ、たとえば、セルラーネットワーク、ＷｉＦｉネットワークなどによって少なくとも一部提供され得る１つまたは複数の位置情報サービス（ＬＢＳ）のようなＬＢＳのために、使用され得る。ＳＰＳ受信機３１０は、動作可能に位置情報を提供することができ、かつ／または、測位エンジン３１４とともに何らかの方式で別様に動作することができる。いくつかの事例では、測位エンジン３１４のすべてまたは一部が、ＳＰＳ受信機３１０によって提供され得る。
【００５０】
示されるように、モバイルデバイス１０６は、１つまたは複数のユーザインターフェース３１２を備え得る。たとえば、ユーザインターフェース３１２は、１つまたは複数のユーザ入力および／またはユーザ出力デバイスを表し得る。よって、たとえば、ユーザインターフェース３１２は、キーパッド、タッチスクリーン、様々なボタン、様々なインジケータ、ディスプレイスクリーン、スピーカ、マイクロフォン、プロジェクタ、カメラなどを備え得る。
【００５１】
モバイルデバイス１０６は、環境１００内で移動され得る任意の電子デバイスを表す。たとえば、モバイルデバイス１０６は、携帯電話、スマートフォン、ラップトップコンピュータ、タブレットコンピュータ、測位／ナビゲーションデバイスなどのような、ハンドヘルドコンピューティングデバイスおよび／または通信デバイスを備え得る。いくつかの例示的な実装形態では、モバイルデバイス１０６は、回路基板、電子チップなどの一部であってよい。
【００５２】
モバイルデバイス１０６は、１つまたは複数の他の機能または能力を実行する際に役立ち、かつ／または本明細書で提供されるいくつかの例示的技法を支援し得る、１つまたは複数の他の回路、機構など（図示せず）を、同様に、または代替的に備え得ることを理解されたい。
【００５３】
コンピューティングデバイス１０２および／またはモバイルデバイス１０６は、たとえば、（たとえば、１つまたは複数のネットワークインターフェース２０８、１つまたは複数のワイヤレスインターフェース３０８などを介して）ワイヤレスワイドエリアネットワーク（ＷＷＡＮ）、ワイヤレスローカルエリアネットワーク（ＷＬＡＮ）、ワイヤレスパーソナルエリアネットワーク（ＷＰＡＮ）などのような様々なワイヤレス通信ネットワークとともに使用することが可能であり得る。「ネットワーク」および「システム」という用語は、本明細書では互換的に使用されることがある。ＷＷＡＮは、符号分割多元接続（ＣＤＭＡ）ネットワーク、時分割多元接続（ＴＤＭＡ）ネットワーク、周波数分割多元接続（ＦＤＭＡ）ネットワーク、直交周波数分割多元接続（ＯＦＤＭＡ）ネットワーク、シングルキャリア周波数分割多元接続（ＳＣ−ＦＤＭＡ）ネットワークなどであってよい。ＣＤＭＡネットワークは、ほんのいくつかの無線技術を挙げれば、ｃｄｍａ２０００、広帯域ＣＤＭＡ（Ｗ−ＣＤＭＡ）、時分割同期符号分割多元接続（ＴＤ−ＳＣＤＭＡ）などの１つまたは複数の無線アクセス技術（ＲＡＴ）を実装し得る。この場合、ｃｄｍａ２０００は、ＩＳ−９５規格、ＩＳ−２０００規格、およびＩＳ−８５６規格に従って実装される技術を含み得る。ＴＤＭＡネットワークは、Ｇｌｏｂａｌ  Ｓｙｓｔｅｍ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ（ＧＳＭ）、Ｄｉｇｉｔａｌ  Ａｄｖａｎｃｅｄ  Ｍｏｂｉｌｅ  Ｐｈｏｎｅ  Ｓｙｓｔｅｍ（Ｄ−ＡＭＰＳ）、または何らかの他のＲＡＴを実装することができる。ＧＳＭおよびＷ−ＣＤＭＡは、「３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ  Ｐａｒｔｎｅｒｓｈｉｐ  Ｐｒｏｊｅｃｔ」（３ＧＰＰ）という名称の組織からの文書に記載されている。ｃｄｍａ２０００は、「３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ  Ｐａｒｔｎｅｒｓｈｉｐ  Ｐｒｏｊｅｃｔ  ２」（３ＧＰＰ２）という名称の組織からの文書に記載されている。３ＧＰＰおよび３ＧＰＰ２の文書は公に入手可能である。たとえば、ＷＬＡＮは、ＩＥＥＥ８０２．１１ｘネットワークを含んでよく、ＷＰＡＮは、Ｂｌｕｅｔｏｏｔｈネットワーク、ＩＥＥＥ８０２．１５ｘを含んでよい。ワイヤレス通信ネットワークは、たとえば、Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ（ＬＴＥ）、Ａｄｖａｎｃｅｄ  ＬＴＥ、ＷｉＭＡＸ（登録商標）、Ｕｌｔｒａ  Ｍｏｂｉｌｅ  Ｂｒｏａｄｂａｎｄ（ＵＭＢ）のような、いわゆる次世代技術（たとえば、「４Ｇ」）を含み得る。
【００５４】
屋内空間の符号化された地図は、たとえば、ＣＡＤまたは他の同様の図面またはファイルから導出され得る。よって、ＣＡＤ図面は、壁、出入口などによって形成される部屋および通路、および／または他の物体もしくは関心地点を示し得る。ＣＡＤ図面がデジタル地図として使用可能な特定のフォーマットに変換されると、デジタル地図は、上で論じられたように、様々なコンピューティングプラットフォームによるアクセスのために電子的に記憶され得る。
【００５５】
１つの特定の実装形態では、符号化された経路指定可能性グラフは、オフィスビル、ショッピングモール、校舎などのある階のような、ある屋内領域の地図によってカバーされる領域にわたって仮想的に投影され得る、点のグリッドのセットを備えてよく、または点のグリッドのセットに基づいてよい。次いで、障害物（たとえば、壁）を伴わない隣接する点の場所の間でのあり得る直接の転換を示すために、隣接する（隣の）グリッド点が、地図中の地物の影響を受けながらエッジによって選択的に接続され得る。よって、たとえば、相互接続されたグリッド点は、屋内領域中のモバイルデバイスの動きをモデル化する際に使用するための、符号化された経路指定可能性グラフ中の「ノード」を形成し得る。ノードの１つまたは複数は、たとえば、分岐点を表してよく、または分岐点によって表されてよい。
【００５６】
特定の実装形態では、モバイルデバイスの場所は、上で説明された符号化された経路指定可能性グラフ中の隣接するノードを接続するエッジに沿った点に位置するものとして、モデル化され得る。同様に、最初の位置から後続の位置への転換は、符号化された経路指定可能性グラフのエッジに沿って起きるようにモデル化され得る。加えて、可能性モデルがさらに、ある期間にわたる、最初の位置から後続の位置へのモバイルデバイスのあり得る転換を特徴付けることができる。ある特定の例では、カルマンフィルタリングモデルまたは粒子フィルタリングモデルなどが、最初の場所、速度、および方向により決定される特定の後続の場所、速度、および方向をモバイルデバイスが有する可能性を、確立することができる。
【００５７】
十分な詳細度を実現するために、ある例示的な符号化された経路指定可能性グラフの表現では、グリッド点は、符号化された経路指定可能性グラフが特定の用途に対応するのに十分詳細であり得るように、屋内領域にわたって密に投影され得る。しかしながら、高密度のグリッド点に対して符号化された経路指定可能性グラフおよび／または転換確率を求めることは、計算量が多いことがある。同様に、モバイルアプリケーションを実行して経路指定、粒子フィルタリングなどを実行することで、モバイルデバイスの処理リソースは、詳細な進路を計算／評価すること、および／または、粒子フィルタリング技法を使用する大量の／高密度の粒子によって負荷がかけられ得る。したがって、たとえば、処理リソースに過剰な負荷をかけることなく、符号化された経路指定可能性グラフにおける十分な詳細度および／または粒子の密度を実現するように、符号化された経路指定可能性グラフ中のノードまたは分岐点の数を減らすことが有用であり得る。よって、いくつかの例示的な事例では、あり得る経路が、縮小された符号化された経路指定可能性グラフの表現を使用して決定され得る。
【００５８】
次に図４に対して参照が行われ、図４は、符号化された地図において見出され得るような様々な地物を図示する、ｖ字状のオフィスビル４００の平面図における縮小された分岐点のセットを示す説明のための図である。たとえば、ビル４００は、出入口を介して相互接続された複数のオフィス空間などを備える。
【００５９】
符号化された経路指定可能性グラフがさらに、平面図にわたって分散させられた複数のノード４０２によって、図４において示される。たとえば、ノード４０２−１およびノード４０２−２は、エッジ４０４によって相互接続されているものとして示される。理解され得るように、いくつかのノード（たとえば、ノード４０２−３）は１つのエッジを有し、このことはそのノードを終端ノードとするが、他のノード（たとえば、ノード４０２−１）は２つ以上のエッジを有し、このことはそのノードを非終端ノードとする。
【００６０】
ビル４００を通る、またはその中の移動の経路は、たとえば、適用可能なノードおよびエッジによって示される地点間接続のいくつかのサブセットを一般にたどり得る。理解され得るように、いくつかのノードまたは分岐点は、１つまたは複数の関心地点に関連し得る（たとえば、共設され得る、隣接し得る、近くにあり得るなど）。たとえば、休憩室または会議室、または場合によっては化粧室は、ユーザの関心の対象であり得るので、関心地点を表す。さらに、建物の入口および／または出口も、関心地点を表し得る。したがって、いくつかのあり得る経路は、１つまたは複数の特定の関心地点につながり得る。図４の例で示される符号化された経路指定可能性グラフは、ある実装形態による、符号化された経路指定可能性グラフの縮小されたバージョンを表すことに留意されたい。明らかに、他の符号化された経路指定可能性グラフが使用されてよく、たとえば、符号化された経路指定可能性グラフは、他のグリッド点に対して揃えられた追加のノードまたは分岐点などを含んでよい。さらに、ユーザは通常、ある関心点または他の行先へのより短い進路をとることに留意されたい。当然、一部のユーザは、道に迷い、または遠回りをすることがあり、これによりユーザは長い経路を選ぶことになる。本明細書で説明されるように、使用可能な経路のセットは、何らかの方式で、たとえば、関心地点、最短経路などを考慮して、あり得る経路のセットへと減らされ得る。したがって、ユーザが偶然最短経路を選ぶ場合、決定される転換の可能性は、ユーザの動きの追跡を支援している可能性のある測位エンジンにおいて有用であることがわかり得る。
【００６１】
図５は、ある例示的な実装形態による、互いに接続され、かつ複数の入口エッジと出口エッジに接続されるノードの形式の２つの分岐点（ｘおよびｙと名付けられる）を備える符号化された経路指定可能性グラフの部分５００を、それらの分岐点に対応する複数のあり得る経路とともに示す、説明のための図である。
【００６２】
示されるように、分岐点ｙおよびｘは、ｘｙと名付けられるエッジによって接続される。この例では、分岐点ｙから分岐点ｘへのエッジｘｙをたどるいくつかのあり得る経路が示され、エッジｘｙをたどらない１つの経路が示される。この例では、分岐点ｙはｙ１およびｙ２という２つのエッジを有し、ｙ１およびｙ２はそれぞれ、分岐点ｙおよび経路Ｐ１およびＰ２、ならびに分岐点ｙおよび経路Ｐ４およびＰ５に関して入口エッジとして動作する。この例では、分岐点ｘは、ｘ１、ｘ２、およびｘ３と名付けられる３つのエッジを有し、これらの各々が、例示的な経路の少なくとも１つに関する出口エッジを表す。たとえば、経路Ｐ１は、分岐点ｙへの入口エッジｙ１、分岐点ｘへのエッジｘｙをたどり、出口エッジｘ１を介して出る。例示的な経路Ｐ２は、分岐点ｙへの入口エッジｙ１、分岐点ｘへのエッジｘｙをたどり、出口エッジｘ２を介して出る。たとえば、経路Ｐ４は、２つの分岐点ｙへの入口エッジｙ２、分岐点ｘへのエッジｘｙをたどり、出口エッジｘ１を介して出る。例示的な経路Ｐ５は、分岐点ｙへの入口エッジｙ１、分岐点ｘへのエッジｘｙをたどり、出口エッジｘ３を介して出る。例示的な経路Ｐ３は、分岐点ｘへのエッジｘ２（入口エッジとしての）をたどり、出口エッジｘ３を介して分岐点ｘを出る。したがって、例示的な経路Ｐ３はエッジｘｙをたどらない。
【００６３】
いくつかの実装形態において言及されたように、あるエッジを通ってある行先へと流れるあり得る経路は、そのエッジを通って流れる符号化された経路指定可能性グラフの縮小されたバージョンにおけるノードの地点間接続の特定に基づいて、特定または決定され得る。いくつかの他の実装形態では、あるエッジを通って流れるあり得る経路は、符号化された地図によって表される屋内環境における特定の部屋または領域のような、関心地点（ＰＯＩ）の地点間接続に基づいて、特定または決定され得る。
【００６４】
ある分岐点からの方向およびユーザがたどり得る様々なあり得る経路について複数の選択肢が与えられる場合、方向の各々が同じ転換の可能性（たとえば、確率値）を有する可能性は低いことが理解されよう。したがって、符号化された地図の地物の分析において、各方向に対する演繹的な確率を決定することができる。そのような確率は、たとえば、各方向の行先に依存し得る。しかしながら、そのような方向的な確率は、微視的な規模（たとえば、符号化された接続グラフ）規模では適用可能ではないことがあり、方向的な確率は、１つまたは複数の行先へのあり得る経路が巨視的なグラフの一部である巨視的な規模（たとえば、符号化された経路指定可能性グラフ、符号化された経路指定可能性グラフの縮小されたバージョンなど）において適用可能であり得ることに、留意されたい。
【００６５】
本明細書で指摘されるように、方向的な確率は、ユーザの予想される次の大きな移動の行先についてのヒントを測位エンジンに与えるために使用され得る。たとえば、粒子フィルタなどを使用する測位エンジンを有するモバイルデバイスは、モバイルデバイスが巨視的な規模でどこに向かう可能性が高いかについての演繹的な確率値によって、より効率的に動作することができる。
【００６６】
いくつかの例示的な実装形態では、あるノードから別のノードへのある経路を流れに指定させることができ、重みを各ノードに与えることができ、各ノードは、その特定のノードから開始する流れとその特定のノードを通過する流れとを備え得る。したがって、たとえば、各ノードは、そのすべての隣接ノードからの入来する流れと、特定のノードにおいて開始する流れとを有する。そのような流れは、特定のノード自体において終端する、隣接するノードへの複数のエッジへと分割され得る。したがって、流れが分割される比率は、特定のノードからの出口エッジに関する経路の方向的確率値に対応し得る。
【００６７】
この例では、ＸＹを、分岐点ｘを通って流れる符号化された経路指定可能性グラフのノードからのすべての経路のセットを表すものとし、Ｘ１を、分岐点ｘを通って出口エッジｘ１へと流れるｘｙにおける経路のサブセットを表すものとし、Ｘ２を、分岐点ｘを通って出口エッジｘ２へと流れるｘｙにおける経路のサブセットを表すものとし、Ｘ３を、分岐点ｘを通って出口エッジｘ３へと流れるｘｙにおける経路のサブセットを表すものとする。以前に言及されたように、経路Ｐ３はｘｙを通って流れないことに留意されたい。
【００６８】
したがって、以下でさらに詳しく説明されるように、分岐点ｘを通る、入口エッジｘｙから出口エッジｘ１、ｘ２、およびｘ３への転換の１つまたは複数の可能性を表す１つまたは複数の値が、次のように（たとえば、確率値の形式で）推定され得る。
【数１】
2014530370.tif 000003
【００６９】
ここで、Ｎ（ξ）は、セットξの濃度（またはセットξ中の要素の数）を表す。
【００７０】
よって、たとえば、分岐点ｙから分岐点ｘにユーザが移動すると仮定すると、ユーザが分岐点ｘから出口エッジｘ１、ｘ２、およびｘ３へと出発する確率を計算することができる。そのような計算は、たとえば、これらのエッジの各々に対する転換の可能性を表す１つまたは複数の値をもたらし得る。たとえば、図５の部分５００では、エッジｘｙに４つの流れ（Ｐ１、Ｐ２、Ｐ４、Ｐ５）があり、それらの流れのうちの２つ（Ｐ１、Ｐ４）は出口エッジｘ１へと続き、それらの流れのうちの１つ（Ｐ２）は出口エッジｘ２へと続き、それらの流れのうちの１つ（Ｐ５）は出口エッジｘ３へと続く。したがって、たとえば、４つの流れのうちの２つの流れが出口エッジｘ１へと続くので、ユーザが分岐点ｘから出口エッジｘ１へと出発する確率は５０％であり得る。４つの流れのうちの１つの流れが出口エッジｘ２へと続くので、ユーザが分岐点ｘから出口エッジｘ２へと出発する確率は２５％であり得る。４つの流れのうちの１つの流れが出口エッジｘ３へと続くので、ユーザが分岐点ｘから出口エッジｘ３へと出発する確率は２５％であり得る。やはり、そのような例示的な確率は、分岐点から離れる出口エッジを通るあり得る経路の数と、分岐点に向かう入口エッジを通るあり得る経路の数との比に基づいて決定され得る。以前に言及されたように、いくつかの事例では、転換の可能性を表す値は、たとえば、ノードまたは分岐点に割り当てられ得る重みの変化に影響を与えるために、追加されてよく、またはそうでなければ何らかの方法で使用されてよい。各経路（たとえば、Ｐ１、Ｐ２、Ｐ３）はまた、経路自体がどの程度頻繁に使用されるかを表す重みを有し得る。これらの重みは、たとえば、上で説明されたように転換確率を計算するために使用され得る。
【００７１】
加えて、いくつかの実装形態では、分岐点またはその近くにおいて、引き返すことまたは移動の方向を反転させることを決めるユーザに対する転換の可能性を表す値を含むことが、有益であり得る。よって、たとえば、いくつかの事例では、ノミナル値（たとえば、所定の値、動的に決定される値など）が、そのような可能性を表すために使用され得る。よって、これまでの例では、５％という引き返しの確率を割り当てることが有益であることがあり、このことは、他の確率をそれに対応するようにわずかに下げ得る。
【００７２】
いくつかの例示的な実装形態では、符号化された経路指定可能性グラフに関してあり得る経路を決定するために、様々な方法が使用され得る。たとえば、いくつかの実装形態では、ＡＰＳＰアルゴリズムなどが、符号化された経路指定可能性グラフの縮小されたバージョンにおいて各ノードから実行され得る。各ＡＰＳＰの後、ＳＰ中の各エッジｘｙに対して、たとえば、カウンタｘｙをインクリメントし、たとえば経路の源に応じてカウンタｙ１、ｙ２の１つをインクリメントし、たとえば経路の行先に応じてカウンタｘ１、ｘ２、ｘ３の１つをインクリメントすることができる。
【００７３】
いくつかの例示的な実装形態では、符号化された経路指定可能性グラフの縮小されたバージョン中の各ノードまたは分岐点は、各ノードまたは分岐点に吸収された、符号化された経路指定可能性グラフのグリッド点もしくはノードの数を表す、および／または、各ノードまたは分岐点が別様に表す、対応する重みｗを有し得る。ここで、たとえば、ノードまたは分岐点の重みｗに少なくとも一部基づいて、カウンタがインクリメントされてよく、またはそうでなければ何らかの方式で影響を受けてよい。
【００７４】
次に図６が注目され、図６は、ある実装形態による、符号化された経路指定可能性グラフの表現に対する転換の１つまたは複数の可能性を表す１つまたは複数の値を生成するための、１つまたは複数のコンピューティングプラットフォームによって全体または一部が実施され得る、例示的な処理または方法を示す流れ図である。
【００７５】
例示的なブロック６０２において、符号化された経路指定可能性グラフの表現が取得され得る。たとえば、符号化された経路指定可能性グラフの表現は、１つまたは複数の他のデバイス１２０（図１）から取得されてよく、かつ／または、既知の技法を使用して別様に決定されてよい。いくつかの事例では、符号化された経路指定可能性グラフの表現は、符号化された経路指定可能性グラフの縮小されたバージョンを備え得る。符号化された経路指定可能性グラフの表現は、たとえば、屋内空間を備える構造物のすべてまたは一部に対する、符号化された地図のすべてまたは一部に関し得る。以前に言及されたように、符号化された経路指定可能性グラフの表現は、エッジによって何らかの方式で相互接続される、複数の分岐点を規定し得る。加えて、分岐点の１つまたは複数は、符号化された経路指定可能性グラフの表現に含まれ得る、または別様に導出され得る、１つまたは複数の特定の地物、関心点などに対応し得る。本明細書で使用される場合、簡潔にするために、「符号化された経路指定可能性グラフの表現」という句は、単に、符号化された経路指定可能性グラフおよび／または符号化された経路指定可能性グラフの縮小されたバージョンと呼ばれ得る。また、ノードおよび分岐点という用語は互換的に使用されることがある。
【００７６】
例示的なブロック６０４において、転換の１つまたは複数の可能性を表す１つまたは複数の値は、符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、分岐点からの個々の出口エッジに割り当てられ得る。いくつかの例示的な実装形態では、符号化された経路指定可能性グラフ中のあり得る経路は、たとえば、ブロック６０６において決定され得る。ブロック６０８において、転換の１つまたは複数の可能性を表す１つまたは複数の値は、あり得る出発側経路および／またはあり得る行先側経路に少なくとも一部基づいて割り当てられ得る。ブロック６１０において、転換の１つまたは複数の可能性を表す１つまたは複数の値は、分岐点から離れるあり得る経路の数と、分岐点に向かうあり得る経路の数の比に少なくとも一部基づき得る。
【００７７】
例示的なブロック６１２において、いくつかの事例では、転換の１つまたは複数の可能性を表す１つまたは複数の値は、１つまたは複数のモバイルデバイスに送信され、または別様に提供され得る。ここで、たとえば、コンピューティングデバイス１０２は、ブロック６１２において示されるように、転換の１つまたは複数の可能性を表す１つまたは複数の値を、ネットワーク１１０（図１）を介してモバイルデバイス１０６に送信することができる。
【００７８】
例示的なブロック６１４において、モバイルデバイスは、１つまたは複数の機能において、転換の１つまたは複数の可能性を表す１つまたは複数の値を使用し得る。たとえば、モバイルデバイスは、測位エンジンまたは他の同様の測位機能もしくはナビゲーション機能において、転換の１つまたは複数の可能性を表す１つまたは複数の値を使用することができる。たとえば、いくつかの実装形態では、測位エンジンは、粒子フィルタなどを備えてよく、粒子フィルタなどは、転換の１つまたは複数の可能性を表す１つまたは複数の値を使用して、あり得る経路、符号化された経路指定可能性グラフ、関心地点、および／または符号化された地図の他の地物に関して、ユーザの移動の方向および／または可能性のある行先を予測すること、または別様に推定することを場合によっては助けることができる。
【００７９】
１つまたは複数の演繹的な方向的確率値の知識を有するモバイルデバイスが性能を改善できることを、本明細書で提供された例から認識されたい。さらに、本明細書の例の一部において指摘されたように、ユーザは、符号化された経路指定可能性グラフ中のノードからノードに単に移動するのではないことがあり、むしろ、ユーザは、経路上を、符号化された地図および／もしくは他の同様の符号化されたファイルから前もって特定され得るいくつかの関心地点および／もしくは他の同様の地物へと、かつ／またはそれらから、移動する傾向がある。そのような地物および／または関心地点の間の最短経路を、符号化された経路指定可能性グラフを使用して考えることによって、転換の可能性を決定し、移動の方向および／または何らかの行先を推定する際に考慮するために、そのような情報を測位エンジンに提供することができる。よって、たとえば、関心地点のセットおよび／または関心地点の様々な分類と、符号化された経路指定可能性グラフ中の関心地点の場所とを定義することができ、１つまたは複数の関心地点へと、またはそれからつながる、そのような経路指定可能性グラフ上のあり得る（たとえば、最短の）経路を考えることができる。たとえば、あり得る経路は、オフィスから出口、または会議室から化粧室などに延び得る。言及されたように、いくつかの事例では、そのようなノードまたは分岐点、および／またはエッジに対して重み値を割り当てることが有益であることがあり、重み値は次いで、転換の可能性を表す値を表すことができ、またはその値を決定するために使用され得る。たとえば、重み値は、たとえば以前に示されたように、方向的確率値を計算するために使用され得る。他の重みがある事例において符号化された経路指定可能性グラフ中で使用される場合、本技法の重み値を他の重みと組み合わせて、所与のノードまたは分岐点に対する転換の可能性をさらに推定することが可能であり得る。たとえば、ノードまたは分岐点が、それが表すノードまたはグリッド点の数を示す重みｗを有する場合、転換の可能性の計算に関連する対応する重み値とともに重みｗを組み合わせること、または別様に考慮することが可能であり有益であり得る。
【００８０】
本明細書全体にわたる「一例」、「例」、「いくつかの例」、または「例示的な実装形態」という言及は、特徴および／または例に関して説明する特定の特徴、構造、または特性が、特許請求される主題の少なくとも１つの特徴および／または例の中に含まれ得ることを意味する。したがって、本明細書全体にわたる様々な場所における「一例では」、「例」、「いくつかの例では」または「いくつかの実装形態では」という句、または他の同様の句の出現は、必ずしもすべてが同じ特徴、例、および／または限定を指すとは限らない。さらに、それらの特定の特徴、構造、または特性は、１つまたは複数の例および／または特徴へと組み合わされ得る。
【００８１】
本明細書で説明された方法は、特定の特徴および／または例に従って適用例に応じて様々な手段によって実装され得る。たとえば、そのような方法は、ソフトウェアとともにハードウェア、ファームウェア、および／またはそれらの組合せで実装され得る。ハードウェア実装の場合、たとえば、処理ユニットは、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）、デジタル信号プロセッサ（ＤＳＰ）、デジタル信号処理デバイス（ＤＳＰＤ）、プログラマブル論理デバイス（ＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、本明細書で説明する機能を実施するように設計された他のデバイスユニット、および／またはそれらの組合せの中で実装され得る。
【００８２】
上記の詳細な説明では、特許請求される主題の完全な理解を与えるために多数の具体的な詳細が記載された。しかしながら、特許請求される主題は、これらの具体的な詳細を伴わずに実施され得ることが当業者には理解されよう。他の事例では、特許請求される主題を不明瞭にしないように、当業者には既知であろう方法および装置は詳細には説明されていない。
【００８３】
上記の詳細な説明のいくつかの部分は、特定の装置または専用コンピューティングデバイスまたはプラットフォームのメモリ内に記憶された２値デジタル電子信号の演算のアルゴリズムまたは記号表現に関して提示された。この特定の明細書の文脈では、特定の装置などの用語は、プログラムソフトウェアからの命令に従って特定の機能を実施するようにプログラムされた後の汎用コンピュータを含む。アルゴリズムの説明または記号表現は、信号処理または関連技術において、自身の仕事の本質を他の当業者に伝達するために当業者により使用される技法の例である。アルゴリズムは、本明細書では、また一般に、所望の結果をもたらす自己無撞着な一連の演算または同様の信号処理であると考えられる。この文脈では、演算または処理は物理量の物理操作に関係する。必ずしもそうとは限らないが、一般に、電子信号は情報を表すので（たとえば、表現データとして）、そのような量は、記憶され、転送され、組み合わされ、比較され、または別様に操作されることが可能な、電気信号または磁気信号の形式をとり得る。主に一般的に使用されているという理由で、そのような信号をビット、データ、値、要素、記号、文字、項、数、数字、情報などと呼ぶことは時々便利であることがわかっている。しかしながら、これらおよび同様の用語はすべて、適切な物理量と関連付けられるべきものであり、便宜的なラベルにすぎないことを理解されたい。別段に明記されていない限り、以下の説明から明らかなように、本明細書全体にわたって、「処理する」、「算出する」、「計算する」、「判定する」、「確立する」、「取得する」、「識別する」などの用語を利用する説明は、専用コンピュータまたは同様の専用電子コンピューティングデバイスのような、特定の装置の動作または処理を指すことを理解されたい。したがって、本明細書の文脈では、専用コンピュータまたは同様の専用電子コンピューティングデバイスは、専用コンピュータもしくは同様の専用電子コンピューティングデバイスのメモリ、レジスタもしくは他の情報記憶デバイス、送信デバイス、またはディスプレイデバイス内の電子的な物理量もしくは磁気的な物理量として一般に表される信号を、操作または変換することが可能である。この特定の特許出願の文脈では、「特定の装置」という用語は、プログラムソフトウェアからの命令に従って特定の関数を実行するようにプログラムされた汎用コンピュータを含み得る。
【００８４】
本明細書で使用される「および」、「または」、および「および／または」という用語は、そのような用語が使用される文脈に少なくとも部分的に依存することも予想される様々な意味を含み得る。一般に、「または」がＡ、ＢまたはＣなどの列挙を関連付けるために使用された場合、包含的な意味で使用された場合はＡ、Ｂ、およびＣを意味し、排他的な意味で使用された場合はＡ、ＢまたはＣを意味するものとする。加えて、本明細書で使用される「１つまたは複数」という用語は、単数形の任意の特徴、構造、または特性などを説明するために使用され得るか、または、複数の特徴、構造、または特性、または特徴、構造、または特性の何らかの他の組合せを説明するために使用され得る。しかし、これは例示的な例にすぎないこと、および特許請求される主題がこの例に限定されないことに留意されたい。
【００８５】
現在例示的な特徴と考えられていることが例示され説明されたが、特許請求される主題から逸脱することなく、他の様々な変更が行されてよく、等価物が置換されてよいことが、当業者には理解されよう。さらに、本明細書で説明された中心概念から逸脱することなく、特許請求される主題の教示に特定の状況を適合させるために多くの変更が行われ得る。
【００８６】
したがって、特許請求される主題は、開示された特定の例に限定されず、そのような特許請求される主題は、添付の特許請求の範囲の中に入るすべての態様、およびその等価物も含み得るものとする。
【図１】
2014530370.tif 000004
【図２】
2014530370.tif 000005
【図３】
2014530370.tif 000006
【図４】
2014530370.tif 000007
【図５】
2014530370.tif 000008
【図６】
2014530370.tif 000009
【手続補正書】
【提出日】平成26年5月30日(2014.5.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピューティングプラットフォームによって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得することと、
前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てることとを備える方法であって、前記割り当てることが、
（ｉ）前記符号化された地図の１つまたは複数の地物と、
（ｉｉ）前記分岐点に向かう前記入口エッジを通る、前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路の数と、
（ｉｉｉ）前記分岐点から離れる前記個々の出口エッジを通る、前記分岐点に接続されるあり得る行先側経路の数とに少なくとも一部基づく、方法。
【請求項２】
前記コンピューティングプラットフォームによって、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の前記数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の前記数との比に少なくとも一部基づいて、転換の前記可能性を決定することをさらに備える、請求項１に記載の方法。
【請求項３】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項１に記載の方法。
【請求項４】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項３に記載の方法。
【請求項５】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項１に記載の方法。
【請求項６】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項５に記載の方法。
【請求項７】
前記コンピューティングプラットフォームによって、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えることをさらに備える、請求項１に記載の方法。
【請求項８】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項１に記載の方法。
【請求項９】
前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、請求項８に記載の方法。
【請求項１０】
前記コンピューティングプラットフォームによって、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定することをさらに備える、請求項１に記載の方法。
【請求項１１】
転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、請求項１に記載の方法。
【請求項１２】
前記演繹的な方向確率値が、前記符号化された経路指定可能性グラフに関する前記モバイルデバイスの配置に関して可能性のある行先を推定するための、モバイルデバイス中の測位エンジンによる使用のために設定される、請求項１１に記載の方法。
【請求項１３】
前記コンピューティングプラットフォームによって、
転換の前記可能性の少なくとも１つを少なくとも１つのモバイルデバイスに提供することをさらに備える、請求項１に記載の方法。
【請求項１４】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項１に記載の方法。
【請求項１５】
コンピューティングプラットフォームにおいて使用するための装置であって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得するための手段と、
前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための手段とを備え、前記割り当てることが、
（ｉ）前記符号化された地図の１つまたは複数の地物と、
（ｉｉ）前記分岐点に向かう前記入口エッジを通る、前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路の数と、
（ｉｉｉ）前記分岐点から離れる前記個々の出口エッジを通る、前記分岐点に接続されるあり得る行先側経路の数とに少なくとも一部基づく、装置。
【請求項１６】
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の前記数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の前記数との比に少なくとも一部基づいて、転換の前記可能性を決定するための手段をさらに備える、請求項１５に記載の装置。
【請求項１７】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項１５に記載の装置。
【請求項１８】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項１７に記載の装置。
【請求項１９】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項１５に記載の装置。
【請求項２０】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項１９に記載の装置。
【請求項２１】
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるための手段をさらに備える、請求項１５に記載の装置。
【請求項２２】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項１５に記載の装置。
【請求項２３】
前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するための手段をさらに備える、請求項１５に記載の装置。
【請求項２４】
転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、請求項１５に記載の装置。
【請求項２５】
少なくとも転換の前記可能性を少なくとも１つのモバイルデバイスに提供するための手段をさらに備える、請求項１５に記載の装置。
【請求項２６】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項１５に記載の装置。
【請求項２７】
メモリと、
１つまたは複数の処理ユニットとを備え、前記１つまたは複数の処理ユニットが、
前記メモリから、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、
前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるためのものであり、前記割り当てることが、
（ｉ）前記符号化された地図の１つまたは複数の地物と、
（ｉｉ）前記分岐点に向かう前記入口エッジを通る、前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路の数と、
（ｉｉｉ）前記分岐点から離れる前記個々の出口エッジを通る、前記分岐点に接続されるあり得る行先側経路の数とに少なくとも一部基づく、コンピューティングプラットフォーム。
【請求項２８】
前記１つまたは複数の処理ユニットがさらに、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の前記数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の前記数との比に少なくとも一部基づいて、転換の前記可能性を決定するためのものである、請求項２７に記載のコンピューティングプラットフォーム。
【請求項２９】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３０】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項２９に記載のコンピューティングプラットフォーム。
【請求項３１】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３２】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項３１に記載のコンピューティングプラットフォーム。
【請求項３３】
前記１つまたは複数の処理ユニットがさらに、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるためのものである、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３４】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３５】
前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、請求項３４に記載のコンピューティングプラットフォーム。
【請求項３６】
前記１つまたは複数の処理ユニットがさらに、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するためのものである、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３７】
転換の前記可能性が演繹的な方向確率値を備える、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３８】
ネットワークインターフェースと、
前記１つまたは複数の処理ユニットとをさらに備え、前記１つまたは複数の処理ユニットがさらに、
転換の前記可能性の少なくとも１つの、少なくとも１つのモバイルデバイスへの送信を開始するためのものである、請求項２７に記載のコンピューティングプラットフォーム。
【請求項３９】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項２７に記載のコンピューティングプラットフォーム。
【請求項４０】
コンピューティングプラットフォームにおいて使用するための物品であって、
コンピュータ実施可能命令を記憶した非一時的コンピュータ可読媒体を備え、前記コンピュータ実施可能命令が、１つまたは複数の処理ユニットによって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、
前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるように実行可能であり、前記割り当てることが、
（ｉ）前記符号化された地図の１つまたは複数の地物と、
（ｉｉ）前記分岐点に向かう前記入口エッジを通る、前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路の数と、
（ｉｉｉ）前記分岐点から離れる前記個々の出口エッジを通る、前記分岐点に接続されるあり得る行先側経路の数とに少なくとも一部基づく、物品。
【請求項４１】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の前記数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の前記数との比に少なくとも一部基づいて、転換の前記可能性を決定するように実行可能である、請求項４０に記載の物品。
【請求項４２】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、請求項４０に記載の物品。
【請求項４３】
前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、請求項４２に記載の物品。
【請求項４４】
前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、請求項４０に記載の物品。
【請求項４５】
前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、請求項４４に記載の物品。
【請求項４６】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるように実行可能である、請求項４０に記載の物品。
【請求項４７】
転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、請求項４０に記載の物品。
【請求項４８】
前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、請求項４７に記載の物品。
【請求項４９】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するように実行可能である、請求項４０に記載の物品。
【請求項５０】
転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、請求項４０に記載の物品。
【請求項５１】
前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
転換の前記可能性の少なくとも１つの、少なくとも１つのモバイルデバイスへの送信を開始するように実行可能である、請求項４０に記載の物品。
【請求項５２】
前記コンピューティングプラットフォームがモバイルデバイス内で提供される、請求項４０に記載の物品。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
したがって、特許請求される主題は、開示された特定の例に限定されず、そのような特許請求される主題は、添付の特許請求の範囲の中に入るすべての態様、およびその等価物も含み得るものとする。
以下、本願の出願当初の特許請求の範囲に記載の発明を付記する。  
［Ｃ１］  コンピューティングプラットフォームによって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得することと、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てることとを備える、方法。
［Ｃ２］  転換の前記可能性を割り当てることがさらに、
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てることを備える、［Ｃ１］に記載の方法。
［Ｃ３］  前記コンピューティングプラットフォームによって、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定することをさらに備える、［Ｃ２］に記載の方法。
［Ｃ４］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、［Ｃ２］に記載の方法。
［Ｃ５］  前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、［Ｃ４］に記載の方法。
［Ｃ６］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、［Ｃ２］に記載の方法。
［Ｃ７］  前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、［Ｃ６］に記載の方法。
［Ｃ８］  前記コンピューティングプラットフォームによって、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えることをさらに備える、［Ｃ２］に記載の方法。
［Ｃ９］  転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、［Ｃ２］に記載の方法。
［Ｃ１０］  前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、［Ｃ９］に記載の方法。
［Ｃ１１］  前記コンピューティングプラットフォームによって、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定することをさらに備える、［Ｃ２］に記載の方法。
［Ｃ１２］  転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、［Ｃ１］に記載の方法。
［Ｃ１３］  前記演繹的な方向確率値が、前記符号化された経路指定可能性グラフに関する前記モバイルデバイスの配置に関して可能性のある行先を推定するための、モバイルデバイス中の測位エンジンによる使用のために設定される、［Ｃ１２］に記載の方法。
［Ｃ１４］  前記コンピューティングプラットフォームによって、
転換の前記可能性の少なくとも１つを少なくとも１つのモバイルデバイスに提供することをさらに備える、［Ｃ１］に記載の方法。
［Ｃ１５］  前記コンピューティングプラットフォームがモバイルデバイス内で提供される、［Ｃ１］に記載の方法。
［Ｃ１６］  コンピューティングプラットフォームにおいて使用するための装置であって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得するための手段と、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるための手段とを備える、装置。
［Ｃ１７］  前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てるための手段をさらに備える、［Ｃ１６］に記載の装置。
［Ｃ１８］  前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定するための手段をさらに備える、［Ｃ１７］に記載の装置。
［Ｃ１９］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、［Ｃ１７］に記載の装置。
［Ｃ２０］  前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、［Ｃ１９］に記載の装置。
［Ｃ２１］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、［Ｃ１７］に記載の装置。
［Ｃ２２］  前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、［Ｃ２１］に記載の装置。
［Ｃ２３］  前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるための手段をさらに備える、［Ｃ１７］に記載の装置。
［Ｃ２４］  転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、［Ｃ１７］に記載の装置。
［Ｃ２５］  前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するための手段をさらに備える、［Ｃ１７］に記載の装置。
［Ｃ２６］  転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、［Ｃ１６］に記載の装置。
［Ｃ２７］  少なくとも転換の前記可能性を少なくとも１つのモバイルデバイスに提供するための手段をさらに備える、［Ｃ１６］に記載の装置。
［Ｃ２８］  前記コンピューティングプラットフォームがモバイルデバイス内で提供される、［Ｃ１６］に記載の装置。
［Ｃ２９］  メモリと、
１つまたは複数の処理ユニットとを備え、前記１つまたは複数の処理ユニットが、
前記メモリから、符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるためのものである、コンピューティングプラットフォーム。
［Ｃ３０］  前記１つまたは複数の処理ユニットがさらに、
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てるためのものである、［Ｃ２９］に記載のコンピューティングプラットフォーム。
［Ｃ３１］  前記１つまたは複数の処理ユニットがさらに、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定するためのものである、［Ｃ３０］に記載のコンピューティングプラットフォーム。
［Ｃ３２］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、［Ｃ３０］に記載のコンピューティングプラットフォーム。
［Ｃ３３］  前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、［Ｃ３２］に記載のコンピューティングプラットフォーム。
［Ｃ３４］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、［Ｃ３０］に記載のコンピューティングプラットフォーム。
［Ｃ３５］  前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、［Ｃ３４］に記載のコンピューティングプラットフォーム。
［Ｃ３６］  前記１つまたは複数の処理ユニットがさらに、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるためのものである、［Ｃ３０］に記載のコンピューティングプラットフォーム。
［Ｃ３７］  転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、［Ｃ３０］に記載のコンピューティングプラットフォーム。
［Ｃ３８］  前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、［Ｃ３７］に記載のコンピューティングプラットフォーム。
［Ｃ３９］  前記１つまたは複数の処理ユニットがさらに、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するためのものである、［Ｃ３０］に記載のコンピューティングプラットフォーム。
［Ｃ４０］  転換の前記可能性が演繹的な方向確率値を備える、［Ｃ２９に記載のコンピューティングプラットフォーム。
［Ｃ４１］  ネットワークインターフェースと、
前記１つまたは複数の処理ユニットとをさらに備え、前記１つまたは複数の処理ユニットがさらに、
転換の前記可能性の少なくとも１つの、少なくとも１つのモバイルデバイスへの送信を開始するためのものである、［Ｃ２９］に記載のコンピューティングプラットフォーム。
［Ｃ４２］  前記コンピューティングプラットフォームがモバイルデバイス内で提供される、［Ｃ２９］に記載のコンピューティングプラットフォーム。
［Ｃ４３］  コンピューティングプラットフォームにおいて使用するための物品であって、
コンピュータ実施可能命令を記憶した非一時的コンピュータ可読媒体を備え、前記コンピュータ実施可能命令が、１つまたは複数の処理ユニットによって、
符号化された地図によって表される屋内環境中の使用可能な経路を表す符号化された経路指定可能性グラフを取得し、
前記符号化された地図の１つまたは複数の地物に少なくとも一部基づいて、前記符号化された経路指定可能性グラフ中の入口エッジから個々の出口エッジへの、前記入口エッジを複数の出口エッジに接続する分岐点を通る転換の可能性を割り当てるように実行可能である、物品。
［Ｃ４４］  前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記入口エッジを通り前記分岐点に接続される前記符号化された経路指定可能性グラフ中のあり得る出発側経路と、前記個々の出口エッジを通り前記分岐点に接続されるあり得る行先側経路とに少なくとも一部基づいて、転換の前記可能性を割り当てるように実行可能である、［Ｃ４３］に記載の物品。
［Ｃ４５］  前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記分岐点から離れる前記個々の出口エッジを通る前記あり得る行先側経路の数と、前記分岐点に向かう前記入口エッジを通る前記あり得る出発側経路の数との比に少なくとも一部基づいて、転換の前記可能性を決定するように実行可能である、［Ｃ４４］に記載の物品。
［Ｃ４６］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフの縮小されたバージョンにおけるノード間の地点間接続に少なくとも一部基づく、［Ｃ４４］に記載の物品。
［Ｃ４７］  前記符号化された経路指定可能性グラフの前記縮小されたバージョン中の前記ノードの少なくとも１つが、前記ノードの前記少なくとも１つによって表される符号化された接続グラフノードの数に少なくとも一部基づく重み値を割り当てられる、［Ｃ４６］に記載の物品。
［Ｃ４８］  前記あり得る出発側経路および前記あり得る行先側経路が、前記符号化された経路指定可能性グラフに沿った前記符号化された地図中の関心地点を表すノード間の地点間接続に少なくとも一部基づく、［Ｃ４４］に記載の物品。
［Ｃ４９］  前記関心地点の少なくとも１つを表す前記ノードの少なくとも１つが、前記関心地点の少なくとも別の１つを表す少なくとも１つの他のノードに関する重み値を割り当てられる、［Ｃ４８］に記載の物品。
［Ｃ５０］  前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
前記分岐点に対応する前記符号化された経路指定可能性グラフ中の少なくとも１つのノードに割り当てられる少なくとも１つの重み値に影響を与えるように実行可能である、［Ｃ４４］に記載の物品。
［Ｃ５１］  転換の前記可能性の少なくとも１つが、前記分岐点におけるあり得る引き返しの転換を表し、前記入口エッジが前記複数の出口エッジの１つをさらに表す、［Ｃ４４］に記載の物品。
［Ｃ５２］  前記あり得る引き返しの転換を表す転換の前記可能性の前記少なくとも１つが所定の値を備える、［Ｃ５１］に記載の物品。
［Ｃ５３］  前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
全対最短経路（ＡＰＳＰ）アルゴリズムを使用して、前記符号化された経路指定可能性グラフ中の前記あり得る出発側経路の少なくとも１つを決定するように実行可能である、［Ｃ４４］に記載の物品。
［Ｃ５４］  転換の前記可能性の少なくとも１つが演繹的な方向確率値を備える、［Ｃ４３］に記載の物品。
［Ｃ５５］  前記コンピュータ実施可能命令がさらに、前記１つまたは複数の処理ユニットによって、
転換の前記可能性の少なくとも１つの、少なくとも１つのモバイルデバイスへの送信を開始するように実行可能である、［Ｃ４３］に記載の物品。
［Ｃ５６］  前記コンピューティングプラットフォームがモバイルデバイス内で提供される、［Ｃ４３］に記載の物品。
【国際調査報告】
2014530370.tif 000010
2014530370.tif 000011
2014530370.tif 000012