JP6731423B2 - ナビゲーション制御のための装置および方法 - Google Patents

Description

本出願は、その全体が参照によって本願に組み込まれる、いずれも２０１５年２月５日に出願されたシンガポール特許出願第１０２０１５００８８２Ｖ号およびオーストラリア特許出願第２０１５９００３６２号に対する優先権を主張するものである。

本開示は一般に、車両の移動を制御すること、および、商品格納エリアに商品が格納され、そこから商品が取り出される商品取り扱いシステムに関する。

本明細書に記述される背景技術の説明は、一般に本開示の文脈を提示する目的を有する。ここで名前を挙げた発明人（複数も可）の研究は、この背景技術セクションならびに出願の時点で従来技術と見なされない本説明の態様において説明される研究の範囲において、明示的にも暗示的にも本開示に対する従来技術と認められるものではない。

一部が自動化された商品取り扱いシステムにおいて、商品は、商品格納エリアに格納され、たとえば搬送ロボットなどの搬送車両を用いて商品格納エリアとオペレータステーションとの間で搬送される。そのようなシステムにおいて、搬送車両は、所定の移動経路に沿って倉庫の床に配置された機械検出可能テープを用いて、または、たとえば倉庫の壁に配置された反射材料と相互作用するレーザを用いることによって、商品格納エリアを通ってナビゲートされる。

しかし、そのような既存の商品取り扱いシステムは、比較的複雑な搬送車両を必要とし、車両の位置を制御するための計算集約的タスクを伴う。また、そのようなシステムは、高い精度で搬送車両の位置を制御するものではない。したがって、シームレスかつ計算効率の良い方法で搬送車両の位置を正確に制御（および監視）する技術への要望がある。

本開示の態様は、搬送経路に沿った車両の移動を制御するための方法を提供し、方法は、情報処理装置の回路によって、所定の位置に設置された複数のマーカの１つである第１のマーカが車両によって検出されることに基づいて生成される第１のマーカ情報を受信することと、回路によって、車両が第１のマーカから移動する複数のマーカにおける第２のマーカを決定することと、第１のマーカ情報と、第１のマーカに対する第２のマーカの位置を示す、第１のマーカに関連付けられた所定のナビゲーション情報とに基づいて、第１のマーカから第２のマーカへの車両の移動を制御するための第１の制御情報を生成することと、第１の制御情報を車両へ送信することとを備える。

１つの実施形態によると、方法は更に、回路によって、第２のマーカが車両によって検出されることに基づいて生成される第２のマーカ情報を受信することと、回路によって、車両が第２のマーカから移動する複数のマーカにおける第３のマーカを決定することと、 第２のマーカ情報と、第２のマーカに対する第３のマーカの位置を示す所定のナビゲーション情報とに基づいて、第２のマーカから第３のマーカへの車両の移動を制御するための第２の制御情報を生成することとを備える。

１つの実施形態によると、第２のマーカは第１のマーカと隣り合い、所定のナビゲーション情報は、第１のマーカと隣り合う複数のマーカにおける各マーカの相対位置を示す。また、複数のマーカの各々は機械可読パターンであり、機械可読パターンは、バーコードおよびクイックレスポンス（ＱＲ）コード（登録商標）の１つを含む。また、複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む。

１つの実施形態によると、第１のマーカ情報は、機械可読パターンから車両によって抽出される固有識別子を含む。

１つの実施形態によると、方法は更に、回路によって、車両によって搬送されるラックに配置されたラックマーカが車両によって検出されることに基づいて生成されるラックマーカ情報を受信することを備える。

第１のマーカ情報は、第１のマーカに対する車両の方位情報、および第１のマーカに関連付けられた識別情報を含み、第１のマーカ情報は、車両によって捕捉される第１のマーカの画像を含む。

実施形態によると、方法は更に、回路によって、出発点マーカを始点とし到着点マーカを終点とする車両が通行する複数のマーカにおけるマーカのシーケンスを含む搬送経路を計算することを備え、搬送経路はＡ^＊アルゴリズムを用いて計算される。

また、搬送経路は複数の経路セグメントに分割され、方法は更に、経路セグメントの各々の始点において、車両の移動を制御するための制御情報を送信することを備える。

１つの実施形態によると、方法は更に、メモリに格納されたマーカマップから所定のナビゲーション情報を検索することを更に備え、マーカマップは、複数のマーカの各々について、複数のマーカのそれぞれに対する複数のマーカにおける少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を含み、ナビゲーション情報は、複数のマーカのそれぞれと少なくとも１つの規定の他のマーカとの間の車両の移動を制御するために用いることができ、ナビゲーション情報は、複数のマーカのそれぞれと複数のマーカにおける少なくとも１つの規定の他のマーカとの間の距離に対応する変位値と、方位角値とを含む。

１つの実施形態によると、マーカマップは複数のキーを含み、複数のキーの各々は、複数のマーカの１つに対応し、車両が対応するマーカに位置する時に識別情報を格納する第１のデータフィールド、対応するマーカの予約情報を格納する第２のデータフィールド、対応するマーカの北方向、南方向、東方向、および西方向に配置された少なくとも１つのマーカを含む対応するマーカの近隣マーカに対応し、対応するマーカから対応する近隣マーカへ移動する車両の妥当性を決定するために用いられる情報を格納する第３のデータフィールド、対応するマーカから対応する近隣マーカへ移動する際に車両によって生じるコストを決定するために用いられる、対応するマーカから近隣マーカの各々までの距離を格納する第４のデータフィールド、および車両が対応するマーカに商品ラックを配置することができるかを示す第５のデータフィールドを含む。

本開示の１つの態様によると、搬送経路に沿った車両の移動を制御するための情報処理装置が提供され、情報処理装置は、所定の位置に設置された複数のマーカの１つである第１のマーカが車両によって検出されることに基づいて生成される第１のマーカ情報を受信し、車両が第１のマーカから移動する複数のマーカにおける第２のマーカを決定し、第１のマーカ情報と、第１のマーカに対する第２のマーカの位置を示す、第１のマーカに関連付けられた所定のナビゲーション情報とに基づいて、第１のマーカから第２のマーカへの車両の移動を制御するための第１の制御情報を生成し、第１の制御情報を車両へ送信するように構成された回路を備える。

１つの実施形態によると、回路は更に、第２のマーカが車両によって検出されることに基づいて生成される第２のマーカ情報を受信し、車両が第２のマーカから移動する複数のマーカにおける第３のマーカを決定し、第２のマーカ情報と、第２のマーカに対する第３のマーカの位置を示す所定のナビゲーション情報とに基づいて、第２のマーカから第３のマーカへの車両の移動を制御するための第２の制御情報を生成するように構成され、第２のマーカは第１のマーカと隣り合い、所定のナビゲーション情報は、第１のマーカと隣り合う複数のマーカにおける各マーカの相対位置を示す。

また、１つの実施形態によると、複数のマーカの各々は機械可読パターンであり、機械可読パターンは、バーコードおよびクイックレスポンス（ＱＲ）コード（登録商標）の１つを含み、複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む。

１つの実施形態によると、第１のマーカ情報は、機械可読パターンから車両によって抽出される固有識別子を含み、回路は更に、車両によって搬送されるラックに配置されたラックマーカが車両によって検出されることに基づいて生成されるラックマーカ情報を受信するように構成される。

１つの実施形態によると、情報処理装置に関して、第１のマーカ情報は、第１のマーカに対する車両の方位情報、および第１のマーカに関連付けられた識別情報を含み、第１のマーカ情報は、車両によって捕捉される第１のマーカの画像を含む。

１つの実施形態によると、回路は更に、出発点マーカを始点とし到着点マーカを終点とする車両が通行する複数のマーカにおけるマーカのシーケンスを含む搬送経路を計算するように構成され、搬送経路はＡ^＊アルゴリズムを用いて計算される。

１つの実施形態によると、搬送経路は複数の経路セグメントに分割され、回路は更に、経路セグメントの各々の始点において、車両の移動を制御するための制御情報を送信し、メモリに格納されたマーカマップから所定のナビゲーション情報を検索するように構成され、マーカマップは、複数のマーカの各々について、複数のマーカのそれぞれに対する複数のマーカにおける少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を含み、ナビゲーション情報は、複数のマーカのそれぞれと少なくとも１つの規定の他のマーカとの間の車両の移動を制御するために用いることができる。

１つの実施形態によると、ナビゲーション情報は、複数のマーカのそれぞれと複数のマーカにおける少なくとも１つの規定の他のマーカとの間の距離に対応する変位値と、方位角値とを含み、マーカマップは、複数のキーを含み、複数のキーの各々は、複数のマーカの１つに対応し、車両が対応するマーカに位置する時に識別情報を格納する第１のデータフィールド、対応するマーカの予約情報を格納する第２のデータフィールド、マーカの北方向、南方向、東方向、および西方向に配置された少なくとも１つのマーカを含む対応するマーカの近隣マーカに対応し、対応するマーカから対応する近隣マーカへ移動する車両の妥当性を決定するために用いられる情報を格納する第３のデータフィールド、対応するマーカから対応する近隣マーカへ移動する際に車両によって生じるコストを決定するために用いられる、対応するマーカから近隣マーカの各々までの距離を格納する第４のデータフィールド、および車両がマーカに商品ラックを配置することができるかを示す第５のデータフィールドを含む。

本開示の態様は、コンピュータによって実行されると、コンピュータに、搬送経路に沿った車両の移動を制御するための方法を実行させるプログラムが格納された非一時的コンピュータ可読媒体を提供し、方法は、所定の位置に設置された複数のマーカの１つである第１のマーカが車両によって検出されることに基づいて生成される第１のマーカ情報を受信することと、車両が第１のマーカから移動する複数のマーカにおける第２のマーカを決定することと、第１のマーカ情報と、第１のマーカに対する第２のマーカの位置を示す、第１のマーカに関連付けられた所定のナビゲーション情報とに基づいて、第１のマーカから第２のマーカへの車両の移動を制御するための第１の制御情報を生成することと、第１の制御情報を車両へ送信することとを備える。

１つの実施形態によると、方法は更に、第２のマーカが車両によって検出されることに基づいて生成される第２のマーカ情報を受信することと、車両が第２のマーカから移動する複数のマーカにおける第３のマーカを決定することと、第２のマーカ情報と、第２のマーカに対する第３のマーカの位置を示す所定のナビゲーション情報とに基づいて、第２のマーカから第３のマーカへの車両の移動を制御するための第２の制御情報を生成することとを備える。

１つの実施形態によると、第２のマーカは第１のマーカと隣り合い、所定のナビゲーション情報は、第１のマーカと隣り合う複数のマーカにおける各マーカの相対位置を示し、複数のマーカの各々は機械可読パターンであり、機械可読パターンは、バーコードおよびクイックレスポンス（ＱＲ）コード（登録商標）の１つを含む。

１つの実施形態によると、第１のマーカ情報は、機械可読パターンから車両によって抽出される固有識別子を含み、方法は更に、車両によって搬送されるラックに配置されたラックマーカが車両によって検出されることに基づいて生成されるラックマーカ情報を受信することを備え、第１のマーカ情報は、第１のマーカに対する車両の方位情報、および第１のマーカに関連付けられた識別情報を含む。

１つの実施形態によると、第１のマーカ情報は、車両によって捕捉される第１のマーカの画像を含み、方法は更に、出発点マーカを始点とし到着点マーカを終点とする車両が通行する複数のマーカにおけるマーカのシーケンスを含む搬送経路を計算することを備え、搬送経路はＡ^＊アルゴリズムを用いて計算される。

また、１つの実施形態によると、搬送経路は複数の経路セグメントに分割され、方法は更に、経路セグメントの各々の始点において、車両の移動を制御するための制御情報を送信することと、メモリに格納されたマーカマップから所定のナビゲーション情報を検索することとを備え、マーカマップは、複数のマーカの各々について、複数のマーカのそれぞれに対する複数のマーカにおける少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を含み、ナビゲーション情報は、複数のマーカのそれぞれと少なくとも１つの規定の他のマーカとの間の車両の移動を制御するために用いることができる。

１つの実施形態によると、ナビゲーション情報は、複数のマーカのそれぞれと複数のマーカにおける少なくとも１つの規定の他のマーカとの間の距離に対応する変位値と、方位角値とを含む。

１つの実施形態によると、マーカマップは複数のキーを含み、複数のキーにおける各キーは、複数のマーカの１つに対応し、車両が対応するマーカに位置する時に識別情報を格納する第１のデータフィールド、対応するマーカの予約情報を格納する第２のデータフィールド、対応するマーカの北方向、南方向、東方向、および西方向に配置された少なくとも１つのマーカを含む対応するマーカの近隣マーカに対応し、対応するマーカから対応する近隣マーカへ移動する車両の妥当性を決定するために用いられる情報を格納する第３のデータフィールド、対応するマーカから対応する近隣マーカへ移動する際に車両によって生じるコストを決定するために用いられる、対応するマーカから近隣マーカの各々までの距離を格納する第４のデータフィールド、および車両がマーカに商品ラックを配置することができるかを示す第５のデータフィールドを含む。

本開示の１つの態様によると、車両の回路によって、所定の位置に設置された複数のマーカにおける第１のマーカを検出すること、回路によって、検出された第１のマーカに基づいて第１のマーカ情報を生成すること、回路によって、生成された第１のマーカ情報を情報処理装置へ送信すること、回路によって、第１のマーカ情報と、第１のマーカ情報に応答する所定のナビゲーション情報とに基づいて情報処理装置によって生成される第１の制御情報を、情報処理装置から受信すること、および、回路によって、車両に、第１の制御情報に基づいて複数のマーカにおける第２のマーカへ移動させることが提供され、所定のナビゲーション情報は、第１のマーカに対する第２のマーカの位置を示す。

１つの実施形態によると、方法は更に、回路によって、第２のマーカを検出することと、回路によって、検出された第２のマーカに基づいて第２のマーカ情報を生成することと、回路によって、生成された第２のマーカ情報を情報処理装置へ送信することと、回路によって、第２のマーカ情報と、第１のマーカ情報に応答する所定のナビゲーション情報とに基づいて情報処理装置によって生成される第２の制御情報を、情報処理装置から受信することと、回路によって、車両に、複数のマーカにおける第３のマーカへ移動させることとを備え、所定のナビゲーション情報は、第２のマーカに対する第３のマーカの位置を示し、第２のマーカは第１のマーカと隣り合い、所定のナビゲーション情報は、第１のマーカと隣り合う複数のマーカにおける各マーカの相対位置を示す。また、複数のマーカの各々は機械可読パターンであり、機械可読パターンは、バーコードまたはクイックレスポンス（ＱＲ）コード（登録商標）を含み、複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む。

１つの実施形態によると、第１のマーカ情報を生成するステップは、回路によって、機械可読パターンから固有識別子を抽出することを備え、第１のマーカ情報は、第１のマーカに対する車両の方位情報、および第１のマーカに関連付けられた識別情報を含み、第１のマーカ情報は、車両によって捕捉される第１のマーカの画像を含む。

１つの実施形態によると、搬送経路は複数の経路セグメントに分割され、方法は更に、経路セグメントの各々の始点において、車両の移動を制御するための制御情報を受信することを備える。

本開示の態様は、所定の位置に設置された複数のマーカにおける第１のマーカを検出し、検出された第１のマーカに基づいて第１のマーカ情報を生成し、生成された第１のマーカ情報を情報処理装置へ送信し、第１のマーカ情報と第１のマーカ情報に応答する所定のナビゲーション情報とに基づいて情報処理装置によって生成される第１の制御情報を、情報処理装置から受信し、車両に、第１の制御情報に基づいて複数のマーカにおける第２のマーカへ移動させるように構成された回路を備える車両を提供し、所定のナビゲーション情報は、第１のマーカに対する第２のマーカの位置を示す。

１つの実施形態によると、回路は更に、第２のマーカを検出し、検出された第２のマーカに基づいて第２のマーカ情報を生成し、生成された第２のマーカ情報を情報処理装置へ送信し、第２のマーカ情報と第１のマーカ情報に応答する所定のナビゲーション情報とに基づいて情報処理装置によって生成される第２の制御情報を、情報処理装置から受信し、車両を複数のマーカにおける第３のマーカへ移動させるように構成され、所定のナビゲーション情報は、第２のマーカに対する第３のマーカの位置を示す。

１つの実施形態によると、第２のマーカは第１のマーカと隣り合い、所定のナビゲーション情報は、第１のマーカと隣り合う複数のマーカにおける各マーカの相対位置を示す。また、複数のマーカの各々は機械可読パターンであり、機械可読パターンは、バーコードまたはクイックレスポンス（ＱＲ）コード（登録商標）を含み、複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む。

１つの実施形態によると、回路は更に、機械可読パターンから固有識別子を抽出するように構成され、第１のマーカ情報は、第１のマーカに対する車両の方位情報、および第１のマーカに関連付けられた識別情報を含む。

１つの実施形態によると、第１のマーカ情報は、車両によって捕捉される第１のマーカの画像を含み、搬送経路は複数の経路セグメントに分割され、回路は更に、経路セグメントの各々の始点において、車両の移動を制御するための制御情報を受信するように構成される。

上記段落は、概括的な導入部として記載されるものであり、後述する特許請求の範囲を限定することは意図されない。説明される実施形態は、更なる利点とともに、添付図面と関連して示される以下の詳細な説明を参照することによって最も良く理解される。

例として提供される本開示の様々な実施形態は、同様の番号が同様の要素に言及する以下の図面を参照して詳しく説明される。

