JP6598090B2 - 記憶媒体、ロボット動作を計画する方法、ロボット動作を計画するハードウェア、及びロボット - Google Patents

Description

本発明は、専用ロボットの動作を計画するハードウェアならびにその作製方法および使用方法に関する。
本出願は２０１５年１月２６日に出願された米国仮出願番号第６２／１０７，７５５号の利益を主張し、その数値、表、図面を含む全てが参照によって本願に組み込まれる。

今日、最も刺激的な計算機応用の多くがロボット工学に関わっている。近年のロボット工学の進歩により、ロボットが人々の生活に変化を及ぼす機会が大幅に拡大している。ロボットの開発は、医療、個人支援、汎用製造、捜索救助、軍事活動を含む広範囲な実社会での応用を目的として行われている。厳密に制御された環境（例えば、静的であって先験的に分かっている環境の組立ライン）でロボットが動作する従来のロボット工学応用とは違い、近年の応用では、ロボットが動作計画を行うことが要求される。

動作計画とは、目的を達成するのにロボットがどのように動かなければならないかを決定する処理である。例えば、ロボットが、それ自体や他の物体にぶつからずにアームを所望の物体まで動かしたいと望む場合がある。自ら移動して物体を操作するという動作計画を行う機能は、細かく制御されたり調整されたりしていない自然環境に対応するのに欠かせない機能である。まずロボットが周囲の物理的環境について情報を認識すると、次いでコンピュータが、その身体であるロボットの制御方法を決定して、ロボットが認識した環境で移動できるようにする。

多くの場合、ロボットには、障害物が存在する環境で実時間動作計画を行う機能に、実用上大きな制約がある。動作計画のアルゴリズムは、大量の計算を行うものが多く、各動作に対して莫大な数の衝突確認が必要とされる。既存の技術では通常、１台以上の汎用プロセッサおよび／またはグラフィックス・プロセッシング・ユニット（ＧＰＵ）で動作するソフトウェアによって衝突検出が実現される。しかし、汎用プロセッサで衝突検出ソフトウェアを動作させるのでは、実時間で動作計画を行うには速度が不十分であり、および／または（ＧＰＵを用いる場合は）多数の対象アプリケーションが非常に多くの電力を消費してしまう。

専用ロボットの動作を計画するハードウェアと、その作製方法および使用方法とを提供する。本記載のハードウェアは、実時間動作計画の問題に対処することができる。本記載のシステムおよび方法は、特定のロボットを利用し、そのロボットに関して実時間動作計画を行うことができる低電力かつ低コストのハードウェアアーキテクチャを生成することができる。

本明細書に記載のロボットの動作を計画するハードウェアは、特定ロボットに関して受信したロボット記述と受信したシナリオ記述とを用いて確率的ロードマップ（ＰＲＭ）を生成するソフトウェアツールを使用して設計することができる。次いで、このＰＲＭのエッジ毎に、ソフトウェアツールが、そのエッジに対する衝突検出部の設計を生成する。この衝突検出部は、各エッジに対応する動作が障害点または障害面に衝突するかどうかを算定する回路として実装される。この特定ロボットは、その衝突ジオメトリ、関節それぞれの自由度、および関節制限によって定義され、これらの情報はロボット記述に示されている。シナリオ記述は、確定領域、障害物の分布、初期ロボット姿勢の分布、および目標姿勢分布に関する設定値を含むことができる。

特定のロボットに対しては、入力を並行して処理するように構成された複数の衝突検出部を含む動作計画ハードウェアを設けることができ、各衝突検出部は確率的ロードマップのエッジ毎に対応する回路を備える。この回路は、ブール論理ゲートおよび／または参照テーブルを含むことができる。ロボット動作計画を行うためには、ロボットが、動作計画ハードウェアで、そのロボットのセンサシステムで取得した環境に関するデータと目標位置に関するデータとを受信し、動作計画ハードウェアの各衝突検出部で、衝突検出部に対応する確率的ロードマップのエッジが環境データで認識された障害物の部分と衝突するかどうかに関する表示を出力する。この動作計画ハードウェアの出力を用いて、その環境で衝突が起こるおそれがある確率的ロードマップのエッジを除去する。続いて確率的ロードマップのグラフ検索を行って、確率的ロードマップの残りのエッジに沿ったロボットの現在位置から目標位置までの最短経路を特定することができる。

この概要は、下記「発明を実施するための形態」で説明するいくつかの概念を簡潔な形で紹介するために提供するものである。この概要は、請求項に記載された主題の重要な特徴や本質的な特徴を特定することを目的とするものではなく、また、請求項に記載された主題の範囲の限定に使用することを目的とするものでもない。

図面を参照することにより、本開示の多くの観点をより良く理解することができる。これらの図面に関連していくつかの実装や実施例を記載するが、本開示は本明細書に開示する実装や実施例に制限されるものではない。
確率的ロードマップを使用した動作計画を示す図である。 確率的ロードマップを使用した動作計画を示す図である。 確率的ロードマップを使用した動作計画を示す図である。 第１の位置から第２の位置への移動によって生み出された掃引容積を示す図である。 動作計画処理の一例を示す図である。 計算装置で実行されるソフトウェアツールで実施され得る動作計画ハードウェア設計の生成処理を示す図である。 ロボットの動作を計画するハードウェアアーキテクチャの高水準概要図である。 例示的動作計画ハードウェアの高水準概略図である。 回路生成ソフトウェアに供給するように生成された、例示的エッジ構成に対するシンボリックテキストである。 ロボットの動作を計画するハードウェアに対して生成された例示的回路の一部を示す図である。

専用ロボットの動作を計画するハードウェアと、その作製方法および使用方法とを提供する。本記載のハードウェアは、実時間動作計画の問題に対処することができる。本記載のシステムおよび方法は、特定のロボットを利用し、そのロボットに対して実時間動作計画を行うことができる低電力かつ低コストのハードウェアアーキテクチャを生成することができる。

図１Ａ〜１Ｃは、確率的ロードマップを用いた動作計画を示す。背景技術で述べたように、動作計画とは、ロボットがある位置から他の位置へと動いて所望の位置まで達するまでの動作を突き止めるのに用いる処理群をいう。多関節ロボットは、関節で接続された一式の剛体で形成されているため、ある姿勢から他の姿勢へと動いて目標姿勢になるまでの動きを、動作計画によって決定する。

多関節型ロボットの姿勢は、その全ての関節に対して位置を割り当てることで描くことができる。このような全ての関節位置の空間はロボットの「コンフィギュレーション空間」と呼ばれ（しばしばＣ空間と呼ばれ）、Ｑで示される。Ｑにおける（関節位置の）コンフィギュレーションには、ロボットが置かれている環境内の障害物やそのロボット自体と衝突するものがある。Ｑ以外の空間は、自由空間と呼ばれる。

