(57)【要約】【課題】分散型の運航管理システムにおいて、非効率な領域割当の改善に寄与する。【解決手段】本発明の領域管理システム５００は、自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出するもつれ検出手段５０１と、もつれ検出手段５０１による検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する情報出力手段５０２とを備える。【選択図】図２２
2019007832.tif 000002
【特許請求の範囲】
【請求項１】
自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、前記ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの前記移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出するもつれ検出手段と、
前記もつれ検出手段による検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する情報出力手段とを備えた
ことを特徴とする領域管理システム。
【請求項２】
前記もつれ検出手段は、前記運航計画の各々に対する前記経路改善度および／またはそれらに基づいて算出される選択ユーザごとの運航改善度が所定の条件を満たす場合に、もつれを検出するとともに、前記条件を満たした運航経路を改善案として検出する
請求項１に記載の領域管理システム。
【請求項３】
前記もつれ検出手段は、選択ユーザの全てで前記運航改善度が０以上であり、かつ選択ユーザの少なくとも一部で前記運航改善度がプラスである場合に、もつれを検出する
請求項２に記載の領域管理システム。
【請求項４】
前記もつれ検出手段は、選択ユーザの全てで前記運航改善度がプラスである場合に、もつれを検出する
請求項２に記載の領域管理システム。
【請求項５】
前記もつれ検出手段は、選択ユーザの全てで前記運航改善度がプラスであり、かつ選択ユーザによる運航計画の全てで前記経路改善度が０以上である場合に、もつれを検出する
請求項２に記載の領域管理システム。
【請求項６】
前記情報出力手段は、もつれが検出された場合に、少なくとも１つの改善案の情報と、前記改善案での前記運航改善度とを含む情報を出力する
請求項２から請求項５のうちいずれかに記載の領域管理システム。
【請求項７】
前記情報出力手段は、もつれが検出された場合に、所定の基準に基づいて改善案を評価した結果に基づいて、ランキング形式で、少なくとも１つの改善案の情報と、前記改善案での前記運航改善度とを含む情報を出力する
請求項２から請求項６のうちいずれかに記載の領域管理システム。
【請求項８】
前記情報出力手段は、もつれが検出された場合に、改善案により特定される選択ユーザ間で交換対象とされる占有領域の情報と、交換後のユーザの運航改善度とを含む情報を出力する
請求項２から請求項７のうちいずれかに記載の領域管理システム。
【請求項９】
前記もつれ検出手段は、選択ユーザの占有領域を解放したときの非占有領域を用いて、前記運航計画の集合に対して、所定の探索時間範囲内において占有領域の排他条件を満たす運航経路の組み合わせであるパスセットを全て探索し、探索された全てのパスセットについて算出した前記運航経路の各々に対する前記経路改善度を基に、もつれを検出する
請求項１から請求項８のうちのいずれかに記載の領域管理システム。
【請求項１０】
前記もつれ検出手段は、選択ユーザの占有領域を解放したときの非占有領域を用いて、前記運航計画の集合に対して、所定の探索時間範囲内において時刻の小さい順に遷移可能状態を列挙していく際に、予測される到着時間が短いものを選択して遷移可能状態を列挙していった結果、占有領域の排他条件を満たす運航経路の組み合わせであって前記所定の条件を満たすパスセットが探索された場合に、もつれを検出する
請求項１から請求項８のうちのいずれかに記載の領域管理システム。
【請求項１１】
前記もつれ検出手段は、ダイクストラ法またはＡスター法を利用して、前記パスセットを探索する
請求項９または請求項１０に記載の領域管理システム。
【請求項１２】
情報処理装置が、
自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、前記ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの前記移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出し、
もつれの検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する
ことを特徴とする領域管理方法。
【請求項１３】
コンピュータに、
自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、前記ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの前記移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出するもつれ検出処理、および
前記もつれ検出処理での検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する情報出力処理
を実行させるための領域管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体の運航に用いられる領域を管理する領域管理システム、領域管理方法、領域管理プログラムに関する。
【背景技術】
【０００２】
ドローンなどの無人航空機（Unmanned Aircraft System，ＵＡＳ）を空輸等に活用することが検討されている。ＵＡＳの活用のためには、ＵＡＳの運航計画およびそれに用いられる領域を管理する機構が必要となる。そこで、そのようなＵＡＳの運航管理（UAS Traffic Management，ＵＴＭ）の方法が種々検討されている。
【０００３】
ＵＡＳの運航を管理する運航管理システムに関連する技術として、例えば、特許文献１に記載された技術がある。
【０００４】
特許文献１に記載の技術は、自動無人搬送車（Automated Guided Vehicle，ＡＧＶ）がそれぞれに経路計画を作成した上で、情報の授受と各ＡＧＶでの再経路探索を複数回繰り返して実行する。このような方法により、他のＡＧＶとの衝突や干渉に関する不整合な経路計画に関するペナルティ関数の重み係数を各ＡＧＶで次第に増加させて、不整合な経路計画を分散協調的に解消できるとされている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−２８０２１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＵＡＳに限らず移動体の運航を管理する運航管理システムの一例として、多数の移動体の運航計画やその運航に用いられる領域を１つの管制システムが集中して管理する集中型の運航管理システムが考えられる。しかし、当該方法は承認要求が大量に積み重なると、各運航計画の整合性を考慮しつつ迅速に承認を行うのが困難であるとともに、障害時に全ての運航が停止してしまう等の問題があり、好ましくない。
【０００７】
そこで、分散型の運航管理システムを考える。具体的には、複数の運航管理システムのそれぞれに、割り当てた領域に対する移動体の運航計画の承認権限を委譲し、各運航管理システムが、自身に割り当てられた領域内において各移動体の運航を管理する分散型の運航管理システムを考える。
【０００８】
このような分散型の運航管理システムによれば、各運航管理システムに排他的に領域を割り当てることにより、異なる運航管理システム間で移動体のコンフリクトを回避しつつ、運航計画の承認処理を各運航管理システムが独立して行うことができるので、上記の問題を回避できる。
【０００９】
しかし、各運航管理システムが自身が管理する移動体の運航計画に基づいて自立的に領域を申請して該領域に対する承認権限を得る場合、複数の運航管理システムにとって非効率な領域割当になる可能性がある。このような非効率な領域割当があった場合には、複数の運航管理システムにとってメリットのある解の情報を提供するなどして、改善に寄与できることが望ましい。
【００１０】
なお、特許文献１に記載の方法は、各ＡＧＶが単独で計画した経路計画の実行不可能性を無くすために分散計算をさせて、全体最適を行おうというものであって、上記のような非効率な領域割当があった場合に、複数の運航管理システムにとってメリットのある解の情報を提供するものではない。例えば、特許文献１に記載の方法における再経路計画は、移動体が単体で計画した最短経路に対して、他の移動体との衝突を回避するために行われるものであって、そのような移動体の運航管理は、上記の分散型の運航管理システムでは各運航管理システムの範疇である。これに対して、分散型の運航管理システムにおける再経路計画では、各運航管理システムが自身に割り当てられた領域内において最適化された既存の経路と比較して、領域割当の変更によって、複数の運航管理システムにとってより良い経路を発見することが要求される。
【００１１】
そこで、本発明は、分散型の運航管理システムにおいて、非効率な領域割当の改善に寄与できる領域管理システム、領域管理方法、領域管理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明による領域管理システムは、自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出するもつれ検出手段と、もつれ検出手段による検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する情報出力手段とを備えたことを特徴とする。
【００１３】
本発明による領域管理方法は、情報処理装置が、自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出し、検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力することを特徴とする。
【００１４】
本発明による領域管理プログラムは、コンピュータに、自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出するもつれ検出処理、およびもつれ検出処理での検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する情報出力処理を実行させることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、分散型の運航管理システムにおいて、非効率な領域割当の改善に寄与できる。
【図面の簡単な説明】
【００１６】
【図１】領域管理システム１０を含む移動体運航システム１００の概略構成図である。
【図２】領域管理システム１０の構成例を示すブロック図である。
【図３】管理対象領域の分類を示す説明図である。
【図４】もつれの発生例を示す説明図である。
【図５】もつれの判定例を示す説明図である。
【図６】領域管理システム１０の動作の一例を示すフローチャートである。
【図７】領域変更に伴う経路長の改善度を用いたもつれの検出例を示す説明図である。
【図８】領域のイメージ図である。
【図９】領域のイメージ図である。
【図１０】領域の占有状態と移動体の移動の例を示す説明図である。
【図１１】もつれ判定アルゴリズムにおける空域の表現例を示す説明図である。
【図１２】グラフ表現された空域群に対する移動体の移動ルールを示す説明図である。
【図１３】遷移可能状態の抽出アルゴリズムの疑似コードを示す説明図である。
【図１４】遷移可能状態の導出例を示す説明図である。
【図１５】第１例のもつれ判定アルゴリズムの疑似コードを示す説明図である。
【図１６】運航計画における移動体Ｍ１および移動体Ｍ２のパスの例を示す説明図である。
【図１７】遷移可能状態の一例を示す説明図である。
【図１８】パスセットの一例を示す説明図である。
【図１９】第２例のもつれ判定アルゴリズムのパス探索例を示す説明図である。
【図２０】第２例のもつれ判定アルゴリズムの判定例を示す説明図である。
【図２１】本発明の実施形態にかかるコンピュータの構成例を示す概略ブロック図である。
【図２２】本発明の領域管理システムの概要を示すブロック図である。
【発明を実施するための形態】
【００１７】
実施形態１．
以下、本発明の実施形態を図面を参照して説明する。
【００１８】
図１は、本実施形態の領域管理システム１０を含む移動体運航システム１００の概略構成図である。図１に示すように、本実施形態の領域管理システム１０は、配下に、それぞれが自身に割り当てられた占有領域内において移動体の運航管理を行う運航管理システム２０が複数属していることを前提とする。その上で、領域管理システム１０は、運航管理システム２０からの領域申請に従って領域を割り当てるだけでなく、全体最適化のために、少なくとももつれの検出およびその改善のための情報提供を行う。
【００１９】
なお、運航管理システム２０への領域割当や、運航管理システム２０への領域割当状況を示す領域情報および各々の運航管理システム２０から報告される各移動体の運航計画を示す運航情報の管理等は別途行われるものとし、本実施形態ではこれらに関する情報が適宜参照可能であるとする。
【００２０】
移動体運航システム１００において、領域は、各々の運航管理システム２０に排他的に割り当てられるものとする。割り当て後の領域内における移動体の運航管理は、割当先の運航管理システム２０に委譲される。割当先の運航管理システム２０以外は、交渉して領域そのものを得ない限り、該領域を移動体の運航に使用することはできない。このような制約を運航管理システム２０の各々に課すことにより、異なる運航管理システム２０間での移動体のコンフリクトを回避する。
【００２１】
図２は、本実施形態の領域管理システム１０の構成例を示すブロック図である。図２に示す領域管理システム１０は、もつれ検出部１１と、改善情報出力部１２とを備える。
【００２２】
もつれ検出部１１は、複数の運航管理システム２０の各々に対して占有領域を割り当てた結果、非効率となっている領域割当を「もつれ」として検出する。もつれ検出部１１は、運航情報と領域情報とに基づいて、もつれを検出する。
【００２３】
ここで、「占有領域」は、いずれかのユーザが使用中または使用予定の領域であって、ユーザからの申請等により、その時間帯に対して当該ユーザに割り当てられる領域である。本実施形態では、自身に割り当てられた占有領域内において移動体の運航管理を行う運航管理システム２０またはその事業者を「ユーザ」と呼ぶ。
【００２４】
図３に示すように、領域管理システム１０の管理対象領域は、「利用可能領域」と「利用不可領域」とに大別される。また、「利用可能領域」は、さらに「占有領域」と「非占有領域」とに大別される。ここで、「利用可能領域」は、移動体の運航に利用できる領域である。「利用不可領域」は、建物や天候等の物理条件や緊急時の対応等で一般の移動体が運航に利用できない領域である。換言すると、「利用不可領域」は「利用可能領域」以外の領域である。また、「非占有領域」は、「利用可能領域」のうちいずれのユーザにも占有されていない領域である。「非占有領域」は、いずれかのユーザが予約すればその時間帯において該ユーザの「占有領域」となる。
【００２５】
領域情報は、例えば、取得可能な運航計画にかかる時間帯における管理対象領域の占有状況を示す情報を含む。領域情報は、例えば、所定の時間帯ごとの占有領域の割当状況（予約を含む）を示す情報であってもよい。
【００２６】
また、運航情報は、移動体の運航の出発位置と、到着位置と、出発時刻と、出発位置から到着位置までの運航経路の所定の評価指標またはそれを算出可能な情報とを含む。ここで「所定の評価指標」は、本システムにおける改善したいものに対応する。一例として、到着時刻、経路長、移動距離、移動所要時間、消費エネルギ、経路上の各点における障害物との距離およびそれらの組み合わせなどが挙げられる。なお、運航情報のデータ形式は予め定められているものとする。
【００２７】
本実施形態において、「もつれ」を、より具体的に「２以上のユーザを指定したときに、指定されたユーザに対する領域割当を変更することにより、これらユーザの全てで、現在登録されている移動体の運航計画に対して運航経路の改善が見込まれる状態」と定義してもよい。領域割当の変更は、例えば、占有領域の少なくとも一部を解放または他のユーザと交換することである。また、運航経路の改善は、具体的には、到着時刻、経路長、移動距離、移動所要時間、消費エネルギ、経路上の各点における障害物との距離およびそれらの組み合わせなどによって示される運航コストの改善であってもよい。
【００２８】
なお、「もつれ」の定義は、上記に限定されない。例えば、一部のユーザまたは一部の移動体にとって改善がない場合や不利益になる場合であっても、領域割当の変更により、現在登録されている移動体の運航計画に対して、移動体全体または選択されたユーザ全体で運航経路の改善が見込まれる場合は、該状態を「もつれ」として検出してもよい。
【００２９】
より単純に、「もつれ」を「ある指定された２以上のユーザの移動体の現在の運航計画に対して、該ユーザの占有領域の変更に伴う各移動体の運航経路の改善度および／または該改善度に基づくユーザの運航改善度が所定の条件を満たす状態」とすることも可能である。この場合、「所定の条件」の例として、「指定されたユーザについて、移動体の運航経路の改善度に基づくユーザ単位の運航改善度が全てプラスである」、「移動体全体での運航経路の改善度（合計）がプラスである」、「指定されたユーザ全体での運航改善度（合計）がプラスであって、かつ全ての移動体の運航経路の改善度が０以上である」等が挙げられる。ここで、「移動体の運航経路の改善度」および「ユーザの運航改善度」はマイナス値で悪化状態、ゼロで現状維持、プラス値で改善状態を表すものとする。
【００３０】
移動体の運航経路の改善度は、例えば、運航計画における移動コストと占有領域の変更後の移動コストの差であってもよい。また、ユーザの運航改善度は、該ユーザが管理する移動体の運航経路の改善度の合計や重み付け和であってもよい。
【００３１】
また、もつれ検出部１１は、もつれが検出された場合には、該もつれを解消するための各移動体の運航経路を示す１つ以上の改善案と、各改善案による運航改善度とを併せて検出する。
【００３２】
改善情報出力部１２は、もつれ検出部１１による検出結果に基づいて、現在の運航計画を改善するための情報（以下、改善情報という）を出力する。改善情報の例としては、改善案の情報や、各移動体の最適経路の情報が挙げられる。また、この他にも、改善情報出力部１２は、改善情報として、交換対象の領域の情報とその交換に伴うユーザの運航改善度とを出力してもよい。さらに、改善情報出力部１２は、改善案に対して、交渉の成立のしやすさ（例えば、ユーザの中で最小の運航改善度）や全体最適度合い（全ユーザの運航改善度の合計）、公平さ（ユーザ間の運航改善度の差（分散））などを評価し、ランキング形式等で出力することも可能である。また、改善情報出力部１２は、もつれ検出に用いたユーザ（選択ユーザ）のうちの一部のユーザに対してのみ、上記情報を出力することも可能である。もつれに関わるユーザに向けてこれらの情報を出力することで、ユーザに領域交渉の有意性を示唆することができる。
【００３３】
なお、図示省略しているが、領域管理システム１０は、領域情報および運航情報を保持する情報保持部や、領域情報および運航情報を受信するデータ受信部を備えていてもよい。
【００３４】
図４はもつれの発生例を示す説明図である。本例の前提として、各ユーザは、自身が管理する移動体について出発地と目的地（到着地）の情報を所持している。また、領域は悪天候などで利用不可になることがある。図４（ａ）〜図４（ｄ）は、このような前提の下、もつれが生じた例を示す。
【００３５】
図４（ａ）は、ある時刻における管理領域の状態を示す。図４（ａ）には、一部領域が利用不可であること、および、ユーザＡが管理する移動体である移動体Ｍ１と、ユーザＢが管理する移動体である移動体Ｍ２の出発地（Ｓｔａｒｔ）と目的地（Ｇｏａｌ）とが示されている。なお、図４（ａ）の時刻において、利用可能領域はいずれのユーザにも割り当てられていないものとする。
【００３６】
まずユーザＡが、移動体Ｍ１のその時点での最短経路にかかる領域を申請する。図４（ｂ）は、ユーザＡによる領域申請後の領域の割当状況を示す。
【００３７】
しばらくした後、天候が回復して利用不可領域が利用可能領域になったとする。図４（ｃ）は、天候回復後の領域の状態を示す。
【００３８】
次いで、ユーザＢが、移動体Ｍ２のその時点での最短経路にかかる領域を申請する。図４（ｄ）は、ユーザＢによる領域申請後の領域の割当状況を示す。図４（ｄ）の状態は、もつれが発生している状態である。
【００３９】
図５は、もつれの判定例を示す説明図である。図５（ａ）は、図４（ｄ）の状態をそのまま示している。この状態に対して、図５（ｂ）に示すように、ユーザＡとユーザＢの領域割当を変更すると、両ユーザの移動体の移動距離をともに短くできる。このような場合、図５（ａ）の状態は、もつれが生じていると判定されるとともに、図５（ｂ）の状態は、該もつれの改善案とされる。
【００４０】
このように、各ユーザが限られた情報の中で自身の利益を追求するだけでは、互いに損する状況になることがある。そこで、もつれが検知された場合に、図５（ｂ）に示すようなもつれを解消した状態を改善案としてユーザに提示するなどの情報提供を行うことにより、ユーザに領域交換を促す。
【００４１】
次に、本実施形態の領域管理システム１０の動作を説明する。図６は、本実施形態の領域管理システム１０の動作の一例を示すフローチャートである。図６に示す例では、まず、もつれ検出部１１が、ユーザを２以上選択する（ステップＳ１０１）。
【００４２】
次に、もつれ検出部１１は、選択したユーザの占有領域を解放したときの非占有領域を使って、該ユーザが管理する移動体の各運航について経路を探索する（ステップＳ１０２）。
【００４３】
次に、もつれ検出部１１は、現在の運航計画と探索結果とに基づいて、各移動体の運航経路の改善度を算出する（ステップＳ１０３）。
【００４４】
次に、もつれ検出部１１は、各移動体の運航経路の改善度が所定の条件を満たすか否かを判定する（ステップＳ１０４）。所定の条件を満たしている場合（ステップＳ１０４のＹｅｓ）、もつれ検出部１１は、もつれが発生していると判定する（もつれ検出）。このとき、もつれ検出部１１は、もつれの検出ともに、１つ以上の改善案と、各改善案による運航改善度とを併せて検出する（ステップＳ１０５）。
【００４５】
次に、改善情報出力部１２は、もつれ検出部１１の検出結果に基づいて改善情報を出力する（ステップＳ１０６）。
【００４６】
一方、各移動体の運航経路の改善度が所定の条件を満たしていない場合（ステップＳ１０４のＮｏ）、もつれ検出部１１は、領域割当によるもつれが発生していないと判定し、そのまま終了する。なお、このとき、もつれ検出部１１が、もつれが発生していない旨を出力してもよい。
【００４７】
次に、具体例を示しながらもつれの検出方法をより詳しく説明する。図７は、領域変更に伴う経路長の改善度を用いたもつれの検出例を示す説明図である。図中において、ｓｉは移動体Ｍ１の出発位置、ｇｉは移動体Ｍ２の到着位置を表す。今、ユーザＡが管理する移動体Ｍ１と、ユーザＢが管理する移動体Ｍ２と、ユーザＣが管理する移動体Ｍ３のそれぞれの運航経路が図７（ａ）の運航計画に示す状態であったとする。運航計画における移動体Ｍ１の経路長は１０、移動体Ｍ２の経路長は７、移動体Ｍ３の経路長は１０である。
【００４８】
このような運航計画に対して、もつれ検出部１１が、ユーザＡとユーザＢとを選択したとする（図７（ｂ））。図７（ｂ）には、ユーザＡおよびユーザＢの占有領域を解放したときの領域の状態が示されている。なお、白塗りの領域は非占有領域である。もつれ検出部１１は、移動体Ｍ１および移動体Ｍ２の運航計画に基づき、非占有領域を使用してそれぞれの運航経路を探索する（図７（ｃ））。ここでは、移動体Ｍ１について経路長が４の経路が発見され、移動体Ｍ２について経路長が３の経路が発見される。もつれ検出部１１は、移動体Ｍ１および移動体Ｍ２について、領域解放前後の経路長を比較し、いずれも短くなっていることからもつれを検出する。
【００４９】
次に、もつれ判定アルゴリズムの具体例をいつくか提示する。以下では、移動体の例としてドローンを例示するが、移動体はドローンに限定されない。
【００５０】
図８および図９は、本例の領域のイメージ図である。図８に示すように、本例では、移動体の運航に用いる領域として３次元の空間を想定する。その上で、該３次元の空間を所定の管理単位に分割したものを、「領域」（「空域」）の１単位として定義する。各空域は、ユーザに排他的に割り当てられる。
【００５１】
また、図９に示すように、空域は時間毎に割り当てられ、各ユーザは自身に割り当てられた空域の中から、ドローンが現在位置する空域に対して隣接する空域を広げてルートを形成する。以下では、説明を簡単にするため、移動体の運航経路として２次元に拡がる空域を例示するが、該経路が３次元に拡がる空域にも適用可能であることは当業者であれば容易に想像されるであろう。なお、移動体が２次元的に移動する車等であれば、移動体の運航に用いる領域として２次元の空間を想定し、該２次元の空間を所定の管理単位に分割したものを「領域」の１単位として定義することも可能である。
【００５２】
また、図１０は、領域の占有状態と移動体の移動の例を示す説明図である。図１０（ａ）は本例の移動にかかる空域の２次元配置を示す説明図である。図１０（ａ）には、領域ａ１〜領域ａ４という４つの空域が示されている。なお、本図に示すように、領域ａ１と領域ａ２と領域ａ４が、図中＋Ｘ方向に直線上に繋がっており、その迂回路として領域ａ２の＋Ｙ方向に領域ａ３が隣接している。
【００５３】
また、図１０（ｂ）は各領域の割当状況を示す表であり、図１０（ｃ）は当該領域配置における移動体の移動例を示す説明図である。図１０（ｃ）において、空域内の丸印はドローンを表し、中の数字はドローンの識別子を表す。なお、丸印の１は、ユーザＡが管理するドローン（移動体Ｍ１）であり、丸印の２はユーザＢが管理するドローン（移動体Ｍ２）である。図１０（ｂ）および図１０（ｃ）に示すように、１つの空域に異なるユーザが管理するドローンは侵入できない。また、空域を跨ぐ時刻を厳密に制御できないことを考慮して、１つ前の時刻でドローンが存在して現在時刻で該ドローンが他の空域に移動している場合も、その空域（１つ前の時刻でドローンが存在した空域）に他のユーザのドローンは入れないものとする。なお、図１０では、各ドローンが単位時間あたりに１つの空域を進む例を示しているが、ドローンの移動速度は本例に限定されない。
【００５４】
図１０（ｃ）に示すように、時刻ｔ＝０において、移動体Ｍ１が領域ａ１、移動体Ｍ２が領域ａ４にいたとする。このとき、領域ａ１はユーザＡの占有領域であり、領域ａ４はユーザＢの占有領域である。なお、移動体Ｍ１の目的位置は領域ａ１であり、移動体Ｍ２の目的位置は領域ａ４である。
【００５５】
時刻ｔ＝１で、ユーザＡは、領域ａ２を自身の占有領域とした上で移動体Ｍ１を領域ａ２に進める。ユーザＢは、領域ａ２がユーザＡの占有領域となっているため、移動体Ｍ２を領域ａ２に進めることができず、領域ａ４に留めておく。
【００５６】
時刻ｔ＝２で、ユーザＡは、領域ａ４がユーザＢの占有領域となっているため、領域ａ３を自身の占有領域とした上で移動体Ｍ１を領域ａ３に迂回させる。ユーザＢは、領域ａ２がまだユーザＡの占有領域となっているため、移動体Ｍ２を領域ａ４に留めておく。
【００５７】
時刻ｔ＝３で、ユーザＡは、領域ａ４がまだユーザＢの占有領域となっているため、移動体Ｍ１を領域ａ３に留めておく。ユーザＢは、領域ａ２が解放されたため、領域ａ２を自身の占有領域とした上で移動体Ｍ２を領域ａ２に移動させる。
【００５８】
時刻ｔ＝４で、ユーザＡは、領域ａ４が解放されたが領域ａ２がユーザＢの占有領域となっているため、移動体Ｍ１を領域ａ３に留めておく。ユーザＢは、領域ａ１を自身の占有領域とした上で移動体Ｍ２を領域ａ１に移動させる（到着）。
【００５９】
時刻ｔ＝５で、ユーザＡは、領域ａ２が解放されたため、領域ａ２を自身の占有領域とした上で移動体Ｍ１を領域ａ２に移動させる。また、時刻ｔ＝６で、ユーザＡは、領域ａ４を自身の占有領域とした上で移動体Ｍ１を領域ａ４に移動させる（到着）。
【００６０】
このように、ある空域がいずれかのユーザに占有されているとき、他のユーザは当該空域は使用できないため、そのような空域を避けて移動する。なお、迂回経路の設定等は、その移動体を管理する運航管理システム２０が行えばよい。
【００６１】
次に、図１１〜図２０を参照して、もつれ判定アルゴリズムの具体例を説明する。図１１は、もつれ判定アルゴリズムにおける空域の表現例を示す説明図である。図１１に示すように、以下に示す例では、空域（３次元）をグラフで表現する。より具体的には、各空間の座標をグラフの点に対応させ、単位時間あたりにドローンが移動可能な空間座標の繋がりを辺に対応させる。その上で、各空域を、座標の集合として表現する。なお、空の空間構造を表現するグラフおよび各空域は以下の式（１）のように表される。ここで、Ｖは点の集合、Ｅは辺の集合、ｍは空域の数である。ここで各空域は、上述した領域の管理単位に相当する。
【００６２】
【数１】
2019007832.tif 000003
【００６３】
図１２は、グラフ表現された空域群に対する移動体の移動ルールを示す説明図である。図１２に示すように、各移動体は、空域間を移動するときに移動前と移動後の両空間の占有を必要とする。また、１つの空域に対して、異なるユーザの移動体が１つの単位時間内に同時に存在することはできない。また、１つ前の時刻で移動体が存在して限時刻では移動している場合も、その領域には入れない。
【００６４】
次に、もつれ判定アルゴリズムの第１例を説明する。第１例は、ダイクストラ法を異なるユーザに管理される複数の移動体向けに適用したものである。
【００６５】
第１例のもつれ判定アルゴリズムは、判定対象とされた各ドローンについて、出発点と到着点のペア（ｓｉ，ｇｉ）と現在の運航計画により示される出発時刻Ｔｓｉと到着時刻Ｔｇｉとを入力する。ここで、ｎは判定対象とされたドローンの数である。判定対象のドローンは、例えば、もつれ検出対象とされた時間帯において、選択されたユーザが管理するドローンである。また、出発点ｓ、到着点ｇ、出発時刻Ｔｓ、到着時刻Ｔｇの右肩のｉ（ｉ＝１，．．．，ｎ）は、ドローンの識別子を表す。また、出力は、もつれの有無およびもつれが存在する場合、代替ルートの情報（各ドローンのパス情報）である。なお、空域の単位や割当状況などの空域情報は随時参照可能とする。
【００６６】
第１例のもつれ判定アルゴリズムは、判定対象とされた各ドローンについて、選択したユーザの空域を解放したときに取り得るルートの組み合わせを列挙していき、現状よりも良いルートがないかを探索し、探索結果を基にもつれを判定する。このとき、判定対象とされた各ドローンの現在の運航計画の中で一番最初の出発時刻から一番最後の到着時刻までを探索時間範囲とする。
【００６７】
以下、もつれ判定アルゴリズムの詳細を説明する前に、該もつれ判定アルゴリズムに用いる遷移可能状態の抽出アルゴリズムについて説明する。本アルゴリズムでは、ドローンの移動可能な状態として、以下を想定する。まず出発時刻を過ぎてまだ出発していないドローンに対しては、ドローンの位置を出発点とするか出発を見送る。このとき、出発していないドローンの位置としては、出発していない状態を表す特別な座標を付与するなどして、グラフ上にはいないものとする。また、到着点にいるドローンに対しては、到着済み状態を表す特別な座標を付与するなどして、グラフ上にはいないものとする。
【００６８】
また、各ドローンの位置をｄｉで表し、出発前はｓ０、到着後はｇ０にいるとする。また各時刻における各ドローンの状態を、ドローンの位置と時刻とを用いて、ｗ＝（ｄ１，．．．，ｄｎ，ｔ）で表す。以下では、簡単のため、各ドローンは、選択されたユーザの占有領域の解放後の非占有領域内を、１つの時刻の経過で隣接する点から点すなわち辺で繋がった点から点に移動可能とする。
【００６９】
以下、より具体的な処理フローを説明する。遷移可能状態の抽出アルゴリズムでは、時刻ｔの状態が与えられた場合に、時刻ｔ＋１において遷移可能な状態を抽出する。
【００７０】
まず、時刻ｔのｗにおいて到着点にいるドローンがあれば、時刻ｔ＋１の状態における当該ドローンの位置をｇ０とする。次いで、その状態に対して、ｄ１が各隣接位置（ただし、非占有領域に限る）に移動する場合と、移動しない場合とを列挙する。このとき、出発時刻を過ぎていて出発していない場合は、出発する場合と出発しない場合とを列挙する。次いで、１つ前で列挙したすべての状態に対して、さらにｄ２について各隣接位置（ただし、非占有領域に限る）に移動する場合と、移動しない場合とを列挙する。このとき、出発時刻を過ぎていて出発していない場合は、出発する場合と出発しない場合とを列挙する。
【００７１】
以降、同様の処理を、ｄ３，．．．，ｄｎまで繰り返す。最後に、ｄｎについて列挙した全ての状態から、占有条件により遷移不可能な状態を削除し、残った状態を時刻ｔ＋１における遷移可能な状態として出力する。
【００７２】
図１３に、遷移可能状態の抽出アルゴリズムの疑似コードを示す。図１３に示す遷移可能状態の抽出アルゴリズムは、時刻ｔの状態ｗを入力し、状態ｗから遷移可能な時刻ｔ＋１の全ての状態を出力する。まず、Ｓｔｅｐ．１で、遷移可能状態候補を示すＳｔの１つとして、Ｓｔ（０）にｗを代入する。その上で、各ｉ＝１，．．．，ｎについて、ｄｉ＝ｇｉならば、Ｓｔ（０）．ｓｔｉ＝ｇ０とする。また、Ｓｔ（０）．ｓｔｎ＋１＝ｔ＋１とする。
【００７３】
ここで、ｓｔｉはＳｔのｉ番目の要素を表す。また、Ｓｔ（０）は、全ての移動体が時刻ｔ＋１においてｔの位置のままか到着済みを表すｇ０の状態となる。また、Ｓｔの右肩の（）内の数字は、当該Ｓｔのラベルを表す。該ラベルは、次Ｓｔｅｐ以降において遷移先の導出対象とした移動体の識別子ｉに対応する。Ｓｔｅｐ．１は到着済みの処理をした上で、全ての移動体が現状維持となる状態を遷移可能状態候補として生成する処理である。
【００７４】
Ｓｔｅｐ．２では、候補集合ＳＴ［］にＳｔ（０）を追加する。
【００７５】
Ｓｔｅｐ．３では、ＳＴの要素から、ｅ（Ｓｔ）が最小となるＳｔを選ぶ。ここで、ｅ（）はラベルを返す関数である。このとき選択されたＳｔのラベルをｉとし、ｉ＝ｅ（Ｓｔ）＞ｎならばＳｔｅｐ．６に進む。なお、Ｓｔｅｐ．３はＳＴの要素のうちｉの小さいものから順に選ぶ処理である。例えば、ＳＴ［］の唯一の要素がＳｔ（０）であれば、ｅ（Ｓｔ）＝０が返された結果、Ｓｔ（０）が選択される。
【００７６】
Ｓｔｅｐ．４では、遷移先の導出対象を示すｉをｉ＋１に更新するとともに、選択したＳｔのラベルｅ（Ｓｔ）=ｉとする。これにより、選択したＳｔにおいてｄｉも現状位置または出発しない状態の候補がＳｔ（ｉ）としてＳＴ［］に保持される。さらに、時刻ｔにおける状態ｗのｄｉがＶの要素ならば、辺（ｄｉ，ｄｉ’）がＥの要素であることを満たすｄｉ’の各々について、選択したＳｔを基にして、新たなＳｔ（ｉ）を生成する。具体的には、まずＳｔ’に選択したＳｔを代入し、かつＳｔ’．ｓｔｉ＝ｄｉ’としたものを新たなＳｔ（ｉ）として、ＳＴ［］に追加する。なお、Ｓｔｅｐ．３で選択されたＳｔが複数ある場合は、各Ｓｔに対して、遷移先ｄｉ’を反映した新たなＳｔ（ｉ）を生成する。例えば、Ｓｔが２つ選択され、遷移可能な位置ｄｉ’が２つ列挙された場合、４つのＳｔ（ｉ）が生成される。一方、時刻ｔにおける状態ｗのｄｉ＝ｓ０かつｔ＋１≧Ｔｓｉならば、選択したＳｔを基にして、遷移先ｄｉ’＝ｓｉとする新たなＳｔ（ｉ）を生成する。具体的には、まずＳｔ’に選択したＳｔを代入し、その上で、Ｓｔ’．ｓｔｉ＝ｓｉとしたものをＳｔ（ｉ）として、ＳＴ［］に追加する。
【００７７】
Ｓｔｅｐ．５では、Ｓｔｅｐ．３に処理を戻す。以降、ｉ＞ｎになるまでＳｔｅｐ．３〜４の処理を繰り返す。
【００７８】
Ｓｔｅｐ．６では、ＳＴ［］の要素で、ｅ（Ｓｔ）がｎであるＳｔを全て選択する。選択したＳｔのうち、条件（ａ）を満たすものすべてを時刻ｔ＋１において遷移可能状態として出力する。
【００７９】
条件（ａ）：
各ｉ＝１，．．．，ｎ、各ｊ＝１，．．．，ｍについて、選択したＳｔ．ｓｔｉがａｊの要素すなわち領域ａｊ内の点ならば、ｉを除く全てのｋ＝１，．．．，ｎに対して、Ｓｔ（０）．ｓｔｋがａｊの要素でなく、かつＳｔ．ｓｔｋがａｊの要素でない。
【００８０】
なお、条件（ａ）は、領域が他のドローンと重なっているものを削除するための条件（領域の排他条件）である。ここでは、各ｉすなわちドローン単位で領域の排他条件を適用しているが、ユーザが同じドローンについては上記排他条件の適用外とすることも可能である。その場合、上記のｋを、ｋ＝１，．．．，ｎ（ただし、ｉおよびｉと同じユーザの移動体ｌを除く）とすればよい。このように、１つのユーザが複数のドローンの運航を管理する場合、ユーザ単位で領域の排他制御を行うことも可能である。
【００８１】
図１４は、領域の排他条件が適用された例を示す説明図である。今、一直線上に並ぶ５つのポイントｐ１〜ｐ５があったとする。ｐ１は領域ａ１に属し、ｐ２およびｐ３は領域ａ２に属し、ｐ４およびｐ５は領域ａ３に属す。今、状態ｗ＝｛ｐ１，ｐ４，ｔ｝とする。すなわち、時刻ｔにおいて、ユーザＡが管理する移動体Ｍ１がｐ１に位置し、ユーザＢが管理する移動体Ｍ２がｐ４に位置している。この状態ｗに対して、ｔ＋１への遷移可能状態を考える。なお、領域ａ１〜ａ３は、全ての判定対象時刻において解放されているものとみなす。
【００８２】
まず、Ｓｔ（０）＝｛ｐ１，ｐ４，ｔ＋１｝が生成される。次いで、移動体Ｍ１の遷移可能状態が反映されたＳｔ（１）として、移動体Ｍ１が隣接点に移動するパターンの状態｛ｐ２，ｐ４，ｔ＋１｝，移動体Ｍ１が移動しないパターンの状態｛ｐ１，ｐ４，ｔ＋１｝が生成される。次いで、移動体Ｍ２の遷移可能状態が反映されたＳｔ（２）として、上記２つのＳｔ（１）に対して、それぞれ移動体Ｍ２が隣接点に移動するパターンの状態と、移動体Ｍ２が移動しないパターンの状態とが生成される。生成される状態Ｓｔ（２）は｛ｐ２，ｐ３，ｔ＋１｝，｛ｐ２，ｐ５，ｔ＋１｝，｛ｐ２，ｐ４，ｔ＋１｝，｛ｐ１，ｐ３，ｔ＋１｝，｛ｐ１，ｐ５，ｔ＋１｝，｛ｐ１，ｐ４，ｔ＋１｝である。この結果に対して、条件（ａ）を適用すると、｛ｐ２，ｐ３，ｔ＋１｝が除外される。最終的に出力される状態は、Ｓｔ（２）のうち｛ｐ２，ｐ３，ｔ＋１｝を除外した４つの状態である。
【００８３】
次に、第１例のもつれ判定アルゴリズムの詳細を説明する。まず、判定対象とされた各ドローンは出発前とし、ｔを最も早い出発時刻の１つ前の時刻とする。次いで、ｔから遷移可能なｔ＋１の状態を列挙する。当該状態の列挙は既に説明した遷移可能状態の抽出アルゴリズムを用いればよい。
【００８４】
次いで、列挙した全ての状態に対して、さらに次の時刻で遷移可能な状態を列挙する。ここでは、ｔを１ずつ大きくしていき、最も遅い到着時刻になるまで各ｔについて遷移可能な状態を列挙する。
【００８５】
最も遅い到着時刻まで遷移可能な状態の列挙を終えると、列挙された状態のうち、ｔが最大で、かつ全てのドローンが到着済みの状態全てを対象に、該状態から時刻ｔを逆に辿って各ドローンのルートの組み合わせを示すパスセットを導出する。ここでは、対象とされた状態のそれぞれに対して、パスセットが１つ導出される。
【００８６】
導出されたパスセットの中に、各ユーザにとってドローンの到着時刻が早くなるルートの組み合わせがあれば、もつれが存在するとして、該パスセットを出力する。そのようなものがなければ、もつれは存在しないとしてその旨を出力する。
【００８７】
図１５に、第１例のもつれ判定アルゴリズムの疑似コードを示す。本例のもつれ判定アルゴリズムは、出発点と到着点のペア（ｓｉ，ｇｉ）と現在の運航計画により示される出発時刻Ｔｓｉと到着時刻Ｔｇｉとを入力し、もつれの有無およびもつれがある場合にはもつれ解消後のパスセットＰＳの情報を出力する。
【００８８】
まず、Ｓｔｅｐ．１で、展開前の状態（その状態から次の状態へのパスを導出していない状態）の集合をＳ、展開順を記録する木をＷとする。時刻ｔを、判定対象とされたドローンのうち１番早い出発時刻の１つ前の時刻に合わせ、各ドローンの位置ｄｉを、出発前ｓ０とした状態ｗ（ｔ）を生成する。ここでｗの右肩の（）内の数字は当該状態が対応する時刻を表す。ｗ（ｔ）をＳとＷの唯一の要素とする。
【００８９】
Ｓｔｅｐ．２では、Ｓの要素からｔが最小のｗを選択する。以下、選択されたｗが対応する時刻をｔとする。このとき、ｔが最も遅い到着時刻以上ならば、Ｓｔｅｐ．５に進む。そうでないならば、選択したｗ（ｔ）をＳから削除する。
【００９０】
Ｓｔｅｐ．３では、選択した状態ｗ（ｔ）の各々について、次の時刻において遷移可能な状態ｗ（ｔ＋１）を全て列挙する。そして、列挙したｗ（ｔ＋１）をＳとＷに追加する。このとき、Ｗには、ｗ（ｔ＋１）の各々について遷移前の状態ｗ（ｔ）の情報を付与して追加する。具体的には、木構造において枝（ｗ（ｔ），ｗ（ｔ＋１））を付与する。これにより、後から遷移前の状態を辿れるようにする。
【００９１】
Ｓｔｅｐ．４では、Ｓｔｅｐ．２に処理を戻す。以降、ｔが最も遅い到着時刻を超えるまでＳｔｅｐ．２〜３の処理を繰り返す。
【００９２】
Ｓｔｅｐ．５では、Ｗの要素から、ｔが最大かつ全てのドローンの位置が到着済み（全てのｉについてｄｉ＝ｇ０）の状態ｗ（ｔＭＡＸ）を取り出し、取り出したｗ（ｔＭＡＸ）の各々に対して、枝を遡って時刻が１番早い出発時刻の１つ前の時刻になるまでのパスセットＰＳを生成する。Ｓｔｅｐ．５では、Ｗにおいて枝を遡り、時刻が１つ前の状態を繋げることで、パスセットＰＳを生成すればよい。ここで、ｗの右肩のｔＭＡＸおよびｔＭＩＮは、それぞれＷの要素であるｗの最大時刻および最小時刻を表す。パスセットＰＳは、判定対象とされた全てのドローンの各時刻における位置を含む。パスセットＰＳにより、各ドローンのパスの組み合わせが示される。
【００９３】
Ｓｔｅｐ．６では、形成したパスセットＰＳの中で、全てのドローンにおいて、ｄｉ＝ｇｉとなる最初の時刻である到着時刻が、入力された到着時間Ｔｇｉよりも早いパスセットＰＳをすべて出力する。そのようなパスセットＰＳが存在しなければ、もつれが発生していないとして、その旨を示す情報を出力する。
【００９４】
次に、図１６〜図１８を参照して、パス探索およびもつれの判定例を示す。図１６は、運航計画における移動体Ｍ１および移動体Ｍ２のパスの例を示す説明図である。本例では、簡単のため、各移動体が１つの領域間を単位時間あたりに移動可能な場合を考える。すなわち、ポイントと領域とが１対１に対応している場合を考える。移動体Ｍ１はユーザＡによって管理され、移動体Ｍ２はユーザＢによって管理されている。また、図１６（ａ）に示すように、領域は、４×５の２０マスのブロックに分割されており、そのうちの中央６マスは利用不可領域である。また、利用可能領域の各領域に対して、図１６（ｂ）に示すように、識別用にポイント番号（ｐ１〜ｐ１４のいずれか）が割り振られている。また、移動体Ｍ１の出発位置ｓ１はポイントｐ１、到着位置ｇ１はポイントｐ１１に設定され、移動体Ｍ２の出発位置ｓ２はポイントｐ８、到着位置ｇ２はポイントｐ４に設定されている。また、図１６（ｃ）には、運航計画時の領域の割当状況が示されている。運航計画によれば、移動体Ｍ１の開始時刻Ｔｓ１と到着時刻Ｔｇ１は（Ｔｓ１，Ｔｇ１）＝（０，１０）、移動体Ｍ１の開始時刻Ｔｓ１と到着時刻Ｔｇ１は（Ｔｓ２，Ｔｇ２）＝（０，１０）である。
【００９５】
以下、このような状態から時刻ｔ＝０〜１０の時間帯におけるポイントｐ１〜ｐ１４の領域を解放したときの、上記もつれ判定アルゴリズムの判定結果の例を示す。
【００９６】
図１７に、判定対象とされた移動体のうち最も早い出発時刻の１つ前の時刻ｔ＝−１から最も遅い到着時刻ｔ＝１０までの間の遷移可能な状態を時間が小さいものから順に列挙した場合の一部を示す。
【００９７】
第１例のもつれ判定アルゴリズムでは、このようにして列挙された状態の中から、時刻が最大（本例ではｔＭＡＸ＝１０）でかつ判定対象とされた全ての移動体が到着済みの状態を取り出し、時刻が最小（ｔＭＩＮ＝−１）となるまで時刻の逆順に枝を辿ることで、パスセットＰＳ（ｗ（１０），．．．，ｗ（−１））を形成する。なお、図１７において、ｔ＝１０で上から２段目の状態は、領域解放前の各移動体のルートと同じルートを示しているが、全ての移動体が到着済みとなっていないため、当該状態ｗ（ｔＭＡＸ）を基にしたパスセットＰＳは形成されない。
【００９８】
なお、もつれの定義によりパスセットＰＳが形成される条件は異なる。例えば、領域解放前のパスと同じ到着時刻となるパスを一部含んでいても、ユーザ単位で到着時間の合計がプラスになる場合も許容する場合等は、上記の限りではない。このような場合、例えば、許容される最大遅延時間まで探索時間範囲を拡張して遷移可能な状態を列挙し、全ての移動体が到着済みの状態に対し、パスセットＰＳを形成した上で、もつれの定義に従い、出力するパスセットＰＳを取捨選択すればよい。
【００９９】
図１８は、パスセットの一例を示す説明図である。図１８に示す例は、図１７においてｔ＝１０で上から１段目の状態を基に形成されたパスセットＰＳの例である。当該パスセットＰＳによれば、領域の割当を変更することにより、ユーザＡおよびユーザＢともに、到着時刻が短縮されることがわかる。図１８（ａ）には、該パスセットＰＳに含まれる各移動体のルートが示されている。また、図１８（ｃ）には、該パスセットＰＳにおける領域割当の例が示されている。ここでは、４＜１０＝Ｔｇ１、４＜１０＝Ｔｇ２となっており、互いのユーザにとってＷＩＮ−ＷＩＮなルートになっている。なお、本例のパスセットＰＳと各移動体のルートの関係は、図１８（ｄ）に示す通りである。すなわち、パスセットＰＳの要素である各時刻の状態ｗ（ｔ）におけるｉ番目の要素ｄｉを時刻の順に繋げたものが、ｉ番目の移動体のルートとされる。なお、出力されるパスの組は１つに限定されず、条件を満たすパスの組を対象に、運航改善度を評価し、上位ｎ個のパスセットＰＳを出力するといった制御も可能である。
【０１００】
次に、第２例のもつれ判定アルゴリズムについて説明する。第２例は、Ａ＊（Ａスター）をベースにしたアルゴリズムである。
【０１０１】
本例のもつれ判定アルゴリズムも、判定対象とされた各ドローンについて、出発点と到着点のペア（ｓｉ，ｇｉ）と現在の運航計画により示される出発時刻Ｔｓｉと到着時刻Ｔｇｉとを入力する。また、出力は、もつれの有無およびもつれが存在する場合、代替ルートの情報（パスセット）とする。
【０１０２】
ダイクストラ法をベースにした第１例のもつれ判定アルゴリズムでは、現状の時刻が小さいものから順に次の状態を考えたが、Ａ＊をベースにした第２例のもつれ判定アルゴリズムは、予測される到着時間が小さいものから次の状態を考える。予測される到着時刻が実際の到着時間に近ければ、より早く到着しそうなものだけを考えればよいため、処理時間の削減が見込まれる。なお、理論的には、予測される到着時刻が実際の到着時刻よりも低く見積もられていればよい。ここで、「予測される到着時刻＝現在の時刻＋現在の状態から到着までの予測時間」とする。
【０１０３】
到着までの予測時間の取得方法としては、他の移動体の動きを考慮せず、Ａ＊法を用いて最短経路を導出して得る方法や、現在地と到着点の直線距離から算出する方法などが挙げれる。なお、実際の到着時間よりも小さく見積もられる方法であれば、特に限定されない。
【０１０４】
以下、第２例のもつれ判定アルゴリズムの具体的な処理フローを例示する。
【０１０５】
Ｓｔｅｐ．０で、まず初期状態として、各ドローンの位置を出発前とし、時刻ｔを最も早い出発時刻の１つ前の時刻とする状態を定義し、状態の展開木Ｗに追加する。
【０１０６】
Ｓｔｅｐ．１では、Ｗにおいて次の遷移可能な状態が列挙されていない状態の中から、全てのドローンの到着までの予測時間が最小のものを選ぶ。そして、該状態を基に次の時刻で遷移可能な状態を列挙する。このとき、予測される到着時刻のうち最小の時刻である最小予測到着時刻が、入力された最も遅い到着時刻よりも大きいならば、もつれが発生していないとして、その旨を示す情報を出力して終了する。
【０１０７】
Ｓｔｅｐ．２では、Ｗにおいて全てのドローンが到着済みの状態があればそれを選択する。そして、該状態から時刻ｔを逆に辿って各ドローンのルートの組み合わせを示すパスセットＰＳを導出する。ここでは、選択された状態１つに対して、パスセットが１つ導出される。
【０１０８】
Ｓｔｅｐ．３では、導出されたパスセットの中に、所定の条件を満たすものがあれば、もつれが存在するとして、該パスセットを出力して終了する。そのようなものがなければ、Ｓｔｅｐ．１に戻る。
【０１０９】
図１９は、第２例のもつれ判定アルゴリズムのパス探索例を示す説明図である。図１９に示すように、次の状態を列挙する処理の中で、予測される到着時刻が最小の状態について、次の状態を列挙する。
【０１１０】
また、図２０は、第２例のもつれ判定アルゴリズムの判定例を示す説明図である。図２０に示すように、各時刻における遷移可能な状態を全て列挙しなくても、全ての移動体が到着済みでかつ所定の条件を満たすパスセットが導出されれば、その時点でもつれを検出することができる。これにより、全ての状態を通るパスセットが形成されなくても、途中で条件を満たすパスセットが見つかった時点で処理を終了することができる。
【０１１１】
なお、もつれ判定アルゴリズムは上記の例に限定されない。例えば、一部のユーザについて改善がないもしくは不利益を許すパスセットを、もつれ解消後のパスセットとして出力することも可能である。
【０１１２】
また、運航計画に複数の経由点が指定されている場合には、それらを制約条件として入れて遷移先の状態を導出することも可能である。
【０１１３】
また、遷移先の状態を導出する際、各移動体に対して速さの概念を追加することも可能である。この場合、移動可能な位置を、スピートに応じて変更すればよい。例えば、移動体のスピードが１なら、辺を一度跨いだ先（隣接点）までを移動可能とすればよい。また、スピードが２なら、辺を二度跨いだ先（隣接点の隣接点）までを移動可能とすればよい。また、スピードが３なら、辺を三度跨いだ先（隣接点の隣接点の隣接点）までを移動可能とすればよい。なお、いずれの場合も移動体は移動可能な範囲内であれば途中で止まってもよいものとする。
【０１１４】
また、ユーザの選択方法としては、最初から全てのユーザを対象にする方法や、任意のユーザの組み合わせをランダムに選択する方法などが挙げられる。また、もつれが存在する可能性の高いユーザを別のアルゴリズムを用いて判定し、それらユーザを選択することも可能である。
【０１１５】
別のアルゴリズムの例としては、運航計画が示された移動体について、すべて非占有領域と仮定した場合の最短経路を探索し、最短の予想到着時刻と運航計画における到着時刻との差を評価する方法が挙げられる。例えば、探索結果に基づいて、最短の予想到着時刻と運航計画における到着時刻との差が所定数以上または大きい順にｎ個の移動体をリストアップし、それら移動体を管理するユーザを対象にしてもよい。
【０１１６】
また、例えば、あるユーザについて、すべて非占有領域と仮定した場合の各移動体の最短経路を探索した結果の最短経路を基に、該経路上の空域を占有している他のユーザをリストアップする処理を、他のユーザについても同様に行い、その結果を利用する方法が挙げられる。最短経路上の空域を占有している他のユーザのリストアップ処理を相互に繰り返し行って、最終的にリストアップされた全てのユーザを対象にしてもよい。
【０１１７】
また、第２例では、条件を満たすパスセットが導出された時点で該パスセットを出力して処理を終了していたが、Ａ＊ベースのアルゴリズムにおいても、改善案とされる複数のパスセットや、最適経路のパスセットを出力することも可能である。この場合、例えば、許容される最大遅延時間となるまで次の状態を列挙する処理を継続すればよい。
【０１１８】
このように、本実施形態のもつれ検出部１１を利用すれば、もつれがあると判定した場合に、一部の領域の割当変更により改善されるパスセット（改善案）の情報と、該パスセットにおける各移動体の運航経路の改善度またはユーザの運航改善度とを含む情報を得ることができる。ここで、該パスセットは、例えば、最適なものすべてといった複数出力が可能である。なお、ここでの最適性はパレート最適であってもよい。
【０１１９】
例えば、２ユーザを対象にもつれを判定した結果、もつれとともに、（第１のユーザの運航改善度，第２のユーザの運航改善度）＝（４，４），（３，５），（６，３），（３，３）の解（パスセット）を得たとする。その場合、改善情報出力部１２は、（４，４），（３，５），（６，３）の解を改善情報として出力してもよい。
【０１２０】
また、改善情報をランキング形式等で出力する場合、改善情報出力部１２は、何かしらの基準に基づいて各解に対して評価を行い、各解にランクを付ければよい。例えば、全体最適を基準にする場合、移動体全体またはユーザ全体で改善度の合計を計算し、評価してもよい。また、例えば、交渉のしやすさを基準にする場合、対象ユーザの最小の運航改善度を計算し、評価してもよい。また、例えば、公平性を基準にする場合、ユーザ間の運航改善度の差や分散などを計算し、評価してもよい。
【０１２１】
次に、本発明の実施形態にかかるコンピュータの構成例を示す。図２１は、本発明の実施形態にかかるコンピュータの構成例を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１と、主記憶装置１００２と、補助記憶装置１００３と、インタフェース１００４と、ディスプレイ装置１００５と、入力デバイス１００６とを備える。
【０１２２】
上述した運航管制システムは、例えば、コンピュータ１０００に実装されてもよい。その場合、各構成要素の動作は、プログラムの形式で補助記憶装置１００３に記憶されていてもよい。ＣＰＵ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、そのプログラムに従って上記の実施形態における所定の処理を実施する。
【０１２３】
補助記憶装置１００３は、一時的でない有形の媒体の一例である。一時的でない有形の媒体の他の例として、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータは１０００がそのプログラムを主記憶装置１００２に展開し、上記の実施形態における所定の処理を実行してもよい。
【０１２４】
また、プログラムは、各実施形態における所定の処理の一部を実現するためのものであってもよい。さらに、プログラムは、補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで上記の実施形態における所定の処理を実現する差分プログラムであってもよい。
【０１２５】
インタフェース１００４は、他の装置との間で情報の送受信を行う。また、ディスプレイ装置１００５は、ユーザに情報を提示する。また、入力デバイス１００６は、ユーザからの情報の入力を受け付ける。
【０１２６】
また、実施形態における処理内容によっては、コンピュータ１０００の一部の要素は省略可能である。例えば、ユーザから直接情報の入力を受け付けないのであれば、入力デバイス１００６は省略可能であるし、ユーザに直接情報を提示しないのであれば、ディスプレイ装置１００５は省略可能である。
【０１２７】
また、本システムの各構成要素の一部または全部は、汎用または専用の回路（Circuitry）、プロセッサ等やこれらの組み合わせによって実施される。これらは単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。また、本システムの各構成要素の一部又は全部は、上述した回路等とプログラムとの組み合わせによって実現されてもよい。
【０１２８】
各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【０１２９】
次に、本発明の領域管理システムの概要を説明する。図２２は、本発明の領域管理システムの概要を示すブロック図である。図２２に示す領域管理システム５００は、もつれ検出手段５０１と、情報出力手段５０２とを備えている。
【０１３０】
もつれ検出手段５０１（例えば、もつれ検出部１１）は、自身に割り当てられた占有領域内において移動体の運航管理を行うユーザへの占有領域の割当状況を示す領域情報と、ユーザによる各移動体の運航計画を示す運航情報であって、各移動体の出発位置、出発時刻、到着位置および当該運航計画における運航経路を評価する情報を含む運航情報とに基づいて、少なくとも選択された２以上のユーザである選択ユーザの移動体の各々の運航計画に対して、選択ユーザの占有領域の少なくとも一部を変更した場合の運航経路の改善度である経路改善度を算出して、もつれを検出する。
【０１３１】
情報出力手段５０２（例えば、改善情報出力部１２）は、もつれ検出手段５０１による検出結果に基づいて、選択ユーザの少なくとも一部に情報を出力する。
【０１３２】
上記構成によれば、分散型の運航管理システムにおいて、非効率な領域割当の改善に寄与できる。
【０１３３】
以上、本実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１３４】
本発明は、分散型の運航管理システムにおいて、効率的な領域割当を行う用途に好適に適用可能である。
【符号の説明】
【０１３５】
１００  移動体運航システム
１０  領域管理システム
１１  もつれ検出部
１２  改善情報出力部
２０  運航管理システム
１０００  コンピュータ
１００１  ＣＰＵ
１００２  主記憶装置
１００３  補助記憶装置
１００４  インタフェース
１００５  ディスプレイ装置
１００６  入力デバイス
５００  領域管理システム
５０１  もつれ検出手段
５０２  情報出力手段
【図１】
2019007832.tif 000004
【図２】
2019007832.tif 000005
【図３】
2019007832.tif 000006
【図４】
2019007832.tif 000007
【図５】
2019007832.tif 000008
【図６】
2019007832.tif 000009
【図７】
2019007832.tif 000010
【図８】
2019007832.tif 000011
【図９】
2019007832.tif 000012
【図１０】
2019007832.tif 000013
【図１１】
2019007832.tif 000014
【図１２】
2019007832.tif 000015
【図１３】
2019007832.tif 000016
【図１４】
2019007832.tif 000017
【図１５】
2019007832.tif 000018
【図１６】
2019007832.tif 000019
【図１７】
2019007832.tif 000020
【図１８】
2019007832.tif 000021
【図１９】
2019007832.tif 000022
【図２０】
2019007832.tif 000023
【図２１】
2019007832.tif 000024
【図２２】
2019007832.tif 000025