JP7779092B2 - 情報処理装置、情報処理方法及びコンピュータプログラム - Google Patents

Description

本発明は、情報処理装置、情報処理方法及びコンピュータプログラムに関する。

所定のマップを用いてモバイルロボットの移動計画を生成するための技術が提案されている。例えば特許文献１には、環境内の物体の幾何マップを用いて、位置姿勢を確率的に表した物体が占有する空間の分布を表したグリッドマップを生成し、グリッドマップから、物体の位置姿勢の不確実性に応じた距離を用いてボロノイグラフを生成して、ボロノイグラフの上で物体との衝突可能性と経路長をコストとして、与えられた出発点から目的地へ向かう経路の探索を行う技術が開示されている。

特開２００５－３２１９６号公報

従来技術では環境内の物体の幾何マップを用いてモバイルロボットの移動計画を生成しているが、複数のモバイルロボットについての移動計画は考慮されていない。モバイルロボットの集団を混雑なく管理するため、幾何マップ中に一方通行エリア又は台数制限エリアを設けて、予めモバイルロボットの回避経路を形成するが、回避経路の適切な設定には、人手による工数がかかり、非効率となっている。

本発明は、上記の点に鑑みてなされたものであり、従来技術と比較して移動可能なロボットの集団を効率よく管理できるデータ構造を出力する情報処理装置、情報処理方法及びコンピュータプログラムを提供することを目的とする。

上記目的を達成するために、本発明に係る情報処理装置は、移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及び前記ロボットの大きさに関する情報とを取得する取得部と、前記マップの前記通行可能な領域を前記ロボットの走行方向が定まる第１の領域と前記ロボットの走行方向が定まらない第２の領域とに分け、前記ロボットの大きさに関する情報を用いて、前記第１の領域の情報として前記第１の領域における前記ロボットの擦れ違い可否情報を、前記第２の領域の情報として前記ロボットが同時に存在できる台数の情報を格納した所定のデータ構造を生成する処理部と、前記データ生成部が生成した前記データ構造を出力する出力部と、を備える。これにより、移動可能なロボットの集団を効率よく管理できるデータ構造を出力できる。

前記処理部は、前記第１の領域又は前記第２の領域における前記ロボットの移動に対する制限に関する情報を前記データ構造に格納してもよい。これにより、ロボットの移動に対する制限に関する情報を出力できる。

前記取得部は、ユーザにより入力された前記制限に関する情報を取得してもよい。これにより、ユーザにより入力された制限に関する情報を出力できる。

前記処理部は、前記第２の領域の情報として、前記第２の領域の面積の情報を前記データ構造に格納してもよい。これにより、ロボットの走行方向が定まらない領域の面積の情報を出力できる。

前記処理部は、前記第１の領域に関する情報として、前記ロボットの進行方向に関する情報を前記データ構造に格納してもよい。これにより、ロボットの進行方向に関する情報を出力できる。

前記処理部は、前記通行可能な領域から前記第２の領域を抽出し、抽出した前記第２の領域を除いた前記通行可能な領域から前記第１の領域を抽出してもよい。これにより、ロボットの走行方向が定まらない領域ではない領域をロボットの走行方向が定まる領域とすることができる。

前記取得部は、前記ロボットの機種ごとに異なる前記ロボットの大きさに関する情報を取得してもよい。これにより、ロボットの大きさに関する情報に基づいてデータ構造を出力できる。

前記データ構造に格納された情報を反映した前記マップを表示させる表示制御部をさらに備えてもよい。これにより、データ構造に格納された情報を視覚的にマップ上に提示できる。

前記処理部は、前記データ構造に格納された情報に基づいた前記ロボットの経路計画を生成してもよい。これにより、データ構造に格納された情報からロボットの経路計画を生成できる。

上記目的を達成するために、本発明に係る情報処理方法は、移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及び前記ロボットの大きさに関する情報とを取得し、前記マップの前記通行可能な領域を前記ロボットの走行方向が定まる第１の領域と前記ロボットの走行方向が定まらない第２の領域とに分け、前記ロボットの大きさに関する情報を用いて、前記第１の領域の情報として前記第１の領域における前記ロボットの擦れ違い可否情報を、前記第２の領域の情報として前記ロボットが同時に存在できる台数の情報を格納した所定のデータ構造を生成し、生成した前記データ構造を出力する。これにより、移動可能なロボットの集団を効率よく管理できるデータ構造を出力できる。

上記目的を達成するために、本発明に係るコンピュータプログラムは、コンピュータに、移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及び前記ロボットの大きさに関する情報とを取得し、前記マップの前記通行可能な領域を前記ロボットの走行方向が定まる第１の領域と前記ロボットの走行方向が定まらない第２の領域とに分け、前記ロボットの大きさに関する情報を用いて、前記第１の領域の情報として前記第１の領域における前記ロボットの擦れ違い可否情報を、前記第２の領域の情報として前記ロボットが同時に存在できる台数の情報を格納した所定のデータ構造を生成し、前記第１の領域の情報及び前記第２の領域の情報を格納した所定のデータ構造を生成し、生成した前記データ構造を出力する、処理を実行させる。これにより、移動可能なロボットの集団を効率よく管理できるデータ構造を出力できる。

本発明によれば、移動可能なロボットの大きさの情報を用いることで従来技術と比較して移動可能なロボットの集団を効率よく管理できるデータ構造を出力する情報処理装置、情報処理方法及びコンピュータプログラムを提供することができる。

