JP7511259B2 - モーション計画グラフ生成ユーザインターフェース、システム、方法、および物品 - Google Patents

Description

本開示は一般に、ロボットのモーション計画に関し、特に、ロボットのモーション計画に有用なモーション計画グラフの生成を容易にするユーザインターフェース、システム、方法、および物品に関する。

モーション計画は、可動付属肢を有するロボットおよび自律または半自律車両を含むロボット制御およびロボット工学における基本的な問題である。モーション計画はロボットが開始状態またはポーズ（又は、姿勢）から目標状態またはポーズへと追従することができる経路を完全に指定し、典型的には、動作環境内の障害物と衝突することなく、または動作環境内の障害物と衝突する可能性を低減する。モーション計画（又は、モーションプランニング／動作プラニング／動作計画／運動計画／motion planning／動作を計画すること）の課題は、ロボット自体の特性が変化しても、動作中の障害物だけでなく、ロボット自体の運動学を説明する比較的低コストで非常に高速な速度でモーション計画を実行する能力を含む。例えば、そのような特性はロボットが様々なサイズの物体を保持しているとき、異なるエンドエフェクタに変更するとき、または異なる付属肢（又は、アペンデージ／appendage）に変更するときに、ロボットによって占有されていると考えられる容積を含むことができる。また、プロセッサチップ回路上に記憶することができる限られた量のモーション計画情報に関しても課題がある。

モーション計画グラフツールキットはモーションプランナ（例えば、リアルタイムロボットモーション計画アクセラレータおよびRapidSense Spatial Perceptionシステム（又は、ラピッドセンス空間感知システム））によって使用されるモーション計画グラフ（本明細書では交換可能にロードマップまたはロードマップファイルまたはラティス（又は、格子／lattice）と呼ばれる）の作成または生成を可能にする。モーション計画グラフツールキットは、１つ以上の非一時的コンピュータまたはプロセッサ可読媒体上に記憶されるプロセッサ実行可能命令またはアプリケーション（例えば、ソフトウェアおよび／またはファームウェア）として実装される。モーション計画グラフツールキットは、直感的なユーザインターフェース、例えば直感的なグラフィカルユーザインターフェース（ＧＵＩ）を提供する。アプリケーションはエンドユーザがロボットのデジタルモデルまたは仮想モデル、およびロボットが動作する動作環境（本明細書では互換的にワークセルと呼ばれる）のデジタル表現または仮想表現と対話して、既知の位置を有する物体（例えば、静止物体）に関して運動学的（又は、動力学的に）に検査（又は、チェック）され、衝突検査されたモーション計画グラフまたはロードマップまたはラティスを生成または作成することを可能にする。運動学的検査はロボットが例えば、物理的な幾何学的形状または設計、またはロボット（例えば、関節の数、関節の位置、自由度、付属肢の長さ）に基づいて、定義された状態またはポーズになれるか、またはそれに移動し得るかを決定することを含み得る。衝突検査は、ロボットが例えば、環境内の静止物体と衝突することがないなど、衝突無しで定義された状態またはポーズになれるか、または移動することができるかどうかを判定することを含むことができる。

システムまたはアプリケーションは起点の（又は、原点の／オリジンの）または「シード」ポーズ（”seed” poses）の指定を可能にするユーザインターフェース（例えば、グラフィカルユーザインターフェース）を提示することができる。これは、有利には、ロボットおよび障害物を伴う環境の表現が提示されるプレゼンテーションウィンドを提供することができる。ユーザインターフェースは起点またはシードポーズが視覚的に指定されることを可能にするツールを提供することができ、ロボットの現在のポーズ、将来のポーズ、または過去のポーズさえも表すことができる。

システムまたはアプリケーションはいくつか（又は、多数）の追加ポーズ、例えば、隣接ポーズまたは同じ領域内のポーズを自律的に生成することができ、起点ポーズおよび追加または隣接ポーズはポーズグループ（又は、ポーズのグループ）を形成し、また、自律的にいくつかのエッジを形成し、各エッジが、起点ポーズおよび追加または隣接ポーズを含むポーズグループのポーズのそれぞれのペア間の移行（又は、遷移）を識別する。

システムまたはアプリケーションは、ロボットの自己衝突またはロボットにとって不可能なポーズを識別するなど、運動学的検査を自律的に実行してもよい。

システムまたはアプリケーションは、ポーズのそれぞれの衝突検査を自律的に実行することができる。システムまたはアプリケーションは、ポーズのそれぞれのペア（又は、対）の間の各移行の衝突検査を自律的に実行することができる。

システムまたはアプリケーションはロボットが自己衝突しているか、またはワークスペース内の物体と衝突している場合に、ポーズグループから任意のポーズを自律的に除去することができる。

ユーザインターフェースを提供するためのプロセッサベースのシステムにおけるオペレーションの方法は、
１つまたは複数の起点またはシードポーズの視覚的指定を可能にする少なくとも１つのユーザインターフェース要素を提供するステップと、
１つまたは複数の起点またはシードポーズの指定を受信するステップと、
例えば、隣接ポーズまたは同じ領域内のポーズなどのいくつかの追加ポーズを自律的に生成するステップであって、起点ポーズおよび追加または隣接ポーズがポーズグループを形成する、該ステップと、
いくつかのエッジを自律的に生成するステップであって、各エッジが起点ポーズおよび追加または隣接ポーズを含むポーズグループのポーズのそれぞれのペア間の移行を特定する、該ステップを含むものとして要約され得る。

この方法は、プロセッサベースのシステムによって運動学的検査を自律的に実行することをさらに含むことができる。運動学的検査を自律的に実行することは、ロボットの幾何学的形状に基づいて、プロセッサベースのシステムによって自律的に生成された追加ポーズの運動学的検査を自律的に実行することを含むことができる。

この方法は、各ポーズの衝突検査を自律的に実行するステップをさらに含むことができる。

この方法は、ポーズのそれぞれのペアの間の各移行の衝突検査を自律的に実行するステップをさらに含むことができる。

この方法はさらに、プロセッサベースのシステムによって、ポーズグループから、ロボットが自己衝突しているか、またはワークスペース（又は、作業空間）内の物体と衝突している任意のポーズを自律的に排除することを含むことができる。

本明細書では可動付属肢およびエンドエフェクタを有するロボットに関して、実装形態および例を一般的に説明するが、本明細書で説明する様々な構造、プロセス、および技法を、例えば自律車両を含む他のロボットに適用することができる。特に明記しない限り、本明細書におけるロボットへの言及は、移動可能な付属肢を有するロボット、ならびに自律車両の形態のロボットを含む。本明細書では、リアルタイムロボットモーション計画加速器（ＭＰＡ）に関して、実施形態および例を一般的に説明するが、他のモーション計画器は本明細書で一般的に説明されるモーション計画グラフ、ロードマップ、またはラティスを使用することができる。

図面において、同一の参照番号は、同様の要素または作用を示す。図面における要素のサイズおよび相対位置は、必ずしも一定の縮尺で描かれてはいない。例えば、さまざまな要素の形状および角度は一定の縮尺で描かれず、これらの要素のいくつかは、図面を見やすくするために、随時適当に拡大および配置されている。さらに、描かれた要素の特定の形状は、特定の要素の実際の形状に関するいかなる情報も伝えることを意図しておらず、図面における認識を容易にするために単に選択されたものである。
図１は、１つの例示としての実施に従って、ロボットが動作し得る環境の概略図である。
図２は、少なくとも部分的に、図１の環境で動作することができるロボットのモーション計画に有用なモーション計画グラフを生成するように動作可能な、１つの例示された実施形態によるプロセッサベースのシステムの機能ブロック図である。
図３Ａは、図示された一実施形態による、図２のプロセッサベースのシステムによって最初に提示されるグラフィカルユーザインターフェースの最初の画面のスクリーンプリント（又は、スクリーン画面）であり、モーション計画グラフを事前に生成する。
図３Ｂは、図示された一実施形態による、図２のプロセッサベースシステムによって２回目に提示されるグラフィカルユーザインターフェースの第１画面のスクリーンプリントである。
図３Ｃは、図示された一実施形態による、図２のプロセッサベースシステムによって提示されるグラフィカルユーザインターフェースの新規プロジェクトダイアログボックスのスクリーンプリントである。
図３Ｄは、図示された一実施形態による、図２のプロセッサベースシステムによって提示されるグラフィカルユーザインターフェースの衝突部品取り付けダイアログボックスのスクリーンプリントである。
図３Ｅは、図示された一実施形態による、図２のプロセッサベースシステムによって提示されるグラフィカルユーザインターフェースのエンドエフェクタダイアログボックスのスクリーンプリントである。
図３Ｆは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのロボットインスペクタダイアログボックス（又は、検査ダイアログボックス）のスクリーンプリントである。
図３Ｇは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのワークスペースインスペクタダイアログボックスのスクリーンプリントである。
図３Ｈは、図示された一実施形態による、図２のプロセッサベースシステムによって提示されるグラフィカルユーザインターフェースの起点ポーズ設定ダイアログボックスのスクリーンプリントである。
図３Ｉは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのロードマップ領域ウィンドのスクリーンプリントであり、複数の起点ポーズを有する例示的なロードマップ領域を示す。
図３Ｊは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのスクリーンプリントであり、経路可視オプション（又は、経路表示オプション）が選択されたときの、現在のエッジの例示的なロボット、ワークスペース、および経路を示す。
図３Ｋは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのスクリーンプリントであり、例示的なロボット、ワークスペース、およびエッジを示している。
図４Ａは、１つの例示の実施形態による、図１のロボットのための例示的なモーション計画グラフであって、対応する移行がロボットと環境内の１つ以上の障害物との間の衝突をもたらすであろうと判定された計画グラフのエッジを含む。
図４Ｂは、１つの例示の実施形態による、図１のロボットのための例示的モーション計画グラフであって、対応する移行がロボットと環境内の１つ以上の障害物との間の衝突をもたらすであろうと判定された計画グラフのエッジが除去されている。
図５は、１つの例示の実施形態による、プロセッサベースのシステムにおけるオペレーションの方法を示すフロー図である。
図６は、１つの例示の実施形態による、図５に示された方法を実行する際に使用され得る、プロセッサベースのシステムにおけるオペレーションの方法を示すフロー図である。

以下の説明においては、種々の開示の実施形態が正しく理解されるように、ある程度具体的に詳細を記載する。但し、当業者ならば、これら具体的な詳細の１つ以上を欠いても、または他の方法、他の構成部材、他の材料を用いても実施が可能であることは容易に理解するところであろう。他の例では、コンピュータシステム、アクチュエータシステム、および／または通信ネットワークに関連する周知の構造は実施形態の説明を不必要に曖昧にすることを避けるために、詳細には示されておらず、または説明されていない。他の例では実施形態の説明を不必要に曖昧にすることを回避するために、１つまたは複数のオブジェクトなどの知覚データおよびボリュメトリック表現を生成するための周知のコンピュータビジョン方法および技法は詳細には説明されていない。

本明細書及び特許請求の範囲において文脈上他に要求されない限り、用語「を有する（comprise）」及びそのヴァリエーション（comprises、comprising等）は、「含むが、それに限定されない（including, but not limited to）」として、確定していない（open）包括的な意味であるとみなされるべきである。

本明細書全体を通して、「一実施形態（one embodiment又はan embodiment）」とは実施形態に関連して説明された特定の特徴、構成または特質が少なくとも一実施形態に含まれることを意味し、したがって、本明細書全体を通して様々な箇所に「一実施形態（one embodiment又はan embodiment）において」という語句が現れることは必ずしもすべてが同じ実施形態を指すわけではない。さらに、特定の特徴、構造または特質は１以上の実施形態において任意の適当な方法で組み合わせられ得る。

本明細書および添付の特許請求の範囲で使用されるように、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は文脈上別段の明確な指示をしない限り、複数の指示対象を含む。また、用語「または」は文脈上別段の明確な指示をしない限り、「および／または」を含む意味で一般に使用されることにも留意されたい。

発明の名称及び要約は便宜上のものであり、本発明の範囲を表すものではなく、又は実施形態を意味するものでもない。

図１は、１つの例示としての実施形態による、ロボット１０２が動作し得る動作環境１００を示す。簡潔にするために、本明細書では、動作環境１００を環境１００と呼ぶ。環境はロボット１０２が動作し、移動することができる二次元または三次元空間を表す。ロボット１０２はデカルト（Cartesian）、ロボットアセンブリ用選択的コンプライアンスアーム（ＳＣＡＲＡ）、円筒座標（cylindrical）、デルタ（delta）、極座標（polar）、および垂直関節型ロボットを含むが、これらに限定されない、任意のタイプのロボットであってもよい。また、ロボットは自律的に又は半自律的に（すなわち、少なくとも部分的には自律的に）作動し、環境１００によって表される空間内を移動することができる自動車、飛行機、ドローン、又は任意の他の車両であってもよい。環境１００はロボットが動作し、ロボットの「構成空間」（しばしば「Ｃ空間」と呼ばれる）とは異なり、ロボットの「構成空間」は図４Ａおよび図４Ｂのモーション計画グラフに関して以下で参照され、「自動車および再構成可能な動作計画プロセッサのための動作計画」と題された２０１７年６月９日に出願された国際特許出願第ＰＣＴ／ＵＳ２０１７／０３６８８０号（その全体が参照により本明細書に組み込まれる）、ならびに「特定のロボット動作計画ハードウェアおよびその製造および使用方法」と題された２０１６年１月５日に出願された国際特許出願第ＷＯ２０１６／１２２８４０号（その全体が参照により本明細書に組み込まれる）に説明されているように、二次元または三次元空間である。構成空間は典型的には多くの次元（すなわち、三次元より大きい）である。特に、計画グラフの各ノードはロボットの特定の構成（ロボットの関節位置の特定のセットの完全な仕様である）、ロボットのポーズ、速度、および方位を含むことができるが、これらに限定されない、ロボットの状態を表す。計画グラフの各エッジは、ある状態から別の状態へのロボットの移行を表す。

図１を参照すると、環境１００は、障害物衝突領域を含むことができる。これらの障害物衝突領域は環境１００内の静的物体（例えば、ビン、コンテナ、柱、棚、建物、木、岩、家具）または動的物体（例えば、他のロボット、車両、人）によるものであり得る。例えば、障害物Ａ １１２および障害物Ｂ １０４は、ロボット１０２が障害物Ａ １１２または障害物Ｂ １０４のいずれかと同時に環境１００内の同じ空間を占有しようとした場合に、ロボット１０２が障害物Ａ １１２または障害物Ｂ １０４と衝突することが可能であるように、環境１００内に衝突領域を作り出す物体を表す。様々な実施形態では、図１に示すオブジェクトよりも少ないオブジェクトまたは追加のオブジェクトがあってもよい。

さらに、ロボット自体の幾何学的形状、ならびにロボットの数、位置、および移動の自由度に基づいて、ロボットの移動またはポーズに課される運動学的制約が一般に存在する。

モーション計画に対する課題は比較的低コストであるが、非常に高速でモーション計画を実行する能力を含む。これに関与するのは、ロボット１０２が占有されていると考えられる空間および環境１００内の障害物を効率的に表現し、伝達し、比較するための課題である。例えば、図１に示されるように、障害物Ａ １１２は、現在、ロボット１０２の前方にある。ロボット１０２が、ロボットアーム１０６のどの動作（およびロボット１０２の任意の動作）が障害物Ａ １１２との衝突をもたらすかを迅速かつ効率的に判定することができることは有利である。したがって、本開示はロボット１０２および１つまたは複数の障害物Ａ １１２によって占有される環境１００内で動作する、自律車両を含むロボット１０２のためのモーション計画を可能にするために、モーション計画グラフ、ロードマップまたはラティスを生成する解決策を提供する。特に、エンドユーザは１つまたは複数のポーズを指定することができ、システムまたはアプリケーションは、有利には１つまたは複数の自律的に生成された追加のポーズ、およびポーズ間のエッジを自動的にまたは自律的に決定することができる。システム又はアプリケーションは、ポーズ及びエッジの運動学的検査及び衝突検査を自動的に又は自律的に実行することが有利である。

図１は代表的な環境１００を示すが、典型的な環境は他のロボットに対応する物体、ならびに様々な他の自然または人工の静的および動的な物体および障害物を含む、多くの追加の物体および実体を含むことができる。本明細書で教示する概念は、図示したものよりも込み入った（又は、物の多い／populated）環境で同様に使用することができる。

図２および以下の説明は、例示された一実施形態による、様々な例示され説明されたモーション計画システムおよび方法が実施され得る、適切なプロセッサベースのシステム２００の簡潔で一般的な説明を提供する。

必須ではないが、実施形態の多くはコンピュータまたはプロセッサ可読媒体上に記憶され、衝突評価およびモーション計画動作を実行することができる１つ以上のコンピュータまたはプロセッサによって実行されるプログラムアプリケーションモジュール、オブジェクト、またはマクロなどの、コンピュータ実行可能命令の一般的なコンテキストで説明される。そのようなモーション計画の動作は、計画グラフのエッジに関連するロボットの掃引ボリューム（又は、掃引体積／swept volumes）の１つまたは複数の離散化された（discretized）表現を生成することと、ロボット掃引ボリュームの離散化された表現を生成するためにいくつかの離散化（discretizations）のうちのどれを使用するかを決定すること、環境中の障害物を含む、ロボット１０２が動作することになる環境の離散化された表現を生成すること、環境の離散化された表現を生成するために、複数の離散化のうちのどれを使用するかを決定すること、複数の計画グラフを決定すること、決定された複数の計画グラフおよびエッジ情報のそれぞれのセットを記憶すること、計画グラフのノードによって表される状態の間を遷移する際にロボット１０２の少なくとも一部によって掃引されるボリュームを表す情報を生成すること、計画グラフのエッジに関する衝突評価を実行すること（又は、計画グラフのエッジでの衝突評価を実行すること）、計画グラフのためのエッジ情報のセットを提供すること、計画グラフから１つまたは複数の最適化された結果を識別すること、計画グラフのエッジに関連する掃引ボリュームの離散化された表現と、ロボット１０２が動作する環境内の障害物の離散化された表現との間の衝突に対して衝突検査を行うこと、最適化がロボット１０２のための衝突のない経路を生成するかどうかを判定すること、及び、ロボット１０２のためのモーション計画を実施することのうちの１つまたは複数を含むことができるが、それらに限定されない。