ロボット動作計画問題とは、図１Ａに示すように、ある開始コンフィギュレーションｑ_０から一群の目標コンフィギュレーションＧのうちいずれかのコンフィギュレーションまでの経路を探索することである。図１Ａを参照すると、Ｃ空間１００は障害物衝突領域１０２、１０４、および自由空間１１０を含むことができる。初期コンフィギュレーション１２２から一群の目標コンフィギュレーション１２４のうちいずれかのコンフィギュレーションまでの経路１２０を、自由空間１１０内に導出することができる。

動作計画問題を解決するのによく使用されるアプローチとしては、確率的ロードマップ（ＰＲＭ）を確立することがあり、これは、Ｋａｖｒａｋｉらによる『高次元コンフィギュレーション空間における経路計画のための確率的ロードマップ（“Probabilistic roadmaps for path planning in high-dimensional configuration spaces”）』（ＩＥＥＥロボティクスおよびオートメーションにおける対話（Transactions on Robotics and Automation）１２巻、４号、５６６〜５８０頁、１９９６年８月）に記載されており、その全体が参照により本明細書に組み込まれる。ＰＲＭはグラフで構成され、図１Ｂに示すように、各ノードをＣ空間内に点として示し、ある一対の点と点の間で衝突することなく直接移動が可能であれば、その点と点とを結ぶ。図１Ｂを参照すると、ノード１３０とエッジ１４０（２つのノードを結ぶ線）からなるＰＲＭがコンフィギュレーション空間１００の自由空間１１０内に示されている。

（ｑ_０，Ｇ）を一対とした場合、各ノードからｑ_０とＧまでの無衝突結線を見つけ出そうとし、次いでグラフ内にｑ_０とＧの間の経路を見つけ出すことよって動作計画を導き出すことができる。このことは図１Ｃに示されており、衝突が起こることのないｑ_０からＧまでの経路１５０を導出することができる。

上述のように、ＰＲＭは、コンフィギュレーション空間内の２点の間の直線経路（この直線経路は、ロボットの各関節のある位置から他の位置への直接的移動を表す）が、障害物に衝突するかどうかを判定すること（これを「衝突検出」という）によって構築される。この衝突検出は、各ロボット動作の掃引容積の幾何モデルを築くことで行うことができる。掃引容積とは、ある位置から他の位置へとロボットが移動するときに通る（三次元の）空間を言う。

図２は、第１の位置から第２の位置への移動により生じた掃引容積を示す。この動作例では、第１の剛体２０１を有するアームが第１の関節２０３で基部２０２に結合し、かつ第２の剛体２０４が第２の関節２０５で第１の剛体２０１に結合していて、このアームが位置１と位置２の間を移動すると、「掃引容積」と呼ばれる容積２１０が形成される。

図３は、動作計画処理の一例を示す。図３を参照すると、動作計画処理３００は全体として２部、つまり、オフライン部と実時間部に分けられる。最初にオフライン部で、ＰＲＭ（３０１）の作成が始まる。この工程は、ロボットの動作計画ハードウェアを設計する前に行うことができるが、特定のロボットに特化したものである。操作３０１でＰＲＭを作成するには、ロボットのＣ空間からノードをサンプリングし、サンプリングされたノード間に、自己衝突を起こさないと判定されれば、そのエッジを加える。つまり、例えば、ロボットが１つのノードで示されたコンフィギュレーションから他のノードで示されたコンフィギュレーションまで動いたときに、その動作によりアームがロボットに衝突するようであれば、そのエッジはこの初期ＰＲＭグラフに含めない。

このＰＲＭはグラフデータ構造の形式で保存することができ、また、任意で切り取って（すなわち「トリミング」して）ある効用関数に基づき特定のエッジを除去できる。初期の（任意で切り取られた）ＰＲＭは、ロボット以外の障害物がない世界の自由空間にのみエッジを有する。このＰＲＭは、動作計画中に使用するようにロボットの記憶システムに保存できる。このＰＲＭは、特殊ロボットの動作計画ハードウェアの設計（下記でさらに詳細に説明する）に用いることができる。

次に、オフラインで作成された（また、ロボットの記憶システムに保存できる）ＰＲＭを、実時間で使用し、認識された環境内に障害物があるために自由空間にはないエッジを無効とする（３０２）。ロボットの動作中、ロボットはそれが置かれた環境を解析して、動作計画ハードウェアへ送信する。ただし、ロボットが取得し解析する環境は、必ずしもロボットの現在位置と目標位置の間の直接経路内にある環境に限られるわけではないことを理解するべきである。ロボットは、回り道にのみ有効経路を有することもできる（しかもこの有効経路は、目標姿勢の視程範囲内にない場合もある）。このロボットは、環境を検出し分析できる様々なセンサシステムのいずれかを含むか、それと通信することができる。例えば、ロボットは赤、緑、青および深さ情報を（例えば赤外線で）受信することができる１台以上のカメラセンサを有することができる。他の例では、カメラ（またはその他センサ）を、壁、天井、床など環境内の１箇所以上の位置に、および／または環境内の物体（テーブルの上、箱の上など）に配置してもよい。環境内のセンサ（１つ以上）で取得した環境情報は、有線手段または無線手段を介してロボットに送信することができる。

センサ入力から受信したデータを解析して、障害物として扱われ得る環境内の物体を認識することができる。動作計画ハードウェアに提供される環境情報にこの物体認識を含めることができる。場合によっては、物体はボクセル値（例えば三次元画素）で示される。他の場合では、環境内で検出された物体を、各頂点が三次元座標で描かれた複数の三角形で構成されるメッシュモデルで示すことができる。もちろん、実装例によっては、確率的占有格子やオクトマップ（octomap）などの他の表示を使用することができる。

環境情報が動作計画ハードウェアに提供されると、動作計画ハードウェアは、まず、そのＰＲＭにおけるロボットの全動作が障害物（何らかの方法でそのロボットが示す）の部分と衝突するかを検出することで、障害物との衝突を起こすであろうＰＲＭのエッジの無効化を始めることができる。例えば、環境を画像撮影することによって、ロボット環境内にランプ（またはその他物体）を認識することができる。ランプ（または少なくともそのランプの表面）の三次元座標をハードウェアに送って並行分析を行うことができる。