実施形態に係る商品取り扱いシステムのブロック図である。 図１の商品取り扱いシステムが実装される倉庫の図式表現である。 図１に示す商品取り扱いシステムの搬送車両の図式表現である。 図１に示す商品取り扱いシステムの商品ラックを搬送している車両を示す図式表現である。 図１に示す商品取り扱いシステムのオペレータステーションの図式表現である。 グラフ理論に従って商品取り扱いシステムのマーカ間の関係を示す図式表現である。 実施形態に係る典型的なマップデータベースを示す。 図１に示す商品取り扱いシステムの管理システムの機能部品を示すブロック図である。 図１に示す商品取り扱いシステムの車両の機能部品を示すブロック図である。 図１に示す商品取り扱いシステムのオペレータステーションの機能部品を示すブロック図である。 在庫プロセスのステップを示すフロー図である。 商品ピッキングプロセスを示すフロー図である。 注文履行プロセスを示すフロー図を示す。 注文履行プロセスを示すフロー図を示す。 車両のナビゲーション経路の補償のために用いられる方法を示す図である。 実施形態に係る経路補正において実行されるステップを示す典型的なフローチャートを示す。 １つの実施形態に係るコンピューティングデバイスのブロック図を示す。

典型的な実施形態が参照図面に示される。本明細書に開示される実施形態および図面は、限定的ではなく例示的であるものと見なされる。本技術の範囲およびそれに従う特許請求の範囲における限定はいずれも、図面に示され本明細書で説明される例に帰するものではない。

実施形態は主に、特定の実装において提供される特定のプロセスおよびシステムの観点から説明される。しかし、プロセスおよびシステムは、他の実装においても効果的に動作するものである。たとえば「実施形態」、「１つの実施形態」、および「他の実施形態」などの語句は、同じ実施形態または異なる実施形態を指してよい。実施形態は、特定の構成要素を有する方法および構成に関して説明される。しかし、方法および構成は、示されたものよりも多いまたは少ない構成要素を含んでよく、本開示の範囲から逸脱することなく、配置および構成要素の種類の変化がもたらされてよい。

典型的な実施形態は、特定のステップを有する方法に関連して説明される。しかし、方法および構成は、典型的な実施形態に反しない追加のステップおよび異なる順序のステップによって効果的に動作する。したがって本開示は、示された実施形態に限定されることは意図されず、本明細書で説明される原理および特徴と矛盾しない最も広い範囲と一致するものであり、特許請求の範囲によってのみ限定されることが意図される。

また、値の範囲が示される場合、範囲の上限値と下限値との間にある各値、および記載範囲内の他の任意の記載値または間にある値が本開示に包含される。記載範囲が上限値および下限値を含む場合、それらの値のいずれかを除外する範囲も含まれる。明確に記載されない限り、本明細書で用いられる用語は、当業者によって理解されるような平易かつ一般的な意味を有することが意図される。以下の定義は、本開示を理解する上で読者の助けとなることが意図されており、明示されない限り、そのような用語の意味を変更または限定することは意図されない。

図１を参照すると、商品取り扱いシステム１０が示される。システム１０は、たとえば顧客の注文などの注文に含まれ得るいくつかの商品を保持するように各々が構成された複数の商品ラック１２を含む。商品取り扱いシステム１０はまた、１または複数のオペレータステーション１４、および商品格納エリア２３と１または複数のオペレータステーション１４との間で商品ラック１２を搬送する複数の車両１６も含む。一例において、車両は、搬送車両または搬送ロボットであってよい。

搬送車両１６の移動は、たとえば無線通信ネットワークなどの通信ネットワーク１９を介してオペレータステーション（複数も可）１４および搬送車両１６と通信している管理システム１８によって管理される。１つの実施形態によると、管理システム１８は、ナビゲーションタスク、監視タスク、および本明細書で説明される他のタスクを制御するように構成された回路を含むたとえばサーバ（図８を参照して後述）などの情報処理装置を備える。動作中、注文を履行するために必要な商品は、少なくとも１台の搬送車両１６によって商品格納エリア２３とオペレータステーション１４との間で搬送される。注文は一部において、注文の商品を含む搬送ラック１２によって履行される。商品取り扱いシステムはまた、たとえば倉庫の床に配置され、１つの箇所から別の箇所へ車両１６をナビゲートすることができるマーカ２０ａおよび２０ｂも含む。入荷在庫プロセスおよび出荷注文履行プロセスは、この例において管理システム１８によって管理される。

図２は、図１の商品取り扱いシステム１０が実装され得る典型的な倉庫を示す。倉庫は、倉庫の床２１に配置された複数のマーカ２０ａ〜２０ｄを含む。図２は複数のマーカ２０ａ〜２０ｄを示し、これらは１つの実施形態によると、倉庫内のマーカの種類および／または位置に従って分類される。ただし、図を乱雑にしないように、マーカの一部のみ（２０ａ〜２０ｄ）が符号付けされている。特定のマーカ２０ａ、２０ｂ、２０ｃ、または２０ｄへの言及は、特定の符号付きマーカのいずれかを指してよい。

ラック１２は、商品格納エリア２３に格納される。この例において、マーカは、商品格納エリア２３とオペレータステーション（複数も可）１４ａ〜１４ｃとの間に概ね配置された倉庫マーカ２０ａとして分類され得る。ラックマーカ２０ｂはラック１２に関連付けられ、関連するラック１２が商品格納エリア２３内の規定の格納位置にある時、ラック１２の下にあるように配置される。待ち行列入口マーカ２０ｃは、ステーション待ち行列２２の入口位置に配置され、待ち行列出口マーカ２０ｄは、ステーション待ち行列２２の出口位置に配置される。ただし、マーカは、追加または代替として、たとえば壁など他の場所に配置されてもよいことが理解される。

１つの実施形態によると、マーカ２０ａ〜２０ｄは、機械可読バーコードの形式であってよい。ただし、たとえばＲＦＩＤタグ、ＱＲコード（登録商標）などのように個別に識別されることができる任意の機械可読マーカが、本明細書で説明される実施形態によって組み込まれてよい。各マーカ２０ａ〜２０ｄは、ナビゲーション情報にリンク付けされた関連する固有識別情報を有する。識別情報は、第１のマーカ２０ａ〜２０ｄの１つと、少なくとも１つの他のマーカ２０ａ〜２０ｄとの間の車両の移動を制御するために用いられ得る。各マーカ２０ａ〜２０ｄについて、ナビゲーション情報は、第１のマーカ２０ａ〜２０ｄと、第１のマーカ２０ａ〜２０ｄに関連付けられた他の全てのマーカ２０ａ〜２０ｄとの間の方向および距離を規定する。いくつかの実施形態において、他のマーカ２０ａ〜２０ｄは、第１の指定マーカ２０ａ〜２０ｄの対象エリアまたは生じ得る障害物に対応する。他のマーカ２０ａ〜２０ｄは、第１のマーカ２０ａ〜２０ｄと隣り合ってよく、または所定の距離の範囲内であってよい。

車両１６がマーカ２０ａ〜２０ｄの上または近隣を通過すると、ナビゲーション情報によって、各マーカ２０ａ〜２０ｄを識別することによって複数のマーカ２０ａ〜２０ｄの間でナビゲーション経路が規定され得る。１つの実施形態によると、たとえば１または複数のカメラなどのセンサが車両１６の底面に設置され得る。車両１６がマーカ２０ａ〜２０ｄを通行すると、センサが特定のマーカ２０ａ〜２０ｄを識別し、それによって車両１６の位置を識別する。

１つの実施形態によると、サーバは、倉庫内での車両１６のナビゲーション動作を制御する。具体的には、車両１６が特定のマーカの上を通行すると、車両１６はマーカの画像を捕捉し、捕捉した画像をサーバへ送信する。サーバはマーカ画像を受信すると、マーカ画像を処理し、マーカに関連付けられた固有識別情報を決定する。追加または代替の例として、１つの実施形態によると、車両１６は、マーカの画像を捕捉すると画像を処理して固有識別情報を決定し、その後、識別情報をサーバへ送信してもよい。

サーバは、受信したマーカ画像および／またはマーカに関連付けられた固有識別情報を処理し、（本明細書においてマーカマップとも称され、図７を参照して後述される）マップデータベースに格納されたナビゲーション情報を車両１６へ送信する。１つの実施形態によると、サーバは、ホップバイホップベースで車両１６へナビゲーション情報を送信する。具体的には、出発点マーカと到着点マーカとの間で車両１６をナビゲートするために、車両１６が通行すべき、出発点マーカと到着点マーカとの間のマーカのシーケンスを示す搬送経路が（サーバによって）計算される。また、車両１６が通行する所与のマーカのシーケンスに関して、車両が現在位置するマーカの画像またはマーカに関連付けられた固有識別を捕捉し、その後（サーバへ）送信する度に、サーバは、現在のマーカから、マーカのシーケンス内の次に後続するマーカへのナビゲーション情報を車両１６へ送信する。

１つの実施形態によると、出発点マーカと到着点マーカとの間で車両１６をナビゲートするために、サーバは、車両１６が通行すべき出発点マーカと到着点マーカとの間のマーカのシーケンスを示す搬送経路を計算する。その後、サーバは、マーカのシーケンスにおける複数の連続したマーカの通行に対応するナビゲーション情報を車両１６へ送信する。たとえばサーバは、マーカのシーケンスにおける５つの連続したマーカの通行に対応するナビゲーション情報を送信してよい。そうすることで、本開示は、商品取り扱いシステム１０の通信帯域幅を効率的に利用する有利な能力をもたらす。

理解されるように、各マーカ２０ａ〜２０ｄは、１つのマーカ２０ａ〜２０ｄから隣り合うマーカ２０ａ〜２０ｄへ移動するように車両１６に指示するために用いられる、自身に関連付けられたナビゲーション情報を有するので、マーカ２０ａ〜２０ｄは、任意の既定のパターンで倉庫の床２１に配置される必要はない。マーカ２０は、倉庫の形状に適した位置で床２１に配置されてよい。また、マーカ２０ａ〜２０ｄは、たとえば壁またはラックなど他の場所に配置されてもよい。

ナビゲーション情報は、衝突を回避し、複数の車両１６によるデッドロック状況を回避および解消するためにも用いられ得る。実施形態において、車両１６は、ナビゲーション経路に乗り入れる前に自身のナビゲーション経路の一部を予約し得る。一度に１台の車両１６のみがナビゲーション経路の同じ部分またはセグメントを占有し得るので、ナビゲーション経路の一部が予約される。ナビゲーション経路の一部が利用可能である場合、車両１６は予約を行い、自身の到着点に向かって移動を開始する。車両１６が自身の経路の予約部分を通過すると、同じ予約部分を他の車両１６が通行することが妨げられないように、予約部分の予約が解除される。１つの実施形態によると、車両１６は継続的に、自身のナビゲーション経路の連続した部分を予約し、通行済みの部分を予約解除する。

移動予約は、車両１６がナビゲーション経路に沿って通行する間に所定の数の経路セグメントを予約するために行われ得る。予約される経路セグメントの数は、たとえば角を曲がること、一方通行エリアを通行すること、障害物を周回すること、または同じナビゲーション経路の区分内で車両１６の付近にある他の車両を妨げるような任意の移動など、ナビゲーション経路の特定の領域に依存してよい。

１つの実施形態によると、たとえば交差点のように、２台の車両１６が同じ時間に同じ領域を通過する必要が生じ得る。この状況において、車両１６は、交差点を通行する自身のナビゲーション経路の一部を予約し得る。加えて、車両１６は、第１の車両１６が交差点を通行する間、他の車両１６が交差点を通行しないように、交差経路の交差部分に安全予約を取り付け得る。第１の車両１６が交差点を通行した後、第１の車両１６は、安全予約を解除し得る。

１つの実施形態によると、デッドロックマネージャは、第１の車両１６または障害物が第２の車両１６のナビゲーション経路において第２の車両１６の通行を妨げた場合、それを通知され得る。デッドブロックマネージャは、依存性グラフを作成し得る。グラフ内にサイクル、すなわち周期的依存性が存在する場合、デッドロックマネージャはデッドロック状況を制御し、サイクル内の車両１６の１つをループ外へ移動し得るので、他の車両１６は自身のナビゲーション経路を進行することができる。障害物が車両１６の進行を妨げている場合、デッドロックマネージャによってナビゲーション経路が変更されてよく、それによって車両１６の通路が再びナビゲーション経路上に戻される。

本明細書で説明される実施形態は、デッドロック状況の発生を回避することもできる。特定の車両１６に関してナビゲーション経路が計算されると、ナビゲーション経路は別のデータベースに格納されてよい。車両１６がナビゲーション経路の特定の区分またはセグメントを予約しようとする場合、検討中のその特定の区分またはセグメントに対して他の車両１６が計画されたナビゲーション経路を有するかを決定するために、データベース照会が実行される。そうである場合、潜在的なデッドロック地点が存在しないナビゲーション経路の区分に到達するまで、車両１６によって、重複経路の各セグメントの安全予約が行われる。安全予約が存在するセグメントまたは区分を他の車両１６が予約することはできない。実施形態において、他の車両１６は、安全ゾーンに出入りすることはできるが、安全ゾーン内で停車することはできない。デッドロック状況を回避するための実施形態は、実際のナビゲーション経路とともに、ナビゲーション経路を通行する時間も考慮する。

図３は、典型的な搬送車両１６を示す。車両１６は、搬送車両または搬送ロボットであってよい。車両１６は、本体３０および車輪３４を含み、車両１６の移動の速度および方向を制御するために車輪の少なくともいくつかは個々に制御可能である。本明細書で説明される実施形態によって様々な種類およびサイズの車輪３４が考えられ、これは床面の種類に依存してよい。たとえば、滑らかで硬い床面ではより小さな車輪が用いられ得るが、粗い床面ではより大きなゴム車輪が必要とされ得る。接触板３６は、搬送車両１６に載置された商品ラック１２を上昇または下降させるために本体３０に対して制御可能に上昇または下降することができ、それによって、商品格納エリア２３とオペレータステーション１４との間での商品ラック１２の搬送を容易にする。

図４には、車両１６によって搬送される商品ラック１２が示される。図示したように、接触板３６は上昇位置にあるので、床２１に対して商品ラック１２を持ち上げる。例において、商品ラック１２は、車両１６の接触板３６によってたとえば約５〜１０ｃｍ持ち上げられ得る。ただし、本明細書で説明される実施形態によって他の上昇寸法も考えられ、これは、たとえば床の種類、床の平滑度、床の水平度、および／またはラック１２によって運搬される商品の総重量などの要因に依存してよい。たとえば、ラック上の商品の重量が特定の所定の閾値重量を上回る場合、確実に車両の重心を低くするように、ラックの高さは（総重量に対応する）所定の高さレベルに設定され得る。そうすることで、本開示は、ラックが安定し、ラック上の商品が横転する恐れなく１つの場所から他の場所へ搬送され得ることを確実にする有利な能力をもたらす。また、商品ラック１２は１または複数の棚４０を含み、その各々が、商品４２を受け入れることができるいくつかの商品受入れ位置を組み込む。商品受入れ位置は更に区画に分けられてよく、その結果、ワークステーションに配属されたオペレータが商品を取り出す際のアクセス容易性がもたらされる。

次に図５を参照すると、典型的なオペレータステーション１４が示される。オペレータステーション１４が、商品格納エリア２３へ新たな商品を追加すること、および注文の一部または全部を履行するために商品格納エリア２３から商品を取り出すことのどちらかに用いられるか、または両方に用いられるかに依存して、ピックおよび／またはプットステーションとして構成され得る。

図５に示すように、オペレータステーション１４は複数の注文品箱４６を含み、その各々が、注文の一部を成す商品を受け入れるために用いられる。理解されるように、注文を履行するための商品の取出しが自動化される場合、注文品箱４６内への商品の載置はシステム１０によって制御され、システム１０は、同時に複数の注文を履行することができる。ピックおよび／またはプットステーションが複数の人間を収容できる場合も、複数の注文が同時に履行され得る。

図５のオペレータステーション１４は注文履行プロセス中が示され、ここで、注文の一部を成す商品４２は、オペレータによって商品格納エリア２３から取り出され、注文品箱４６内に載置される。注文品箱４６は、システム１０のサーバによって注文に割り当てられる。オペレータステーション１４は、オペレータステーション１４における動作を制御および調整するように構成された制御ユニット４８を含む。オペレータステーション１４は、たとえばレーザポインタなどのポインティングデバイス５０、および商品４２に付された識別子をスキャンするように構成されたスキャナ５２も含む。識別子は、ラインバーコードまたはたとえばＱＲコード（登録商標）などの二次元コードを含む任意のコンピュータ可読識別子であってよい。

商品４２が搬送車両１６によってオペレータステーション１４へ搬送されると、現在履行中の注文の一部を成す商品４２がポインティングデバイス５０によって識別される。この例において、レーザポインタが商品４２を指す。１つの実施形態において、レーザは、バーコードまたは二次元コードを含むがこれらに限定されないコードを指す。また、関連する複数の箱内に載置される複数の注文に関する商品４２を識別するために、複数のレーザカラーが用いられ得る。様々なレーザカラーまたは他の区別的識別方法の使用は、同じ商品ラック１２が、複数の注文を履行し得る同じまたは様々な商品を含む場合に有益である。

識別された商品４２をラック１２から取り出した後、オペレータステーション１４のオペレータは、スキャナ５２を用いて商品４２のバーコードまたは二次元コードをスキャンしてよい。そうすることで、商品４２が制御ユニット４８によって確認され、現在の注文に関する正しい商品４２がラック１２から取り出されたことが確実になる。その後、たとえば注文品箱４６に光を照射することによって、商品４２のための適切な注文品箱４６がオペレータに示される。様々なレーザカラーの場合、注文品箱４６への光は、対応する注文のために用いられたレーザカラーと一致するように構成されてよい。

１つの実施形態によると、各マーカ２０ａ〜２０ｄは、第１のマーカから、たとえば第１のマーカと隣り合う位置にあるマーカなど１または複数の他のマーカへのナビゲーション経路を識別する関連ナビゲーション情報を有する。この方法では、全てのマーカ２０ａ〜２０ｄに関してマーカマップが形成され、各マーカ２０ａ〜２０ｄは、１または複数の所定の経路に沿った他のマーカに対する第１のマーカの位置を効果的に規定する関連情報を有する。

