JPH06259410A

JPH06259410A - 経路選択方法及び装置

Info

Publication number: JPH06259410A
Application number: JP462694A
Authority: JP
Inventors: Karen Trovato; アイトルヴァートカレン
Original assignee: Koninklijke Philips Electronics NV; Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1993-01-22
Filing date: 1994-01-20
Publication date: 1994-09-16
Also published as: DE69425595D1; DE69425595T2; EP0609928A3; EP0609928A2; EP0609928B1

Abstract

(57)【要約】【目的】別個のスタート位置と集結（ランデブー）位
置との間で少なくとも二つのアクターがとる経路、また
これらアクターのうちの少なくとも一方が集結位置から
最終ゴールに至る経路を効率よく最適化する。【構成】少なくとも１個の集結状態への経路を選択す
る方法において、集結条件への移動のための第１シナリ
オを定義し、第１シナリオとは異なる集結条件への移動
のための第２シナリオを定義し、少なくとも１個のタス
ク状態が共通するそれぞれの形態空間を前記シナリオに
基づいて形成し、各形態空間に対応するソースからコス
トウェーブを伝播させて共通タスク状態に対応する各形
態状態のコストを決定し、全域的規準を定義するブール
演算式を決定し、共通タスク状態の各々に対し、ブール
演算式に従って対応の形態状態を評価して集結候補状態
を識別し、集結候補状態の識別情報を選択手段に出力す
ることよりなる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、二つの互いに独立した
空間変数の制約又はシナリオに従って少なくとも二次元
での移動が可能な一つ又はそれ以上のアクター（マシン
又は人間）の運行プランニング（計画）方法に関するも
のである。特に、本発明は、例えば、集結（ランデブ
ー:rendezvous)が、一つのアクターと他のアクターとの
間に、又は時間又は空間にわたる移動する条件を必要と
する時間又は空間に関する運行プランニングに適用する
ことができる。

【０００２】

【従来の技術】軌跡又は経路プランニングの最も共通す
る用途としてはロボットを制御することであった。典型
的なロボット軌跡プランにおいては、障害物を避けなが
らロボット（又はロボットの一部例えば、ロボットの把
持部材）をスタートポイントからゴールポイントに到達
させる経路を選択するものであった。特に、多次元状況
ではコンピュータによるシミュレーション／制御が性能
を改善させた。

【０００３】

【発明が解決しようとする課題】本発明の更に他の用途
として、交通若しくは緊急車両の制御、又は動的状況に
おける人間若しくはマシンのとりうるルート若しくは活
動のプランニング又は予報がある。

【０００４】従来の技術としては、特に、空間変数メト
リック(space-variant metric)を使用してバッディング
(budding) によって形態空間(configuration space) に
コストウェーブを伝播させることを開示している。簡単
な軌跡プランニングの問題において、形態空間は、二次
元の離散化した物理的条件を表す。代表的な直交座標系
を使用することにより、各形態状態は、既知の値を有す
る種々のパラメータによって記述されるタスク状態又は
物理的条件を表す。特定の順序で配列されたタプル(tup
le) として知られているこれら値のリストが各形態状態
を表す。このとき、形態空間はタプルのスパンである。

【０００５】ゴールの位置(locations) 又は状態(state
s)は一連の解析のために定義され限定される。スタート
位置の選択はプランニング方法の一つのステップであ
る。

【０００６】１個の形態状態から他の形態状態への移行
のコスト（コストメトリック(costmetric) として知ら
れているが、ここでは単にメトリックと称する）は、形
態空間における隣接部(neighbors) の各々に対する各形
態状態のために定義される。アクター（例えば、マシ
ン）が特定の形態状態にあることは不可能又は極めて好
ましくない場合、この形態状態は障害物と見なされる。
この状態への移動は、極めて高い又は無制限の移行コス
トに関連付けされる。これに隣接する領域は、このとき
移行コストが定義されないか又は有限の値即ち、許容さ
れる状態変化を有する状態のみを含むものとして定義さ
れる。