実施形態に係る情報処理装置のハードウェア構成を示すブロック図である。 情報処理装置の機能構成の例を示すブロック図である。 情報処理装置による情報処理の流れを示すフローチャートである。 情報処理装置による情報処理の流れを示すフローチャートである。 情報処理装置がマップからオープンスペース及びエッジを抽出する様子を示す図である。 情報処理装置がマップからオープンスペース及びエッジを抽出する様子を示す図である。 情報処理装置が生成するデータ構造の例を示す図である。 情報処理装置がマップからオープンスペース及びエッジを抽出する様子を示す図である。 情報処理装置が生成するデータ構造の例を示す図である。 情報処理装置によって生成されたデータ構造に基づいたマップの表現例を示す図である。 情報処理装置によって生成されたデータ構造に基づいたマップの表現例を示す図である。 情報処理装置によって生成されたデータ構造に基づいたマップの表現例を示す図である。 情報処理装置によって生成されたデータ構造に基づいたマップの表現例を示す図である。 情報処理装置がディスプレイに表示するユーザインターフェイスの例を示す図である。 マップ情報をデータドリブンに抽出する場合の処理を説明する図である。 マップ情報をデータドリブンに抽出する場合の処理を説明する図である。 マップ情報をデータドリブンに抽出する場合の処理を説明する図である。 マップ情報をデータドリブンに抽出する場合の処理を説明する図である。 情報処理装置が生成するデータ構造の例を示す図である。 情報処理装置がディスプレイに表示するユーザインターフェイスの例を示す図である。 モバイルロボットの運行計画の作成のバリエーションを説明する図である。

以下、本発明の実施形態の一例を、図面を参照しつつ説明する。なお、各図面において同一または等価な構成要素および部分には同一の参照符号を付与している。また、図面の寸法比率は、説明の都合上誇張されており、実際の比率とは異なる場合がある。

図１は、本実施形態に係る情報処理装置１０のハードウェア構成を示すブロック図である。本実施形態に係る情報処理装置１０は、移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及びロボットの大きさに関する情報とに基づいて、所定のデータ構造を生成して出力する装置である。本実施形態に係る情報処理装置１０は、係るデータ構造を生成して出力することで、移動可能なロボットの集団を効率よく管理することができる。なお、本実施形態において制御対象とするロボットは、ＡＭＲ（Ａｕｔｏｎｏｍｏｕｓ Ｍｏｂｉｌｅ Ｒｏｂｏｔ、自律走行搬送ロボット）である。

図１に示すように、情報処理装置１０は、メモリ１１、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１２、ビデオアダプタ１３、シリアルポートインターフェイス１４、ハードディスクドライブインターフェイス１５、及びハードディスクドライブ１６を有する。各構成は、バス１９を介して相互に通信可能に接続されている。

メモリ１１は、例えばＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）及びＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）等からなる記憶領域である。ＲＯＭは、各種プログラムおよび各種データを格納する。ＲＡＭは、作業領域として一時的にプログラムまたはデータを記憶する。

ＣＰＵ１２は、中央演算処理ユニットであり、各種プログラムを実行したり、各部を制御したりする。すなわち、ＣＰＵ１２は、メモリ１１のＲＯＭまたはハードディスクドライブ１６からプログラムを読み出し、メモリ１１のＲＡＭを作業領域としてプログラムを実行する。ＣＰＵ１２は、メモリ１１のＲＯＭまたはハードディスクドライブ１６に記録されているプログラムにしたがって、上記各構成の制御および各種の演算処理を行う。本実施形態では、メモリ１１のＲＯＭまたはハードディスクドライブ１６には所定のデータ構造を生成して出力する情報処理プログラムが格納されている。

ビデオアダプタ１３は、ディスプレイ２０と接続される。ビデオアダプタ１３は、ディスプレイ２０に表示する各種の情報をディスプレイ２０へ出力する。ディスプレイ２０は、液晶ディスプレイ、有機ＥＬディスプレイ等の種々の情報表示装置である。

シリアルポートインターフェイス１４は、マウス３０及びキーボード４０と接続される。シリアルポートインターフェイス１４は、ユーザがマウス３０及びキーボード４０を操作して入力した内容をＣＰＵ１２に出力する。

ハードディスクドライブ１６は、オペレーティングシステムを含む各種プログラム、および各種データを格納する。ハードディスクドライブ１６は、ハードディスクドライブインターフェイス１５を通じてデータ及びプログラムの読み書きが行われる。

上記の情報処理プログラムを実行する際に、情報処理装置１０は、上記のハードウェア資源を用いて、各種の機能を実現する。情報処理装置１０が実現する機能構成について説明する。

図２は、情報処理装置１０の機能構成の例を示すブロック図である。

図２に示すように、情報処理装置１０は、機能構成として、取得部１０１、処理部１０２、出力部１０３、表示制御部１０４及び保持部１０５を有する。各機能構成は、ＣＰＵ１２がメモリ１１のＲＯＭまたはハードディスクドライブ１６に記憶された情報処理プログラムを読み出し、実行することにより実現される。

