TOP > 国内特許検索 > 最適飛行網の生成方法及びシステム > 明細書

明細書 :最適飛行網の生成方法及びシステム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2017-161315 (P2017-161315A)
公開日 平成29年9月14日(2017.9.14)
発明の名称または考案の名称 最適飛行網の生成方法及びシステム
国際特許分類 G01C  21/26        (2006.01)
G08G   5/00        (2006.01)
FI G01C 21/26 Z
G08G 5/00 A
請求項の数または発明の数 14
出願形態 OL
全頁数 12
出願番号 特願2016-044821 (P2016-044821)
出願日 平成28年3月8日(2016.3.8)
発明者または考案者 【氏名】浜中 雅俊
出願人 【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
個別代理人の代理人 【識別番号】100091443、【弁理士】、【氏名又は名称】西浦 ▲嗣▼晴
審査請求 未請求
テーマコード 2F129
5H181
Fターム 2F129AA11
2F129CC15
2F129CC16
2F129CC17
2F129DD02
2F129DD47
2F129DD62
5H181AA26
5H181AA27
5H181FF11
5H181FF17
要約 【課題】 消費エネルギが少なく済む飛行経路を決定できる最適飛行網の生成方法及びシステムを提供する。
【解決手段】 地図データ記憶部10から読み出した3次元地図データより、適正位置決定部12の飛行予定領域決定部14は飛行予定領域を決定する。暫定位置決定部16は飛行予定領域内の複数の移動ウエイポイントについて、蟻コロニー最適化により各移動ウエイポイントから各固定ウエイポイントまでの消費エネルギが最小となる飛行経路を決定し、次に粒子群最適化により平均消費エネルギが最小となる位置を決定する。この過程を3次元地図データに含まれる全ての飛行予定領域について適用する。
【選択図】 図1
特許請求の範囲 【請求項1】
3次元地図データに対して経路データベースの基準点となる複数のウエイポイントを設定し、上限飛行高度が定められた無人飛行体を低消費エネルギで飛行させるのに適した飛行経路を各ウエイポイント間に生成する最適飛行網の生成方法であって、
前記3次元地図データ内に1つの飛行予定領域を決定し、該飛行予定領域を囲む複数のウエイポイントを移動しない複数の固定ウエイポイントと定める第1のステップと、
前記複数の固定ウエイポイントに囲まれた前記飛行予定領域内にある1以上のウエイポイントの位置を変えながら、前記1以上のウエイポイントと前記複数の固定ウエイポイントとの間を前記無人飛行体が移動するのに消費エネルギが最小になる経路を求め、前記1以上のウエイポイントと前記複数の固定ウエイポイントとの間の前記消費エネルギの平均消費エネルギが最小になる経路が得られる前記1以上のウエイポイントの位置を該1以上のウエイポイントの暫定位置として決定する第2のステップを、
前記3次元地図データを網羅するように定めた複数の前記飛行予定領域に対して、それぞれ実行することにより、前記3次元地図データに設定した前記複数のウエイポイントの適正位置を決定することを特徴とする最適飛行網の生成方法。
【請求項2】
前記3次元地図データの外周部に位置する複数のウエイポイントを常に固定ウエイポイントとする請求項1に記載の最適飛行網の生成方法。
【請求項3】
先に暫定位置が決定された前記1以上のウエイポイントを含む前記飛行予定領域に隣接して次の飛行予定領域を設定する請求項1または2に記載の最適飛行網の生成方法。
【請求項4】
前記複数の飛行予定領域をランダムに設定することを特徴とする請求項1または2に記載の最適飛行網の生成方法。
【請求項5】
前記第1のステップ及び第2のステップでは、消費エネルギを目的関数とする最適化を行うことを特徴とする請求項1に記載の最適飛行網の生成方法。
【請求項6】
前記第2のステップにおいて、前記経路を求める際に、蟻コロニー最適化または遺伝的アルゴリズムを用い、前記1以上のウエイポイントを移動させるときに粒子群最適化またはグリッドサーチを用いることを特徴とする請求項1に記載の最適飛行網の生成方法。
【請求項7】
前記蟻コロニー最適化では、f=ax+by+czの関数を消費エネルギに相当するコスト関数とし演算を行い、
但し、xは飛行経路の水平方向の移動距離、yは飛行経路の垂直方向の移動距離、zは前記飛行経路の平均曲率であり、a、b及びcは前記無人飛行体の性能によって定められる係数であることを特徴とする請求項3に記載の最適飛行網の生成方法。
【請求項8】
3次元地図データに対して経路データベースの基準点となる複数のウエイポイントを設定し、上限飛行高度が定められた無人飛行体を低消費エネルギで飛行させるのに適した飛行経路を各ウエイポイント間に生成する最適飛行網の生成システムであって、
前記複数のウエイポイントを設定した前記3次元地図データを記憶する地図データ記憶部と、
前記複数のウエイポイントの適正位置を決定して前記地図データ記憶部に記憶させる適正位置決定部とを備え、
適正位置決定部は、コンピュータを用いて、
前記3次元地図データ内に1つの飛行予定領域を決定し、該飛行予定領域を囲む複数のウエイポイントを移動しない複数の固定ウエイポイントと定める第1のステップと、
前記複数の固定ウエイポイントに囲まれた前記飛行予定領域内にある1以上のウエイポイントの位置を変えながら、前記1以上のウエイポイントと前記複数の固定ウエイポイントとの間を前記無人飛行体が移動するのに消費エネルギが最小になる経路を求め、前記1以上のウエイポイントと前記複数の固定ウエイポイントとの間の前記消費エネルギの平均消費エネルギが最小になる経路が得られる前記1以上のウエイポイントの位置を該1以上のウエイポイントの暫定位置として決定する第2のステップとを、
前記3次元地図データを網羅するように定めた複数の前記飛行予定領域に対して、それぞれ実行することにより、前記3次元地図データに設定した前記複数のウエイポイントの適正位置を決定するように構成されていることを特徴とする最適飛行網の生成システム。
【請求項9】
前記3次元地図データの外周部に位置する複数のウエイポイントを常に固定ウエイポイントとする請求項8に記載の最適飛行網の生成システム。
【請求項10】
先に暫定位置が決定された前記1以上のウエイポイントを含む前記飛行予定領域に隣接して次の飛行予定領域を設定する請求項8または9に記載の最適飛行網の生成システム。
【請求項11】
前記複数の飛行予定領域をランダムに設定することを特徴とする請求項8または9に記載の最適飛行網の生成システム。
【請求項12】
前記第1のステップ及び第2のステップでは、消費エネルギを目的関数とする最適化を行うことを特徴とする請求項8に記載の最適飛行網の生成システム。
【請求項13】
前記第2のステップにおいて、前記経路を求める際に、蟻コロニー最適化または遺伝的アルゴリズムを用い、前記1以上のウエイポイントを移動させるときに粒子群最適化またはグリッドサーチを用いることを特徴とする請求項8に記載の最適飛行網の生成システム。
【請求項14】
前記蟻コロニー最適化では、f=ax+by+czの関数を消費エネルギに相当するコスト関数とし演算を行い、
但し、xは飛行経路の水平方向の移動距離、yは飛行経路の垂直方向の移動距離、zは前記飛行経路の平均曲率であり、a、b及びcは前記無人飛行体の性能によって定められる係数であることを特徴とする請求項10に記載の最適飛行網の生成システム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、最適飛行網の生成方法及びシステムに関するものである。
【背景技術】
【0002】
特開平6-149376号公報(特許文献1)には3次元地形情報に基づいて経路コストが最小になるような経路を探索する経路生成技術が開示されている。また特許第3557443号公報(特許文献2)及び特許第3302735号公報(特許文献3)には、3次元の地図データに対して経路データベースの基準点となる複数のウエイポイントを設定し、航空機を低高度で飛行させるのに適した飛行経路を複数のウエイポイントを結んで生成する飛行経路の生成技術が開示されている。
【先行技術文献】
【0003】