【０００７】バッディング(budding) は、通常所定の形
態空間における一つ又はそれ以上のゴールであるソース
(source)からスタートし、ゴールから展開する計算のウ
ェーブにおいて各状態に対して方向矢印(direction arr
ow) 及びコスト−トゥ−ゴールメトリック(cost-to-goa
l metric) を発生するのに使用される。この展開プロセ
スを図形的に見ることにより「コストウェーブ伝播(cos
t wave propagation)」という用語が生じているもので
ある。各形態空間に対して発生した方向矢印は、ゴール
に向かう最低コストの経路を逆向きに指し示す。制御ロ
ボットにおいて、このことは、ロボットが最適経路から
逸脱した場合に、状態識別(identification of state)
を行って即座に既知の新たな最良経路方向をとることが
できる点で有利である。

【０００８】米国特許第4,949,277 号に記載のバッディ
ングプロセスの特別な改良では、例えば、障害物又はゴ
ールが追加されたり、その形態空間から僅かな距離移動
したり、又は除去されたときに、形態空間の小さな部分
のみをディファレンシャルバッディッグ(differential
budding)を行うことがある。

【０００９】米国特許第5,083,256 号には、状態自体の
変化よりも形態空間における移行変化を考慮するディフ
ァレンシャルバッディングの変更例が記載されている。

【００１０】本発明の目的は、計画した集結が全域的制
約条件を満足するものとして、より大きい空間内で複数
個の集結領域(rendezvous regions)を識別(identify)す
ることにある。

【００１１】本発明の他の目的は、異なるソースからの
コストウェーブ伝播を一層効率的に利用する方法を得る
にある。

【００１２】更に、本発明の他の目的は、別個のスター
ト位置とランデブー位置との間で少なくとも二つのアク
ターがとる経路（軌跡）、またこれらアクターのうちの
少なくとも一方が集結位置から最終ゴールに至る経路
（軌跡）を最適化することにある。

【００１３】更に、本発明の他の目的は、アクターマシ
ンがスタート位置から集結位置を経て更に最終ゴール位
置に至る最適化した経路をたどるようアクターマシンを
制御するにある。

【００１４】少なくとも二つのアクターのためのすべて
の全域的制約条件(global constraint) を満足する集結
領域を表示する装置を得るにある。

【００１５】更に、本発明の他の目的は、環境が変化し
たとき効率的に更新して、アクターマシンがスタート位
置から集結位置を経て最終ゴール位置に達する最適経路
をたどるようアクターマシンを制御する装置を得るにあ
る。

【００１６】

【課題を解決するための手段】この目的を達成するた
め、本発明方法及び装置は、それぞれのアクターに適用
できるシナリオの各々に対して形態空間(configuration
space) を形成し、この形態空間内で障害物及びゴール
を定義する。次に各形態空間においてコストウェーブを
伝播させ、形態状態(configuration states)の各々のコ
ストを記憶する。それぞれのアクターに有効なタスク状
態(task state)の各々に対して個別のブール演算評価(B
oolean evaluation)を行い、集結のための全域的制約条
件(globalcriterion)を満足する集結候補状態を識別す
る。このブール演算(The Boolean)は、この識別を行う
ための基礎となる。

【００１７】本発明装置における第１の好適な実施例に
おいては、ブール演算の結果に基づいて、アクターがス
タート位置から集結位置への移動を最適化する制御信号
を発生する。

【００１８】本発明装置の他の好適な実施例において
は、集結領域を図形的に又はセットポイントリストとし
て視覚的表示を行う。

【００１９】種々の有利な特徴を従属請求項に記載す
る。

【００２０】

【実施例】次に、図面につき本発明の好適な実施例を説
明する。

【００２１】複数個のマシン(multiple machines) は、
一般的に、より大きい目標(largergoal) を達成するた
めに協調させるべきである。代表的には、このことは、
相互に容認できる位置:location(又は状態:state) での
出会い(meeting) がある。特定のマシンのための容認で
きる領域は、全域的制約条件(global constraints)とし
て記述される。相互に容認できる位置は集結位置(rende
zvous location) と称される。多くの場合、これらのう
ちの一つのみが実際のインプリメンテーション（実施）
のために選択される。

【００２２】図１において、集結領域を見出すための最
も一般的の方法を示す。オーバル100 はこの方法のスタ
ートを示す。