取得部１０１は、移動可能なロボット（以下モバイルロボットとも称する）の通行可能な領域と通行不可能な領域とが区別されたマップ及びモバイルロボットの大きさに関する設定情報１１１とを取得する。マップは、例えばモバイルロボットが通行不可能な障害物を座標系列で表現したマップ、通行可能な領域と通行不可能な領域とをビットで表現したマップ、Ｌｉｄａｒ（Ｌｉｇｈｔ Ｄｅｔｅｃｔｉｏｎ Ａｎｄ Ｒａｎｇｉｎｇ、光による検知と測距）で取得された点群情報からなるマップ、等がある。

処理部１０２は、取得部１０１が取得した情報に基づいて所定のデータ構造を生成する。具体的には、処理部１０２は、取得部１０１が取得したマップ上のモバイルロボットが通行可能な領域を、エッジとオープンスペースとに分ける。エッジは、モバイルロボットの走行方向が定まる領域であり、本発明の第１の領域の一例である。オープンスペースは、モバイルロボットの走行方向が定まらない領域であり、本発明の第２の領域の一例である。

処理部１０２は、モバイルロボットの大きさに関する情報を用いて、エッジの情報として、当該エッジにおけるモバイルロボットの擦れ違い又は追い抜きの可否を定める擦れ違い可否情報を定める。処理部１０２は、エッジの擦れ違い可否情報として、エッジの離合条件の情報をデータ構造に格納する。エッジの離合条件は、複数のモバイルロボットが互いに擦れ違える制約条件である。エッジの離合条件の情報は、例えば、モバイルロボットが同時に並行できる台数、又は擦れ違える台数の情報で表される。当該台数の情報は、例えばモバイルロボットが通行する車線の数という形式で表現されてもよい。すなわち、車線が１つだけの場合は同時に並行できない、又は擦れ違えないエッジであり、車線が２つ以上の場合は同時に並行できる、又は擦れ違えるエッジである。また、エッジの離合条件の情報は、最も幅が狭い部分の道幅の情報で表されてもよい。また処理部１０２は、オープンスペースの情報としてモバイルロボットが同時にそのオープンスペースに存在できる台数の情報をデータ構造に格納する。そして処理部１０２は、係る情報が格納されたデータ構造を生成する。

処理部１０２は、マップの通行可能な領域からオープンスペースを抽出し、抽出したオープンスペースを除いた通行可能な領域からエッジを抽出する。具体的なオープンスペース及びエッジの抽出方法については後に詳述する。

処理部１０２は、エッジ又はオープンスペースにおけるモバイルロボットの移動に対する制限に関する情報をデータ構造に格納してもよい。モバイルロボットの移動に対する制限に関する情報は、取得部１０１によって取得されてもよい。また、処理部１０２は、オープンスペースの情報として、オープンスペースの面積の情報をデータ構造に格納してもよい。また、処理部１０２は、エッジに関する情報として、モバイルロボットの進行方向に関する情報をデータ構造に格納してもよい。データ構造に格納された情報の具体例は後に詳述する。

処理部１０２は、生成したデータ構造に基づいて、モバイルロボットの移動計画を生成する処理を実行してもよい。データ構造に基づいたモバイルロボットの移動計画の生成については後に詳述する。

処理部１０２は、擦れ違い可否情報を、エッジの領域中の進行方向に対して定められる最も狭い道幅に基づいて算出してもよい。処理部１０２は、オープンスペースの容量を、オープンスペースの形状に基づいて算出してもよい。また、処理部１０２は、擦れ違い可否情報及びオープンスペース容量を、スループットが向上するように走行シミュレーションによって求めても良い。本実施形態において、スループットとは、モバイルロボットの稼働効率をいう。また、処理部１０２は、擦れ違い可否情報及びオープンスペース容量を、スループットが向上するように実際にモバイルロボットを走行させて、モバイルロボットの走行により得られたデータを用いて求めても良い。

出力部１０３は、処理部１０２が生成したデータ構造を出力する。出力部１０３によって出力されたデータ構造は保持部１０５に格納され得る。表示制御部１０４は、ユーザインターフェイスをディスプレイ２０に表示する制御を行う。より詳細には、表示制御部１０４は、出力部１０３が出力したデータ構造を反映させたユーザインターフェイスをディスプレイ２０に表示する制御を行う。表示制御部１０４によってディスプレイ２０に表示されるユーザインターフェイスの例は後述する。保持部１０５は、モバイルロボットが移動する場所のマップ１１２を保持する。

本発明の実施形態に係る情報処理装置１０は、係る構成を有することで、移動可能なロボットの大きさの情報を用いたデータ構造を出力することができる。本発明の実施形態に係る情報処理装置１０は、移動可能なロボットの大きさの情報を用いることで、従来技術と比較して、移動可能なロボットの集団を効率よく管理するためのデータ構造を出力することができる。

次に、情報処理装置１０の作用について説明する。

図３は、情報処理装置１０による情報処理の流れを示すフローチャートである。ＣＰＵ１２がメモリ１１のＲＯＭまたはハードディスクドライブ１６に記憶された情報処理プログラムを読み出して、メモリ１１のＲＡＭに展開して実行することにより、情報処理が行なわれる。

図３に示したフローチャートは、情報処理装置１０がデータ構造を出力する処理のフローチャートである。ＣＰＵ１２は、まずステップＳ１０１において、データ構造の出力のために設定情報の入力を受け付ける。設定情報の入力は、所定のユーザインターフェイスによって行われ得る。ユーザインターフェイスの詳細については後述する。ステップＳ１０１においてＣＰＵ１２が受け付ける設定情報は、モバイルロボットの大きさに関する情報を含む情報である。モバイルロボットの大きさに関する情報には、例えばモバイルロボットの形状が円形であれば当該モバイルロボットの半径の情報、モバイルロボットの形状が円形でなければ当該モバイルロボットの外接円の半径の情報がある。また、ＣＰＵ１２は、モバイルロボットと、モバイルロボットが通行する通路の壁との間のバッファ距離の情報を受け付けてもよい。