図１のロボット１０２は、図２に示すセンサ２８２などのセンサを有し、これはプロセッサ２１２ａなどの１つまたは複数のプロセッサに知覚データを送る。知覚データは、どのボクセル又はボックス又は他の表現が現在の環境で占有されているかのストリームとして提供することができる。このデータは、占有グリッドまたは他のデジタル表現の形でプロセッサ２１２ａなどの１つまたは複数のプロセッサによって生成される（または前記プロセッサに提供される）。特に、ロボットまたは環境１００内の物体（例えば、障害物）のいずれかを表す場合、それらの表面をボクセル（３Ｄピクセル）または多角形（又は、ポリゴン）のメッシュ（しばしば三角形）のいずれかとして表すことができる。空間の各離散化された領域は、「ボクセル」と呼ばれ、３Ｄ（体積）ピクセルと等価である。場合によっては、代わりに物体をボックス（直角プリズム）として表すことが有利である。物体がランダムに成形されていないという事実のために、ボクセルがどのように構成されるかにはかなりの量の構造が存在することがあり、物体内の多くのボクセルは３Ｄ空間内で互いにすぐ隣り合っている。したがって、オブジェクトをボックスとして表すことは、はるかに少ないビットを必要とすることがある（すなわち、ボックスの２つの対向するコーナーについてのｘ、ｙ、ｚデカルト座標だけを必要とすることがある）。また、ボックスに対して交差テスト（又は、インターセクションテスト／intersection tests）を行うことは、ボクセルに対して行うことに匹敵する複雑さである。

多くの実施形態は複数のセンサの出力を組み合わせることができ、センサは、非常に細かい粒度のボクセル化を提供することができる。しかし、ロボット１０２がモーション計画を効率的に実行するために、ロボット１０２のプロセッサ２１２ａは様々な状態間の遷移を行うときに、ロボット１０２によって掃引される３Ｄ空間内の環境およびボリュームを表すために、より粗いボクセル（すなわち、「プロセッサボクセル」）を使用することができる。したがって、システム２００は、それに応じてセンサ２８２の出力を変換することができる。例えば、センサ２８２のアウトプットは各軸上で１０ビットの精度を使用することができ、したがって、センサ２８２から直接的に生じる各ボクセル（すなわち、「センサボクセル」）は３０ビットのＩＤを有し、２^３０のセンサボクセルがある。システム２００は１８ビットのプロセッサボクセルＩＤに対して、それぞれの軸上で６ビットの精度を（設計時（又は、計画時）および実行時に）使用し、２^１８のプロセッサボクセルが存在する。したがって、プロセッサボクセルごとに２^１２のセンサボクセルがある。実行時に、システム２００が、プロセッサボクセル内のセンサボクセルのいずれかが占有されていると判定した場合、システム２００はプロセッサボクセルが占有されていると見なし、それに応じて占有グリッドまたは他の表現を生成する。

ロボット１０２のための計画グラフの各エッジはまた、そのエッジによって表されるある状態から別の状態への計画グラフにおける遷移を行うときに、ロボット１０２によって掃引される３Ｄ空間内の体積に対応するいくつかの数のボクセル（またはボックス）を有する。そのエッジによって表されるある状態から別の状態への計画グラフの遷移を行うときにロボット１０２によって掃引されるこれらのボクセルまたはボックスは、計画グラフエッジ情報メモリ２８４などの計画グラフ専用のオフチップメモリに計画グラフのエッジごとに記憶することができる。様々な他の実施形態では、そのエッジによって表されるある状態から別の状態への計画グラフの遷移を行うときにロボット１０２によって掃引されたボクセルまたはボックスは、例えば、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）内のオンチップメモリなどの他の位置に、計画グラフのエッジごとに格納することができる。

１つの実施形態では、衝突評価（又は、衝突アセスメント）がまず、プロセッサ２１２ａのようなプロセッサに、すべての障害ボクセル（またはボックス）をストリーミングすることによって実行される。例えば、障害物Ａ １１２及び障害物Ｂ １０４を含む、環境１００を表す障害物ボクセル（又はボックス）が、プロセッサ２１２ａにストリームされて環境メモリ２９４に保存され得る。環境メモリ２９４は、プロセッサ２１２ａのオンチップメモリである。いくつかの実施形態では、環境メモリ２９４がフィールドプログラマブルゲートアレイ（ＦＰＧＡ）内のブロックＲＡＭ（ＢＲＡＭ）であってもよい。ある実施形態では、ＢＲＡＭが数キロビットのランダムアクセスメモリ（ＲＡＭ）を含む専用の構成可能な２ポートメモリユニットであってもよい。ＦＰＧＡは、これらのブロックのいくつかを含む。次に、ロボット１０２に対する計画グラフの各エッジに対するエッジ情報は計画グラフエッジ情報メモリ２８４からなど、計画グラフに充てられたオフチップメモリからストリーミングされる。エッジボクセル（またはボックス）ごとに、エッジの掃引ボリュームからストリーミングインされるとき、それが障害物ボクセル（またはボックス）のいずれかと衝突する場合、プロセッサ２１２ａは、計画グラフ内のそのエッジとの衝突を判定する。

例えば、エッジボクセルが計画グラフのエッジｘの掃引ボリュームからストリーミングインされるとき、プロセッサ２１２ａは、エッジボクセルを環境メモリ２９４に記憶された全ての障害物ボクセル（又はボックス）と比較するためにブール回路を使用することができる。システム２００が比較に基づいて、エッジボクセルが障害物ボクセル（またはボックス）のいずれかと衝突すると判定した場合、システム２００は、エッジｘとの衝突を記録する。この実施形態は、衝突評価が計画グラフのすべてのエッジ上で並行して実行される他の設計と比較して、衝突評価においてはるかに大きな計画グラフを使用することを可能にするので、衝突評価の技術を改善する。特に、これは、プロセッサチップ回路上に記憶することができる限られた量の計画グラフ情報に関する他の設計の欠点を克服するのに役立つ。本明細書で説明する衝突評価方法を使用すると、環境メモリ２９４などのオンチップ記憶装置は、多くの場合、すべての障害物ボックスを記憶するのに十分以上である（ボクセルを使用する場合はそれほどそうではない場合があるが）。これは、より安価なオフチップ記憶装置に大きな計画グラフおよび／または複数の計画グラフを記憶する能力を提供する。例えば、これは大きな計画グラフおよび／または複数の計画グラフを、いくつかの実施形態ではダイナミックランダムアクセスメモリ（ＤＲＡＭ）のような安価なタイプのメモリである計画グラフエッジ情報メモリ２８４に記憶する能力を提供する。

様々な実施形態では、そのような動作が完全にハードウェア回路で、またはシステムメモリ２１４などのメモリストレージに格納されたソフトウェアとして実行され、１つまたは複数のマイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、グラフィックス処理ユニット（ＧＰＵ）プロセッサ、プログラムドロジックコントローラ（ＰＬＣ）、電気的プログラマブルリードオンリメモリ（ＥＥＰＲＯＭ）などの１つまたは複数のハードウェアプロセッサ２１２ａによって、またはメモリストレージに格納されたハードウェア回路およびソフトウェアの組合せとして実行され得る。

また、知覚、計画グラフ構築、衝突検出、および経路探索の様々な関連する態様の実施は、その全体が参照により本明細書に組み込まれる「自動車および再構成可能な動作計画プロセッサのための動作計画」と題された２０１７年６月９日に出願された国際特許出願第ＰＣＴ／ＵＳ２０１７／０３６８８０号、「特定のロボット動作計画ハードウェアおよびその製造および使用方法」と題された２０１６年１月５日に出願された国際特許出願第ＷＯ２０１６／１２２８４０号および「動的オブジェクトを有する環境における自動車の動作計画を容易にするための装置、方法、および物品」と題された２０１８年１月１２日に出願された米国特許出願第６２／６１６，７８３号にも記載されている。当業者は例示された実施形態、ならびに他の実施形態はロボット、ハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサベースの、またはプログラム可能な家庭用電化製品、パーソナルコンピュータ（「ＰＣ」）、ネットワーク接続されたＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む、他のシステム構造および構成、ならびに／または他のコンピューティングシステム構成を用いて実施することができることを理解するであろう。実施形態またはその一部は、通信ネットワークを介してリンクされたリモート処理デバイスによってタスクまたはモジュールが実行される分散コンピューティング環境で（例えば、設計時および事前実行時に）実施することができる。分散コンピューティング環境では、プログラムモジュールがローカルおよびリモートメモリ記憶装置または媒体の両方に配置されてもよい。しかしながら、モーション計画を改善するのを助けるためには、ある種の情報がどこにどのように記憶されるかが重要である。

例えば、様々なモーション計画の解決策はロードマップ（すなわち、計画グラフ）をプロセッサに「ベークイン」し、ロードマップ内の各エッジはプロセッサの再構成不可能なブール回路に対応する。プランニンググラフ（又は、計画グラフ）がプロセッサに「ベークイン」される設計は、複数のまたは大きな計画グラフを格納するためのプロセッサ回路が限られているという問題を提起する。

１つの解決策は、計画グラフ情報をメモリ記憶装置に配置する再構成可能な設計を提供する。このような解決策では再び、計画グラフの各エッジについての情報が存在するが、この情報は回路にベーク（又は、べークイン）される代わりにメモリに記憶される。各エッジはロボット１０２の動作に対応し、各動作は、３Ｄ空間内のボリュームを掃引する。この掃引ボリュームはいくつかの障害物ボクセル（またはボックス、しかしながら、様々な実施形態で障害物を表すことが決定されてもよい）と衝突する。このような解決策では、このエッジが衝突するボクセルがメモリに記憶される情報である。

いくつかの実施形態では、システムまたはアプリケーションが実行時に複数の計画グラフ間を動的に切り替える（すなわち、プロセッサを再構成する）ことを提供してもよい。例えば、物体を把持することができるエンドエフェクタを有するロボットを考える。何かを保持しているときと、何かを保持していないときとで、ロボットアームが３Ｄ空間の異なる部分に衝突する。一例は、エンドエフェクタを有するアームの端部に大きなボールを保持するロボットアーム１０６である。ロボット１０２が何かを保持している場合、ロボット１０２が「何も保持していない」ときに対応する計画グラフは動作しない。逆に、ロボット１０２が何も保持していない場合であっても、「何かを保持している」計画グラフを非常に控えめに使用することができるが、それは非効率的であり、ロボット１０２が最大の可能なオブジェクトを保持しているシナリオに対応する単一の計画グラフの使用を必要とする。代わりに、様々な実施形態ではシステム２００が異なる可能な特性に対応する計画グラフのファミリ、例えば、「何も保持していない」、「サイズｘの小さい球を保持している」、「サイズｙの直角プリズムを保持している」などを構築する。これらの計画グラフはロボット１０２が物を拾い上げ、それらを下に置くときに、プロセッサ２１２ａによって計画グラフエッジ情報メモリ２８４に入れたり、そこから出したりすることができる。この解決策は、エンドエフェクタが時々変化するロボットにも適用される。例えば、ロボット１０２は、第１のセット（又は、組）の寸法を有する第１のエンドエフェクタを有する構成であってもよい。この第１のエンドエフェクタは、第２のセットの寸法を有する第２のエンドエフェクタとスワップ（又は、交換）されてもよい。第１のエンドエフェクタが第２のセットの寸法の第２のエンドエフェクタとスワップされると、ロボット１０２は、第２のエンドエフェクタを有する異なる配置になる。第２のセットの寸法の寸法が第１のセットの寸法の寸法と異なる場合、ロボットによって掃引されるボリューム（又は、体積）は、エンドエフェクタが交換されると変化する。また、例えば、ロボットが自律型または部分的に自律型の車両である場合、車両は第１の期間の間、第１の配置において第１のセットの寸法を有し、同じ車両は、第２の期間の間、第２の配置において第２のセットの寸法を有することができる。例えば、車両は第１の構成では空であり、第２の構成では完全に積載されており、車両の重量を変化させ、場合によっては、例えば、曲がり角またはカーブの周りをコーナリングするときに、道路上の車両の高さ、車両の下のクリアランス、または車両の軌道さえも変化させることができる。第２の寸法のセットの寸法が第１の寸法のセットの寸法と異なる場合、車両によって掃引されるボリュームは、第１の構成と第２の構成との間で変化する。同様に、第１の配置と第２の配置との間で軌道が変化する場合、車両によって掃引されるボリュームが配置間で変化する。したがって、システム２００は、異なるエンドエフェクタについて、異なる計画グラフを計画グラフエッジ情報メモリ２８４に格納する。

計画グラフは、前もって、例えば、実行時より前の設定時に生成することができる。いったん計画グラフが生成されると、それらはすべて計画グラフエッジ情報メモリ２８４に記憶されてもよく、プロセッサ２１２ａがそれらをスワップインおよびスワップアウトするか、またはロボットが特定のサイズの物体を把持しているときなど、ロボット１０２の現在の特性に基づいてどちらを使用するかを選択することは、比較的迅速かつ効率的である。

上述したように、いくつかの前処理活動は実行時の前に実行されてもよく、したがって、いくつかの実施形態ではこれらの動作が、ネットワークインターフェース２６０を介してプロセッサベースのシステム２００に通信ネットワークを介してリンクされる遠隔処理装置によって実行されてもよい。例えば、プログラミング段階は、関心のある問題に対するロボットの準備を可能にする。そのような実施形態では、実行時計算を回避するために、広範囲の前処理が活用される。ロードマップ内のエッジによって表される１つの状態から別の状態への計画グラフ内の遷移を行うときにロボット１０２によって掃引される３Ｄ空間内のボリュームに関する事前計算されたデータは、計画グラフエッジ情報メモリ２８４に格納され、実行時にプロセッサ２１２ａによってアクセスされ得る。システム２００はまた、実行時の前に、実行時中に起こり得るロボットの異なる可能な変化する寸法特性に対応する一群の計画グラフを構築してもよい（又は、システム２００はまた、実行時中に起こり得るロボットの異なる可能な変化する寸法特性に対応する実行時前の一群の計画グラフを構築してもよい）。次に、システム２００は、このような計画グラフを計画グラフエッジ情報メモリ２８４に記憶する。

実行時フェーズの間、センサ２８２は、プロセッサ２１２ａに知覚データを送信する。知覚データは、現在の環境に存在し、オンチップ環境メモリ２９４に格納されているボクセルまたはボックスのストリームであってもよい。環境メモリ２９４から検索された知覚データを計画グラフエッジ情報メモリ２８４に記憶された情報と比較するためにブール回路を使用して、プロセッサ２１２ａはどの動作が衝突を回避するかを計算し、ロボット１０２が従うべき計画グラフ内の対応する経路を選択する。次に、プロセッサ２１２ａが動作し、結果として生じる経路をアクチュエータシステム２６６に戻す。

図２は、プロセッサ２１２ａによって表される１つまたは複数のプロセッサと、システムメモリ２１４、計画グラフエッジ情報メモリ２８４、およびディスクドライブ２２４に関連するコンピュータ可読媒体２２６などの１つまたは複数の関連する非一時的機械可読記憶媒体とを備える、ロボット１０２用のシステムなどのプロセッサベースのシステム２００を示す。システムメモリ２１４、計画グラフエッジ情報メモリ２８４、およびディスクドライブ２２４に関連するコンピュータ可読媒体２２６を含む、関連する非一時的コンピュータまたはプロセッサ可読記憶媒体は、システムバス２１６などの１つ以上の通信チャネルを介してプロセッサ２１２ａに通信可能に結合される。システムバス２１６は、メモリコントローラを備えたメモリバス、周辺バス、および／またはローカルバスを含む、任意の既知のバス構造またはアーキテクチャを採用することができる。１つまたは複数のセンサ２８２およびアクチュエータシステム２６６も、システムバス２１６を介してプロセッサ２１２ａに通信可能に結合される。このような構成要素の１つまたは複数は、また、または代わりに、例えば、１つ以上のパラレルケーブル、シリアルケーブル、または高速通信が可能なワイヤレスネットワークチャネル、例えば、ユニバーサルシリアルバス３．０、ＰＣＩｅ（Peripheral Component Interconnect Express）等の１つ以上の他の通信チャネルを介して、またはＴｈｕｎｄｅｒｂｏｌｔ（登録商標）を介して、互いに通信することも可能である。

プロセッサベースのシステム２００はまた、ネットワークインターフェース２６０を介してプロセッサベースのシステム２００の様々な構成要素に直接通信可能に結合されたまたは間接的に通信可能に結合されたリモートシステム、例えば、デスクトップコンピュータ、ラップトップコンピュータ、ウルトラポータブルコンピュータ、タブレットコンピュータ、スマートフォン、ウェアラブルコンピュータ（図示せず）に通信可能に結合されてもよい。このような遠隔システムは、プロセッサベースのシステム２００およびプロセッサベースのシステム２００内の様々な構成要素とのプログラミング、構成、制御、または他の方法でのインターフェースまたは入力データに使用することができる。このような接続はインターネットプロトコルを使用する１つ以上の通信チャネル、例えば、インターネット等の１つ以上のワイドエリアネットワーク（ＷＡＮ）を介してもよい。上述したように、実行前計算（例えば、計画グラフのファミリの生成）はロボット１０２または他のロボットとは別個のシステムによって実行することができ、一方、システム２００がロボット１０２の物理的寸法の変化にリアルタイムで反応するように計画グラフを変更することができることが重要であるため、実行時計算は、ロボット１０２上にあるプロセッサ２１２上で実行することができる。

