(57)【要約】【課題】動的システムのためのリアルタイムアプリケーションを確率計算時間アルゴリズムを使用して開発及び使用する方法を提供する。【解決手段】検知サブシステム、作動サブシステム、制御サブシステム、及びアプリケーションサブシステムを備えた動的システムのためのリアルタイムアプリケーションを開発し使用する方法は、確率計算時間アルゴリズムを使用する。最適化関数、所望の状態、及び制約が受け取られセンササブシステムから検出装置データが提供された後、統計最適化誤差記述を生成する。この統計最適化誤差記述から、最適化誤差を含んだ戦略を制御サブシステム内で開発する。次に、制御サブシステム内の実行モジュールが、作動サブシステム内の各種作動装置に実行戦略を送信する。【選択図】図１
2004199692.tif 000002
【特許請求の範囲】
【請求項１】
検知サブシステム、作動サブシステム、制御サブシステム、及びアプリケーションサブシステムで構成される動的システムを制御するために確率計算時間アルゴリズムを使用してリアルタイムアプリケーションを開発し使用する方法であって、
初期検出装置データ、最適化関数、所望の状態、及び制約を受け取るステップと、
統計最適化誤差記述を生成するステップと、
最適化誤差を含むストラテジーを開発するステップと、
リアルタイムアプリケーションで前記ストラテジーを実行するステップと
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の確率計算時間アルゴリズムを使用してリアルタイムアプリケーションを開発し使用する方法であって、前記統計記述を生成するステップは、
固定時間割当てで前記検出装置データを最適化するステップと、
無制限時間割当てで前記検出装置データを最適化するステップと、
誤差の確率分布を決定するステップと
を含むことを特徴とする方法。
【請求項３】
請求項１に記載の確率計算時間アルゴリズムを使用してリアルタイムアプリケーションを開発し使用する方法であって、ストラテジーを生成するステップは、
解の誤差の確率分布から誤差の最大範囲を決定するステップと、
制御誤差の範囲をモデルの不確定性の範囲として使用するステップと、
状態誤差の範囲を観測値不確定性の範囲として使用するステップと、
誤差範囲から安定性及び安定性限界値を決定するステップと
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は主にコンピュータによる問題解決の分野に関し、特に、確率計算時間アルゴリズムを使用して各種リアルタイムアプリケーションを開発するシステム及び方法に関する。
【背景技術】
【０００２】
計画、スケジューリング、制御、監視、及び診断アプリケーション等の一部の組込みシステムアプリケーションでは、それぞれが制御、監視、及び障害診断機能を持つネットワーク接続された複数のセンサ及び作動装置で構成された複雑なシステムについて、時間的制約が厳しい状態でも正しい決定を下すことができるシステムの要求が高まっている。ハードウェアテクノロジが進歩してプロセッサの価格が下がり低価格のマイクロ電気機械システム（ＭＥＭＳ）作動装置やセンサが実現し、また、通信コストが低減した結果、今まで以上に再構成化、柔軟性に優れた強力なシステムが可能になった。しかし、ネットワーク接続されたアプリケーションでは、分散化された制約条件付き最適化方法と複雑さ分析及び学習技法とを組み合わせた意志決定システムテクノロジが要求されている。
【０００３】
このようなアプリケーションの意志決定システムとハードウェアの開発とは、歩調が合っていなかった。従来、意志決定システムは、単一の作業向けに作成された特殊目的コンピュータプログラムを使用していた。最近の各種システムの場合、意志決定システムはモデルベースコンピュータプログラムを利用していて、このプログラムが単一のハイエンドプロセッサで実行される汎用制約解法技法（制約問題の解を見つける）を使用している。例えば、単純な制約問題とは「印刷システムの用紙が所望の時間（目的）に次の位置合せステーションに到着し、その時の速度がローラの速度制限（制約）を超えないようにローラ速度（所望の解）を決定する」と言うものである。分散型組込みソフトウェアの例としては制御ソフトウェアがあり、例えば、マシンの機能を制御し、単一のパソコンまたはワークステーションではなくマシン内の複数のネットワーク接続プロセッサで実行されるソフトウェア等である。マシン制御等の組込みアプリケーションは、通常、厳しいリアルタイム制約の下で解決しなければならない複雑な制約問題を扱うのに対し、組込みプロセッサには、通常、メモリが制限された低速中央処理装置等、重大な資源上の制限がある。
【０００４】
制約条件付き最適化は、多くの組込みアプリケーションの最も重要な部分である。計画、スケジューリング、制御、及び診断等のアプリケーションでは、操作計画、制御入力、障害仮説、及び回復処置等のタイムリーで正確な解を生成することが必要である。これらのアプリケーションにおける共通の作業は、特定の目的に関する解、つまり、システムの制約下で実現可能な解、またはシステムの制約と矛盾しない解を繰り返し求めることである。現在、このようなアプリケーションは、通常、決まったシステム構成及びシステムタスクの広範囲な分析に基づき、手作業でコーディングされるプログラムである。しかし、将来のネットワーク接続組込みシステムで動的再構成及びフォルトトレラント動作を可能にするためには、商用及び軍用アプリケーションでしばしば要求されるように、ソフトウェアリアルタイム操作の一部として統合操作を実行しなければならない。本明細書に記載する発明は軍用アプリケーションに限定されてはいないが、以下の説明は例として軍事関係について述べている。
【０００５】
例えば、軍事ハードウェアは、テクノロジ面で古くなってもそのまま使用できることがある。この問題に対処するために、新しいハードウェアへ投資するより、既存システムを新しい作業向けにアップグレードしたり再構成したりする方が望ましい。例えば、無人の水中輸送機関は、兵器配置、偵察任務、掃海作業、救助操作等の多目的水中プラットフォームになる可能性を秘めている。しかし、このような船舶を新しいタイプのサブシステム（兵器、センサ、掃海または救助機器）でアップグレードまたは再構成することは難しい。それは、機器のタイプ、役割、及び元の構成に強く依存する相互作用をソフトウェアが調整したり制御したりしなければならないからである。例えば、機雷を検出し捕捉する作業では、センサ、ロボットアーム、及び推進力の制約を考慮しなければならず、その結果発生する制約問題は複雑になる可能性がある。例えば、ロボットコントローラが繰り返し解決する制約問題には、モジュール構造のマニピュレータに関する数百の非線形の範囲、トルク、及び衝突制約が関係し、エネルギーを節約しモータ音を最小にしながら目標に到達する等の、複数の目的がある。現在、このような問題は、組込みプロセッサで実行される既存の技法ではリアルタイムに解決することはできない。
【０００６】
２番目の例は、多数の分散型組込みサブシステム間の調整である。例えば、Ｆｌａｎｋ  Ａｒｒａｙｓ等のソナーが使用する水中聴音器の数はますます増え（ミサイル発射機クラスの潜水艦では３０，０００の大台）、複雑な平行アーキテクチャを必要とする。膨大な数のデータ配列、集中作業負荷、及びデータフローを動的にマッピングし最適再構成化を図る作業は、高度な計算集約問題であることが知られている。解は、処理装置、メモリー編成とサイズ、通信帯域幅、及びデータ／計算の局地性等の空間制約と、応答時間及び遅延等の時間制約を満足する必要がある。
【０００７】
最後の例は、複数の輸送機関の分散化されフォルトトレラントな連携動作である。オンボード解決サービスを使用しなければならないアプリケーションには、任務立案から最適輸送機関制御まで、多くのアプリケーションがある。例えば、前線の戦闘地域の後方で長期特定任務を自律的に実行する１組の航空機編隊につい検討してみよう。各編隊のリーダは編隊の戦略（長期）指揮を実行して協同操作及び調整操作に係わる制約を満足させる一方、すべての航空機は短期の自主制御を実行する。現在、計画立案、スケジューリング、及び調整等の作業は、主に、任務を遂行する前に実行される。これらの作業は、任務の目的、特定のナヴィゲーションポイント、敵及び戦略上の環境制約、及びデータ相関要件に従った場所／時間の軌跡の生成で構成される。この場合もモデルベースの技法を使用して環境の変化及び任務の更新に動的且つ敏感に対処してこれらの作業を解決することで、編隊の有効性及び柔軟性は動的に向上する。そのためには、輸送機関に分散されたソルバが各種目的（任務の目標、交戦の規則、検出回避、航空機間の対話等）に適合する機能を持ち、個別の航空機が機能低下や戦闘不能に陥った場合でも自力で再構成できる能力を持つことが要求される。
【０００８】
ネットワーク接続された組込みシステムで実行されるアプリケーションは、オフラインでは予想もできない複雑な制約問題の解決を制約ソルバに要求する。しかも、制約ソルバの実行環境は本来分散型計算環境で、資源制約も厳しい。しかし、複雑なシステムでは、制約ソルバはリアルタイムパフォーマンスを保証せず、また、メモリーが制限された下で実行できるとは限らない。したがって、制約解決システムの多様性や能力向上の要望は強いが、制約条件付き最適化計算時間には本質的に確率的要素があるため、制限付きアルゴリズムのパフォーマンスは低い。このような確率計算時間アルゴリズムは、通常、制御等のリアルタイムアプリケーションには考慮されていない。したがって、制御等のリアルタイムアプリケーションでは、確率計算時間アルゴリズムを制約条件付き最適化ソルバへ適用するアプローチに関する要求が高まっている。
【０００９】
【特許文献１】米国特許出願公開第５，８７０，７３１号明細書
【特許文献２】米国特許出願公開第６，０８８，６９０号明細書
【特許文献３】米国特許出願公開第６，１４４，９５３号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の目的は、動的システムのためのリアルタイムアプリケーションを確率計算時間アルゴリズムを使用して開発及び使用する方法を提供することである。
【課題を解決するための手段】
【００１１】
簡単に説明すると、本発明の一側面によれば、検知サブシステム、作動サブシステム、制御サブシステム、及びアプリケーションサブシステムで構成される動的システムのためのリアルタイムアプリケーションを確率計算時間アルゴリズムを使用して開発及び使用する方法を開示している。最適化機能、所望の状態、及び制約条件を受信し検出装置のデータがセンササブシステムから提供された後、統計最適化誤差記述を生成する。この統計最適化誤差記述から、最適化誤差も含めたストラテジー（strategy：広義には、目的達成のための方法、手順、指令であり、狭義には戦略である）を制御サブシステム内で開発する。次に、制御サブシステム内の実行モジュールが、作動サブシステム内の各種作動装置に実行ストラテジーを送信する。
【発明を実施するための最良の形態】
【００１２】
本明細書では、確率計算時間アルゴリズムよる動的システム制御を開発及び使用するシステムと方法、特に、実行時にオフライン及び／またはオンラインで開発されたアルゴリズムパフォーマンスの統計記述による制約解法アプローチを開発及び使用するシステムと方法を開示する。このアルゴリズムは各種入力を使用して実行され、出力の確率分布は一定の計算時間について決まる。複雑さ分析、フェーズ遷移記述、または他の問題分類等の各種方法を使用し、結果として得られ且つアルゴリズムパフォーマンスを特徴付ける確率分布をパラメータ化することができる。確率制御方法を一般化してアルゴリズムの統計パフォーマンスを組み込むようにしたため、複雑なシステムの制御に使用できるアルゴリズム分野は拡張され、実際の複雑なモデルも組み込むことができるようになった。以下に述べる開示では制御アプリケーションについてこのシステムと方法を記述するが、当業者は、本明細書で開示している方法及びシステムは他のリアルタイムアプリケーションにおけるサービスとしても適用可能であることが理解できる。
【００１３】
従来技術では、装置が不確定である理由を明らかにして強力なコントローラを設計したり、モデル不確定性を表現したり、決定論的不確定性をモデル化したりするなどの試みがいくつかなされている。これらのさまざまなアプローチでは、装置、測定、及び外部障害における不確定性をモデル化し、強力な制御方法を使用してこれらの不確定性を明らかにしている。これらすべての場合、特定の状態観察値Ｙについて、システム状態Ｘ*＝ｆ（Ｙ）の推定を行い、推定された状態Ｘ*から、制御アクションＵ＝ｇ（Ｙ，Ｘ*）を計算するものとする。ここで、ｆ（．）及びｇ（．，．）は制限付きアルゴリズムである。つまり、特定の入力について、システムのループタイム内で出力を計算できる。しかし、制約条件付き最適化を使用してＸ*及びＵを計算すると、Ｘ*及びＵの計算は固定でなくなり、Ｙの変化に合わせて大幅に変化する可能性がある。Ｙの一部の値について、Ｘ*及び／またはＹの計算時間は他に比べ極端に長くなる可能性がある。また等価的に、問題を制約条件付き最適化問題として公式化する場合、解の品質は非常に悪くなる可能性がある。計算に関するこの確率的性質は、従来技術では明示的に含まれてなくまた考慮されていない。
【００１４】
確率計算時間アルゴリズムを基にリアルタイムアプリケーションを実現するシステムを図１に示す。この図では、例示システム１３０は、再構成モジュール１３２、診断モジュール１３４、制御モジュール１３６、または計画及びスケジューリングモジュール（図示せず）及び他のモジュールを備えている。制御サブシステム１４０は、動的システムの状態を推定するシステム状態モジュール１５０、システム状態及び所望の状態を基に制御信号を生成する状態アクションモジュール１６０、及びシステム状態を所望の状態に近づけるのに必要なアクションを生成する実行モジュール１７０とを備えている。検知サブシステム１１０は、各種の検出装置１２０を備えている。これらは、温度、速度、ピッチ、偏揺角、時間等の各種数量を検知することができる。検出装置１２０からの出力は、ネットワーク接続１２５を介して制御サブシステム１４０へ提供される。システム状態モジュール１５０は、付随する検出装置のノイズを考慮に入れ、検出装置１２０から受信する情報に基づいてシステムの状態の統計記述を生成し更新する。その結果得られる計算されたシステム状態には、計算により展開されたアルゴリズムノイズの要素が含まれる。次に、ソルバが誤差の確率分布を決定し、これが、状態アクションモジュール１６０により使用されパフォーマンス戦略を生成する。このパフォーマンス戦略は実行モジュール１７０に渡され、このモジュールがネットワーク接続１８５を介して実行命令を作動サブシステム１８０に送信する。このサブシステムには、各種作動モジュール１９０が含まれている。
【００１５】
図２では、フローチャートが、制御、診断、または再構成等の各種リアルタイムアプリケーションに確率計算時間アルゴリズムを使用する方法を示している。本明細書で開示している方法及びシステムは便宜上及び説明を簡単にするために制御システムを中心に説明しているが、該方法及びシステムは複数のアプリケーションにも適用可能で、これらすべては本明細書の開示及び請求項の対象になっている。方法２００では、２１０で最初の検出器データを受け取り蓄積する。アルゴリズムの統計記述またはモデル２２０を、オフラインかまたは操作中に生成する。次にこの統計記述を使用して制御戦略２３０を生成するが、この戦略は受け入れ可能な制御を生成するためにアルゴリズムの確率計算時間を考慮したものである。オンライン計算の場合、統計モデル２２０を更新すると、対応する制御戦略２３０も変更され、アルゴリズムの動作に関する新しい知識を反映させる。次に、制御戦略２３０を２４０で実行し、その結果が戻されて統計記述２２０を更新する。
【００１６】
図３から５は、統計記述を生成または更新する各種実施例を示している。図３では、検出器データ３１０を決められた時間割り当て３２０で最適化し、誤差３３０の確率分布を決定する。検出器データ３１０には
Ｙ＝Ｙ´＋ΔＹ
になるように観測値Ｙ´の集合と検出器ノイズ構成要素ΔＹの両方が含まれている。
【００１７】
時間、温度、速度、ピッチ、偏揺角、または検知された他の数量を含むことができる検出器データＹの集合から、推定システム状態Ｘ*を決定するために、Ｘ*が次の条件を満たすように最適化問題を記述できる。
【数１】
2004199692.tif 000003
【００１８】
Ｙだけがわかっていてもシステムの状態Ｘは固有に定義できないため、最適化関数ｈを使用し、この関数により各解に値を与える必要がある。最小２乗法及び最小最大誤差法は、制約を満足する各種解を評価するために一般的に使用する最適化関数の２つの例である。新しい観測値及び直前の観測値を使用してこの計算を各時間ステップで繰り返し実行することで、システムの現在状態の最適推定値を得ることができる。制御のための戦略を生成するために、システム記述の生成及び更新により決まるシステムの状態は、システムの推定状態と計算の結果得られるノイズ構成要素の両方で構成される。この場合、Ｘ*が次のように表されるようにする。
Ｘ*＝Ｘ＋ΔＸ
ここで、ΔＸはアルゴリズムノイズ構成要素を表している。このように、アルゴリズムノイズは、実行可能な制御アクションを決定する場合に実際のノイズと同様に扱われる。制御アクションを決定するために、Ｕとして定義された制御法則は以下の最小解である。
【数２】
2004199692.tif 000004
ここで、ｈ2（Ｕ，Ｘ*）は最も望ましいパフォーマンスを取得する目標関数で、Ｘdはシステムの所望の状態である。ｈ1（Ｘ）またはｈ2（Ｕ，Ｘ*）のいずれかが定値関数の場合、最適化問題は最適化というよりむしろ一種の充足可能性の追求になる。これは、制約を満たすすべての解が、目標関数により等しく重み付けされるからである。または、制約はペナルティ関数または最も一般的にはラグランジュの乗数を使用して、目標関数の一部として組み込むこともできる。Ｘ、Ｙ、及びＵはハイブリッド連続／離散スペース上で連続でも、離散でも、定義済みでもよい。
【００１９】
最適化問題は、本技術分野で利用可能な様々な方法で解決できる。例えば、問題が連続変数で定義されている場合、解決方法にはニュートンの方法、擬似ニュートンの方法、内部ポイント、シンプレックス、Ｎｅｌｄｅｒ−Ｍｅａｄ等がある。離散問題に関する最適化方法には、縦型探索、横型探索、及び分枝限定探索、およびＯｕｔｅｒ  ａｐｐｒｏｘｉｍａｔｉｏｎｓがある。制約は、ラグランジュの乗数またはペナルティ関数により組み込まれる。
【００２０】
本明細書に記載されている目的を達成するために、任意に選択し、且つ、操作時に現れると考えられる状態、最悪状態、または操作時に取得した状態を表すように選択したＹ値の集合について、最適化問題の解を求める。固定の計算または時間割当てについて最適化問題の解を求め、計算終了時に最善解の目標関数値及びラグランジュ値の分布が得る。さらに、Ｙ値の集合について制約条件付き最適化問題の解を求めたり、解決時間の分布を決定したりできる。したがって、操作の前及び／または操作時に、目標関数値及び解決時間の分布を入力値の集合について入手できる。割り当てられた時間割当て内にソルバが解を得られない場合は、戻される最善解Ｘ´及びＵ´は、所望の解Ｘ*、Ｕ*から次の式で与えられるΔＸ及びΔＵだけ誤差がある。
Ｘ´＝Ｘ*＋ΔＸ
Ｕ´＝Ｕ*＋ΔＵ
【００２１】
図４では、無制限の時間割当て４２０で検出器データ４１０を最適化し、誤差４３０の確率分布を求めている。図３により上記で説明したアプローチも本実施例で使用しているが、時間割当てを無制限として推定作業を行っている。図５では、固定時間割当て５２０及び無制限時間割当て５３０で検出装置データ５１０を最適化し、誤差の確率分布５４０を求めている。この場合も、図３により説明したアプローチを使用する。ただし、制限時間割当て及び無制限時間割当ての両方を使用して推定作業を行う。
【００２２】
誤差ΔＸ及びΔＵの確率分布を使用し、様々な方法で動的システムの制御アクションを生成できる。その１つを図６に示す実施例で示している。この図では、最大誤差範囲６１０を解の誤差６０５の確率分布から導き出している。ΔＸmax及びΔＵmaxで与えられる誤差｜ΔＸ｜及び｜ΔＵ｜に最大範囲６１０が存在する場合、これらの範囲はモデルの不確定性６２０の範囲として使用できる。ΔＵmaxはモデル不確定性６２０と等価で、ΔＸmaxは観測不確定性６３０と等価である。これらの誤差範囲について、安定性及び安定性限界値６４０を決定し、制御戦略を公式化できる。安定性及び安定性限界値は説明を簡単にするために使用されているだけであって、他の制御手段を決定することもできる。この戦略はシステムに渡され、実行される。
【００２３】
図７では、代替実施例が誤差確率分布７０５を受信し、誤差の統計分布全体を７１０で拒絶される測定ノイズまたは障害として使用する。誤差分布は正規、指数、Ｃａｕｃｈｙ分布等のパラメータファミリーに合わせて調整できるか、または、分布のモーメントを取得できる。調整済み分布またはモーメントを使用し、予期されるパフォーマンスが所望の目標を達成することを確認できる。考えられる解には、線形２次調整装置（ＬＱＲ）最適化及び正規分布ノイズに関する確率的Ｒｉｃｃａｔｉ方程式が含まれる。特異値分割及びｍｕ合成は、制御を生成するためのノイズの統計的特徴抽出法として使用される別の方法である。発生すると思われる問題は、誤差分布のテール部分が非常に長いので、アルゴリズムノイズに関係するノイズ信号は２乗可積可能でないことであり、このことは、当該手順に必要な周波数応答またはラプラス変換が見つからないことを示している。本実施例では、このようなノイズを拒絶する障害として扱う。結果として得られた制御戦略は、システムに渡され実行される。
【００２４】
図８では、別の実施例が誤差確率分布８０５を受け取り、モンテカルロ法８１０を使用してシステムの動作をシミュレートする。システムをシミュレートでき、アルゴリズム分布からの標本を使用してシステム動作をシミュレートできる。システムが許容可能状態で動作する確率を決定できる。望ましくない行動の確率が特定の値以下になるように、８２０における最適制御を調整できる。この最適制御戦略はシステムに渡され、実行される。
【００２５】
本発明を具体的な実施例により図示し説明してきたが、当業者はさらなる変更及び改良を思いつくと思われる。さらに、本明細書で使用されている「コード」つまり本明細書で使用されている「プログラム」は、複数の２進値、つまり、作業を実行するためにコンピュータまたは実行装置が使用できる実行可能な解釈またはコンパイルされたコードのことである。このコードつまりプログラムは、複数の既知のコンピュータ言語であれば、任意の言語で作成できる。本明細書で使用されている「コンピュータ」は、データを記憶、処理、転送、操作、または同様の操作を実行する任意の装置を意味する。したがって、本発明は説明した特定の形式に制限されず、また、添付の請求項は本発明の主旨及び範囲から逸脱しないすべての代替、変更、変形を含むものとする。
【図面の簡単な説明】
【００２６】
【図１】確率計算時間アルゴリズムを基にリアルタイムアプリケーションを実現するシステムの構成要素を示すブロック図である。
【図２】図１によるシステムの操作を示すフローチャートである。
【図３】本発明による統計記述の生成または更新の実施例を示すフローチャートである。
【図４】本発明による統計記述を生成または更新する代替実施例を示すフローチャートである。
【図５】本発明による統計記述を生成または更新する別の代替実施例を示すフローチャートである。
【図６】本発明による制御の戦略を生成する実施例を示すフローチャートである。
【図７】本発明による制御の戦略を生成する代替実施例を示すフローチャートである。
【図８】本発明による制御の戦略を生成する別の代替実施例を示すフローチャートである。
【符号の説明】
【００２７】
１３０  アプリケーションモジュール、１３２  再構成、１３４  診断、１３６  制御、１４０  制御サブシステム、１５０  システム状態モジュール、１６０  状態アクションモジュール、１７０  実行モジュール、１１０  検知サブシステム、１８０  作動サブシステム。
【図１】
2004199692.tif 000005
【図２】
2004199692.tif 000006
【図３】
2004199692.tif 000007
【図４】
2004199692.tif 000008
【図５】
2004199692.tif 000009
【図６】
2004199692.tif 000010
【図７】
2004199692.tif 000011
【図８】
2004199692.tif 000012