設定情報の入力を受け付けると、続いてＣＰＵ１２は、ステップＳ１０２において、モバイルロボットが通行可能な領域の中から、オープンスペースの候補点を、所定の抽出手法に基づいて抽出する。オープンスペースの候補点の抽出手法の具体例は後述する。

オープンスペースの候補点を抽出すると、続いてＣＰＵ１２は、ステップＳ１０３において、抽出した候補点からオープンスペースを、所定の選択手法に基づいて選択する。オープンスペースは複数選択され得る。オープンスペースの選択手法の具体例は後述する。

オープンスペースを選択すると、続いてＣＰＵ１２は、ステップＳ１０４において、選択したオープンスペースの容量を、オープンスペース毎に計算する。ここで、オープンスペースの容量とは、そのオープンスペースに同時に存在できるモバイルロボットの台数をいう。従って、ＣＰＵ１２は、ロボットの大きさの情報を用いて、オープンスペースの容量を計算する。

オープンスペースの容量を計算すると、続いてＣＰＵ１２は、ステップＳ１０５において、モバイルロボットが通行可能な領域の中の、オープンスペース以外の領域をエッジと定義する。

オープンスペース以外の領域をエッジと定義すると、続いてＣＰＵ１２は、ステップＳ１０６において、エッジの離合条件を、所定の計算手法に基づいて計算する。エッジの離合条件は、当該エッジを並行して通行できる、または擦れ違えるモバイルロボットの数で表される。エッジの離合条件の計算手法は後述する。

エッジの離合条件を計算すると、続いてＣＰＵ１２は、ステップＳ１０７において、生成したノードとエッジとをデータ構造として出力する。データ構造の具体例は後述する。

図４は、情報処理装置１０による情報処理の流れを示すフローチャートである。ＣＰＵ１２がメモリ１１のＲＯＭまたはハードディスクドライブ１６に記憶された情報処理プログラムを読み出して、メモリ１１のＲＡＭに展開して実行することにより、情報処理が行なわれる。図４に示したフローチャートは、図３に示した情報処理のフローチャートを、ボロノイ図で実現する場合の情報処理の流れである。

ＣＰＵ１２は、まずステップＳ１１１において、データ構造の出力のために設定情報の入力を受け付ける。設定情報の入力は、所定のユーザインターフェイスによって行われ得る。

設定情報の入力を受け付けると、続いてＣＰＵ１２は、ステップＳ１１２において、マップを保持部１０５から取り出し、マップにおけるモバイルロボットの通行可能な領域と通行不可能な領域との境界の座標系列を基にボロノイ線を生成する。

ボロノイ線を生成すると、続いてＣＰＵ１２は、ステップＳ１１３において、ボロノイ線の接続端点数が３つ以上の点をオープンスペース点として抽出する。

オープンスペースの候補点を抽出すると、続いてＣＰＵ１２は、ステップＳ１１４において、オープンスペース点を中心した障害物と接する円を描き、当該円の半径を計算する。障害物は、例えば壁などのモバイルロボットの通行可能な領域と通行不可能な領域との境界である。

円の半径を計算すると、続いてＣＰＵ１２は、ステップＳ１１５において、オープンスペースの容量を決定する。ＣＰＵ１２は、例えば円の半径と、モバイルロボットの半径とを用いて、オープンスペースの容量を決定してもよい。例えば、円の半径がモバイルロボットの半径の２倍以下であれば、当該オープンスペースにはモバイルロボットが同時に１台しか存在できないので、ＣＰＵ１２は、当該オープンスペースの容量を１と決定する。

オープンスペースの容量を決定すると、続いてＣＰＵ１２は、ステップＳ１１６において、オープンスペースとエッジとの接続部を新たなノードとする。

オープンスペースとエッジとの接続部を新たなノードとすると、続いてＣＰＵ１２は、ステップＳ１１７において、ボロノイ線の端点を中心とした障害物との内接円の半径を求める。

内接円の半径を求めると、続いてＣＰＵ１２は、ステップＳ１１８において、内接円の半径からエッジの離合条件を求める。エッジの離合条件は、当該エッジを並行して通行できる、または擦れ違えるモバイルロボットの数で表される。ＣＰＵ１２は、例えば内接円の半径と、モバイルロボットの半径とを用いて、エッジの離合条件を決定してもよい。例えば、内接円の半径がモバイルロボットの半径の２倍以下であれば、当該エッジにはモバイルロボットが同時に１台しか通行できないので、ＣＰＵ１２は、当該エッジの離合条件を１台と決定する。