ハードウェアでは、ＰＲＭのエッジ毎に衝突検出部が備えられている。各衝突検出部は、掃引容積が、その掃引容積が三次元空間の特定の点と衝突するかどうかを決定する単一のブール関数を有しているとみなすことができる。つまり、各衝突検出部は、（センサシステムで認識されるように）物体の表面上の１点がロボットの動作と衝突する場合は真（ｔｒｕｅ）と評価する１つのブール関数Ｆ（物体＿エッジ）の論理で構成することができる。このブール関数のシンボリックテキストの例を図７に示す。このブール関数は、三次元空間での描点に使用されるビット数と等しい数の入力を有する。本実装例では、三次元空間での描点に１５ビット（１軸毎に５ビット）が使用されているため、回路への１５入力によりブール関数を行う。

一般的な環境や用途では、三次元空間に描点する座標を極めて微細に特定する必要はない。ロボットの動作計画での要件の厳しさは、２つの物体が衝突するかどうかを判定する物理学的シミュレーションよりも緩い。つまり、物理学的シミュレーションでは、物体が衝突するかどうかを厳密に知る必要があるのに対して、ロボットの動作計画では、それが保守的に行われるとしても、衝突を避けるだけでよい（例えば、ある経路がおそらくは衝突を起こさないものであろうという場合であっても、保守的観点からその経路を消去する）。２つの物体がいつ衝突するかを保守的に予想すると、少ないビット数で計算を行うことができる。例えば、はるかにコストが高い３２ビットの浮動小数点演算の代わりに、５ビットの固定小数点演算で計算を行うことができる。一般的な環境に対してどのくらい低い分解能で足るかということを示すために、１ｍ^３の箱の周りを移動することができるアーム付ロボットを考えてみよう。座標を描くのに僅か５ビットで済むので、各次元での点の位置は１ｍ／２^５（約３．１ｃｍに相当する）まで分解することができる。

衝突検出が完了すると、衝突検出の結果を用いて、ロボットがエッジで結ばれたノード対の間を移動した場合衝突が起こるであろうとされるＰＲＭのエッジを無効とすることができる。例えば、各衝突検出部の出力を、単一ビット、フラグ、または、その衝突検出部によって示されるエッジと障害物の部分との間に衝突があるか否か示すその他の指数とすることができる。動作計画ハードウェアの出力を用いて、その環境内で衝突の可能性がある確率的ロードマップのエッジを除去する。

衝突を起こす可能性があるエッジを除去することで、残りのエッジを用いて正規動作計画（３０４）を決定することができる。例えば、ロボットは、確率的ロードマップのグラフデータ構造のエッジに対応する回路が、そのエッジには衝突がないことと示している場合には、そのエッジを有効と特定することで、正規動作計画を決定することができる。次いで、グラフに対してグラフ検索を行う。その動作計画ハードウェアプロセッサまたはそのロボットで動作しているソフトウェアにより、（衝突検出部の出力から衝突がないと示された）有効なエッジを用いて経路を選択することができる。例えば、ダイクストラの最短経路アルゴリズムや、ベルマン−フォードアルゴリズムを用いることができる。

図３に示すように、動作計画処理３００の一部をまずオフラインで実行することで、ロボットが環境内で動作している実時間で動作計画に関する決定を行うことができるようになっている。このような動作計画を実時間で決定することができる機能は、専用ロボットの動作を計画するハードウェアの使用によるものである。

図４は、（汎用コンピュータなどの）計算装置で実行されるソフトウェアツールによって実現可能な動作計画ハードウェア設計を生成するための処理を示す。本明細書に記載のロボットの動作を計画するハードウェアは、特定のロボットに関する受信したロボット記述４０１と受信したシナリオ記述４０２とを用いてＰＲＭを生成する（４０３）ソフトウェアツールを使用して設計することができる。次いで、ＰＲＭのエッジ毎に、ソフトウェアツールがそのエッジ（４０４）に対する衝突検出部の設計を生成する。エッジ毎の衝突検出部に対して生成された設計の例を図７に示す。衝突検出部は、論理ゲートおよび／または参照テーブルで構成される回路であり、ＰＲＭ（掃引容積に相当する）内のエッジとその環境内に存在する障害物の部分（例えば三次元空間における点として表される）との衝突を検出する。ソフトウェアツールは、衝突検出部の回路が記述された回路設計ファイル４０５を出力することができる。この回路設計ファイル４０５を実装方法に応じたさまざまなファイル形式で具現化することで、このファイルを、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）のプログラミングへの使用、集積回路製作用のレイアウトソフトウェアでの直接的もしくは間接的な使用、またはハードウェアプロセッサの作製に用いられるその他の設計ソフトウェアとの併用に適合させることができる。

ロボット記述４０１とシナリオ記述４０２の２つを入力することで、動作計画ハードウェア設計は、推定されるさまざまなロボットと環境の種類を考慮に入れ、またこれを格納することができる。

この特定のロボットは、その衝突ジオメトリ、関節それぞれの自由度、および関節制限によって定義され、これらの情報はロボット記述４０１に示されている。場合によっては、このロボット記述４０１を、業界標準の統一ロボット記述フォーマット（ＵＲＤＦ：Unified Robotic Description Format）ファイルの形式で提供することもできる。このＵＲＤＦファイルは、ロボットの衝突ジオメトリ、表示ジオメトリ（これらはしばしば視覚化の目的によって異なる）、および各関節の自由度と関節制限とを規定するものであり、ロボット製造業者からほぼ必ず入手可能である。もちろん、現在既知またはこれ以降に既知となる他の標準フォーマットを用いることもできる。

動作計画ハードウェアは特定のロボット用に設計されているため、効率の良いプロセッサを実現することができる。この効率性のいくつかは、動作計画ハードウェアが任意のロボットに関して包括的な動作計画を行う必要がないということに由来する。例えば、それぞれ長さが３フィートの２本のアームを有するロボットがシナリオに含まれている場合は、プロセッサはこれらの２本のアームだけに関して動作を計画すればよく、ロボットから３フィートより離れた物体を考慮する必要はない。さらに、プロセッサを特定のロボットに合わせて調整することで、高コストの（例えば高電力消費または低速度の）計算の多くを、オフラインかつプロセッサ設計の前段階で行うことができる。例えば、ロボット自体のみに基づいた方程式（例えば、ロボットの一方のアームを動かすともう一方のアームに衝突するかどうかを決定する計算）の結果を事前に計算し、これらの事前計算の結果をプロセッサに埋め込むことができる。これらの計算をオフラインで行うことができる機能により、当該分野における時間が掛かる計算および／または多くの処理を必要とする計算の必要性が回避される。