【特許文献1】特開平6-149376号公報
【特許文献2】特許第3557443号公報
【特許文献3】特許第3302735号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
特許文献2及び3に記載の技術では、設定したウエイポイントを固定した状態でウエイポイント間に適正な飛行経路を設定している。しかしながらドローンのような無人飛行体では、電池を電源にして飛行しなければならず長時間の飛行ができず、しかも飛行高度に制限が付けられている。このような条件では、飛行時間をできるだけ長くする(言い換えると燃費に相当する消費エネルギができるだけ少なくなる)経路を選択する必要がある。しかしながら従来の技術では、ウエイポイントを固定しているために、このような要求に十分に応えることができない。
【0005】
本発明の目的は、できるだけ高速で飛行することができ、しかも消費エネルギが少なく済む飛行経路を決定できる最適飛行網の生成方法及びシステムを提供することある。
【課題を解決するための手段】
【0006】
本発明の方法は、3次元地図データに対して経路データベースの基準点となる複数のウエイポイントを設定し、上限飛行高度が定められた無人飛行体を低消費エネルギで飛行させるのに適した飛行経路を各ウエイポイント間に生成する最適飛行網の生成方法を対象とする。本発明では、第1のステップと第2のステップを3次元地図データを網羅するように定めた複数の飛行予定領域に対して、それぞれ実行することにより、3次元地図データに設定した複数のウエイポイントの適正位置を決定する。
【0007】
第1のステップでは、3次元地図データ内に1つの飛行予定領域を決定し、該飛行予定領域を囲む複数のウエイポイントを移動しない複数の固定ウエイポイントと定める。
第2のステップでは、複数の固定ウエイポイントに囲まれた飛行予定領域内にある1以上のウエイポイントの位置を変えながら、1以上のウエイポイントと複数の固定ウエイポイントとの間を無人飛行体が移動するのに消費エネルギが最小になる経路を求め、1以上のウエイポイントと複数の固定ウエイポイントとの間の消費エネルギの平均消費エネルギが最小になる経路が得られる1以上のウエイポイントの位置を該1以上のウエイポイントの暫定位置として決定する。そして、第1のステップと第2のステップを3次元地図データを網羅するように定めた複数の飛行予定領域に対して、それぞれ実行することにより、3次元地図データに設定した複数のウエイポイントの適正位置を決定する。
【0008】
本発明では、固定ウエイポイントに囲まれた飛行予定領域内の1以上のウエイポイントの位置を適宜に変更しながら1以上のウエイポイントと複数の固定ウエイポイントとの間の消費エネルギの平均消費エネルギが最小になる経路が得られる1以上のウエイポイントの位置を該1以上のウエイポイントの暫定位置として決定する。したがってウエイポイントを固定した状態で最適飛行網を決定していた従来の技術と比べて、出発点から到達点に達するまでに要する消費エネルギを少なくすることができる。
【0009】
複数の飛行予定領域が重ならない状態で設定される場合には、1以上のウエイポイントの暫定位置はそのまま適正位置となる。複数の飛行予定領域が一部重なる状態で設定される場合には、重なる位置にある1以上のウエイポイントの暫定位置は、再度第2のステップが実施されることにより新たな暫定位置に変わることがある。暫定位置は、すべての飛行予定領域に対する1以上のウエイポイントの決定動作が終了した時点で、適正位置となる。
【0010】
なお1以上のウエイポイントが1つのウエイポイントの場合は、最も簡単で且つ適正位置の決定時間が短くなる。
【0011】
また複数の飛行予定領域の設定は、次に設定される飛行予定領域が前に設定された飛行予定領域内の暫定位置にあるウエイポイントが固定ウエイポイントとなるように、隣合うように設定すると位置決定に要する時間が短くなるが、次の飛行予定領域の設定をランダムに行ってもよいのは勿論である。
【0012】
3次元地図データの外周部に位置する複数のウエイポイントを常に固定ウエイポイントとするのが好ましい。このようにすると外周部に位置する複数のウエイポイントの適正位置の決定のための地図データを準備する必要がなくなる。
【0013】
前記第2のステップでは、消費エネルギを目的関数とする最適化を行うことができる。
【0014】
第2のステップにおいて、経路を求める際に、蟻コロニー最適化または遺伝的アルゴリズムを用い、1以上のウエイポイントを移動させるときに粒子群最適化またはグリッドサーチを用いると、経路の決定及び1以上のウエイポイントの決定が容易になる。
【0015】
蟻コロニー最適化では、f=ax+by+czの関数を消費エネルギに相当するコスト関数とし演算を行うことができる。この場合、xは飛行経路の水平方向の移動距離、yは飛行経路の垂直方向の移動距離、zは飛行経路の平均曲率であり、a、b及びcは無人飛行体の性能によって定められる係数である。このようなコスト関数を用いると、経路の決定を簡単な演算で実現できる。なおコスト関数は、上記の関数に限定されるものではない。
【図面の簡単な説明】
【0016】
【図1】本発明の最適飛行網の生成システムの1つの実施の形態を示すブロック図である。
【図2】図1の実施の形態における飛行予定領域決定部により決定された3次元地図上の飛行予定領域を表した図である。
【図3】蟻コロニー最適化部により飛行予定領域内の移動ウエイポイントから各固定ウエイポイントまでの最適飛行経路を決定する様子を示す図2と同様の図である。
【図4】蟻コロニー最適化部が図3の最初の移動ウエイポイントについての処理が終了した後に移動ウエイポイントを移動させた状態を示す図2と同様の図である。
【図5】粒子群最適化部がウエイポイントの暫定位置を決定した状態を示す図2と同様の図である。
【図6】1つの暫定位置が決定した後の次の飛行予定領域の各ウエイポイントを示す図2と同様の図である。
【図7】図1に示した最適飛行網の生成システムを、コンピュータを用いて実施する場合のソフトウエアのアルゴリズムを示すフローチャートである。
【図8】図2のステップ2の詳細を示すフローチャートである。
【図9】3つの飛行予定領域を含む最適飛行網を3次元地図データ上に表した図である。
【発明を実施するための形態】
【0017】
以下、図面を参照しつつ本発明の最適飛行網の生成方法及びシステムの実施の形態の一例について説明する。