【００２３】ボックス101 において、アクター(actor)
のシナリオを特定する。特定した各シナリオに対しては
形態空間(configuration space) が創出される。代表的
には、この形態空間はすべてのアクターの活動の共通領
域を示す。例えば、４個の異なる種類のトラック（truc
ks：それぞれ固有の運動学及びコストを有する）が、無
人の(desert)の同一範囲(expanse) に沿って走っている
とする。代表的には、各シナリオには、アクターに関連
するシナリオの名前と、プランニングのソース方向(sou
rce direction)即ちスタート又はゴールと、ソース位置
(source location) を特定する一組の状態（状態セッ
ト：a set of states ）、及びサーチ（検索）を管理す
るのに使用するメトリック(metric)がある。操縦を実施
している間には、一つのスタートのみがあり、プランを
評価する場合には１個以上の代替スタートがある。

【００２４】ボックス102 においては、障害物を形態空
間に変換する。

【００２５】ボックス103 においては、コストウェーブ
をボックス101 で特定された各シナリオに対して伝播さ
せる。ソース方向は、ゴールと任意のスタート状態(sta
rting state)との間に単独の経路（パス：path）を即座
に見出される点で、「スタート」及び「ゴール」に対す
る過去の参照(references)とは異なる。この状況で、ソ
ース方向が「ゴール」である場合にウェーブをゴールか
ら外方に伝播させる。ソース方向が「スタート」を通過
する場合に、ウェーブはスタート状態(start state) か
ら伝播し、コストは「コスト- フロム- スタート（ｃｏ
ｓｔｆｒｏｍｓｔａｒｔ）」として測定される。この
ことは、スタート状態のためのコスト- フロム- スター
トがゼロであり、メトリック関数(metric function) を
逆転することを呼び出し（例えば、dist(a,b) の代わり
にdist(b,a) を呼び出す）、矢印はスタートから離れる
方向ではなくスタートに向かう方向を指し示す。コスト
ウェーブ伝播のためのメカニズムはこれらの相違点は別
として同一である。

【００２６】ボックス104 においては、各形態状態(con
figuration state) における全域的規準(global criter
ion)を評価する。

【００２７】ボックス105 においては、全域的規準を満
足する集結状態(rendezvous states) を出力する。全域
的規準は、満足する解を得ることができる全ての行路を
包括(encompass) するブール演算論理式である。

【００２８】例えば、２個の燃量トラックのうちの少な
くとも一方と飛行機とが集結し、飛行機（シナリオＡで
測定した燃量コストメトリック(fuel cost metric)を有
する）がそのタンクに依然として少なくとも１００ガロ
ンの燃量があり、第１燃量トラック（シナリオＦ１で測
定した距離コストメトリック(distance cost metric)を
有する）が５０マイル以下の距離を走行しなければなら
ず、一方第２燃量トラック（シナリオＦ２で測定したタ
イムコストメトリック(time cost metric)を有する）が
２ｐｍと４ｐｍとの間でのみ出会うことができる場合に
は、これら全ての制約を満足する位置は全域的規準を有
する。特に、この場合の全域的規準は以下の通りとな
る。即ち、 G=(A>100)and((F1<50)or((F2>1400)and(F2<1600))) である。

【００２９】全域的規準の結果はセットポイントのプリ
ントした集合(printed collection)であることが多い
が、代案として、マップ上のハイライトした領域(highl
ightedregion)とすることもできる。解を表示するのに
多くの有用な方法をとることができる。

【００３０】ボックス106 においては特定集結状態(a s
pecific rendezvous state) を選択規準(selection cri
terion) に基づいて選択する。この選択規準は、ある種
の集合コスト(collection cost) を最適化するか、又は
シナリオの最も重要なものの最小コストを選択すること
が多い。例えば、２０個の可能な集結位置(rendezvous
locations)がある場合、所定のアクターの燃量消費を最
小にする集結位置が最も望ましい。代案として、全ての
集結状態(rendezvous states) が等価（等しい）である
とみなせる場合、ランダムな選択を行うことができる。
更に他の選択方法としては、人間の指示による選択があ
る。