別段の記載がない限り、図２に示される様々なブロックの構造および動作は従来の設計のものであるか、またはその全体が参照により本明細書に組み込まれる「自動車および再構成可能な動作計画プロセッサのための動作計画」と題する２０１７年６月９日出願の国際特許出願第ＰＣＴ／ＵＳ２０１７／０３６８８０号、「特定のロボット動作計画ハードウェアおよびその製造および使用方法」と題する２０１６年１月５日出願の国際特許出願第ＷＯ２０１６／１２２８４０、および／または「動的オブジェクトを有する環境における自動車の動作計画を容易にするための装置、方法、および物品」と題する２０１８年１月１２日出願の米国特許出願第６２／６１６，７８３号に記載されている。その結果、そのようなブロックは参照により本明細書に組み込まれる参考文献を考慮して、当業者によって理解されるように、さらに詳細に説明される必要はない。

プロセッサベースのシステム２００は、１つまたは複数の処理ユニット２１２、システムメモリ２１４、計画グラフエッジ情報メモリ２８４、およびシステムメモリ２１４および計画グラフエッジ情報メモリ２８４を含む様々なシステム構成要素を処理ユニット２１２に結合するシステムバス２１６を含むことができる。いくつかの実施形態では、計画グラフエッジ情報メモリ２８４がシステムメモリ２１４であってもよく、またはその一部であってもよい。処理ユニットは、１つまたは複数の中央処理ユニット（ＣＰＵ）２１２ａ、デジタル信号プロセッサ（ＤＳＰ）２１２ｂ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などの任意の論理処理ユニットとすることができる。システムメモリ２１４は、リードオンリーメモリ（「ＲＯＭ」）２１８およびランダムアクセスメモリ（「ＲＡＭ」）２２０を含み得る。計画グラフエッジ情報メモリ２８４はＤＲＡＭなどのＲＡＭを含み得る。ＲＯＭ２１８の一部を形成し得る基本入出力システム（「ＢＩＯＳ」）２２２は、スタートアップ時など、プロセッサベースのシステム２００内の要素間で情報を転送するのに役立つ基本ルーチンを含む。

プロセッサベースのシステム２００は例えば、ハードディスクから読み書きするためのハードディスクドライブ、リムーバブルフラッシュメモリデバイスから読み書きするためのフラッシュメモリドライブ、リムーバブル光ディスクから読み書きするための光ディスクドライブ、または磁気ディスクから読み書きするための磁気ディスクドライブであってもよいディスクドライブ２２４を含んでもよい。プロセッサベースのシステム２００はまた、様々な異なる実施形態において、そのようなディスクドライブの任意の組み合わせを含んでもよい。ディスクドライブ２２４は、システムバス２１６を介して処理ユニット２１２と通信することができる。ディスクドライブ２２４は当業者に知られているように、そのようなドライブとシステムバス２１６との間に結合されたインターフェースまたはコントローラ（図示せず）を含むことができる。ディスクドライブ２２４およびその関連するコンピュータ可読媒体２２６は、コンピュータ可読命令、データ構造、プログラムモジュール、およびプロセッサベースのシステム２００のための他のデータの不揮発性記憶装置を提供する。当業者は、ＷＯＲＭドライブ、ＲＡＩＤドライブ、磁気カセット、デジタルビデオディスク（「ＤＶＤ」）、ベルヌーイカートリッジ、ＲＡＭ、ＲＯＭ、スマートカードなど、コンピュータによってアクセス可能なデータを記憶することができる他のタイプのコンピュータ可読媒体を使用することができることを理解するであろう。

プログラムモジュールは、オペレーティングシステム２３６、１つ以上のアプリケーションプログラム２３８、他のプログラムまたはモジュール２４０、プログラムデータ２４２などのシステムメモリ２１４に記憶することができる。アプリケーションプログラム２３８はプロセッサ２１２に、計画グラフのエッジに関連するロボット掃引ボリュームの１つまたは複数の離散化された表現を生成すること、ロボット掃引ボリュームの離散化された表現を生成するために、いくつかの離散化のうちのどれを使用するかを決定すること、環境１００における障害物を含むロボットが動作する環境１００の離散化された表現を生成すること、環境１００の離散化された表現を生成するためにいくつかの離散化された表現のどれを使用するかを決定すること、複数の計画グラフを決定すること、決定された複数の計画グラフおよびエッジ情報のそれぞれの組を記憶すること、計画グラフのノードによって表される状態の間を遷移する際にロボットの少なくとも一部によって掃引されるボリュームを表す情報を生成すること、計画グラフのエッジに関する衝突評価を実行すること、計画グラフのためのエッジ情報のセットを提供すること、計画グラフから１つまたは複数の最適化された結果を特定すること、計画グラフのエッジとロボット１０２が動作する環境１００内の障害物の離散化された表現に関連する掃引ボリュームの離散化された表現の間の衝突に対し衝突検査を行うこと、最適化がロボットのための衝突のない経路を生成するかどうかを決定すること、およびロボットのためのモーション計画を実施することのうちの１つまたは複数を実行させる命令を含むことができる。アプリケーションプログラム２３８は本明細書および参照により本明細書に組み込まれる参照文献に記載されるように、プロセッサ２１２に（センサ２８２を介して）知覚、計画グラフ構築、衝突検出、および経路探索の他の動作を実行させる１つまたは複数の機械可読命令をさらに含むことができる。

アプリケーションプログラム２３８はさらに、プロセッサ２１２に、ロボット１０２が異なる寸法を有するときに対応する状態間の遷移においてロボット１０２によって掃引される異なるボリュームを表す計画グラフエッジ情報のそれぞれのセットを生成させ、計画グラフエッジ情報のそれぞれのセットに対応して計画グラフエッジ情報メモリ２８４に複数の計画グラフを記憶させる、１つまたは複数の機械可読命令を含むことができる。

アプリケーションプログラム２３８はさらに、プロセッサ２１２に、ロボット１０２が動作する環境１００の第１の離散化された表現の少なくとも一部分について、環境１００の第１の離散化された表現の少なくとも一部分を環境メモリ２９４に供給させ、格納させ、計画グラフの各エッジに対して、計画グラフエッジ情報メモリ２８４内にエッジ情報のそれぞれのセットを提供させ、格納させ、対応する遷移がロボット１０２の少なくとも一部分と、環境１００内の障害物Ａ １１２および障害物Ｂ １０４などの１つ以上の障害物の少なくとも１つの少なくとも一部分との間の衝突をもたらす計画グラフのエッジのいずれかを特定させる１つ以上の機械可読命令を含むことができる。

「環境」という用語は本例では障害物を含むロボットの現在のワークスペースを指すために使用される。「タスク」という用語は本例ではロボット１０２がその環境内の障害物と衝突することなく、ポーズＡからポーズＢに到達しなければならない（おそらく、何かを把持または落とす）ロボットタスクを指すために使用される。「シナリオ」という用語は本例では環境／タスク対のクラスを指すために使用される。例えば、シナリオは「３フィートのテーブルを有する環境内での所与の範囲内のサイズおよび形状を有するｘ障害物とｙ障害物との間でのピックアンドプレースタスク」とすることができる。このような基準に適合する多くの異なるタスク／環境対が、目標の位置、障害物のサイズおよび形状に応じて存在し得る。システム２００は、ネットワークインターフェース２６０を介して通信ネットワークを介してリンクされる１つ以上の遠隔処理装置を含んでもよい。そのような１つまたは複数のリモート処理デバイスはシステム２００に、様々な異なるシナリオのタスクおよび環境の対に対してロボット１０２が動作する環境１００の表現のそれぞれの離散化を生成させる、１つまたは複数の機械可読命令を実行することができる。例示的な実施形態では、それぞれの離散化のうちの少なくとも２つはボクセルのそれぞれのセットを含む。それぞれの離散化のボクセルは、それぞれの離散化内のサイズおよび形状のうちの少なくとも１つにおいて非均質（non-homogenous）であってもよい。また、それぞれの離散化のボクセルの不均一性のそれぞれの分布は、互いに異なっていてもよい。特に、離散化はそれぞれのボクセルのセットを含むことができ、それぞれの離散化のうちの少なくとも２つのボクセルはそれぞれの離散化内でサイズおよび形状のうちの少なくとも１つにおいて不均質であり、それぞれの離散化のうちの少なくとも２つのボクセルの不均質性のそれぞれの分布は互いに異なる。アプリケーションプログラム２３８はプロセッサ２１２に、ロボットが動作する環境１００の表現の生成されたそれぞれの離散化の有効性を評価させ、特定のシナリオに対して最も有効であると評価される生成されたそれぞれの離散化を記憶させる、１つまたは複数の機械可読命令を含むことができる。

アプリケーションプログラム２３８はロボット１０２が実行するタスクとロボットが動作する環境１００のペアを分類する特定（又は、識別）されたシナリオに基づいて、プロセッサ２１２に、ロボット１０２の１つの状態とロボット１０２の別の状態との間で遷移するときにロボット１０２が通過するそれぞれの領域を表すいくつかの掃引ボリュームを生成するために、いくつかの離散化のうちのどれを使用するかを決定させ、計画グラフ内の複数のエッジのそれぞれについて、決定された離散化を使用してエッジのそれぞれの掃引ボリュームを決定させる、１つまたは複数の機械可読命令をさらに含むことができる。アプリケーションプログラム２３８はさらに、プロセッサ２１２に、識別されたシナリオに対して最も有効であると評価される、ロボット１０２が動作することになる環境１００の表現の決定された掃引ボリュームのそれぞれの離散化を記憶させる、１つまたは複数の機械可読命令を含むことができる。

アプリケーションプログラム２３８はロボット１０２が動作する環境１００とロボット１０２が実行するタスクのペアを分類する識別されたシナリオに少なくとも部分的に基づいて、プロセッサ２１２に、環境１００の離散化表現を生成するためにいくつかの離散化のうちのどれを使用すべきかを決定させる、１つまたは複数の機械可読命令をさらに含むことができる。アプリケーションプログラム２３８はさらに、プロセッサ２１２に、環境１００を感知する１つまたは複数のセンサ２８２によって生成されたセンサ情報を受信させ、判定された離散化を使用して環境内に障害物がある場合にはそれを含む環境の離散化表現を生成させる１つまたは複数の機械可読命令を含むことができる。決定された離散化の複数のボクセルはそれぞれの離散化内の（又は、離散化内で）サイズおよび形状のうちの少なくとも１つにおいて不均質であってもよく、決定された離散化のボクセルの不均質性のそれぞれの分布はいくつかの離散化のうちの別の１つのボクセルの不均質性の分布と異なってもよい。

アプリケーションプログラム２３８はさらに、プロセッサ２１２に、ロボットが動作する環境内の任意の障害物と計画グラフのエッジの間の複数の計画グラフの衝突検査を実行させる１つまたは複数の機械可読命令を含むことができる。プロセッサ２１２は各計画グラフに対してこのような衝突検査を実行し、それに応じて計画グラフを一時的に更新し、最適化を実行し、更新された計画グラフからの最適化された結果（もしあれば）が満足条件を満たすかどうかを判定することができる。満足条件が満たされない場合、プロセッサ２１２は次の計画グラフに移動し、同じ動作を実行してもよい。満足条件が満たされる計画グラフが見つかると、プロセッサ２１２は、満足条件を満たす計画グラフからの最適化された結果のうちの１つによって識別される遷移をロボット１０２に適用する。

アプリケーションプログラム２３８はさらに、プロセッサ２１２に、図５および図６に示される方法を含むがこれに限定されない、本明細書で説明される様々な他の方法を実行させる１つまたは複数の機械可読命令を含むことができる。

様々な実施形態では上述の動作のうちの１つまたは複数がシステム２００の１つまたは複数のリモート処理デバイスによって実行することができ、これらのデバイスはネットワークインターフェース２６０を介して通信ネットワークを介して、またはロボット１０２上に配置された１つまたは複数のプロセッサ２１２によってリンクされる。

図２にはシステムメモリ２１４に記憶されるように示されているが、オペレーティングシステム２３６、アプリケーションプログラム２３８、他のプログラム／モジュール２４０、およびプログラムデータ２４２はディスクドライブ２２４の関連するコンピュータ可読媒体２２６上に記憶することができる。

プロセッサ２１２は、１つまたは複数の中央処理装置（ＣＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などの任意の論理処理装置とすることができる。市販のコンピュータシステムの非限定的な例としては米国Ｉｎｔｅｌ（登録商標）社が提供するマイクロプロセッサのＣｅｌｅｒｏｎ、Ｃｏｒｅ ２、Ｉｔａｎｉｕｍ、Ｘｅｏｎファミリ、米国Ａｄｖａｎｃｅｄ Ｍｉｃｒｏ Ｄｅｖｉｃｅｓが提供するＫ８、Ｋ１０、Ｂｕｌｌｄｏｚｅｒ、およびＢｏｂｃａｔシリーズマイクロプロセッサ、米国アップルコンピュータが提供するＡ５、Ａ６、およびＡ７シリーズマイクロプロセッサ、米国Ｑｕａｌｃｏｍｍ、Ｉｎｃ．が提供するＳｎａｐｄｒａｇｏｎシリーズマイクロプロセッサ、米国Ｏｒａｃｌｅ Ｃｏｒｐ．が提供するＳＰＡＲＣシリーズマイクロプロセッサが挙げられるが、これらに限定されない。別途記載されない限り、図２に示される種々のブロックの構成およびオペレーションは、従来の設計のものである。その結果、そのようなブロックは当業者によって理解されるので、本明細書でさらに詳細に説明される必要はない。

したがって、衝突の回避を容易にするために、設計時（実行時の前）に、１つまたは複数の計画グラフがシステム２００によって生成され、１つの状態から別の状態への様々な遷移を行うときに、ロボット１０２によってどの領域が占有されるかが判定される。例えば、ロボット１０２のための計画グラフのエッジは、領域３０２に対応するロボット１０２によって掃引される３Ｄ空間内のボリュームに対応するいくつかの数のボクセル（またはボックス）を有する。計画グラフの対応する遷移を行うときの領域に対応するロボット１０２によって掃引されるボクセルまたはボックスは、計画グラフエッジ情報メモリ２８４などの、計画グラフに専用のオフチップメモリに計画グラフのエッジに対応するものとして記憶することができる。次に、実行時に、障害物Ａ １１２（および障害物Ｂ １０４も）を含む環境１００を表す障害物ボクセル（またはボックス）が占有グリッドまたは他の表現の形でプロセッサ２１２ａに提供され（たとえば、ストリーミングされ）、オンチップ環境メモリ２９４に記憶される。システム２００は（占有グリッドまたは他の表現に基づいて）どのボクセルが占有されているかを決定し、現在占有されているボクセルと衝突する動きを使用しないことを決定する。特に、エッジの掃引ボリュームの一部を表すそれぞれのエッジボクセル（またはボックス）について、それが計画グラフエッジ情報メモリ２８４からストリームイン（又は、流入／stream in）されるとき、プロセッサは、占有グリッドまたは他の表現に基づいて、環境メモリ２９４に記憶されている障害ボクセル（またはボックス）のいずれかと衝突するかどうかを決定する。エッジボクセル（またはボックス）が障害物ボクセル（またはボックス）のいずれかと衝突する場合、システム２００は計画グラフ内のそのエッジとの衝突を判定し、計画グラフ内のそのエッジに関連するロボット１０２の動作を使用しないと判定する。

例えば、図１に示すロボットアーム１０６の運動を実行する前に、システム２００は、計画グラフエッジメモリ２８４から適用可能な計画グラフの全てのエッジのエッジボクセル（又はボックス）をストリームインし始める。各エッジについて、プロセッサ２１２ａは各エッジボクセル（又はボックス）に遭遇するとき、任意のエッジボクセル（又はボックス）が環境メモリ２９４（障害物Ａ １１２のためのものを含む）に記憶された障害ボクセル（又はボックス）のいずれかと衝突するかどうかを検査する。環境メモリ２９４に格納された障害物Ａ １１２の障害物ボクセル（またはボックス）は占有グリッドまたは他の表現に従ってその同じ領域を占有するので、掃引領域内の任意のエッジボクセル（またはボックス）はそのような衝突をもたらすことになる。プロセッサ２１２ａは障害物ボクセル（又はボックス）のいずれかと衝突するエッジボクセル（又はボックス）に遭遇するとすぐに、その後、プロセッサ２１２ａは、計画グラフのそのエッジを使用しないことを決定する。計画グラフのエッジの処理が終了すると、プロセッサ２１２ａは、環境メモリ２９４に記憶された障害物ボクセル（またはボックス）と衝突すると判定されなかった残りのエッジを使用して、ロボットを初期位置から目標位置に移動させる計画グラフ内の経路を決定する。

システム２００はまた、各計画グラフによって表される掃引ボリュームをどのように表すか、ならびに環境１００内の障害物をどのように表すかに関する決定を行うことができる。そのような決定は例えば、掃引ボリュームをボクセルまたはボックスで表すかどうか、使用するボクセルまたはボックスの形状およびサイズ、使用するボクセルまたはボックスのサイズおよび／または形状が不均一である離散化を使用するかどうか、およびどのシナリオでボクセルまたはボックスの異なる形状および／またはサイズを使用するかなど、どのように離散化を実行すべきかに関してプロセッサ２１２ａによって行われる決定を含むことができる。様々な実施形態では計画グラフのそれぞれによって表される掃引ボリュームをどのように表すか、ならびに環境１００内の障害物をどのように表すかに関する決定を行うための上述の１つまたは複数のそのような動作はネットワークインターフェース２６０を介して通信ネットワークを介してリンクされるシステム２００の１つまたは複数のリモート処理デバイスによって、またはロボット１０２上に位置する１つまたは複数のプロセッサ２１２によって実行され得る。

