JP6503474B2 - 移動デバイスの経路を求めるシステム及び方法 - Google Patents

Description

［関連出願の相互参照］
本出願は、２０１６年３月１４日に出願された中国特許出願第２０１６１０１４２８８０．５号の優先権を主張し、この出願の内容は、引用することによりその全体が本明細書の一部をなす。
（技術分野）
本開示は、包括的には、移動デバイスの位置情報を収集するシステム及び方法に関し、特に、移動車両の経路を求めるシステム及び方法に関する。

移動デバイスが道路又は街路に沿って移動しているとき、サーバーは、この移動デバイスの位置情報（例えば、ＧＰＳ情報）を収集することができる。サーバーは、地図データをデータベースからロードし、移動デバイスの位置情報を解析し、地図データに基づいて移動デバイスの経路を求めることができる。幾つかの状況において、地図データが入手不能であるとき、移動デバイスの経路を求めることが困難な場合がある。

本開示の一態様によれば、システムが、１つ以上の記憶媒体と、この１つ以上の記憶媒体と通信するように構成された１つ以上の処理部（プロセッサ）とを備えることができる。１つ以上の記憶媒体は、移動デバイスの経路を求める一組の命令を含むことができる。１つ以上の処理部が一組の命令を実行すると、複数の移動デバイスの各移動デバイスについて、１つ以上の処理部は、以下の動作のうちの１つ以上を実行するように指示されることができる。１つ以上の処理部は、移動デバイスに関する複数の位置点を取得することができる。１つ以上の処理部は、複数の位置点のうちの２つの間における移動デバイスの少なくとも１つの平均速度を求めることができる。１つ以上の処理部は、少なくとも１つの平均速度に基づいて、複数の位置点から少なくとも１つの干渉位置点を除去することができる。１つ以上の処理部は、少なくとも１つの平均速度に基づいて、複数の位置点の残余を一組の有効位置点として決定することができる。１つ以上の処理部は、一組の有効位置点に基づいて移動デバイスの経路を求めることができる。１つ以上の処理部は、移動デバイスの経路のデータを１つ以上の記憶媒体に記憶することができる。

幾つかの実施の形態では、１つ以上の処理部は、複数の位置点が位置する領域を特定することができる。１つ以上の処理部は、地図データが領域に利用不能な場合があると判断することができる。

幾つかの実施の形態では、１つ以上の処理部は、複数の移動デバイスに対応する求められた経路に基づいて地図を構築することができる。

幾つかの実施の形態では、１つ以上の処理部は、複数の位置点から第１の点、第２の点、及び第３の点を選択することができる。１つ以上の処理部は、第１の点、第２の点、及び第３の点のうちのいずれか２つの間における移動デバイスの３つの平均速度を求めることができる。

幾つかの実施の形態では、１つ以上の処理部は、移動デバイスの基準速度を求めることができる。１つ以上の処理部は、３つの平均速度と基準速度との比較を行うことができる。１つ以上の処理部は、干渉位置点が第１の点、第２の点、及び第３の点から出現しているか否かを比較に基づいて判断することができる。１つ以上の処理部は、干渉位置点が出現しているとき、干渉位置点を除去することができる。１つ以上の処理部は、第１の位置点、第２の位置点、及び第３の位置点の残余から少なくとも１つの有効位置点を求めることができる。

幾つかの実施の形態では、基準速度は、少なくとも１つの平均速度のうちの最大のものとすることができる。

幾つかの実施の形態では、１つ以上の処理部は、一組の有効位置点から第１の有効位置点、第２の有効位置点、及び第３の有効位置点を選択することができる。１つ以上の処理部は、第１の有効位置点、第２の有効位置点、及び第３の有効位置点に基づいて第１のラインを求めることができる。１つ以上の処理部は、第１のラインに基づいて移動デバイスの経路を求めることができる。

幾つかの実施の形態では、１つ以上の処理部は、一組の有効位置点から第４の有効位置点を選択することができる。１つ以上の処理部は、第４の有効位置点に対応する、第１のライン上の点を求めることができる。１つ以上の処理部は、第４の有効位置点と対応する点との間の距離を求めることができる。１つ以上の処理部は、距離が閾値未満の場合があると判断することができる。１つ以上の処理部は、対応する点に基づいて第１のラインを更新することができる。１つ以上の処理部は、更新された第１のラインに基づいて移動デバイスの経路を求めることができる。

幾つかの実施の形態では、１つ以上の処理部は、距離が閾値よりも大きい場合があると判断することができる。１つ以上の処理部は、第４の有効位置点を経路の方向転換点と判断することができる。

幾つかの実施の形態では、１つ以上の処理部は、第１のライン及び方向転換点に基づいて移動デバイスの経路を更新することができる。

幾つかの実施の形態では、１つ以上の処理部は、第５の有効位置点及び第６の有効位置点を選択することができる。１つ以上の処理部は、方向転換点、第５の有効位置点、及び第６の有効位置点に基づいて第２のラインを求めることができる。１つ以上の処理部は、第１のライン及び第２のラインに基づいて移動デバイスの経路を更新することができる。

本開示の別の態様によれば、方法が、以下の動作のうちの１つ以上を含むことができる。コンピューターサーバーは、移動デバイスに関する複数の位置点を取得することができる。コンピューターサーバーは、複数の位置点のうちの２つの間における移動デバイスの少なくとも１つの平均速度を求めることができる。コンピューターサーバーは、少なくとも１つの平均速度に基づいて、複数の位置点から少なくとも１つの干渉位置点を除去することができる。コンピューターサーバーは、少なくとも１つの平均速度に基づいて、複数の位置点の残余を一組の有効位置点として決定することができる。コンピューターサーバーは、一組の有効位置点に基づいて移動デバイスの経路を求めることができる。コンピューターサーバーは、移動デバイスの経路のデータを１つ以上の記憶媒体に記憶することができる。

幾つかの実施の形態では、コンピューターサーバーは、複数の位置点が位置する領域を特定することができる。コンピューターサーバーは、地図データが領域に利用不能な場合があると判断することができる。

幾つかの実施の形態では、コンピューターサーバーは、複数の移動デバイスに対応する求められた経路に基づいて地図を構築することができる。

幾つかの実施の形態では、コンピューターサーバーは、複数の位置点から第１の点、第２の点、及び第３の点を選択することができる。コンピューターサーバーは、第１の点、第２の点、及び第３の点のうちのいずれか２つの間における移動デバイスの３つの平均速度を求めることができる。

幾つかの実施の形態では、コンピューターサーバーは、移動デバイスの基準速度を求めることができる。コンピューターサーバーは、３つの平均速度と基準速度との比較を行うことができる。コンピューターサーバーは、干渉位置点が第１の点、第２の点、及び第３の点から出現しているか否かを比較に基づいて判断することができる。コンピューターサーバーは、干渉位置点が出現しているとき、干渉位置点を除去することができる。コンピューターサーバーは、第１の位置点、第２の位置点、及び第３の位置点の残余から少なくとも１つの有効位置点を求めることができる。

幾つかの実施の形態では、基準速度は、少なくとも１つの平均速度のうちの最大のものとすることができる。

幾つかの実施の形態では、コンピューターサーバーは、一組の有効位置点から第１の有効位置点、第２の有効位置点、及び第３の有効位置点を選択することができる。コンピューターサーバーは、第１の有効位置点、第２の有効位置点、及び第３の有効位置点に基づいて第１のラインを求めることができる。コンピューターサーバーは、第１のラインに基づいて移動デバイスの経路を求めることができる。

幾つかの実施の形態では、コンピューターサーバーは、一組の有効位置点から第４の有効位置点を選択することができる。コンピューターサーバーは、第４の有効位置点に対応する、第１のライン上の点を求めることができる。コンピューターサーバーは、第４の有効位置点と対応する点との間の距離を求めることができる。コンピューターサーバーは、距離が閾値未満の場合があると判断することができる。コンピューターサーバーは、対応する点に基づいて第１のラインを更新することができる。コンピューターサーバーは、更新された第１のラインに基づいて移動デバイスの経路を求めることができる。

幾つかの実施の形態では、コンピューターサーバーは、距離が閾値よりも大きい場合があると判断することができる。コンピューターサーバーは、第４の有効位置点を経路の方向転換点と判断することができる。

幾つかの実施の形態では、コンピューターサーバーは、第１のライン及び方向転換点に基づいて移動デバイスの経路を更新することができる。

幾つかの実施の形態では、コンピューターサーバーは、第５の有効位置点及び第６の有効位置点を選択することができる。コンピューターサーバーは、方向転換点、第５の有効位置点、及び第６の有効位置点に基づいて第２のラインを求めることができる。コンピューターサーバーは、第１のライン及び第２のラインに基づいて移動デバイスの経路を更新することができる。

追加の特徴は、以下の説明に一部が述べられ、以下の内容及び添付図面を検討することで当業者には部分的に明らかになるか、又はそれらの例の作成若しくは動作によって知得することができる。本開示の特徴は、以下で論述される詳細な例に述べられる方法論、手段及び組み合わせの様々な態様の実施又は使用によって実現及び達成することができる。

本開示を例示的な実施形態について更に説明する。これらの例示的な実施形態は、図面を参照して詳細に説明される。これらの実施形態は、非限定の例示的な実施形態であり、同様の参照符号は、図面の幾つかの図を通して同様の構造体を表している。