【００３１】ボックス107 においては、シナリオを表現
する形態空間のセットから選択した情報を読み出す。

【００３２】特定の集結状態を選択した場合、その集結
状態に至るスタート及びゴールの状態から導き出される
経路（パス）を形態空間から読み出すことができる。特
定アクターのための経路は、先ずアクターのスタートを
含むシナリオに関連した形態空間を選択し、集結状態か
らスタートまでの逆の経路をトレースすることによって
見出す。順次の移行は、代表的な実施の仕方と比べて逆
の順序でリストされるため、経路を逆転すべきであ
る。。特定アクターの特定の集結ポイントから経路の残
りの部分は、このアクターのためのゴールを含むシナリ
オに関連した形態空間を選択し、集結状態からゴールに
至る経路をトレースすることによって見つける。順次の
移行は、代表的に行われる順序でリストされるため、経
路を逆転する必要はない。

【００３３】経路に関連するコストが必要な場合、特定
集結状態でコストを読み出すことができる。例えば、ス
タートから集結状態までのコストを、そのアクターのた
めのゴールを含むシナリオに関連する形態空間で読み出
すことができる。集結状態からゴールまでのコストは、
そのアクターのためのゴールを含むシナリオに関連する
形態空間で読み出す。

【００３４】図１のステップを示す実施例を図２〜図６
につき説明する。以下の〔表１〕〜〔表４〕のテーブル
(Tables)１〜４は、図１のボックス101 に必要とされる
シナリオの明細である。以下の実施例のための図１のボ
ックス102 のステップに必要な障害物レイアウトが、各
シナリオに対して同一であると仮定する。他のシナリオ
では、各シナリオのための障害物レイアウトは、たとえ
地形が同一であったとしても異なる。例えば、川が自動
車にとって障害物であり、土手に沿って走行し、橋を渡
らなければならない場合があり、また船にとっては同一
の地形は土手及び低い橋が障害物となる。

【００３５】以下の〔表１〕のテーブル(Table)1はマシ
ンＡ及びシナリオ１の簡略化した明細である。このシナ
リオにおいて、２個のスタート状態があり、〔表１〕の
メトリック(metric)として最小距離規準(minimum dista
nce criterion)を選択する。但し、ユーザーが設けたル
ックアップテーブル及び複雑な公式を含む他のメトリッ
クスを選択することもできる。

【００３６】

【表１】

【００３７】図２には、表１のテーブル(Table)1のシナ
リオを有する形態空間にコストウェーブ伝播を使用して
発生した経路の簡略化した例を示す。これは、図１のボ
ックス103 の方法に対応する。障害物は、303 における
３個の状態(states)であり、304 における１個の状態で
ある。コスト- フロム- スタート（ｃｏｓｔｆｒｏｍ
ｓｔａｒｔ）は各状態で与えられている。方向矢印(d
irection arrows)は等価スタート状態(equivalent star
ting states)301,302 を指し示す。

【００３８】以下の表２のテーブル(Table)2は、マシン
Ａ、シナリオ２の簡略化した明細である。このシナリオ
において、２個のゴール状態(goal states) が与えられ
ており、メトリックとして最小距離規準(minimum dista
nce criterion)が選択されている。

【００３９】

【表２】

【００４０】図３は、表２のテーブル(Table)2のシナリ
オを有する形態空間にコストウェーブ伝播を使用して発
生した経路の簡略化した例を示す。これは図１のボック
ス103 の方法に対応する。障害物は503 における３個の
状態であり、504 における１個の状態である。方向矢印
は等価ゴール状態501,502 を指し示す。

【００４１】以下の表３のテーブル(Table)3はマシン
Ｂ、シナリオ１の簡略化した仕様を示す。このシナリオ
において、２個のスタート状態が与えられており、表３
のメトリックとして最小時間規準(minimum time criter
ion)が選択される。

【００４２】

【表３】

【００４３】図４は表３のテーブル(Table)3のシナリオ
を有する形態空間にコストウェーブ伝播を使用して発生
した経路の簡略化した例を示す。これは図１のボックス
103の方法に対応する。障害物は703 における３個の状
態であり、704 における１個の状態である。方向矢印は
等価スタート状態701,702 を指し示す。