特に、システム２００は、ロボット１０２のワークスペースをボクセル（後でボックスにグループ化することができる）に離散化することを決定することができる。１つの例示的な実施形態は、三次元の各々において均一な量子化（又は、量化／数量化／quantization））を実行する。しかしながら、ロボットのワークスペースの異なる部分においてより小さい／より大きいボクセル及び／又は非立方体形状のボクセルを有することが有利であり得る。例えば、一実施形態はロボット１０２のすぐ目の前の空間においてより小さなボクセル（より細かい解像度）を使用し、ロボットが到達できる最遠端のところでより大きなボクセル（より粗い解像度）を使用する。したがって、様々な実施形態は、非一様量子化を使用および／または非立方体形状ボクセルを使用することができる。本開示はまた、システム２００がボクセルサイズおよび／または形状をどのように選択するかについてのアルゴリズムを提供する。

一実施形態では、実行時間の前に実行のためのトレーニングアルゴリズムを使用して、様々な異なるシナリオに対してどのボクセルサイズおよび形状を使用するのがよいかを決定する。システム２００は、１つまたは複数のシナリオからのタスク／環境ペアの所与のまたは生成された大きなセットを使用することによってトレーニングされ得る。次いで、システム２００は、トレーニングサンプルの大きなセットにわたって最も効果的であると評価される離散化を選択する。

例えば、任意の所与の環境／タスク対に対して、最適な離散化（または等しく最適な複数の離散化）が存在する。システム２００はＴ個の環境／タスクペア（ここで、Ｔは大きな数である）をテスト／トレーニングし、次いで、それぞれについて最適な離散化を記録することができる。これは多くの異なる離散化をもたらし得、その各々は１つのみまたは少数の環境／タスク対に対して最適である。すべてのＴ個の環境／タスク対をテストした後、システムは、サンプルのセット全体にわたって最も有効であると評価される離散化を選択する。このアプローチはまた、取り扱いにくいあらゆる可能な環境／タスク対に対してあらゆる可能な離散化を試みることを含む。

上記の問題を克服するために、システム２００はシステム２００が有限数の可能な離散化Ｇを考慮することを除いて、上記で説明したようなトレーニングを実行する。各環境／タスク対に対して、システムは、提供されたＧ個の離散化のうちのどれが最も効果的であると評価されるかを記録する。全てのＴ個の環境／タスク対を処理した後、システム２００は、最も多くの環境／タスク対において最も効果的であると評価される離散化を選択する。

一例として、ロボット１０２は、その前方の空間のボックスに面していてもよい。システムは６ビットが各次元における位置を記述するために使用されるように、空間を離散化することを決定してもよい（すなわち、各軸上に２^６の位置があり得る）。これにより、それぞれが一意の１８ビットＩＤを持つ２^１８ボクセルが生成される。計画時に、システム２００はあらゆるエッジの動作について掃引ボリュームを事前計算し、それをその掃引ボリューム内のボクセルＩＤの集合として記録する。掃引ボリュームがボクセルと部分的に交差する場合であっても、掃引ボリュームは、その掃引ボリューム内のボクセルＩＤの集合に含まれる。これが、より細かい解像度を使用することがより良い理由である。次に、実行時に、センサ２８２はプロセッサ２１２ａに、ロボット１０２の前に何があるかを知らせるが、予め計算された掃引ボリュームを表すボクセルよりはるかに細かい粒度であり、したがって、システム２００はセンサ入力を処理し、どのボクセルが現在占有されているかをプロセッサ２１２ａに通信する。いくつかの実施形態ではプロセッサ２１２ａがセンサ入力を処理し、他の実施形態ではセンサ入力を処理してプロセッサ２１２ａに通信するセンサ２８２のプロセッサなどの別個のプロセッサがある。プロセッサ２１２ａは環境メモリ２９４に記憶されている情報に基づいて現在環境にあるボクセルまたはボックスを、計画グラフエッジ情報メモリ２８４に記憶されている計画グラフエッジ情報の各エッジに対してリストされているボクセルまたはボックスと比較し、現在どのエッジが衝突しているかを決定する。そのような実施形態では、比較を可能にするために、実行時と同じ離散化が計画時に使用されることが重要である。

システム２００が非一様離散化を使用することを選択するとき、システム２００は１８ビットのボクセルＩＤおよび２^１８ボクセルを依然として使用してもよいが、ボクセルはキューブ（又は、立方体）である必要はない（またはそれらはキューブであってもよいが、すべて同じサイズではない）。再度、この実施形態では、システムが実行時と同じ離散化を計画時に使用することが重要である。非一様離散化を使用する場合、システム２００は計画時および実行時に使用され、最も効果的であると評価されるボクセルサイズおよび形状をシステムが選択するように、上述のようなトレーニングを使用して、各ボクセルのサイズおよび形状が何であるかを選択する。そのような訓練で使用される評価基準は解決することができる（例えば、システム２００が、ロボット１０２の目標を達成するための何らかの衝突のない経路を見出すことができる）タスクの割合および見出される経路の質に関する基準を含んでもよい。

モーション計画グラフまたはロードマップツールキットはモーションプランナ（例えば、リアルタイムロボットモーション計画アクセラレータおよびRapidSense Spatial Perceptionシステム）によって使用されるモーション計画グラフ（本明細書では互換的にロードマップまたはロードマップファイルと呼ばれる）の作成または生成を可能にする。モーション計画グラフツールキットは、１つ以上の非一時的コンピュータまたはプロセッサ可読媒体に記憶される一セットのプロセッサ実行可能命令またはアプリケーション（例えば、ソフトウェアおよび／またはファームウェア）として実施される。モーション計画グラフツールキットは、直感的なユーザインターフェース、例えば直感的なグラフィカルユーザインターフェース（ＧＵＩ）を提供する。このアプリケーションにより、エンドユーザは、ロボットのデジタルモデルまたは仮想モデルと、ロボットが動作する動作環境（本明細書では互換的にワークセルと呼ぶ）のデジタル表現または仮想表現と対話して、運動学的に検査され、衝突検査されたモーション計画グラフまたはロードマップを生成または作成することができる。

システム、アプリケーション、ユーザインターフェース、およびオペレーションの理解を容易にするために、最初に、高レベル概念のいくつかの概要をすぐ下に提供する。

プロジェクトは、モーション計画グラフ又はロードマップツールキットにおける最上位のコンテナ（又は、容器）である。各プロジェクトは、名前付きワークスペースのセット、ハブのセット、ロードマップ領域のセット、およびボクセル領域を含む。

ワークスペースは、環境内のロボットのある物理的構成を表す。周囲の作業セルまたはそれ自体との異なる衝突の可能性をもたらすロボットの物理的構成に対するいかなる修正も、別個のワークスペースと見なされるべきである。したがって、環境内のすべての障害物が固定されたままであっても、第１のワークスペースの物理的特性からのロボットの物理的特性の変化は、別個の第２のワークスペースに対応する。

ワークスペースには、それぞれ独自のロードマップ領域のセットがある。ワークスペースは、異なるワークスペースにわたって同じ領域をクローニングするために複製されてもよいことに留意されたい。モーション計画グラフやロードマップツールキットで作業している間、「アクティブワークスペース」という概念がある。これは、現在、モーション計画グラフやロードマップツールキットによって提供されている三次元ビューで視覚化されているワークスペースである。各ワークスペースは、最上位プロジェクトで定義されたすべての「ハブ」も継承し、各ロードマップ領域が他の領域やハブにどのように接続するかの設定が含まれる。この設定は、補間マトリクス（行列）と呼ばれる。エッジを生成するとき、各ロードマップ領域はこれらの設定に基づいて、他の領域およびハブと同様に、内部的に接続される。ワークスペースはまた、ロボットまたは静的シーン内のリンクの対が互いに衝突検査される設定を含む。この設定のセットは、衝突マトリクスと呼ばれる。プロジェクトで定義されているワークスペースごとに、ユーザはシステムまたはアプリケーションに「Occupancy Group」または*.ogファイルを生成させ、リアルタイムロボティックスモーション計画アクセラレータ（ＭＰＡ）などで実行時に使用する。

ボクセル領域は、システムによって使用されるカメラの視野を表す。ＭＰＡは動的障害物がこの領域にある場合にのみ、動的障害物を検査および／または回避する。ボクセル領域内に存在する任意のポーズまたはエッジは「ボクセル化」され、すなわち、ロボットがポーズで取る物理的空間（またはエッジモードである場合、エッジ内のすべての中間ポーズのセット）が計算され、ボクセルとして保存される。各エッジのボクセルの集合は実行時中の衝突検査のためにＭＰＡハードウェアに送信される「占有グループ」ファイルに保存される。

ロードマップ領域は、ポーズのグルーピング（又は、グループ）である。エッジを生成するとき、ロードマップ領域内のすべてのポーズは補間マトリクス内の設定に基づいて、ネットワーク内の他の領域およびハブと同様に、互いに接続される。ロードマップ領域の寸法、密度、および位置を構成することができる。ロードマップ領域内のすべてのポーズは、ロードマップ領域を作成または修正するときに指定される起点ポーズと呼ばれる、ロボットの様々な構成でシード（又は、導入／seed）される。

ハブはすべてのワークスペースで共有されるロボットの特定のポーズである。デフォルトでは、すべてのロードマップ領域がすべてのハブに接続される。ハブはホームポーズを指定したり、複数のロードマップ領域間の接続性を強制したりする場合に便利である。

可動付属肢を有するロボットを扱う場合、ポーズは、ロボットの特定の関節構成と組み合わされた三次元空間におけるエンドエフェクタの特定の点である。自律車両を扱う場合、ポーズは自律車両の三次元空間における特定の点と方向である。ポーズはロボットの関節が特定の関節構成にあるとき、ロボットのエンドエフェクタが三次元空間のどこにあるかを記述する回転成分と共に、ｘ、ｙ、ｚ変位を有する。ポーズは、ロボットアームがそれ自体または静的ワークスペース内の他の物体と衝突することなく、空間内のその点に到達することができる場合に有効である。衝突するか、または運動学的に実行不可能なポーズは無効とみなされ、視覚的に示され得る（例えば、赤で表示される）。

エッジは任意の２つのポーズ間の接続であり、２つの関連するポーズ間の遷移を表す。また、エッジは、補間タイプを有する。モーション計画グラフまたはロードマップツールキットは、ジョイント補間およびデカルト補間をサポートする。ジョイント補間モードでは、終点ジョイント構成間のロボットのジョイント空間で直線補間することにより、動作を計算する。デカルト補間モードでは、自律的に生成された付加ポーズの離散集合で、２つの終点フレーム間の三次元空間で補間することにより、動作を計算する。

いずれの補間モードにおいても、エッジは有効であっても無効であってもよい。ポーズの場合と同様に、エッジはその任意の部分が運動学的に実行不可能であり、かつ／または衝突している場合には、無効にされる。

衝突パーツ（又は、衝突部分／衝突部品）は、ロボットまたはモデル化された環境またはシーンの任意の位置に取り付けることができる単純な境界形状である。通常、衝突パーツは、ロボットがオブジェクトをピック（又は、把持）または配置したときのコリジョンボリュームの変化を表すために使用される。衝突パーツはまた、所望であれば、任意のキープアウトゾーンを生成するために使用され得る。

衝突マトリクスは、ポーズおよびエッジを生成するときに衝突について検査されるべき「ユニバーサルロボット記述フォーマット」（ＵＲＤＦ）リンクのペアのセットを定義する。２つのものが決して衝突しない場合、そのもののペアを検査から除去することができ、これにより、より高速なエッジ生成が可能になる。ワークスペースごとに１つの衝突マトリクスがあり、システムまたはアプリケーションのパフォーマンスが向上する。

補間マトリクスは、各ロードマップ領域が他の領域およびハブにどのように接続するかを定義する。各接続のオプションは、ジョイント補間、デカルト補間、または接続されていない。

モーション計画グラフまたはロードマップツールキットは、ロボットオペレーティングシステム（ＲＯＳ）と協働することができる。ＲＯＳはロボットミドルウェア（すなわち、ロボットソフトウェア開発のためのソフトウェアフレームワークの集合）である。また、マクロを用いてもよい。たとえば、モーション計画グラフやロードマップツールキットは、ＲＯＳで使用されるパッケージの構築（ビルド）に使用されるＣＭａｋｅマクロと関連コードの集合であるＣａｔｋｉｎで機能する場合がある。

次に、図３Ａ～図３Ｋに示す様々なユーザインターフェース要素を参照して、オペレーションを説明する。

モーション計画グラフまたはロードマップの作成を開始するために、プロセッサベースのシステムまたはプロセッサベースのシステムで実行されるアプリケーションが、多数のユーザインターフェース要素を介して多数の初期入力仕様を受け取る。

例えば、プロセッサベースのシステムまたはアプリケーションは、ロボットの記述またはデジタルモデルを、例えばデジタルファイルとして受信することができる。モデル化されるロボットについて、このファイルは、視覚メッシュ、衝突メッシュ、および運動学を定義する。デジタルモデルは、手動で作成することも、コンピュータ支援設計（ＣＡＤ）アプリケーション（ソフトウェアやファームウェアなど）からのエクスポートプロセスを介して作成することもできる。ロボットの記述は、標準化されたフォーマット、例えばＵＲＤＦを使用して提供されてもよい。例えば、ＳｏｌｉｄＷｏｒｋｓ（登録商標）アセンブリをＵＲＤＦファイルに変換する市販のプラグインがある。

また、例えば、ＵＲＤＦファイルがＲＯＳパッケージへのリンクを含む場合、プロセッサベースのシステムまたはアプリケーションは、ＲＯＳパッケージへのパス仕様をオプションで受け取ることができる。ＲＯＳ＿ＰＡＣＫＡＧＥ＿ＰＡＴＨは、ｃａｔｋｉｎワークスペース内のＲＯＳパッケージへのすべての可能なパスを含む環境変数である。この変数を使用すると、プロセッサベースのシステムまたはアプリケーションがＵＲＤＦファイルを正常に見つけて解析できる。

また、例えば、プロセッサベースのシステムまたはアプリケーションは、ＵＲＤＦ規格に含まれていないロボットに関する追加情報を含むファイルをオプションで１つ以上受け取ることができる。追加情報は標準フォーマット、例えば、「ＳＲＤＦ（Semantic Robot Description File）」フォーマットで受信されてもよい、追加情報の１つは、例えば、ＵＲＤＦ内のどのリンクが互いに衝突検査されるべきかを定義する「衝突マトリクス」であってもよい。このファイルは、プロセッサベースのシステムまたはアプリケーションにインポートして、ポーズおよびエッジの妥当性を検査するためにプロセッサベースのシステムまたはアプリケーションによって使用される衝突マトリックスを抽出することができる。

図３Ａは、記述された一実施形態による、先験的にモーション計画グラフを生成するために図２のプロセッサベースシステムによって最初に提示されるグラフィカルユーザインターフェースの第１の画面３００ａを示す。図３Ｂは、記述された一実施形態による、図２のプロセッサベースのシステムによって２回目に提示されるグラフィカルユーザインターフェースの第１の画面３００ｂを示す。

第１の画面３００ａは４つのプルダウンメニュー、すなわち、ファイルメニュー３０２ａ、編集メニュー３０２ｂ、カメラメニュー３０２ｃ、およびヘルプメニュー３０２ｄを含むメニューバー３０２を含む。第１のスクリーン３００ａは、また、ロボットモデル３０５及び動作環境又はワークスペース３０７の三次元表現が提示されるプレゼンテーションウィンド３０４を含む。第１の画面３００ａはプレゼンテーションウィンド３０４に隣接し、情報を提供するか、またはユーザ入力の入力または選択を可能にする様々なユーザインターフェース要素を含む１セットのパネルをさらに含む。パネルは例えば、プロジェクトパネル３０６、インスペクタパネル３０８、ビューコントロールパネル３１０、およびコンソールパネル３１２を含むことができる。

（ファイルメニュー）
ファイルプルダウンメニュー３０２は、ファイルに関連する多くのユーザ選択可能なオプションを提供する。

例えば、エンドユーザは、ファイルプルダウンメニュー３０２ａから新規プロジェクトメニュー項目を選択することができる。ファイルプルダウンメニュー３０２ａからの新規プロジェクトメニュー項目の選択に応答して、システムまたはアプリケーションは、「新規プロジェクト」ダイアログボックス３１４を提示することができる。

新規プロジェクトダイアログボックス
図３Ｃは、例示の一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースの新規プロジェクトダイアログボックス３１４を示す。

新規プロジェクトダイアログボックス３１４は、ユーザに新規プロジェクトを作成するように促す。新規プロジェクトダイアログボックス３１４は、プロジェクトのディレクトリ名となる名前を入力するための「プロジェクト名」フィールド３１４ａを提供する。新規プロジェクトダイアログボックス３１４はプロジェクトが作成されるディレクトリを入力するための「プロジェクトパス」フィールド３１４ｂを提供する。新規プロジェクトダイアログボックス３１４は、使用するＵＲＤＦまたは*.xacroファイルへのパスを入力するための「ＵＲＤＦパス」フィールド３１４ｃを提供する。新規プロジェクトダイアログボックス３１４は「ＲＯＳパッケージパス」フィールド３１４ｄを提供して、ＵＲＤＦがそのような名前を使用する場合、ファイルパスを指定するための「package://」プレフィックスを入力する。これは、これらの最上位ディレクトリへのパスを指定するために使用できる。新規プロジェクトダイアログボックス３１４はそれぞれプロジェクトパスフィールド３１４ｂ、ＵＲＤＦパスフィールド３１４ｃ、およびＲＯＳパッケージパス３１４ｄに対応するユーザ選択可能なブラウザアイコン３１４ｅ、３１４ｆ、３１４ｇのセットを提供し、ユーザはそれぞれのフィールドに対して適切な入力をブラウザで選択することができる。