モバイルロボットの機種が複数存在し、機種ごとに大きさが違う場合が考えられる。モバイルロボットが３種類あり、それぞれＡＭＲ１、ＡＭＲ２、ＡＭＲ３とする。そして、ＡＭＲ１の幅が１．０、ＡＭＲ２の幅が１．５、ＡＭＲ３の幅が１．７であるとする。この幅は幅が最少のＡＭＲ１を単位として規格化した値である。通路幅（車線数）を３．０とすると、ＡＭＲ１同士は３台まで並走可であり、かつ擦れ違い可である。また、ＡＭＲ２同士は２台まで並走可であり、かつ擦れ違い可である。また、ＡＭＲ３同士は並走不可であり、かつ擦れ違いも不可である。また、ＡＭＲ１とＡＭＲ２とは２台まで並走可であり、かつ擦れ違い可である。また、ＡＭＲ１とＡＭＲ３とは２台まで並走可であり、かつ擦れ違い可である。また、ＡＭＲ２とＡＭＲ３なら並走不可であり、かつ擦れ違いも不可である。このように、ＣＰＵ１２はモバイルロボットの機種に応じた離合条件を決定する。もちろん、離合条件を求める際に、モバイルロボットの大きさを規格化した値ではなく、モバイルロボットの実際の大きさの数値を用いてもよい。

内接円の半径からモバイルロボットの離合条件を求めると、続いてＣＰＵ１２は、ステップＳ１１９において、生成したノードとエッジをデータ構造として出力する。

本発明の実施形態に係る情報処理装置１０は、係る処理を実行することで、移動可能なロボットの大きさの情報を用いたデータ構造を出力することができる。本発明の実施形態に係る情報処理装置１０は、移動可能なロボットの大きさの情報を用いることで、従来技術と比較して移動可能なロボットの集団を効率よく管理するためのデータ構造を出力することができる。

なお、ＣＰＵ１２は、ボロノイ図以外の手法、例えば確率的ロードマップ法又はＲＲＴ（Ｒａｐｉｄｌｙ ｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ）等によってオープンスペースを特定してもよい。

続いて、情報処理装置１０による具体的なデータ構造の生成例を示す。

図５は、情報処理装置１０がマップからオープンスペース及びエッジを抽出する様子を示す図である。マップ２００が情報処理装置１０に与えられると、情報処理装置１０は、マップ２００からオープンスペース及びエッジを抽出する。符号２１０で示したマップ２００の一部分を参照すると、情報処理装置１０は、オープンスペースには「Ａ１」というＩＤを付与し、ノードｖ１とｖ２との間のエッジには「ｅ１」というＩＤを付与している。また、情報処理装置１０は、各エッジについて離合条件を車線数で表した情報を生成する。そして情報処理装置１０は、オープンスペース及びエッジの情報をデータ構造に格納することで、図５に示したように、どこがオープンスペースであり、どこがエッジであり、エッジがどのような離合条件を有しているかを、データ構造に基づいて視覚的に提示できる。

図６は、図４に示したフローチャートに基づき、情報処理装置１０がマップからオープンスペース及びエッジを抽出する様子を示す図である。

図６（ａ）のように、マップ２００が情報処理装置１０に与えられると、情報処理装置１０は、図６（ｂ）のように、マップにおけるモバイルロボットの通行可能な領域と通行不可能な領域との境界の座標系列を基にボロノイ線を生成する。ボロノイ線を生成すると、続いて情報処理装置１０は、図６（ｃ）のように、ボロノイ線の接続端点数が３つ以上の点をオープンスペース点として抽出する。オープンスペースの候補点を抽出すると、続いて情報処理装置１０は、図６（ｄ）のように、オープンスペース点を中心した障害物と接する円を描き、当該円の半径を計算する。障害物は、例えば壁などのモバイルロボットの通行可能な領域と通行不可能な領域との境界である。

オープンスペース点を中心した障害物と接する円を描き、当該円の半径を計算すると、続いて情報処理装置１０は、図６（ｅ）のように、当該円と障害物の接点数を求め、接点数の個数が「ボロノイ線の接続端点数」×２の数になるまで半径を拡大する。続いて情報処理装置１０は、図６（ｆ）のように、接点同士の距離が所定の閾値以下になるように、
接点間の距離を調整する。続いて情報処理装置１０は、図６（ｇ）のように、得られた接点同士を接続しオープンスペースを生成する。

オープンスペースの容量を決定すると、続いて情報処理装置１０は、図６（ｈ）のように、オープンスペースとエッジとの接続部を新たなノードとする。オープンスペースとエッジとの接続部を新たなノードとすると、続いて情報処理装置１０は、図６（ｉ）のように、ボロノイ線の端点を中心とした障害物との内接円の半径を求める。

内接円の半径を求めると、続いて情報処理装置１０は、図６（ｊ）のように、内接円の半径からエッジの離合条件を求める。そして、情報処理装置１０は、内接円の半径からモバイルロボットの離合条件を求めると、生成したノードとエッジをデータ構造として出力する。このように、情報処理装置１０は、マップ２００が与えられると、マップ２００の内容に基づいてデータ構造を出力することができる。

図７は、情報処理装置１０が生成するデータ構造の例を示す図である。図７の上段はノードの情報が格納されたテーブルのデータ構造であり、ノードを識別するノードＩＤ、当該ノードの座標、当該ノードに接続されているオープンスペースのＩＤ（接続ＯＳ－ＩＤ）の情報が格納されている。なお座標の値は、マップ２００の任意の点を原点とした場合の値である。図７の中段はオープンスペースの情報が格納されたテーブルのデータ構造であり、オープンスペースを識別するＩＤ（ＯＳ－ＩＤ）、当該オープンスペースの容量、当該オープンスペースの面積、当該オープンスペースに接続されているノードの情報（接続ノード－ＩＤ）が格納されている。図７の下段はエッジの情報が格納されたテーブルのデータ構造であり、エッジＩＤ、始点のノード、終点のノード、離合条件、当該エッジの距離の情報が格納されている。なお、始点及び終点は、当該エッジの進行方向が決められていなければどちらのノードであってもよいが、当該エッジの進行方向が決められていれば、始点及び終点はどちらか一方に決められる。