図６は、マーカマップのグラフ理論表現６０を示す。グラフ６０は、（各々がマーカ２０ａ〜２０ｄの１つを表す）ノード６２と、辺６６とを含む。辺６６は、２つのマーカ２０ａ〜２０ｄの間に存在する連結部を示す。具体的には、２つのマーカを連結する辺６６は、車両１６が１つのマーカから他のマーカへ、他の任意の中間マーカを訪れることなく直接移動できることを示す。したがって、全体として考慮される辺は全て、互いに対するマーカ２０ａ〜２０ｄの位置を規定する。

１つの実施形態によると、サーバは、様々なマーカ間の連結関係に対応するデータを（本明細書においてマーカマップと称される）データベース内に維持してよい。データは、バーコード（または固有識別情報）をキーとして有し、バーコードに関連する特性を値として有するキー値型データベースに格納され得る。特性は、ナビゲーションデータ内の近隣マーカのリストなど、特定の要件が満たすことができるように規定され得る。したがって、この実施形態では、マーカ位置を空間内の絶対位置として格納するのではなく、マーカ位置が互いに関連して格納される。そうすることで、本開示は、マーカ間の連結関係を効率的に識別する有利な能力をもたらす。したがって、サーバは、出発点マーカと到着点マーカとの間のルートを決定するためにマーカマップを利用する。

１つの実施形態によると、マーカマップは、たとえば倉庫の床などの面における検出可能点に関連する全てのデータを格納するデータベースシステムである。各点は、テリトリ内の二次元エリアを表す。第１のマーカからのコードは、マーカマップ内にあることを検証され得る。コードは、マーカに符号化される固有の文字列によって表されたマップ構造における１つの点であるバーコードであってよい。第１のマーカと隣り合う、または付近の近隣マーカ２０ａ〜２０ｄもまた、他の全てのマーカに対する各マーカのマーカ情報を格納することによってリスト化され得る。そうすることで、他のマーカまでの距離を計算する際に消費される処理電力および時間の節減がもたらされる。

本明細書で説明されるマーカマップに関する実施形態は、マーカマップ内にバーコードが存在するかを決定し、更に、マーカの全ての近隣マーカのバーコードをリスト化することができる。特定のバーコードに関して、マーカマップは、特定のサイズのラックがバーコードの周囲を旋回した場合に影響を受ける近隣マーカをリスト化する。またマーカマップは、車両１６の状態に依存して、特定の車両１６が現在のバーコードから移動することができる近隣マーカもリスト化し得る。バーコードの各近隣に関して、マーカマップは、各近隣マーカにどのように到達するかに関するナビゲーション情報を格納する。ナビゲーション情報は、参照点に対して測定された向首角、移動距離などに関してよい。ただし、本明細書で説明される実施形態とともに他のナビゲーション識別が用いられ得ることを理解しなければならない。

したがって、マーカマップは、２つのマーカ間のナビゲーション経路に関する情報も格納してよい。第１のマーカから各近隣マーカ２０ａ〜２０ｄへのナビゲーション経路および指示もリスト化されてよい。ラック１２を運搬する上昇リフト、または下降リフトといった条件は、各近隣マーカ２０ａ〜２０ｄへのナビゲーション指示に含まれる。また、特定のサイズのラック１２の旋回によって影響を受ける任意の近隣マーカ２０ａ〜２０ｄがリスト化され得る。

以下で、本開示の車両ナビゲーションシステムと併用され得るマーカマップ構造が１つの実施形態によって説明される。本明細書で説明される実施形態は特定のマップ構造に限定されないことを理解しなければならない。特定のマップ構造は、二次元空間において表現される。しかし、他の実施形態は、本明細書で説明される特定のマップ構造の３次元（またはより高次元の）拡張を利用し得る。

表Ｉは、マーカに関して格納された情報を説明する典型的なマーカマップ構造を示す。説明のために、４つのマーカに対応する情報のみが表Ｉに示される。しかし、マーカマップは、他のバーコードに対応する情報を同様に格納してよいことを理解しなければならない。表Ｉにおいて、ＢＡＲＣＯＤＥは、マーカのバーコード番号に対応し、ＢＯＴＩＤは、現在バーコード上に位置する車両の識別番号に対応し、ＢＬＯＣＫＥＤは、バーコードが予約されているか否かを表し、ＮＥＩＧＨＢＯＵＲＳは、マーカの近隣に関する情報を格納する１２ビットの２値フィールドであり、ＺＯＮＥは、マーカが配置された倉庫内の地理的エリアを示し、ＳＩＺＥ＿ＩＮＦＯの数値は、現在のバーコードが４つの（東西南北の）近隣バーコードから離れている距離であり、ＳＴＯＲＥ＿ＳＴＡＴＵＳは、ラックをバーコードの上に置くことができるかを示す２値エンティティ（１はイエス、０はノー）である。

１つの実施形態によると、フィールドＮＥＩＧＨＢＯＲは１２桁の２値フィールドであり、バーコードのそれぞれ北、南、東、および西方向において直接隣り合った各バーコードにつき３桁が確保される。しかし、これらの方向の各々における近隣が必ずしも各バーコードに存在するものではない。（方向に対応する）３桁の数字の各々は、（北方向に関して述べられた）以下の情報、（ａ）北方向にバーコードが存在するか（１はイエス、０はノー）、（ｂ）車両がラックを伴わずに北のバーコードへ移動できるか（１はイエス、０はノー）、および（ｃ）車両がラックを伴って北のバーコードへ移動できるか（１はイエス、０はノー）を表す。

図７は、他の典型的なマーカマップからの部分データを説明する、１つの実施形態に係る表７０を示す。データは、各マーカ２０ａ〜２０ｄを他のマーカ２０ａ〜２０ｄに対して示すものである。マーカ２０ａ〜２０ｄの位置を示すナビゲーション情報および他のマーカ２０ａ〜２０ｄに対する相対位置がデータベースに格納される。

表７０は、出発点マーカを識別する固有情報を含む出発点フィールド７２、到着点マーカを指定する到着点フィールド７４、および搬送車両が出発点マーカと到着点マーカとの間で比較的平坦な地面の上、エレベータの中、傾斜面の上を移動する必要があるかを示す通行方法フィールド７６を含む。表７０は、搬送車両１６が出発点マーカから到着点マーカまでナビゲーション経路に沿って移動するために必要なナビゲーション情報を規定する方向、傾斜、および距離ナビゲーション値の詳細フィールド７８も含む。表７０は更に、かかる時間の観点からナビゲーション経路に沿って移動する搬送車両１６のそれぞれの「コスト」を示すコストフィールド８０を含む。

図７に示す典型的なデータにおいて、商品格納エリア２３は、いくつかの高さ（階数）の建物の上に配置されてよい。したがって、建物の様々な高さの間で移動するために、搬送車両１６はエレベータで移動することを必要とし得る。そのため、エレベータ内にマーカが配置されてよい。表７０に示すように、エレベータ内に配置されたマーカに関して、出発点フィールド７２および到着点フィールド７４は、たとえば２１階など、エレベータが位置する現在の階数を示す情報も含む。詳細フィールド７８は、エレベータを一意的に識別する情報も含む。他の実施形態において、各階に１または複数の車両１６が割り当てられてよい。その結果、車両１６を伴わず、ラック１２のみしかエレベータで移動する必要がない。ラック１２は、様々な車両１６によって積み降ろしされてよく、この場合、第１の車両１６が第１の階でエレベータにラック１２を載せてよく、第２の車両１６が第２の階でエレベータからラック１２を降ろしてよい。

図８を参照すると、商品取り扱いシステムの管理システムの機能部品を示す典型的なブロック図８１が示される。機能部品８１は回路によって実装され、たとえば関連するプロセッサ（複数も可）、メモリ、およびデータストレージ（図１６を参照して後述）を有する適切なコンピューティングデバイスなど、任意の適切な構成を用いる。実施形態において、機能部品８１は、１または複数のデータベースと連動する１つ（または複数）のサーバを含む。本明細書で説明されるサーバは、任意の特定の組み合わせまたはハードウェア回路および／またはソフトウェアに限定されないことを理解しなければならない。

機能部品８１は、たとえばハードディスクドライブ（ＨＤＤ）またはソリッドステートデバイス（ＳＳＤ）などのデータストレージデバイス８２を含み、これは図８においてデータベースとして表現されるが、理解されるように、任意の適切なデータストレージ構成が、本明細書で説明される実施形態によって考慮される。データストレージデバイス８２は、図６および図７および表Ｉにおいて表現された種類のマーカマップを示すマーカデータ８３を格納するように構成される。マーカマップ８３は、各マーカ２０ａ〜２０ｄに関連する固有識別情報および他のマーカ２０ａ〜２０ｄとのナビゲーション関係を含み得る。

機能部品８１は、新たな商品４２を倉庫へ追加するプロセスを管理し、在庫データベース８６に商品４２の現在の在庫を記録する在庫マネージャ８４も含む。在庫データベース８６は、倉庫内のラック１２のそれぞれの格納位置およびラック１２における商品４２の位置を示す情報も含む。このように、倉庫における全ての商品４２の格納位置が知られている。

注文生成器８８は、たとえば電子商取引ウェブサイトに関連するオンライン決済システムを介して受けた注文など、顧客からの注文の受領を管理する。作成された注文は、未決注文データベース９２に注文エントリとして注文の詳細を格納する注文マネージャ９０によって管理される。注文マネージャ９０は、たとえばネットワークインタフェース１１２を介してポストされた注文など、クライアントによってポストされた注文を処理する。ネットワークインタフェース１１２は、到来する注文を処理するためにそれらをフォーマット化し、１または複数の注文アプリケーションプログラミングインタフェース（ＡＰＩ）を用いてそれらをシステム１０へポストする。注文は、未決注文リストにポストされる。

１つの実施形態によると、注文マネージャ９０は、未決注文が処理される現在の条件下での最適な注文を見出すために、未決注文が処理される注文処理ループを形成する。大量の未決注文の場合、所望の結果を得るためにフィルタが用いられ得る。たとえば第１の典型的なフィルタは、到来ラックフィルタである。任意の未決注文が、既に注文処理ステーションにあるラックによって履行され得る場合、これらの注文が処理される機会を増やすためにこれらの注文は未決注文待ち行列のより高い位置に位置付けられ、必要なラック１２の少なくとも１つが注文処理ステーションに置かれたままである。また、第２の典型的なフィルタは、クライアント優先度フィルタ、または特別に指定された注文が優先サービスのためにフラグ付けされる注文優先度フィルタである。第３の典型的なフィルタは、古い注文が新しい注文より先に処理される年代フィルタ（すなわち、現在の注文がどれほどの期間システム内で未決であるか）である。

注文マネージャ９０は、注文データベース９２内の未決注文のタイミング履行も管理する。一例において、注文マネージャ９０は、注文を履行するためにオペレータステーション１４で注文品箱４６が利用可能であることを示すためのトリガ信号が生成されると、未決注文の処理を開始するように構成される。

注文を履行し得る商品在庫のセットを入手するために優先順位付きの未決注文リストが注文処理ループへ送られる。本明細書において注文履行リスト（ＯＦＬ）とも称される商品履行組み合わせ（ＩＦＣ）を形成するために、（関連するラック１２の識別を伴った）商品と様々な注文処理ステーションとの全ての組み合わせが生成される。各ＩＦＣについて、様々なラックの組み合わせ、すなわち、特定の注文処理ステーションにおける特定の注文に関する商品４２を含むラックの組み合わせが生成される。

注文マネージャ９０は、各未決注文の「コスト」を計算し、最小「コスト」に基づいて注文の履行を開始することによって、未決注文の履行の順序を管理する。注文「コスト」は、注文のために必要なラックの全てを指定のオペレータステーション１４へ搬送するのにかかる時間に関連する。ただし、他の実施形態において、他のコスト要因が所要時間と置き換えられ、または所要時間とともに考慮されてよい。

実施形態において、「コスト」は、距離コスト、ラックコスト、およびピックおよび／またはプレイスステーション（ＰＰＳ）負荷コストに副分割され得る。距離コストは、注文を履行するために選択されたラック１２とＰＰＳとの間で１または複数の車両１６が走行する総距離を含み得る。ラックコストは、注文を履行するために使用されるラック１２の総数を含む。より少ない数のラックを有するラック組み合わせによって、注文を履行する際の１または複数の車両１６の移動時間が最小化される。ＰＰＳ負荷コストは、最も近いまたは付近のＰＰＳと、各ＰＰＳにおける利用状況または最小待ち時間との間の最適バランスを見出すことを含む。ＰＰＳは、注文処理ステーションの一例である。ただし、本明細書で説明される実施形態によって、出荷のための商品を調達し、集め、および／または準備するように構成された任意のステーションが考えられる。注文処理ステーションは、製造環境において商品を調達し、集め、および／または転送するために使用されてもよい。

処理するために選択された注文ごとに、オペレータステーション１４が選択され、注文のために必要な商品４２を含む１または複数のラック１２が予約され、オペレータステーション１４における注文品箱４６が予約される。未決注文のコストを計算するために、まず商品４２を提供する可能性がある全てのラック１２が識別され、商品４２を保持する識別されたラックのラックセットリストが規定される。ラックセットリストは、商品４２ごとに規定される。その後、各ラックセットから選択されたラック１２を備えるラック組み合わせは、ラック組み合わせごとに以下のヒューリスティックを計算することによって、決定されたラックセットから選択される。
Ｈｅｕｒｉｓｔｉｃ，Ｈ＝Ｄｉｓｔａｎｃｅ／（１＋Ｎｏ．ｏｆ Ｃｏｍｍｏｎ Ｒａｃｋｓ） （１）
式中、Ｄｉｓｔａｎｃｅは、利用可能な注文品箱４６からラック組み合わせ内の全てのラック１２までの合計距離であり、Ｎｏ．ｏｆ Ｃｏｍｍｏｎ Ｒａｃｋｓは、複数のラックセットに共通のラック組み合わせ内のラック１２の数である。ヒューリスティックＨは、オペレータステーション１４の利用可能な全ての注文品箱について計算される。

１つの実施形態によると、最小または最も少ないヒューリスティックＨ値を有するラック組み合わせが選択され、選択されたラック組み合わせに関連する「コスト」は、組み合わせ内の全てのラック１２が、選択された注文品箱４６を有するオペレータステーション１４へ移動するために必要な時間である。さらに、選択されたラック組み合わせ内に含まれるラック１２は、予約データベース９４において予約および識別される。同様に、選択されたオペレータステーション１４およびオペレータステーション１４の選択された注文品箱４６もまた、予約データベース９４において、選択されたオペレータステーション１４および注文品箱４６を指定することによって予約される。

また、ブロック図８１の機能部品は、処理するための注文が選択されると、注文を履行するために少なくとも１つの車両１６を選択するタスクマネージャ９６も含む。車両１６は、利用状況、タスク優先度、およびタスクの「コスト」に基づいて選択される。利用可能な車両１６が識別され、識別された利用可能な車両１６の中から、現在空いている、または停止状態である車両１６、および注文に関して選択されたラック組み合わせ内のラック１２への車両１６の近接度に基づいて、車両のセットが選択される。選択された各車両１６は、商品格納エリア２３から特定のラック１２を取り出すタスクを割り当てられる。注文に関して選択された車両（複数も可）１６は、割当て車両データベース９８に格納される。

ブロック図８１の機能部品は、車両マップ構造において、選択された車両１６のためのナビゲーション経路の計画および予約を制御および調整するプランナ１００も含む。プランナ１００また、車両の発車／停車動作および車両の一時停車／停車解除動作に対する制御を含む、選択されたオペレータステーション１４と行き来する車両１６の移動の実行に関しても計画する。プランナ１００はまた、車両１６の充電状態の確認および充電が必要な車両１６の車両充電ステーションへの移動を含む、車両１６の充電を管理する。プランナ１００は、車両１６が準備完了状態になるまで待機すること、予約ステータスを変更およびタスクのステータスを更新すること、車両１６の充電レベルを確認すること、および充電のタスクを割り当てることを含むがこれらに限定されない、割り当てられたタスクの実行を計画する。車両１６の充電ステーションへの出入りのフローの管理もまたプランナ１００によって制御される。

プランナ１００は、注文を履行するために選択された車両のセットにおける車両１６の各々のための搬送経路を計算する経路計算機１０２を含む。各搬送経路は、車両１６が、商品格納エリア２３内のラック格納位置へ、およびラック格納位置とオペレータステーション１４との間でラック１２を搬送するために辿るマーカ２０ａ〜２０ｄのシーケンスを規定する。各車両１６のために計算された搬送経路は、規定経路データベース１０３に格納される。１つの実施形態によると、規定された各搬送経路の「コスト」は、最初の出発点から最終到着点までの移動にかかる時間に基づく。ナビゲーション経路の計算は更に、ラック１２のリフト状態にも依存してよい。たとえば１つの実施形態によると、リフト状態が上がっている場合、他のラック１２は全て、経路内に存在し得る物理的障害物とともに障害物として考慮される。ただし、リフト状態が下がっている場合、物理的障害物のみしか考慮される必要はない。

１つの実施形態によると、車両１６のための搬送経路は、Ａ^＊アルゴリズムを用いて計算される。アルゴリズムは、出発点マーカから到着点マーカまでのマーカ２０ａ〜２０ｄを通る効率的な経路を計算するために、図６に示すグラフ理論に従って規定され得る、マーカ２０ａ〜２０ｄの間の関係性を用いる。Ａ^＊アルゴリズムは最良優先探索を用い、所与の初期ノードから、考えられる１または複数の目的地から選択された１つの目的地ノードへの最小コスト経路を割り出す。Ａ^＊がグラフを横切ることによって部分経路のツリーが構築される。ツリーの（開集合またはフリンジと称される）リーフは、コスト関数によってリーフノードを順序付ける優先待ち行列に格納される。これは、目的地に到達するまでのコストおよび初期ノードからの移動距離のヒューリスティック推定値を結び付けるものである。