【００４４】以下の〔表４〕のテーブル(Table)4はマシ
ンＢ、シナリオ２の簡略化した明細である。このシナリ
オにおいて２個のゴール状態が与えられ、表４のメトリ
ックとして最小燃量規準(minimum fuel criterion)が選
択される。

【００４５】

【表４】

【００４６】図５は、表４のテーブル４のシナリオを有
する形態空間にコストウェーブ伝播を使用して発生した
経路の簡略化した例を示す。これは、図１のボックス10
3 の方法に対応する。障害物は903 における３個の状態
であり、904 における１個の状態である。方向矢印は等
価ゴール状態901,902 を指し示す。

【００４７】この簡単な例の全域的制約条件(global co
nstraint) は、以下のブール演算式によって定義され
る。即ち、 (a1>2)&(a1<=8)&((a1+a2)=7)&(b1<4)&(b2>4)&((a2+b2)<
9)&((a2+b2)>6) である。

【００４８】この制約条件は図１のボックス104 で与え
られる方法を実施するのに使用する。この簡単な例にお
いては、全域的制約条件は、実際的には、集結解(rende
zvous solution) が以下の規準（制限）を満足しなけれ
ばならないことを意味する。 1)スタートから集結状態まで移動する距離Ａは(2,8) の
間でなければならない。かつ(AND) 2)合計の移動距離Ａは精密に７でなければならない。かつ(AND) 3)スタートから集結状態まで移動する時間ｂは４以下で
なければならない。かつ(AND) 4)集結状態からゴールまでｂが消費する燃量は少なくと
も４でなければならない。かつ(AND) 5)（ａが移動する距離＋ｂが消費する燃量）の合計は９
より小さくなければならない。かつ(AND) 6)（ａが移動する距離＋ｂが消費する燃量）の合計は６
よりも大きくなければならない。

【００４９】いかなるブール演算の組み合わせも容認で
き、OR,XOR演算子を使用した標準論理演算式に限定され
ることなく、比較判定（即ち、>,=,又は<)のためのオペ
ランド(operands)としてのいかなる数学的演算式も含む
ことができる。

【００５０】各状態において、全域的制約条件を評価す
る。必ずしも必要ではないが、計算的費用及び失敗の恐
れが最小の副次式(sub-expressions) を制約条件に入れ
ることは一層効率的である。これは、式の最終結果を決
定してからすべての副次式を評価することができる場合
に、カレントコンパイラ(current compilers) が「短絡
評価(short circuit evaluation)」を行い、このとき残
余部分は判定しないからである。

【００５１】全域的制約条件がTRUEとなる場合、状態は
集結状態である。

【００５２】図６において、全域的制約条件1101、1102
を満足する状態をクロスハッチでハイライトして示す。
代案として、座標を出力することができる。このこと
は、図１のボックス105 で特定した方法に対応する。

【００５３】任意の選択した個別の集結状態に対して、
それぞれのスタートからそれぞれのゴールに追従する各
アクターの経路は、それぞれの形態空間における集結状
態から追跡(tracing) することによって検索することが
できる。

【００５４】例えば、選択した集結状態が座標(4,8) を
有する図６の1102である場合には、アクターＡは図２に
おける座標(3,2) のスタート状態302 から座標(3,3),
(3,4),(3,5),(3,6),(3,7),(3,8) に、また最終的に(4,
8) に至る。繰り返し説明すると、このことは、図２に
おける座標(4,8) における集結状態305 から最も近いス
タートに戻るよう追跡し、この経路を逆にたどることに
よって達成することができる。経路を知ることの他に、
スタートから集結状態に移動するコストが７であること
を知得する。アクターＡが図６の集結状態1102からゴー
ルに達する経路を見出すのは、図５における座標(4,8)
から最も近いゴールに達する経路をトレースすることに
よって得られる。この場合、アクターはすでにゴール50
2 に存在し、移動は必要でない。ゴールに達するコスト
はゼロである。

【００５５】同様に、アクターＢの経路及びコストを見
出すことができる。