情報処理装置１０は、このようにデータ構造を生成して出力することで、図５に示したように、どこがオープンスペースであり、どこがエッジであり、エッジがどのような離合条件を有しているかを、データ構造に基づいて視覚的に提示できる。

なお、図７に示した例では、オープンスペースの情報とエッジの情報とが、それぞれ別のテーブルに格納されていたが、本発明は係る例に限定されるものでは無い。オープンスペースの情報とエッジの情報とが同一のテーブルに格納されてもよい。

図８は、情報処理装置１０がマップからオープンスペース及びエッジを抽出する様子を示す図である。マップ２００が情報処理装置１０に与えられると、情報処理装置１０は、マップ２００からオープンスペース及びエッジを抽出する。符号２１で示したマップ２００の一部分を参照すると、情報処理装置１０は、オープンスペースには「ｖ６」というＩＤを付与し、ノードｖ１とｖ２との間のエッジには「ｅ１」というＩＤを付与している。

図９は、情報処理装置１０が生成するデータ構造の例を示す図である。図９の上段はエッジの情報が格納されたテーブルのデータ構造であり、エッジＩＤ、始点のノード、終点のノード、離合条件、当該エッジの距離の情報が格納されている。なお、始点及び終点は、当該エッジの進行方向が決められていなければどちらのノードであってもよいが、当該エッジの進行方向が決められていれば、始点及び終点はどちらか一方に決められる。図９の中段はノードの情報が格納されたテーブルのデータ構造であり、ノードを識別するノードＩＤ、当該ノードの座標、当該ノードに接続されているオープンスペースのＩＤ（接続ＩＤ）、当該フィールドの属性の情報が格納されている。なお座標の値は、マップ２００の任意の点を原点とした場合の値である。なお、ノードには容量及び面積の概念が無いので、容量及び面積のフィールドには値が何も入っていない（又はｎｕｌｌ値が入っている）。図９の下段はオープンスペースの情報が格納されたテーブルのデータ構造であり、オープンスペースを識別するＩＤ、当該オープンスペースの面積、当該オープンスペースの容量、当該オープンスペースに接続されているノードの情報（接続ＩＤ）、当該フィールドの属性の情報が格納されている。なお、オープンスペースには座標の概念が無いので、座標のフィールドには値が何も入っていない（又はｎｕｌｌ値が入っている）。

情報処理装置１０は、このようにオープンスペースの情報とエッジの情報とが同一のテーブルに格納することができる。そして、情報処理装置１０は、データ構造を生成して出力することで、図８に示したように、どこがオープンスペースであり、どこがエッジであり、エッジがどのような離合条件を有しているかを、データ構造に基づいて視覚的に提示できる。

次に、情報処理装置１０によって生成されたデータ構造に基づいたマップの表現例を示す。図１０Ａ～１０Ｄは、情報処理装置１０によって生成されたデータ構造に基づいたマップの表現例を示す図である。情報処理装置１０は、例えば図１０Ａに示したように、エッジの離合条件に応じてエッジの色を変化させて表現してもよい。また、情報処理装置１０は、例えば図１０Ｂに示したように、エッジの離合条件に応じてエッジの近傍に数字を表示することで表現してもよい。また、情報処理装置１０は、例えば図１０Ｃに示したように、エッジの離合条件に応じて、線の太さを変化させて表現してもよい。また、情報処理装置１０は、例えば図１０Ｄに示したように、モバイルロボットの進行方向をエッジ上に示すことでエッジの離合条件を表現してもよい。

次に、情報処理装置１０が表示するユーザインターフェイスの例を説明する。図１１は、情報処理装置１０がディスプレイ２０に表示するユーザインターフェイスの例を示す図である。ユーザインターフェイス３００は、情報処理装置１０にデータ構造を出力させるためのユーザインターフェイスである。

符号３０１は、情報処理装置１０がマップ及びユーザからの入力情報に基づいてデータ構造を出力する場合にユーザによって選択されるタブである。符号３０２は、ユーザによる手動設定に基づいてデータ構造を出力する場合にユーザによって選択されるタブである。符号３０３は、モバイルロボットの大きさに関する情報を入力するためのテキストボックスである。図１１の例では、モバイルロボットの大きさに関する情報として、モバイルロボットの半径及び速度制限エリアの壁からの最小幅が入力できる。もちろんモバイルロボットの大きさに関する情報は係る例に限定されるものでは無い。

符号３０４は、情報処理装置１０がデータ構造に基づいたモバイルロボットの運行計画を生成する場合に参照すべき制約の対象項目を選択するための領域である。ここで、モバイルロボットの運行計画を生成する場合に参照すべき制約について説明する。モバイルロボットの運行計画を生成する際に、人とモバイルロボットとが同時に複数存在する領域（混流領域）のマップで普遍的にみられる知見、ノウハウ又は暗黙知が存在する。情報処理装置１０が符号３０４の領域で表示する制約は、このような知見、ノウハウ又は暗黙知をリストアップしたものである。本実施形態では８つの制約を提示している。表１に制約の例、及びその制約を設ける理由と、データドリブンによる実現方法とを示す。