コスト関数は、ｆ（ｎ）＝ｇ（ｎ）＋ｈ（ｎ）によって表すことができ、式中、ｇ（ｎ）は、初期ノードからｎに至るまでの既知のコストであり、この値はアルゴリズムによって追跡される。パラメータｈ（ｎ）は、ｎから任意の目的地ノードに至るまでのコストのヒューリスティック推定値である。実際の最短経路を割り出すためのアルゴリズムの場合、ヒューリスティック関数は許容的でなくてはならず、これは、最も近い目的地ノードに至るまでの実際のコストを過大に見積もってはならないことを意味する。ヒューリスティック関数は問題特有であり、アルゴリズムのユーザによって提供される。

プランナ１００はまた、車両１６のために規定されたそれぞれの搬送経路に個々に従って各車両１６の移動を管理する車両ナビゲータ１０４も含む。車両ナビゲータ１０４は、搬送経路内のマーカ２０ａ〜２０ｄのシーケンスに沿った車両１６の移動を制御すること、および車両１６から受信する通信を処理することを請け負う。

車両１６がマーカ２０ａ〜２０ｄに到着すると、車両１６によってマーカ２０ａ〜２０ｄが検出され、たとえば検出されたマーカ２０ａ〜２０ｄに関連する固有識別情報および／または捕捉されたマーカ画像などのマーカ情報が、無線通信ネットワーク１９を介して車両ナビゲータ１０４へ伝達される。受信した情報に基づいて、車両ナビゲータ１０４は、識別されたマーカ２０ａ〜２０ｄが搬送経路内の予想されるマーカ２０ａ〜２０ｄに対応することを確認し、搬送経路内の後続マーカ２０ａ〜２０ｄへ車両１６を向けるために車両１６へナビゲーション情報を伝達する。一例において、ナビゲーション情報は、マーカデータベース８３に格納されたナビゲーション情報から導出された方位値および距離値の形式であり、図７に表形式で示される。すなわち、車両ナビゲータ１０４は、個別のマーカ２０ａ〜２０ｄごとに（すなわち、上述したようにヒップバイホップベースで）車両１６へナビゲーション情報を送信する。

車両ナビゲータ１０４はまた、マーカ２０ａ〜２０ｄに対する車両１６の重心の位置、およびマーカ２０ａ〜２０ｄに対する車両１６の方位も計算する。位置は、たとえば図９に示すセンサ／カメラ１３４などのセンサおよび／またはカメラによって捕捉された画像を用いて計算され得る。検出されたマーカ２０ａ〜２０ｄに対する車両１６のオフセット位置は、図１４を参照してその場所から計算され得る。車両１６の現在位置は、車両位置データベース１０５に格納される。その結果、プランナ１００は、全ての車両１６の位置を常に知ることになる。

車両の経路に沿って車両１６をナビゲートすることに加えて、車両ナビゲータ１０４は、車両１６からのメッセージの受信および処理もする。１つの実施形態によると、車両１６から受信される第１の種類のメッセージは、開始メッセージである。開始メッセージは、車両１６が始動または再起動すると車両ナビゲータ１０４へ送信される。開始メッセージは、スキャンされたマーカに対応する情報を含むデータパケットとして送信されてよい。スキャンされたマーカが有効である場合、開始メッセージは車両マネージャ１１０によって処理され、車両マネージャ１１０はその後ナビゲーション方向を車両へ送信する。

車両ナビゲータ１０４によって受信される車両１６からの第２の種類のメッセージは、警告メッセージである。車両１６が、車両１６のために予約されていない有効ナビゲーションマーカに到達すると、車両ナビゲータ１０４によって警告データパケットが受信される。この状況において、車両１６が位置するナビゲーションマーカが予約されてよく、可能であれば、ナビゲーション経路内の次のナビゲーションマーカも予約される。しかし、現在のナビゲーションマーカが他の車両１６によって予約されている場合、第１の車両１６は、更なる移動を阻止される。

車両ナビゲータ１０４によって受信される車両１６からの第３の種類のメッセージは、情報メッセージである。情報データパケットは、車両１６がラック１２を持ち上げ、または運搬中である場合、ラック１２の位置を更新するために車両ナビゲータ１０４へ送信される。車両ナビゲータ１０４は、ラック１２の動きに関係している人員および車両マネージャ１１０に、完了すべき任意の関連タスクを確認するように通知する。また情報パケットは、旧位置が存在する場合それを予約解除し、順番予約が完了するとそれを予約解除することもできる。車両ナビゲータ１０４は、たとえば割当て車両データベース９８、車両位置データベース１０５、規定搬送経路データベース１０３、または予約経路およびマーカデータベース１０８などの関連車両データベースにおける車両１６の情報を更新する。また車両ナビゲータ１０４は、到着点ナビゲーションマーカに到達したか、または次の予約ナビゲーションマーカに到達したかを決定することもできる。

車両ナビゲータ１０４によって受信される車両１６からの第４の種類のメッセージは、エラーメッセージである。無効ナビゲーションマーカのバーコードが車両１６によって読み取られると、車両ナビゲータ１０４によってエラーメッセージが受信される。車両１６への指示が車両１６によって処理されることができなかった場合も、車両ナビゲータ１０４へエラーパケットが送信され得る。

また車両ナビゲータ１０４は、衝突が回避されるように車両１６の移動を管理するようにも構成され得る。１つの実施形態において、衝突管理は経路およびマーカ予約を管理することによって実現され、それによって（本明細書においてセグメントと称される）２つのマーカ間の各ナビゲーション経路は、車両１６が到着する直前に予約される。ただし、後続するナビゲーション経路（すなわちナビゲーション経路のセグメント）内での移動は、ナビゲーション経路が予約されるまで許可されない。ナビゲーション経路が他の車両１６によって既に予約されている場合、ナビゲーション経路を予約しようと望む車両１６は待機状態に入る。ただし、特定の実施形態において、たとえば既存の予約を用いて履行中である注文よりも高い優先度が特定の注文に割り当てられている場合、優先度情報に基づいて過去の予約が取り消され、再スケジュールされてもよい。１つの実施形態によると、倉庫の特定の区分における特定の経路は、修理またはサポートのために取り除かれてよい。

また、各車両１６のためのエンドツーエンド（すなわち出発点マーカから到着点マーカまでの）搬送経路は一度には予約されないので、２台の車両１６が同様の経路に沿って逆方向に移動しようと望むことによるデッドロック状況が存在し得ることを理解しなければならない。デッドロックを解消するために、一方の車両１６が経路を外れて移動する必要がある。したがって、車両ナビゲータ１０４は、デッドロック状況に関与する車両１６の一方を指定経路から離れるように能動的に制御し、それによってデッドロック状況における他方の車両１６が自身の指定搬送経路に従って移動することを可能にする。

１つの実施形態によると、車両ナビゲータ１０４は、デッドロック状況の発生を能動的に回避するように構成され得る。車両ナビゲータ１０４が車両１６のためにマーカ２０ａ〜２０ｄを予約しようと試みる場合、車両ナビゲータ１０４は、他の車両１６もまた、マーカ２０ａ〜２０ｄを通過するように規定された搬送経路を有するかを確認する。そうである場合、車両ナビゲータ１０４は、安全予約として車両１６のためにマーカ２０ａ〜２０ｄを予約する。安全予約として予約されたマーカ２０ａ〜２０ｄに関して、他の車両１６が安全予約されたマーカ２０ａ〜２０ｄから出ることができるマーカ２０ａ〜２０ｄも予約されていない限り、他の車両１６は安全予約中のマーカ２０ａ〜２０ｄを予約することはできない。すなわち、安全予約が行われると、他の車両１６は、安全予約された領域に留まることを許可されない。また、予約されたマーカ２０ａ〜２０ｄおよびナビゲーション経路に基づいて車両１６の移動を管理すること、および車両１６の移動のタイミングを制御することによって、衝突およびデッドロックが回避され得る。その結果、車両１６を待機させること、または車両１６の移動速度を能動的に修正することによって、衝突が回避され得る。

本開示の実施形態によると、ナビゲーション経路を処理する際、車両ナビゲータ１０４によってナビゲーション変数が用いられ得る。本明細書においてセグメント長さ変数と称される第１の変数は、車両１６のために予約されるナビゲーション経路の長さに対応する。本明細書において予約距離変数と称される第２の変数は、ナビゲーション経路の終点までの距離に対応する。ナビゲーション経路が決定された後、ナビゲーション経路内の第１のセグメント長さが予約される。次のセグメントとともに、次の予約が行われるナビゲーションマーカが計算される。車両１６が次の予約位置に到達すると、他の予約距離が計算される。上記プロセスは、車両１６がナビゲーション経路の到着点に到達するまで継続する。

また、ナビゲーション経路内に曲がり角が存在する場合、近隣ナビゲーションマーカに関して予約距離が計算される。予約されるナビゲーション経路セグメント内に、移動中の車両１６または角を曲がっている車両１６が発見された場合、予約は行われず、不履行位置が計算される。また、１つの実施形態によると、到着点にアイドル車両がある場合、計算を完了することができない。車両１６はアイドル状態に設定されるか、あるいは待機状態に入る。１つの実施形態によると、予約されるセグメント内にアイドル車両１６が発見された場合、新たな経路が計算される。

プランナ１００はまた、車両１６間の衝突を回避するために、マーカ２０ａ〜２０ｄの予約およびマーカ２０ａ〜２０ｄ間のナビゲーション経路を管理する予約マネージャ１０６も含む。プランナ１００は、予約経路およびマーカデータベース１０８内に、予約されたマーカ２０ａ〜２０ｄおよびナビゲーション経路を示す情報を格納する。

プランナ１００はまた、車両の発車および停車動作を制御し、車両１６の接触板３６の動きを上昇位置と下降位置との間で制御する車両マネージャ１１０も含む。車両マネージャ１１０はまた、車両１６の充電レベルも管理し、これは、車両１６の充電状態を確認することおよび充電が必要な車両１６の車両充電ステーションへの移動を管理することを含む。また、図８に示すように、管理システム１８のブロック図８１の機能部品は、管理システム１８、車両１６、およびオペレータステーション１４の間のネットワーク通信を容易にするネットワークインタフェース１１２も含んでよい。

たとえば搬送車両または搬送ロボットなどの車両１６の機能部品１１８が図９に示される。機能部品１１８は、車両１６および管理システム１８の各々とオペレータステーション１４との間のネットワーク通信を容易にするネットワークインタフェース１２０を含む。（図１６を参照して後述される、回路によって実装される）マイクロコントローラ１２２は、車両１６における動作を制御および調整し、たとえばマーカ２０ａ〜２０ｄの検出を管理すること、車両ナビゲータ１０４から受信した指示に従って車両の移動の制御を管理すること、およびマーカ２０ａ〜２０ｄ間で決定された搬送経路に、ベジェ曲線を用いて再計算されたナビゲーション経路などの補償経路を適用することなどの専用タスクを実行する。マイクロコントローラ１２２は、車両の車輪３４に付随する１または複数のモータ１２６を制御するためにモータドライバ１２４と通信し、それによって車両１６の速度および方向を制御する。

機能部品１１８はまた、マイクロコントローラ１２２からの指示に応答して接触板３６を制御可能に上昇または下降させるリフトデバイス１３０も含む。マイクロコントローラ１２２からの指示は、車両マネージャ１１０から受信した指示に応答して生成され得る。

機能部品１１８はまた、車両１６がマーカ２０ａ〜２０ｄに近づくとマーカ２０ａ〜２０ｄを検出するように構成された、たとえばカメラまたはＲＦＩＤリーダなどの少なくとも１つのセンサ１３４も含む。センサ／カメラ１３４は、マーカ２０ａ〜２０ｄに関連する固有識別情報を取得し得る。取得された固有識別情報はマイクロコントローラ１２２によってプランナ１００へ伝達され、それによって車両１６の現在位置が決定され得る。

センサ（複数も可）／カメラ１３４はまた、車両１６の位置と検出されたマーカ２０ａ〜２０ｄの位置との間のオフセットを決定するためにも用いられ得る。オフセットは、検出されたマーカ２０ａ〜２０ｄと搬送経路内の後続マーカ２０ａ〜２０ｄとの間で既定された搬送経路を修正するために用いられ得る（図１４を参照して後述）。これは、マーカ２０ａ〜２０ｄを含む画像を捕捉すること、および画像を処理するためにプランナ１００へ転送することによって実現される。１つの実施形態において、オフセットは車両１６によって計算される。車両１６に対する捕捉画像の位置および方位が知られるので、車両１６に対するマーカ２０ａ〜２０ｄの位置および方位を決定することが可能である。

機能部品１１８はまた、車両１６がラック１２を搬送している場合、重量測定値を生成するはかり１３８も含む。重量測定値は、たとえば車両１６によって搬送中のラック１２の重量を考慮した適切な加速および減速パラメータなど、荷積み車両１６のための移動パラメータを計算するためにマイクロコントローラ１２２によって用いられ得る。移動パラメータは、接触板３６が上昇位置にあるか下降位置にあるかに基づいて計算されてもよい。

はかり１３８はまた、空のラック１２の既知の重心、各商品４２の既知の重量、およびラック１２における商品４２の位置を用いることによって、重量分布プロファイルを決定するためにも用いられ得る。重量分布プロファイルは、ラックおよび積載商品４２の重心を計算するために用いることができ、これはその後、荷積みラック１２の重心が規定の範囲内にあることを確実にするために用いられる。そうすることで、荷積みラック１２が搬送中に過度にバウンドしないことが確実である。

１つの実施形態によると、荷積みラック１２の重心のｚ成分は、ラック１２における商品４２の位置を調整することによって、重心が高すぎないように操作され得る。荷積みラックの重心（ＣＯＧ）は、ラック上の基準点およびラック１２における商品４２の分布（すなわち各商品のＣＯＧ）に基づいて計算され得ることを理解しなければならない。加えて、重心のｘ−ｙ成分に関連して、商品４２がラック１２に追加され、またはラック１２から取り出される度に、ラック１２における商品４２受入れ位置の全てについてコスト値が計算され得る。コスト値は、荷積みラック１２が重心からずれている量に対応してよい。

マイクロコントローラ１２２は、プランナ１００からの指示に応答するモータ１２６の制御、プランナ１００からの指示に応答するリフトデバイス１３０の制御、センサ／カメラ１３４およびはかり１３８との通信の管理、およびネットワークインタフェース１２０との通信の管理を含む、車両１６における規定の機能を実装するように構成されてよい。

オペレータステーション１４の機能部品１３９が図１０に示される。機能部品１３９は、オペレータステーション１４、管理システム１８、および車両１６の間のネットワーク通信を容易にするネットワークインタフェース１４０を含む。制御ユニット１４２は、オペレータステーション１４における動作を制御および調整する。制御ユニット１４２は、たとえば入荷商品プロセス１４４および出荷商品プロセス１４６などの規定の機能を実装するように構成される。

入荷商品プロセス１４４は、物理的意味および電子的意味の両方において、商品取り扱いシステム１０内への新たな在庫商品の受取りを管理する。物理的意味では、選択されたラック１２に新たな商品４２が載置され、ラック１２が商品格納エリア２３内の格納位置へ搬送される。電子的意味では、商品４２の存在および位置が在庫データベース８６に記録される。

出荷商品プロセス１４６は、物理的意味および電子的意味の両方において、商品取り扱いシステム１０からの商品４２の取出しを管理する。物理的意味では、注文の一部を成す商品４２が、商品格納エリア２３内のラック１２から取り出される。電子的意味では、取り出された商品の記録が、在庫データベース８６から消去される。

機能部品１３９はまた、ポインティングデバイス５０およびスキャナ５２も含む。ポインティングデバイス５０は、ラック（複数も可）１２からの正しい商品（複数も可）４２の取出しおよびラック（複数も可）１２の正しい位置への商品４２の載置を調整するために入荷商品プロセス１４４および出荷商品プロセス１４６に関連して動作する。スキャナ５２は、注文履行中に商品４２がラック１２から取り出され、または新たな在庫の追加中にラック１２に載置されると、たとえば商品４２のバーコードなど、商品４２の識別子をスキャンするように構成される。スキャンされたバーコードによって、オペレータステーション１４は、スキャンされた商品４２が正しいかを検査および確認することが可能である。コードをスキャンすることに加えて、またはその代替として、スキャンされた商品４２が正しいかを確認するために物体認識デバイスが用いられ得る。

図１１は、商品取り扱いシステム１０によって実装される在庫プロセスにおいて実行されるステップを示す典型的なフローチャート１６０を示す。

ステップ１６２において、商品４２の新たな在庫が倉庫に到着する。ステップ１６４において、到着した商品４２ごとに、オペレータステーション１４のオペレータは、スキャナ５２を用いて、たとえば商品４２のバーコードなどの識別子をスキャンする。オペレータステーション１４は、商品４２を示す情報を管理システム１８の在庫マネージャ８４へ伝達する。在庫マネージャ８４は、商品４２の記録を在庫データベース８６に追加し、商品格納エリア２３における商品４２の所望の位置をオペレータステーション１４へ伝達する。たとえば、商品４２が格納されるべきラック１２およびラック１２における商品４２の載置位置がオペレータステーション１４へ伝達される。実施形態において、ラック１２における全商品４２の構成を最適化するために、１または複数の商品４２の配置を変更するように在庫マネージャ８４によって指示が与えられ得る。

また、ステップ１６６において、管理システム１８から受信した位置の通信に基づいて、入荷商品プロセス１４４は車両１６に、商品格納エリア２３から関連ラック１２を取り出すように指示する。ラック１２がオペレータステーション１４へ搬送１６８された後、ステップ１６８において、ポインティングデバイス５０は、商品４２が載置されるべきラック１２上の位置を示す。たとえば、ステップ１７０において、レーザポインタは、商品４２が載置されるべきラック１２上の位置を指し得る。