新規プロジェクトダイアログボックス３１４は「キネマティックチェーン開始」フィールド３１４ｈを提供し、キネマティックチェーン（又は、動力学チェーン／一連の動力学処理）が開始するＵＲＤＦからのロボットリンクを指定する。指定されたリンクには、可動の親ジョイントがあってはならない。特に、キネマティックチェーン開始フィールドは、選択するリンクのスクロール可能なリストを提供することができる。新規プロジェクトダイアログボックス３１４は、キネマティックチェーンが終了する場合にＵＲＤＦからのロボットリンクを指定するためのキネマティックチェーン終了フィールド３１４ｉを提供する。このリンクはキネマティックチェーンスタートの子であるべきであり、子として可動ジョイントを有さないべきである。衝突検査が可能になるためには、ロボット内の各可動ジョイントが各ポーズに対して完全に分かっている必要がある。

ファイルメニュー
図３Ａ及び３Ｂに戻ると、ファイルプルダウンメニュー３０２ａはユーザ選択可能な「Load Project」メニューアイテムを含むことができ、その選択によりシステム又はアプリケーションは既存のプロジェクトをロードする。ファイルプルダウンメニュー３０２ａがユーザ選択可能な「Save Project」メニューアイテムを含むことができ、その選択によりシステム又はアプリケーションは現在のプロジェクトを同じ場所に保存する。ファイルプルダウンメニュー３０２ａがユーザ選択可能な「Save Project As」メニューアイテムを含むことができ、その選択によりシステム又はアプリケーションは現在のプロジェクトを新しい場所に新規事例（又は、インスタンス）として保存する。ファイルプルダウンメニュー３０２ａはユーザ選択可能な「Load Scene Snapshot」メニューアイテムを含み、その選択によりシステムまたはアプリケーションはrtr-apiから生成したスナップショットをプレゼンテーションウィンド３０４に表示のためにロードする。ファイルプルダウンメニュー３０２ａはユーザ選択可能な「Export Configs」メニューアイテムを含むことができ、その選択によりシステム又はアプリケーションはアクティブなワークスペースのすべての有効なジョイント構成をエクスポートする。ファイルプルダウンメニュー３０２ａはユーザ選択可能な「Export Edges」メニューアイテムを含むことができ、その選択によりシステム又はアプリケーションはアクティブなワークスペースのすべてのエッジをエクスポートする。ファイルプルダウンメニュー３０２ａはユーザ選択可能な「Export Poses」メニューアイテムを含むことができ、その選択によりシステム又はアプリケーションはアクティブなワークスペースのすべてのポーズをエクスポートする。

引き続き図３Ａおよび図３Ｂを参照すると、「edit」プルダウンメニュー３０２ｂはユーザが「設定」メニューを選択することを可能にし、「設定」メニューは、プロジェクト設定およびワークスペース設定のためのユーザ選択可能なオプションを提供する。

プロジェクト「設定」はユーザが自動ポーズ検証を設定（例えば、トグル）することを可能にする。自動ポーズ検証設定は、ロードマップ領域またはハブに対する何らかの変更がシステムまたはアプリケーションがポーズを自動的に再計算することになるかどうかを判定する。このプロセスはバックグラウンドで行われる。ユーザは、非常に大きな動作計画グラフまたはロードマップを用いて作業する場合、自動ポーズ検証を無効にしたい場合がある。

プロジェクト設定により、ユーザは起点ポーズが領域と共に回転するか否かを設定（例えば、トグル）することができる。領域と共に回転する起点ポーズの設定は、ロードマップ領域の回転がどのようにオペレートされるかを決定する。領域と共に回転する起点ポーズの設定が無効にされる場合、ロードマップ領域内のポーズの向きは、世界に対して固定されたままである。領域と共に回転する起点の設定が有効であれば、それらの方向は全体として領域とともに回転する。

ワークスペース設定により、ユーザはキネマティックチェーンを設定することができる。キネマティックチェーン設定は、システムが衝突検査ポーズ計算のために使用するキネマティックチェーンを設定する。このチェーンは、一旦設定されると編集できない。キネマティックチェーン設定を変更するために、エンドユーザは新しいプロジェクトを作成する。ワークスペース設定では、ＵＲＤＦ内のどのリンクが互いに衝突検査されるかをエンドユーザが設定（configure）できる。したがって、エンドユーザは物理的位置またはジョイント制限の制約のために、決して衝突しないリンク間の衝突検査を無効にすることを選択することができ、有利には処理時間を短縮する。設定（configuration）は、衝突マトリクスを介して実施することができる。

エンドユーザは、例えば「import SRDF」ユーザインターフェース要素を介して、システムまたはアプリケーションにＳＲＤＦファイルから衝突マトリクスをインポートさせることができる。

エンドユーザはシステムまたはアプリケーションに、「補間タイプマトリックス」ユーザインターフェース要素を介して、モーション計画グラフまたはロードマップが互いにどのように接続するか、および／またはハブにどのように接続するかを定義させることができる。利用可能なオプションは、JOINT、CARTESIAN、またはNOT CONNECTEDを含むことができる。

１つまたは複数のタブにより、エンドユーザは、ＵＲＤＦ内の任意のリンクの任意の位置に取り付けることができる様々な部品を作成することができる。システムまたはアプリケーションは、衝突検査を実行するときにこれらの部分を使用する。部品は様々な形態、例えば、ボックス、球、または円筒のいずれかをとることができ、部品ライブラリとして格納することができる。部品のサイズは、エンドユーザによって指定または調整することができる。

カメラ／ビューポイントメニュー（Camera/Viewpointメニュー）
カメラまたはビューポイントメニュー３０２ｃはユーザがビューを切り替えること、例えば、パースペクティブビューモードとオルソグラフィックビューモードとの間で切り替えることを可能にする。あるいは、三次元ビューに提示される１セットの軸の中心にある立方体（右上隅に位置する）を選択（例えば、クリック）して、カメラ設定間で切り替えることができる。

ヘルプメニュー
ヘルププルダウンメニュー３０２ｄを選択すると、ユーザが選択できる各種ヘルプメニューを備えたヘルプメニューが表示される。

プレゼンテーションウィンド
プレゼンテーションウィンド３０４は、ロードされたロボットワークセルの三次元ビューを提供する。エンドユーザはプレゼンテーションウィンド３０４内でパンし、軌道を描き（orbit）、ズームすることができる。ハブ、ロードマップ領域、ポーズ、エッジ、およびボクセル領域はすべてプレゼンテーションウィンド３０４内に視覚化される。オブジェクト（例えば、ロボット）を選択する（例えば、クリックする）と、選択されたオブジェクトが作成される。

プレゼンテーションウィンド３０４で利用可能なツールを使用して、ロボットモデル３０５および任意のロードマップ領域の両方を操作するいくつかの異なる方法がある。

プレゼンテーションウィンド３０４は「ＦＫパネル」ユーザ選択可能アイコン３０４ａを含み、その選択によりＦＫパネルのプレゼンテーションが行われる。ＦＫパネルはエンドユーザが関節角度を入力として指定することを可能にし、システムまたはアプリケーションは三次元空間におけるロボットの対応する位置を決定し、ロボットの対応する三次元位置を提示するであろう。

プレゼンテーションウィンド３０４は「ＩＫパネル」ユーザが選択可能なアイコン３０４ｂを含み、その選択はＩＫパネルのプレゼンテーションを引き起こす。ＩＫパネルはエンドユーザがロボットの少なくとも一部（例えば、エンドエフェクタ）の位置を三次元で指定することを可能にし、システムまたはアプリケーションはロボットの対応する関節角度を決定して、ロボットの一部を三次元空間内に位置決めし、対応する関節角度を提示する。

また、「ＦＫパネル」と「ＩＫパネル」は単にＣ空間と三次元空間または実世界空間との間を平行移動するだけであり、「ＦＫパネル」と「ＩＫパネル」は、エンドユーザがエンドエフェクタの並進および／または回転を微調整することを可能にする。各調整の増分は変更可能である。現在の位置が「世界」基準フレーム内、または任意の定義されたロードマップ領域の基準フレーム内で見ることができる。

プレゼンテーションウィンド３０４は、並進ウィジェット３０４ｃを含む。どの項目が選択されるかに応じて、システムまたはアプリケーションは並進ウィジェット３０４ｃを、ロボットのエンドエフェクタに、またはロードマップ領域またはボクセル領域の起点に出現させる。並進ウィジェット３０４ｃはエンドユーザが例えば、ポインタまたはカーソルを位置決めし（例えば、マウスオーバーし）、対応する軸上で選択する（例えば、クリックする）ことによって、選択されたアイテムを三次元（ｘ、ｙ、またはｚ軸）でドラッグすることを可能にする。翻訳ウィジェット３０４ｃはユーザが選択可能な（例えば、「Ｔ」ボタン）の選択（クリック）によって有効／無効にすることができる。

プレゼンテーションウィンド３０４は、回転ウィジェット３０４ｄを含む。どのアイテムが選択されるかに応じて、システムまたはアプリケーションは回転ウィジェット３０４ｄをロボットのエンドエフェクタに、またはロードマップ領域の起点に出現させる。回転ウィジェット３０４ｄは、エンドユーザが、選択されている間に、対応する軸の周りを選択（例えば、クリック）およびドラッグすることによって、選択されたアイテムを３つの軸（ｘ、ｙ、またはｚ軸）の周りで回転させることを可能にする。回転ウィジェット３０４ｄはユーザが選択可能なアイコン（例えば、「Ｒ」ボタン）を選択する（例えば、クリックする）ことによって、有効／無効にすることができる。

プレゼンテーションウィンド３０４は、スケーリングウィジェット３０４ｅを含む。システムまたはアプリケーションにより、スケーリングウィジェット３０４ｅがロードマップまたはボクセル領域の起点に出現させる。スケーリングウィジェット３０４ｅは、エンドユーザが選択されたオブジェクトの寸法を三次元（ｘ、ｙ、またはｚ）で変更することを可能にする。ロードマップ領域をスケーリングする場合、システムまたはアプリケーションは、その特定の領域の密度設定に基づいて、領域内のポーズの数を自動的に増加および／または減少させる。

プレゼンテーションウィンド３０４には、ユーザが選択可能なアイコン３０４ｆを間接ドラッグモードで含む。関節ドラッグモードがアクティブであるとき、並進、回転、およびスケーリングウィジェット３０４ｃ、３０４ｄ、３０４ｅは無効とされ、エンドユーザはロボット表現上の可動リンク上でホバー（例えば、マウスオーバー）することができる。リンクが選択されると、システムまたはアプリケーションはそのようなものを視覚的に示し（例えば、リンクを強調表示する）、可能な関節移動を表す視覚的指示（例えば、螺旋）の提示を引き起こす。次いで、エンドユーザは視覚的表示に対してリンク（例えば、ボール）の表現を移動させることができ、例えば、関節の位置を制御するために螺旋上でボールを上下に移動させることができる。システムまたはアプリケーションは、入力に従って位置を更新する。

プレゼンテーションウィンド３０４は、一セットの三次元コントロール３０４ｇを含む。エンドユーザは三次元コントロール３０４ｇを操作して、システムまたはアプリケーションに、プレゼンテーションウィンド３０４に提示される三次元ビューを調整させることができる。例えば、エンドユーザは、マウスまたは他のポインティングデバイス上のボタンを押し続けることによって、表現されたシーンの周りをパンすることができる。最終用途は、マウスまたは他のポインティングデバイス上の別のボタンを押し続けることによってビューを回転させることができる。エンドユーザは例えば、マウスまたは他のポインティングデバイス上のスクロールホイールを介してズームを制御することができる。プレゼンテーションウィンド３０４は例えば、三次元制御アイコン３０４ｇ（例えば、プレゼンテーションウィンド３０４の右上に示されている）を含むことができ、これは、エンドユーザがポインタで操作することができ、エンドユーザが特定の軸整列ビューに迅速に移動することを可能にし、また、オルソグラフィックモードとパースペクティブモードとを切り替えることを可能にする。

プロジェクトパネル（Projectパネル）
プロジェクトパネル３０６は、現在のワークスペースおよびプロジェクト内のすべてのオブジェクトをリストする。項目を選択する（クリックするなど）と、その項目が選択された項目になり、詳細情報が表示される。

プロジェクトパネル３０６は、エンドユーザが利用可能なワークスペースのすべてを見ること、ならびに新しいワークスペースを作成することを可能にするワークスペースセクション３０６ａを含む。新しいワークスペースを作成するために、エンドユーザは「ワークスペース名」テキストフィールドに名前をタイプし、「追加」ユーザ選択可能アイコン３０６ｂを選択する。エンドユーザは「アクティブワークスペース」ドロップダウンメニュー３０６ｃを使用して、どのワークスペースが現在のワークスペースであるかを選択することもできる。新しいワークスペースを作成することは、新しいワークスペースをアクティブワークスペースに自動的にしないことに留意されたい。現在アクティブなワークスペースがプレゼンテーションウィンド３０４に表示され、プロジェクトパネル３０６にリストされたすべての領域および衝突パーツはアクティブワークスペースに基づく。エンドユーザがクローニングするワークスペースを選択（例えば、クリック）し、次いで、インスペクタパネル３０８上の「複製」ユーザ選択可能アイコン３０８ａを選択することによって、既存のワークスペースを複製することができる。

投影パネル３０６は、ボクセル領域セクション３０６ｄを含む。ボクセル領域セクション３０６ｄはそれぞれが異なる機能を有する３つのユーザ選択可能なアイコン（例えば、ボタン）を有する。「ターゲット」ユーザ選択可能アイコン３０６ｅは、エンドユーザにボクセル領域を選択させ、インスペクタパネル３０８は選択されたボクセル領域に関する詳細を示し、プレゼンテーションウィンド３０４内に変換またはスケール制御をもたらす。「目」ユーザ選択可能アイコン３０６ｆはエンドユーザに、プレゼンテーションウィンド３０４上のボクセル領域の可視性をトグルさせる。「ボクセル」ユーザ選択可能アイコン３０６ｇはエンドユーザに、プレゼンテーションウィンド３０４上のボクセルの可視性をトグルさせる。

プロジェクトパネル３０６は、ロードマップ領域セクション３０６ｈを含む。ロードマップ領域セクション３０６ｈは、アクティブワークスペース内の利用可能なロードマップ領域のすべてをエンドユーザに示す。領域を選択する（例えば、クリックする）と、インスペクタパネル３０８上のその領域が選択され、プレゼンテーションウィンド３０４内で、選択された領域を回転、スケーリング、または変換することができる。「追加」ユーザ選択可能アイコン３０６ｉを選択する（例えば、クリックする）ことにより、システムまたはアプリケーションはロボットのエンドエフェクタの現在の位置に新しいロードマップ領域を作成し、エンドユーザが新しい起点ポーズを追加できるようにするメニューを提示することになる。「インポート」ユーザ選択可能アイコン３０６ｊを選択する（例えば、クリックする）ことにより、システムまたはアプリケーションはエンドユーザに、インポートのためのファイルを選択するように促すことになる。インポートされたロードマップ領域は変換および回転することができるが、スケーリングすることはできない。「複製」ユーザ選択可能アイコン３０６ｋを選択する（例えば、クリックする）ことにより、選択されたロードマップ領域がクローン化される。

プロジェクトパネル３０６は、ハブセクション３０６ｌを含む。ハブセクション３０６ｌは、プロジェクトで作成されたすべての利用可能なハブを提示する。エンドユーザはエントリを選択し（例えば、クリックし）、インスペクタパネル３０８でハブを選択することができる。アイテム上でのダブル選択（例えば、ダブルクリック）はシステムまたはアプリケーションに、ロボットモデルを、選択されたハブによって識別されるポーズに移動させることができる。新しいハブは例えば、名称フィールド３０６ｍに名前を入力し、ユーザ選択可能なアイン３０６ｎを「追加」することを選択（例えばクリック）することによって追加される。これに応答して、システムまたはアプリケーションは、ロボットモデルのエンドエフェクタの現在位置に新しいハブを作成する。

プロジェクトパネル３０６は、衝突部品セクション３０６ｏを含む。衝突部品セクション３０６ｏは、ロボットモデルに現在取り付けられているすべての部品、すなわち動作環境を提示する。部品の１つを選択する（例えば、クリックする）と、システムまたはアプリケーションは、選択されたアイテムについてインスペクタパネル３０８を提示する。エンドユーザは「追加」ユーザ選択可能なアイコン３０６ｐを選択（例えばクリック）することで新しい部品を取り付けることができ、その選択により、システムまたはアプリケーションがエンドユーザに接続名称を付けるように促し、取り付ける部品ライブラリから部品を選択し、部品にどのリンクに取り付けるかを識別し、その部品を親リンクに接続する方法についてのオフセットを指定することができる。部品ライブラリに部品がない場合は、設定パネルから部品を追加できる。また、部品を取り付けると、システムまたはアプリケーションは、現在のワークスペースの衝突マトリクスを修正することになる。デフォルトでは衝突部品は親リンクに対して衝突検査されないが、ＵＲＤＦ内の他のすべてのリンクに対して衝突検査される。部品がキネマティックチェーン内にないリンクに取り付けられる場合、システムまたはアプリケーションは、依然として、それを衝突として扱う。部品を取り付けることが説明できないポーズを無効にする場合、エンドユーザは、衝突マトリクスが新たに取り付けた部品に対して正しいことを確認するために検査することができる。