幾つかの実施形態に係る一例示的なオンデマンドサービスシステム１００のブロック図である。 本開示の幾つかの実施形態に係るオンデマンドサービスシステムにおける一例示的なコンピューティングデバイスを示すブロック図である。 本開示の幾つかの実施形態に係る一例示的な処理エンジンを示すブロック図である。 本開示の幾つかの実施形態に係る移動デバイスの経路を求める一例示的なプロセス／方法３００を示すフローチャートである。 本開示の幾つかの実施形態に係る一組の有効位置点を求める一例示的なプロセス／方法４００を示すフローチャートである。 本開示の幾つかの実施形態に係る移動デバイスの経路を求める一例示的なプロセス／方法５００を示すフローチャートである。 本開示の幾つかの実施形態に係る移動デバイスの経路を求める一例示的なプロセス／方法５００を示すフローチャートである。 本開示の幾つかの実施形態に係る方向転換点を求める一例示的なプロセス／方法を示す概略図である。 本開示の幾つかの実施形態に係る複数の位置点の一例示的な分布を示す概略図である。

以下の説明は、いずれの当業者も本開示内容を製造及び使用することができるように提示され、特定の用途及びその要件に関して提供されている。開示された実施形態に対する様々な変更は、当業者に容易に明らかであり、本明細書において規定される一般的な原理は、本開示の趣旨及び範囲から逸脱することなく他の実施形態及び用途に適用することができる。したがって、本開示は、提示された実施形態に限定されるものではなく、特許請求の範囲と一致した最も広い範囲を与えられることになる。

本明細書において用いられる術語は、特定の例示の実施形態を説明することのみを目的としており、限定することを意図するものではない。個数が特定されていないものが本明細書において用いられているとき、それらは、文脈が明らかに別のことを示していない限り、単数のもの及び複数のものを含む。「備える」及び／又は「含む」という用語は、本明細書において用いられるとき、明示された特徴、完全体、ステップ、動作、要素、及び／又は構成要素が存在することを明記しているが、１つ以上の他の特徴、完全体、ステップ、動作、要素、構成要素、及び／又はそれらの群が存在すること又は追加されることを排除するものではないことが更に理解されるであろう。

本開示のこれらの特徴及び特性並びに他の特徴及び特性、更には、構造の関連した要素及び部分の組み合わせの動作の方法及び機能並びに製造の経済性は、添付図面を参照しながら以下の説明を検討することでより明らかになり得る。添付図面の全ては、本開示の一部をなす。一方、これらの図面は、例示及び説明のみを目的としたものにすぎず、本開示の範囲を限定することを意図するものではないことが明らかに理解されるであろう。なお、図面は、一律の縮尺でないことが理解される。

本開示において用いられるフローチャートは、システムが本開示における幾つかの実施形態に従って実施する動作を示している。フローチャートの動作は、順序どおりに実施されない場合があることが明らかに理解されるであろう。逆に、それらの動作は、逆の順序で実施される場合もあるし、同時に実施される場合もある。その上、１つ以上の他の動作が、フローチャートに追加される場合がある。１つ以上の動作がフローチャートから除去される場合がある。

その上、本開示におけるシステム及び方法は、主として一組の共有可能なオーダーを配分することに関して説明されているが、これは１つの例示的な実施形態にすぎないことも理解されるべきである。本開示のシステム又は方法は、他の任意の種類のオンデマンドサービスに適用することができる。例えば、本開示のシステム又は方法は、陸上、海上、航空宇宙空間等、又はそれらの任意の組み合わせを含む種々の環境の輸送システムに適用することができる。輸送システムの車両は、タクシー、自家用車、ヒッチハイク、バス、列車、弾丸列車、高速鉄道、地下鉄、船舶、航空機、宇宙船、熱気球、無人車両等、又はそれらの任意の組み合わせを含むことができる。輸送システムは、管理及び／又は配送のための任意の輸送システム、例えば、速達便を送付及び／又は受領するシステムも含むことができる。本開示のシステム又は方法の用途は、ウェブページ、ブラウザのプラグイン、クライアント端末、カスタムシステム、内部解析システム、人工知能ロボット等、又はそれらの任意の組み合わせを含むことができる。

本開示における「乗客」、「要求者」、「サービス要求者」、及び「顧客」という用語は、サービスを要求又はオーダーすることができる個人、団体又はツールを指すために区別なく用いられる。また、本開示における「ドライバー」、「提供者」、「サービス提供者」、及び「供給者」という用語は、サービスを提供することができるか又はサービスの提供を容易にすることができる個人、団体又はツールを指すために区別なく用いられる。本開示における「ユーザー」という用語は、サービスを要求することができる個人、団体若しくはツール、サービスをオーダーすることができる個人、団体若しくはツール、サービスを提供することができる個人、団体若しくはツール、又はサービスの提供を容易にすることができる個人、団体若しくはツールを指すことができる。例えば、ユーザーは、乗客、ドライバー、オペレーター等、又はそれらの任意の組み合わせであってもよい。本開示において、「乗客」及び「乗客端末」は、区別なく用いられる場合があり、「ドライバー」及び「ドライバー端末」は、区別なく用いられる場合がある。

本開示における「サービス要求」及び「オーダー」という用語は、乗客、要求者、サービス要求者、顧客、ドライバー、提供者、サービス提供者、供給者等、又はそれらの任意の組み合わせが開始することができる要求を指すために区別なく用いられる。サービス要求は、乗客、要求者、サービス要求者、顧客、ドライバー、提供者、サービス提供者、又は供給者のうちの任意の者が受理することができる。サービス要求は、有料の場合もあるし、無料の場合もある。

本開示において用いられる測位技術は、全地球測位システム（ＧＰＳ）、全地球航法衛星システム（ＧＬＯＮＡＳＳ）、コンパスナビゲーションシステム（ＣＯＭＰＡＳＳ）、ガリレオ測位システム、準天頂衛星システム（ＱＺＳＳ）、ワイヤレスフィデリティー（ＷｉＦｉ）測位技術等、又はそれらの任意の組み合わせに基づくことができる。上記測位システムのうちの１つ以上は、本開示において区別なく用いられる場合がある。

本開示の一態様は、地図データなしで、及び／又は複数の移動デバイスの複数の経路に基づいて地図を構築することなく、移動デバイスの位置情報（例えば、ＧＰＳ点）に基づいて移動車両（例えば、車両、ユーザー端末）の経路を求めるシステム及び方法に関する。

当然ながら、ＧＰＳ測位は、全体がインターネットワールドに深く根差した技術である。地図を用いることなく車両の運転経路を求めることは、リアルタイムＧＰＳ測位、及び端末デバイスとリモートサーバーとの間のリアルタイム通信の実現性なくして可能ではない。したがって、本開示に開示された技術的解決策も、インターネット時代に深く根差した技術である。

このプラットフォーム又は処理エンジンのアプリケーションシナリオについて、このアプリケーションシナリオは、ユーザー端末（例えば、要求者端末又は提供者端末）及び車両（例えば、タクシー）を含むことができる。ユーザー端末又は車両が道路に沿って移動しているとき、プラットフォーム又は処理エンジンは、ユーザー端末又は車両の位置情報（例えば、ＧＰＳ情報）を取得することができる。例えば、ユーザーがタクシーを呼び止めると、プラットフォーム又は処理エンジンは、ユーザーの位置情報を取得し、この位置情報をタクシードライバーに提供することができる。プラットフォーム又は処理エンジンは、タクシードライバー（すなわち、提供者端末又は車両）の位置情報も取得し、タクシードライバーの移動経路を求めることもできる。

図１は、幾つかの実施形態に係る一例示的なオンデマンドサービスシステム１００のブロック図である。例えば、オンデマンドサービスシステム１００は、タクシー配車、運転代行サービス、急行貨物用貨車、カープール、バスサービス、ドライバーハイヤー及びシャトルサービス等の輸送サービスのためのオンライン輸送サービスプラットフォームとすることができる。オンデマンドサービスシステム１００は、サーバー１１０と、ネットワーク１２０と、要求者端末１３０と、提供者端末１４０と、データベース１５０とを備えるオンラインプラットフォームとすることができる。サーバー１１０は、処理エンジン１１２を備えることができる。

幾つかの実施形態では、サーバー１１０は、単一のサーバーであってもよいし、サーバーグループであってもよい。サーバーグループは、集中型であってもよいし、分散型であってもよい（例えば、サーバー１１０は分散型システムであってもよい）。幾つかの実施形態では、サーバー１１０は、ローカルであってもよいし、リモートであってもよい。例えば、サーバー１１０は、要求者端末１３０、提供者端末１４０、及び／又はデータベース１５０に記憶された情報及び／又はデータにネットワーク１２０を介してアクセスすることができる。別の例として、サーバー１１０は、要求者端末１３０、提供者端末１４０、及び／又はデータベース１５０に直接接続されて、記憶された情報及び／又はデータにアクセスすることができる。幾つかの実施形態では、サーバー１１０は、クラウドプラットフォーム上で実施されてもよい。単なる例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散型クラウド、インタークラウド、マルチクラウド等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、サーバー１１０は、本開示における図２に示す１つ以上の構成要素を有するコンピューティングデバイス２００上で実施されてもよい。

幾つかの実施形態では、サーバー１１０は、処理エンジン１１２を備えることができる。処理エンジン１１２は、サービス要求に関する情報及び／又はデータを処理して、本開示において説明する１つ以上の機能を実行することができる。例えば、処理エンジン１１２は、要求者端末１３０、提供者端末１０４、又はオンデマンドサービスシステム１００に関する車両の経路を求めることができる。幾つかの実施形態では、処理エンジン１１２は、１つ以上の処理エンジン（例えば、シングルコア処理エンジン（複数の場合もある）又はマルチコアプロセッサ（複数の場合もある））を含むことができる。単なる例として、処理エンジン１１２は、中央処理装置（ＣＰＵ）、特定用途向け集積回路（ＡＳＩＣ）、特定用途向け命令セットプロセッサ（ＡＳＩＰ）、グラフィックス処理装置（ＧＰＵ）、物理処理装置（ＰＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、プログラマブルロジックデバイス（ＰＬＤ）、コントローラー、マイクロコントローラーユニット、縮小命令セットコンピューター（ＲＩＳＣ）、マイクロプロセッサ等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、処理エンジン１１２は、要求者端末１３０又は提供者端末１４０に統合されてもよい。