ステップ１７２において、他の商品４２が同じラック１２に格納されるかが決定される。他の商品４２が同じラック１２に載置される場合、ステップ１７４において、追加の商品４２がスキャンされ、ポインティングデバイス５０によってオペレータに示されたラック１２における特定の位置に載置される。同じラック１２に載置される追加の商品４２がない場合、ステップ１７６において、ラック１２は、商品格納エリア２３内の規定の格納位置へ返送される。ステップ１７８において、新たな在庫に追加の商品４２が存在するかが決定される。ステップ１７８において、商品格納エリア２３に格納される新たな在庫商品４２ごとにプロセスは繰り返される。新たな在庫に追加の商品４２がない場合、ステップ１８０においてプロセスは終了する。

図１２は、商品取り扱いシステム１０によって実装される商品ピッキングプロセスのステップ１９２〜２１２を説明するフロー図１９０を示す。１つの実施形態によると、注文処理サーバは、到来する注文を注文待ち行列に追加する。ステップ１９２において、管理システム１８の注文マネージャ９０によって、注文は処理のためにトリガされる。注文処理サーバは、注文待ち行列内の注文を履行するために最適なラック（すなわち、最小ラックコストを有するラック）のセットを決定する。最適なラックのセットが決定されると、タスク割当てサーバは、在庫取出しプロセスのためにオペレータステーション１４へラックのセットを運搬するための最適な車両のセットを計算する。経路計算サーバは、ナビゲーション経路内で重複する領域がない、選択された車両のための最も効率的なナビゲーション経路を計算する。

注文の一部を成す商品４２に関して、ステップ１９４において、車両ナビゲータ１０４は、注文内の商品４２を含む選択されたラック１２を商品格納エリア２３から取り出すように車両１６に指示する。ステップ１９４は、マーカ２０ａ〜２０ｄの間を移動するための連続ナビゲーション経路を示すように車両１６に順次ナビゲーション指示を通信することによって実現され得る。車両１６が選択されたラック１２に到達すると、選択されたラック１２は、選択されたラック１２の下にあるナビゲーションマーカを用いて識別される。車両ナビゲータ１０４は、ラックのリフトおよび搬送中に選択されたラック１２が確実に位置を合わせられるように、ナビゲーションマーカからのデータを用いて車両の重心と選択されたラック１２の中心との位置を合わせる。選択されたラック１２は、車両１６のリフトヘッドの高さを高くすることによって地面から持ち上げられる。一例として、選択されたラックは、搬送のために地面から約５〜１０ｃｍ持ち上げられる。

ステップ１９６において、車両１６は、商品４２を含む選択されたラック１２をオペレータステーション１４へ搬送する。車両は、関連する車両１６ごとに過去に計算された加速および減速プロファイルを用いて、選択されたラック１２をオペレータステーション１４へ運搬する。ステップ１９８において、選択されたラック１２がオペレータステーション１４に到着すると、各車両１６の制御は、待ち行列管理サーバへ移行される。待ち行列管理サーバは、車両１６を注文処理待ち行列に移動させる。車両１６がオペレータステーション１４のピックポイントに到達すると、ステップ２００において、ポインティングデバイス５０は、商品４２が載置されるラック１２上の位置を指す。一例において、ラック１２上の位置にレーザポインタが向けられる。

ステップ２０２において、オペレータステーション１４のオペレータは、識別された商品４２をラック１２から取り出し、商品４２に設けられた識別子をスキャンする。それに応答して、ステップ２０４において、オペレータステーション１４は、正しい商品４２が選択されたかを確認するために商品４２を示す情報を伝達する。商品が正しいと確認された場合、商品４２を示す情報は、管理システム１８の在庫マネージャ８４へも伝達され、在庫マネージャ８４は、在庫データベース８６から商品４２の記録を消去する。

ステップ２０６において、他の商品４２が同じラック１２に格納されているかが決定される。追加の商品４２が同じラック１２から取り出される場合、ポインティングデバイス５０は、取り出される追加の商品４２があるラック１２上の位置を示し、追加の商品４２ごとに上記プロセスが繰り返される。

また、１つの実施形態によると、ラック上の商品４２は、最適な配置ではないことがある。たとえば、追加された商品４２の在庫は、元々最適な位置に載置されていてよい。しかし、更に追加された在庫によって、ラック空間が可能な最大限まで利用されず、または重心がずれてバランスを欠くことがある。したがって、在庫マネージャ８４は、ラック１２上の商品４２の一部または全部を再構成するように指示を送信してよい。

また、同じラック１２から取り出される追加の商品４２がない場合、ステップ２０８において、ラック１２は、商品格納エリア２３内の規定の格納位置に返送される。ステップ２１０において、注文内に追加の商品４２があるかがステップ２１０において決定される。プロセスは、商品格納エリア２３から取り出される注文内の追加の新たな商品４２ごとに繰り返される。注文内に追加の商品４２がない場合、ステップ２１２においてプロセスは終了する。

次に図１３Ａおよび図１３Ｂを参照すると、注文履行プロセスおよび車両の移動の制御において実行されるステップを示すフローチャート２２０が示される。

ステップ２２２において、たとえば電子商取引ウェブサイトを介して、注文生成器８８を用いて管理システム１８において注文が受信される。受信された注文は、注文マネージャ９０によって注文データベース９２に記録され、ステップ２２４において注文待ち行列に入れられる。ステップ２２６において、注文がトリガされたかが決定される。注文が履行のためにトリガされた場合、ステップ２２８においてタスクマネージャ９６は、上述したヒューリスティック算法に基づいて注文の履行のために好適なラック組み合わせを決定する。ステップ２３０において、タスクマネージャ９６は、ラック１２に対する車両１６の位置に基づいて、決定されたラック１２の各々の取出しを実行するための車両１６の最適なセットを決定する。

ステップ２３２において、ラック組み合わせ内の各ラック１２について、管理システム１８における経路計算機１０２は、ラック１２の取出し中に各車両１６が辿る搬送経路を計算する。また、商品格納エリア２３へ戻る車両１６の搬送経路も決定される。実施形態において、搬送経路は、Ａ^＊アルゴリズムを用いて計算される。搬送経路は、車両１６が自身の現在位置から商品格納エリア２３内の関連ラック１２へ移動するために通過するマーカ２０ａ〜２０ｄのシーケンス、または車両１６が商品格納エリア２３からオペレータステーション１４へ移動するために通過するマーカ２０ａ〜２０ｄのシーケンスを規定する。

ステップ２３４において、商品格納エリア２３からラック１２を取り出すために割り当てられた各車両１６について、車両ナビゲータ１０４は、現在のマーカ２０ａ〜２０ｄから規定搬送経路における後続マーカ２０ａ〜２０ｄへ移動するためのセグメント化ナビゲーション経路を示すナビゲーション指示を車両１６へ伝達する。そのようなナビゲーション情報は、たとえば方位形式の方向情報、および現在のマーカ２０ａ〜２０ｄと後続マーカ２０ａ〜２０ｄとの間の距離を示す距離情報を含む。ステップ２３６において、車両１６が後続マーカ２０ａ〜２０ｄに到着すると、車両１６はセンサ１３４を用いて後続マーカ２０ａ〜２０ｄに関連する固有識別情報を読み取り、後続マーカ２０ａ〜２０ｄを示す情報を車両ナビゲータ１０４へ伝達する。

ステップ２３８において、取り出されることが決定されたラック１２のマーカ２０ｂに車両１６が到着したかが決定される。後続マーカ２０ａ〜２０ｄが決定されたラックマーカ２０ｂではない場合、車両ナビゲータ１０４は、車両１６が規定搬送経路において現在のマーカ２０ａ〜２０ｄから更に後続のマーカ２０ａ〜２０ｄへどのように移動するかを示す追加のナビゲーション指示を車両１６へ伝達する。このプロセスは、決定されたラックマーカ２０ｂの後続マーカ２０ａ〜２０ｄに到着するまで継続する。マーカ２０ａ〜２０ｄが全て避けられ、車両１６が一時的に「行方不明」になると、車両１６は停車するように指示され、および／または車両１６の位置センサが検索され得る。

車両１６が、取り出すべきラック１２の下に配置されたラックマーカ２０ｂに到着すると、位置決定器１３２は、ラック１２に対する車両１６の位置を決定し、必要であれば、ステップ２４０において、車両１６とラック１２との位置が正確に合うように車両１６はラック１２に対して移動する。車両１６とラック１２との位置を正確に合わせる際、車両１６のセンサ１３４が位置決定器１３２を補助する。位置合わせ後、ステップ２４２において、車両マネージャ１１０は、接触板３６を下降位置から上昇位置へ上げることによってラック１２を地面から持ち上げるように車両１６に指示するための通信を車両１６へ送信する。

車両１６は、更なる規定搬送経路に沿ってオペレータステーション１４へ向かって移動する。ステップ２４４において、車両ナビゲータ１０４は、現在のラックマーカ２０ｂから規定搬送経路における後続マーカ２０ａ〜２０ｄへどのように移動するかを車両１６に示すナビゲーション指示を車両１６へ伝達する。ナビゲーション情報は、たとえば方位形式の方向情報、および現在のマーカ２０ａ〜２０ｄと後続マーカ２０ａ〜２０ｄとの間の距離を示す距離情報を含み得る。車両１６が後続マーカ２０ａ〜２０ｄに到着すると、ステップ２４６において、車両１６はマーカ２０ａ〜２０ｄを読み取り、マーカ２０ａ〜２０ｄを示す情報を車両ナビゲータ１０４へ伝達する。ステップ２４８において、車両１６が待ち行列入口マーカ２０ｃに到着したかが決定される。車両１６が待ち行列入口マーカ２０ｃに到着していない場合、後続マーカ２０ａ〜２０ｄが待ち行列入口マーカ２０ｃになるまでプロセスは継続する。

車両１６が待ち行列入口マーカ２０ｃに到着すると、ステップ２５０において、車両１６の移動に対する制御は、管理システム１８からオペレータステーション１４へ移行する。ステップ２５２において、オペレータステーション１４は、オペレータに隣接するピックポイントへ順次移動するように、ステーション待ち行列２２内の車両１６および関連ラック１２に指示する。ステップ２５４において、車両１６がピックポイントに到着したかが決定される。ラック１２を有する車両がピックポイントに到着すると、ステップ２５６において、ポインティングデバイス５０は、取り出すべき商品４２が存在するラック上の位置を示す。これは、レーザポインタをラック１２上の位置に向けることによって実行され得る。ステップ２５８において、オペレータステーション１４のオペレータは、商品４２を取り、スキャンする。オペレータステーション１４は、ステップ２６０において、ラック１２から取り出された商品４２が正しいかを確認する。商品４２が正しい場合、オペレータは、割り当てられた注文品箱４６内に商品を載置する。

ステップ２６２において、ラック１２から更に取り出す商品４２があるかが決定される。更に取り出す商品がある場合、同じラック１２から取り出される追加の商品４２ごとにプロセスは繰り返される。ラック１２から更に取り出される商品４２がない場合、ステップ２６４において、車両１６およびラック１２はオペレータステーションによって制御され、ステーション待ち行列２２の出口における待ち行列出口マーカ２０ｄへ移動する。車両が待ち行列出口マーカ２０ｄを検出すると、ステップ２６６において、車両の移動に対する制御は、オペレータステーション１４から管理システム１８へ移行する。

ステップ２６８において、車両ナビゲータ１０４は、現在のマーカ２０ａ〜２０ｄから次のマーカ２０ａ〜２０ｄへの移動の方向および距離を示す移動情報を車両１６へ伝達する。ステップ２７０において、車両１６がマーカ２０ａ〜２０ｄに到着すると、車両１６はマーカ２０ａ〜２０ｄを読み取り、マーカ２０ａ〜２０ｄを示す情報を車両ナビゲータ１０４へ伝達する。

ステップ２７２において、車両１６がラックマーカ２０ｂに到着したかが決定される。車両１６がラックマーカ２０ｂに到着していない場合、ラックマーカ２０ｂに到達するまでプロセスは繰り返される。車両１６は、ラック１２を商品格納エリア２３内の関連格納位置へ返送する。ステップ２７４において、商品格納エリア２３内の格納位置において車両マネージャ１１０は、接触板３６を下げることによってラック１２を地面に降ろすように車両１６に指示するための通信を車両１６へ送信する。

ステップ２７６において、他のラック１２から更に取り出される商品４２があるかが決定される。他のラック１２からの追加の商品４２が注文に含まれる場合、注文内の全ての商品４２が注文品箱４６内に載置されるまで、商品格納エリア２３からオペレータステーション１４へ、および再び商品格納エリア２３への各他のラック１２の搬送についてプロセスが繰り返される。全ての商品４２が注文品箱４６内に載置されると、ステップ２７８において注文は完了する。

図１３Ａ〜図１３Ｂのプロセスは、簡潔性のために１台のみの車両１６に関して説明された。しかし、作業環境において、数台の車両１６が同時にまたは連続した交互の動作で車両ナビゲータ１０４によって操作され、注文の履行または任務の遂行を果たし得る。

図１４は、車両のナビゲーション経路を補償するために用いられる方法を示す図である。図１４は、第１のマーカ２８２に近接した車両１６を示す。車両１６は、第２の後続マーカ２８４に向かって移動している。図内のナビゲーション経路２８５は、第１のマーカ２８２と第２のマーカ２８４との間の直線である。

図１４に示すように、車両１６の重心２８６は、

の距離だけ第１のマーカ２８２からずれており、式中、ΔＸは第１の軸（ｘ軸）方向のオフセットであり、ΔＹは第２の軸（ｙ軸）方向のオフセットである。オフセットを補償するために、重心２８６とナビゲーション経路２８５との間に延びる補正経路２８８が規定される。

実施形態において、未補正ナビゲーション経路２８５に適用するための補正経路２８８は、第１のマーカ２８２から重心２８６までのｘ軸方向のオフセット距離ΔＸ、および第１のマーカ２８２から重心２８６までのｙ軸方向のオフセット距離ΔＹを用いて計算される。また、搬送車両１６の方向ベクトルと（Ｖｆとして示される）未補正ナビゲーション経路２８５の方向ベクトルとの差（すなわち角度差）が、未補正ナビゲーション経路２８５からの角度シータとして示される。角度シータもまた、補正経路２８８を計算するために用いられる。１つの実施形態によると、補正経路２８８は、上記の情報に基づいて生成されるベジェ曲線である。

１つの実施形態によると、補正経路２８８は、累積速度プロファイルから計算されてよい。累積速度プロファイルは、たとえば車両１６がラック１２を運搬しているか、している場合はラック１２の重量など、特定の変数を考慮し得る。ただし、車両１６がラック１２を運搬している場合、補正経路２８８は、ナビゲーション経路内に存在し得る他の任意の物理的障害物を考慮するとともに、ナビゲーション経路内の他の任意のラック１２を障害物として考慮する必要がある。車両１６がラック１２を運搬していない場合、物理的障害物のみしか考慮する必要はない。

１つの実施形態によると、補償経路の計算において考慮される他の変数は、ナビゲーション経路において通行するマーカセグメントの数である。後述するように、これらの変数ならびに他の関連変数から、加速距離および加速率、ならびに減速距離および減速率が計算され得る。実施形態において、時間単位ごとの加速の度合い、および時間単位ごとの減速の度合いが得られ得る。たとえば、時間単位ごとに３つの度合いの加速および減速が決められてよい。しかし、時間単位ごとの加速および減速を決めるために他の度合いが用いられてもよい。したがって、累積速度プロファイルは、計算された加速プロファイル、減速プロファイル、および一定速度プロファイルから得られ得る。計算された累積速度プロファイルの適用により、３つの程度のベジェ曲線が生じ得る。その結果、ベジェ曲線は、補正経路２８８を得るために、投射される地上における車両の質点の中心の動きに関する参照であってよい。上記プロセスは、車両１６が自身のナビゲーション経路における新たなマーカ２０ａ〜２０ｄに到達する度に繰り返される。

１つの実施形態によると、隣接するマーカ２８２と２８４との間のナビゲーション経路は、複数のセグメントに分割される。一例において、２つの隣接するマーカ間のナビゲーション経路は、５００のセグメントに分割され得る。車両１６の移動が開始すると、タイマおよび車輪カウンタが起動する。車輪カウンタは、車両１６の各車輪に関する回転数を計測する。合計車輪回転は、車両１６が移動する方向および距離に関係し得る。

また、セグメントカウンタは、現在のセグメントの記録を維持する。車輪３４のそれぞれの速度は、各セグメントの始点で設定され得る。たとえば５００μｓごとなど所定の時間後、タイマは中断され、車輪カウントが読み取られる。車輪カウントが予想されたカウントと少なくとも等しい場合、セグメントカウンタはインクリメントされる。たとえば補正後ナビゲーション経路の約９５％など、補正後ナビゲーション経路の規定の量が完了した後、車両１６は、車両ナビゲータ１０４によって、第２のマーカ２８４を検出するよう試みるように指示される。

１つの実施形態によると、以下のパラメータを考慮することによって計算が実行され得る。パラメータＮｏＭは、直線経路で通行するステップ（すなわちマーカ）の数に対応し（ただしＮｏＭは少なくとも１）、パラメータＸは、加速距離に対応する定数であり（たとえば、Ｘに値１２０が割り当てられるものとし）、パラメータＹは、減速距離に対応する定数であり（たとえば、Ｙに値１２０が割り当てられるものとし）、パラメータｓｔａｒｔ＿ｓｐｅｅｄに値１５が割り当てられ、パラメータｍａｘ＿ｓｐｅｅｄに値１００が割り当てられ、パラメータｓｔｏｐ＿ｓｐｅｅｄに値７が割り当てられるものとする。

初期加速減速プロファイルは、以下のように加速距離（ＡＤ）、減速距離（ＤＤ）、および最高速度（ＭＳ）を計算することによって決定される。
ＡＤ＝ｍｉｎｉｍｕｍ（Ｘ，Ｘ^＊０．５^＊ＮｏＭ） （２）
ＤＤ＝ｍｉｎｉｍｕｍ（Ｙ，Ｙ^＊０．５^＊ＮｏＭ） （３）
ＭＳ＝ｍｉｎｉｍｕｍ（ｍａｘ＿ｓｐｅｅｄ，ｓｔａｒｔ＿ｓｐｅｅｄ^＊（４^＊ＮｏＭ） （４）
その結果、１つの実施形態によると、加速減速プロファイルは、直線で通行するマーカの数に基づいて計算される。