【0018】
図1において、本実施の形態の最適飛行網の生成システムは、3次元地図データに対して経路データベースの基準点となる複数のウエイポイントを設定し、上限飛行高度が定められた無人飛行体を低消費エネルギで飛行させるのに適した飛行経路を各ウエイポイント間に生成するシステムである。そのために本実施の形態の最適飛行網の生成システムは、地図データ記憶部10と、適正位置決定部12とを備えている。

【0019】
地図データ記憶部10は、複数のウエイポイントを設定した3次元地図データを記憶する。3次元地図データは通常の2次元地図データに加えて標高データを含んでいる。標高データは、例えば陸域観測技術衛星が生成したものを用いることができる。

【0020】
適正位置決定部12は、複数のウエイポイントの適正位置を決定して地図データ記憶部10に記憶させる。

【0021】
適正位置決定部12は、飛行予定領域決定部14と、暫定位置決定部16と、ウエイポイント設定部18とを含む。飛行予定領域決定部14は、地図データ記憶部10から読み出した3次元地図データ内に1つの飛行予定領域を決定し、該飛行予定領域を囲む6つのウエイポイントを、移動しない6つの固定ウエイポイントと定める。図2は、飛行予定領域決定部14により決定された3次元地図上の飛行予定領域を表す。図2において、飛行経路は三角メッシュ状に3次元地図全体を覆っており、飛行経路の各交点がそれぞれウエイポイントである。多数のウエイポイントのうち、6つの固定ウエイポイントWPf1~WPf6により囲まれた領域を飛行予定領域とし、飛行予定領域に含まれる1つのウエイポイントを移動ウエイポイントWPmとする。