シナリオ記述４０２は、確定領域（例えば床、壁、作業空間の大きさ、特定の高さの机など）、障害物の分布（場所、大きさ、形状）、初期ロボット姿勢の分布、および目標姿勢の分布に対する設定値を含むことができる。この明細書で使用する「シナリオ」は、「物体が置かれた机」や「物体が入っている本棚」などといった環境の種類を示す。シナリオは、複数の障害物の分布や場所、大きさ、形状を含む。また、シナリオは、ロボットの初期姿勢分布および目標姿勢分布、ならびにさまざまなロボット部品の位置を含む。常時、ロボットは、１つのシナリオから導き出された１つのタスクに対して動作計画を行う必要がある。例えば「３フィートの高さの机に複数の物体が載っている」というシナリオで、障害物の分布、障害物の位置、障害物の大きさ／形状と、ロボットの初期姿勢および目標姿勢とが与えられている場合は、ロボットがテーブルの下でアームを動かすことができる必要はないと予測される。他の例としては、多くのシナリオにおいて、ロボットがそれ自体の背後にアームを動かすことができる必要がある場合はほとんどない。このようなシナリオの先験的な知識によって、予期される動作計画問題を解決するための資源を保全する（さらに多くのハードウェアを確保する）ことができる。所定の環境で２つ以上のシナリオが見込まれる場合は、これらの見込まれるシナリオを効果的に融合させた合成シナリオを利用するか、シナリオが切り替わるときにロボット動作を計画するハードウェアを再構成する。

ソフトウェアツールによって特定の最適化を行い、例えばＦＰＧＡに適合するほど小型でありつつも、シナリオから導き出された問題に対して計画を生成する可能性が高い設計を出力することができる。ただし、ロボット動作を計画するハードウェアの実装は、特定用途向け集積回路（ＡＳＩＣ）、ＦＰＧＡ、または他の回路として実現できることを理解するべきである。

例えば、任意でソフトウェアツールにより、工程４０３で生成されたＰＲＭからエッジをトリミングして、ＰＲＭ中のエッジの総数を減らすことができる。この任意の処理（４０６）は、問題インスタンスの作成と、寄与因子にしたがったエッジのトリミングとを含むことができる。寄与因子とは、初期ＰＲＭ中のエッジが問題インスタンスに対する最短解経路を導き出すのにどれだけ貢献したかを示す。エッジが最短解経路に僅かしか関係していないか全く関係していない場合は、そのエッジは除去されることもある。

場合によっては、シナリオ記述４０２からのシナリオ記述を用いて、複数の具体的な問題インスタンスを生成する。ＰＲＭにおける経路探索の失敗に対する許容度に基づいて、問題インスタンスの数を選択する。例えば、数十、数百、数千、またはそれ以上の問題インスタンスを生成してもよい。問題インスタンスとは、シナリオ記述４０２中のシナリオ記述から生成された領域／障害物／初期・目標タプルを指す。この問題インスタンスは、所定のシナリオの制約を満たす動作計画問題を示す。問題インスタンス毎に評価を行い、ＰＲＭ中の各エッジが最短解経路の探索にどれだけ貢献しているか（例えば、シナリオから導き出された問題を解決するのに必要なエッジだと確率的推定によって定義されたエッジの有用性）を判定する。実際には、ソフトウェアツールが各問題インスタンスで示された環境／シナリオを用いて動作計画ハードウェアのシミュレーションを行う。

一例では、複数本エッジをそれぞれのエッジの平均貢献度に基づいてトリミングして、閾値を満たすかそれを超えるエッジは保存し、そうでないエッジは除去することができる。他の例では、エッジを平均貢献度によってランク付けし、上位１０本、１００本、１０００本、またはその他の数（プロセッサに対応するエッジ予定量）のエッジを保存することができる。多くの場合、総エッジ量が予定量に達するまで、最も「有用性」が低いエッジを反復的に除去することができる。バックグラウンドタスクの知識なしにロードマップを疎化および切り取りできるアルゴリズムを組み込むこともできる。トリミング工程は非常に計算コストが高いが、このトリミング工程が行われるのはロボットとシナリオのペアごとに１度だけであり、しかもオフラインで実行される。

Ｃ空間内の点がランダムにサンプリングされる場合は、ＰＲＭの使用は確率的に終了する。アルゴリズムがＣ空間内の点をさらにサンプリングするので、解経路を導出できる確率は１になる傾向にある。しかし、プロセッサ設計でＰＲＭを固定すると、特にハードウェアとＰＲＭエッジの量を固定した場合には、解経路が見つからないという状況に遭遇するおそれがある。固定されたＰＲＭ設計を使用したときに起こるこのような状況を最小限にするため、ＰＲＭを生成する処理（例えばソフトウェアツール）に、所定のシナリオの制約を満たすサンプル動作計画問題シミュレーションを組み込むことができる。さらに、シナリオに特化したサンプリング戦略を組み込むことも可能である。例えば、あるシナリオで役に立つと期待されるサンプル（例えば机の上または机の近くでの行動を伴い得るタスクの場合は、机の真上のサンプルを示す）を具体的に組み込むことが可能である。これらのシミュレーションは任意の処理４０６に関連して説明する。

その他の最適な最適化として、衝突検出部を実現するゲートの数を低減することが挙げられる（４０７）。例えば、ブール最小化を用いることができる。

ある実装例では、ロボット動作を計画するＫｌａｍｐｔオープンソースソフトウェアを使用して、ロボットと領域に特化したＰＲＭを生成することができる（操作４０３）。このＰＲＭを、最適化工程４０６および／または４０７を用いて最適化し、ＦＰＧＡに適合させることができる。上述のように、（例えば処理４０６で）一旦ＰＲＭをトリミングすれば、（操作４０４で述べたように）そのトリミングしたＰＲＭを用いて１式の衝突検出部回路を生成することができる。次いで衝突検出部回路を最適化し、ブール最小化を用いて（例えばＥＳＰＲＥＳＳＯ論理ミニマイザーで）ゲートの数を低減することができる（４０７）。ソフトウェアツールで生成した設計に基づいて、所望のロボットとシナリオのペアに対してＦＰＧＡを構成（または再構成）することができる。