【００５６】各集結状態に対するすべてのアクターのす
べての経路及びコストは、決まり通りの表示を行うこと
ができ、又はいくつかのもののみ選択することができ
る。

【００５７】許容されるバリエーション(Permissible V
ariations)： a)マシン（アクター）間の共通タスク空間(Common Task
Spaces)のマッピングをすること。図１のボックス101 において、種々のアクターの形態空
間は異なる形状及び寸法とすることができるが、共通領
域を識別できるマッピングでなければならない。例え
ば、１個のアクターはニューヨーク、ニュージャージ
ー、及びコネチカット内での移動を計画し、第２のアク
ターがニューヨーク、ニュージャージー、デラウェア、
及びメリーランド内での移動を計画するものとする。こ
の場合、ニューヨーク又はニュージャージーでの集結(r
endezvous)を生ずることが容易にわかる。このタイプの
問題を処理するには、共通領域(common area) のマッピ
ングのための方法を用意しなければならない。非共通領
域(non-common area) は、計画即ちプランニング（即
ち、図１の方法101,102 及び103 ）にとって依然として
必要とされるが、全域的規準(global criterion)を満足
する状態を見出すには１個の共通領域のみを評価すべき
である（図１のボックス104 の方法）。

【００５８】他の共通する問題としては、同一の物理的
領域（「タスク空間(task space)」と称するものがある
が、それぞれの形態空間(configuration space) は全く
異なる場合がある（即ち、１個のマシンは２度の自由度
があり、他のマシンは３度の自由度がある）。全域的規
準は、例えば、マシン間のドッキング距離を特定する。
更に、必ずしも必要ではないが、集結を生ずる可能性が
ある領域を絞ることができる。予期される集結領域(ren
dezvous region) はフルタスク空間(full taskspace)
のサブセットとすることができる。この予期される集結
領域を各マシンの対応の形態空間に変換しなければなら
ない。この能力は既に存在している。即ち、これは障害
物変換を行うに必要な方法と同一であるためである。タ
スク空間における各変換した状態に対して、全域的規準
を評価する。

【００５９】b)アクターの固定の組み合わせを識別する
ときの効率改善互いに出会うことを必要とする全域的規準を有する２個
のアクターのみが存在するとき、任意のシナリオに対し
て障害物がいずれかのアクターの状態にあるすべての集
結候補状態を排除するとより効率的である。他方、アク
ターＡがアクターＢ又はアクターＣに出会う場合、規準
を評価する前にすべてのシナリオにおいて障害物がない
ことを必要とするストラトジー(strategy)は、アクター
Ｂと集結しかつアクターＣと集結しない（またその逆）
という集結状態を見落とす場合がある。前もって必要と
される障害物がないシナリオパターンを識別することに
よって、必要な全域的規準の評価の数を一層減少するこ
とができる。

【００６０】c)演算の並列性(Parallelism) 及び次数(O
rder) における効率(Efficiency) 図１のボックス101,102,103 は各シナリオに対して並列
処理することができる。即ち、各シナリオに含まれる情
報はそれぞれ独立しているためである。更に、ボックス
101,102 に含まれる演算は逆算又は並列的に行うことが
できる。

【００６１】d)ディファレンシャルバッディング(Diffe
rencial Budding) 何らかの環境変化がある場合にディファレンシャルバッ
ディングを使用して形態空間を更新することができる。

【００６２】e)同一マシンに対する多重制約条件(Multi
ple Constraints) 数個のマシンを使用する簡単な例であっても、異なるタ
イプの制約条件を有する単独マシンのための解を計算す
ることができる。例えば、一定の目的地に移動する自動
車が１／４の燃量レベルになる前に停止し、少なくとも
一時間後に移動又はトリップを継続することがある。上
述の方法は、これらの要求を統合する。給油のための停
止位置は、集結領域(rendezvous region) 内で見出すこ
とができる。

【００６３】f)人間の集結(Rendezvous of People) マシンの集結位置を計算するのに多くの例があるが、人
間の集結位置（位置、時間等を含む）を計算することも
できる。各人間は地形に基づいて移動するのに異なる能
力を有し、また固有の肉体的能力（ランニングスピー
ド、ジャンプ距離等）を有する。見出した集結状態に基
づいて人間はその人の個性に従う固有の経路を進む傾向
がある。