【0022】
なお本実施の形態では、3次元地図データの外周部に位置する複数のウエイポイントは、常に固定ウエイポイントとするようにしている。図2に示した3次元地図データでは、固定ウエイポイントWPf1~WPf6は、飛行予定領域の外周部に位置しており、移動ウエイポイントWPmの適正位置を決定するまでの間は、常に固定ウエイトポイントで、移動ウエイトポイントにはならない。このようにすると外周部に位置するウエイポイントの適正位置決定のためのデータを準備する必要がなくなる。これらの固定ウエイポイントWPf1~WPf6も、順次移動ウエイポイントWPmとなって適正位置を決めるときには、移動させられることになる。

【0023】
暫定位置決定部16は、飛行予定領域決定部14が設定した飛行予定領域と3次元地図データとを受け取って、飛行予定領域内における最適な移動ウエイポイントWPmの位置を決定し、暫定ウエイポイントWPpとする。本実施の形態では、リソースの節約及び決定時間の短縮の観点より、一回の処理で1つの暫定ウエイポイントWPpを決定する。しかしながら条件によっては、1つの飛行予定領域内に複数の移動ウエイポイントを設けて、複数の暫定ウエイポイントWPpを同時に得ることも可能である。 暫定位置決定部16は、暫定ウエイポイントWPpを決定するために、蟻コロニー最適化部20及び粒子群最適化部22において2段階での決定処理を行う。