図１２Ａ～図１２Ｄは、マップ情報をデータドリブンに抽出する場合の処理を説明する図である。図１２Ａ及び図１２Ｂは、表１の７番の制約が設定された場合の処理を説明する図である。この場合、ＣＰＵ１２はボロノイ線の接続端点数でオープンスペースを抽出し、オープンスペースとエッジとの結合点を全結合のグラフで繋ぐことで、優先通過ラインを定義する。図１２Ｃは、表１の１番、２番、又は６番の制約が設定された場合の処理を説明する図である。この場合、ＣＰＵ１２はボロノイ端点を中心とした車線数×Ｎの円を描くことで車線数を定義する。図１２Ｄは、表１の８番の制約が設定された場合の処理を説明する図である。この場合、ＣＰＵ１２はエッジの曲がり角に相当する場所では、壁に向かってボロノイ線が一本だけ伸びているという特徴を用いて曲がり角を特定し、速度制限エリアを設ける。

なお、表１の３番の制約が設定された場合、ＣＰＵ１２は、ゴール地点に最も近傍のボロノイ端点を見つけ、そのボロノイ端点を中心に仮想壁との内接円を描いて、速度制限エリアを定義する。また、表１の４番の制約が設定された場合、ＣＰＵ１２は、ボロノイ端点を中心とした仮想壁と接触する内接円を描き、速度制限エリアの幅分だけ半径を減らし、モルフォロジ処理によって仮想壁を膨張させて元の座標との差分を求めることにより速度制限エリアを定義する。

図１３は、情報処理装置１０が生成するデータ構造の例を示す図である。図１３に示したデータ構造は、図７に示したデータ構造に、ユーザによって指定された制約が追加されたものである。図１３の上段は図７の上段と同様である。図１３の中段はオープンスペースの情報が格納されたテーブルのデータ構造であり、オープンスペースを識別するＩＤ（ＯＳ－ＩＤ）、当該オープンスペースの容量、当該オープンスペースの面積、当該オープンスペースに接続されているノード（接続ノード－ＩＤ）、当該オープンスペースの制約の情報が格納されている。図１３の下段はエッジの情報が格納されたテーブルのデータ構造であり、エッジＩＤ、始点のノード、終点のノード、離合条件、当該エッジの距離、当該エッジの制約の情報が格納されている。

図１４は、情報処理装置１０がディスプレイ２０に表示するユーザインターフェイスの例を示す図である。図１４に示したのは、情報処理装置１０が生成したデータ構造に基づいてマップ上に情報を重畳して表示するユーザインターフェイスの例である。情報処理装置１０は、データ構造に基づいてマップ上に情報を重畳して表示することで、当該マップにおけるモバイルロボットの移動の様子をユーザに予め把握させることができる。

情報処理装置１０が上述したようなデータ構造を生成して出力することで、モバイルロボットの運行計画の作成工数の低減に寄与できる。

図１５は、モバイルロボットの運行計画の作成のバリエーションを説明する図である。図１５の左側の列は、モバイルロボットの走行を制御するサーバ側からは、モバイルロボットが通るべきルート上の大まかな領域のみを指示し、その中での動き方はモバイルロボットの自動走行による制御に任せる実装形態である。モバイルロボット同士の干渉回避はモバイルロボットの自律制御に任せられることになる。図１５の右側の列は、サーバ側がより詳細な空間座標であるウェイポイント点列によってモバイルロボットへ軌道を指示する形態である。この場合、モバイルロボット同士の干渉回避をサーバ側が指示することが可能になる。モバイルロボットの自律制御は、人などの非制御物体との干渉を回避する目的で利用されることになる。図１５の上段の行は、モバイルロボットのキネマティクス又はダイナミクスを考慮して経路計画を策定する実施例である。例えば直進ではモバイルロボットは速く走行し、曲がる際にはモバイルロボットは遅く走行するという特性を考えて最適化を行うものである。なお、図１５の下段の行は、モバイルロボットのキネマティクス又はダイナミクスを考慮せずに経路計画を策定する実施例である。この場合では、モバイルロボットがゆっくり動作する場合を想定し、経路の所要時間は経路等に比例するものとして扱う。

図１５の左上の実施例の場合、情報処理装置１０は、抽出されたロードマップに対して、モバイルロボットのダイナミクスを考慮した拘束条件の上でＭＡＰＦ（Ｍｕｌｔｉ－Ａｇｅｎｔ Ｐａｔｈ Ｆｉｎｄｉｎｇ、マルチエージェント経路探索）問題を定式化して解く。図１４の左上の実施例の場合でも、情報処理装置１０は、ロードマップ領域に対する離合条件又は容量などの衝突判定の情報を利用して、最適化のサーチ計算量を削減できる。

図１５の左下の実施例の場合、情報処理装置１０は、抽出されたロードマップに対して、モバイルロボットの動きを等速直線運動としてＭＡＰＦ問題を定式化して解く。図１５の左下の実施例の場合でも、情報処理装置１０は、ロードマップ領域に対する離合条件又は容量などの衝突判定の情報を利用して、最適化のサーチ計算量を削減できる。なお、図１５の左下の実施例において、ｎ１～ｎ５はオープンスペースとして、ｅ１～ｅ７はエッジとして、それぞれ抽出された領域を表している。