ネットワーク１２０は、情報及び／又はデータの交換を容易にすることができる。幾つかの実施形態では、オンデマンドサービスシステム１００における１つ以上の構成要素（例えば、サーバー１１０、要求者端末１３０、提供者端末１４０、及びデータベース１５０）は、ネットワーク１２０を介してオンデマンドサービスシステム１００における他の構成要素（複数の場合もある）に情報及び／又はデータを送信することができる。例えば、サーバー１１０は、要求者端末１３０からネットワーク１２０を介してサービス要求を取得／入手することができる。幾つかの実施形態では、ネットワーク１２０は、任意のタイプの有線ネットワーク若しくは無線ネットワーク、又はそれらの組み合わせであってもよい。単なる例として、ネットワーク１３０は、ケーブルネットワーク、ワイヤーラインネットワーク、光ファイバーネットワーク、電気通信ネットワーク、イントラネット、インターネット、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、無線ローカルエリアネットワーク（ＷＬＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、公衆電話交換網（ＰＳＴＮ）、Ｂｌｕｅｔｏｏｔｈ（登録商標）ネットワーク、ＺｉｇＢｅｅ（登録商標）ネットワーク、近接場通信（ＮＦＣ）ネットワーク等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、ネットワーク１２０は、１つ以上のネットワークアクセスポイントを備えることができる。例えば、ネットワーク１２０は、基地局及び／又はインターネットエクスチェンジポイント１２０−１、１２０−２、．．．等の有線ネットワークアクセスポイント又は無線ネットワークアクセスポイントを備えることができ、これらのアクセスポイントを通じて、オンデマンドサービスシステム１００の１つ以上の構成要素は、ネットワーク１２０に接続されてデータ及び／又は情報を交換することができる。

幾つかの実施形態では、要求者は、要求者端末１３０のユーザーである場合がある。幾つかの実施形態では、要求者端末１３０のユーザーは、要求者以外の者である場合がある。例えば、要求者端末１３０のユーザーＡは、要求者端末１３０を用いて、ユーザーＢのサービス要求を送信することもできるし、サービス及び／又は情報若しくは命令をサーバー１１０から受信することもできる。幾つかの実施形態では、提供者は、提供者端末１４０のユーザーである場合がある。幾つかの実施形態では、提供者端末１４０のユーザーは、提供者以外の者である場合がある。例えば、提供者端末１４０のユーザーＣは、提供者端末１４０を用いて、ユーザーＤのサービス要求、及び／又は情報若しくは命令をサーバー１１０から受信することができる。幾つかの実施形態では、「要求者」及び「要求者端末」は、区別なく用いられる場合があり、「提供者」及び「提供者端末」は、区別なく用いられる場合がある。

幾つかの実施形態では、要求者端末１３０は、モバイルデバイス１３０−１、タブレットコンピューター１３０−２、ラップトップコンピューター１３０−３、自動車内の組み込みデバイス１３０−４等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、モバイルデバイス１３０−１は、スマートホームデバイス、ウェアラブルデバイス、スマートモバイルデバイス、仮想現実デバイス、拡張現実デバイス等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、スマートホームデバイスは、スマート照明デバイス、インテリジェント電気装置の制御デバイス、スマート監視デバイス、スマートテレビ、スマートビデオカメラ、インターフォン等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、ウェアラブルデバイスは、スマートブレスレット、スマートフットギア、スマートグラス、スマートヘルメット、スマートウォッチ、スマート衣服、スマートバックパック、スマートアクセサリー等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、スマートモバイルデバイスは、スマートフォン、パーソナルデジタルアシスタント（ＰＤＡ：携帯情報端末）、ゲーミングデバイス、ナビゲーションデバイス、販売時点（ＰＯＳ）デバイス等、又はそれらの任意の組み合わせを含むことができる。幾つかの実施形態では、仮想現実デバイス及び／又は拡張現実デバイスは、仮想現実ヘルメット、仮想現実グラス、仮想現実パッチ、拡張現実ヘルメット、拡張現実グラス、拡張現実パッチ等、又はそれらの任意の組み合わせを含むことができる。例えば、仮想現実デバイス及び／又は拡張現実デバイスは、Ｇｏｏｇｌｅ（登録商標） Ｇｌａｓｓ、Ｏｃｕｌｕｓ Ｒｉｆｔ（登録商標）、Ｈｏｌｏｌｅｎｓ、Ｇｅａｒ ＶＲ等を含むことができる。幾つかの実施形態では、自動車内の組み込みデバイス１３０−４は、オンボードコンピューター、オンボードテレビ等を含むことができる。幾つかの実施形態では、要求者端末１３０は、要求者及び／又は要求者端末１３０の場所を突き止める測位技術を有するデバイスであってもよい。

幾つかの実施形態では、提供者端末１４０は、要求者端末１３０と同様のものであってもよいし、同じデバイスであってもよい。幾つかの実施形態では、提供者端末１４０は、提供者及び／又は提供者端末１４０の場所を突き止める測位技術を有するデバイスであってもよい。幾つかの実施形態では、要求者端末１３０及び／又は提供者端末１４０は、他の測位デバイスと通信して、要求者、要求者端末１３０、提供者、及び／又は提供者端末１４０の場所を求めることができる。幾つかの実施形態では、要求者端末１３０及び／又は提供者端末１４０は、測位情報をサーバー１１０に送信することができる。

データベース１５０は、データ及び／又は命令を記憶することができる。幾つかの実施形態では、データベース１５０は、要求者端末１３０及び／又は提供者端末１４０から取得されたデータを記憶することができる。幾つかの実施形態では、データベース１５０は、サーバー１１０が、実行又は使用して、本開示において説明する例示的な方法を実行することができるデータ及び／又は命令を記憶することができる。幾つかの実施形態では、データベース１５０は、マスストレージ、リムーバブルストレージ、揮発性リードライトメモリ、リードオンリーメモリ（ＲＯＭ）等、又はそれらの任意の組み合わせを含むことができる。例示的なマスストレージは、磁気ディスク、光ディスク、ソリッドステートドライブ等を含むことができる。例示的なリムーバブルストレージは、フラッシュドライブ、フロッピーディスク、光ディスク、メモリカード、ｚｉｐディスク、磁気テープ等を含むことができる。例示的な揮発性リードライトメモリは、ランダムアクセスメモリ（ＲＡＭ）を含むことができる。例示的なＲＡＭは、ダイナミックＲＡＭ（ＤＲＡＭ）、ダブルデータレート同期ダイナミックＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、スタティックＲＡＭ（ＳＲＡＭ）、サイリスタＲＡＭ（Ｔ−ＲＡＭ）、及びゼロキャパシタＲＡＭ（Ｚ−ＲＡＭ）等を含むことができる。例示的なＲＯＭは、マスクＲＯＭ（ＭＲＯＭ）、プログラマブルＲＯＭ（ＰＲＯＭ）、消去可能プログラマブルＲＯＭ（ＰＥＲＯＭ）、電気的消去可能プログラマブルＲＯＭ（ＥＥＰＲＯＭ）、コンパクトディスクＲＯＭ（ＣＤ−ＲＯＭ）、及びデジタル多用途ディスクＲＯＭ等を含むことができる。幾つかの実施形態では、データベース１５０は、クラウドプラットフォーム上で実施されてもよい。単なる例として、クラウドプラットフォームは、プライベートクラウド、パブリッククラウド、ハイブリッドクラウド、コミュニティクラウド、分散型クラウド、インタークラウド、マルチクラウド等、又はそれらの任意の組み合わせを含むことができる。

幾つかの実施形態では、データベース１５０は、ネットワーク１２０に接続されて、オンデマンドサービスシステム１００における１つ以上の構成要素（例えば、サーバー１１０、要求者端末１３０、提供者端末１４０等）と通信することができる。オンデマンドサービスシステム１００における１つ以上の構成要素は、データベース１５０に記憶されたデータ又は命令にネットワーク１２０を介してアクセスすることができる。幾つかの実施形態では、データベース１５０は、オンデマンドサービスシステム１００における１つ以上の構成要素（例えば、サーバー１１０、要求者端末１３０、提供者端末１４０等）に直接接続することもできるし、これらの構成要素と通信することもできる。幾つかの実施形態では、データベース１５０は、サーバー１１０の一部分であってもよい。

幾つかの実施形態では、オンデマンドサービスシステム１００における１つ以上の構成要素（例えば、サーバー１１０、要求者端末１３０、提供者端末１４０等）は、データベース１５０にアクセスする許可を有することができる。幾つかの実施形態では、オンデマンドサービスシステム１００における１つ以上の構成要素は、１つ以上の条件が満たされたとき、要求者、提供者、及び／又は公衆に関する情報を読み出し及び／又は変更することができる。例えば、サーバー１１０は、サービス後に１人以上のユーザーの情報を読み出し及び／又は変更することができる。別の例として、提供者端末１４０は、要求者端末１３０からサービス要求を受信すると、要求者に関する情報にアクセスすることはできるが、提供者端末１４０は、要求者の関連情報を変更することはできない。