また、補償曲線を生成するために、２つのマーカ間の距離（たとえば、マーカ２８２と２８４との間の距離）は、所定の数のセグメントに分割される。また、所定の数の補間点が選択される。１つの実施形態によると、４つの補間点が選択される。ただし、選択される点の数は、補償曲線の滑らかさに影響する。本明細書で説明される実施形態は、４つの補間点の選択に限定されるものではなく、他の任意の数の補間点が選択されてよいことを理解しなければならない。

１つの実施形態によると、第１の補間点には、車両の重心のオフセット位置の座標が割り当てられ、第４の座標点には、第２のマーカの座標が割り当てられる。また、中間補間点の座標は、初期オフセットΔＸおよびΔＹ、初期角度差（シータ）、およびマーカ間の距離に基づいて計算され得る。補間点の座標を計算すると、たとえばベジェ曲線などの補償曲線が生成され得る。また、車両が各セグメントを通行すると、車輪カウンタに基づいて加速減速プロファイルが修正され得る。また、各セグメントにおいて車両の速度を調整すると同時に、１つの実施形態によると、車両の線速度および旋回速度が考慮されるとともに、車両がラックを運搬しているか、および関連するラックの重量プロファイルが考慮される。

本開示の１つの実施形態によると、第１のマーカ２８２から重心２８６までのオフセット距離ΔＸ、ΔＹは、車両ナビゲータ１０４によって計算される。オフセット距離ΔＸ、ΔＹは、車両１６内のセンサ／カメラ１３４によって捕捉された画像に基づき、捕捉された画像は第１のマーカ２８２を含む。車両１６に対するセンサ／カメラ１３４の位置および方位は、たとえばジグを用いて決定され得る。車両１６の中心と、センサ／カメラ１３４によって捕捉された画像の中心との間のデフォルト距離を表す不変オフセットが計算される。

捕捉された画像における第１のマーカ２８２の位置および方位は、画像処理技術を用いて決定されてよい。第１のマーカ２８２の重心が計算され、第１のマーカ２８２と車両１６の中心との間のオフセットが決定される。この例において、第１のマーカ２８２の位置および方位は、ＯｐｅｎＣＶ画像処理アルゴリズムを用いて決定されるが、理解されるように、任意の適切な画像処理技術が用いられてよい。

また、第１のマーカ２８２の角の座標および第１のマーカ２８２の中心の座標が、ＯｐｅｎＣＶ関数「ｍｉｎＡｒｅａＲｅｃｔ」を用いて決定され得る。角座標は、第１のマーカ２８２に対する車両１６の旋回角度を決定するために用いられる。第１のマーカ２８２の中心と、捕捉された画像の中心との間の距離は、オフセット距離ΔＸ、ΔＹを表す。

１つの実施形態によると、オフセット距離は、距離を計測するために用いられるたとえば複数のレーザなどの適切なセンサを用いて決定されてよく、マーカ２０に対する車両１６の重心の位置は三角測量法を用いて計算される。ただし、他の相対位置決定構成が用いられてもよい。また、車両ナビゲータ１０４は、車両１６が辿る搬送経路に基づいて、かつ検出されたマーカ２０ａ〜２０ｄからの車両１６のオフセット位置に基づいて、車両１６の移動に関する速度および加速情報を計算するように構成されてもよい。計算された速度、加速、および方向情報は、車両１６の移動中にモータドライバ１２４へ伝達される。

図１５は、実施形態係る経路補正において実行されるステップを示す典型的なフローチャート１５００を示す。図１５に示すような経路補正ステップは、第１のマーカから第２のマーカへ通行する車両の場合に関して説明され、ここで、車両は第１のマーカにおいてオフセットを有する。

ステップ１５０１において、車両の重心と第１のマーカとの間のオフセットが計算される。上述したように、１つの実施形態によると、オフセット（ΔＸ、ΔＹ）は、車両１６に配置されたセンサ／カメラによって捕捉された画像に基づいて計算されてよく、捕捉された画像は第１のマーカを含む。

ステップ１５０３において、第１のマーカと第２のマーカとの間の距離は、所定の数のセグメントに分割される。１つの実施形態によると、マーカ間の距離は、５００のセグメントに分割される。

また、ステップ１５０７において、直線経路で通行する距離に基づく初期加速減速プロファイルが計算される。この例において、距離は、第１のマーカと第２のマーカとの間の距離に対応する。ただし、距離は、直線経路で通行するマーカの数に対応してもよい。加速減速プロファイルは、式（２）〜（４）において上述したように計算され得る。

ステップ１５０９において、所定の数の補間点が選択される。また、上述したように、補間点の各々に関する座標は、車両の角度偏差および第１のマーカと第２のマーカとの間の距離に基づいて計算される。１５１１におけるプロセスは、１５０１において計算されたオフセットおよび１５０９において計算された補間点の座標に基づいて補償曲線を生成する。

また、プロセス１５００はステップ１５１３において、車両がセグメント間隔を通行した後、車両の加速減速プロファイルを修正する。たとえば１つの実施形態によると、車両がセグメントを通行すると、車両の各車輪に関する回転数を計測する車輪カウンタに基づいて車両の速度が調整される。合計車輪回転は、車両が移動する方向および距離に対応する。このように、プロセス１５００は、第１のマーカにおいてずれている車両のための補償経路を生成することによって、車両がマーカ間の距離の通行を開始すると、車両が確実に第２のマーカ上に位置するようにする。それにもかかわらず、車両が第２のマーカ上に正確に位置していない場合、更なる経路補正を提供するために１５００のプロセスは繰り返され得ることを理解しなければならない。

上述した実施形態の機能の各々は、１または複数の処理回路によって実装されてよい。処理回路はプログラムされたプロセッサ（たとえば図１６のプロセッサ１６０３）を含み、プロセッサは回路を含む。処理回路はまた、たとえば特定用途向け集積回路（ＡＳＩＣ）および上記機能を実行するように構成された回路部品も含む。

上述した様々な特徴は、コンピュータシステム（またはプログラマブルロジック）によって実装されてよい。図１６は、そのようなコンピュータシステム１６０１を示す。１つの実施形態において、プロセッサ１６０３が、車両のナビゲーションプロセス、補償経路の計算、および上述した他の機能を実行するようにプログラムされる場合、コンピュータシステム１６０１は特定の専用マシンである。

コンピュータシステム１６０１は、たとえば磁気ハードディスク１６０７およびリムーバブルメディアドライブ１６０８（たとえばフロッピーディスクドライブ、読取専用コンパクトディスクドライブ、読取／書込コンパクトディスクドライブ、コンパクトディスクジュークボックス、テープドライブ、およびリムーバブル光磁気ドライブ）など、情報および命令を格納するための１または複数のストレージデバイスを制御するために、バス９０２に結合されたディスクコントローラ１６０６を含む。ストレージデバイスは、適切なデバイスインタフェース（たとえば、小型コンピュータシステムインタフェース（ＳＣＳＩ）、集積デバイスエレクトロニクス（ＩＤＥ）、拡張ＩＤＥ（Ｅ−ＩＤＥ）、ダイレクトメモリアクセス（ＤＭＡ）、またはウルトラＤＭＡ）を用いてコンピュータシステム１６０１に追加されてよい。

コンピュータシステム１６０１はまた、専用ロジックデバイス（たとえば特定用途向け集積回路（ＡＳＩＣ））または構成可能ロジックデバイス（たとえば簡易プログラマブルロジックデバイス（ＳＰＬＤ）、複合プログラマブルロジックデバイス（ＣＰＬＤ）、およびフィールドプログラマブルゲートアレイ（ＦＰＧＡ））も含んでよい。

コンピュータシステム１６０１はまた、コンピュータユーザに情報を表示するためのディスプレイ１６１０を制御するための、バス９０２に結合されたディスプレイコントローラ１６０９も含んでよい。コンピュータシステムは、コンピュータユーザとインタラクトし、プロセッサ１６０３へ情報を提供するための、たとえばキーボード１６１１およびポインティングデバイス１６１２などの入力デバイスを含む。ポインティングデバイス１６１２はたとえば、方向情報およびコマンド選択をプロセッサ１６０３へ伝達するため、およびディスプレイ１６１０上でのカーソルの動きを制御するためのマウス、トラックボール、タッチスクリーンセンサ用のフィンガ、またはポインティングスティックであってよい。

プロセッサ１６０３は、たとえば主要メモリ１６０４などのメモリに含まれる１または複数の命令の１または複数のシーケンスを実行する。そのような命令は、たとえばハードディスク１６０７またはリムーバブルメディアドライブ１６０８など他のコンピュータ可読媒体から主要メモリ１６０４に読み込まれてよい。多重処理構成における１または複数のプロセッサは、主要メモリ１６０４に含まれる命令のシーケンスを実行するために利用されてもよい。代替実施形態において、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて、ハードワイヤード回路が用いられてよい。したがって実施形態は、ハードウェア回路とソフトウェアとの任意の特定の組み合わせに限定されるものではない。

上述したように、コンピュータシステム１６０１は、本開示の教示のいずれかに従ってプログラムされた命令を保持するため、および本明細書で説明されたデータ構造、表、記録、または他のデータを収容するための少なくとも１つのコンピュータ可読媒体またはメモリを含む。コンピュータ可読媒体の例は、コンパクトディスク、ハードディスク、フロッピーディスク、テープ、光磁気ディスク、ＰＲＯＭ（ＥＰＲＯＭ、ＥＥＰＲＯＭ、ｆｌａｓｈ ＥＰＲＯＭ）、ＤＲＡＭ、ＳＲＡＭ、ＳＤＲＡＭ、または他の任意の磁気媒体、コンパクトディスク（たとえばＣＤ−ＲＯＭ）、または他の任意の光媒体、パンチカード、紙テープ、または穴のパターンを有する他の物理媒体である。

コンピュータ可読媒体のいずれか１つまたは組み合わせに格納された状態で、本開示は、コンピュータシステム１６０１を制御するため、本開示の特徴を実装するためにデバイスまたは複数のデバイスを駆動するため、およびコンピュータシステム１６０１が人間のユーザとインタラクトすることを可能にするためのソフトウェアを含む。そのようなソフトウェアは、デバイスドライバ、オペレーティングシステム、およびアプリケーションソフトウェアを含んでよいがこれらに限定されない。そのようなコンピュータ可読媒体は更に、本開示の任意の部分を実装において実行される処理の全部または（処理が分散される場合）一部を実行するための本開示のコンピュータプログラム製品を含む。

本実施形態のコンピュータコードデバイスは、スクリプト、解釈可能プログラム、ダイナミックリンクライブラリ（ＤＬＬ）、Ｊａｖａ（登録商標）クラス、完全実行可能プログラムを含むがこれらに限定されない任意の解釈可能または実行可能なコードメカニズムであってよい。また、本実施形態の処理の一部は、より良い性能、信頼性、および／またはコストのために分散されてもよい。

「コンピュータ可読媒体」という用語は、本明細書で用いられる場合、実行のためにプロセッサ１６０３へ命令を提供することに関与する任意の非一時的媒体を指す。コンピュータ可読媒体は、不揮発性媒体または揮発性媒体を含むがこれらに限定されない様々な形式であってよい。不揮発性媒体は、たとえばハードディスク１６０７またはリムーバブルメディアドライブ１６０８のような、たとえば光、磁気ディスク、および光磁気ディスクを含む。揮発性媒体は、たとえば主要メモリ１６０４のような動的メモリを含む。一方、送信媒体は、バス９０２を構成するワイヤを含む同軸ケーブル、銅線、および光ファイバを含む。送信媒体は、たとえば電波および赤外線データ通信中に生じるような音波または光波の形式であってもよい。

様々な形式のコンピュータ可読媒体は、実行のためにプロセッサ１６０３へ１または複数の命令の１または複数のシーケンスを搬送することに関与してよい。たとえば命令は最初、遠隔コンピュータの磁気ディスクに担持されてよい。遠隔コンピュータは、本開示の一部または全部を実行するための命令を遠隔的に動的メモリにロードし、モデムを用いて電話線を介して命令を送信し得る。コンピュータシステム１６０１にローカルなモデムは、電話線においてデータを受信し、バス９０２にデータを置いてよい。バス９０２は、主要メモリ１６０４へデータを搬送し、そこからプロセッサ１６０３は命令を取り出し実行する。主要メモリ１６０４によって受信された命令は、任意選択的に、プロセッサ１６０３による実行の前後いずれかにストレージデバイス１６０７または１６０８に格納されてよい。

コンピュータシステム１６０１はまた、バス９０２に結合された通信インタフェース１６１３も含む。通信インタフェース１６１３は、たとえばローカルエリアネットワーク（ＬＡＮ）１６１５、またはたとえばインターネットなど他の通信ネットワーク１６１６に接続されたネットワークリンク１６１４との双方向データ通信結合を提供する。たとえば通信インタフェース１６１３は、任意のパケット交換ＬＡＮに取り付けるネットワークインタフェースカードであってよい。他の例として、通信インタフェース１６１３は、統合サービスデジタルネットワーク（ＩＳＤＮ）カードであってよい。無線リンクが実装されてもよい。任意のそのような実装において、通信インタフェース１６１３は、様々な種類の情報を表すデジタルデータストリームを搬送する電気、電磁、または光信号を送受信する。

ネットワークリンク１６１４は一般的に、１または複数のネットワークを介して他のデータデバイスへのデータ通信を提供する。たとえば、ネットワークリンク１６１４は、ローカルネットワーク１６１５（たとえばＬＡＮ）を介して、または通信ネットワーク１６１６を介して通信サービスを提供するサービスプロバイダによって操作される機器を介して他のコンピュータへの接続を提供してよい。ローカルネットワーク１６１４および通信ネットワーク１６１６は、たとえば、デジタルデータストリームを搬送する電気、電磁、または光信号および関連する物理層（たとえばＣＡＴ５ケーブル、同軸ケーブル、光ファイバなど）を用いる。コンピュータシステム１６０１へ、およびコンピュータシステム１６０１からのデジタルデータを搬送する、様々なネットワークを介する信号および通信インタフェース１６１３を介するネットワークリンク１６１４における信号は、ベースバンド信号、または搬送波ベースの信号において実装されてよい。

ベースバンド信号は、デジタルデータビットのストリームを記述する非変調電気パルスとしてデジタルデータを伝送し、ここで「ビット」という用語はシンボルを意味するように幅広く解釈されるものであり、各シンボルが少なくとも１または複数の情報ビットを伝送する。デジタルデータは、導電媒体を介して伝搬される、または伝搬媒体を介して電磁波として送信される、たとえば振幅、位相、および／または周波数シフトキー信号などを用いて、搬送波を変調するためにも用いられてよい。したがって、デジタルデータは、「有線」通信チャネルを介して非変調ベースバンドデータとして送信され、および／または、搬送波を変調することによってベースバンドとは異なる所定の周波数帯域内で送信されてよい。コンピュータシステム１６０１は、ネットワーク（複数も可）１６１５および１６１６、ネットワークリンク１６１４、および通信インタフェース１６１３を介して、プログラムコードを含むデータを送受信し得る。また、ネットワークリンク１６１４は、ＬＡＮ１６１５を介して、たとえば携帯情報端末（ＰＤＡ）、ラップトップコンピュータ、または携帯電話などのモバイルデバイス１６１７への接続を提供してよい。

本明細書において、実施形態は、たとえば搬送車両または搬送ロボットなどの車両に関して説明されることを理解しなければならない。ただし、本明細書で説明される実施形態は、他の自動的にガイドされる車両にも適用され得る。その例は、４輪駆動車両、または内側フロントタイヤが外側フロントタイヤよりも大きい半径でカーブを曲がるアッカーマンステアリングシステムを用いる車両を含むが、これらに限定されない。

本開示の態様は、例として提示されたそれらの特定の実施形態に関して説明されたが、その例に対する代替例、変更例、および変形例がもたらされてよい。ただし、本明細書および特許請求の範囲において用いられる場合、単数形の「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈が明確に例外を示さない限り、複数形の対象物を含む。

また、上記説明は、本発明の単に典型的な実施形態を開示および記述するにすぎない。当業者には理解されるように、本開示は、本開示の主旨または根幹的な特徴から逸脱することなく他の特定の形式で具体化されてもよい。したがって本開示は、特許請求の範囲と同様、例示的であり範囲を限定するものではないことが意図される。本明細書における教示の容易に認識可能な任意の変形例を含む本開示は、主題事項が公衆に捧げられることがないように、上記請求項における用語の範囲を一部において定義するものである。また、上記開示は、以下に記述する実施形態も包括するものである。