図１５の右上の実施例の場合、情報処理装置１０は、グリッド点に対してモバイルロボットのダイナミクスを考慮した拘束条件を定義し、その上でＭＡＰＦ問題とモーションプラニング問題を同時に解く。情報処理装置１０は、グリッド点が属するロードマップ領域情報を利用して、グリッド点間のダイナミクスの定義を（例えば道と交差点で）変更することで計算量を削減できる。図１５の右上の実施例の場合でも、情報処理装置１０は、ロードマップ領域に対する離合条件又は容量などの衝突判定の情報を利用して、最適化のサーチ計算量を削減できる。

なお、上記各実施形態でＣＰＵがソフトウェア（プログラム）を読み込んで実行した情報処理を、ＣＰＵ以外の各種のプロセッサが実行してもよい。この場合のプロセッサとしては、ＦＰＧＡ（Ｆｉｅｌｄ－Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）等の製造後に回路構成を変更可能なＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）、及びＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）等の特定の処理を実行させるために専用に設計された回路構成を有するプロセッサである専用電気回路等が例示される。また、情報処理を、これらの各種のプロセッサのうちの１つで実行してもよいし、同種又は異種の２つ以上のプロセッサの組み合わせ（例えば、複数のＦＰＧＡ、及びＣＰＵとＦＰＧＡとの組み合わせ等）で実行してもよい。また、これらの各種のプロセッサのハードウェア的な構造は、より具体的には、半導体素子等の回路素子を組み合わせた電気回路である。

また、上記各実施形態では、情報処理のプログラムがＲＯＭまたはストレージに予め記憶（インストール）されている態様を説明したが、これに限定されない。プログラムは、ＣＤ－ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＤＶＤ－ＲＯＭ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、及びＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）メモリ等の非一時的（ｎｏｎ－ｔｒａｎｓｉｔｏｒｙ）記録媒体に記録された形態で提供されてもよい。また、プログラムは、ネットワークを介して外部装置からダウンロードされる形態としてもよい。

１０ 情報処理装置
２００ マップ
３００ ユーザインターフェイス

Claims (11)

1. 移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及び前記ロボットの大きさに関する情報とを取得する取得部と、
   前記マップの前記通行可能な領域を前記ロボットの走行方向が定まる第１の領域と前記ロボットの走行方向が定まらない第２の領域とに分け、前記ロボットの大きさに関する情報を用いて、前記第１の領域の情報として前記第１の領域における前記ロボットの擦れ違い可否情報を、前記第２の領域の情報として前記ロボットが同時に存在できる台数の情報を格納した所定のデータ構造を生成する処理部と、
   前記処理部が生成した前記データ構造を出力する出力部と、
   を備える情報処理装置。
2. 前記処理部は、前記第１の領域又は前記第２の領域における前記ロボットの移動に対する制限に関する情報を前記データ構造に格納する、請求項１に記載の情報処理装置。
3. 前記取得部は、ユーザにより入力された前記制限に関する情報を取得する、請求項２に記載の情報処理装置。
4. 前記処理部は、前記第２の領域の情報として、前記第２の領域の面積の情報を前記データ構造に格納する、請求項１～請求項３のいずれか１項に記載の情報処理装置。
5. 前記処理部は、前記第１の領域に関する情報として、前記ロボットの進行方向に関する情報を前記データ構造に格納する、請求項１～請求項４のいずれか１項に記載の情報処理装置。
6. 前記処理部は、前記通行可能な領域から前記第２の領域を抽出し、抽出した前記第２の領域を除いた前記通行可能な領域から前記第１の領域を抽出する、請求項１～請求項５のいずれか１項に記載の情報処理装置。
7. 前記取得部は、前記ロボットの機種ごとに異なる前記ロボットの大きさに関する情報を取得する、請求項１～請求項６のいずれか１項に記載の情報処理装置。
8. 前記データ構造に格納された情報を反映した前記マップを表示させる表示制御部をさらに備える、請求項１～請求項７のいずれか１項に記載の情報処理装置。
9. 前記処理部は、前記データ構造に格納された情報に基づいた前記ロボットの経路計画を生成する、請求項１～請求項８のいずれか１項に記載の情報処理装置。
10. 移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及び前記ロボットの大きさに関する情報とを取得し、
    前記マップの前記通行可能な領域を前記ロボットの走行方向が定まる第１の領域と前記ロボットの走行方向が定まらない第２の領域とに分け、前記ロボットの大きさに関する情報を用いて、前記第１の領域の情報として前記第１の領域における前記ロボットの擦れ違い可否情報を、前記第２の領域の情報として前記ロボットが同時に存在できる台数の情報を格納した所定のデータ構造を生成し、
    生成した前記データ構造を出力する、
    情報処理方法。
11. コンピュータに、
    移動可能なロボットの通行可能な領域と通行不可能な領域とが区別されたマップ及び前記ロボットの大きさに関する情報とを取得し、
    前記マップの前記通行可能な領域を前記ロボットの走行方向が定まる第１の領域と前記ロボットの走行方向が定まらない第２の領域とに分け、前記ロボットの大きさに関する情報を用いて、前記第１の領域の情報として前記第１の領域における前記ロボットの擦れ違い可否情報を、前記第２の領域の情報として前記ロボットが同時に存在できる台数の情報を格納した所定のデータ構造を生成し、
    前記第１の領域の情報及び前記第２の領域の情報を格納した所定のデータ構造を生成し、
    生成した前記データ構造を出力する、
    処理を実行させる、コンピュータプログラム。