幾つかの実施形態では、オンデマンドサービスシステム１００における１つ以上の構成要素の情報交換は、サービスの要求を介して達成することができる。サービス要求の対象は、任意の商品（product：生産品）とすることができる。幾つかの実施形態では、この商品は、有形の商品であってもよいし、非物質的な商品であってもよい。有形の商品は、食料品、医薬品、日用品、化学製品、電気器具、衣料品、自動車、家屋物件、高級品等、又はそれらの任意の組み合わせを含むことができる。非物質的な商品は、サービス財、金融商品、知的産物、インターネット商品等、又はそれらの任意の組み合わせを含むことができる。インターネット商品は、個別ホスト商品、ウェブ商品、モバイルインターネット商品、商用ホスト商品、組み込み商品等、又はそれらの任意の組み合わせを含むことができる。モバイルインターネット商品は、モバイル端末のソフトウェア、プログラム又はシステム等、又はそれらの任意の組み合わせにおいて用いることができる。モバイル端末は、タブレットコンピューター、ラップトップコンピューター、モバイルフォン、パーソナルデジタルアシスタント（ＰＤＡ）、スマートウォッチ、販売時点（ＰＯＳ）デバイス、オンボードコンピューター、オンボードテレビ、ウェアラブルデバイス等、又はそれらの任意の組み合わせを含むことができる。例えば、商品は、コンピューター又はモバイルフォンにおいて用いられる任意のソフトウェア及び／又はアプリケーションであってもよい。このソフトウェア及び／又はアプリケーションは、ソーシャライジング、ショッピング、輸送、娯楽、学習、投資等、又はそれらの任意の組み合わせに関するものであってもよい。幾つかの実施形態では、輸送に関するソフトウェア及び／又はアプリケーションは、旅行ソフトウェア及び／又は旅行アプリケーション、車両スケジューリングソフトウェア及び／又は車両スケジューリングアプリケーション、地図ソフトウェア及び／又は地図アプリケーション等を含むことができる。車両スケジューリングソフトウェア及び／又は車両スケジューリングアプリケーションにおいて、車両は、馬、運搬車、人力車（例えば、一輪手押し車、二輪自転車、三輪自転車等）、自動車（例えば、タクシー、バス、自家用車等）、列車、地下鉄、船舶、航空機（例えば、飛行機、ヘリコプター、スペースシャトル、ロケット、熱気球等）等、又はそれらの任意の組み合わせを含むことができる。

図２は、本開示の幾つかの実施形態に係る、サーバー１１０、要求者端末１３０、及び／又は提供者端末１４０を実施することができるコンピューティングデバイス２００の例示的なハードウェア構成要素及びソフトウェア構成要素を示す概略図である。例えば、処理エンジン１１２は、コンピューティングデバイス２００上で実施することができ、本開示において開示された処理エンジン１１２の機能を実行するように構成することができる。

コンピューティングデバイス２００は、汎用コンピューターであってもよいし、専用コンピューターであってもよく、いずれも、本開示のオンデマンドシステムを実施するのに用いることができる。コンピューティングデバイス２００は、本明細書において説明するようなオンデマンドサービスの任意の構成要素を実施するのに用いることができる。例えば、処理エンジン１１２は、コンピューティングデバイス２００上で、そのハードウェア、ソフトウェアプログラム、ファームウェア、又はそれらの組み合わせによって実施することができる。便宜上、１つのそのようなコンピューターしか示されていないが、本明細書において説明するようなオンデマンドサービスに関するコンピューターの機能は、処理負荷を分散させるために、複数の同様のプラットフォーム上に分散形式で実施されてもよい。

コンピューティングデバイス２００は、例えば、ネットワークに接続されて、接続されたネットワークに対するデータ通信を容易にするＣＯＭポート２５０を備えることができる。コンピューティングデバイス２００は、プログラム命令を実行する１つ以上のプロセッサの形態の中央処理装置（ＣＰＵ）２２０も備えることができる。この例示的なコンピュータープラットフォームは、内部通信バス２１０と、種々の形態のプログラム記憶装置及びデータ記憶装置、例えばディスク２７０と、このコンピューターによって処理及び／又は送信される様々なデータファイルのためのリードオンリーメモリ（ＲＯＭ）２３０又はランダムアクセスメモリ（ＲＡＭ）２４０とを備えることができる。この例示的なコンピュータープラットフォームは、ＲＯＭ２３０、ＲＡＭ２４０、及び／又は他のタイプの非一時的記憶媒体に記憶され、ＣＰＵ２２０によって実行されるプログラム命令も有することができる。本開示の方法及び／又はプロセスは、プログラム命令として実施されてもよい。コンピューティングデバイス２００は、このコンピューターと、ユーザーインターフェース要素２８０等の当該コンピューターにおける他の構成要素との間の入力／出力をサポートするＩ／Ｏ構成要素２６０も備える。コンピューティングデバイス２００は、ネットワーク通信を介してプログラミング及びデータも受信することができる。

単なる例示として、１つのＣＰＵ及び／又はプロセッサのみがコンピューティングデバイス２００において説明されている。しかしながら、当然ながら、本開示におけるコンピューティングデバイス２００は、複数のＣＰＵ及び／又はプロセッサも備えてもよく、したがって、本開示において説明するように１つのＣＰＵ及び／又はプロセッサによって実行される動作及び／又は方法ステップは、複数のＣＰＵ及び／又はプロセッサによって共同で又は別々に実行されてもよい。例えば、本開示において、コンピューティングデバイス２００のＣＰＵ及び／又はプロセッサが、ステップＡ及びステップＢの双方を実行する場合、ステップＡ及びステップＢは、コンピューティングデバイス２００における２つの異なるＣＰＵ及び／又はプロセッサによって共同で又は別々に実行されてもよい（例えば、第１のプロセッサがステップＡを実行し、第２のプロセッサがステップＢを実行するか、又は、第１のプロセッサ及び第２のプロセッサがステップＡ及びステップＢを共同で実行する）ことが理解されるであろう。

図３−Ａは、本開示の幾つかの実施形態に係る一例示的な処理エンジン１１２を示すブロック図である。処理エンジン１１２は、入手モジュール３１０と、速度決定モジュール３２０と、事前決定モジュール３３０と、経路決定モジュール３４０とを備えることができる。

入手モジュール３１０は、移動デバイスに関する複数の位置点（例えば、ＧＰＳ点）を取得するように構成することができる。この移動デバイスは、要求者端末１３０、提供者端末１４０又は提供者の車両を含むことができる。入手モジュール３１０は、要求者端末１３０、提供者端末１４０、又は車両内の測位システム（例えば、ＧＰＳ、ドライブレコーダー）から複数の位置点を取得することができる。

速度決定モジュール３２０は、複数の位置点のうちの２つの間における移動デバイスの少なくとも１つの平均速度を求めるように構成することができる。

事前決定モジュール３３０は、一組の有効位置点を求めるように構成することができる。例えば、事前決定モジュール３３０は、干渉位置点（複数の場合もある）が出現しているか否かを判断することができ、干渉位置点（複数の場合もある）を複数の位置点から除去することができる。

経路決定モジュール３４０は、一組の有効位置点に基づいて移動デバイスの経路を求めるように構成することができる。移動デバイスの経路は、直線の場合もあるし、曲線の場合もある。

処理エンジン１１２内のモジュールは、有線接続又は無線接続を介して互いに接続又は通信することができる。有線接続は、金属ケーブル、光ケーブル、ハイブリッドケーブル等、又はそれらの任意の組み合わせを含むことができる。無線接続は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、ＺｉｇＢｅｅ（登録商標）、近接場通信（ＮＦＣ）等、又はそれらの任意の組み合わせを含むことができる。これらのモジュールのうちの２つ以上は、単一のモジュールとして組み合わされてもよく、これらのモジュールのうちのいずれか１つは、２つ以上のユニットに分割されてもよい。例えば、入手モジュール３１０及び速度決定モジュール３２０は、複数の位置点を取得することと、複数の位置点のうちのいずれか２つの間における少なくとも１つの平均速度を求めることとの双方を行うことができる単一のモジュールとして統合されてもよい。

図３−Ｂは、本開示の幾つかの実施形態に係る移動デバイスの経路を求める一例示的なプロセス／方法３００を示すフローチャートである。プロセス及び／又は方法３００は、オンデマンドサービスシステム１００によって実行することができる。例えば、このプロセス及び／又は方法は、記憶装置のＲＯＭ２３０又はＲＡＭ２４０に記憶された一組の命令（例えば、アプリケーション）として実施することができる。ＣＰＵ２１０は、一組の命令を実行することができ、それに応じて、プロセス及び／又は方法３００を実行するように指示を受けることができる。

ステップ３０２において、処理エンジン１１２は、移動デバイスに関する複数の位置点（例えば、ＧＰＳ点）を取得することができる。

例えば、これらの位置点は、車両に搭載されたＧＰＳデバイスによって検出された車両の位置点であってもよい。これらの位置点は、車両内のモバイル端末（例えば、要求者端末１３０又は提供者端末１４０）の位置点であってもよい。複数の位置点の数は、少なくとも３とすることができる。処理エンジン１１２が複数の位置点を取得すると、処理エンジン１１２は、これらの複数の位置点が位置する領域を特定し、地図データがこの領域に利用可能であるか否かを判断することができる。地図データがこの領域に利用可能である場合、処理エンジン１１２は、この地図データに基づいて複数の位置点を解析し、地図（例えば、Ｔｅｎｃｅｎｔ（テンセント）地図、Ｇｏｏｇｌｅ（登録商標）マップ）上で移動デバイスの経路（例えば、道路又は街路の一部分）を求めることができる。地図データがこの領域に利用不能である場合、処理エンジン１１２は、例えば、複数の位置点を更に処理し、複数の位置点のうちのいずれか２つの間における平均速度を求め、干渉位置点が出現しているか否かを判断することができる。干渉位置点は、本明細書において用いられるとき、移動デバイスの実際の場所を反映することができないエラー点を指すことができる。このエラー点は、移動デバイスの正常な走路から逸脱した点又はシステムエラーに起因した点を含むことができる。干渉位置点は、誤って測定されたので、その結果、移動デバイスの不正確な推定経路をもたらす場合がある。処理エンジン１１２は、複数の位置点のうちのいずれか２つの間における複数の平均速度に基づいて干渉位置点を求め、この干渉位置点を複数の位置点から削除することができる。