プロジェクトパネル３０６はポーズ検証ステータスセクション（例えば、プロジェクトパネルの底部の青いバー）３０６ｑを含む。ポーズ検証ステータスセクション３０６ｑは、完了したポーズ検証のパーセンテージの表示を提供する。システムまたはアプリケーションは、領域またはハブが作成または変更されるたびにポーズ検証を実行する。このシステムまたはアプリケーションはバックグラウンドでこのプロセスを実行し、完了すると、すべてのポーズが有効または無効として識別される。システムまたはアプリケーションは第１の視覚特性（例えば、緑色）を使用して有効なポーズを視覚的に表すことができ、第２の視覚特性（例えば、赤色）を使用して無効なポーズを視覚的に表すことができる。ポーズ生成を必要とするアイテムが検証が既に実行されている間に修正される場合、システムまたはアプリケーションは、検証プロセスを再開する。通常、ポーズ検証は自動的に実行されるが、エンドユーザは大きなモーション計画グラフやロードマップなどに対して設定パネルを使用して、この機能を無効にすることができる。自動ポーズ検証が無効になっている場合は、ユーザが選択可能な「検証」アイコン（緑色のボタンなど）がプログレスバーの下などに表示される。

プロジェクトパネル３０６は、エッジ生成ユーザ選択可能アイコン３０６ｒを含む。グラフやロードマップが設定され、ポーズ検証が完了したら、エンドユーザはユーザ選択可能なアインコン３０６ｒ「エッジを生成する」を選択する（例えばクリックする）ことができる。ユーザ選択可能なアインコン３０６ｒ「エッジを生成する」を選択すると、システムまたはアプリケーションは現在アクティブなワークスペースのすべてのポーズを１つの接続されたロードマップに接続するプロセスを起動する。このプロセスの間、システムまたはアプリケーションは、各ロードマップ領域および補間マトリクスの設定を使用して、どのポーズを互いに接続するかを決定する。次に、システムまたはアプリケーションは、各可能な接続を衝突検査して、接続が有効であるか否かを判定する。このプロセスが完了した後、エンドユーザは、エッジを視覚化することを望むことができる。

プロジェクトパネル３０６には、「接続可視」ユーザ選択可能なアイコン３０６ｓ（例えば、チェックボックス、ラジオボタン）が含まれる。システムまたはアプリケーションは第１の視覚特性（例えば、青）を使用して有効なエッジを提示し、第２の視覚特性（例えば、赤）を使用して無効なエッジを提示する。現在のワークスペースの複雑さに応じて、システムまたはアプリケーションは有効なエッジを決定し、そのようなものをレンダリングするのにいくらかの時間がかかることがある。

エッジが満足できるようになると、現在アクティブなワークスペースに対して占有ファイルが生成できる。占有ファイルは例えばランタイムオペレーション中に、ＭＰＡによって採用されてもよい。プロジェクトパネル３０６は占有生成ユーザ選択可能アイコン３０６ｔ（例えば、チェックボックス、ラジオボタン）を含む。占有生成ユーザ選択可能なアイコン３０６ｔの選択（クリックなど）により、システムまたはアプリケーションは現在アクティブなワークスペース用の占有ファイルを生成する。システムまたはアプリケーションでは、占有ファイルのファイル名を選択するようにエンドユーザに求められる場合がある。名前を入力すると、エンドユーザは「保存」ユーザ選択可能アイコンを選択（例えばクリック）できる。「保存」ユーザ選択可能アイコンを選択すると、システムまたはアプリケーションは生成プロセスを開始する。これは、ロードマップの複雑さに応じて長時間かかる可能性がある。なお、使用中の作業領域ごとにそれぞれの占有ファイルを生成してもよい。

検査パネル（または、インスペクションパネル／Inspectionパネル）
インスペクタパネル３０８は、現在選択されているオブジェクトに関する情報を提示する。インスペクタパネル３０８はコンテキストに依存して（又は、コンテキストセンシティブであって）もよく、表示される情報はどのタイプのオブジェクトが選択されるかに応じて異なる。例えば、インスペクタパネル３０８はモデル化されたロボットのエンドエフェクタの位置および向きを、座標フレーム選択ユーザインターフェース（例えば、プルダウンメニューまたはリスト）３０８ｂを介して選択された実世界座標基準系または他の何らかの座標基準系で提示することができる。インスペクタパネル３０８はまた、システムまたはアプリケーションが衝突解析に基づいて衝突していると判定する任意のリンクのリストを示すことができる。

ビューコントロールパネル（View Controlパネル）
ビュー制御パネル３１０は、どのオブジェクトがプレゼンテーションウィンド３０４に表示されるかを制御するウィジェットを含む。ビュー制御パネル３１０は、エンドユーザがボクセルを表示、または経路をビューイングするときにどのポーズまたはエッジが視覚化されるかを選択することを可能にする。

「ハブ可視（Ｈｕｂｓ Ｖｉｓｉｂｌｅ）」ユーザインターフェース要素（例えば、チェックボックス）３０８ｃにより、エンドユーザは、プレゼンテーションウィンド３０４に表示されるプロジェクトで作成されたハブを有することを、選択することができる（チェックされた場合など）。

「ポーズ可視（Ｐｏｓｅｓ Ｖｉｓｉｂｌｅ）」ユーザインターフェース要素（例えば、チェックボックス）３０８ｄにより、エンドユーザは、プレゼンテーションウィンド３０４に表示されるアクティブなワークスペースに対して生成されたポーズを有することを選択することができる（チェックされた場合など）。

「接続可視（Ｃｏｎｎｅｃｔｉｏｎｓ Ｖｉｓｉｂｌｅ）」ユーザインターフェース要素（例えば、チェックボックス）３０８ｅにより、エンドユーザは、プレゼンテーションウィンド３０４に表示されるアクティブなワークスペースに対して生成されたエッジ接続を有することを選択することができる（チェックされた場合など）。

「経路可視（Ｐａｔｈｓ Ｖｉｓｉｂｌｅ）」ユーザインターフェース要素（例えば、チェックボックス）３０８ｆはエンドユーザが、ディスプレイモードがエッジモードである場合、プレゼンテーションウィンド３０４に表示される現在のインデックスのためにアームが移動する経路を有することを選択する（例えば、チェックされる場合）ことができる。、「経路可視（Ｐａｔｈｓ Ｖｉｓｉｂｌｅ）」ユーザインターフェース要素がチェックされず、ディスプレイモードがエッジモードである場合、ロボットアームは、選択されたエッジに沿って前後に移動する。

「スナップボクセル領域（Ｓｎａｐ Ｖｏｘｅｌ Ｒｅｇｉｏｎ）」ユーザインターフェース要素（例えば、トグル）３０８ｇは、エンドユーザがシステムまたはアプリケーションに、ボクセル領域の位置および寸法を計算させ、更新させることを選択することを可能にし、その結果、得られるボクセル領域は、動作計画グラフまたはロードマップにおいて生成された各エッジ上のロボットのすべての位置を囲む。

「ディスプレイモード（Ｄｉｓｐｌａｙ Ｍｏｄｅ）」ユーザインターフェース要素（例えば、プルダウンメニュー）３０８ｈは、エンドユーザがプレゼンテーションウィンド３０４におけるプレゼンテーションのためのポーズモードとエッジモードとの間で選択することを可能にする。ポーズモードにおいて、「インデックス（Ｉｎｄｅｘ）」フィールドの値の変化は、システムまたはアプリケーションに、示された位置にロボットアームをジャンプさせる。エッジモードにおいて、インデックスフィールドの値の変化は、システムまたはアプリケーションに、ロボットのアームを、選択されたエッジに沿って前後に移動させる、または「経路可視」が選択される場合、システムまたはアプリケーションはエンドエフェクタがそのエッジのためにとる経路のプレゼンテーションを引き起こす。

「インデックス（Ｉｎｄｅｘ）」ユーザインターフェース要素（例えば、フィールド）３０８ｉは、エンドユーザがどのポーズまたはエッジがアクティブであるか、およびそのポーズまたはエッジがどのように表示されるかを選択することを可能にする。ポーズまたはエッジが生成されると、それらは大きなアレイでシステムに記憶される。

「スナップショットビュー（Ｓｎａｐｓｈｏｔ Ｖｉｅｗ）」ユーザインターフェース要素（例えばプルダウンメニュー）３０８ｊにより、エンドユーザは、「ファイル（Ｆｉｌｅ）」メニューからスナップショットがシステムにロードされた場合、どのタイプのデータが表示されるかを選択することができる。

コンソールパネル
コンソールパネル３１２は、システムまたはアプリケーションから出力されたすべてのログを表示する。コンソールパネル３１２は、システムからのメッセージ、警告およびエラーを表示する。

図３Ｄは、例示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースの「衝突部品取り付け」ダイアログボックス３２０を示す。

「衝突部品取付け」ダイアログボックス３２０は取付け名を指定する「取付け名」フィールド３２０ａと、取付け部品を選択するための取付け部品プルダウンリストと、親リンクを選択するための親リンクプルダウンリストとを含む。「衝突部品取付け」ダイアログボックス３２０は、ｘ、ｙ、ｚ軸座標３２０ｂ、３２０ｃ、３２０ｄ、およびｘ、ｙ、ｚ軸３２０ｅ、３２０ｆ、３２０ｇの周りの向きの角度を介して三次元ポーズを入力するためのフィールドも含む。ユーザが選択可能なアイコンにより、エンドユーザは取付けを受け入れるかキャンセルすることができる。

図３Ｅは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのＩＫパネル３２２を示す。ＩＫパネル３２２を使用して、モデル化されているロボットのエンドエフェクタのポーズを指定することができる。

ＩＫパネル３２２は、位置フィールド３２２ａ、３２２ｂ、３２２ｃと、ｘ、ｙ、ｚ軸座標を介して三次元ポーズを表示する回転フィールド３２２ｄ、３２２ｅ、３２２ｆと、ｘ、ｙ、ｚ軸の周りの配向角とを含む。ＩＫパネル３２０は各位置および回転フィールドについて、ユーザが選択可能な位置および回転調整アイコン（例えば、上向き矢印、下向き矢印）３２２ｇ、３２２ｈ、３２２ｉ、３２２ｊのペアを含み、その選択によってポーズが調整される。ＩＫパネル３２０は位置調整アイコンおよび／または回転調整アイコンがそれぞれ選択されたときに位置および回転が調整される増分サイズを設定するために、位置および回転増分フィールド３２２ｋ、３２２ｌを含む。ＩＫパネル３２２は１セットのスナップツーアクシスのユーザ選択可能要素（例えば、トグル）３２２ｍを含み、その選択により、システムまたはアプリケーションは、座標をそれぞれの軸にスナップする。ＩＫパネル３２２は座標が表現される基準系（例えば、実世界）を選択するための基準系プルダウンリスト３２２ｎを含む。

前述したように、検査パネル３０８はコンテキストに依存し（コンテキストセンシティブであって）、どのタイプのアイテムが現在選択されているかに基づいて情報を表示することができる。

図３Ｆは、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのロボットインスペクタパネル３０８－１の形態のインスペクタパネル３０８を示す。

ロボットインスペクタパネル３０８－１は、アクティブなワークスペース内のロボットの状態に関する情報を示す。これらは、どのメッシュモード３０８－１ｂがロボットを描くために使用されているか（衝突または視覚）、およびエンドエフェクタのポーズ、例えば、ｘ、ｙ、ｚ軸３０８－１ｃ、３０８－１ｄ、３０８－１ｅおよびエンドエフェクタのｘ、ｙ、ｚ軸３０８－１ｆ、３０８－１ｇ、３０８－１ｈの周りの向き（座標を見るためのフレームを含む）などのｕｒｄｆからの名前３０８－１ａなどを含む。「基準フレーム選択」プルダウンリスト３０８－１ｉにより、ユーザは基準フレームを選択することができる。それはまた、現在互いに衝突している全てのロボットリンクをリストするテーブル３０８－１ｊを含む。この情報は現在のワークスペースの衝突マトリクスのエラーを迅速に診断し、訂正するのに役立つ。ロボット検査パネル３０８－１は、三次元パネル３０４内のロボット上の任意の可動リンクをクリックすることによって可視にすることができる。

図３Ｇは、図示された一実施形態による、図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースの「ワークスペースインスペクタ」パネル（又は、Workspace Inspectorパネル）３０８－２の形態のインスペクタパネル３０８を示す。

「ワークスペースインスペクタ」パネル３０８－２はプロジェクトパネル上で検査したい作業領域をクリックすることによって見ることができる。インスペクタパネル３０８－２は、現在の状態を特定する「状態」フィールド３０８－２ａと、システムまたはアプリケーションに作業領域の複製又はクローン（duplicate or clone）を行わせる「複製」ユーザ選択可能アイコン（例えばボタン）３０８－２ｂを含む。インスペクタパネル３０８－２はＩＫ解決のために使用されるキネマティックチェーンの開始リンク３０８－２ｃおよび終了リンク３０８－２ｄの表示を含む。インスペクタパネル３０８－２は有効および無効なポーズ３０８－２ｅと有効および無効なエッジ３０８－２ｆの数の表示を含む統計値も含む。インスペクタパネル３０８－２は生成されたジョイント構成、エッジ、ポーズを各々エクスポートする能力を提供する「構成」ユーザ選択可能アイコン３０８－２ｇ、「エッジ」ユーザ選択可能アイコン３０８－２ｈ、および「ポーズ」ユーザ選択可能アイコン３０８－２ｉを含む。

ワークスペースはワークスペースインスペクタパネル３０８内の名前フィールド（例えば、トップフィールド）を編集することによって、名前を変更することができる。ワークスペースは、名前フィールドの横にある「×」をクリックして選択（クリックなど）することで削除できる。

「ボクセル領域インスペクタ」パネル（又は、"voxcel Region Inspector"パネル）（図示せず）は、ボクセル領域の現在の座標（ｘ、ｙ、ｚ）を、その現在の寸法と共に提示する。この「ボクセル領域インスペクタ」パネルはプロジェクトパネル上の「ターゲット」アイコンを選択する（例えば、クリックする）ことによって可視にすることができる。

「ロードマップ領域インスペクタ」パネル（又は、"roadmap region Inspector"パネル）（図示せず）は現在選択されている領域に関する情報を提示し、エンドユーザが、領域内のポーズがどのように生成され、互いに接続されるかを変更することを可能にする。

ロードマップ領域をスケーリングするとき、ポーズ間隔値は、各ポーズ間の間隔を決定する。例えば、ロードマップ領域を大きくすると、所定のポーズ間隔値で指定された間隔で、より多くのポーズが追加されることになる。

「接続密度」値（又は、"Connection density"値）は、システムまたはアプリケーションによって生成されるエッジの数を指定または制御することができる。内部値は、現在選択されている領域内のすべてのポーズの間でいくつのエッジが生成されるかを制御する。外部値は、領域間の接続が補間マトリクスに従って接続されるように設定されると仮定して、現在選択されている領域と他のすべての領域との間でいくつのエッジが生成されるかを制御する。

「内部モーションタイプ値」" Internal Motion type "値は、選択されたロードマップ領域内の各ポーズ間のエッジがＪＯＩＮＴまたはＣＡＲＴＥＳＩＡＮ補間タイプを使用して作成されるかどうかを決定する。

「ハブインスペクタ」パネル（又は、"hub inspector"パネル）（図示せず）はワールドフレーム内のハブの現在位置（ｘ、ｙ、ｚ、ロール、ピッチ、ヨー）を示し、「移動（Ｇｏ Ｔｏ）」ボタンはロボットモデルをそのハブに移動させ、「ポーズ更新」ボタンをクリックすると、ハブの位置およびジョイントの構成は現在のロボットモデルの位置およびジョイントの構成になる。

「衝突部品インスペクタ」パネル（又は、"collision part inspector"パネル）（図示せず）には、衝突部品の名前、現在の親、親からの取り付けオフセット、およびその寸法が表示され、名前フィールドの横の「×」ボタンをクリックすることによって、部品を削除することができる。

また、インスペクタはエンドユーザに、対応するフィールドに新しい数字を入力することによって、領域の位置およびサイズを閲覧および編集させるとともに、「起点位置」を管理させる

図３Ｈは、図示された一実施形態による、図２のプロセッサベースシステムによって提示されるグラフィカルユーザインターフェースの「セット起点ポーズ」ダイアログボックス（又は、"set origin pose"ダイアログボックス）３３０を示す。

起点ポーズは、所与のロードマップ領域内の他のポーズのすべてがどのようにシードされるかを記述するポーズのセットである。「起点ポーズ管理」ユーザ選択可能アイコン（例えば、ボタン）を選択する（例えば、クリックする）と、システムまたはアプリケーションはエンドエフェクタ座標がロックされたままであるモードにロボットモデルをロックするが、回転制御ウィジェットおよび／またはＩＫウィンドを介してその点の周りで回転させることができる。