【００６４】g)非物理的集結状態(Non-physical rendez
vous states) 多くの例は成就するランデブーに共通でなければならな
い物理的会合位置(physical meeting location) を記述
する。しかし、集結は異なる同時条件を有することもあ
る。例えば、電話の会話は、時間が同一であることを必
要とする。電話分布がまばらであると仮定すると、計画
（プラン）は可能な電話位置に対する情報を組み込まな
ければならない。この例では、全域的制約条件を表現す
るブール論理演算式において、その状態に電話があるこ
とを識別する各形態状態(configuration state) におけ
る変数を使用することができる。

【００６５】 h)早期停止規準(Early Stopping Criterion) 各シナリオに対してウェーブ伝播(wave propagation)を
とらなければならない形態空間がある。先の特許出願に
おけるウェーブ伝播は、スタート状態をウェーブが通過
するとき停止することができた。即ち、これ以上の計算
は意味がないためである。できるだけ早期にウェーブ伝
播を停止することによって時間を節約することができ
る。同様に、全域的規準の計算結果が常にFALSE となる
集結のウェーブ伝播における所定ポイントの後に、継続
するウェーブ伝播も無意味であることがわかった場合、
停止することができる。例えば、全域的規準が必要とさ
れる副次式（ＡｃｔｏｒＡｃｏｓｔ＜５０）を含むと
仮定する。この例では、コストウェーブ伝播はヒープの
トップにおける値（コストウェーブの端縁で生ずること
もある）が５０に達したとき停止することができる。一
般的に、１個のアクターシナリオのみに関与する副次式
(subexpressions)を使用してコストウェーブ伝播を早期
に停止することができる。

【００６６】 i)相対集結状態(Relative Rendezvous states) 上述のシナリオにおいて、タスク空間はリファレンスの
固定フレームから測定する。高速車両を制御する関連の
出願と同様に、リファレンスフレームはアクターに対し
て相対移動する。ドッキングする移動車両の問題はこの
ようにしてアドレスされる。容認できる集結状態を見出
す方法は、リファレンスの移動フレームに基づいて共有
タスク空間を決定するという変更を行って上述のように
行うことができる。このようにして見出した集結候補状
態(candidate rendezvous states) はリファレンス移動
フレームに対して相対的である。

【００６７】装置のバリエーション(Apparatus Variations) 上述の方法は、多くの異なる装置形態に使用することが
できる。図７に示すように、必要なものは、入力装置、
プロセッシングユニット、及び出力装置である。入力装
置10としては、キーボード、マップ上の位置を示すマウ
ス又はライトペン、発声言語認識装置(spoken-word rec
ognition system)、アクター及び／又は障害物の位置を
示すレーダー出力装置、又はコンピュータシステムとす
ることができる。中央処理装置12は、専用計算及び論理
ユニット、「ワークステーション」又はマイクロプロセ
ッサ、又はよりパワフルな計算機とすることができる。
メモリ14はオプショナルとし、３−Ｄマップデータ又は
チャートデータ、アクター（人間又はマシン）能力及び
限界のための記憶装置を有する構成とすることができ
る。出力のためには、視覚的スクリーンディスプレイ16
によりプランニングの決定に使用する人間用の情報を発
生し、コントローラ18を介して運動を制御するロボット
がとる最適な計画ルートを示すようにする。代案とし
て、集結位置のリストをプリントし、その後に使用する
データをコンピュータに与えるようにする。

【図面の簡単な説明】

【図１】本発明による方法の基本ステップを示すフロー
チャートである。

【図２】テーブル１のシナリオを使用する第１アクター
のための形態空間に発生する経路（パス）を示すダイヤ
グラム（図表）である。

【図３】テーブル２のシナリオを使用する第１アクター
のための形態空間に発生する経路を示すダイヤグラムで
ある。

【図４】テーブル３のシナリオを使用する第２アクター
のための形態空間に発生する経路を示すダイヤグラムで
ある。

【図５】テーブル４のシナリオを使用する第２アクター
のための形態空間に発生する経路を示すダイヤグラムで
ある。