この他にも、工程４０６および／または４０７中に行うことができる最適化がいくつかある。例えば、ロボットのＣ空間の戦略的サンプリングを取り入れて設計のさらなる最適化を行うことができる。一般的なアルゴリズムは、経路探索の可能性が確率的に保証されるように、ランダムに点を選択する。しかし、ある実装例では、Ｃ空間内の点を戦略的にサンプリングして、衝突検出に必要なハードウェアを最小化し、および／または特定のロボットの予測シナリオを利用することができる。ハードウェアや電力の量が固定されている場合、衝突検出部が小さくなり電力の消費が少なくなればなるほど、より多くのＰＲＭ（より多くのサンプルとそれによるより多くの動作オプションを含む）をハードウェアに表示することができる。衝突検出部の大きさと消費電力を低減するにあたっては、物体や障害物との衝突を判定する同サイズの回路をすべてのロボット動作に備えなくてもよいことが確認されている。したがって、局所論理の最小化により適した回路を有する（すなわち、必要とされる回路がより小さい）掃引容積がもたらされるように、Ｃ空間内で点の選択を行うことが可能である。さらに、衝突検出部間における包括的な論理の最適化が容易になるように、Ｃ空間内で点を選択することができる。図７に示される下記の例のように、三次元空間に描点するのに１５ビットを用いることができ、これは２^１５項目の真理値表を意味する。これら真理値表のほとんどが疎化されるので、ブール関数を（例えば掃引容積に境界ボックスを用いて）効率よく計算することができ、（例えばＥＳＰＲＥＳＳＯ論理ミニマイザーを用いて最適化した場合に）比較的小さな回路を得られると考えられる。実際、実験により、ほとんどの真理値表は最適化してわずか数十個の論理ゲートにまで低減できることが分かっている。

衝突検出部それぞれの論理を（例えばＥＳＰＲＥＳＳＯを用いて）局所的に最適化することの他に、衝突検出部間で包括的に最適化することも可能である。多くの動作が同様の真理値表を有することになるので、この類似性を包括的最適化に有効に利用することができる。ＥＳＰＲＥＳＳＯと非常に簡略的なロボットアームとを三次元空間で用いた事前実験によって、包括的最適化のために多くの共通する部分式を取り除くことができることが分かっている。（実験ではＥＳＰＲＥＳＳＯ論理ミニマイザーを使用したため）実験のコンフィギュレーションでは最適化する衝突検出部が１６個に限定されたが、実際には衝突検出部は何個でも包括的に最適化可能である。

戦略的サンプリング（およびそれによる最適化）は、ロボットが直面するシナリオが開始点、目標点、障害物の分布の形態として分かっている場合にも利用することができる。例えば、多くのシナリオにおいて、ロボットの把持部を肩部の真上や肩部の後方の領域に配置させる計画よりも、ロボットよりも前方の作業空間に配置させる計画の生成が求められる可能性の方が大幅に高い。同様に、多くのシナリオにおいて、障害物は、ロボットの肘の真正面よりも、作業空間内または作業空間のはずれに出現する可能性の方が大幅に高い。シナリオによっては、障害物は小さい見込みとなり、他のシナリオでは大きい見込みとなる。このようなシナリオの事前の大雑把な情報を、実際の数多くのアプリケーションに容易に記述することができる。このようなシナリオ情報を用いて、サンプルを適応的に配置し、例えば、ロボットアームを肩部の後方に有するコンフィギュレーション範囲をより疎にすることができる。

図５はロボット動作を計画するハードウェアアーキテクチャの高水準概要図である。図５を参照すると、動作計画用の高水準アーキテクチャ５００は、ロボット仕様５０１、動作計画目標５０２、障害物データ５０３、衝突検出結果５０４、および動作計画５０５を含む。具体的には、ロボット動作を計画するハードウェア５１０がロボット仕様５０１、動作計画目標５０２、および障害物データ５０３を用いて衝突検出結果５０４および動作計画５０５を生成する。上述のように、ロボット仕様５０１（さらには動作計画目標５０２）をオフラインで使用して、実時間動作計画で使用されるハードウェアを生成することができる。ロボット動作を計画するハードウェア５１０の出力を、インターフェース５２０を介してロボットに提供すると、ロボットは動作計画５０５に従って動くようになる。

図６は、例示的動作計画ハードウェアの高水準概略図である。ロボット動作を計画するハードウェアを、特殊用途の動作計画プロセッサ６００とすることができる。動作計画プロセッサは、ロボットの各予測動作（または少なくともソフトウェアツールで作成したＰＲＭでの各動作）に対応する衝突検出部（例えば６０１、６０２、６０３・・・、６０Ｘ）と、経路計算部６１０とを含む。

プロセッサの入力により、環境における障害物情報６１１と経路目標（動作計画目標）６１２とを記述する。障害物情報６１１が衝突検出部によって受信される。好ましい実施例では、全ての衝突検出部が並行して動作する。しかし、実装例によっては、衝突検出部を時分割多重化して複数のロボット動作を提供してもよい。動作計画目標６１２および衝突検出部６０１、６０２、６０３・・・、６０Ｘの出力が経路計算部６１０に提供されると、この経路計算部６１０がグラフ検索を行って目標に到達するために使用する経路を特定する。プロセッサから出力されるのは経路６１３であり、任意で衝突検出情報を伴う。

図６を参照すると、特定のロボットに、入力を並行して処理するように構成された複数の衝突検出部を有する動作計画ハードウェアを備えることができる。各衝突検出部は、確率的ロードマップのエッジ毎に対応する回路を備えており、この回路は、論理ゲートおよび／または参照テーブルを有する。ロボット動作計画を行うにあたって、ロボットは、動作計画ハードウェアで、目標位置のデータとロボットのセンサシステムから取得した環境データとを受け取り、動作計画ハードウェアの衝突検出部それぞれで、その衝突検出部に対応する確率的ロードマップのエッジが受信したデータで特定された障害物の部分と衝突しているかどうかの表示を出力する。この動作計画ハードウェアの出力を用いて、環境内で衝突を起こす可能性がある確率的ロードマップのエッジを除去する。次いで、確率的ロードマップのグラフ検索を行い、確率的ロードマップの残りのエッジに沿った最短経路を特定することができる。

衝突検出回路に対してさらなる入力を行って、例えば、これらに限られるものではないが、握る、つかむ、押す、移動するなどの動作やこれらを組み合わせた動作などの特定のロボット動きを操作してもよい。ロボットの仕様に応じ、ロボット本体のさまざまな部分を介して特定の行動を起こすことができる。可能なロボット動作をモデル化して、ハードウェア設計に組み込むことができる。例えば、特定のロボットが物体をつかんでその物体と一緒に移動可能である場合（たとえば所謂「ピックアンドプレース」タスクで）は、ロボットがつかんでいる物体を立方体として非常に粗くモデル化することができる。次いでプロセッサが、片手ずつに含まれている複数の物体サイズのうちの１つを作動させるように構成することができる。これにより、衝突検出回路への入力数は多少増加するが、計画者の自由度は大幅に向上する。