【0024】
蟻コロニー最適化とは、フェロモンを使って蟻が効率的に巣から餌場まで移動しているしくみを確率モデルで表したものである。蟻は、巣であるコロニーから餌を採りに出かけるが、餌を見つけるとその一部を持ち帰るが、その際にフェロモンを出しながら帰る。そして、餌を探しに行く蟻はフェロモンを見つけると、その先にある餌を求めてその経路を移動し、帰りにフェロモンを強化していく。フェロモンは時間と共に蒸発するため、より適した経路が選択される。

【0025】
第1のステップを実行する蟻コロニー最適化部20は、図3に示すように、移動ウエイポイントWPmから各固定ウエイポイントWPf1~WPf6までの飛行経路においてエネルギの消費が最小になる経路を最適飛行経路として設定する。したがって移動ウエイポイントWPmと各固定ウエイポイントWPf1~WPf6との間に、それぞれ1本ずつ、計6本の最適飛行経路が生成される。すなわちコロニーに該当する移動ウエイポイントWPmから、各固定ウエイポイントWPf1~6までの消費エネルギが最小となる経路が、上記の蟻コロニー最適化の手法を利用して求められる。因みに図3の最初に選択される移動ウエイポイントWPmは、三角メッシュ状の飛行経路の交点上にある。 本実施の形態において、どの経路が消費エネルギが最小となるかは、無人飛行体が飛行した場合に、消費エネルギを目的関数とする最適化演算により決定する。すなわち以下のコスト関数が最小となる経路を最適飛行経路とする。

【0026】
f=ax+by+cz (1)
コスト関数を表す式(1)において、
x:飛行経路の水平方向の移動距離
y:飛行経路の垂直方向の移動距離(積算)
z:飛行経路の平均曲率
である。

【0027】
飛行経路の水平方向の移動距離が長ければそれだけエネルギを消費し、積算の水平方向の移動距離(始点と終点の高度差ではない)はそのまま消費エネルギに反映し、平均曲率は無人飛行体が曲がると加減速のためにエネルギを使うためである。a、b及びcは無人飛行体の性能によって定まる定数であるが、例えば0.08、0.8、0.01のような数値の重み定数である。定数は無人飛行体の機種ごとに定まり、無人飛行体を実際に飛行させてデータを取得することができるほか、メーカから提供される仕様からも導き出せる。また無人飛行体が実荷か空荷かで定数に相当な差が生じるが、無人飛行体が実荷で目的地に行き、空荷で出発点まで戻るとすると、最大積載重量の半分程度の重量の荷物を積載した状態で定数を求めるようにしてもよいのは勿論である。このようなコスト関数を用いると、経路の決定を簡単な演算で実現することができる。

【0028】
関数格納部24は上記のコスト関数を格納し、外部から入力された各定数を記憶しておき、コスト関数に各定数を入れて、蟻コロニー最適化部20にコスト関数を出力する。なおコスト関数は上記のものに限定されることはなく、乗算を含めたり、他の要素を加えたり、あるいは消費エネルギ以外の評価基準(例えば目的地に到達するまでに要する時間等)が考慮されていてもよい。

