(57)【要約】      （修正有）【課題】非線形動力学を有するエージェントを制御するのに適したマルチエージェント制御のためのシステムおよび方法を提供する。【解決手段】同一の非線形動力学を有する複数のエージェント１０１〜１０４の運動が制御され、初期密度１１０から最終密度１２０までエージェントの密度が変更され、第１の制御問題は、密度空間１５０におけるエージェントの動力学下で初期密度から最終密度へのエージェントの密度変化の制御コストを最適化するように定式化され、マルチエージェント制御１７０およびエージェントの密度にわたる非線形非凸問題である第１の制御問題は、エージェントの密度、およびマルチエージェント制御とエージェントの密度との積にわたる第２の制御問題に変形され、、状態空間１３０のセクションごとに制御入力が生成され、各エージェントの運動が、状態空間の該エージェントのセクションに対応する制御入力に従って制御される。【選択図】図１
2018073395.tif 000002
【特許請求の範囲】
【請求項１】
同一の非線形動力学を有する複数のエージェントの運動を制御するためのシステムであって、
状態空間における前記エージェントの初期密度および所与の時点の前記状態空間における前記エージェントの最終密度のうちの少なくとも１つまたはこれらの組み合わせを示すデータを受信する受信機であって、前記状態空間はセクションの組に分割され、前記状態空間のセクションの密度が、前記状態空間の前記セクション内の状態を有するエージェント数に比例するようにされる、受信機と、
プロセッサであって、
密度空間における前記エージェントの動力学下で前記初期密度から前記最終密度への前記エージェントの密度変化の制御コストを最適化する第１の制御問題を定式化することであって、前記第１の制御問題は、マルチエージェント制御および前記エージェントの密度にわたる非線形非凸制御問題であり、前記マルチエージェント制御は、前記状態空間の前記セクションごとに制御入力を定義する、前記状態空間の前記セクションの組上でパラメーター化される関数であることと、
前記第１の制御問題を第２の制御問題に変形することであって、前記第２の制御問題は、前記エージェントの前記密度、および前記マルチエージェント制御と前記エージェントの前記密度との積にわたる非線形凸問題であることと、
前記第２の制御問題を解いて前記状態空間の前記セクションごとに前記制御入力を生成することと、
を行うように構成される、プロセッサと、
前記各エージェントの運動を、前記状態空間の前記エージェントのセクションに対応する制御入力に従って制御するコントローラーと、
を備える、システム。
【請求項２】
前記プロセッサは、
前記第１の制御問題および前記第２の制御問題を、前記状態空間の近隣セクション間の前記エージェントの流れのシーケンスとして表すことと、
前記第２の制御問題を解いて、前記状態空間のセクション間の時変流量、および前記状態空間の前記セクションの時変密度を得ることと、
前記セクション間の前記時変流量および前記セクションの前記時変密度から、各制御ステップにおける前記制御入力を求めることと、
を行うように構成される、請求項１に記載のシステム。
【請求項３】
前記プロセッサは、
前記状態空間の前記セクションの前記時変密度を用いて、前記状態空間の前記セクション間の前記時変流量から、前記制御の各時間ステップにおける前記セクションごとの制御振幅を抽出することと、
対応する制御振幅を組み合わせることによって、前記制御の前記各時間ステップにおいて各達成可能な制御方向における前記状態空間の前記セクションごとの正味の制御振幅を求めることと、
前記制御の前記各時間ステップにおける前記各達成可能な制御方向における前記制御入力を、対応する正味の制御振幅として求めることと、
を行うように更に構成される、請求項２に記載のシステム。
【請求項４】
前記プロセッサは、
前記状態空間の前記セクションのグラフ構造を決定することであって、グラフの各頂点はセクションを表し、近傍の頂点は少なくとも１つのエッジによって連結されることと、
グラフ上の前記エージェントの前記密度の移流の結果として、各制御時点における前記状態空間の近傍のセクション間の前記エージェントの前記流れのシーケンスを表すことと、
によって前記第１の制御問題および前記第２の制御問題を表すように構成される、請求項２に記載のシステム。
【請求項５】
前記第１の制御問題は、前記エージェントの制御されていない動力学と、前記エージェントの離散時間制御との間で切り替え、前記エージェントの前記制御されていない動力学は、前記密度空間において線形であり、前記エージェントの前記離散時間制御は前記密度空間において非線形であり、前記エージェントの前記制御されていない動力学は、前記エージェントの前記非線形動力学の線形転送作用素と前記エージェントの前記密度との積を含み、前記エージェントの前記離散時間制御は、前記マルチエージェント制御と前記エージェントの前記密度との積を含み、
前記第２の制御問題は、前記マルチエージェント制御と前記エージェントの前記密度との前記積を、変数と置き換え、前記非線形凸問題を形成する、請求項１に記載のシステム。
【請求項６】
前記プロセッサは、時間切り替えの一定の頻度について前記第２の制御問題を解く、請求項５に記載のシステム。
【請求項７】
前記エージェントの前記離散時間制御は、前記エージェントの前記制御されていない動力学よりも少なくとも１０倍高速である、請求項５に記載のシステム。
【請求項８】
前記プロセッサは、
前記状態空間の前記セクションのグラフ構造を求めることであって、グラフの各頂点はセクションを表し、近傍の頂点は少なくとも１つのエッジによって連結されることと、
グラフ上の前記エージェントの前記密度の移流の結果として、各制御時点における前記セクションごとの前記エージェントの前記離散時間制御を表すことと、
を行うように構成される、請求項５に記載のシステム。
【請求項９】
前記エージェントは非線形制御アフィン動力学に従い、
前記第１の制御問題は、線形の第１の項と非線形の第２の項との組み合わせを含み、前記第１の項は、前記エージェントの非線形の制御されていない動力学の線形無限小生成作用素と、前記エージェントの現在の密度との積を含み、前記第２の項は、前記マルチエージェント制御と、制御ベクトルフィールドの線形無限小生成作用素と、前記エージェントの前記密度との積を含み、
前記第２の制御問題は、前記制御ベクトルフィールドごとの前記マルチエージェント制御と前記エージェントの前記密度との積を、変数と置き換え、前記非線形凸問題を形成する、
請求項１に記載のシステム。
【請求項１０】
前記プロセッサは、
前記状態空間の前記セクションのグラフ構造を求めることであって、グラフの各頂点はセクションを表し、近傍の頂点は少なくとも１つのエッジによって連結され、前記各エッジは、前記制御ベクトルフィールドの前記線形無限小生成作用素によって与えられる重みを有する重みベクトルに関連付けられることと、
グラフ上の前記エージェントの前記密度の移流の結果として、前記制御の各時点における前記セクションごとに前記エージェントの前記制御を表すことと、
を行うように構成される、請求項９に記載のシステム。
【請求項１１】
前記第１の制御問題は、異なる制御転送作用素の凸線形結合と、前記エージェントの前記密度との積を含み、前記制御転送作用素は、許容可能な制御を有限数の値に離散化した結果であり、
前記第２の制御問題は、前記エージェントの前記密度と前記凸線形結合の重みとの積を、変数と置き換えて、前記非線形凸問題を形成する、請求項１に記載のシステム。
【請求項１２】
前記コントローラーは、前記各エージェントに、前記状態空間の前記エージェントのセクションに対応する制御入力を適用するコマンドを送信する送信機を備える、請求項１に記載のシステム。
【請求項１３】
前記コントローラーは、前記状態空間のそのセクションに対応する制御入力を適用するアクチュエーターを備える、請求項１に記載のシステム。
【請求項１４】
前記アクチュエーターは、前記エージェントに磁場を印加するための磁気アクチュエーターを含み、前記磁場は前記制御入力によって決定される、請求項１３に記載のシステム。
【請求項１５】
前記受信機は、前記エージェントの初期状態を受信し、前記プロセッサは、前記エージェントの前記初期状態から前記状態空間における前記エージェントの初期確率密度を求める、請求項１に記載のシステム。
【請求項１６】
同一の非線形動力学を有する複数のエージェントの運動を制御するための方法であって、
状態空間における前記エージェントの初期密度および所与の時点の前記状態空間における前記エージェントの最終密度のうちの少なくとも１つ又はこれらの組み合わせを示すデータを受信することであって、前記状態空間はセクションの組に分割され、前記状態空間のセクションの密度が、前記状態空間の前記セクション内の状態を有するエージェント数に比例するようにされることと、
密度空間における前記エージェントの動力学下で前記初期密度から前記最終密度への前記エージェントの密度変化の制御コストを最適化する第１の制御問題を定式化することであって、前記第１の制御問題は、マルチエージェント制御および前記エージェントの密度にわたる非線形非凸制御問題であり、前記マルチエージェント制御は、前記状態空間の前記セクションごとに制御入力を定義する、前記状態空間の前記セクションの組上でパラメーター化される関数であることと、
前記第１の制御問題を第２の制御問題に変形することであって、前記第２の制御問題は、前記エージェントの前記密度、および前記マルチエージェント制御と前記エージェントの前記密度との積にわたる非線形凸問題であることと、
前記第２の制御問題を解いて前記状態空間の前記セクションごとに前記制御入力を生成することと、
前記各エージェントの運動を、前記状態空間の該エージェントのセクションに対応する制御入力に従って制御することと、
を含み、前記方法の少なくともいくつかのステップはプロセッサを用いて実行される、方法。
【請求項１７】
前記第１の制御問題および前記第２の制御問題を、前記状態空間の近隣セクション間の前記エージェントの流れのシーケンスとして表すことと、
前記第２の制御問題を解いて、前記状態空間のセクション間の時変流量、および前記状態空間の前記セクションの時変密度を得ることと、
前記セクション間の前記時変流量および前記セクションの前記時変密度から、各制御ステップにおける前記制御入力を求めることと、
を更に含む、請求項１６に記載の方法。
【請求項１８】
前記状態空間の前記セクションの前記時変密度を用いて、前記状態空間の前記セクション間の前記時変流量から、前記制御の各時間ステップにおける前記セクションごとの制御振幅を抽出することと、
対応する制御振幅を組み合わせることによって、前記制御の前記各時間ステップにおいて各達成可能な制御方向における前記状態空間の前記セクションごとの正味の制御振幅を求めることと、
前記制御の前記各時間ステップにおける各達成可能な制御方向における前記制御入力を、対応する正味の制御振幅として求めることと、
を更に含む、請求項１７に記載の方法。
【請求項１９】
前記状態空間の前記セクションのグラフ構造を決定することであって、グラフの各頂点はセクションを表し、近傍の頂点は少なくとも１つのエッジによって連結されることと、
グラフ上の前記エージェントの前記密度の移流の結果として、各制御時点における前記状態空間の近傍のセクション間の前記エージェントの前記流れのシーケンスを表すことと、
を更に含む、請求項１７に記載の方法。
【請求項２０】
方法を実行するためにプロセッサによって実行可能なプログラムが実現された非一時的なコンピューター可読ストレージ媒体であって、前記方法は、
状態空間におけるエージェントの初期密度および所与の時点の前記状態空間における前記エージェントの最終密度のうちの少なくとも１つ、またはこれらの組み合わせを示すデータを受信することであって、前記状態空間はセクションの組に分割され、前記状態空間のセクションの密度が、前記状態空間の前記セクション内の状態を有するエージェント数に比例するようにされることと、
密度空間における前記エージェントの動力学下で前記初期密度から前記最終密度への前記エージェントの密度変化の制御コストを最適化する第１の制御問題を定式化することであって、前記第１の制御問題は、マルチエージェント制御および前記エージェントの密度にわたる非線形非凸制御問題であり、前記マルチエージェント制御は、前記状態空間の前記セクションごとに制御入力を定義する、前記状態空間の前記セクションの組上でパラメーター化される関数であることと、
前記第１の制御問題を第２の制御問題に変形することであって、前記第２の制御問題は、前記エージェントの前記密度、および前記マルチエージェント制御と前記エージェントの前記密度との積にわたる非線形凸問題であることと、
前記第２の制御問題を解いて前記状態空間の前記セクションごとに前記制御入力を生成することと、
前記各エージェントの運動を、前記状態空間の前記エージェントのセクションに対応する制御入力に従って制御することと、
を含む、非一時的なコンピューター可読ストレージ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチエージェント制御システムおよび方法に関し、より詳細には、非線形動力学を有するエージェントを制御するのに適したマルチエージェント制御システムおよび方法に関する。
【背景技術】
【０００２】
いくつかの状況では、共通の目的に従って複数の移動性のエージェントを制御する必要がある。エージェントは、制御された方式で動くことが可能な任意のオブジェクトとすることができる。エージェントの例は、移動ロボット、ＵＶ（無人車両）、衛星、ＡＵＶ（自律型水中器）、および流体流における固体粒子を含む。個々のエージェントは、先行する動力学（prior dynamics）で動くことができ、その運動は、制御によって変更することができる。全てのエージェントは同じ先行する動力学を有し、複数のマルチエージェント制御アプリケーションにおいて、そのような動力学は非線形である。
【０００３】
様々なマルチエージェント制御アプリケーションは、エージェントを最適な方式で所望の状態に移す制御ポリシーを見つけることを目的としている。例えば、１つの方法は、全てのエージェントについて個々の最適な軌道を計算する。一方、この方法は、計算コストが高く、エージェント数が多すぎるときに対応できない。別の方法は、いくつかのエージェントを「リーダー」として選択し、リーダーに対してのみ軌道を決定し、他のエージェントには何らかのリーダー追従アルゴリズムを適用する。一方、この方法は、リーダーエージェントの失敗の影響を受けやすい。また別の方法は、エージェントの線形動力学のみを考慮することによってエージェントの軌道を決定する。一方、線形動力学の仮定は多くの事例において不正確である。
【０００４】
したがって、非線形動力学を有するエージェントを制御するのに適したマルチエージェント制御システムおよび方法が必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
いくつかの実施の形態の目的は、非線形動力学を有するエージェントを制御するのに適したマルチエージェント制御のためのシステムおよび方法を提供することである。いくつかの実施の形態の別の目的は、マルチエージェント制御の計算負荷を低減しながら、エージェントの共同最適制御を提供することである。一方、いくつかの実施の形態は、エージェントが非線形動力学を有する場合、そのような共同制御最適化が非線形非凸問題であり、解くのが難しい可能性があるという認識に基づいている。
【０００６】
いくつかの実施の形態は、いくつかの応用形態において、全てのエージェントが同一であり、共通の制御目的を有するという認識に基づいている。そのような場合、個々のエージェントの状態は、全てのエージェントの集合的状態ほど重要でない。この認識の結果として、最適化問題における再ラベル付け対称性が得られる。そして、再ラベル付け対称性は、いくつかの用途にとって、エージェントの密度が、個々のエージェントの状態を表すのに十分であることを意味する。そのために、いくつかの実施の形態は、制御を、状態空間ではなく密度空間において実行することができるという認識に基づいている。
【０００７】
そのような認識は、密度空間において、エージェントの自然の、すなわち制御されていない非線形動力学が線形になるため、マルチエージェント制御の目的にとって有利であり得る。一方、エージェントの制御は依然として非線形であり、密度空間における複数のエージェントの全体マルチエージェント制御は、依然として非凸非線形問題である。
【０００８】
いくつかの実施の形態は、密度空間における制御を、流体力学からの類推を用いて記述することができるという認識に基づいている。流体力学では、制御を、状態空間の近傍セクション間のエージェントの流れ、および／または流量に関係付けることができる。この類推から取り入れた洞察を用いて、いくつかの実施の形態は、変数のある特定の変更を伴って、マルチエージェント制御問題を、非線形非凸問題から非線形凸問題に変換する。例えば、１つの実施の形態は、エージェントの制御および密度にわたる非線形非凸制御問題を、エージェントの密度、および制御とエージェントの密度との積にわたる非線形凸問題に変換する。
【０００９】
そのような制御とエージェントの密度との積は、エージェントの流れに類似する。流れは、エージェントの密度に関連しているため、エージェントの密度、および制御とエージェントの密度との積にわたる制御問題は凸である。この制御問題が解かれた後、制御は、エージェントの密度、および制御とエージェントの密度との積の知識から復元することができる。
【００１０】
本明細書において用いられるとき、制御は、状態空間のセクションごとの制御入力を定義する、状態空間のセクションの組上でパラメーター化される関数である。このため、状態を有する個々のエージェントを制御する代わりに、凸問題の解は、エージェントの状態を含むセクションに制御を与える。そのために、いくつかの実施の形態は、状態空間の様々なセクションのための制御入力を決定し、特定のセクションにおける状態を有するエージェントに、その特定のセクションについて決定された制御入力に従って動くようにさせる。例えば、１つの実施の形態は、エージェントに対し、そのエージェントがこの特定のセクションにおける状態を有するエージェントである場合、これがそのエージェントの制御入力であることを指定するメッセージをブロードキャストする。
【００１１】
いくつかの実施の形態では、凸最適化は、グラフベースの手法を用いて定式化される。ここで、グラフのノードは、エージェントの状態の密度を表し、エッジは、自然の動力学および（未知の）制御された動力学の組み合わせの下での密度の流れを表す。このグラフベースの手法は、近傍のセクション、すなわち、グラフのノード間の関係のみを考慮することを可能にする。これによって、計算が単純化し、非線形動力学を有するシステムのための「最適輸送」の理論への拡張が得られる。
【課題を解決するための手段】
【００１２】
したがって、１つの実施の形態は、同一の非線形動力学を有する複数のエージェントの運動を制御するためのシステムを開示する。本システムは、状態空間におけるエージェントの初期密度および所与の時点の状態空間におけるエージェントの最終密度のうちの少なくとも１つ、またはこれらの組み合わせを示すデータを受信する受信機であって、状態空間はセクションの組に分割され、状態空間のセクションの密度が、状態空間のセクション内の状態を有するエージェント数に比例するようにされる、受信機と、プロセッサであって、密度空間におけるエージェントの動力学下で初期密度から最終密度へのエージェントの密度変化の制御コストを最適化する第１の制御問題を定式化することであって、第１の制御問題は、マルチエージェント制御およびエージェントの密度にわたる非線形非凸制御問題であり、マルチエージェント制御は、状態空間のセクションごとに制御入力を定義する、状態空間のセクションの組上でパラメーター化される関数であることと、第１の制御問題を第２の制御問題に変形することであって、第２の制御問題は、エージェントの密度、およびマルチエージェント制御とエージェントの密度との積にわたる非線形凸問題であることと、第２の制御問題を解いて状態空間のセクションごとに制御入力を生成することと、を行うように構成される、プロセッサと、各エージェントの運動を、状態空間のエージェントのセクションに対応する制御入力に従って制御するコントローラーとを備える。
【００１３】
別の実施の形態は、同一の非線形動力学を有する複数のエージェントの運動を制御するための方法を開示する。本方法は、状態空間におけるエージェントの初期密度および所与の時点の状態空間におけるエージェントの最終密度のうちの少なくとも１つ、またはこれらの組み合わせを示すデータを受信することであって、状態空間はセクションの組に分割され、状態空間のセクションの密度が、状態空間のセクション内の状態を有するエージェント数に比例するようにされることと、密度空間におけるエージェントの動力学下で初期密度から最終密度へのエージェントの密度変化の制御コストを最適化する第１の制御問題を定式化することであって、第１の制御問題は、マルチエージェント制御およびエージェントの密度にわたる非線形非凸制御問題であり、マルチエージェント制御は、状態空間のセクションごとに制御入力を定義する、状態空間のセクションの組上でパラメーター化される関数であることと、第１の制御問題を第２の制御問題に変形することであって、第２の制御問題は、エージェントの密度、およびマルチエージェント制御とエージェントの密度との積にわたる非線形凸問題であることと、第２の制御問題を解いて状態空間のセクションごとに制御入力を生成することと、各エージェントの運動を、状態空間のエージェントのセクションに対応する制御入力に従って制御することとを含む、方法の少なくともいくつかのステップは、プロセッサを用いて実行される。
【００１４】
また別の実施の形態は、方法を実行するためにプロセッサによって実行可能なプログラムが実現された非一時的なコンピューター可読ストレージ媒体であって、前記方法は、状態空間におけるエージェントの初期密度および所与の時点の状態空間におけるエージェントの最終密度のうちの少なくとも１つ、またはこれらの組み合わせを示すデータを受信することであって、状態空間はセクションの組に分割され、状態空間のセクションの密度が、状態空間のセクション内の状態を有するエージェント数に比例するようにされることと、密度空間におけるエージェントの動力学下で初期密度から最終密度へのエージェントの密度変化の制御コストを最適化する第１の制御問題を定式化することであって、第１の制御問題は、マルチエージェント制御およびエージェントの密度にわたる非線形非凸制御問題であり、マルチエージェント制御は、状態空間のセクションごとに制御入力を定義する、状態空間のセクションの組上でパラメーター化される関数であることと、第１の制御問題を第２の制御問題に変形することであって、第２の制御問題は、エージェントの密度、およびマルチエージェント制御とエージェントの密度との積にわたる非線形凸問題であることと、第２の制御問題を解いて状態空間のセクションごとに制御入力を生成することと、各エージェントの運動を、状態空間のエージェントのセクションに対応する制御入力に従って制御することとを含む、非一時的なコンピューター可読ストレージ媒体を開示する。
【図面の簡単な説明】
【００１５】
【図１】本発明のいくつかの実施の形態によるマルチエージェント制御の概略図である。
【図２】本発明のいくつかのの実施の形態によって用いられるエージェントの制御された、および制御されていない動力学の概略図である。
【図３】本発明の１つの実施の形態による、非凸マルチエージェント制御問題を凸マルチエージェント制御問題に変換する概略図である。
【図４】本発明の１つの実施の形態による、同一の非線形動力学を有する複数のエージェントの運動を制御するシステムおよび方法のブロック図である。
【図５】本発明のいくつかの実施の形態による、１組のセクションに分割された状態空間の例示的な概略図である。
【図６】本発明のいくつかの実施の形態による、状態空間のセクションの組を表す例示的なグラフである。
【図７Ａ】本発明の１つの実施の形態による、エージェントの時変フローを用いたマルチエージェント制御のための方法のフローチャートである。
【図７Ｂ】本発明の１つの実施の形態による、制御入力を求めるための方法のフローチャートである。
【図７Ｃ】本発明の１つの実施の形態による、第１の制御問題および第２の制御問題を時変流量として表すための方法のフローチャートである。
【図８】本発明の１つの実施の形態による、エージェントの動力学に基づいてマルチエージェント制御のタイプを選択するための概略図である。
【図９Ａ】本発明の１つの実施の形態による、制御切り替え方法のブロック図である。
【図９Ｂ】図９Ａの切り替え方法の原理を示すグラフ９００である。
【図９Ｃ】本発明の１つの実施の形態による切り替え方法のフローチャートである。
【図９Ｄ】本発明の１つの実施の形態による線形転送作用素を決定するための概略図である。
【図１０Ａ】エージェントが非線形制御アフィン動力学に従う１つの実施の形態によるマルチエージェント制御のブロック図である。
【図１０Ｂ】本発明の１つの実施の形態による、各エージェントの制御アフィン動力学を用いたマルチエージェント制御のための方法のフローチャートである。
【図１１Ａ】本発明の１つの実施の形態による、確率的制御転送作用素法の概略図である。
【図１１Ｂ】本発明の１つの実施の形態による、確率的マルチエージェント制御法のための方法のフローチャートである。
【図１２】マルチエージェント制御のために構成された例示的なシステムのブロック図である。
【図１３Ａ】本発明の１つの実施の形態による、マイクロロボットのマルチエージェント制御の例である。
【図１３Ｂ】本発明の別の実施の形態による、エージェントの密度のマルチエージェント制御の例である。
【図１４】本発明の別の実施の形態による、エージェントの密度のマルチエージェント制御の例である。
【発明を実施するための形態】
【００１６】
図１は、本発明のいくつかの実施の形態によるマルチエージェント制御の概略図を示す。初期状態を有するエージェント１０１ａ、１０２ａ、１０３ａおよび１０４ａは、所与の時点において最終状態１０１ｂ、１０２ｂ、１０３ｂおよび１０４ｂに移るように制御される（１７０）。エージェントは、制御された方式で動くことが可能な任意の物体とすることができる。エージェントの例は、モバイルロボット、ＵＶ（無人車両）、衛星、ＡＵＶ（自律型水中器）、および流体流における固体粒子を含む。個々のエージェントは、先行する動力学で動くことができ、その運動は、制御によって変更することができる。マルチエージェント制御の様々な実施の形態において、全てのエージェントは同じ動力学を有し、そのような動力学は非線形であり得る。
【００１７】
本発明のいくつかの実施の形態は、同一の動力学を有するエージェントについて、制御最適化問題における再ラベル付け対称性が存在するという認識に基づいている。例えば、エージェント１０１ａは、状態１０１ｂまたは１０２ｂに動かすことができ、エージェント１０２ａは状態１０２ｂまたは１０３ｂに動かすことができる。エージェントは同一であるので、いずれの特定のエージェントが状態１０２ｂを占有するかは問題ではない。このため、いくつかの用途の場合、エージェントの密度を制御最適化のパラメーターとして用いることができる。そのために、いくつかの実施の形態は、マルチエージェント制御のコスト関数を最小にしながら、初期密度から最終密度までエージェントを制御する問題に対処する。
【００１８】
例えば、マルチエージェント制御システム１８０は、初期密度１１０から最終的密度１２０まで状態空間におけるエージェントの密度を変更するようにこれらのエージェントを制御する（１７０）。エージェントの状態空間は、特定の用途に依拠する。例えば、状態空間は、エージェントの位置および速度を含むことができる。マルチエージェント制御システム１８０は、状態空間１３０から密度空間１５０まで制御最適化を引き上げ（１４０）、密度空間におけるマルチエージェント制御の最適化を実行する。
【００１９】
エージェントは、先行する自然の、すなわち制御されていない動力学を有する。この動力学は、状態空間において非線形であり得る。一方、密度空間において、エージェントの自然の、すなわち制御されていない非線形動力学は線形になる。そのために、いくつかの実施の形態は、状態空間ではなく密度空間において制御を実行する。
【００２０】
このため、個々のエージェントを制御する代わりに、制御最適化問題の解は、所与の状態を有する全てのエージェントのための制御を提供する。そのために、いくつかの実施の形態は、状態空間の様々なセクションについて制御入力を決定し、特定のセクションにおける状態を有するエージェントに、その特定のセクションについて決定された制御入力に従って動くようにさせる（１６０）。例えば、実施の形態は、エージェントに対し、そのエージェントがこの特定の状態にあるエージェントである場合、これがそのエージェントの制御入力であることを指定するメッセージをブロードキャストすることができる。
【００２１】
いくつかの実施の形態は、エージェントの制御されていない動力学が密度空間において線形になる場合であっても、密度空間におけるエージェントの制御が依然として非線形であり、密度空間における複数のエージェントの全体制御が依然として非凸非線形問題であるという認識に基づく。特に、制御されていない動力学に制御項を加えることによって、制御問題が非凸かつ双線形になり、これは非線形性の特殊なタイプであり、ここで、制御および状態が乗算される。したがって、この非凸制御問題を凸問題に変換する必要がある。
【００２２】
図２は、本発明のいくつかのの実施の形態によって用いられるエージェントの制御された、および制御されていない動力学の概略図を示す。制御されていない動力学２３０は、初期密度２１０を異なる時点における密度２４０、２５０および２６０に変更する。マルチエージェント制御１７０は、制御されていない動力学２３０とマルチエージェント制御１７０との組み合わせによって、初期密度２１０を最終密度２２０に変更するように決定される。
【００２３】
本発明のいくつかの実施の形態は、密度空間における制御を、流体力学からの類推を用いて説明することができるという認識に基づいている。流体力学では、制御を、状態空間の近傍セクション間のエージェントの流れ、および／または流量に関係付けることができる。この類推から取り入れた洞察を用いて、いくつかの実施の形態は、変数のある特定の変更を伴って、制御問題を、非線形非凸問題から非線形凸問題に変換する。例えば、１つの実施の形態は、制御およびエージェントの密度にわたる非線形非凸制御問題を、エージェントの密度、および制御とエージェントの密度との積にわたる非線形凸問題に変換する。
【００２４】
図３は、本発明の１つの実施の形態による、非凸マルチエージェント制御問題を凸マルチエージェント制御問題に変換する概略図を示す。実施の形態は、所与の時点におけるマルチエージェント制御３１５およびエージェントの密度３１７にわたる第１の制御問題３１０を定式化する。マルチエージェント制御３１５は、状態空間のセクションごとに制御入力を定義する、状態空間のセクションの組上でパラメーター化される機能である。そのような制御入力は、エージェントに対し作用する外力を表す。例えば、状態空間は、状態の全ての可能な値の一部分を定義する矩形である。この矩形の状態空間は、正方形のセクションに分割することができる。このとき、制御値は、各正方形の中心の座標（ｘ，ｙ）の関数である。そして、エージェントの密度３１７は、エージェントの制御されていない先行する非線形の動力学を表す。制御された動力学および制御されていない動力学の双方がエージェントの密度を変更するので、第１の制御問題は、マルチエージェント制御と、エージェントの密度との積を含み、これによって、第１の制御問題３１０が非凸になる。
【００２５】
いくつかの実施の形態は、制御とエージェントの密度との積がエージェントの流れを表すという認識に基づく。積を１つの新たな変数と置き換えることによって、ここで、動力学はこの新たな変数において線形になる。ここで、制御項は「分子が二次で分母が一次の（quadratic over linear）」形式をとり、これは、新たな変数の凸関数である。そのために、１つの実施の形態は、第１の制御問題３１０を、エージェントの密度、およびマルチエージェント制御とエージェントの密度との積にわたる第２の制御問題３２０に変形する（３３０）。結果として、第２の制御問題は、非線形凸問題である。この制御問題が解かれた後、制御は、エージェントの密度、および制御とエージェントの密度との積の知識から復元することができる。
【００２６】
図４は、本発明の１つの実施の形態による、同一の非線形動力学を有する複数のエージェントの運動を制御するシステム４００および方法のブロック図を示す。実施の形態は、状態空間内のエージェントの初期密度および所与の時点における状態空間内のエージェントの最終密度のうちの少なくとも１つ、またはそれらの組み合わせを示すデータを受信する（４１０）。例えば、データは、有線または無線チャネルを介して受信機を用いて受信することができる（４１０）。状態空間は、セクションの組に分割され、状態空間のセクションの密度が、状態空間のセクション内の状態を有するエージェント数に比例するようにされる。状態空間のセクションは、システム４００（図示せず）のメモリにおいて予め決定し、記憶することができる。
【００２７】
図５は、第１のセクション５１０および第２のセクション５２０を含むセクションの組に分割された状態空間５００の例示的な概略図を示す。この例において、第１のセクション５１０は、３つのエージェント５１１、５１２および５１３を含む。第２のセクション５２０は２つのエージェント５２１および５２２を含む。１つの実施の形態の原理によれば、この例において、セクション５１０の密度は数３に比例し、セクション５２０の密度は数２に比例する。状態空間のセクションの組の全てのセクションの密度は、初期密度、最終密度又は中間密度等のエージェントの密度を形成する。
【００２８】
実施の形態は、密度空間におけるエージェントの動力学を受ける制御コストを最適化する第１の制御問題を定式化する（４２０）。第１の制御問題３１０は、マルチエージェント制御およびエージェントの密度にわたる非線形非凸制御問題である。マルチエージェント制御は、状態空間のセクションごとに制御入力を定義する、状態空間のセクションの組上でパラメーター化される機能である。例えば、マルチエージェント制御は、制御入力の組を定義し、状態空間のセクションごとに１つの入力が存在する。例えば、マルチエージェント制御は、第１の制御セクション５１０のための第１の制御入力と、第２のセクション５２０のための第２の制御入力とを含む。
【００２９】
制御問題が解かれた後、状態の同じセクション内の全てのエージェントが、同じ制御入力に従って同様に制御される。例えば、エージェント５１１、５１２および５１３は、これらのエージェントが同じ制御入力に従って制御される所与の時間にわたって、同じ状態セクション５１０内に収まる状態を有する。一方、同じ制御入力が、エージェントを状態空間の異なるセクション内に動かす可能性がある。このため、制御の異なるステップについて、エージェント５１１、５１２および５１３は異なる制御入力に従って制御することができる。
【００３０】
第１の制御問題は、非線形非凸問題である。したがって、実施の形態は、第１の制御問題を、エージェントの密度、およびマルチエージェント制御とエージェントの密度との積にわたる第２の制御問題に変形する（４３０）。例えば、マルチエージェント制御とエージェントの密度との積は、第２の制御問題における変数と置き換えられる。第２の制御問題は、非線形凸問題である。実施の形態は、第２の制御問題を解いて、状態空間のセクションごとに制御入力を生成し、各エージェントの運動を、状態空間のそのセクションに対応する制御入力に従って制御する。
【００３１】
例えば、実施の形態は、プロセッサ４７０を用いて、制御問題を定式化し、変形し、解くことができる。プロセッサ４７０は、メモリに記憶された命令（図示せず）を実行するように構成することができる。プロセッサ４７０は、シングルコアプロセッサ、マルチコアプロセッサ、コンピューティングクラスター、または任意の数の他の構成体とすることができる。メモリは、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、フラッシュメモリ、または他の任意の適したメモリシステムを含むことができる。
【００３２】
実施の形態は、コントローラー４８０を用いて、各エージェントの運動を制御することができる。例えば、１つの実施態様では、コントローラーは、各エージェントにコマンドを送信、例えばブロードキャストまたはユニキャストして、状態空間のそのエージェントのセクションに対応する制御入力を適用する送信機を備える。更にまたは代替的に、１つの実施態様では、コントローラーは、状態空間のそのエージェントのセクションに対応する制御入力を適用するためのアクチュエーターを含む。例えば、アクチュエーターは、エージェントへの制御入力によって決定される磁場を印加するための磁気アクチュエーターを含むことができる。
【００３３】
１つの実施の形態では、凸最適化は、グラフベースのフレームワークを用いて定式化される。ここで、グラフのノードは、エージェントの状態の密度を表し、エッジは、自然の動力学および制御された動力学の組み合わせの下での密度の流れを表す。このグラフベースのフレームワークは、状態空間の近傍のセクション、すなわち、グラフのノード間の関係のみを考慮することを可能にする。これによって、計算が単純化し、非線形動力学を有するシステムのための「最適輸送」の理論への拡張が得られる。
【００３４】
図６は、本発明のいくつかの実施の形態による、状態空間のセクションの組を表す例示的なグラフ６００を示す。頂点６２０および頂点６３０等の、グラフ６００の各頂点は、状態空間のセクションを表す。近傍セクションを表す頂点は、エッジ６１０等のエッジによって連結される。異なる実施の形態では、密度は、グラフの各頂点上のその「質量」によって特定され、エッジは一方向性とすることができ、セクション間のエージェントの流れの方向を詳細に指す。更にまたは代替的に、エッジは、セクション間のエージェントの交換が可能であることを示す双方向を指すことができる。エッジのタイプは、例えば、エージェントの動力学のタイプから、および／またはセクション内の状態の値間の関係から決定することができる。
【００３５】
グラフベースのフレームワークは、全てのロケーションから全ての他のロケーションへの輸送を計算する、はるかにより計算コストが高いステップではなく、近傍頂点間のエージェントの時変フローを計算することを可能にする。近傍ノード／セクションのみが連結されているので、グラフ６００はスパースである。いくつかの実施の形態は、結果として得られるグラフ構造におけるスパース性を利用して、計算の利点を得る。問題は、ここでもまた流体力学における発展によって動機付けされた、変数の変化による凸最適化問題に変換される。制御振幅を計算するのではなく、いくつかの実施の形態は、エージェントの最適なフローまたは流動を計算する。これらのエージェントの最適な流れまたは流動が計算されると、制御入力は、後処理ステップにおいて見つけることができる。
【００３６】
図７Ａは、本発明の１つの実施の形態による、エージェントの時変フローを用いたマルチエージェント制御のための方法のフローチャートを示す。本方法は、第１の制御問題および第２の制御問題を、状態空間の近傍セクション間のエージェントの一連の流れとして表す（７１０）。各エージェントを制御するのではなく、これらの制御問題は、エージェントの適切な最終密度をもたらす速度フィールドを計算するように定式化される。
【００３７】
本方法は、第２の制御問題を解いて、セクション間の時変流量およびセクションの時変密度を得る（７２０）。第２の問題は凸であるため、凸問題のための様々な解が異なる実施の形態によって用いられる。例えば、いくつかの実施の形態は、凸最適化問題をより小さな部分に分けることによってこの問題を解く交互方向乗数法（ＡＤＭＭ）を用いる。次に、本方法は、セクション間の時変流量およびセクションの時変密度から各制御ステップにおける制御入力を求める（７３０）。
【００３８】
図７Ｂは、本発明の１つの実施の形態による、セクション間の時変流量およびセクションの時変密度から制御入力を求める（７２０）方法のフローチャートを示す。図７Ｂの方法は、セクションの時変密度を用いて、セクション間の時変流量から、制御の各時間ステップにおけるセクションごとの制御振幅を抽出する（７４０）。例えば、本方法は、流量を密度で除算して、制御振幅を得る。
【００３９】
次に、本方法は、方向ごとに、全ての流入流の流入制御振幅を加算し、全ての流出流の制御振幅を減算することを組み合わせることによって、制御の各時間ステップにおける各達成可能な制御方向のセクションごとの正味の制御振幅を求める（７５０）。次に、本方法は、制御の各時間ステップにおける各達成可能な制御方向における制御入力を、対応する正味の制御振幅として求める（７６０）。
【００４０】
図７Ｃは、１つの実施の形態による、第１の制御および第２の制御を、セクション間の時変流量およびセクションの時変密度として表すための方法のフローチャートを示す。実施の形態は、状態空間のセクションのグラフ６００等のグラフを求める（７７０）。グラフの各頂点はセクションを表し、近傍の頂点は、少なくとも１つのエッジによって連結される。
【００４１】
実施の形態は、グラフ上のエージェントの密度の動きの結果としての、制御の各時点における状態空間の近傍セクション間のエージェントの流れのシーケンスを表す（７８０）。密度のこの流れは、式（４）等の移流方程式によって与えられる。この移流方程式は、状態空間の各セクションにおけるエージェントの密度の変化の速度を、近傍のセクションからそのセクションへの流入流および流出流間の差と同等とみなす。この流入流および流出流は、自然動力学に起因した、および制御動作に起因した、流れの組み合わせである。
【００４２】
様々な実施の形態において、個々のエージェントの動力学は非線形であり、このため、実施の形態は非自明な非線形動力学を用いてエージェントに適用可能である。実施の形態は最適化問題における対称性およびスパース性を利用するため、実施の形態ははるかにより多くの数のエージェントに対応可能であり、特定のエージェントの選択に依存せず、このため、任意の特定のエージェントの失敗に対して頑健である。
【００４３】
図８は、エージェントの動力学に基づいてマルチエージェント制御のタイプを選択する（８１０）ための概略図を示す。例えば、１つの実施の形態は、エージェントの動力学が、制御よりも１桁遅いとき、制御切り替え法８２５を選択する（８２０）。その状況では、離散時間制御の適用時間が比較的小さく、離散時間制御の影響が優勢である。そのために、エージェントの制御されていない動力学は、離散時間制御の適用の持続時間にわたって無視することができる。
【００４４】
更にまたは代替的に、エージェントが非線形の制御アフィン動力学に従う場合（８３０）、無限小生成作用素を介した連続時間制御８３５が用いられる。時間離散切り替え方法と対照的に、エージェントの制御アフィン動力学は、マルチエージェント制御問題を、連続時間制御として定式化することを可能にする。更にまたは代替的に、いくつかの実施の形態は、確率的転送作用素行列に基づいたマルチエージェント制御を用いる。
【００４５】
図９Ａは、本発明の１つの実施の形態による、制御切り替え方法のブロック図を示す。この実施の形態において、第１の制御問題は、エージェントの制御されていない動力学と、エージェントの離散時間制御との間で切り替える（９１０）。エージェントの制御されていない動力学は、密度空間において線形であるのに対し、エージェントの離散時間制御は密度空間において非線形である。この実施の形態において、エージェントの制御されていない動力学は、エージェントの非線形動力学の線形転送作用素と、エージェントの現在の密度との積を含み、エージェントの離散時間制御は、制御とエージェントの現在の密度との積を含む。非線形凸問題を形成するために、第２の制御プログラムは、制御とエージェントの現在の密度との積を、変数と置き換える（９２０）。
【００４６】
図９Ｂは、図９Ａの切り替え方法の原理を示すグラフ９００を示す。切り替え方法は、作用素分割方法によって動機付けされ、運動の異なる時間ステップにおいて異なる作用素が用いられるようにされる。特に、マルチエージェント制御は、２つのタイプの輸送を切り替えて、所与の時間に初期分布から所望の最終分布への完全な輸送を得ることによって行われる。切り替え時間は、一定の頻度を有することができる。第１のタイプの輸送変換は、中間密度、例えば９４１および９４２を得るための制御されていない動力学、例えば９３１および９３２に起因する。第１の輸送は、転送作用素Ｐ９３０を用いて実行される。第２のタイプの輸送は、ＯＴ９４０によって示される、離散時間において適用される制御動作に起因する。Ｔ時間ステップ最適化問題は、ｉ＝１〜Ｔについて密度の対
【数１】
2018073395.tif 000003
について解くことを含む。後者の密度は、制御動作下における前者の展開によって得られる。
【００４７】
図９Ｃは、本発明の１つの実施の形態による切り替え方法の詳細なフローチャートを示す。本方法は、以下の関係に従って、エージェントの動力学並びに初期密度および最終密度を定義することにより初期化される（９５０）。
【数２】
2018073395.tif 000004
ここで、ρｉはｉ番目の制御後の密度であり、
【数３】
2018073395.tif 000005
はｉ番目の制御前の密度であり、Ｔｉはｉ番目の制御の動作を表す作用素である。
【００４８】
時点ｉにおける密度
【数４】
2018073395.tif 000006
は以下によって関係付けられる。
【数５】
2018073395.tif 000007
ここで、
【数６】
2018073395.tif 000008
はｉ番目の制御の前の密度であり、
【数７】
2018073395.tif 000009
は（ｉ−１）番目の制御後の密度であり、Ｐは先行する動力学の動作を表す転送作用素である。
【００４９】
図９Ｄは、本発明の１つの実施の形態による、ウラム法（Ulam's method）を用いて決定された線形転送作用素Ｐを決定するための概略図を示す。状態空間９７５が、セクションＢｉ９７１およびセクションＢｊ９７２を含むＮ個のセクション（Ｂ１，Ｂ２，．．．，ＢＮ）の組に離散化される。セクションＢｊ等の状態空間のセクションのための転送作用素Ｐの行列がウラム法によって得られる（９５２）。例えば、セクション９７２は、例えば一様にサンプリングされ、動力学Ｆの下で事前イメージ９７０が計算される。事前イメージ９７０は、先行する動力学の下で１つの時間ステップにおいてセクションＢｊ内に入る全ての点の組である。セクション９７１および事前イメージ９７０の交差部分９７３の面積をセクション９７１の面積で除算したものによって、行列Ｐの（ｉ，ｊ）エントリが得られる。
【００５０】
最適化問題は、上記の２つの式の下で密度の対
【数８】
2018073395.tif 000010
間の移流のコストの平方和を最小にすることを含む。最適輸送流作用素について直接解くことは、計算コストが非常に高いことが認識されている。このため、いくつかの実施の形態は、最適化問題を解決するために連続時間離散空間手法を用いる。
【００５１】
例えば、いくつかの実施の形態は、状態空間のセクションのグラフ構造を決定し、グラフの各頂点はセクションを表し、近傍の頂点は、少なくとも１つのエッジによって連結され、グラフ上のエージェントの密度の移流の結果としての各制御時点におけるセクションごとのエージェントの離散時間制御を表す。例えば、１つの実施の形態は、（ρ、Ｕ）変数におけるＧに対する移流方程式を用いて、疑似時間におけるＯＴ制御摂動を表し（９５４）、Ｔ個の時間ステップについてＰとＯＴとの間で切り替えることによって非凸最適化問題を定式化する（９５６）。
【００５２】
例えば、最適輸送（ＯＴ）ステップは、輸送を各対間のＧにおける連続時間流として書くことによって以下のように計算される。
【数９】
2018073395.tif 000011
ここで、ρ（ｖ）はｖ番目の頂点６２０における質量であり、ρ（ｗ）はｗ番目の頂点６３０における質量であり、Ｕ（ｔ，ｅ）はエッジｅ６１０上の時点ｔにおける制御であり、エッジｅは頂点ｖから頂点ｗに向かう。
【００５３】
式（３）は、疑似時間変数が０から１に向かうときに、速度Ｕにわたって最小化されるコスト関数である。式は、擬似時間が増大しているときの密度質量の変動を記述する。この式は、有限差分法を用いて、疑似時間変数において小さな数のステップに離散化される。
【数１０】
2018073395.tif 000012
に従う速度変数Ｕから流れＪヘの変数の変化により、非凸最適化問題が凸最適化問題に変換される（９５８）。この変換後、上記の式（３）および式（４）の離散化バージョンが、分散の対ごとに、式（２）によって与えられる関係に沿って組み合わされる。次に、１つ以上の凸最適化ソルバーを用いて完全最適化問題が解かれる（９６０）。
【００５４】
図１０Ａは、エージェントが非線形制御アフィン動力学に従う１つの実施の形態による事例のためのマルチエージェント制御のブロック図を示す。この実施の形態では、第１の制御問題は、線形の第１の項および非線形の第２の項の組み合わせを含む（１０１０）。第１の項は、エージェントの非線形の制御されていない動力学の線形無限小生成作用素と、エージェントの現在の密度との積を含み、第２の項は、制御と、制御ベクトルフィールドの線形無限小生成作用素と、エージェントの現在の確率密度との積を含む。非線形凸問題を形成するために、第２の制御問題は、制御ベクトルフィールドごとの制御とエージェントの現在の密度との積を変数と置き換える（１０２０）。
【００５５】
例えば、この実施の形態は、切り替え手法を用いるのではなく、単一のステップにおいて最適制御ポリシーの直接計算を可能にするようにグラフ構造を変更する。例えば、実施の形態は、状態空間のセクションのグラフ構造を決定する。グラフの各頂点はセクションを表し、近傍の頂点は、少なくとも１つのエッジによって連結され、各エッジは、制御ベクトルフィールドの線形無限小生成作用素によって与えられる重みを有する重みベクトルに関連付けられる。実施の形態は、グラフ上のエージェントの密度の移流の結果として、制御の各時点におけるセクションごとにエージェントのマルチエージェント制御を表す。
【００５６】
各エージェントの制御アフィン動力学は、以下の形式で書くことができる。
【数１１】
2018073395.tif 000013
ここで、ｘはエージェントの状態であり、ｕｉはｉ番目の制御入力を表し、ｆは各エージェントの自然動力学ベクトルフィールドであり、ｇｉはｉ番目の制御ベクトルフィールドである。
【００５７】
この実施の形態では、エッジｅについてＦ（ｅ）およびＧｉ（ｅ）として表される各エッジの（ｋ＋１）個の異なるエッジ重みが、異なるベクトルフィールドの流れに従って計算される。例えば、この計算は、（ｋ＋１）個のベクトルフィールドの各々に対応する転送作用素の無限小生成作用素を用いることによって行われる。この無限小生成作用素は、エッジによって連結される２つのセクション間の境界にわたる各ベクトルフィールドの単位振幅Ｕｉに起因した無限小流を計算する。次に、変更された最適輸送問題が定式化され、ここで、未知数は、ｋ個の制御ベクトルフィールドに対応する各エッジにわたるｋ個の時変制御振幅である。
【００５８】
第１の制御問題は、以下に基づいて定式化することができる。
【数１２】
2018073395.tif 000014
ここで、Ｕｉ（ｔ，ｅ）は、エッジｅ６１０にわたる時点ｔにおけるｉ番目の制御ベクトルフィールドの制御振幅であり、ｅは、頂点ｖ６２０から頂点ｗ６３０に向かうエッジである。Ｇ０（ｅ）は、エッジｅにおける自然動力学ベクトルフィールドｆの無限小生成作用素の値であり、Ｇｉ（ｅ）は、エッジｅにおけるｉ番目の制御ベクトルフィールドｇｉの無限小の値である。
【００５９】
第２の制御問題を形成するために、制御振幅から流れへの制御ごとの変数の変更を以下のように行うことができる。
【数１３】
2018073395.tif 000015
【００６０】
エージェントごとの制御入力は、流れＪｉを用いて計算することができ、制御振幅Ｕｉは式（８）における最適化によって計算することができる。例えば、１つの実施の形態は、ベクトルフィールドｆおよびｇｉごとに、各セクションに出入りする時間依存の正味の流れを求める。例えば、時間依存の正味の流れは、ｊ番目のセクション内に入るか、ｊ番目のセクションから出るエッジごとに、時間依存の流入流から流出流を減算したものを計算することによって求めることができる。ベクトルフィールドごとにこのプロセスが完了した後、エージェントごとのベクトルフィールドごとの制御入力が、この正味の流れに等しくなるように設定される。このため、エージェントごとのフィードバック制御は、その正確な状態の値ではなく、現時点におけるその状態が存在するセクションに依拠する。セクション離散化のサイズが小さくされると、結果として得られる制御が、式（７）における動力学下で所望の分布間の最適な輸送を実行するのに必要な理論最適制御に近づく。
【００６１】
図１０Ｂは、本発明の１つの実施の形態による各エージェントの制御アフィン動力学のための方法の詳細なフローチャートを示す。本方法は、以下の関係に従って、エージェントの動力学並びに初期密度および最終密度を定義することで初期化される（１０３０）。エージェントの動力学は式（７）に従って定義される。本方法は、ベクトルフィールドのためのＧにおいて無限小生成作用素を計算し（１０４０）、連続時間移流方程式（９）を用いて、結合された非凸最適化問題方程式（８）を定式化する（１０５０）。例えば、エッジｅにわたる無限小生成作用素Ｇｉ（ｅ）は、頂点ｖおよびｗの交差部における面にわたってベクトルフィールドｇｉを積分し、頂点ｖに属するセクションの面積で除算することによって計算される。ここで、ｅは頂点ｖおよびｗ間のエッジである。
【００６２】
次に、本方法は、例えば、式（１０）に従って変数を変更し（１０６０）、凸問題を形成し、ＡＤＭＭを用いて凸最適化問題を解き、最適化変数ρおよびＪの時変値を得る（１０７０）。後処理ステップ１０８０において、本方法は、同じセクション内の全てのエージェントについて固定値を有する制御入力ｕを決定する。
【００６３】
図１１Ａは、本発明の１つの実施の形態による、確率的制御転送作用素法の概略図を示す。この実施の形態において、確率的制御ポリシー１１１０、１１１１、１１１２、１１１３および１１１４が、時間ステップごとに計算され、第１段階において得られた中間分布を達成する。この実施の形態において、状態空間のｉ番目のセクションにおけるエージェントにわたる制御は、有限数の可能な「制御転送作用素」Ｐｋにわたる期待値、すなわち、異なる転送作用素の凸線形結合としてモデル化される。これらの制御転送作用素は、許容可能な制御を有限数の値に離散化し、次に、ウラム方法を介して制御の各有限値の下で対応する作用素Ｐｋを計算した結果である。最適化問題において解かれる未知数は、各行がＰｋの各列の重みのベクトルであるＱ行列を含む。
【００６４】
例えば、１つの実施の形態は、以下を用いて第１の制御問題を定式化する。
【数１４】
2018073395.tif 000016
ここで、ρｔ（ｉ）は、ｉ番目のセクションにおける時点ｔにおける密度であり、ρｔ＋１（ｊ）は、ｊ番目のセクションにおける時点（ｔ＋１）における密度であり、Ｑｉｋは、状態がｉ番目のセクションにあるエージェントを展開するためのｋ番目の制御転送作用素Ｐｋを選択する確率を表す。
【００６５】
次に、実施の形態は、以下に従って、マルチエージェント制御とエージェントの密度との積を、変数と置き換えることによって、第２の制御問題を定式化する。
【数１５】
2018073395.tif 000017
【００６６】
更にまたは代替的に、元のシステム動力学のｎステップ制御可能性の結果として、分布のｎステップ制御可能性が得られることが実現される。これによって、確率制御の保証された存在が可能になり、その各々の結果として、個々のエージェントに対する許容可能な制御が得られる。輸送のコストは、状態空間の全てのセクションにわたって合算された、制御入力に対する線形コストまたは二次コストである。１つの実施の形態は、この問題定式化を、最終密度が制御によって厳密に達成可能でない場合があるか、またはこれらの分布を達成するのに必要とされる制御が達成可能でない場合がある可能性を許容する。この緩和定式化の第１の段階中、最終分布は、コスト関数にペナルティ項を追加することによってソフト制約として課され、このコスト関数は、実際の最終密度の所望の最終密度との偏差にペナルティを課し、近似解を許容する。
【００６７】
図１１Ｂは、本発明の１つの実施の形態による、確率的マルチエージェント制御法のための方法のフローチャートを示す。本方法は、以下の関係に従って、エージェントの動力学並びに初期密度および最終密度を定義することで初期化される（１１２０）。エージェントのための許容可能な制御は離散化され（１１３０）、離散化された制御入力の組が生成される。例えば、モバイルシステムへの力入力範囲は［０，１］Ｎｅｗｔｏｎｓであり、この際、離散力入力は［０，．２，．４，．６，．８，１］Ｎｅｗｔｏｎｓであり得る。
【００６８】
実施の形態は、離散化された制御入力ごとに、制御転送作用素の組を計算する（１１４０）。例えば、図９Ｄに関連して上記で説明したように、各制御転送作用素は、ウラムの方法を用いて決定することができる。
【００６９】
第１の制御問題は、確率的制御を用いて各時点において密度を展開することによって定式化される（１１５０）。例えば、密度は、各時点において、重みＱを有するＰｋの凸結合である確率的制御を用いて展開することができる。例えば、式（６）を参照されたい。
【００７０】
次に、実施の形態は、変数を変更して凸最適化問題を形成し（１１６０）、第２の制御問題を解き、各離散時間における最適制御入力を得る（１１７０）。例えば、実施の形態は、マルチエージェント制御とエージェントの密度との積を、Ｒｉｋ＝ρ（ｉ）Ｑｉｋに従って変数と置き換える。そのために、解は、Ｒおよびρの時変値を生成する。これらの値について、実施の形態は、各離散時間における最適な制御入力を得るための値Ｑを更に求めることができる。
【００７１】
図１２は、マルチエージェント制御のために構成された例示的なシステム１２００のブロック図を示す。システム１２００のコンポーネントの様々な組み合わせを、エージェントの制御のためにエージェントおよび／またはマルチエージェントシステムにおいて実施することができる。システム１２００は、センサー１２１０、慣性測定ユニット（ＩＭＵ）１２３０、プロセッサ１２５０、メモリ１２６０、送受信機１２７０、およびディスプレイ１２８０／スクリーンのうちの１つ、または組み合わせを備えることができる。これらは、接続１２２０を通じて他のコンポーネントに動作可能に結合することができる。接続１２２０は、バス、ライン、ファイバー、リンク又はそれらの組み合わせを含むことができる。
【００７２】
マルチエージェント制御システムにおいて実施される送受信機１２７０は、エージェントの初期密度および最終密度を受信し、制御入力をエージェントに通信するために用いることができる。エージェントにおいて実施される送受信機１２７０は、エージェントの現在の状態を送信および／または制御入力を受信するために用いることができる。送受信機１２７０は、例えば、１つ以上のタイプの無線通信ネットワークを通じて１つ以上の信号を送信することを可能にする送信機と、１つ以上のタイプの無線通信ネットワークを通じて送信された１つ以上の信号を受信する受信機とを備えることができる。送受信機１２７０は、様々な技術に基づいて無線ネットワークとの通信を可能にすることができる。これらの技術は、標準規格のＩＥＥＥ８０２．１１ファミリーに基づくことができるフェムトセル、Ｗｉ−Ｆｉネットワーク又は無線ローカルエリアネットワーク（ＷＬＡＮ）、標準規格のＩＥＥＥ８０２．１５ｘファミリーに基づくＢｌｕｅｔｏｏｔｈ（登録商標）、近距離場通信（ＮＦＣ）、ネットワーク等の無線パーソナルエリアネットワーク（ＷＰＡＮ）、および／またはＬＴＥ、ＷｉＭＡＸ等の無線ワイドエリアネットワーク（ＷＷＡＮ）等であるが、これらに限定されるものではない。システム１２００は、有線ネットワークを通じて通信する１つ以上のポートを備えることもできる。
【００７３】
いくつかの実施の形態では、システム１２００は、ＣＣＤセンサーもしくはＣＭＯＳセンサー、レーザーおよび／またはカメラ等の画像センサー１２１０を備えることができる。この画像センサーは、以下では「センサー１２１０」と呼ばれる。センサー１２１０は、エージェントの状態を検知してエージェントの現在の密度を求めるために用いることができる。センサー１２１０は、エージェントによって、割り当てられたアプリケーションを実行するために用いることができる。例えば、センサー１２１０は、「カラー情報」を提供するカラーカメラまたはグレースケールカメラを含むことができる。「カラー情報」という用語は、本明細書において用いられるとき、カラー情報および／またはグレースケール情報を指す。例えば、センサー１２１０は、「奥行き情報」を提供する奥行きセンサーを含むことができる。例えば、いくつかの実施の形態では、センサー１２１０はＲＧＢＤカメラを備える。このＲＧＢＤカメラは、カラー（ＲＧＢ）画像に加えて、奥行きセンサーが有効にされているときはピクセルごとの奥行き（Ｄ）情報を捕捉することができる。
【００７４】
いくつかの実施の形態では、センサー１２１０は立体カメラを備える。例えば、奥行きセンサーは、２つ以上のカメラを用いてシーンの奥行き情報を取得することができる受動ステレオビジョンセンサーの一部分を成すことができる。捕捉されたシーンにおける双方のカメラに共通の点のピクセル座標を、カメラ姿勢情報および／または三角測量技法とともに用いて、ピクセルごとの奥行き情報を取得することができる。
【００７５】
いくつかの実施の形態では、システム１２００は、デュアルフロントカメラおよび／または前面カメラおよび背面カメラ等の複数のセンサー１２１０に動作可能に接続することができ、これらの複数のセンサーは、様々なセンサーを組み込むこともできる。いくつかの実施の形態では、センサー１２１０は、静止画像およびビデオ画像の双方を捕捉することができる。いくつかの実施の形態では、センサー１２１０は、例えば、３０フレーム毎秒（ｆｐｓ）で画像を捕捉することが可能なＲＧＢＤ又は立体ビデオカメラを備えることができる。１つの実施の形態では、センサー１２１０によって捕捉された画像は、生の未圧縮フォーマットとすることができ、処理および／またはメモリ１２６０への記憶の前に圧縮することができる。いくつかの実施の形態では、画像圧縮は、プロセッサ１２５０によって可逆圧縮技法または非可逆圧縮技法を用いて実行することができる。
【００７６】
いくつかの実施の形態では、プロセッサ１２５０は、ＩＭＵ１２３０から入力を受信することもできる。他の実施の形態では、ＩＭＵ１２３０は、３軸加速度計（複数の場合もある）、３軸ジャイロスコープ（複数の場合もある）、および／または磁気計（複数の場合もある）を備えることができる。ＩＭＵ１２３０は、速度、方位、および／または他の位置関連情報をプロセッサ１２５０に提供することができる。いくつかの実施の形態では、ＩＭＵ１２３０は、測定された情報を、センサー１２１０による各画像フレームの捕捉と同期して出力することができる。いくつかの実施の形態では、ＩＭＵ１２３０の出力は、プロセッサ１２５０がエージェントの密度を求めるのに部分的に用いられる。
【００７７】
また、システム１２００は、カラー画像および／または奥行き画像等の画像をレンダリングするスクリーンまたはディスプレイ１２８０を備えることができる。いくつかの実施の形態では、ディスプレイ１２８０は、センサー１２１０によって捕捉されたライブ画像を表示するのに用いることができる。いくつかの実施の形態では、ディスプレイ１２８０は、ユーザーが、仮想キーボード、アイコン、メニュー、または他のＧＵＩ、ユーザージェスチャーおよび／またはスタイラスおよび他の筆記用具等の入力デバイスのある組み合わせを介してデータを入力することを可能にするタッチスクリーンを備えることができ、および／または、このようなタッチスクリーンとともに収容することができる。いくつかの実施の形態では、ディスプレイ１２８０は、液晶ディスプレイ（ＬＣＤ）または有機ＬＥＤ（ＯＬＥＤ）ディスプレイ等の発光ダイオード（ＬＥＤ）ディスプレイを用いて実施することができる。他の実施の形態では、ディスプレイ１２８０は、ウェアラブルディスプレイとすることができる。
【００７８】
マルチエージェント制御システムのいくつかの実施の形態において、プロセッサ１２５０は、様々な実施の形態に従って、マルチエージェント制御１２５５を実行することができる。システム１２００がエージェントにおいて実施されるとき、プロセッサ１２５０はエージェントに割り当てられたアプリケーション１２５５を実行するように構成することができる。
【００７９】
例示的なシステム１２００は、図示した機能ブロックのうちの１つ以上の追加、組み合わせ、または省略等によって、本開示と整合性を有するように様々な方法で変更することもできる。例えば、いくつかの構成では、システム１２００は、ＩＭＵ１２３０または送受信機１２７０を備えていない。さらに、いくつかの特定の例示の実施態様では、システム１２００は、周辺光センサー、マイクロフォン、音響センサー、超音波センサー、レーザーレンジファインダー等の様々な他のセンサー（図示せず）を備える。いくつかの実施の形態では、システム１２００のいくつかの部分は、１つ以上のチップセット等の形態を取る。
【００８０】
プロセッサ１２５０は、ハードウェア、ファームウェア、およびソフトウェアの組み合わせを用いて実施することができる。プロセッサ１２５０は、センサーフュージョンおよび／または融合した測定値を更に処理するための方法に関連付けられる計算手順またはプロセスの少なくとも一部を実行するように構成可能な１つ以上の回路を表すことができる。プロセッサ１２５０は、メモリ１２６０から命令および／またはデータを引き出す。プロセッサ１２５０は、１つ以上の特定用途向け集積回路（ＡＳＩＣ）、中央および／またはグラフィカル処理ユニット（ＣＰＵおよび／またはＧＰＵ）、デジタルシグナルプロセッサ（ＤＳＰ）、デジタル信号処理デバイス（ＤＳＰＤ）、プログラマブル論理デバイス（ＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、コントローラー、マイクロコントローラー、マイクロプロセッサ、埋め込みプロセッサコア、電子デバイス、本明細書において記述される機能を実行するように設計された他の電子ユニット、またはその組み合わせを用いて実現することができる。
【００８１】
メモリ１２６０は、プロセッサ１２５０の内部に、および／またはプロセッサ１２５０の外部に実装することができる。本明細書において使用されるときに、「メモリ」という用語は、任意のタイプの長期、短期、揮発性、不揮発性、または他のメモリを指しており、任意の特定のタイプのメモリもしくはメモリの数、またはメモリが記憶される物理媒体のタイプに制限されるべきではない。いくつかの実施の形態において、メモリ１２６０は、様々な実施の形態の実行を容易にするプログラムコードを保持する。
【００８２】
二次メモリは、例えば、プライマリメモリと同じ、または類似のタイプのメモリ、および／または、例えば、フラッシュ／ＵＳＢメモリドライブ、メモリカードドライブ、ディスクドライブ、光ディスクドライブ、テープドライブ、ソリッドステートドライブ、ハイブリッドドライブ等の１つ以上のデータストレージデバイスまたはシステムを含むことができる。いくつかの実施態様では、二次メモリは、リムーバブルメディアドライブ（図示せず）内の非一時的なコンピューター可読媒体を動作可能に受け入れ得るか、またはそれらに対し他の形で構成可能であり得る。いくつかの実施の形態では、非一時的なコンピューター可読媒体は、メモリ１２６０および／またはプロセッサ１２５０の一部を形成する。
【００８３】
図１３Ａは、本発明の１つの実施の形態による、マイクロロボット１３２０の密度のマルチエージェント制御の例を示す。ロボットは、自身の状態１３３０を判断し、マルチエージェント制御システム１３１０に送信する。状態１３３０は、内蔵のＧＰＳデバイスを用いて判断することができる。状態を用いて、システム１３１０は、制御入力１３４０を決定し、モバイルロボットに送信する。送信は、制御入力と状態の対応するセクションとの対を含むことができる。モバイルロボットは、自身の状態を含む、セクションと対にされた自身の制御入力を選択し、選択された制御入力に従って制御運動を実行する。状態入力および制御入力は、送受信機１２７０等の様々な種類の送受信機を用いて交換することができる。この例において、状態は、モバイルロボットの位置、速度および／または向きを含む。モバイルロボットの状態は、ＩＭＵ１２３０またはセンサー１２１０を用いて判断することができる。制御入力は、新たな状態、例えば、モバイルロボットの新たな位置、モバイルロボットが辿る軌道および／またはモバイルロボットのアクチュエーターのためのコマンドを含むことができる。
【００８４】
図１３Ｂは、本発明の別の実施の形態による、エージェント１３２１の密度のマルチエージェント制御の例を示す。この例において、状態空間は、エージェント１３２１の分布の姿勢の配置を定義する回転行列の空間である。この場合、状態１３３１は、ＩＭＵ１２３０の一部とすることができる内蔵のジャイロスコープによって判断することができる。最適な輸送が計算され、姿勢制御情報１３４２は、例えば、無線送信機を介して中継によりエージェントに返される。
【００８５】
図１４は、本発明の１つの実施の形態による、エージェント１４５０の密度のマルチエージェント制御の別の例を示す。この例において、マルチエージェント制御システムは、複雑な流体流１４６０において磁気粒子１４５０の密度を制御する。システムは、制御入力を決定するための中央コントローラー１４１０と、状態空間のその磁気粒子のセクションに対応する制御入力を適用するアクチュエーター１４２０とを備える。例えば、アクチュエーター１４２０は、磁場１４４０をエージェントに適用するための磁気アクチュエーターを含むことができる。磁場は、制御入力によって決定される。エージェントの状態は、撮像システム１４３０によって観察することができる。例えば、撮像システム１４３０は、磁気粒子の位置および／または密度を求めるのに適したカメラおよび／または任意の他のタイプのセンサーを含むことができる。
【００８６】
本発明の上記で説明した実施の形態は、多数の方法のうちの任意のもので実施することができる。例えば、実施の形態は、ハードウェア、ソフトウェアまたはそれらの組み合わせを用いて実施することができる。ソフトウェアで実施される場合、ソフトウェアコードは、単一のコンピューターに設けられるのかまたは複数のコンピューター間に分散されるのかにかかわらず、任意の適したプロセッサまたはプロセッサの集合体において実行することができる。そのようなプロセッサは、１つ以上のプロセッサを集積回路部品に有する集積回路として実装することができる。ただし、プロセッサは、任意の適したフォーマットの回路類を用いて実装することができる。
【００８７】
また、本発明の実施の形態は、例が提供された方法として実施することができる。この方法の一部として実行される動作は、任意の適切な方法で順序付けすることができる。したがって、動作が示したものと異なる順序で実行される実施の形態を構築することができ、これには、例示の実施の形態では一連の動作として示されたにもかかわらず、いくつかの動作を同時に実行することを含めることもできる。
【００８８】
請求項の要素を修飾する、特許請求の範囲における「第１」、「第２」等の序数の使用は、それ自体で、１つの請求項の要素の別の請求項の要素に対する優先順位も、優位性も、順序も暗示するものでもなければ、方法の動作が実行される時間的な順序も暗示するものでもなく、請求項の要素を区別するために、単に、ある特定の名称を有する１つの請求項の要素を、同じ（序数の用語の使用を除く）名称を有する別の要素と区別するラベルとして用いられているにすぎない。
【００８９】
本発明を好ましい実施の形態の例によって説明してきたが、本発明の趣旨および範囲内で様々な他の適応および変更を行うことができることは理解されたい。
【００９０】
したがって、添付の特許請求の範囲の目的は、本発明の真の趣旨および範囲内に入る全ての変形および変更を包含することである。
【図１】
2018073395.tif 000018
【図２】
2018073395.tif 000019
【図３】
2018073395.tif 000020
【図４】
2018073395.tif 000021
【図５】
2018073395.tif 000022
【図６】
2018073395.tif 000023
【図７Ａ】
2018073395.tif 000024
【図７Ｂ】
2018073395.tif 000025
【図７Ｃ】
2018073395.tif 000026
【図８】
2018073395.tif 000027
【図９Ａ】
2018073395.tif 000028
【図９Ｂ】
2018073395.tif 000029
【図９Ｃ】
2018073395.tif 000030
【図９Ｄ】
2018073395.tif 000031
【図１０Ａ】
2018073395.tif 000032
【図１０Ｂ】
2018073395.tif 000033
【図１１Ａ】
2018073395.tif 000034
【図１１Ｂ】
2018073395.tif 000035
【図１２】
2018073395.tif 000036
【図１３Ａ】
2018073395.tif 000037
【図１３Ｂ】
2018073395.tif 000038
【図１４】
2018073395.tif 000039
【外国語明細書】
2018073395.tif 000040
2018073395.tif 000041
2018073395.tif 000042
2018073395.tif 000043
2018073395.tif 000044
2018073395.tif 000045
2018073395.tif 000046
2018073395.tif 000047
2018073395.tif 000048
2018073395.tif 000049
2018073395.tif 000050
2018073395.tif 000051
2018073395.tif 000052
2018073395.tif 000053
2018073395.tif 000054
2018073395.tif 000055
2018073395.tif 000056
2018073395.tif 000057
2018073395.tif 000058
2018073395.tif 000059
2018073395.tif 000060
2018073395.tif 000061
2018073395.tif 000062
2018073395.tif 000063
2018073395.tif 000064
2018073395.tif 000065
2018073395.tif 000066
2018073395.tif 000067
2018073395.tif 000068
2018073395.tif 000069
2018073395.tif 000070
2018073395.tif 000071
2018073395.tif 000072
2018073395.tif 000073
2018073395.tif 000074
2018073395.tif 000075
2018073395.tif 000076
2018073395.tif 000077
2018073395.tif 000078
2018073395.tif 000079
2018073395.tif 000080
2018073395.tif 000081
2018073395.tif 000082
2018073395.tif 000083
2018073395.tif 000084
2018073395.tif 000085
2018073395.tif 000086
2018073395.tif 000087
2018073395.tif 000088
2018073395.tif 000089
2018073395.tif 000090
2018073395.tif 000091
2018073395.tif 000092
2018073395.tif 000093
2018073395.tif 000094
2018073395.tif 000095
2018073395.tif 000096
2018073395.tif 000097
2018073395.tif 000098
2018073395.tif 000099
2018073395.tif 000100
2018073395.tif 000101
2018073395.tif 000102
2018073395.tif 000103
2018073395.tif 000104