動作計画で求められる計算量のほとんどは、ある動作が衝突につながるかどうかの検出に費やされる。先に述べたように、衝突検出は計算コストが高い。しかし、上述の動作計画ハードウェアを用いて特定の処理を並行して行うことで、多数の障害物に対する多数のロボット操作に関する衝突検出を同時に行うことが可能である。

動作計画ハードウェアの利点として、汎用ＣＰＵやＧＰＵに搭載される汎用ハードウェアが不要であるということが挙げられる、というのも、動作計画ハードウェアは命令を取り出して解読したり、ＩＥＥＥ−７５４準拠の浮動小数点演算を行ったり、汎用プロセッサのハードウェアやエネルギーを使用するその他のさまざまな機能を行ったりする必要がないからである。実際、動作計画目標を達成するために必要とされる精度は先験的に分かっているため、異常な幅（例えば、９ビットの固定小数点）となるような場合があっても、その粒度ぴったりの処理を行うようにハードウェアを適合させることができる。

図７は、生成されて回路生成ソフトウェアに供給される例示的エッジ構成に関するシンボリックテキストである。図７には、１本のエッジに対する論理が示されている。この例の場合、エッジと衝突する可能性があると認められた（空間内の三次元の点として表現される）障害物の部分が、ｘ軸に対して５ビット、ｙ軸に対して５ビット、ｚ軸に対して５ビットの合計１５ビットで表されている。各ビットは次の２つの設定可能な値を有する。すなわち、１つは文字（例えばＡ）で表される値であり、もう１つは文字ではないもの（例えば！Ａ）で表される値である。このシンボリックテキストには７０の衝突が反映されている。次に、回路生成ソフトウェアがＡＮＤ、ＯＲ、ＮＯＴ、ＮＡＮＤ、およびＮＯＲゲートおよび／または参照テーブルを用いて、このシンボリックテキストを実行する。場合によっては、いくつかまたは全てのゲートをＮＯＲもしくはＮＡＮＤ論理に変換することで、ゲートの数を最適化（低減）することができる。

図８は、ロボット動作を計画するハードウェアに対して生成された例示的回路の一部を示す。図８を参照すると、エッジ−１（８００）のエッジ論理などをはじめとする動作計画ハードウェアエッジ論理は、ブール回路８１０を含むことができる。このブール回路８１０は、１つのエッジ（掃引容積）と衝突する障害物の部分それぞれを示す複数の論理ゲート８１２と、図７のシンボリックテキストで記述されるような障害物の部分のブール論理表現の論理和をとって単一ビットとして出力するＯＲゲート８１４とを含む。フリップフロップ８２０を含んでここにブール回路８１０からの単一ビットの出力値を保存し、必要なときに適切な値を読み出し可能としてもよい。エッジ毎にエッジ論理を（例えば、エッジ−１（８００）に対してエッジ論理を、エッジ−２（８３０）に対してエッジ論理を、といった具合に）与えることで、障害物の部分を示す入力を受信したときには、全てのエッジの動作計画ハードウェアエッジ論理が並行してその入力を処理するようになる。

図９は、本明細書に記載のロボット動作を計画するハードウェアを組み込むことができる例示的ロボットのブロック図を示す。図９を参照すると、ロボット９００は、センサシステム９１０、アクチュエータシステム９２０、処理システム９３０、記憶システム９４０、およびロボット動作を計画するハードウェア９５０を含むことができる。図示はないが、ロボット９００は、さまざまな構成要素に必要に応じて電力を供給する電力システムを含むことができる。この電力システムに電池を使用してもよく、あるいは電力を供給するための有線手段（例えばＡＣアダプタとプラグ）および無線手段（例えば変換器や電荷貯蔵器を用いる）を含んでもよい。ロボット９００は図示されていない他のシステムや構成要素を含むことができるが、こうしたシステムや構成要素は簡略化のために図面では省略されているということを理解するべきである。

センサシステム９１０を、環境を検出し分析できる任意の好適なセンサシステムとすることができる。センサシステムの例としては、ビデオカメラの形態の光学センサ、マイクロ波センサ、音響センサ、およびその他のセンサ、画像センサ、赤外線センサ、超音波発受信機、マイクロフォン、力センサ、容量センサ、加速度計、ジャイロスコープ、ならびに温度センサが挙げられるが、これらに限られるものではない。センサシステム９１０は、センサおよび／またはそのセンサの制御からの信号の処理用にハードウェアを含んでもよい。センサシステム９１０の構成要素は、ロボットの一部になり得るものと、ロボットから離して配置できるものとがある。例えば、場合によっては、センサシステム９１０は環境内に配置可能なセンサを含み、そのセンサの出力の分析をロボットで局所的に行うかロボットから離れたところで行うかしてロボットに通信し、（使用可能な幾つものアプリケーションの中で）動作計画で使用することができる。場合によっては、センサシステム９１０の１台以上のセンサがロボット自体に配置される。

アクチュエータシステム９２０は、ロボット部品を動かすためのアクチュエータとモータを含むことができる。アクチュエータシステム９２０は、例えば、空気圧、電気、熱、磁気、または機械による作動を取り入れることができる。

処理システム９３０は、記憶システム９４０に保存されているソフトウェアの命令に従ってデータを変換または操作する１台以上のプロセッサを含むことができる。処理システム９３０のプロセッサの例としては、汎用中央処理装置、特定用途向けプロセッサ、論理デバイス、およびその他の処理デバイス、これらの組み合わせや変形が挙げられる。処理システム９３０は、ネットワーク接続要素、センサ、映像表示要素などの１つ以上の他の構成要素と併用されるシステムオンチップ（ＳｏＣ）であってもよく、またはこれに含まれる。

記憶システム９４０は、コンピュータ読み取り可能な命令、データ構成、プログラムモジュール、またはその他のデータなどの情報を記憶する任意の方法や技術により実現される揮発性または非揮発性の取り出し可能または取り出し不可能な媒体を含んでもよい。記憶システム９４０の記憶媒体の例としては、ランダムアクセスメモリ、読み出し専用メモリ、磁気ディスク、光学ディスク、ＣＤ、ＤＶＤ、フラッシュメモリ、磁気カセット、磁気テープ、磁気ディスク記憶装置もしくはその他の磁気記憶デバイス、またはその他の好適な記録媒体が挙げられる。どのような場合でも、記録媒体が伝搬信号や搬送波であることはない。記憶システム９４０は単一の記憶装置として実装することができるが、複数の記憶装置間で実装しても、あるいは同一場所に設置するか互いに関連しながら分散して設置されたサブシステムとして実装してもよい。記憶システム９４０は、処理システム９３０と通信可能なコントローラなどの付加的な要素を含んでも良い。