設定起点ポーズダイアログボックス（又は、"set origin pose"ポーズダイアログボックス）３３０は「領域名」フィールド３３０ａを含み、領域名を入力または表示する。設定起点ポーズダイアログボックス３３０は、「go to」ユーザ選択可能アイコン３３０ｂを含み、その選択によって、システムまたはアプリケーションは選択されたポーズにアイテムを移動させる。次に、「add current pose」ユーザ選択可能アイコン３３０ｃを選択する（例えば、クリックする）ことによって、ロードマップ領域に新しい起点ポーズを追加することができる。ロードマップ領域に追加された各起点ポーズについて、システムまたはアプリケーションは対応する起点ポーズの向きにシードされた領域の密度および間隔パラメータに一致するポーズのセットを作成する。「Poses Visible」が使用可能であり、複数の起点ポーズが追加される場合、向きの違いは容易に明らかになるであろう。設定起点ポーズダイアログボックス３３０は「update」ユーザ選択可能アイコン３３０ｄを含み、その選択はシステムまたはアプリケーションに起点ポーズを更新させる。設定起点ポーズダイアログボックス３３０が「削除」ユーザ選択可能アイコン（又は、"delete"ユーザ選択可能アイコン）３３０ｅを含み、その選択は、システムまたはアプリケーションに起点ポーズを削除させる。

図３Ｉは、図示された一実施形態による、図２のプロセッサベースのシステムによって第３の時点で提示されたグラフィカルユーザインターフェースのプレゼンテーションウィンド３０４を示し、例示的なロボット３４０と、複数の起点ポーズ３４４を有するロードマップ領域３４２とを示す。

図３Ｊは第４の時点での図２のプロセッサベースのシステムによって提示されるグラフィカルユーザインターフェースのプレゼンテーションウィンド３０４であり、例示された一実施形態による、経路可視オプションが選択されたときの、現在のエッジのための例示的なロボット３４０、ワークスペース３４６、および経路３４８を示す。

図４Ａは図１のロボット１０２のための例示的モーション計画グラフ４００であり、これは、１つの例示的実施形態による、対応する移行がロボット１０２と環境１００内の１つ以上の障害物との間の衝突をもたらすであろうと決定された計画グラフ４００のエッジを含む。図４Ｂは１つの例示の実施形態による、対応する移行がロボット１０２と環境１００内の１つ以上の障害物との間の衝突をもたらすことになると決定された計画グラフ４００のエッジが除去された例示的なモーション計画グラフ４００である。計画グラフ４００の各ノードはロボット１０２の状態を表し、計画グラフ４００の各エッジは、ロボット１０２のある状態から別の状態への移行を表す。例えば、エッジ４１０ａは、ノード４０８ａによって表されるロボット１０２の状態とノード４０８ｂによって表されるロボット１０２の状態との間の移行を表す。エッジ４１０ｉは、ノード４０８ｃによって表されるロボット１０２の状態とノード４０８ｄによって表されるロボット１０２の状態との間の移行を表す。

ロボット１０２のための計画グラフ４００の各エッジは、計画グラフ４００において、そのエッジによって表されるある状態から別の状態への移行を行うときに、ロボット１０２によって掃引される３Ｄ空間内のボリュームに対応するいくつかの数のボクセル（またはボックス）を有する。このような情報は、オフチップ計画グラフエッジ情報メモリ２８４に計画グラフエッジ情報として記憶され、システム２００はロボット１０２の寸法の変化に対応するために、異なる計画グラフをスワップアウトすることができる。実行時に現在の環境を表すセンサ２８２から受け取った情報を使用して、システム２００はどのボクセル（またはボックス）が現在占有されているかを判定し、システム２００は、現在占有されているボクセル（またはボックス）と衝突する動きを使用しないと判定する。

いくつかの実施形態では、システムが現在の環境（およびその中の障害物）を表すセンサ２８２から受信され、オンチップ環境メモリ２９４に記憶された情報を、計画グラフエッジ情報メモリ２８４に記憶された計画グラフエッジ情報と実行時に比較することによって、占有ボクセル（またはボックス）と衝突するいかなる動きも使用しないことを決定する。この比較に基づいて、システム２００は、どの計画グラフエッジがロボット１０２と環境１００内の１つまたは複数の障害物との間の衝突をもたらすであろう移行（したがって、どの対応する動き）を表すかを決定する。一例として、図４Ａは、エッジ４１０ｂ、４１０ｃ、４１０ｄ、４１０ｅ、４１０ｆ、４１０ｇ、４１０ｈ、４１０ｉ、４１０ｊ、４１０ｋ、および４１０ｌが、ロボット１０２と環境１００内の１つまたは複数の障害物との間の衝突をもたらす移行（したがって、どの対応する動き）を表すと判定されたことを示す。

例えば、ロボット１０２がノード４０８ａによって表される状態からノード４０８ｄによって表される状態に移動するという目標を達成するために、ロボット１０２は、ロボット１０２と環境１００内の１つまたは複数の障害物との間の衝突をもたらす移行を表すと判定されたエッジ４１０ｂ、４１０ｃ、４１０ｄ、４１０ｅ、４１０ｆ、４１０ｇ、４１０ｈ、４１０ｉ、４１０ｊ、４１０ｋおよび４１０ｌによって表される移行を回避しなければならない。したがって、図４Ｂは、環境１００内の１つまたは複数の障害物と衝突することなく、ノード４０８ａによって表される状態からノード４０８ｄによって表される状態に移動するという目標を達成するためにロボット１０２が従うことができる、システム２００によって識別される計画グラフ４００内の、そのようなエッジが除去された計画グラフおよび潜在的経路４１６を示す。

図５は、例示された一実施形態による、プロセッサベースのシステム２００におけるオペレーション方法５００を示す。プロセッサベースのシステム２００におけるオペレーション方法５００は例えば、システムの呼出しまたは起動または電源投入に応答して、５０２から開始する。

５０４で、プロセッサベースのシステムまたはプロセッサベースのシステムを介して実行されるアプリケーションを介して、ユーザインターフェースが提示される。

５０６で、ロボットモデルが、プロセッサベースのシステムまたはアプリケーションを介して受信または指定される。

５０８において、離散化された動作環境が、プロセッサベースのシステムまたはアプリケーションを介して受信または指定される。

５１０において、離散化された動作環境におけるロボットモデルの表現が、プロセッサベースのシステムまたはアプリケーションを介して提示されるユーザインターフェースを介して提示される。

５１２において、プロセッサベースのシステムまたはアプリケーションは、例えば、ユーザインターフェースを介した入力として、１つ以上のシードポーズを指定する入力を受け取る。シードポーズは手動で入力することも、ファイルまたはファイルへのリンクとして提供することもできる。

任意選択で、５１４において、プロセッサベースのシステムまたはアプリケーションは、自律的に生成されたシードポーズの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約がシードポーズまたはシードポーズ間の移行（例えば、エッジ）によって違反されているかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションは、オブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突がシードポーズからまたはシードポーズ間の移行から生じるかどうかを自律的に決定する。

５１６で、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは１つまたは複数のシードポーズおよび／または任意の関連するエッジを、モーション計画グラフ、ロードマップ、またはラティスに、あるいはモーション計画グラフ、ロードマップ、またはラティスの領域またはサブラティスに追加する。

５１８において、プロセッサベースのシステムまたはアプリケーションは、シードポーズに基づいて、１つ以上の追加ポーズおよび／または関連するエッジを自律的に生成する。例えば、プロセッサベースのシステムまたはアプリケーションは、起点ポーズの領域またはサブラティス内に１つまたは複数の隣接するポーズおよびエッジを自律的に生成することができる。

５２０において、プロセッサベースのシステムまたはアプリケーションは、自律的に生成された追加のポーズおよび／またはエッジの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約が、追加のポーズ、または、シードポーズと追加のポーズ間の移行（例えば、エッジ）、または、追加のポーズ間の移行によって違反されるかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションは、オブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突が、追加ポーズにより、または、シードポーズと追加ポーズ間の移行により、または、追加ポーズ間の移行により生じるかどうかを自律的に決定する。

５２２において、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは１つまたは複数の追加のポーズおよび／または関連するエッジを、モーション計画グラフ、ロードマップまたはラティスに、またはモーション計画グラフ、ロードマップまたはラティスの領域またはサブラティスに追加する。

５２４で、システムまたはアプリケーションは、ユーザインターフェースを介して結果を提示する。

５２６において、ロボットモデルおよび／または動作環境に対する調整を指定するユーザ入力が、プロセッサベースのシステムまたはアプリケーションを介して受信される。

５２８において、システムまたはアプリケーションは、指定された調整に基づいて、運動学的検査および／または衝突検査を自律的に実行する。例えば、システム２００は、モデル化されているロボットの運動学的制約が調整に基づいて違反されているかどうかを自律的に判定する。また、例えば、システム２００は、対応する移行がロボット１０２の少なくとも一部と、環境内の１つ以上の障害物の少なくとも１つの少なくとも一部との間の衝突をもたらす第１の計画グラフのエッジがあればそのいずれかを特定する。システムは第１のノードとして表される第１のポーズと第２のノードによって表される第２のポーズの間の移行において、ロボットまたはその一部によって掃引されるボリュームを決定することができ、この移行は、第１のノードと第２のノードの間のエッジとして表される。

５３０において、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは、モーション計画グラフ、ロードマップまたはラティス、またはモーション計画グラフ、ロードマップまたはラティスの領域またはサブラティスを更新して、調整を表す。

５３２において、システムまたはアプリケーションは、ユーザインターフェースを介して結果を提示する。

モーション計画を容易にするためのプロセッサベースのシステム２００におけるオペレーションの方法５００は５３４で、例えば、再び呼び出されるまで終了する。いくつかの実施形態では、方法５００が継続的に実行されることも、マルチスレッドプロセッサ上のスレッドとして実行されることもできる。

図６は図５に示される方法５００を実行する際に使用され得る、例示の一実施形態による、プロセッサベースのシステムにおけるオペレーションの方法６００を示す。プロセッサベースのシステム２００におけるオペレーションの方法６００は６０２において、例えば、システムの呼び出し又はインヴォケーション（call or invocation）または電源投入に応答して開始する。

いくつかの実装形態では、エンドユーザがモーション計画グラフ、ロードマップ、またはラティスの２つ以上の領域またはサブラティスのそれぞれに、シードポーズまたは起点ポーズをシードすることができる。システムまたはアプリケーションはそれぞれの領域またはサブラティスのための追加のポーズおよび／またはエッジを自律的に生成し、運動力学的および／または衝突検査を実行し、運動力学的および／または衝突検査された追加のポーズおよび／またはエッジをそれぞれの領域またはサブラティスに追加することができる。次いで、システムまたはアプリケーションは自律的に、またはエンドユーザによって誘導されて、領域またはサブラティスを縫い合わせて、完全に接続されたモーション計画グラフ、ロードマップ、またはラティスを形成することができる。例えば、システム又はアプリケーションは、サブラティス接続ポーズ及び／又は関連するサブラティス接続エッジを生成し、運動学的及び／又は衝突検査を実行し、運動学的及び／又は衝突検査されたサブラティス接続ポーズ及び／又は関連するサブラティス接続エッジをモーション計画グラフ、ロードマップ又はラティスに追加することができる。例えば、システムまたはアプリケーションは特定の領域のためのロードマップ又はサブラティスを生成し得る。システムまたはアプリケーションはグラフ内の１つまたは複数の最も近いハブへのエッジを生成し、例えば、第１の領域またはサブラティスからのハブ点を第２の領域またはサブラティスのハブ点に直接接続することができる。次に、システムまたはアプリケーションはハブ同士を接続するエッジを生成し、運動学的および／または衝突検査が、不可能なポーズまたは衝突を検出しない場合、そのエッジを追加することができる。

６０４において、プロセッサベースのシステムまたはアプリケーションは、例えば、ユーザインターフェースを介した入力として、モーション計画グラフ、ロードマップ、またはラティスの第１の領域またはサブラティスのための１つまたは複数のシードポーズを指定する入力を受信する。シードポーズは手動で入力することも、ファイルまたはファイルへのリンクとして提供することもできる。

任意選択で、６０６において、プロセッサベースのシステムまたはアプリケーションは、任意選択で、シードポーズの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約がシードポーズまたはシードポーズ間の移行によって違反されているかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションは、オブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突がシードポーズまたはシードポーズ間の移行から生じるかどうかを自律的に決定する。

６０８で、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは、上記１つまたは複数のシードポーズおよび任意の関連するエッジを、モーション計画グラフ、ロードマップ、またはラティスの第１の領域または第１のサブラティスに追加する。

６１０において、プロセッサベースのシステムまたはアプリケーションは、モーション計画グラフ、ロードマップ、またはラティスの第１の領域または第１のサブラティスのシードポーズに基づいて、１つまたは複数の追加のポーズおよび／または関連するエッジを自律的に生成する。例えば、プロセッサベースのシステムまたはアプリケーションは、シードまたは起点ポーズの第１の領域または第１のサブラティス内に１つまたは複数の隣接ポーズを自律的に生成することができる。

６１２において、プロセッサベースのシステムまたはアプリケーションは、自律的に生成された追加のポーズおよび／またはエッジの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約が追加のポーズ（複数）により又はシードポーズと追加のポーズとの間の移行により又は追加のポーズ（複数）間の移行によって違反されるかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションはオブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突が、追加ポーズ（複数）により又はシードポーズと追加ポーズの間の移行により又は追加ポーズの間の移行によって生じるかどうかを自律的に決定する。

６１４で、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは、１つまたは複数の追加のポーズおよび任意の関連するエッジを、モーション計画グラフ、ロードマップ、またはラティスの第１の領域または第１のサブラティスに追加する。

６１６において、プロセッサベースのシステムまたはアプリケーションは、例えば、ユーザインターフェースを介した入力として、モーション計画グラフ、ロードマップ、またはラティスの第２の領域またはサブラティスのための１つまたは複数のシードポーズを指定する入力を受信する。シードポーズは手動で入力することも、ファイルまたはファイルへのリンクとして提供することもできる。

任意選択で、６１８において、プロセッサベースのシステムまたはアプリケーションは、任意選択で、シードポーズの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約がシードポーズによりまたはシードポーズ間の移行により違反されているかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションはオブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突がシードポーズからまたはシードポーズ間の移行から生じるかどうかを自律的に決定する。

６２０で、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは、１つまたは複数のシードポーズおよび任意の関連するエッジを、モーション計画グラフ、ロードマップ、またはラティスの第２の領域または第２のサブラティスに追加する。

６２２において、プロセッサベースのシステムまたはアプリケーションは、モーション計画グラフ、ロードマップ、またはラティスの第２の領域または第２のサブラティスのシードポーズに基づいて１つまたは複数の追加のポーズおよび／または関連するエッジを自律的に生成する。例えば、プロセッサベースのシステムまたはアプリケーションは、シードまたは起点ポーズの第２の領域または第２のサブラティス内に１つまたは複数の隣接ポーズを自律的に生成することができる。

６２４において、プロセッサベースのシステムまたはアプリケーションは、自律的に生成された追加のポーズおよび／またはエッジの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約が追加のポーズによってまたはシードポーズと追加のポーズの間の移行によってまたは追加のポーズ間の移行によって違反されるかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションは、オブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突が、追加のポーズによりまたはシードポーズと追加のポーズとの間の移行によりまたは追加ポーズ間の移行によって生じるかどうかを自律的に決定する。

６２６で、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは、上記１つまたは複数の追加のポーズおよび任意の関連するエッジを、モーション計画グラフ、ロードマップ、またはラティスの第２の領域または第２のサブラティスに追加する。

６２８において、プロセッサベースのシステムまたはアプリケーションは、第１の領域または第１のサブラティスのポーズを第２の領域または第２のサブラティスのポーズと結合するために、１つまたは複数のサブラティス接続ポーズおよび／または関連するサブラティス接続エッジを自律的に生成し、モーション計画グラフ、ロードマップ、またはラティスの２つまたはそれ以上の領域または２つまたはそれ以上のサブラティスの接続またはスティッチ（又は、縫い合わせ）を行う。例えば、プロセッサベースのシステムまたはアプリケーションは、第１の領域と第２の領域との間、または第１のサブラティスと第２のサブラティスとの間に、１つまたは複数の隣接するポーズを自律的に生成することができる。

６３０において、プロセッサベースのシステムまたはアプリケーションは、自律的に生成されたサブラティス接続ポーズおよび／またはサブラティス接続エッジの運動学的検査および／または衝突検査を自律的に実行する。例えば、プロセッサベースのシステムまたはアプリケーションは、モデル化されているロボットの運動学的制約がサブラティス接続ポーズによりまたはサブラティス接続ポーズ間の移行によりまたはサブラティス接続移行により、およびそれぞれの領域またはそれぞれのサブラティスのポーズまたはエッジにより違反されるかどうかを自律的に判定する。また、例えば、プロセッサベースのシステムまたはアプリケーションは、オブジェクト（例えば、環境内の既知の静的オブジェクト）との衝突が、サブラティス接続ポーズ、または、サブラティス接続ポーズ間のサブラティス接続移行、または、それぞれの領域またはそれぞれのサブラティスの移行およびポーズまたはエッジから生じるかどうかを自律的に判定する。

６３２で、運動学的制約に違反せず、衝突が検出されない場合、プロセッサベースのシステムまたはアプリケーションは、上記１つまたは複数のサブラティス接続ポーズおよび任意の関連するサブラティス接続エッジを、モーション計画グラフ、ロードマップ、またはラティスに追加する。

上記の例は、説明を明確にするために、２つの領域またはサブラティスのみを有する実施形態を提示する。当業者は本明細書の教示から、同じアプローチを３つ以上の領域またはサブラティスに適用するために繰り返すことができることを認識するであろう。

モーション計画を容易にするためのプロセッサベースのシステム２００におけるオペレーションの方法６００は例えば、再び呼び出されるまで、６３４で終了する。一部の実施形態では、方法６００が継続的に実行することも、マルチスレッドプロセッサ上のスレッドとして実行することもできる。