幾つかの実施形態では、処理エンジン１１２は、移動デバイスに統合された測位システムから複数の位置点を取得することができる。例えば、処理エンジン１１２は、要求者端末１３０、提供者端末１４０、又は車両内のＧＰＳから複数の位置点を取得することができる。別の例として、処理エンジン１１２は、車両内のドライブレコーダーから複数の位置点を取得することができる。処理エンジン１１２は、ネットワーク１２０を介してＧＰＳ又はドライブレコーダーと通信することができる。更なる例として、提供者端末１４０は、車両と接続又は通信することができ、処理エンジン１１２は、提供者端末１４０から車両の複数の位置点を取得することができる。幾つかの実施形態では、処理エンジン１１２は、データベース１５０から複数の位置点を取得することができる。このデータベースは、時間（例えば、１時間、１日、１週）によって分類された移動デバイスの複数の位置点を記憶することができる。

複数の位置点のうちのいずれか１つは、場所情報及び時刻情報を含むことができる。場所情報は、移動デバイスの地理的場所（例えば、緯度、経度、高度）を指すことができる。時刻情報は、移動デバイスが地理的場所に到着する時点を示すことができる。例えば、時刻情報は、測位システムが地理的情報を処理エンジン１１２に送信した時点であってもよい。別の例として、時刻情報は、処理エンジン１１２が測位システムから地理的情報を受信した時点であってもよい。本開示において、時刻情報は、「位置点の時点」と総称される場合がある。

幾つかの実施形態では、処理エンジン１１２は、複数の位置点を周期的に取得することができる。例えば、処理エンジン１１２は、所定の時間間隔（例えば、５ｓ）に従って複数の位置点を取得することができる。

ステップ３０４において、処理エンジン１１２は、複数の位置点のうちの２つの間における移動デバイスの少なくとも１つの平均速度を求めることができる。

処理エンジン１１２は、２つの位置点に対応する場所情報及び時刻情報に基づいて平均速度を求めることができる。例えば、処理エンジン１１２は、場所情報と、時刻情報に基づく２つの位置点の間の時間差とに基づいて、２つの位置点の間の距離を求めることができる。処理エンジン１１２は、距離及び時間差に基づいて平均速度を更に求めることができる。当然ながら、本開示において用いられる「距離」は、空間距離又は移動距離を指すことができる。空間距離は、本明細書において用いられるとき、道路又は街路の一部分等の、車両が進む際に沿うことができる経路の距離を指すことができる。

ステップ３０６において、処理エンジン１１２は、移動デバイスの少なくとも１つの平均速度に基づいて一組の有効位置点を求めることができる。処理エンジン１１２は、１つ以上の干渉位置点を求め、これらの干渉位置点を複数の位置点から除去することができる。処理エンジン１１２は、速度閾値（「基準速度」とも呼ばれる）を規定し、平均速度を速度閾値と比較することができる。例えば、２つの位置点の間の平均速度が速度閾値以上である場合、これは、車両がナビゲーション中に異常な速度変化を経験したこと、又は、２つの位置点のうちの少なくとも一方が正しく測定されなかったことのいずれかを意味する。ただし、前者の可能性は低いものと仮定される。したがって、処理エンジン１１２は、２つの位置点のうちの少なくとも一方が干渉位置点である可能性があると判断することができる。

ステップ３０８において、処理エンジン１１２は、一組の有効位置点に基づいて移動デバイスの経路を求めることができる。処理エンジン１１２は、一組の有効位置点に基づいて１つ以上のラインを求めることができる。ラインは、直線の場合もあるし、曲線の場合もある。処理エンジン１１２は、フィッティング手法に基づいてライン（複数の場合もある）を求めることができる。フィッティング手法は、直線フィッティング手法、多項式フィッティング手法等、又はそれらの組み合わせを含むことができる。処理エンジン１１２は、１つ以上のラインに基づいて移動デバイスの経路を更に求めることができる。例えば、処理エンジン１１２は、２つのラインを求め、これらの２つのラインを経路として接続することができる。幾つかの実施形態では、処理エンジン１１２は、一組の有効位置点を複数のグループ（例えば、３つの有効位置点を含むグループ）に分割し、これらの複数のグループを同時に又は連続的に処理することができる。例えば、複数のグループのそれぞれについて、処理エンジン１１２は、直線回帰に基づいてラインを求めることができる。処理エンジン１１２は、複数のラインを接続することによって、移動デバイスの経路を更に求めることができる。

幾つかの実施形態では、処理エンジン１１２は、移動デバイスの経路のデータを、データベース１５０又は本開示の他の個所に開示された任意の記憶デバイスに更に記憶することができる。

幾つかの実施形態では、処理エンジン１１２は、移動デバイスの経路を表示するように、移動デバイス（例えば、要求者端末１３０、提供者端末１４０等）に関連付けられたディスプレイ（例えば、スクリーン）に更に指示することができる。

幾つかの実施形態では、処理エンジン１１２は、複数の移動デバイスの複数の経路を求めることができる。例えば、地図データが利用不能である領域について、処理エンジン１１２は、その領域内を進む複数の車両の位置情報（例えば、ＧＰＳ点）を収集し、それらの複数の車両のそれぞれの経路を求めることができる。複数の車両の求められた経路は、その領域内の道路網を示すことができる。幾つかの実施形態では、処理エンジン１１２は、複数の車両に対応する求められた経路に基づいて地図を構築することができる。さらに、処理エンジン１１２は、或る特定の時間間隔（例えば、１０分）でこの地図を更新することができる。幾つかの実施形態では、処理エンジン１１２は、領域の地図を、データベース１５０又は本開示の他の個所に開示された任意の記憶デバイスに記憶することができる。

幾つかの実施形態では、複数の位置点の数又は一組の有効位置点の数は、２の場合がある。この状況では、処理エンジン１１２は、これらの２つの位置点を直接接続し、移動デバイスの経路を求めることができる。幾つかの実施形態では、複数の位置点の数又は一組の有効位置点の数は、１のみの場合がある。この状況では、処理エンジン１１２は、エラーを知らせるアラート又は通知をユーザー（例えば、要求者又は提供者）に提供することができる。

幾つかの実施形態では、図１に関して説明したように、処理エンジン１１２は、要求者端末１３０又は提供者端末１４０に統合されてもよい。処理エンジン１１２は、要求者端末１３０又は提供者端末１４０の位置点を取得し、これらの位置点に基づいて要求者端末１３０又は提供者端末１４０の経路を求めることができる。処理エンジン１１２は、要求者端末１３０又は提供者端末１４０の経路を、データベース１５０又は要求者端末１３０若しくは提供者端末１４０の記憶装置（例えば、ＲＯＭ２３０又はＲＡＭ２４０）に更に記憶することができる。当然ながら、図１に示すアプリケーションシナリオ以外では、処理エンジン１１２は、任意のシステム（例えば、インテリジェント輸送システム）において用いられてもよく、移動デバイスの経路を求めるために用いられる任意の移動デバイスに統合されてもよい。

図４は、本開示の幾つかの実施形態に係る一組の有効位置点を求める一例示的なプロセス／方法４００を示すフローチャートである。プロセス及び／又は方法４００は、オンデマンドサービスシステム１００によって実行することができる。例えば、このプロセス及び／又は方法は、記憶装置のＲＯＭ２３０又はＲＡＭ２４０に記憶された一組の命令（例えば、アプリケーション）として実施することができる。ＣＰＵ２１０は、一組の命令を実行することができ、それに応じて、プロセス及び／又は方法４００を実行するように指示を受けることができる。

ステップ４０２において、処理エンジン１１２は、複数の位置点を時系列に整列することができる。複数の位置点の数は、少なくとも３とすることができる。「時系列に整列する」は、本明細書において用いられるとき、処理エンジン１１２が、複数の位置点の時点に従って、例えば早いものから遅いものに複数の位置点を整列することができることを指すことができる。表１に示すように、処理エンジン１１２は、第１の整列結果を生成することができる。

ステップ４０４において、処理エンジン１１２は、複数の位置点から第１の整列結果に従って順番に第１の点、第２の点、及び第３の点を選択することができる。例えば、処理エンジン１１２は、第１の整列結果に従って最初の３つの位置点を第１の点、第２の点、及び第３の点として選択することができる。

ステップ４０６において、処理エンジン１１２は、第１の点、第２の点、及び第３の点のうちのいずれか２つの間における３つの平均速度を求めることができる。例えば、処理エンジン１１２は、第１の点と第２の点との間における第１の平均速度と、第２の点と第３の点との間における第２の平均速度と、第１の点と第３の点との間における第３の平均速度とを求めることができる。便宜上、例示として、第１の点を点ａと記載し、第２の点を点ｂと記載し、第３の点を点ｃと記載する。したがって、第１の平均速度をｖ_ａｂと記載し、第２の平均速度をｖ_ｂｃと記載し、第３の平均速度をｖ_ａｃと記載する。

ステップ４０８において、処理エンジン１１２は、移動デバイスの速度閾値を求めることができる。この速度閾値は、オンデマンドサービスシステム１００のデフォルト設定とすることもできるし、異なる状況に応じて調整可能とすることもできる。例えば、交通ピーク期間では、速度閾値は、相対的に小さくすることができる（例えば、５０ｋｍ／ｈ）のに対して、アイドル期間（例えば、午前１：００〜午前５：００）では、速度閾値は相対的に大きくすることができる（例えば、８０ｋｍ／ｈ）。別の例として、処理エンジン１１２は、最も早い位置点（例えば、表１に示す位置点１）と最も遅い位置点（例えば、表１に示す位置点ｎ）との間の全体の平均速度を速度閾値として求めることができる。