さまざまなソフトウェアアプリケーションやデータを記憶システム９４０に保存できる。例えばロボットオペレーティングシステムを記憶システム９４０に保存できる。場合によっては、１つ以上の確率的ロードマップを、記憶システム９４０のグラフデータ構造に保存できる。

ロボット動作を計画するハードウェア９５０は、ロボット９００の仕様に基づく特殊用途ハードウェアである。この動作計画ハードウェア９５０を、例えば、図４〜６を参照して上述したように設計および具現化することができる。場合によっては、ロボット動作を計画するハードウェア９５０をＦＰＧＡまたはＡＳＩＣとして具現化できる。場合によっては、動作計画ハードウェア９５０に記憶システム９４０のサブシステムを含めることができる。

実装例

Ｋｉｎｏｖａから入手した６自由度ＪＡＣＯ−２アームに対して動作計画プロセッサを設計した。このロボットのセンサシステムは、環境を視覚化できるように複数のＫｉｎｅｃｔ−２モジュールを含む。実装例として、動作計画プロセッサをアーム制御専用に設計して、ロボットの入出力ポートを介してロボットに接続した。オープンソースロボット財団（Open Source Robotics Foundation）より入手可能なロボットオペレーティングシステム（ＲＯＳ）ソフトウェアエコシステムを使用して、ロボットの制御とインターフェースによる動作計画プロセッサへの接続を行った。このＲＯＳエコシステムは、Ｋｉｎｅｃｔ−２モジュールの出力から環境内の物体を解析するのに使用され、このＲＯＳソフトウェアをロボットで動作させることよって生成された表現は動作計画プロセッサに通信される。

局所的および／または包括的最適化（図４に関連して上述した例など）によって、５０００程度の衝突検出部を大容量ＦＰＧＡに適合可能であることが分かった。さらに、（障害物の部分を特定する）三次元の点をＫｉｎｅｃｔ−２モジュールから直接（さらなる処理を行うことなく）プロセッサにストリーミング可能であった。これにより、ソフトウェアのさらなる最適化が可能であった。

別の実装例

メッシュモデル／三角形を実装する場合、各三角形が３つの頂点を有するので、各頂点を三次元座標で示すことができる。

衝突検出部が三角形同士の衝突を算出する回路を含む場合は、ロボットは、オブジェクト三角形を、動作計画ハードウェアと、ロボットの動作がこれらのオブジェクト三角形と衝突を起こすかどうかを検知するように構成された衝突検出部とにストリーミングすることができる。この実装例では、グラフ内の１本のエッジを１つの衝突検出部が担当しており、このエッジがロボットの動作となり得るものである。ロボットの動作は、その動作を行う過程で掃引される三次元空間における容積に相当する。ここで、衝突検出部は、掃引容積を三角形で構成された包体で表現することができ、各三角形に対して９ｋビット数を保存することができる。次いで、入力されてくるオブジェクト三角形との衝突を検出するために、衝突検出部はいくつかの計算を行って、三角形が互いに交わるかどうかを判定する。例えば、衝突検出部は、各オブジェクト三角形のエッジを各ロボット三角形と比較し、各ロボット三角形のエッジを各オブジェクト三角形と比較することができる。これらのロボット三角形とオブジェクト三角形の比較はそれぞれ、ドット積やクロス積を含む非常に多くの計算を伴う。２４回のドット積と７回のクロス積が行われる場合、ハードウェアは１１４個の乗算器と６９個の加算器を用いる。この実装は、三角形に関して（つまり、ロボット三角形のエッジの最小長と障害物エッジの最大長に対して）制約を課すことで最適化されて、１回の比較（２方向の比較ではなく１方向の比較）に要する計算量を低減することができる。

このような掃引容積三角形メッシュ記憶装置、乗算器、および加算器を有する約１００個の衝突検出部を、最新の大容量ＦＰＧＡに適合させることができると推定される。この数はグラフ内のエッジ数よりもはるかに少ないため、最新の大容量ＦＰＧＡで実行されるよりも（すなわちエッジが１００個よりも少ないロードマップを使用可能な環境で実行されるよりも）高い処理機能を有するロボットには、大型の衝突検出部が適している。時分割多重化を用いてこのような衝突検出部の数を増加させる場合は、メモリ帯域幅を十分に大きくしてエッジ状態の文脈切り替えに対処できるようにする必要があり、そうすることで新しいエッジの三角形状態を十分な速く読み取ることができる。

本明細書に記載の実施例や実施態様はあくまでも例示を目的としたものであり、これらの種々の改良や変更が当業者に示唆され、また、本出願の趣旨および範囲内に含まれることになることを理解されたい。当業者であれば、本発明が、十分にその目的を達成するように、そして記載された結果や利点、およびそれらに内在されるものを得るようにされていることを容易に理解するはずである。本明細書に記載の方法を伴う本実施例は、好ましい実施例の現時点での代表であり、例示的なものであって、本発明の範囲を限定することを目的とするものではない。当業者であれば、これら実施例の変更やその他の使用を想定できるはずであり、それらも請求項の範囲で定義される本発明の趣旨の範囲に包含されるものである。

Claims (15)

1. １つ以上のコンピュータ読み取り可能な記憶媒体であって、計算システムで実行されると、少なくとも、
   ロボットの衝突ジオメトリ、前記ロボットの各関節の自由度、および前記ロボットの関節制限を含むロボット記述を受信すること、
   シナリオ記述を受信すること、
   前記ロボット記述および前記シナリオ記述を用いて、前記ロボットの動作計画を行うために、前記ロボットのコンフィギュレーション空間にグラフを生成すること、
   前記グラフは、前記コンフィギュレーション空間における前記ロボットの姿勢を表す複数のノードと、前記コンフィギュレーション空間における対応する一対の姿勢間の動作を表す複数のエッジとを含んでおり、前記エッジの各々一つは前記ノードの複数の組の中の各組のノード同士を連結しており、ならびに、
   前記グラフの前記複数のエッジのエッジ毎に、前記ロボットが駆動されている環境にあるとしたら前記エッジに衝突するであろう障害物の全部分を示す各回路を備える各衝突検出部を作成すること、
   を前記計算システムに指示する命令が保存されている媒体。