【0029】
蟻コロニー最適化部20は図3のように、まず1つの移動ウエイポイントWPmについての最適飛行経路が求められたら、図4のように移動ウエイポイントWPmを移動させ、さらに図5のように移動させて、各移動ウエイポイントWPmについて上記と同様に6本の最適飛行経路を求める。1回の処理において最適飛行経路が求められる移動ウエイポイントWPmの位置や個数は限定されないが、1つの飛行予定領域に一つの移動ウエイポイントWPmを想定することが最も演算が容易になる。移動ウエイポイントWPmの移動箇所は、初期の位置は全体に分散することなく飛行予定領域の中心付近に集中させることが効率的と考えられる。理論的には、飛行予定領域の広さやリソースや処理時間等により調整されるが、例えば100箇所である。

【0030】
次に、第2のステップを実行する粒子群最適化部22は、粒子群最適化の処理により、移動ウエイポイントWPmと6つの固定ウエイポイントWPfとの間の消費エネルギの平均消費エネルギが最小になる経路が得られる1つの移動ウエイポイントWPmの位置を発見し、暫定ウエイポイントWPpの暫定位置として決定する。

【0031】
粒子群最適化とは、魚群において一匹が良い経路を見つけると、残りの群がそれに倣うしくみをモデル化したものである。多次元空間において、最適解を求めようとするとき、位置と速度を持つ粒子群が動き回る。このとき、最も良い値となっている粒子の位置が全体に通知され、また、ローカルなベストな位置にある粒子が近傍に通知される。

【0032】
粒子群最適化部22は、蟻コロニー最適化部20から複数の移動ウエイポイントWPmそれぞれの位置及び6つの最適飛行経路の平均消費エネルギを受け取り、これらに基づいて粒子群最適化の処理を行う。すなわち平均消費エネルギが最小となる暫定ウエイポイントWPp(=粒子)の位置が求められ、ローカルなベストな位置にある移動ウエイポイントWPmの位置(=粒子)が計算上近傍にある移動ウエイポイントに通知され、各移動ウエイポイントは,自分がそれまでに発見した最良の位置を記憶する。そして、現在位置をその最良の位置と比較し、最良の位置の方が良い位置であれば、移動ウエイポイントは速度を調節してその最良の位置に戻る。これらの通知に基づいて各移動ウエイポイントWPm(=粒子)の位置及び速度が更新される。

【0033】
本実施の形態における上記「平均」は単純な算術平均だが、幾何平均等の他の平均の利用が妥当なこともある。例えば飛行予定領域が荷物の集積地の近傍で、無人飛行体はトラック等の他の輸送手段で搬入された荷物を集積地から個々の目的地に配達するためにその飛行予定領域を飛行するような場合である。このような集積地から離れる方向に向かう無人飛行体はほとんど実荷であり、集積地に近づく方向に向かう無人飛行体はほとんど空荷である。このように実荷と空荷との無人飛行体が同じ飛行経路を、極端に偏った向きで飛行することが見込まれる場合、実荷と空荷とでコスト関数の定数を変えるとともに、向きを考慮した調和平均を適用することにより、現実の無人機運用に即した最適飛行経路を得ることが期待できる。

【0034】
ウエイポイント設定部18は、粒子群最適化部22から位置及び速度の更新された各粒子の位置=移動ウエイポイントWPmの位置を受け取って、再度の処理が必要ならば蟻コロニー最適化部20に出力し、再度の処理が必要ない場合には1つの飛行予定領域について平均消費エネルギの最小だった暫定ウエイポイントWPpの暫定位置を新たな固定ウエイポイントWPfに置き換えて飛行予定領域決定部14に出力する。図5に暫定ウエイポイントWPpの暫定位置を決定した状態を示す。最終的には、暫定位置を適正位置として、地図データ記憶部10に出力する。