【図６】図２〜図５の形態空間における全域的制約条件
を評価することによって見出した集結状態のダイヤグラ
ムである。

【図７】本発明を実施する装置のブロック線図である。

【符号の説明】

10 入力装置 12 中央処理装置 14 メモリ 16 視覚的スクリーンディスプレイ 18 コントローラ

Claims

【特許請求の範囲】

【請求項１】少なくとも１個の集結状態に達する経路を
選択する方法において、集結条件を達成する移動のための第１シナリオを定義す
るステップと、前記第１シナリオとは異なる前記集結条件を達成する移
動のための第２シナリオを定義するステップと、少なくとも１個のタスク状態が共通するそれぞれの形態
空間を前記シナリオに基づいて形成するステップと、各形態空間に対応するソースからコストウェーブを伝播
させて前記共通タスク状態に対応する各形態状態のコス
トを決定するステップと、全域的規準を定義するブール演算式を決定するステップ
と、前記共通タスク状態の各々に対し、前記ブール演算式に
従って前記対応の形態状態を評価して集結候補状態を識
別するステップと、前記集結候補状態の識別情報を選択手段に与える情報出
力ステップとよりなることを特徴とする経路選択方法。
【請求項２】前記形態空間のうちの１個に対応するソー
スをスタート状態とし、前記形態空間のうちの他の形態
空間に対応するソースをゴール状態とした請求項１記載
の経路選択方法。
【請求項３】前記第１シナリオを第１アクターに対して
定義し、前記第２シナリオを異なる他のアクターに対し
て定義し、また前記集結条件を、同一タスク状態におい
て前記第１アクターと前記他のアクターとが同時に存在
する条件とした請求項１又は２記載の経路選択方法。
【請求項４】前記情報出力ステップは、位置を画像で表
示し、前記集結候補状態を識別可能表示によって識別す
るものとした請求項３記載の経路選択方法。
【請求項５】前記集結条件からゴールに至る移動の第３
シナリオを定義するステップを有する請求項３又は４記
載の経路選択方法において、前記形態空間のうちの１個
に対応するソースを前記第１アクターのスタート状態と
し、前記形態空間のうちの他の形態空間に対応するソー
スを前記ゴールとした請求項３又は４記載の経路選択方
法。
【請求項６】少なくとも１個の集結状態に達する経路を
選択する装置において、集結条件を達成する移動のための第１シナリオと及びこ
の第１シナリオとは異なる第２シナリオを定義する手段
と、少なくとも１個のタスク状態が共通するそれぞれの形態
空間を前記シナリオに基づいて形成する手段と、各形態空間に対応するソースからコストウェーブを伝播
させて前記共通タスク状態に対応する各形態状態のコス
トを決定する計算手段と、全域的規準を定義するブール演算式を決定する式決定手
段と、前記共通タスク状態の各々に対し、前記ブール演算式に
従って前記対応の形態状態を評価して集結候補状態を識
別する評価計算手段と、前記集結候補状態の識別情報を選択手段に与える情報出
力手段とを備えたことを特徴とする経路選択装置。
【請求項７】前記形態空間のうちの１個に対応するソー
スをスタート状態とし、前記形態空間のうちの他の形態
空間に対応するソースをゴール状態とした請求項６記載
の経路選択装置。
【請求項８】前記第１シナリオを第１アクターに対して
定義し、前記第２シナリオを異なる他のアクターに対し
て定義し、また前記集結条件を、同一の形態状態におい
て前記第１アクターと前記他のアクターとが同時に存在
する条件とした請求項６又は７記載の経路選択装置。
【請求項９】前記出力手段は、位置を画像で表示し、前
記集結候補状態を識別可能表示によって識別する表示手
段を有する構成とした請求項６乃至８のうちのいずれか
一項に記載の経路選択装置。
【請求項１０】前記集結条件からゴールに至る移動の第
３シナリオを定義する手段を有する請求項８記載の経路
選択装置において、前記形態空間のうちの１個に対応す
るソースを前記第１アクターのスタート状態とし、前記
形態空間のうちの他の形態空間に対応するソースを前記
ゴールとした経路選択装置。