2. 前記グラフは確率的ロードマップである、請求項１に記載の媒体。
3. 前記グラフのエッジ毎に前記回路を備える前記各衝突検出部を作成する前記命令は、前記計算システムに、少なくとも、
   前記ロボットが駆動されている環境にあるとしたら前記各エッジと衝突するであろう前記障害物のうちの１つの障害物の各部分と衝突を起こす可能性がある、前記ＰＲＭ中の全てのエッジを特定すること、および
   エッジ毎に、そのエッジと衝突する可能性がある複数障害物の部分の表現の論理和をとる論理和回路を作成し、任意で、前記論理和回路を最適化して前記論理和回路を形成するゲートの数を減らすことを指示する、請求項１に記載の媒体。
4. 前記衝突検出部の前記回路が、論理ゲートもしくは参照テーブル、または論理ゲートと参照テーブルの両方を含む、請求項１に記載の媒体。
5. 前記計算システムに、少なくとも、
   前記各衝突検出部をエッジ毎に作成する前に、前記グラフからいくつかのエッジまたはノードをトリミングすることを指示する命令をさらに含み、前記シナリオ記述が、確定領域、障害物分布、初期ロボット姿勢の分布、初期ロボット姿勢の分布、および目標姿勢分布を含み、前記グラフをトリミングする命令が、前記計算システムに、少なくとも、
   前記確定領域のタプル、前記障害物分布から選択した数の障害物、前記初期ロボット姿勢のうちの初期ロボット姿勢、および前記目標姿勢分布から選択した目標姿勢を用いて、複数の問題インスタンスを生成すること、
   問題インスタンス毎に、最短解経路の導出に関する各エッジの寄与因子を評価すること、および、
   これらのエッジの前記寄与因子に基づいて、前記グラフのエッジを除去することを指示する、請求項1に記載の媒体。
6. ロボットの動作計画を行うために前記ロボットのコンフィギュレーション空間において事前に計算されたグラフデータ構造のエッジ毎に設けられている複数の回路を備える動作計画ハードウェアにて、前記ロボットのセンサシステムから取得した環境および目標位置のデータであって、前記環境内の障害物の部分を表現するデータを受信すること、
   前記グラフデータ構造は前記コンフィギュレーション空間における対応する一対の姿勢間の動作を表す複数のエッジを含んでおり、前記グラフデータ構造の前記複数のエッジの各エッジに各回路が設けられており、前記複数の回路の各々は前記各エッジによって表される可能な動きのうちの各一つが衝突という結果になるか否かを判断する、
   前記動作計画ハードウェアによって障害物の部分と衝突していると示されている前記グラフデータ構造のエッジを除去すること、ならびに、
   正規動作計画を決定すること、
   を含む、ロボット動作を計画する方法。
7. 前記正規動作計画を決定することが、
   前記グラフデータ構造の検索を行って、前記障害物の前記部分と衝突していると前記動作計画ハードウェアで示された前記グラフデータ構造の前記エッジを除去した後に残った前記グラフデータ構造のエッジに沿って前記ロボットの現在位置と前記目標位置との間の最短経路を求めることを含む、請求項６に記載の方法。
8. 前記グラフデータ構造の各エッジの前記回路がブール回路を備え、前記データが前記環境内の前記障害物の前記部分を表現する三次元の点を含み、
   前記障害物の前記部分を表現する前記三次元の点のそれぞれに対して各ブール回路で並行して処理を行うことであって、このとき各ブール回路は前記三次元の点を受信して、そのブール回路に対応する前記エッジに関して衝突ありの表示または衝突なしの表示を出力することを含み、
   前記動作計画ハードウェアによって障害物の部分と衝突していると示される前記グラフデータ構造のエッジを除去することが、
   前記グラフデータ構造から、対応するブール回路からの衝突ありの表示を有するエッジを除去すること、
   を含む、請求項６に記載の方法。
9. 入力を並行して処理するように構成された複数の衝突検出部を備え、各衝突検出部がロボットの動作計画を行うために前記ロボットのコンフィギュレーション空間に生成されたグラフのエッジ毎に対応するブール回路を備え、
   前記グラフは、前記コンフィギュレーション空間における対応する一対の姿勢間の動作を表す複数のエッジを含んでおり、前記グラフの前記複数のエッジの内の各エッジに各衝突検出部が設けられている、
   ロボット動作を計画するハードウェア。
10. 前記ブール回路が、エッジ毎に、当該エッジと障害物の部分のブール論理表現との論理和を算出する論理和回路を備える、請求項９に記載のハードウェア。
11. 各ブール回路が、一組のビットで表される同じ三次元点を並行して受け取り、衝突ありを示す１または衝突なしを示す０をその三次元点と共に返送する、請求項９に記載のハードウェア。
12. センサシステム、
    アクチュエータシステム、
    処理システム、
    記憶システム、および
    ロボットの動作計画を行うために前記ロボットのコンフィギュレーション空間において事前に計算されたグラフデータ構造のエッジ毎に設けられている１つの回路を含む、複数の回路を備えるロボット動作計画ハードウェアと、を備え、
    前記グラフデータ構造は前記コンフィギュレーション空間における対応する一対の姿勢間の動作を表す複数のエッジを含んでおり、前記グラフデータ構造の前記複数のエッジの各エッジに各回路が設けられており、前記複数の回路の各々は前記各エッジによって表される可能な動きのうちの各一つが衝突の結果になるか否かを判断する、
    ロボット。
13. 前記ロボット動作計画ハードウェアが、少なくとも、前記センサシステムから取得した環境に関するデータであって、前記環境内の障害物の部分を表現する三次元の点を含むデータを受信し、前記障害物の前記部分を表現する前記三次元の点のそれぞれに対して、前記ロボット動作計画ハードウェアの前記回路が、その三次元の点を並行して処理して、その回路に対応するエッジに関する衝突ありの表示または衝突なしの表示をその三次元の点と共に出力し
    前記記憶システムに保存される前記グラフデータ構造をさらに備え、あるエッジに対応する前記回路が前記衝突なしの表示を出力した場合は、前記処理システムが前記グラフデータ構造の前記エッジを有効と特定し、前記グラフデータ構造のグラフ検索を行って前記有効と表示されたエッジに沿って最短経路を求める、請求項１２に記載のロボット。
14. 前記グラフデータ構造のエッジ毎の前記回路が、論理ゲートもしくは参照テーブル、または論理ゲートと参照テーブルの両方を含む、請求項１２に記載のロボット。
15. 前記ロボット動作計画ハードウェアが経路計算部をさらに備え、前記経路計算部が少なくとも、
    目標位置のデータと前記回路から出力された衝突検出結果とを受信し、
    前記衝突検出結果で表示された有効エッジを用いて、前記ロボットの現在位置から前記目標位置までの、前記グラフデータ構造内での経路を選択する、
    請求項１２に記載のロボット。