ステップ４１０において、処理エンジン１１２は、何らかの干渉位置点が出現しているか否かを速度閾値及び３つの平均速度に基づいて判断することができる。例えば、処理エンジン１１２は、ｖ_ａｂ、ｖ_ｂｃ、及びｖ_ａｃを速度閾値と比較し、以下の表２に示す比較結果を生成することができる。処理エンジン１１２は、何らかの干渉位置点が出現している可能性があるか否か、又は、どの点が干渉位置点である可能性があるのかを比較結果に従って判断することができる。

ここで、ｖ_{ｌｉｍｉｔ}は速度閾値を指し、表２におけるスラッシュは、干渉位置点が出現していないことを示す。

処理エンジン１１２が、１つ以上の干渉位置点が点ａ、点ｂ、及び点ｃの中に出現していると判断した場合、処理エンジン１１２は、プロセス／方法４００のステップ４１２を実行して、干渉位置点（複数の場合もある）を除去することができ、次に、ステップ４１２を実行して、１つ以上の有効位置点を求めることができる。処理エンジン１１２が、干渉位置点が点ａ、点ｂ、及び点ｃの中に出現していないと判断した場合、処理エンジン１１２は、プロセス／方法４００のステップ４１４を実行して、点ａ、点ｂ、及び点ｃを有効位置点として決定することができる。

ステップ４１６において、処理エンジン１１２は、複数の位置点の全てが選択されているか否かを判断することができる。全てが選択されている場合、処理エンジン１１２は、プロセス及び／又は方法４００の実行を終了することができる。処理エンジン１１２は、その後、有効位置点に基づいて移動デバイスの経路を求めることができる。全てが選択されていない場合、処理エンジン１１２は、プロセス及び／又は方法４００のステップ４１８を実行することができる。

ステップ４１８において、処理エンジン１１２は、第１の整列結果に従って、第１の点、第２の点、及び第３の点を更新することができる。

処理エンジン１１２は、更新された第１の点、更新された第２の点、及び更新された第３の点を求め、全ての位置点が選択されるまで、ステップ４０６〜４１４のうちの少なくとも１つを更に繰り返すことができる。

幾つかの実施形態では、処理エンジン１１２が、ステップ４１４において、２つ以上の有効位置点を決定した場合、処理エンジン１１２は、それらの有効位置点の中で最も遅いものを更新された第１の点として決定することができる。「最も遅いもの」は、本明細書において用いられるとき、第１の整列結果に従って他の位置点（複数の場合もある）に対して最も遅い時点を有する位置点を指すことができる。例えば、処理エンジン１１２が、ステップ４１４において、点ａ及び点ｃを有効位置点として決定した場合、処理エンジン１１２は、ステップ４１８において、点ｃを更新された第１の点として決定することができる。幾つかの実施形態では、処理エンジン１１２が、ステップ４１４において、１つの有効位置点（例えば、点ａ）しか決定しなかった場合、処理エンジン１１２は、ステップ４１８において、この１つの有効位置点を更新された第１の点として直接決定することができる。処理エンジン１１２は、その後、第１の整列結果に従って、後続の２つの位置点（例えば、点ｄ及び点ｅ）を選択することができる。処理エンジン１１２は、点ｄを更新された第２の点として決定し、点ｅを更新された第３の点として決定することができる。

図５−Ａ及び図５−Ｂは、本開示の幾つかの実施形態に係る移動デバイスの経路を求める一例示的なプロセス／方法５００を示すフローチャートである。プロセス及び／又は方法５００は、オンデマンドサービスシステム１００によって実行することができる。例えば、このプロセス及び／又は方法は、記憶装置のＲＯＭ２３０又はＲＡＭ２４０に記憶された一組の命令（例えば、アプリケーション）として実施することができる。ＣＰＵ２１０は、一組の命令を実行することができ、それに応じて、プロセス及び／又は方法５００を実行するように指示を受けることができる。

プロセス及び／又は方法５００は、一組の有効位置点における全ての有効位置点が処理されるまで循環するプロセスとすることができる。この循環プロセスを通じて、処理エンジン１１２は、複数のライン（例えば、第１のライン、第２のライン、．．．、第ｎのライン）を求めることができる。幾つかの中間ステップにおいて、処理エンジン１１２は、複数のラインを更新し、複数の更新されたライン（例えば、更新された第１のライン、更新された第２のライン、．．．、更新された第ｎのライン）を生成することができる。処理エンジン１１２は、複数のライン及び／又は複数の更新されたラインに基づいて、移動デバイスの経路を求めることができる。

ステップ５０２において、処理エンジン１１２は、一組の有効位置点を時系列に整列することができる。

ステップ４０２に関して同様に説明したように、処理エンジン１１２は、一組の有効位置点を、当該有効位置点の時点に従って整列し、以下の表３に示す第２の整列結果を生成することができる。

ステップ５０４において、処理エンジン１１２は、一組の有効位置点から第２の整列結果に従って順番に３つの有効位置点を選択することができる。

例えば、処理エンジン１１２は、第２の整列結果に従って最初の３つの有効位置点（例えば、有効位置点１’、有効位置点２’、及び有効位置点３’）を選択することができる。

ステップ５０６において、処理エンジン１１２は、これらの３つの有効点に基づいて第１のラインを求めることができる。

第１のラインは、直線の場合もあるし、曲線の場合もある。処理エンジン１１２は、フィッティング手法に従って第１のラインを求めることができる。例えば、処理エンジン１１２は、直線フィッティング手法に従って直線（例えば、図６−Ａに示す直線Ａ’Ｃ’）を求めることができる。第１のラインは、第１の始点（例えば、図６−Ａに示す点Ａ’）及び第１の終点（例えば、図６−Ａに示す点Ｃ’）を含むことができる。

ステップ５０８において、処理エンジン１１２は、全ての有効位置点が選択されているか否かを判断することができる。全ての有効位置点が選択されている場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５１０を実行して、第１のラインに基づいて経路を求めることができる。全ての有効位置点が選択されていない場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５１２を実行することができる。

処理エンジン１１２が第１のラインを求めた後、ステップ５１２において、処理エンジン１１２は、第２の整列結果に従って、上記３つの有効位置点に続く次の有効位置点を選択することができる。例えば、処理エンジン１１２は、一組の有効位置点から有効位置点４’を選択することができる。

ステップ５１４において、処理エンジン１１２は、選択された次の点の、第１のライン上における対応する点を求めることができる。「第１のライン上における対応する点」は、本明細書において用いられるとき、選択された次の点の、第１のライン上又は第１のラインの延長ライン上への投影点を指すことができる。例えば、処理エンジン１１２は、選択された次の点から第１のラインに垂直な基準ラインを求め、この基準ラインと第１のラインとの交点を求めることができる。処理エンジン１１２は、この交点（例えば、図６−Ａ点に示すＤ_２’）を、選択された次の点の対応する点として決定することができる。処理エンジン１１２が、対応する点を決定した後、処理エンジン１１２は、プロセス及び／又は方法５００のノードＡ ５１５を実行し、図５−Ｂに示すノードＡ ５１５から開始するステップのうちの少なくとも幾つかを実行することができる。

ステップ５１６において、処理エンジン１１２は、選択された次の点と対応する点との間の距離（例えば、図６−Ａに示す点Ｄ２と点Ｄ２’との間の距離）を求め、この距離が距離閾値（例えば、２０ｍ）未満であるか否かを判断することができる。上記距離が距離閾値未満である場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５１８を実行して、選択された次の点に基づいて第１のラインを更新することができる。この距離が距離閾値未満でない場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５２０を実行して、上記次の点を方向転換点と判断することができる。方向転換点は、本明細書において用いられるとき、移動デバイスが第１のラインから方向転換していることを示すことができる。

ステップ５１８において、処理エンジン１１２は、選択された次の点に基づいて第１のラインを更新することができる。幾つかの実施形態では、第１のラインが直線である場合、処理エンジン１１２は、第１の始点又は第１の終点を変更することによって第１のラインを更新することができる。例えば、処理エンジン１１２は、第１の終点を、基準ラインと第１のラインとの交点として変更することができる。別の例として、処理エンジン１１２は、３つの選択された有効位置点及び選択された次の点に対して直線フィッティング方法を適用し、更新された第１のラインを求めることができる。幾つかの実施形態では、第１のラインが曲線である場合、処理エンジン１１２は、この曲線を次の点と接続することによって第１のラインを更新することができる。処理エンジン１１２が第１のラインを更新した後、処理エンジン１１２は、プロセス及び／又は方法５００のノードＢ ５１９を実行し、ステップ５０８からのステップのうちの少なくとも幾つかを繰り返すことができる。

処理エンジン１１２が、ステップ５２０において、次の点を方向転換点と判断した後、処理エンジン１１２は、全ての有効位置点が選択されているか否かを判断することができる。全ての有効位置点が選択されている場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５２４を実行して、第１のライン及び方向転換点に基づいて経路を求めることができる。例えば、ステップ５２４において、処理エンジン１１２は、直線又は曲線によって第１のラインの終点を方向転換点と接続することができる。全ての有効位置点が選択されていない場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５２６を実行して、第２の整列結果に従って、方向転換点に続く次の２つの有効位置点を選択することができる。

ステップ５２８において、処理エンジン１１２は、方向転換点及び次の２つの有効位置点に基づいて第２のラインを求めることができる。第１のラインと同様に、第２のラインは、直線の場合もあるし、曲線の場合もある。処理される有効位置点が１つしか存在しない場合、処理エンジン１１２は、方向転換点とこの最後の有効位置点とを接続することによって第２のラインを求めることができる。