（１）各々が関連する固有識別情報を有する複数のマーカと、マーカを検出し、前記マーカに関連付けられた固有識別情報を取得するように構成された少なくとも１つのセンサを各々が含み、規定の位置の間で制御可能に商品を搬送するように各々が構成された少なくとも１つの車両と、各マーカを示す情報、および各マーカに関連付けられ、前記マーカに対する少なくとも１つの規定の他のマーカの位置を示し、前記マーカと前記少なくとも１つの規定の他のマーカとの間での車両の移動を制御するために用いることができるナビゲーション情報を含むデータストレージデバイスとを備える商品取り扱いシステムであって、前記システムは、規定の位置間の搬送経路を規定するように構成され、前記搬送経路は、複数の選択されたマーカによって規定され、前記システムは、各マーカに関連付けられた前記ナビゲーション情報を用いて前記規定の位置間での車両の移動を制御するように構成される、商品取り扱いシステム。
（２）各マーカは機械可読パターンを備える、（１）の商品取り扱いシステム。
（３）前記機械可読パターンは、バーコードまたはＱＲコード（登録商標）を含む、（２）の商品取り扱いシステム。
（４）各マーカはＲＦＩＤデバイスを備える、（１）の商品取り扱いシステム。
（５）少なくとも１つのオペレータステーションを備え、前記システムは、オペレータステーションへ、およびオペレータステーションから各車両を制御可能に移動させるように構成される、（１）〜（４）の商品取り扱いシステム。
（６）前記オペレータステーションはステーション待ち行列を含み、前記オペレータステーションに到着する各車両は前記ステーション待ち行列に入り、前記車両が前記ステーション待ち行列内にある時、１または複数の商品がラックに載置され、またはラックから取り出される、（５）の商品取り扱いシステム。
（７）前記マーカは、前記ステーション待ち行列の入口位置に隣接して配置された少なくとも１つの待ち行列入口マーカ、および前記ステーション待ち行列の出口位置に隣接して配置された少なくとも１つの待ち行列出口マーカを含む、（６）の商品取り扱いシステム。
（８）前記システムは複数の商品ラックを含み、各車両は、ラックをオペレータステーションへ、およびオペレータステーションから制御可能に搬送するように構成される、（５）〜（７）の商品取り扱いシステム。
（９）前記マーカはラックマーカを含み、各ラックマーカは、前記ラックがラック格納位置にある時、ラックの下にある、またはラックに隣接するように配置される、（８）の商品取り扱いシステム。
（１０）前記マーカは、それぞれのラックに配置されたラックマーカを含む、（８）の商品取り扱いシステム。
（１１）前記マーカは、ラック格納位置と前記少なくとも１つのオペレータステーションとの間に配置された倉庫マーカを含む、（１）〜（１０）の商品取り扱いシステム。
（１２）各車両は、接触部材、および前記接触部材を地面に対して制御可能に上昇または下降させるように構成されたリフトデバイスを含む、（１）〜（１１）の商品取り扱いシステム。
（１３）前記車両と無線通信している管理システムを備え、前記管理システムは、各マーカに関連付けられた前記ナビゲーション情報を用いて、前記規定の位置間での車両の移動を制御するための指示を提供するように構成される、（１）〜（１２）の商品取り扱いシステム。
（１４）前記システムは、前記車両が前記ステーション待ち行列内にある時、車両の移動の制御を前記オペレータステーションに移行するように構成される、（５）の商品取り扱いシステム。
（１５）前記ナビゲーション情報は、搬送経路におけるマーカ間のナビゲーション経路を規定し、前記システムは、前記車両と隣接マーカとの間のオフセット変位を決定し、補償経路を計算するために前記決定されたオフセット変位を用いるように構成され、前記補償経路は、前記マーカ間での前記車両の移動を制御するために用いられる補償されたナビゲーション経路を生成するために前記ナビゲーション経路を修正する、（１）〜（１４）の商品取り扱いシステム。
（１６）前記補償経路はベジェ曲線である、（１５）の商品取り扱いシステム。
（１７）前記ナビゲーション経路は複数の経路セグメントに分割され、前記システムは、前記車両の移動を制御するための指示が、各経路セグメントの始点において提供されるように構成される、（１５）〜（１６）の商品取り扱いシステム。
（１８）前記システムは、隣接マーカを含む画像を捕捉し、前記画像を処理して、前記隣接マーカの重心と前記捕捉された画像の重心との間の距離を決定することによって、前記車両と前記隣接マーカとの間のオフセット変位を決定するように構成される、（１５）〜（１７）の商品取り扱いシステム。
（１９）前記画像は、前記隣接マーカの角の座標を決定するために処理され、前記角座標は、前記隣接マーカの回転の角度を決定するために用いられる、（１８）の商品取り扱いシステム。
（２０）車両の速度は、前記車両が荷積みしているかに依存する、（１）〜（１９）の商品取り扱いシステム。
（２１）各車両は、前記車両によって搬送される商品を計量するように構成された計量デバイスを含み、前記車両の前記速度は重量に依存する、（２０）の商品取り扱いシステム。
（２２）前記システムは、空のラックの既知の重心、各搬送される商品の既知の重量、および前記搬送される商品の前記ラック上での位置を用いることによって、重量分散プロファイルを決定するように構成される、（１）〜（２１）の商品取り扱いシステム。
（２３）前記重量分散プロファイルは、前記ラックおよび積載商品の重心を計算するため、および荷積みラックの重心が規定の範囲内であるかを決定するために用いられる、（２２）の商品取り扱いシステム。
（２４）前記ナビゲーション情報は、変位値および方位値を備える、（１）〜（２３）の商品取り扱いシステム。
（２５）前記システムは、全ての車両の前記マーカに対する位置を示す情報を格納するように構成される、（１）〜（２４）の商品取り扱いシステム。
（２６）前記システムは、商品が載置されたそれぞれのラック、および前記商品が載置された前記ラック上の位置を含む、前記商品取り扱いシステムに関連する全ての商品を示す在庫情報を格納するように構成される、（１）〜（２５）の商品取り扱いシステム。
（２７）注文処理のタイミングを管理するように構成された注文マネージャを備える、（１）〜（２６）の商品取り扱いシステム。
（２８）前記注文マネージャは、前記注文を履行するためにかかる予測時間に基づいて注文処理を優先順位付けするように構成される、（２７）の商品取り扱いシステム。
（２９）前記注文マネージャは、次のヒューリスティック、Ｈｅｕｒｉｓｔｉｃ，Ｈ＝Ｄｉｓｔａｎｃｅ／（１＋Ｎｏ ｏｆ Ｃｏｍｍｏｎ Ｒａｃｋｓ）を用いて、注文を履行するために用いるラック組み合わせを決定するように構成され、式中、Ｄｉｓｔａｎｃｅは、利用可能な注文品箱からラック組み合わせにおける全ラックまでの合計距離であり、Ｎｏ ｏｆ Ｃｏｍｍｏｎ Ｒａｃｋｓは、複数のラックセットに共通である前記ラック組み合わせ内のラックの数である、（２７）または（２８）の商品取り扱いシステム。
（３０）前記システムは、注文を履行するために用いる車両のセットを決定するように構成されたタスクマネージャを備える、（１）〜（２９）の商品取り扱いシステム。
（３１）前記選択された車両のセットにおける各車両に関する搬送経路を計算するように構成された経路計算機を備える、（１）〜（３０）の商品取り扱いシステム。
（３２）前記搬送経路はＡ^＊アルゴリズムを用いて計算される、（３１）の商品取り扱いシステム。
（３３）各車両の移動を個々に管理するように構成された車両ナビゲータを備える、（１）〜（３２）の商品取り扱いシステム。
（３４）前記車両ナビゲータは、検出されたマーカに関連付けられた前記固有識別情報を車両から受信し、それに応答して、前記検出されたマーカに関連付けられた前記ナビゲーション情報を前記車両へ伝達するように構成される、（３３）の商品取り扱いシステム。
（３５）前記システムは、前記車両間の衝突を回避するように前記車両の移動を管理するように構成される、（１）〜（３４）の商品取り扱いシステム。
（３６）前記システムは、マーカおよび／またはナビゲーション経路を予約し、タイミングまたは前記車両の移動および／または速度を管理し、一時的に前記搬送経路外を移動するように車両を制御するように構成される、（３５）の商品取り扱いシステム。
（３７）商品を取り扱う方法であって、各々が関連する固有識別情報を有する複数のマーカを規定のエリアに配置することと、マーカを検出し、前記マーカに関連付けられた前記固有識別情報を取得するように構成された少なくとも１つのセンサを各々が含み、規定の位置の間で制御可能に商品を搬送するように各々が構成された少なくとも１つの車両を提供することと、各マーカを示す情報、および各マーカに関連付けられ、前記マーカに対する少なくとも１つの規定の他のマーカの位置を示し、前記マーカと前記少なくとも１つの規定の他のマーカとの間での車両の移動を制御するために用いることができるナビゲーション情報を格納することと、複数の選択されたマーカによって規定される、規定の位置間の搬送経路を規定することと、各マーカに関連付けられた前記ナビゲーション情報を用いて前記規定の位置間での車両の移動を制御することとを備える方法。
（３８）各マーカは機械可読パターンを備える、（３７）の方法。
（３９）前記機械可読パターンは、バーコードまたはＱＲコード（登録商標）を含む、（３８）の方法。
（４０）各マーカはＲＦＩＤデバイスを備える、（３８）の方法。
（４１）前記車両と無線通信している管理システムを提供することと、各マーカに関連付けられた前記ナビゲーション情報を用いて前記規定の位置間での車両の移動を制御するために前記管理システムから指示を提供することとを備える、（３７）〜（４０）の方法。
（４２）ステーション待ち行列を有する少なくとも１つのオペレータステーションを提供することと、オペレータステーションへ、およびオペレータステーションから移動するように各車両を制御することと、前記車両が前記ステーション待ち行列内にある時、車両の移動の制御を前記オペレータステーションへ移行することとを備える、（３７）〜（４１）の方法。
（４３）前記ナビゲーション情報は、搬送経路におけるマーカ間のナビゲーション経路を規定し、前記方法は、前記車両と隣接マーカとの間のオフセット変位を決定することと、補償経路を計算するために前記決定されたオフセット変位を用いることと、前記マーカ間での前記車両の移動を制御するために用いられる補償されたナビゲーション経路を生成するために前記ナビゲーション経路を修正することとを備える、（３７）〜（４２）の方法。
（４４）前記補償経路はベジェ曲線である、（４３）の方法。
（４５）前記ナビゲーション経路を複数の経路セグメントに分割することと、各経路セグメントの始点において、前記車両の移動を制御するための指示を提供することとを備える、（４３）または（４４）の方法。
（４６）隣接マーカを含む画像を捕捉し、前記画像を処理して、前記隣接マーカの重心と前記捕捉された画像の重心との間の距離を決定することによって、前記車両と隣接マーカとの間のオフセット変位を決定することを備える、（４３）〜（４５）の方法。
（４７）前記隣接マーカの角の座標を決定するために前記画像を処理することと、前記隣接マーカの回転の角度を決定するために前記角座標を用いることとを備える、（４６）の方法。
（４８）空のラックの既知の重心、各搬送される商品の既知の重量、および前記搬送される商品の前記ラック上での位置を用いることによって、重量分散プロファイルを決定することを備える、（３７）〜（４７）の方法。
（４９）前記ラックおよび積載商品の重心を計算するために前記重量分散プロファイルを用いることと、荷積みラックの重心が規定の範囲内であるかを決定することとを備える、（４８）の方法。
（５０）全ての車両の前記マーカに対する位置を示す情報を格納することを備える、（３７）〜（４９）の方法。
（５１）注文を履行するためにかかる予測時間に基づいて注文処理を優先順位付けすることを備える、（３７）〜（５０）の方法。
（５２）次のヒューリスティック、Ｈｅｕｒｉｓｔｉｃ，Ｈ＝Ｄｉｓｔａｎｃｅ／（１＋Ｎｏ ｏｆ Ｃｏｍｍｏｎ Ｒａｃｋｓ）を用いて、注文を履行するために用いるラック組み合わせを決定することを備え、式中、Ｄｉｓｔａｎｃｅは、利用可能な注文品箱からラック組み合わせにおける全ラックまでの合計距離であり、Ｎｏ ｏｆ Ｃｏｍｍｏｎ Ｒａｃｋｓは、複数のラックセットに共通である前記ラック組み合わせ内のラックの数である、（３７）〜（５１）の方法。
（５３）Ａ^＊アルゴリズムを用いて前記搬送経路を計算することを備える、（５２）の方法。
（５４）マーカおよび／またはナビゲーション経路を予約すること、タイミングまたは前記車両の移動および／または速度を管理すること、および／または一時的に前記搬送経路外を移動するように車両を制御することによって、前記車両間の衝突を回避するように前記車両の移動を管理することを備える、（３７）〜（５３）に記載の方法。
（５５）車両をナビゲートするためのナビゲーションシステムであって、センサに隣接したマーカを検出するように構成された少なくとも１つのセンサを備え、前記システムは、前記検出されたマーカに対する少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を用いて、前記検出されたマーカと他のマーカとの間のナビゲーション経路に沿って前記車両の移動を制御するように構成され、前記システムは、前記車両と前記検出されたマーカとの間のオフセット変位を決定し、前記決定されたオフセット変位を用いて補償経路を計算するように構成され、前記補償経路は、前記マーカ間での前記車両の移動を制御するために用いられる補償されたナビゲーション経路を生成するために前記ナビゲーション経路を修正するものであり、前記補償経路はベジェ曲線を備える、ナビゲーションシステム。
（５６）前記ナビゲーション経路は複数の経路セグメントに分割され、前記システムは、各経路セグメントの始点において、前記車両の移動を制御するための指示が提供されるように構成される、（５５）のナビゲーションシステム。
（５７）前記システムは、隣接マーカを含む画像を捕捉し、前記画像を処理して、前記隣接マーカの重心と前記捕捉された画像の重心との間の距離を決定することによって、前記車両と隣接マーカとの間のオフセット変位を決定するように構成される、（５５）または（５６）のナビゲーションシステム。
（５８）前記画像は、前記隣接マーカの角の座標を決定するために処理され、前記角座標は、前記隣接マーカの回転の角度を決定するために用いられる、（５７）のナビゲーションシステム。

Claims (63)

1. 搬送経路に沿った車両の移動を制御するための方法であって、前記方法は、
   情報処理装置の回路によって、前記車両によって検出される第１のマーカに基づいて生成される第１のマーカ情報を受信することであって、前記第１のマーカは、所定の位置に設置された複数のマーカのうちの１つであることと、
   前記回路によって、前記車両が前記第１のマーカから移動する前記複数のマーカのうちの第２のマーカを決定することと、
   前記回路によって、前記第１のマーカ情報と、前記第１のマーカに関連付けられた所定のナビゲーション情報とに基づいて、前記第１のマーカから前記第２のマーカへの前記車両の移動を制御するための第１の制御情報を生成することであって、前記所定のナビゲーション情報は、前記第１のマーカに対する前記第２のマーカの位置を示すことと、
   前記回路によって、前記第１の制御情報を前記車両へ送信することと、
   を備え、
   前記第１のマーカと前記第２のマーカとの間の搬送経路は、複数の経路セグメントに分割され、前記回路は、各経路セグメントの始点において、前記車両の移動を制御するために前記第１の制御情報を送信するように更に構成される、方法。
2. 前記回路によって、前記第２のマーカが前記車両によって検出されることに基づいて生成される第２のマーカ情報を受信することと、
   前記回路によって、前記車両が前記第２のマーカから移動する前記複数のマーカのうちの第３のマーカを決定することと、
   前記第２のマーカ情報および前記所定のナビゲーション情報に基づいて、前記第２のマーカから前記第３のマーカへの前記車両の移動を制御するための第２の制御情報を生成することであって、前記所定のナビゲーション情報は、前記第２のマーカに対する前記第３のマーカの位置を示すことと、
   を更に備える、請求項１に記載の方法。
3. 前記第２のマーカは前記第１のマーカと隣り合い、
   前記所定のナビゲーション情報は、前記第１のマーカと隣り合う前記複数のマーカの各マーカの相対位置を示す、
   請求項１または２に記載の方法。
4. 前記複数のマーカの各々は機械可読パターンである、請求項１乃至３のいずれか１項に記載の方法。
5. 前記機械可読パターンは、バーコードおよびクイックレスポンス（ＱＲ）コード（登録商標）のうちの１つを含む、請求項４に記載の方法。
6. 前記複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む、請求項１乃至５のいずれか１項に記載の方法。
7. 前記第１のマーカ情報は、前記機械可読パターンから前記車両によって抽出される固有識別子を含む、請求項４乃至５のいずれか１項に記載の方法。
8. 前記回路によって、前記車両によって検出されるラックマーカに基づいて生成されるラックマーカ情報を受信することであって、前記ラックマーカは、前記車両によって搬送されるラックに配置されること
   を更に備える、請求項１乃至７のいずれか１項に記載の方法。
9. 前記第１のマーカ情報は、前記第１のマーカに対する前記車両の方位情報、および前記第１のマーカに関連付けられた識別情報を含む、請求項１乃至８のいずれか１項に記載の方法。
10. 前記第１のマーカ情報は、前記車両によって捕捉される前記第１のマーカの画像を含む、請求項１乃至９のいずれか１項に記載の方法。
11. 前記回路によって、前記搬送経路を計算することであって、前記搬送経路は、出発点マーカを始点とし到着点マーカを終点とする前記車両が通行する前記複数のマーカのうちのマーカのシーケンスを含むこと
    を更に備える、請求項１乃至１０のいずれか１項に記載の方法。
12. 前記搬送経路はＡ^＊アルゴリズムを用いて計算される、請求項１乃至１１のいずれか１項に記載の方法。
13. メモリに格納されたマーカマップから前記所定のナビゲーション情報を検索することであって、前記マーカマップは、前記複数のマーカの各々について、前記複数のマーカのそれぞれに対する前記複数のマーカのうちの少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を含み、前記ナビゲーション情報は、前記複数のマーカのそれぞれと前記少なくとも１つの規定の他のマーカとの間の前記車両の移動を制御するために使用可能であること
    を更に備える、請求項１乃至１２のいずれか１項に記載の方法。
14. 前記ナビゲーション情報は、前記複数のマーカのそれぞれと前記複数のマーカのうちの前記少なくとも１つの規定の他のマーカとの間の距離に対応する変位値と、方位角値とを含む、請求項１３に記載の方法。
15. 前記マーカマップは複数のキーを含み、前記複数のキーの各々は、前記複数のマーカの１つに対応し、
    車両が前記対応するマーカに位置する時に識別情報を格納する第１のデータフィールドと、
    前記対応するマーカの予約情報を格納する第２のデータフィールドと、
    前記対応するマーカの近隣マーカに対応する情報を格納する第３のデータフィールドであって、前記近隣マーカは、前記対応するマーカの北方向、南方向、東方向、および西方向に配置された少なくとも１つのマーカを含み、前記情報は、前記対応するマーカから前記対応する近隣マーカへ移動する前記車両の妥当性を決定するために用いられる、第３のデータフィールドと、
    前記対応するマーカの前記近隣マーカの各々までの距離を格納する第４のデータフィールドであって、前記距離は、前記対応するマーカから前記対応する近隣マーカへ移動する際に前記車両によって生じるコストを決定するために用いられる、第４のデータフィールドと、
    前記車両が前記対応するマーカに商品ラックを配置することができるかを示す第５のデータフィールドと、
    を含む、請求項１３または１４に記載の方法。