上記の詳細説明においては、ブロック図、概略図及び実施例を用いて、装置及び／又は方法の多様な実施形態について記載した。これらのブロック図、概略図及び実施例は１つまたは複数の機能及び／または動作を含んでいるが、当業者には明らかなように、これらのブロック図、フローチャート及び実施例の範囲におけるそれぞれの機能及び／または動作は個々に及び／または一括して、多様なハードウェア、ソフトウェア、ファームウェア、または事実上任意のこれらの組み合わせによって実装することができる。一実施形態では、本願主題がブール回路、特定用途向け集積回路（ＡＳＩＣ）および／またはＦＰＧＡを介して実装され得る。しかしながら、本明細書に開示された実施形態は全体的にまたは部分的に、標準的な集積回路における様々な異なる実装において、１つまたは複数のコンピュータ上で実行される１つまたは複数のコンピュータプログラムとして（例えば、１つまたは複数のコンピュータシステム上で実行される１つまたは複数のプログラムとして）、１つまたは複数のコントローラ上で実行される１つまたは複数のプログラムとして、１つまたは複数のプロセッサ（例えば、マイクロプロセッサ）上で実行される１つまたは複数のプログラムとして、ファームウェアとして、またはそれらの事実上任意の組合せとして実装することができ、回路を設計すること、および／またはソフトウェアおよび／またはファームウェアのためのコードを書き込むことは、本開示に照らして当業者の技術の範囲内で十分にあることを、当業者は認識するであろう。

当業者は本明細書に記載された方法またはアルゴリズムの多くが、追加のオペレーションを使用し、いくつかのオペレーションを省略し、および／または指定された順序とは異なる順序でオペレーションを実行し得ることを認識するであろう。

さらに、当業者は、本明細書で教示されるメカニズムが様々な形態でプログラム製品として配布されることが可能であり、例示的な実施形態が配布を実際に実行するために使用される信号担持媒体の特定のタイプにかかわらず、等しく適用されることを理解するであろう。信号担持媒体の例にはハードディスクドライブ、ＣＤ ＲＯＭ、およびコンピュータメモリなどの記録可能タイプの媒体が含まれるが、これらに限定されない。

上記の種々の実施形態は組み合わされて更なる実施形態を提供することができる。「１つまたは複数のプロセッサ上に離散化された環境を記憶するロボットのモーションプラニングおよびその改善された動作」と題する２０１８年２月６日に出願された米国特許出願第６２／６２６，９３９号、および「自動運転車のためのモーションプラニングと再構成可能なモーションプラニングプロセッサ」と題する２０１７年６月９日に出願された国際特許出願第ＰＣＴ／ＵＳ２０１７／０３６８８０号、「動的物体を有する環境における自動運転車のモーションプラニングを容易にするための装置、方法及び物品」と題する２０１８年１月１２日に出願された米国特許出願公開第６２／６１６，７８３号、「特殊化されたロボット移動ハードウェア及びその製造及び使用方法」と題する２０１６年１月５日に出願された国際特許出願公開第ＷＯ２０１６／１２２８４０号、および、「モーションプランニンググラフ生成ユーザインターフェース、システム、方法、および物品」と題する２０１９年４月１７日に出願された米国特許出願公開第６２／８３５，１３９号を含むがこれらに限定されない、本願と同一の譲受人に譲渡された、本明細書に言及されかつ／またはアプリケーションデータシートにリストされた米国特許出願公開、米国特許出願、外国特許および外国特許出願の全てが、全体として参照により本明細書に組み込まれる。上記の詳細説明に照らして、上記の及び他の変形がそれらの実施形態に対して行われることが可能である。一般に、以下の特許請求の範囲において、使用される用語は特許請求の範囲を、明細書および特許請求の範囲に開示される特定の実施形態に限定するように解釈されるべきではなく、そのような特許請求の範囲が権利を有する均等物の全範囲とともに、すべての可能な実施形態を含むように解釈されるべきである。したがって、特許請求の範囲は、本開示によって限定されない。
下記は、本願の出願当初に記載の発明である。
＜請求項１＞
ユーザインターフェースを提供するためのプロセッサベースのシステムにおけるオペレーション方法であって、前記方法は、
１つまたは複数の起点ポーズの視覚的指定を可能にする少なくとも１つのユーザインターフェース要素を提供するステップと、
前記プロセッサベースのシステムによって、いくつかの追加ポーズを自律的に生成するステップであって、前記起点ポーズおよび自律的に生成された前記追加ポーズはポーズグループを形成する、該ステップと、
前記プロセッサベースのシステムによって、いくつかのエッジを自律的に生成するステップであって、各エッジは、前記起点ポーズおよび自律的に生成された前記追加ポーズを含む前記ポーズグループの前記ポーズのそれぞれのペアの間の移行を特定する、該ステップと、を有する、方法。
＜請求項２＞
前記プロセッサベースのシステムによる運動学的検査を自律的に実行するステップをさらに有する、請求項１に記載の方法。
＜請求項３＞
運動学的検査を自律的に実行するステップは、ロボットの幾何学的形状に基づいて、前記プロセッサベースのシステムによって自律的に生成された前記追加ポーズの運動学的検査を自律的に実行するステップを含む、請求項２に記載の方法。
＜請求項４＞
前記ポーズのそれぞれの衝突検査を自律的に行うステップをさらに有する、請求項１に記載の方法。
＜請求項５＞
前記ポーズのそれぞれのペア間の各移行の衝突検査を自律的に実行するステップをさらに有する、請求項１に記載の方法。
＜請求項６＞
前記プロセッサベースのシステムによって、ロボットが自己衝突しているか、またはワークスペース内の物体と衝突している場合に、前記ポーズグループから任意のポーズを自律的に排除するステップをさらに有する、請求項１に記載の方法。
＜請求項７＞
前記プロセッサベースのシステムによって、第１のサブラティスと第２のサブラティスの間でポーズを接続するいくつかのサブラティス接続ポーズを自律的に生成するステップをさらに有する、請求項１に記載の方法。
＜請求項８＞
前記プロセッサベースのシステムによって、第１のサブラティスと第２のサブラティスとの間でポーズを接続するいくつかのサブラティス接続エッジを自律的に生成するステップをさらに有する、請求項１に記載の方法。
＜請求項９＞
プロセッサベースのシステムであって、
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサによって実行されるとき、前記少なくとも１つのプロセッサに、
グラフィカルユーザインターフェースを提供させ、
１つまたは複数の起点ポーズの指定を受信させ、
いくつかの追加ポーズを自律的に生成させ、
いくつかのエッジを自律的に生成させる、少なくとも１つのプロセッサ実行可能命令またはデータを格納する少なくとも１つの非一時的プロセッサ読み取り可能媒体を有し、
前記起点ポーズおよび自律的に生成された前記追加ポーズはポーズグループを形成し、
各エッジは前記起点ポーズ及び自律的に生成された前記追加ポーズを含む前記ポーズグループのそれぞれの前記ポーズのペアの間の移行を特定する、
プロセッサベースのシステム。
＜請求項１０＞
前記少なくとも１つのプロセッサによって実行されたとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、
運動学的検査を自律的に実行させる、請求項９に記載のプロセッサベースのシステム。
＜請求項１１＞
運動学的検査を自律的に実行するために、前記少なくとも１つのプロセッサは、
ロボットの幾何学的形状に基づいて自律的に生成された前記追加ポーズの運動学的検査を自律的に実行する、請求項１０に記載のプロセッサベースのシステム。
＜請求項１２＞
前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能な命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
各前記ポーズのそれぞれの衝突検査を自律的に行なわせる、請求項９に記載のプロセッサベースのシステム、
＜請求項１３＞
前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能な命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
前記ポーズのそれぞれのペア間の各移行の衝突検査を自律的に実行させる、請求項９に記載のプロセッサベースのシステム。
＜請求項１４＞
前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
ロボットが自己衝突しているか、またはワークスペース内の物体と衝突している場合に、前記ポーズグループから任意のポーズを自律的に排除する、請求項９に記載のプロセッサベースのシステム。
＜請求項１５＞
前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
第１のサブラティスと第２のサブラティスとの間でポーズを接続するいくつかのサブラティス接続ポーズを自律的に生成させる、請求項９に記載のプロセッサベースのシステム。
＜請求項１６＞
前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
第１のサブラティスと第２のサブラティスとの間でポーズを接続するいくつかのサブラティス接続エッジを自律的に生成させる、請求項９に記載のプロセッサベースのシステム。
＜請求項１７＞
ユーザインターフェースを提供するためのプロセッサベースのシステムにおけるオペレーションの方法であって、実質的に本明細書に開示及び説明された、方法。
＜請求項１８＞
少なくとも１つのプロセッサと、
前記少なくとも１つのプロセッサによって実行されるときに、前記少なくとも１つのプロセッサに、本明細書に実質的に開示及び説明されたユーザインターフェースを提供させるプロセッサ実行可能な命令またはデータの少なくとも１つを格納する少なくとも１つの非一時的プロセッサ可読媒体
を備えるプロセッサベースのシステム。

Claims (22)

1. ユーザインターフェースを提供するためのプロセッサベースのシステムにおけるオペレーション方法であって、前記方法は、
   １つまたは複数の起点ポーズの視覚的指定を可能にする少なくとも１つのユーザインターフェース要素を提供するステップと、
   前記プロセッサベースのシステムによって、いくつかの追加ポーズを自律的に生成するステップであって、前記起点ポーズおよび自律的に生成された前記追加ポーズはポーズグループを形成する、該ステップと、
   前記プロセッサベースのシステムによって、いくつかのエッジを自律的に生成するステップであって、各エッジは、前記起点ポーズおよび前記自律的に生成された前記追加ポーズを含む前記ポーズグループの前記ポーズのそれぞれのペアの間の移行を特定する、該ステップと、を有し、
   前記プロセッサベースのシステムによって、前記自律的に生成された前記追加ポーズのいずれかが運動学的制約に違反するかどうかを決定するために、前記自律的に生成された前記追加ポーズの運動学的検査を自律的に実行するステップと、
   前記プロセッサベースのシステムによって、前記ポーズの前記それぞれのペアのそれぞれの間の各移行の衝突検査を自律的に実行するステップと、
   前記プロセッサベースのシステムによって、前記衝突検査を成功裏に通過し、前記運動学的検査を成功裏に通過した自律的に生成された前記エッジ及び前記自律的に生成された前記追加ポーズのそれぞれについての前記自律的に生成された前記エッジに対応するエッジ及び前記自律的に生成された前記追加ポーズに対応するノードをモーション計画ラティスに追加するステップを含み、
   前記モーション計画ラティスは複数のノードと複数のエッジとを含み、前記ノードはそれぞれの状態を表し、前記エッジは前記モーション計画ラティス内の前記エッジのそれぞれの１つによって結合された前記ノードのそれぞれのペアによって表される前記状態のペアの間の有効な移行をそれぞれ表す、方法。
2. 前記プロセッサベースのシステムによる視覚的に示された１つまたは複数の前記起点ポーズの運動学的検査を自律的に実行するステップをさらに有する、請求項１に記載の方法。
3. 自律的に生成された前記追加ポーズの運動学的検査を自律的に実行するステップは、ロボットの幾何学的形状に基づいて、前記プロセッサベースのシステムによって自律的に生成された前記追加ポーズの運動学的検査を自律的に実行するステップを含む、請求項２に記載の方法。
4. 前記ポーズのそれぞれの間の移行の衝突検査を自律的に行うステップをさらに有する、請求項１に記載の方法。
5. 前記ポーズのそれぞれのペア間の各移行の衝突検査を自律的に実行するステップは、
   前記起点ポーズと前記自律的に生成された前記追加ポーズとを含む前記ポーズグループ内の前記ポーズのそれぞれのペアの間のそれぞれの移行の衝突検査を自律的に実行するステップをさらに有する、請求項１に記載の方法。
6. 前記プロセッサベースのシステムによって、ロボットが自己衝突しているか、またはワークスペース内の物体と衝突している場合に、前記ポーズグループから任意のポーズを自律的に排除するステップをさらに有する、請求項１に記載の方法。
7. 前記プロセッサベースのシステムによって、第１のサブラティス内のポーズと第２のサブラティス内のポーズの間でポーズを接続するいくつかのサブラティス接続ポーズを自律的に生成するステップをさらに有する、請求項１に記載の方法。
8. 前記プロセッサベースのシステムによって、第１のサブラティス内のポーズと第２のサブラティス内のポーズとの間でポーズを接続するいくつかのサブラティス接続エッジを自律的に生成するステップをさらに有する、請求項１に記載の方法。
9. 有効なポーズを無効なポーズから視覚的に区別する視覚的提示を提供するステップをさらに含む、請求項１に記載の方法。
10. プレゼンテーションウィンド内のロボットの視覚的表現における選択されたアイテムの並進または回転の少なくとも１つがドラッグ入力を介して指定されることを可能にする少なくとも１つのユーザインターフェース要素を提示するステップをさらに含む、請求項１に記載の方法。
11. プレゼンテーションウィンド内のロボットの視覚的表現における選択された関節の並進または回転のうちの少なくとも１つがドラッグ入力を介して指定されることを可能にする少なくとも１つのユーザインターフェース要素を提示するステップをさらに含む、請求項１に記載の方法。
12. プロセッサベースのシステムであって、
    少なくとも１つのプロセッサと、
    前記少なくとも１つのプロセッサによって実行されるとき、前記少なくとも１つのプロセッサに、
    グラフィカルユーザインターフェースを提供させ、
    １つまたは複数の起点ポーズの指定を受信させ、
    いくつかの追加ポーズを自律的に生成させ、
    いくつかのエッジを自律的に生成させ、
    前記プロセッサベースのシステムによって、前記自律的に生成された前記追加ポーズのいずれかが運動学的制約に違反するかどうかを決定するために、前記自律的に生成された前記追加ポーズの運動学的検査を自律的に実行させ、
    前記プロセッサベースのシステムによって、前記ポーズの前記それぞれのペアのそれぞれの間の各移行の衝突検査を自律的に実行させ、
    前記衝突検査を成功裏に通過し、前記運動学的検査を成功裏に通過した自律的に生成された前記エッジ及び前記自律的に生成された前記追加ポーズのそれぞれについての前記自律的に生成された前記エッジに対応するエッジ及び前記自律的に生成された前記追加ポーズに対応するノードをモーション計画ラティスに追加させる、少なくとも１つのプロセッサ実行可能命令またはデータを格納する少なくとも１つの非一時的プロセッサ読み取り可能媒体を有し、
    前記起点ポーズおよび自律的に生成された前記追加ポーズはポーズグループを形成し、
    各エッジは前記起点ポーズ及び前記自律的に生成された前記追加ポーズを含む前記ポーズグループのそれぞれの前記ポーズのペアの間の移行を特定し、
    前記モーション計画ラティスは複数のノードと複数のエッジとを含み、前記ノードはそれぞれの状態を表し、前記エッジは前記モーション計画ラティス内の前記エッジのそれぞれの１つによって結合された前記ノードのそれぞれのペアによって表される前記状態のペアの間の有効な移行をそれぞれ表す、
    プロセッサベースのシステム。
13. 前記少なくとも１つのプロセッサによって実行されたとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、
    視覚的に示された１つまたは複数の前記起点ポーズの運動学的検査を自律的に実行させる、請求項１２に記載のプロセッサベースのシステム。
14. 自律的に生成された前記追加ポーズの運動学的検査を自律的に実行するために、前記少なくとも１つのプロセッサは、
    ロボットの幾何学的形状に基づいて自律的に生成された前記追加ポーズの運動学的検査を自律的に実行する、請求項１３に記載のプロセッサベースのシステム。
15. 前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能な命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    各前記ポーズのそれぞれの間の移行の衝突検査を自律的に行なわせる、請求項１２に記載のプロセッサベースのシステム、
16. 前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能な命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    前記ポーズのそれぞれのペア間の各移行の衝突検査を自律的に実行させるために、プロセッサ実行可能な命令またはデータのうちの前記少なくとも１つは、前記起点ポーズと前記自律的に生成された追加ポーズとを含む前記ポーズグループ内の前記ポーズのペアのそれぞれの間のそれぞれの移行の衝突検査を自律的に実行させる、
    請求項９に記載のプロセッサベースのシステム。
17. 前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    ロボットが自己衝突しているか、またはワークスペース内の物体と衝突している場合に、前記ポーズグループから任意のポーズを自律的に排除する、請求項１２に記載のプロセッサベースのシステム。
18. 前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    第１のサブラティス内のポーズと第２のサブラティス内のポーズとの間でポーズを接続するいくつかのサブラティス接続ポーズを自律的に生成させる、請求項１２に記載のプロセッサベースのシステム。
19. 前記少なくとも１つのプロセッサによって実行されるとき、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    第１のサブラティス内のポーズと第２のサブラティス内のポーズとの間でポーズを接続するいくつかのサブラティス接続エッジを自律的に生成させる、請求項１２に記載のプロセッサベースのシステム。
20. 前記少なくとも１つのプロセッサによって実行されるときに、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    有効なポーズと無効なポーズの視覚的に区別する視覚的提示を提供させる、請求項１２に記載のプロセッサベースのシステム。
21. 前記少なくとも１つのプロセッサによって実行されるときに、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    プレゼンテーションウィンド内のロボットの視覚的表現における選択されたアイテムの並進または回転の少なくとも１つがドラッグ入力を介して指定されることを可能にする少なくとも１つのユーザインターフェース要素を提示させる、請求項１２に記載のプロセッサベースのシステム。
22. 前記少なくとも１つのプロセッサによって実行されるときに、プロセッサ実行可能命令またはデータのうちの前記少なくとも１つは、前記少なくとも１つのプロセッサに、さらに、
    プレゼンテーションウィンド内のロボットの視覚的表現における選択された関節の並進または回転のうちの少なくとも１つがドラッグ入力を介して指定されることを可能にする少なくとも１つのユーザインターフェース要素を提示させる、請求項１２に記載のプロセッサベースのシステム。

Images