ステップ５３０において、処理エンジン１１２は、全ての有効位置点が選択されているか否かを判断することができる。全ての有効位置点が選択されている場合、処理エンジン１１２は、プロセス及び／又は方法５００のステップ５３２を実行して、第１のライン及び第２のラインに基づいて経路を求めることができる。全ての有効位置点が選択されていない場合、処理エンジン１１２は、プロセス及び／又は方法５００のノードＣ ５３１を実行し、ステップ５１２からのステップのうちの少なくとも幾つかを繰り返すことができる。

当然ながら、上記説明は、一例として１つの循環プロセスのみを取り上げており、実際の状況では、複数の循環プロセスが存在し得る。さらに、上記説明は、単に例示として提供されているにすぎず、本開示の範囲を限定することを意図するものではない。当業者であれば、本開示の教示の下で複数の変形及び変更を行うことができる。ただし、それらの変形及び変更は、本開示の範囲から逸脱するものではない。例えば、一組の有効位置点の数が相対的に大きい（例えば、１００）場合、処理エンジン１１２が、全ての有効位置点が選択されているか否かを判断する上記ステップのうちの幾つかは省略されてもよい。

図６−Ａは、本開示の幾つかの実施形態に係る方向転換点を求める一例示的なプロセス／方法を示す概略図である。図６−Ａに示すように、処理エンジン１１２は、一組の有効位置点から点Ａ、点Ｂ、及び点Ｃを選択する。処理エンジン１１２は、直線フィッティング手法によって、点Ａ、点Ｂ、及び点Ｃに基づいてラインＡ’Ｃ’を更に求める。ラインＡ’Ｃ’は、始点Ａ’及び終点Ｃ’を含む。

処理エンジン１１２がラインＡ’Ｃ’を求めた後、処理エンジン１１２は、一組の有効位置点の残余から次の点（例えば、点Ｄ_１又は点Ｄ_２）を選択することができる。点Ｄ_１について、処理エンジン１１２は、ラインＡ’Ｃ’上の対応する点Ｄ_１”を求め、点Ｄ_１と点Ｄ_１”との間の距離Ｄ_１Ｄ_１”を求めることができる。処理エンジン１１２は、距離Ｄ_１Ｄ_１”を距離閾値と更に比較することができる。図示するように、距離Ｄ_１Ｄ_１”は、距離閾値よりも大きく、その場合、処理エンジン１１２は、点Ｄ_１を方向転換点と判断することができる。処理エンジン１１２は、次の２つの有効位置点（すなわち、点Ｅ及び点Ｆ）を更に選択し、ラインＤ_１’Ｆ’を求めることができる。

点Ｄ_２について、処理エンジン１１２は、ラインＡ’Ｃ’上の対応する点Ｄ_２’を求め、点Ｄ_２と点Ｄ_２’との間の距離Ｄ_２Ｄ_２’を求めることができる。図示するように、距離Ｄ_２Ｄ_２’は、距離閾値未満であり、処理エンジン１１２は、ラインＡ’Ｃ’をラインＡ’Ｄ_２’として更新することができる。

図６−Ｂは、本開示の幾つかの実施形態に係る複数の位置点の一例示的な分布を示す概略図である。図６−Ｂに示すように、破線は、移動デバイスが沿って移動している道路又は街路の一部分を指す。地図データは利用不能であり、その結果、道路又は街路は不可視である場合がある。中実点は複数の位置点を指す。複数の位置点の分布は、道路又は街路に沿った正常な分布とすることができる。すなわち、道路又は街路は、この正常な分布の回帰ラインとすることができる。干渉位置点は除去されていると仮定することができ、処理エンジン１１２は、複数の位置点に対して直線回帰手法を適用し、移動デバイスの経路（すなわち、道路又は街路の一部分）を求めることができる。

基本概念を上記のように説明してきたが、この詳細な開示を読んだ後、前述の詳細な開示は、単に例としての提示を意図したものにすぎず、限定ではないことが当業者にはかなり明らかになり得る。本明細書において明示的に述べられていないが、様々な改変、改良、及び変更を行うことができ、これらは当業者に意図されている。これらの改変、改良、及び変更は、本開示によって示唆されることが意図されており、本開示の例示的な実施形態の趣旨及び範囲内にある。

その上、幾つかの特定の術語が、本開示の実施形態を説明するのに用いられている。例えば、「１つの実施形態」、「一実施形態」、及び／又は「幾つかの実施形態」という用語は、実施形態について説明した特定の特徴、構造又は特性が本開示の少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書の様々な部分における「一実施形態」若しくは「１つの実施形態」又は「代替の実施形態」への言及が２つ以上あっても、これは、全てが必ずしも同じ実施形態を指しているとは限らないことを強調するとともに、そのことを理解されたい。さらに、特定の特徴、構造又は特性は、本開示の１つ以上の実施形態において適宜組み合わせることができる。

さらに、本開示の態様は、任意の新規で有用なプロセス、機械、生産物、若しくは組成物、又はそれらの任意の新規で有用な改良形態を含む任意の複数の特許可能なクラス又はコンテキストのうちのいずれにおいても本明細書で図示及び説明することができることが当業者によって理解されるであろう。したがって、本開示の態様は、全体をハードウェアで実施することもできるし、全体をソフトウェア（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）で実施することもできるし、本明細書において全て「ユニット」、「モジュール」、又は「システム」と一般に呼ぶことができるソフトウェア及びハードウェアを組み合わせた実施態様で実施することもできる。さらに、本開示の態様は、具現化されたコンピューター可読プログラムコードを有する１つ以上のコンピューター可読媒体に具現化されたコンピュータープログラム製品の形態を取ることができる。

コンピューター可読信号媒体は、例えば、ベースバンド内に又は搬送波の一部分として具現化されたコンピューター可読プログラムコードを有する伝播データ信号を含むことができる。そのような伝播信号は、電磁気、光等、又はそれらの任意の適した組み合わせを含む様々な形態のうちの任意のものを取ることができる。コンピューター可読信号媒体は、コンピューター可読記憶媒体でない任意のコンピューター可読媒体であって、命令実行システム、命令実行装置、若しくは命令実行デバイスによって用いられるか又はこれらに関して用いられるプログラムを通信、伝播、又は搬送することができる任意のコンピューター可読媒体であってもよい。コンピューター可読信号媒体上に具現化されたプログラムコードは、無線、ワイヤーライン、光ファイバーケーブル、ＲＦ等、又はそれらの任意の適した組み合わせを含む任意の適切な媒体を用いて送信することができる。

本開示の態様の動作を実行するコンピュータープログラムコードは、Ｊａｖａ（登録商標）、Ｓｃａｌａ、Ｓｍａｌｌｔａｌｋ、Ｅｉｆｆｅｌ、ＪＡＤＥ、Ｅｍｅｒａｌｄ、Ｃ＋＋、Ｃ＃、ＶＢ．ＮＥＴ、Ｐｙｔｈｏｎ等のオブジェクト指向型プログラミング言語、「Ｃ」プログラミング言語、Ｖｉｓｕａｌ Ｂａｓｉｃ、Ｆｏｒｔｒａｎ２００３、Ｐｅｒｌ、ＣＯＢＯＬ２００２、ＰＨＰ、ＡＢＡＰ等の従来の手続型プログラミング言語、Ｐｙｔｈｏｎ、Ｒｕｂｙ及びＧｒｏｏｖｙ等の動的プログラミング言語、又は他のプログラミング言語を含む１つ以上のプログラミング言語の任意の組み合わせで記述することができる。プログラムコードは、スタンドアローンソフトウェアパッケージとして、全体をユーザーのコンピューター上で実行することもできるし、一部をユーザーのコンピューター上で実行することもできるし、一部をユーザーのコンピューター上で、及び一部をリモートコンピューター上で実行することもできるし、全体をリモートコンピューター又はサーバー上で実行することもできる。後半のシナリオでは、リモートコンピューターは、ローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを通じてユーザーのコンピューターに接続することができる。すなわち、この接続は、（例えば、インターネットサービスプロバイダーを用いてインターネットを通じて）外部コンピューターに対して行うこともできるし、クラウドコンピューティング環境において行うこともできるし、サービス型ソフトウェア（ＳａａＳ）等のサービスとして提供することもできる。

さらに、処理要素若しくは処理シーケンスの列挙した順序、又はそれらの数字、文字、若しくは他の名称の使用は、請求項において指定することができる場合を除いて、請求項に記載のプロセス及び方法をいずれの順序にも限定することを意図するものではない。上記開示は、様々な例を通じて、本開示の様々の有用な実施形態であると現在考えられているものを論述しているが、そのような詳細は、その目的のためのものにすぎず、添付の特許請求の範囲は、開示された実施形態に限定されるものではなく、逆に、開示された実施形態の趣旨及び範囲内にある変更及び均等なアレンジを包含することが意図されていることが理解されるであろう。例えば、上述した様々な構成要素の実施態様は、ハードウェアデバイスに具現化することができるが、ソフトウェアのみのソリューション、例えば、既存のサーバー又はモバイルデバイス上へのインストールとして実施することもできる。

同様に、本開示の実施形態の上記説明では、様々な実施形態のうちの１つ以上の理解に役立つ本開示のストリームライン化を目的として、様々な特徴がともに単一の実施形態、その実施形態の図、又はその実施形態の説明にグループ化されることがあることが理解されるであろう。ただし、この開示方法は、請求項に記載の主題が、各請求項に明示列挙されたものよりも多くの特徴を必要とするという意図を反映するものと解釈されるべきでない。逆に、請求項に記載の主題は、上記開示された単一の実施形態の全ての特徴よりも少ない特徴に依拠することができる。