【0035】
一つの暫定ウエイポイントWPpの暫定位置が決定されると、これを受信した飛行予定領域決定部14は、次に処理する飛行予定領域の設定を行う。その際、本実施の形態では、位置決定に要する時間を短くするために、先に暫定ウエイポイントWPpの位置が決定されて更新された固定ウエイポイントWPfを含む飛行予定領域に隣接して次の飛行予定領域を設定する。その中でも、先に更新された固定ウエイポイントにより囲まれた飛行予定領域に設定すると、より効率的である。図6に示すように、図5の暫定ウエイポイントWPpを新たな固定ウエイポイントWPf7として、固定ウエイポイントWPf2、4、8~10で囲まれる新たな飛行予定領域を設定し、領域内に含まれていた固定ウエイポイントWPf3を新たな移動ウエイポイントWPmとして、暫定位置決定の処理を続行している。なお、処理時間やリソースへの負担が問題にならない限り、次に処理対象となる飛行予定領域はランダムに設定されても、他の規則に従って選択されてもよいことは言うまでもない。

【0036】
他の実施の形態においては、経路を求める際に、蟻コロニー最適化の代わりに遺伝的アルゴリズム等の他の手法を利用することができる。また1以上のウエイポイントを移動させるときに、粒子群最適化の代わりにグリッドサーチ等の他の手法を用いることができる。

【0037】
このような最適飛行網の生成システムは、パーソナルコンピュータの制御装置、演算装置、主記憶装置等、補助記憶装置等の周辺機器及びOSを含むソフトウエアにより構成することができる。蟻コロニー最適化や粒子群最適化に関しては、専用のパッケージソフトが販売されており、入手可能である。

【0038】
次に、本実施の形態に係る最適飛行網の生成システムをコンピュータを用いて実現する場合に用いるソフトウエアのアルゴリズムを図7及び8を参照しつつ説明する。最初に、適正位置決定部12の飛行予定領域決定部14が、初期は三角メッシュ状の飛行経路の交点である複数のウエイポイントを設定した3次元地図データを地図データ記憶部10から読み出し(ステップS1)、図2に示すように、第1のステップとして、移動しない6つの固定ウエイポイントWPf1~WPf6に囲まれた飛行予定領域を決定する(ステップS2)。

【0039】
次に、暫定位置決定部16は、図3以下に示すように、第2のステップとして、飛行予定領域決定部14が決定した飛行予定領域内において、飛行予定領域を囲む6つの固定ウエイポイントWPf1~WPf6との間を無人飛行体が移動するのに消費エネルギが最小となる1つの移動ウエイポイントWPmの位置を、1つの暫定ウエイポイントWPpの暫定位置として決定する(ステップS3)。

【0040】
ステップS3の暫定位置決定は、図7のフローチャートに示すように飛行予定領域内の複数の各移動ポイントWPm(ステップS31で位置を決定)から各固定ウエイポイントWPf1~WPf6までの消費エネルギが最小となる最適経路をそれぞれ得る蟻コロニー最適化のステップ32と、平均消費エネルギの最小となる移動ウエイポイントWPm(=粒子)の位置を求め、これを暫定ウエイポイントWPpとして、その位置が全体の粒子(ウエイポイント)に通知され、またローカルなベストな位置にある粒子(ウエイポイント)が近傍の粒子に通知され、これらの通知に基づいて各粒子の位置及び速度を更新する粒子群最適化のステップS34との2段階の最適化を通じて暫定位置が決定される。

【0041】
次に、暫定ウエイポイントWPpの位置を決定してよいかどうかが判断される(ステップS36)。この判断は、本実施の形態においてはステップS32及びS34を繰り返した回数に基づく。粒子群最適化は、繰り返し処理を行う回数が多ければ多いほど、結果が最適に近づくことは明らかであるが、リソース及び処理時間の問題から、適当な回数で終了することが好ましい。本実施の形態では、同一の飛行予定領域について、ステップS32及び34を5回繰り返すと、今回の暫定ウエイポイントWPpの位置が現在のところ該飛行予定領域内で最適なウエイポイントの位置とであると判断し、暫定位置決定がなされる。繰り返した回数が5回未満の場合には、ステップS34の粒子群最適化において移動された各移動ウエイポイントWPmの位置が更新されて(ステップS38)、更新された各移動ウエイポイントWPmの位置にて蟻コロニー最適化(ステップ32)の処理が繰り返し行われる。

【0042】
その他の実施の形態では、暫定ウエイポイントWPpの位置を決定してよいかどうかの判断は、例えば前回の暫定位置と今回の暫定位置とを比較して、同一か無視してよいような微差しかないような場合には、今回の暫定位置が最適であるとの推定に基づいてなされるようにしてもよい。