16. 搬送経路に沿った車両の移動を制御するための情報処理装置であって、前記情報処理装置は、
    回路であって、
    前記車両によって検出される第１のマーカに基づいて生成される第１のマーカ情報を受信することであって、前記第１のマーカは、所定の位置に設置された複数のマーカのうちの１つであることと、
    前記車両が前記第１のマーカから移動する前記複数のマーカのうちの第２のマーカを決定することと、
    前記第１のマーカ情報と、前記第１のマーカに関連付けられた所定のナビゲーション情報とに基づいて、前記第１のマーカから前記第２のマーカへの前記車両の移動を制御するための第１の制御情報を生成することであって、前記所定のナビゲーション情報は、前記第１のマーカに対する前記第２のマーカの位置を示すことと、
    前記第１の制御情報を前記車両へ送信することと、
    を行うように構成された、回路
    を備え、
    前記第１のマーカと前記第２のマーカとの間の搬送経路は、複数の経路セグメントに分割され、前記回路は、各経路セグメントの始点において、前記車両の移動を制御するために前記第１の制御情報を送信するように更に構成される、情報処理装置。
17. 前記回路は、
    前記第２のマーカが前記車両によって検出されることに基づいて生成される第２のマーカ情報を受信することと、
    前記車両が前記第２のマーカから移動する前記複数のマーカのうちの第３のマーカを決定することと、
    前記第２のマーカ情報および前記所定のナビゲーション情報に基づいて、前記第２のマーカから前記第３のマーカへの前記車両の移動を制御するための第２の制御情報を生成することであって、前記所定のナビゲーション情報は、前記第２のマーカに対する前記第３のマーカの位置を示すことと、
    を行うように更に構成される、請求項１６に記載の情報処理装置。
18. 前記第２のマーカは前記第１のマーカと隣り合い、
    前記所定のナビゲーション情報は、前記第１のマーカと隣り合う前記複数のマーカの各マーカの相対位置を示す、
    請求項１６または１７に記載の情報処理装置。
19. 前記複数のマーカの各々は機械可読パターンである、請求項１６乃至１８のいずれか１項に記載の情報処理装置。
20. 前記機械可読パターンは、バーコードおよびクイックレスポンス（ＱＲ）コード（登録商標）のうちの１つを含む、請求項１９に記載の情報処理装置。
21. 前記複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む、請求項１６乃至２０のいずれか１項に記載の情報処理装置。
22. 前記第１のマーカ情報は、前記機械可読パターンから前記車両によって抽出される固有識別子を含む、請求項１９乃至２０のいずれか１項に記載の情報処理装置。
23. 前記回路は、
    前記車両によって検出されるラックマーカに基づいて生成されるラックマーカ情報を受信することであって、前記ラックマーカは、前記車両によって搬送されるラックに配置されること
    を行うように更に構成される、請求項１６乃至２２のいずれか１項に記載の情報処理装置。
24. 前記第１のマーカ情報は、前記第１のマーカに対する前記車両の方位情報、および前記第１のマーカに関連付けられた識別情報を含む、請求項１６乃至２３のいずれか１項に記載の情報処理装置。
25. 前記第１のマーカ情報は、前記車両によって捕捉される前記第１のマーカの画像を含む、請求項１６乃至２４のいずれか１項に記載の情報処理装置。
26. 前記回路は、
    前記搬送経路を計算することであって、前記搬送経路は、出発点マーカを始点とし到着点マーカを終点とする前記車両が通行する前記複数のマーカのうちのマーカのシーケンスを含むこと
    を行うように更に構成される、請求項１６乃至２５のいずれか１項に記載の情報処理装置。
27. 前記搬送経路はＡ^＊アルゴリズムを用いて計算される、請求項１６乃至２６のいずれか１項に記載の情報処理装置。
28. 前記回路は、
    メモリに格納されたマーカマップから前記所定のナビゲーション情報を検索することであって、前記マーカマップは、前記複数のマーカの各々について、前記複数のマーカのそれぞれに対する前記複数のマーカのうちの少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を含み、前記ナビゲーション情報は、前記複数のマーカのそれぞれと前記少なくとも１つの規定の他のマーカとの間の前記車両の移動を制御するために使用可能であること
    を行うように更に構成される、請求項１６乃至２７のいずれか１項に記載の情報処理装置。
29. 前記ナビゲーション情報は、前記複数のマーカのそれぞれと前記複数のマーカのうちの前記少なくとも１つの規定の他のマーカとの間の距離に対応する変位値と、方位角値とを含む、請求項２８に記載の情報処理装置。
30. 前記マーカマップは複数のキーを含み、前記複数のキーの各々は、前記複数のマーカの１つに対応し、
    車両が前記対応するマーカに位置する時に識別情報を格納する第１のデータフィールドと、
    前記対応するマーカの予約情報を格納する第２のデータフィールドと、
    前記対応するマーカの近隣マーカに対応する情報を格納する第３のデータフィールドであって、前記近隣マーカは、前記マーカの北方向、南方向、東方向、および西方向に配置された少なくとも１つのマーカを含み、前記情報は、前記対応するマーカから前記対応する近隣マーカへ移動する前記車両の妥当性を決定するために用いられる、第３のデータフィールドと、
    前記対応するマーカの前記近隣マーカの各々までの距離を格納する第４のデータフィールドであって、前記距離は、前記対応するマーカから前記対応する近隣マーカへ移動する際に前記車両によって生じるコストを決定するために用いられる、第４のデータフィールドと、
    前記車両が前記マーカに商品ラックを配置することができるかを示す第５のデータフィールドと、
    を含む、請求項２８または２９に記載の情報処理装置。
31. コンピュータによって実行されると、前記コンピュータに、搬送経路に沿った車両の移動を制御するための方法を実行させるプログラムを格納した非一時的コンピュータ可読媒体であって、前記方法は、
    前記車両によって検出される第１のマーカに基づいて生成される第１のマーカ情報を受信することであって、前記第１のマーカは、所定の位置に設置された複数のマーカのうちの１つであることと、
    前記車両が前記第１のマーカから移動する前記複数のマーカのうちの第２のマーカを決定することと、
    前記第１のマーカ情報と、前記第１のマーカに関連付けられた所定のナビゲーション情報とに基づいて、前記第１のマーカから前記第２のマーカへの前記車両の移動を制御するための第１の制御情報を生成することであって、前記所定のナビゲーション情報は、前記第１のマーカに対する前記第２のマーカの位置を示すことと、
    前記第１の制御情報を前記車両へ送信することと、
    を備え、
    前記第１のマーカと前記第２のマーカとの間の搬送経路は、複数の経路セグメントに分割され、前記第１の制御情報は、各経路セグメントの始点において、前記車両の移動を制御するために送信される、非一時的コンピュータ可読媒体。
32. 前記方法は、
    前記第２のマーカが前記車両によって検出されることに基づいて生成される第２のマーカ情報を受信することと、
    前記車両が前記第２のマーカから移動する前記複数のマーカのうちの第３のマーカを決定することと、
    前記第２のマーカ情報および前記所定のナビゲーション情報に基づいて、前記第２のマーカから前記第３のマーカへの前記車両の移動を制御するための第２の制御情報を生成することであって、前記所定のナビゲーション情報は、前記第２のマーカに対する前記第３のマーカの位置を示すことと、
    を更に備える、請求項３１に記載の非一時的コンピュータ可読媒体。
33. 前記第２のマーカは前記第１のマーカと隣り合い、
    前記所定のナビゲーション情報は、前記第１のマーカと隣り合う前記複数のマーカの各マーカの相対位置を示す、
    請求項３１または３２に記載の非一時的コンピュータ可読媒体。
34. 前記複数のマーカの各々は機械可読パターンである、請求項３１乃至３３のいずれか１項に記載の非一時的コンピュータ可読媒体。
35. 前記機械可読パターンは、バーコードおよびクイックレスポンス（ＱＲ）コード（登録商標）のうちの１つを含む、請求項３４に記載の非一時的コンピュータ可読媒体。
36. 前記複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む、請求項３１乃至３５のいずれか１項に記載の非一時的コンピュータ可読媒体。
37. 前記第１のマーカ情報は、前記機械可読パターンから前記車両によって抽出される固有識別子を含む、請求項３４乃至３５のいずれか１項に記載の非一時的コンピュータ可読媒体。
38. 前記方法は、
    前記車両によって検出されるラックマーカに基づいて生成されるラックマーカ情報を受信することであって、前記ラックマーカは、前記車両によって搬送されるラックに配置されること
    を更に備える、請求項３１乃至３７のいずれか１項に記載の非一時的コンピュータ可読媒体。
39. 前記第１のマーカ情報は、前記第１のマーカに対する前記車両の方位情報、および前記第１のマーカに関連付けられた識別情報を含む、請求項３１乃至３８のいずれか１項に記載の非一時的コンピュータ可読媒体。
40. 前記第１のマーカ情報は、前記車両によって捕捉される前記第１のマーカの画像を含む、請求項３１乃至３９のいずれか１項に記載の非一時的コンピュータ可読媒体。
41. 前記方法は、
    前記搬送経路を計算することであって、前記搬送経路は、出発点マーカを始点とし到着点マーカを終点とする前記車両が通行する前記複数のマーカのうちのマーカのシーケンスを含むこと
    を更に備える、請求項３１乃至４０のいずれか１項に記載の非一時的コンピュータ可読媒体。
42. 前記搬送経路はＡ^＊アルゴリズムを用いて計算される、請求項３１乃至４１のいずれか１項に記載の非一時的コンピュータ可読媒体。
43. 前記方法は、
    メモリに格納されたマーカマップから前記所定のナビゲーション情報を検索することであって、前記マーカマップは、前記複数のマーカの各々について、前記複数のマーカのそれぞれに対する前記複数のマーカのうちの少なくとも１つの規定の他のマーカの位置を示すナビゲーション情報を含み、前記ナビゲーション情報は、前記複数のマーカのそれぞれと前記少なくとも１つの規定の他のマーカとの間の前記車両の移動を制御するために使用可能である、
    を更に備える、請求項３１乃至４２のいずれか１項に記載の非一時的コンピュータ可読媒体。
44. 前記ナビゲーション情報は、前記複数のマーカのそれぞれと前記複数のマーカのうちの前記少なくとも１つの規定の他のマーカとの間の距離に対応する変位値と、方位角値とを含む、請求項４３に記載の非一時的コンピュータ可読媒体。
45. 前記マーカマップは複数のキーを含み、前記複数のキーの各キーは、前記複数のマーカの１つに対応し、
    車両が前記対応するマーカに位置する時に識別情報を格納する第１のデータフィールドと、
    前記対応するマーカの予約情報を格納する第２のデータフィールドと、
    前記対応するマーカの近隣マーカに対応する情報を格納する第３のデータフィールドであって、前記近隣マーカは、前記対応するマーカの北方向、南方向、東方向、および西方向に配置された少なくとも１つのマーカを含み、前記情報は、前記対応するマーカから前記対応する近隣マーカへ移動する前記車両の妥当性を決定するために用いられる、第３のデータフィールドと、
    前記対応するマーカの前記近隣マーカの各々までの距離を格納する第４のデータフィールドであって、前記距離は、前記対応するマーカから前記対応する近隣マーカへ移動する際に前記車両によって生じるコストを決定するために用いられる、第４のデータフィールドと、
    前記車両が前記マーカに商品ラックを配置することができるかを示す第５のデータフィールドと、
    を含む、請求項４３または４４に記載の非一時的コンピュータ可読媒体。
46. 搬送経路に沿って車両を移動させるための方法であって、前記方法は、
    前記車両の回路によって、所定の位置に設置された複数のマーカのうちの第１のマーカを検出することと、
    前記回路によって、前記検出された第１のマーカに基づいて第１のマーカ情報を生成することと、
    前記回路によって、前記生成された第１のマーカ情報を情報処理装置へ送信することと、
    前記回路によって、第１の制御情報を前記情報処理装置から受信することであって、前記第１の制御情報は、前記第１のマーカ情報と、前記第１のマーカ情報に応答する所定のナビゲーション情報とに基づいて前記情報処理装置によって生成されることと、
    前記回路によって、前記車両に、前記第１の制御情報に基づいて前記複数のマーカのうちの第２のマーカへ移動させることと、
    を備え、
    前記所定のナビゲーション情報は、前記第１のマーカに対する前記第２のマーカの位置を示し、
    前記第１のマーカと前記第２のマーカとの間の搬送経路は、複数の経路セグメントに分割され、前記回路は、各経路セグメントの始点において、前記車両の移動を制御するために前記第１の制御情報を受信するように更に構成される、方法。
47. 前記方法は、
    前記回路によって、前記第２のマーカを検出することと、
    前記回路によって、前記検出された第２のマーカに基づいて第２のマーカ情報を生成することと、
    前記回路によって、前記生成された第２のマーカ情報を前記情報処理装置へ送信することと、
    前記回路によって、第２の制御情報を前記情報処理装置から受信することであって、前記第２の制御情報は、前記第２のマーカ情報と、前記第１のマーカ情報に応答する前記所定のナビゲーション情報とに基づいて前記情報処理装置によって生成されることと、
    前記回路によって、前記車両に、前記複数のマーカのうちの第３のマーカへ移動させることと
    を更に備え、
    前記所定のナビゲーション情報は、前記第２のマーカに対する前記第３のマーカの位置を示す、請求項４６に記載の方法。
48. 前記第２のマーカは前記第１のマーカと隣り合い、
    前記所定のナビゲーション情報は、前記第１のマーカと隣り合う前記複数のマーカの各マーカの相対位置を示す、
    請求項４６または４７に記載の方法。
49. 前記複数のマーカの各々は機械可読パターンである、請求項４６乃至４８のいずれか１項に記載の方法。
50. 前記機械可読パターンは、バーコードまたはクイックレスポンス（ＱＲ）コード（登録商標）を含む、請求項４９に記載の方法。
51. 前記複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む、請求項４６乃至５０のいずれか１項に記載の方法。
52. 前記第１のマーカ情報を生成することは、
    前記回路によって、前記機械可読パターンから固有識別子を抽出すること
    を備える、請求項４９乃至５０のいずれか１項に記載の方法。
53. 前記第１のマーカ情報は、前記第１のマーカに対する前記車両の方位情報、および前記第１のマーカに関連付けられた識別情報を含む、請求項４６乃至５２のいずれか１項に記載の方法。
54. 前記第１のマーカ情報は、前記車両によって捕捉される前記第１のマーカの画像を含む、請求項４６乃至５３のいずれか１項に記載の方法。
55. 回路であって、
    所定の位置に設置された複数のマーカのうちの第１のマーカを検出することと、
    検出された第１のマーカに基づいて第１のマーカ情報を生成することと、
    生成された第１のマーカ情報を情報処理装置へ送信することと、
    第１の制御情報を前記情報処理装置から受信することであって、前記第１の制御情報は、前記第１のマーカ情報と前記第１のマーカ情報に応答する所定のナビゲーション情報とに基づいて前記情報処理装置によって生成されることと、
    車両に、第１の制御情報に基づいて前記複数のマーカのうちの第２のマーカへ移動させることであって、前記所定のナビゲーション情報は、前記第１のマーカに対する前記第２のマーカの位置を示すことと、
    を行うように構成された、回路
    を備える車両であって、
    前記第１のマーカと前記第２のマーカとの間の搬送経路は、複数の経路セグメントに分割され、前記回路は、各経路セグメントの始点において、前記車両の移動を制御するために前記第１の制御情報を受信するように更に構成される、車両。
56. 前記回路は、
    前記第２のマーカを検出することと、
    前記検出された第２のマーカに基づいて第２のマーカ情報を生成することと、
    前記生成された第２のマーカ情報を前記情報処理装置へ送信することと、
    第２の制御情報を前記情報処理装置から受信することであって、前記第２の制御情報は、前記第２のマーカ情報と前記第１のマーカ情報に応答する前記所定のナビゲーション情報とに基づいて前記情報処理装置によって生成されることと、
    前記車両を前記複数のマーカのうちの第３のマーカへ移動させることであって、前記所定のナビゲーション情報は、前記第２のマーカに対する前記第３のマーカの位置を示すことと、
    を行うように更に構成される、請求項５５に記載の車両。
57. 前記第２のマーカは前記第１のマーカと隣り合い、
    前記所定のナビゲーション情報は、前記第１のマーカと隣り合う前記複数のマーカのうちの各マーカの相対位置を示す、
    請求項５５または５６に記載の車両。
58. 前記複数のマーカの各々は機械可読パターンである、請求項５５乃至５７のいずれか１項に記載の車両。
59. 前記機械可読パターンは、バーコードまたはクイックレスポンス（ＱＲ）コード（登録商標）を含む、請求項５８に記載の車両。
60. 前記複数のマーカの各々は、無線周波数識別（ＲＦＩＤ）デバイスを含む、請求項５５乃至５９のいずれか１項に記載の車両。
61. 前記回路は、
    前記機械可読パターンから固有識別子を抽出する
    ように更に構成される、請求項５８乃至５９のいずれか１項に記載の車両。
62. 前記第１のマーカ情報は、前記第１のマーカに対する前記車両の方位情報、および前記第１のマーカに関連付けられた識別情報を含む、請求項５５乃至６１のいずれか１項に記載の車両。
63. 前記第１のマーカ情報は、前記車両によって捕捉される前記第１のマーカの画像を含む、請求項５５乃至６２のいずれか１項に記載の車両。

Images