(57)【特許請求の範囲】
【請求項１】
複数のエージェントがネットワークに接続して通信するマルチエージェントシステムにおいて、
前記各エージェントは、
実行すべきタスクを認識するタスク認識手段と、
前記タスク認識手段の認識結果に基づいて、前記複数のエージェントのうち、自他のエージェントから、前記タスクの割当が可能な第１のエージェントを選定し、前記第１のエージェントとの通信が可能な場合に、前記第１のエージェントに対して前記タスクの割当処理を実行するタスク割当手段と、
前記第１のエージェントとの通信が不可能な場合に、前記自他のエージェントから、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する予測手段と
を具備するマルチエージェントシステム。
【請求項２】
前記タスク割当手段は、
前記予測手段により前記第２のエージェントを予測できない場合には、前記自他のエージェントから、通信が可能で、前記タスクの割当が可能な第３のエージェントを選定する請求項１に記載のマルチエージェントシステム。
【請求項３】
前記タスク割当手段は、
前記予測手段により前記第２のエージェントを予測された場合には、前記タスクの割当処理を終了する請求項１に記載のマルチエージェントシステム。
【請求項４】
前記タスク割当手段は、
前記自他の複数のエージェントとの通信により、前記タスクの割当が可能であるか否かの照会に対して応答したエージェントから前記第１のエージェントを選定し、
前記照会に対する応答がない場合には、前記タスクの割当処理を終了する請求項１から３のいずれか１項に記載のマルチエージェントシステム。
【請求項５】
前記予測手段は、エージェント間の通信接続確率を含む確率情報に基づいて、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１から４のいずれか１項に記載のマルチエージェントシステム。
【請求項６】
前記予測手段は、エージェント間の通信速度に基づいて、前記第１のエージェントに対して一定時間内に前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１から４のいずれか１項に記載のマルチエージェントシステム。
【請求項７】
前記予測手段は、他エージェントのタスク認識確率を含む確率情報に基づいて、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１から４のいずれか１項に記載のマルチエージェントシステム。
【請求項８】
前記予測手段は、他エージェントのタスク割当ルールに基づいて、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１から４のいずれか１項に記載のマルチエージェントシステム。
【請求項９】
前記予測手段は、全エージェント共通のタスク割当ルールに基づいて、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１から４のいずれか１項に記載のマルチエージェントシステム。
【請求項１０】
複数のエージェントがネットワークに接続して通信するマルチエージェントシステムに適用するタスク割当装置であって、
前記タスク割当装置は、１つのエージェントまたは複数のエージェントの全てに設けられており、
実行すべきタスクを認識するタスク認識手段と、
前記タスク認識手段の認識結果に基づいて、前記複数のエージェントのうち、自他のエージェントから前記タスクの割当が可能な第１のエージェントを選定し、前記第１のエージェントとの通信が可能な場合に、前記第１のエージェントに対して前記タスクの割当処理を実行するタスク割当手段と、
前記第１のエージェントとの通信が不可能な場合に、前記自他のエージェントから、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する予測手段と
を具備するタスク割当装置。
【請求項１１】
前記予測手段は、全エージェント共通のタスク割当ルールに基づいて、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１０に記載のタスク割当装置。
【請求項１２】
前記予測手段は、エージェント間の通信接続確率を含む確率情報に基づいて、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する請求項１０に記載のタスク割当装置。
【請求項１３】
複数のエージェントがネットワークに接続して通信するマルチエージェントシステムに適用するタスク割当方法であって、
実行すべきタスクを認識する処理と、
前記タスクの認識結果に基づいて、前記複数のエージェントのうち、自他のエージェントから前記タスクの割当が可能な第１のエージェントを選定する処理と、
前記第１のエージェントとの通信が可能な場合に、前記第１のエージェントに対して前記タスクの割当処理を実行する処理と、
前記第１のエージェントとの通信が不可能な場合に、前記自他のエージェントから、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する処理と
を具備するタスク割当方法。
【請求項１４】
複数のエージェントがネットワークに接続して通信するマルチエージェントシステムに適用し、前記複数のエージェントを組み込むコンピュータにおいて、
実行すべきタスクを認識する処理と、
前記タスクの認識結果に基づいて、前記複数のエージェントのうち、自他のエージェントから前記タスクの割当が可能な第１のエージェントを選定する処理と、
前記第１のエージェントとの通信が可能な場合に、前記第１のエージェントに対して前記タスクの割当処理を実行する処理と、
前記第１のエージェントとの通信が不可能な場合に、前記自他のエージェントから、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する処理と
を有する手順を前記コンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、マルチエージェントシステム、当該システムに適用するタスク割当装置、タスク割当方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ネットワークを介して複数のエージェント間で相互に通信し、連携して各種のタスク（プロセス）を実行するマルチエージェントシステムの活用が注目されている。例えば、複数のドローン（drone：無人航空機）を制御する制御システムにおいて、マルチエージェントシステムを適用して、各ドローンを連携して制御する連携機能を実現できる。
【０００３】
一般的に、エージェントは、状況（環境）をセンシングし、センシング情報に基づいて実行すべきタスクを認識し、自律的な判断によりリソース（コンピュータのリソース）を使用して当該タスクを実行する。
【０００４】
ここで、マルチエージェントシステムでは、各エージェント間の通信により、例えば各ドローンを制御するためのタスクを各エージェントに割り当てる（分配する）タスク割当（分配）機能が含まれている。タスク割当機能の実現方法には、各エージェント同士が、ネットワークを介した通信機能を使用して情報交換を実行することにより、適切なエージェントへタスク割当をする方法（契約ネットプロトコル）がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−５２６８３号公報
【特許文献２】特開２００２−２２８３９６号公報
【特許文献３】国際公開ＷＯ２００６/１１８１９３号公報
【特許文献４】特開２００９−５５４０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
マルチエージェントシステムでは、各エージェント間の通信により、タスク割当機能が実現されている。各エージェント間の通信が不安定化した場合には、一時的に通信ができない状態や、通信に要する時間が増大して通信効率が低下する状態が発生することがある。
【０００７】
このような場合、１つのタスクに複数のエージェントが重複して担当する事態や、当該タスクを担当するエージェントを特定できない事態など、タスク割当（タスク分配）が実行できない、又は、一定時間（有効時間）内に実行できない可能性がある。
【０００８】
そこで、各エージェント間の通信が不安定化した場合でも、タスク割当を適切に実行できるマルチエージェントシステムを実現するという課題がある。
【課題を解決するための手段】
【０００９】
本実施形態は、複数のエージェントがネットワークに接続して通信するマルチエージェントシステムにおいて、前記各エージェントは、タスク認識手段と、タスク割当手段と、予測手段とを具備する。前記タスク認識手段は、実行すべきタスクを認識する。前記タスク割当手段は、前記タスク認識手段の認識結果に基づいて、自他のエージェントから前記タスクの割当が可能な第１のエージェントを選定し、前記第１のエージェントとの通信が可能な場合に、前記第１のエージェントに前記タスクの割当を実行する。前記予測手段は、前記第１のエージェントとの通信が不可能な場合に、他のエージェントから、前記第１のエージェントに対して前記タスクの割当を行う可能性が高い第２のエージェントを予測する。
【図面の簡単な説明】
【００１０】
【図１】実施形態に関するマルチエージェントシステムの構成を説明するためのブロック図。
【図２】実施形態に関するマルチエージェントシステムの動作を説明するためのフローチャート。
【図３】実施形態に関するネットワークマップ情報の一例を示す図。
【図４】実施形態に関する他エージェントタスク認識性能情報の一例を示す図。
【図５】実施形態に関する他エージェントタスク割当ルールの一例を示す図。
【図６】実施形態に関するタスク割当処理の一例を説明するための模式図。
【図７】実施形態に関するタスク割当処理の一例を説明するための模式図。
【発明を実施するための形態】
【００１１】
以下図面を参照して、実施形態を説明する。
［システムの構成］
図１は、本実施形態に関するマルチエージェントシステムの構成を示す図である。本システムは、ネットワーク２に接続された複数のコンピュータ１-1〜１-Nにおいて、各エージェント１０-1〜１０-Nが相互に通信し、後述するタスク割当（タスク分配）機能を含む構成である。
【００１２】
本実施形態に関するマルチエージェントシステムは、例えば、複数のドローンを制御する制御システムに適用され、各エージェント１０-1〜１０-Nがそれぞれ、各ドローンを連携して制御する。なお、エージェント１０-1〜１０-Nは、便宜的にエージェントＡ，Ｂ，Ｃ，Ｄ等のように表記する場合がある。即ち、エージェント１０-1がエージェントＡ（親エージェント）に相当する場合、他の複数のエージェント（他エージェント）１０-NがエージェントＢ，Ｃ，Ｄ等に相当する。
【００１３】
本実施形態では、図１に示すように、エージェント１０-1〜１０-Nは、基本的に同一の内部構成を有する。以下、エージェント１０-1を代表として内部構成を説明し、他のエージェントの内部構成の説明を省略する。
【００１４】
エージェント１０-1は、各機能１１〜１４，１７を実現するソフトウェアモジュール及びデータベース（情報）１５，１６，１８〜２０を有する構成である。エージェント１０-1は、タスク割当部１１、タスク認識部１２、センシング部１３、タスク実行部１４及び他エージェントタスク割当予測部（以下、タスク割当予測部と表記する）１７を有する。
【００１５】
タスク割当部１１は、実行すべきタスク（便宜的にタスクＸとする）を、タスク割当ルールデータベース（以下、データベースをＤＢと表記する）１５及び他エージェントタスク割当ＤＢ１６を参照し、他エージェント１０-Nに対するタスクＸを割り当てる（分配する）タスク割当処理を実行する。
【００１６】
タスク割当ルールＤＢ１５は、エージェント１０-1（エージェントＡ）がタスク割当処理を実行する際のタスク割当ルール（図５に記載のいずれかのタスク割当ルール）を示す情報である。また、他エージェントタスク割当ＤＢ１６は、いわゆる契約ネットプロトコルに基づいてタスク割当処理を行う際の履歴情報である。この履歴情報は、通信により他エージェントと情報交換を行った際のタスク割当処理に関する情報である。
【００１７】
タスク認識部１２は、センシング部１３のセンシング情報に基づいて、実行すべきタスクＸを認識し、タスク割当部１１に通知する。センシング部１３は、マルチエージェントシステムが適用される、例えば、複数のドローンを連携して制御する際の状況（環境）をセンシング（検出）する。具体例としては、センシング部１３は、例えば、レーダ３０-1と通信し、レーダ３０-1からの探知信号に応じて所定の検出処理（例えば、複数のドローンの位置等の飛行状況）を実行する。タスク認識部１２は、センシング情報に基づいて、例えば指定のドローンを制御するためのタスクＸを認識する。
【００１８】
タスク実行部１４は、タスク割当部１１により割り当てられるタスクを実行する。ここで、エージェント１０-1（エージェントＡ）は、タスク割当部１１により、エージェントＡに割り当てたタスク、又は、他エージェント１０-Nから割り当てられるタスクを実行する。具体例としては、タスク実行部１４は、ドローン制御システムにおいて、各ドローンを制御するコントローラ３１-1と通信し、割り当てられたタスク（例えば制御プロセス）を当該コントローラ３１-1に実行させる。なお、コントローラ３１-1は、制御対象の機器のアクチュエータでもよい。
【００１９】
タスク割当予測部１７は、タスク割当部１１と連携し、他エージェント１０-Nから、該当するエージェント（ここではＢ）に対してタスクＸを割り当てる可能性のあるエージェントを予測する。エージェントＢは、タスク割当部１１の通常のタスク割当処理によりタスクＸが割り当てられたエージェントであり、その後にエージェントＡとの通信ができない状態である。
【００２０】
タスク割当予測部１７は、後述するように、ネットワークマップＤＢ１８、他エージェントタスク認識性能ＤＢ１９、及び他エージェントタスク割当ルールＤＢ２０を参照し、予測処理を実行する。なお、各エージェント１０-1〜１０-Nはそれぞれ、タスク割当ルールＤＢ１５のタスク割当ルールが同一内容であれば、他エージェントタスク割当ルールＤＢ２０を共有する必要はない。
［タスク割当処理］
図２は、本実施形態のタスク割当処理を説明するためのフローチャートである。図２のフローチャートを参照して、本実施形態のタスク割当処理を説明する。
【００２１】
本実施形態では、便宜的に、エージェント１０-1をエージェントＡとし、他エージェント１０-NをエージェントＢ，Ｃ，Ｄ等とする。エージェントＡは、他エージェントＢ，Ｃ，Ｄ等に対してタスク割当を行う親エージェントとする。
【００２２】
図２に示すように、エージェントＡにおいて、タスク認識部１２は、センシング部１３のセンシング情報に基づいて、タスクＸの実行必要性（換言すれば実行すべきタスクＸ）を認識する（ステップＳ１）。具体的には、センシング情報は、例えば、レーダ３０-1からの探知信号に応じて検出される複数のドローンの位置等の飛行状況を示す情報である。
【００２３】
タスク割当部１１は、他エージェントタスク割当ＤＢ１６を参照し、他エージェントＢ，Ｃ，Ｄ等の中で、既にタスクＸの割当処理を開始していることを認識すると、当該タスク割当処理を終了する（ステップＳ２のＹＥＳ）。ここで、エージェントＡは、エージェント間の通信での情報交換により、他エージェントＢ，Ｃ，Ｄ等がタスク割当処理を実行した場合の履歴情報を、他エージェントタスク割当ＤＢ１６として保持している。即ち、当該履歴情報は、いわゆる契約ネットプロトコルに基づいてタスク割当処理を行う際の情報である。
【００２４】
タスク割当部１１は、他エージェントによりタスクＸの割当処理が開始されていない場合（ステップＳ２のＮＯ）、エージェント間の通信により、他エージェントＢ，Ｃ，Ｄ等に対してタスクＸの担当可能性（換言すれば、タスクＸの実行可能性）を問い合わせる（ステップＳ３）。この問い合わせ（照会）に対して、いずれのエージェントからも応答がない場合（ステップＳ４のＮＯ）、タスク割当部１１は、他エージェントＢ，Ｃ，Ｄ等に対するタスク割当処理を終了すると共に、例えば、当該タスクＸを自身のタスク実行部１４により実行する。なお、タスク割当部１１は、自身のタスク実行部１４により実行する以外の他の処理を実行してもよい。
【００２５】
一方、問い合わせに対して、一定時間（有効時間）内に応答した他エージェントがある場合（ステップＳ４のＹＥＳ）、タスク割当部１１は、タスク割当ルールＤＢ１５を参照し、予め設定したタスク割当ルールに基づいて、割当対象として最適であると判定したエージェントＢを選択する（ステップＳ５）。具体例としては、図５に示すようなタスク割当ルールである。
【００２６】
タスク割当部１１は、選択したエージェントＢとの間で一定時間内での通信が可能、即ち、通信が維持できている場合（ステップＳ６のＹＥＳ）、当該エージェントＢに対してタスクＸの割当通知を行う（ステップＳ７）。これにより、エージェントＢは、エージェントＡから割り当てられたタスクＸをタスク実行部１４により実行する。具体例としては、エージェントＢは、例えば、ドローンを制御するコントローラ３１-Nと通信し、割り当てられたタスク（例えば制御プロセス）Ｘを実行させる。
【００２７】
ここで、タスク割当部１１は、選択したエージェントＢとの間で一定時間内での通信が不可、即ち、通信が不安定な場合（ステップＳ６のＮＯ）、タスク割当予測部１７と連携する。タスク割当予測部１７は、ネットワークマップＤＢ１８、他エージェントタスク認識性能ＤＢ１９、及び他エージェントタスク割当ルールＤＢ２０を参照し、他エージェントがエージェントＢに対してタスクＸを割り当てるか否かを予測する予測処理を実行する（ステップＳ８）。
【００２８】
具体的には、タスク割当予測部１７は、ネットワークマップ情報、他エージェントタスク認識性能情報、及び他エージェントタスク割当ルールに基づいて、各条件の確率の乗算結果と基準値を比較し、基準値を超えているエージェントＣがエージェントＢに対してタスクＸを割り当てる可能性が高いと予測する。要するに、タスク割当予測部１７は、タスクを割り当てる可能性を示す確率情報に基づいて、エージェントＣがエージェントＢに対してタスクＸを割り当てる可能性が高いと予測する。
【００２９】
ここで、ネットワークマップＤＢ１８は、図３に示すようなネットワークマップ情報を含み、具体的には各アーク（エージェント間の通信接続）の通信状態の情報である。特に、接続確率は、エージェント間の通信が無線通信の場合に変動が大きい。このネットワークマップ情報は、定期的にエージェント間の情報交換により取得される。他エージェントタスク認識性能ＤＢ１９は、図４に示すような他エージェントタスク認識性能情報を含む。この情報は、センシング性能に依存する情報であり、例えば、レーダ３０-Nの設置位置や探知距離などに基づいている。他エージェントタスク割当ルールＤＢ２０は、図５に示すようなタスク割当ルールを含む。なお、各エージェントのタスク割当ルールＤＢ１５のタスク割当ルールが同一内容であれば、他エージェントタスク割当ルールＤＢ２０を共有する必要はない。
【００３０】
図２に戻って、タスク割当予測部１７は、エージェントＣが一定時間内にエージェントＢと通信して、エージェントＢにタスクＸを割り当てる可能性が高いと予測した場合（ステップＳ９のＹＥＳ）には、タスク割当部１１に通知する。これにより、タスク割当部１１は、当該タスク割当処理を終了する。
【００３１】
タスク割当部１１は、タスク割当予測部１７によりエージェントＢにタスクＸを割り当てる可能性が高いエージェントを予測できない場合（ステップＳ９のＮＯ）には、再度、エージェントＢ以外で、一定時間内に通信可能な他エージェントを選定する。即ち、タスク割当部１１は、タスク割当ルールＤＢ１５を参照し、予め設定したタスク割当ルールに基づいて、割当対象として最適であると判定したエージェントＤを選択する（ステップＳ１０）。
【００３２】
タスク割当部１１は、選択したエージェントＤとの間で一定時間内での通信が可能、即ち、通信が維持できている場合には、当該エージェントＤに対してタスクＸの割当通知を行う（ステップＳ１１）。これにより、エージェントＤは、エージェントＡから割り当てられたタスクＸをタスク実行部１４により実行する。
【００３３】
以上のような本実施形態のタスク割当処理について、図６及び図７の模式図を参照して作用効果を説明する。
【００３４】
先ず、エージェントＡは、タスクＸの割当対象としてエージェントＢを選択した後に、エージェントＡ，Ｂ間で通信が可能であれば、エージェントＢにタスクＸの割当処理を実行して終了する。ここで、図６に示すように、エージェントＡ，Ｂ間で通信ができない状態（６０）が発生すると、タスク割当予測部１７により、エージェントＣが一定時間（有効時間）内にエージェントＢと通信し（６１）、タスクＸを割り当てる可能性が高いと予測した場合、タスク割当部１１は何も実行せずに終了となる。ここで、エージェントＡは、予測されたエージェントＣとは通信できない状態である。
【００３５】
即ち、エージェントＡ，Ｂ間の通信が不安定な場合に、エージェントＡは、エージェントＢにタスクＸを割り当てる可能性が高いエージェントＣを予測した場合、タスク割当部１１は何も実行せずに終了となる。
【００３６】
従って、同じタスクＸを複数のエージェントが重複して担当して、コンピュータのリソースが無駄になるような事態を回避できる。また、同じタスクＸを複数のエージェントが重複して担当すると、各エージェントは他のタスク実行にリソースを配分することができなくなる事態となるが、このような事態を回避できる。これにより、各エージェント間の通信が不安定化した場合でも、タスク割当（タスク分配）を適切に実行できる。
【００３７】
さらに、図７に示すように、エージェントＢ，Ｃ間で通信ができない状態（６２）で、一定時間内にエージェントＢにタスクＸを割り当てる可能性が高いエージェントＣを予測できない場合、タスク割当部１１は、再度、タスクＸの割当対象としてエージェントＤを選択する処理を実行する。エージェントＡは、エージェントＡ，Ｄ間で一定時間（有効時間）内での通信が可能であれば、エージェントＤにタスクＸの割当処理を実行して終了する。従って、各エージェント間の通信が不安定化した状態が発生している場合でも、タスクＸを担当可能なエージェントを特定できない事態を回避できる。
【００３８】
なお、本実施形態では、タスク割当予測部１７及び各ＤＢ１８−２０は、各エージェントに設けられている構成について説明したが、エージェントＡのみに設けられている構成でもよい。
【００３９】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００４０】
１-1〜１-N…コンピュータ、２…ネットワーク、１０-1〜１０-N…エージェント、
１１…タスク割当部、１２…タスク認識部、１３…センシング部、
１４…タスク実行部、１５…タスク割当ルールデータベース（ＤＢ）、
１６…他エージェントタスク割当ＤＢ、１７…他エージェントタスク割当予測部、
１８…ネットワークマップＤＢ、１９…他エージェントタスク認識性能ＤＢ、
２０…他エージェントタスク割当ルールＤＢ、３０-1〜３０-N…レーダ、
３１-1〜３１-N…コントローラ。
【図１】
0006739972.tif 000002
【図２】
0006739972.tif 000003
【図３】
0006739972.tif 000004
【図４】
0006739972.tif 000005
【図５】
0006739972.tif 000006
【図６】
0006739972.tif 000007
【図７】
0006739972.tif 000008