【0043】
1つの飛行予定領域についてステップS3の暫定位置決定が終了したら、3次元地図データに未処理の飛行予定領域があるかどうか判断し(ステップS4)、ある場合には地図データ記憶部10に記憶された3次元地図データ上で暫定位置の移動ウエイポイントを固定ウエイポイントに変更し(ステップS5)、ステップS1に戻って新たな飛行予定領域についてステップS2以下が繰り返される。

【0044】
ステップS4にて、全部の飛行予定領域についての処理が終了したと判断されたら、すなわち3次元地図データに設定した三角メッシュの最外周に位置する固定ウエイポイント以外の固定ウエイポイントを移動ウエイポイントしてその暫定位置を決定したら、それまでに決定された固定ウエイポイントの暫定位置を適正位置としてよいかどうかが判断される(ステップS6)。この判断は、本実施の形態では繰り返しの回数で、3回である。回数が2回以下の場合には、各飛行予定領域について再度の適正位置決定の処理が実行される。従って、1回目と2回目、2回目と3回目では、暫定ウエイポイントWPpの位置が異なってくるが、回数を重ねるうちに収束することは明らかであり、本実施の形態においては、3回繰り返せばほぼ最適な結果に到達したと推測される。他の実施の形態では、3次元地図データの面積の広狭や飛行予定領域の数によって、処理の回数は変動しうる。また他の実施の形態では、ステップS6の判断は前回の結果との照合に基づく。

【0045】
ステップS6で暫定位置が適正位置と判断されたら、3次元地図データに設定した複数のウエイポイントの適正位置を決定し、地図データ記憶部10に書き込んで(ステップS7)、本実施の形態の処理は終了する。

【0046】
図9は、3つの飛行予定領域について、本実施の形態による最適飛行網の生成方法により生成された最適飛行網の一例である。初期は三角メッシュ状に規則的に並んでいた3つのウエイポイントWP1~3は、図1のシステムを用いて図7及び8に示した処理を施した結果、初期の位置からずれ、相互間及び外周の固定ポイントまでの経路が直線ではなくなっている。図9の結果が得られるまで、まず3つの飛行予定領域について最適化を5回繰り返し、それを3回繰り返したので、図9の最適飛行網はステップS33及び34の最適化を総計で45回実行したことになる。

【0047】
地図データ記憶部10に書き込まれた適正位置のウエイポイントを交点とする飛行経路は、無人飛行体がこれに沿って飛行することにより、消費エネルギを最小に抑えることが期待される。上記の処理を3次元地図データ上の三角メッシュの交点に位置する固定ウエイポイント(正しい地図データの最外周部に位置する固定ウエイポイントを除く)について、実施することにより、3次元地図データ上の全ての領域に最適飛行網を設定することができる。

【0048】
以上のように本実施の形態の最適飛行網の生成方法は、ウエイポイントを移動させて最適飛行網を生成することができるので、ウエイポイントを固定した状態で最適飛行網を決定していた従来の技術と比べて、出発点から到達点に達するまでに要する消費エネルギを少なくすることができる。

【0049】
複数の飛行予定領域が重ならない状態で設定される場合には、1以上のウエイポイントの暫定位置はそのまま適正位置となる。複数の飛行予定領域が一部重なる状態で設定される場合には、重なる位置にある1以上のウエイポイントの暫定位置は、再度第2のステップが実施されることにより新たな暫定位置に変わることがある。暫定位置は、3次元地図データをカバーするすべての飛行予定領域に対する1以上のウエイポイントの決定動作が終了した時点で、適正位置となる。
【産業上の利用可能性】
【0050】
以上説明したように、本発明の最適飛行網の生成方法及びシステムによれば、消費エネルギが少なくて済む無人飛行体の最適な飛行経路を決定することができる。
【符号の説明】
【0051】
10 地図データ記憶部
12 適正位置決定部
14 飛行予定領域決定部
16 暫定位置決定部
18 ウエイポイント設定部
20 蟻コロニー最適化部
22 粒子群最適化部
24 コスト関数格納部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8