Claims (14)

1. バスと、
   移動デバイスの経路を求める一組の命令を含む、前記バスに電子的に接続された１つ以上の記憶媒体と、
   前記バスを介して前記少なくとも１つの記憶媒体に電子的に接続された論理回路とを備え、
   前記論理回路は、動作中に、前記一組の命令をロードし、複数の移動デバイスの各移動デバイスについて、
   移動デバイスに関する複数の位置点に関連付けられた電子信号を取得することと、
   時系列に整列された整列結果に従って前記複数の位置点から最初の３つの位置点を順番に第１の点、第２の点、及び第３の点として選択することと、
   前記第１の点、前記第２の点、及び前記第３の点のうちのいずれか２つの間における前記移動デバイスの３つの平均速度を求めることと、
   前記移動デバイスの基準速度を求めることと、
   前記３つの平均速度と前記基準速度との比較を行うことと、
   干渉位置点が前記第１の点、前記第２の点、及び前記第３の点から出現しているか否かを前記比較に基づいて判断することと、
   前記干渉位置点が出現しているときに前記干渉位置点を除去することと、
   前記第１の点、前記第２の点、及び前記第３の点の残余を少なくとも一組の有効位置点として決定することと、
   ２つ以上の前記有効位置点を決定した場合に前記有効位置点の中で最も遅いものを更新された前記第１の点として決定することと、
   １つの前記有効位置点しか決定しなかった場合にこの１つの前記有効位置点を更新された前記第１の点として決定することと、
   前記整列結果に従って順番に更新された前記第１の点、前記第２の点、及び前記第３の点を選択することと、
   前記移動デバイスの３つの平均速度を求めることと、前記基準速度を求めることと、前記比較を行うことと、前記干渉位置点が出現しているか否かを判断することと、前記干渉位置点が出現しているときに前記干渉位置点を除去することと、前記残余を前記一組の有効位置点として決定することと、２つ以上の前記有効位置点を決定した場合に前記有効位置点の中で最も遅いものを更新された前記第１の点として決定することと、１つの前記有効位置点しか決定しなかった場合にこの１つの前記有効位置点を更新された前記第１の点として決定することと、前記整列結果に従って順番に更新された前記第１の点、前記第２の点、及び前記第３の点を選択することと、を全ての位置点が前記第１の点、前記第２の点または前記第３の点として選択されるまで繰り返すことと、
   前記一組の有効位置点に基づいて前記移動デバイスの経路を求めることと、
   前記バスに電子信号を送信して、前記移動デバイスの前記経路のデータを前記１つ以上の記憶媒体に記憶することと、を行う、システム。
2. 前記論理回路は、
   前記複数の位置点が位置する領域を特定することと、
   特定された前記複数の位置点が位置する領域の地図データが利用不能であると判断することと、
   を更に行う、請求項１に記載のシステム。
3. 前記論理回路は、
   前記複数の移動デバイスに対応する前記求められた経路に基づいて地図を構築すること、
   を更に行う、請求項１に記載のシステム。
4. 前記論理回路は、前記一組の有効位置点に基づいて前記移動デバイスの前記経路を求めるために、
   前記一組の有効位置点から第１の有効位置点、第２の有効位置点、及び第３の有効位置点を選択することと、
   前記第１の有効位置点、前記第２の有効位置点、及び前記第３の有効位置点に基づいて第１のラインを求めることと、
   前記第１のラインに基づいて前記移動デバイスの前記経路を求めることと、
   を更に行う、請求項１に記載のシステム。
5. 前記論理回路は、
   前記一組の有効位置点から第４の有効位置点を選択することと、
   前記第４の有効位置点に対応する、前記第１のライン上の点を求めることと、
   前記第４の有効位置点と前記対応する点との間の距離を求めることと、
   前記距離が閾値未満であると判断することと、
   前記対応する点に基づいて前記第１のラインを更新することと、
   前記更新された第１のラインに基づいて前記移動デバイスの前記経路を求めることと、
   を更に行う、請求項４に記載のシステム。
6. 前記論理回路は、
   前記距離が前記閾値よりも大きいと判断することと、
   前記第４の有効位置点を前記経路の方向転換点と判断することと、
   を更に行う、請求項５に記載のシステム。
7. 前記論理回路は、
   前記第１のライン及び前記方向転換点に基づいて前記移動デバイスの前記経路を更新すること、
   を更に行う、請求項６に記載のシステム。
8. 前記論理回路は、
   第５の有効位置点及び第６の有効位置点を選択することと、
   前記方向転換点、前記第５の有効位置点、及び前記第６の有効位置点に基づいて第２のラインを求めることと、
   前記第１のライン及び前記第２のラインに基づいて前記移動デバイスの前記経路を更新することと、
   を更に行う、請求項６に記載のシステム。
9. 少なくとも１つの電子デバイスによって、移動デバイスに関する複数の位置点を取得することと、
   前記少なくとも１つの電子デバイスによって、時系列に整列された整列結果に従って前記複数の位置点から最初の３つの位置点を順番に第１の点、第２の点、及び第３の点として選択することと、
   前記少なくとも１つの電子デバイスによって、前記第１の点、前記第２の点、及び前記第３の点のうちのいずれか２つの間における前記移動デバイスの３つの平均速度を求めることと、
   前記少なくとも１つの電子デバイスによって、前記移動デバイスの基準速度を求めることと、
   前記少なくとも１つの電子デバイスによって、前記３つの平均速度と前記基準速度との比較を行うことと、
   前記少なくとも１つの電子デバイスによって、干渉位置点が前記第１の点、前記第２の点、及び前記第３の点から出現しているか否かを前記比較に基づいて判断することと、
   前記少なくとも１つの電子デバイスによって、前記干渉位置点が出現しているときに前記干渉位置点を除去することと、
   前記少なくとも１つの電子デバイスによって、前記第１の点、前記第２の点、及び前記第３の点の残余を少なくとも一組の有効位置点として決定することと、
   前記少なくとも１つの電子デバイスによって、２つ以上の前記有効位置点を決定した場合に前記有効位置点の中で最も遅いものを更新された前記第１の点として決定することと、
   前記少なくとも１つの電子デバイスによって、１つの前記有効位置点しか決定しなかった場合にこの１つの前記有効位置点を更新された前記第１の点として決定することと、
   前記少なくとも１つの電子デバイスによって、前記整列結果に従って順番に更新された前記第１の点、前記第２の点、及び前記第３の点を選択することと、
   前記少なくとも１つの電子デバイスによって、前記移動デバイスの３つの平均速度を求めることと、前記基準速度を求めることと、前記比較を行うことと、前記干渉位置点が出現しているか否かを判断することと、前記干渉位置点が出現しているときに前記干渉位置点を除去することと、前記残余を前記一組の有効位置点として決定することと、２つ以上の前記有効位置点を決定した場合に前記有効位置点の中で最も遅いものを更新された前記第１の点として決定することと、１つの前記有効位置点しか決定しなかった場合にこの１つの前記有効位置点を更新された前記第１の点として決定することと、前記整列結果に従って順番に更新された前記第１の点、前記第２の点、及び前記第３の点を選択することと、を全ての位置点が前記第１の点、前記第２の点または前記第３の点として選択されるまで繰り返すことと、
   前記少なくとも１つの電子デバイスによって、前記一組の有効位置点に基づいて前記移動デバイスの経路を求めることと、
   前記少なくとも１つの電子デバイスによって、前記経路のデータを前記１つ以上の記憶媒体に記憶することと、
   を含む、方法。
10. 前記少なくとも１つの電子デバイスによって、前記複数の位置点が位置する領域を特定することと、
    前記少なくとも１つの電子デバイスによって、特定された前記複数の位置点が位置する領域の地図データが利用不能であると判断することと、
    を更に含む、請求項９に記載の方法。
11. 前記少なくとも１つの電子デバイスによって、前記複数の移動デバイスに対応する前記求められた経路に基づいて地図を構築すること、
    を更に含む、請求項９に記載の方法。
12. 前記一組の有効位置点に基づいて前記移動デバイスの前記経路を前記求めることは、
    前記少なくとも１つの電子デバイスによって、前記一組の有効位置点から第１の有効位置点、第２の有効位置点、及び第３の有効位置点を選択することと、
    前記少なくとも１つの電子デバイスによって、前記第１の有効位置点、前記第２の有効位置点、及び前記第３の有効位置点に基づいて第１のラインを求めることと、
    前記少なくとも１つの電子デバイスによって、前記第１のラインに基づいて前記移動デバイスの前記経路を求めることと、
    を含む、請求項９に記載の方法。
13. 前記少なくとも１つの電子デバイスによって、前記一組の有効位置点から第４の有効位置点を選択することと、
    前記少なくとも１つの電子デバイスによって、前記第４の有効位置点に対応する、前記第１のライン上の点を求めることと、
    前記少なくとも１つの電子デバイスによって、前記第４の有効位置点と前記対応する点との間の距離を求めることと、
    前記少なくとも１つの電子デバイスによって、前記距離が閾値未満であると判断することと、
    前記少なくとも１つの電子デバイスによって、前記対応する点に基づいて前記第１のラインを更新することと、
    前記少なくとも１つの電子デバイスによって、前記更新された第１のラインに基づいて前記移動デバイスの前記経路を求めることと、
    を更に含む、請求項１２に記載の方法。
14. 前記少なくとも１つの電子デバイスによって、前記距離が前記閾値よりも大きいと判断することと、
    前記少なくとも１つの電子デバイスによって、前記第４の有効位置点を前記経路の方向転換点と判断することと、
    を更に含む、請求項１３に記載の方法。
    

Images