特許ウォッチ

公開番号2024142775
公報種別公開特許公報(A)
公開日2024-10-11
出願番号2023055090
出願日2023-03-30
発明の名称巡回ルート作成装置
出願人株式会社熊谷組
代理人個人
主分類G05D 1/43 20240101AFI20241003BHJP(制御;調整)
要約【課題】複数のエリアを移動体に巡回させるための効率的な巡回ルートを作成可能な巡回ルート作成装置を提供する。
【解決手段】本発明に係る巡回ルート作成装置は、XY座標情報に基づいて区画された複数の移動対象領域の位置情報を認識して当該複数の移動対象領域を移動体に巡回させる巡回ルートを作成するための巡回ルート作成装置であって、巡回ルートの作成方法の異なる複数種類の巡回ルート作成機能と、一つの巡回ルート作成機能を選択する選択手段と、を備えたことを特徴とする。
【選択図】図71
特許請求の範囲【請求項１】
ＸＹ座標情報に基づいて区画された複数の移動対象領域の位置情報を認識して当該複数の移動対象領域を移動体に巡回させる巡回ルートを作成するための巡回ルート作成装置であって、
巡回ルートの作成方法の異なる複数種類の巡回ルート作成機能と、
一つの巡回ルート作成機能を選択する選択手段と、
を備えたことを特徴とする巡回ルート作成装置。
続きを表示（約 2,800 文字）【請求項２】
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、
複数の各移動対象領域の重心同士を繋ぐ重心間経路を作成する重心間経路作成手段と、
重心間経路を辿って各移動対象領域を一巡する巡回ループ経路のうち最も距離の短い巡回ループ経路を作成する巡回ループ経路作成手段と、
各移動対象領域内において複数の巡回パターンを設定可能な巡回パターン設定手段と、
作成された巡回ループ経路に基づいて各移動対象領域を移動するとした場合に、移動コストが最も小さくなる各移動対象領域内での巡回パターンの組み合わせを決定する巡回パターン決定手段と、
各移動対象領域内での巡回パターンの組み合わせが決定した後、２つの移動対象領域における一方の移動対象領域の巡回パターンの終点と他方の移動対象領域の巡回パターンの始点とを繋ぐ各移動対象領域間経路のうち、最も移動コストが大きい移動対象領域間経路を削除して、当該削除された移動対象領域間経路の終点となっていた移動対象領域を巡回開始領域とし、かつ、当該削除された移動対象領域間経路の始点となっていた移動対象領域を巡回終了領域とした巡回ルートを作成する巡回ルート作成手段と、
を備えたことを特徴とする請求項１に記載の巡回ルート作成装置。
【請求項３】
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、
各移動対象領域内において複数の巡回パターンを設定可能な巡回パターン設定手段と、
巡回パターン設定手段により各移動対象領域に設定可能な複数の巡回パターンの始点及び終点として想定可能な地点を各移動対象領域毎に設定して、２つの任意の移動対象領域間において一方の移動対象領域に想定された巡回パターンの終点から他方の移動対象領域に想定された巡回パターンの始点までの二点間で移動するとした場合の当該二点間での移動のしやすさを示す評価値を、全ての始点及び終点の組み合わせによって決まる各二点間に対して作成する評価値作成手段と、
評価値の高い二点間を経路として採用して各移動対象領域を一巡する巡回ループを作成する巡回ループ作成手段と、
巡回ループを構成する移動対象領域間の経路のうち最も移動コストが大きい経路を削除して、当該削除された経路の終点となっていた移動対象領域を巡回開始領域とし、かつ、当該削除された経路の始点となっていた移動対象領域を巡回終了領域とした移動対象領域の巡回順を決定する巡回順決定手段と、
巡回順が決定した後、各移動対象領域毎の始点と終点とを繋ぐ巡回パターンを各移動対象領域毎に決定して、当該各移動対象領域内でそれぞれ決定した巡回パターンと各移動対象領域間の経路とで形成される巡回ルートを作成する巡回ルート作成手段と、
を備えたことを特徴とする請求項１に記載の巡回ルート作成装置。
【請求項４】
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、
各移動対象領域を一巡する巡回ループを作成する巡回ループ作成手段と、
作成された巡回ループの経路を移動体で移動させる場合の移動コストを算出する移動コスト算出手段と、
作成された巡回ループを形成する移動対象領域間ルートのうち最も移動コストの大きい移動対象領域間ルートを削除して、削除した移動対象領域間ルートのルート終端が繋がれていた移動対象領域を巡回ルートのスタート領域とし、かつ、削除した移動対象領域間ルートのルート始端が繋がれていた移動対象領域を巡回ルートのゴール領域とした各移動対象領域を一巡する巡回ルートを作成する巡回ルート作成手段とを備え、
巡回ループ作成手段は、
移動対象領域毎に巡回情報を設定することにより最初の巡回ループを作成する最初の巡回ループ作成手段と、
最初の巡回ループの巡回情報を変更した巡回ループを作成する巡回ループ更新手段とを備え、
巡回ルート作成手段は、
巡回ループ更新手段により作成された今回の巡回ループに基づいて作成された今回の巡回ルート、及び、巡回ループ更新手段により作成された前回の巡回ループに基づいて作成された前回の巡回ルートのうち、どちらの巡回ルートを残すかを判定する判定手段を備え、
巡回情報は、各移動対象領域毎に設定される自己の移動対象領域内の巡回パターンの情報と次に進む移動対象領域の情報とで構成された組み合わせ情報であることを特徴とする請求項１に記載の巡回ルート作成装置。
【請求項５】
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、
各移動対象領域を一巡する巡回ループを作成する巡回ループ作成手段と、
作成された巡回ループの経路を移動体で移動させる場合の移動コストを算出する移動コスト算出手段と、
作成された巡回ループを形成する移動対象領域間ルートのうち最も移動コストの大きい移動対象領域間ルートを削除して、削除した移動対象領域間ルートのルート終端が繋がれていた移動対象領域を巡回ルートのスタート領域とし、かつ、削除した移動対象領域間ルートのルート始端が繋がれていた移動対象領域を巡回ルートのゴール領域とした各移動対象領域を一巡する巡回ルートを作成する巡回ルート作成手段とを備え、
巡回ループ作成手段は、移動対象領域毎に巡回情報を設定することにより巡回ループを作成する初期世代巡回ループ作成手段と、後世代巡回ループ作成手段とを備え、
巡回ルート作成手段は、初期世代巡回ルート作成手段と、後世代巡回ルート作成手段とを備え、
初期世代巡回ループ作成手段は、複数の巡回ループを作成し、
初期世代巡回ルート作成手段は、初期世代巡回ループ作成手段により作成された複数の初期世代巡回ループ毎に、各移動対象領域毎の巡回情報を変更して、複数の初期世代巡回ルートを作成し、
後世代巡回ループ作成手段は、複数の初期世代巡回ルートのうち、移動コストの小さい初期世代巡回ルートをいくつか抽出し、この抽出された初期世代巡回ルートの巡回情報を使用して後世代巡回ループを作成し、
後世代巡回ルート作成手段は、後世代巡回ループ作成手段により作成された後世代巡回ループ毎に、各移動対象領域毎の巡回情報を変更して、後世代巡回ルートを作成し、
巡回情報は、各移動対象領域毎に設定される自己の移動対象領域内の巡回パターンの情報と次に進む移動対象領域の情報とで構成された組み合わせ情報であることを特徴とする請求項１に記載の巡回ルート作成装置。

発明の詳細な説明【技術分野】
【０００１】
本発明は、複数の移動対象領域を移動体に巡回させる巡回ルートを作成するための巡回ルート作成装置に関する。
続きを表示（約 11,000 文字）【背景技術】
【０００２】
本出願人による発明である移動体の移動制御システムとして、移動対象面（移動対象領域）上を移動させる移動体の移動予定情報（移動予定ルート）を作成する移動予定情報作成処理と、移動体を移動予定情報に基づいて移動させるとともに、移動情報取得手段により取得された移動体の実際の移動情報と移動予定情報とを比較して移動体の移動を制御する移動制御処理と、を備えた移動体の移動制御システムが開示されている（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
特開２０２０－１５４４００号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述した移動体の移動制御方法では、移動対象領域が複数ある場合において、移動体を当該複数の移動対象領域間で効率的に巡回させるための巡回ルートを作成することについては開示されておらず、当該巡回ルートを作成するための巡回ルート作成装置の開発が望まれているという課題があった。
本発明は、上記課題に鑑み、複数の移動対象領域を移動体に巡回させるための効率的な巡回ルートを作成可能な巡回ルート作成装置を提供するものである。
【課題を解決するための手段】
【０００５】
本発明に係る巡回ルート作成装置は、ＸＹ座標情報に基づいて区画された複数の移動対象領域の位置情報を認識して当該複数の移動対象領域を移動体に巡回させる巡回ルートを作成するための巡回ルート作成装置であって、巡回ルートの作成方法の異なる複数種類の巡回ルート作成機能と、一つの巡回ルート作成機能を選択する選択手段と、を備えたことを特徴とする。
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、複数の各移動対象領域の重心同士を繋ぐ重心間経路を作成する重心間経路作成手段と、重心間経路を辿って各移動対象領域を一巡する巡回ループ経路のうち最も距離の短い巡回ループ経路を作成する巡回ループ経路作成手段と、各移動対象領域内において複数の巡回パターンを設定可能な巡回パターン設定手段と、作成された巡回ループ経路に基づいて各移動対象領域を移動するとした場合に、移動コストが最も小さくなる各移動対象領域内での巡回パターンの組み合わせを決定する巡回パターン決定手段と、各移動対象領域内での巡回パターンの組み合わせが決定した後、２つの移動対象領域における一方の移動対象領域の巡回パターンの終点と他方の移動対象領域の巡回パターンの始点とを繋ぐ各移動対象領域間経路のうち、最も移動コストが大きい移動対象領域間経路を削除して、当該削除された移動対象領域間経路の終点となっていた移動対象領域を巡回開始領域とし、かつ、当該削除された移動対象領域間経路の始点となっていた移動対象領域を巡回終了領域とした巡回ルートを作成する巡回ルート作成手段と、を備えたことを特徴とする。
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、各移動対象領域内において複数の巡回パターンを設定可能な巡回パターン設定手段と、巡回パターン設定手段により各移動対象領域に設定可能な複数の巡回パターンの始点及び終点として想定可能な地点を各移動対象領域毎に設定して、２つの任意の移動対象領域間において一方の移動対象領域に想定された巡回パターンの終点から他方の移動対象領域に想定された巡回パターンの始点までの二点間で移動するとした場合の当該二点間での移動のしやすさを示す評価値を、全ての始点及び終点の組み合わせによって決まる各二点間に対して作成する評価値作成手段と、評価値の高い二点間を経路として採用して各移動対象領域を一巡する巡回ループを作成する巡回ループ作成手段と、巡回ループを構成する移動対象領域間の経路のうち最も移動コストが大きい経路を削除して、当該削除された経路の終点となっていた移動対象領域を巡回開始領域とし、かつ、当該削除された経路の始点となっていた移動対象領域を巡回終了領域とした移動対象領域の巡回順を決定する巡回順決定手段と、巡回順が決定した後、各移動対象領域毎の始点と終点とを繋ぐ巡回パターンを各移動対象領域毎に決定して、当該各移動対象領域内でそれぞれ決定した巡回パターンと各移動対象領域間の経路とで形成される巡回ルートを作成する巡回ルート作成手段と、を備えたことを特徴とする。
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、各移動対象領域を一巡する巡回ループを作成する巡回ループ作成手段と、作成された巡回ループの経路を移動体で移動させる場合の移動コストを算出する移動コスト算出手段と、作成された巡回ループを形成する移動対象領域間ルートのうち最も移動コストの大きい移動対象領域間ルートを削除して、削除した移動対象領域間ルートのルート終端が繋がれていた移動対象領域を巡回ルートのスタート領域とし、かつ、削除した移動対象領域間ルートのルート始端が繋がれていた移動対象領域を巡回ルートのゴール領域とした各移動対象領域を一巡する巡回ルートを作成する巡回ルート作成手段とを備え、巡回ループ作成手段は、移動対象領域毎に巡回情報を設定することにより最初の巡回ループを作成する最初の巡回ループ作成手段と、最初の巡回ループの巡回情報を変更した巡回ループを作成する巡回ループ更新手段とを備え、巡回ルート作成手段は、巡回ループ更新手段により作成された今回の巡回ループに基づいて作成された今回の巡回ルート、及び、巡回ループ更新手段により作成された前回の巡回ループに基づいて作成された前回の巡回ルートのうち、どちらの巡回ルートを残すかを判定する判定手段を備え、巡回情報は、各移動対象領域毎に設定される自己の移動対象領域内の巡回パターンの情報と次に進む移動対象領域の情報とで構成された組み合わせ情報であることを特徴とする。
前記複数種類の巡回ルート作成機能のうちの一つの巡回ルート作成機能は、各移動対象領域を一巡する巡回ループを作成する巡回ループ作成手段と、作成された巡回ループの経路を移動体で移動させる場合の移動コストを算出する移動コスト算出手段と、作成された巡回ループを形成する移動対象領域間ルートのうち最も移動コストの大きい移動対象領域間ルートを削除して、削除した移動対象領域間ルートのルート終端が繋がれていた移動対象領域を巡回ルートのスタート領域とし、かつ、削除した移動対象領域間ルートのルート始端が繋がれていた移動対象領域を巡回ルートのゴール領域とした各移動対象領域を一巡する巡回ルートを作成する巡回ルート作成手段とを備え、巡回ループ作成手段は、移動対象領域毎に巡回情報を設定することにより巡回ループを作成する初期世代巡回ループ作成手段と、後世代巡回ループ作成手段とを備え、巡回ルート作成手段は、初期世代巡回ルート作成手段と、後世代巡回ルート作成手段とを備え、初期世代巡回ループ作成手段は、複数の巡回ループを作成し、初期世代巡回ルート作成手段は、初期世代巡回ループ作成手段により作成された複数の初期世代巡回ループ毎に、各移動対象領域毎の巡回情報を変更して、複数の初期世代巡回ルートを作成し、後世代巡回ループ作成手段は、複数の初期世代巡回ルートのうち、移動コストの小さい初期世代巡回ルートをいくつか抽出し、この抽出された初期世代巡回ルートの巡回情報を使用して後世代巡回ループを作成し、後世代巡回ルート作成手段は、後世代巡回ループ作成手段により作成された後世代巡回ループ毎に、各移動対象領域毎の巡回情報を変更して、後世代巡回ルートを作成し、巡回情報は、各移動対象領域毎に設定される自己の移動対象領域内の巡回パターンの情報と次に進む移動対象領域の情報とで構成された組み合わせ情報であることを特徴とする。
本発明によれば、複数の移動対象領域を移動体に巡回させるための効率的な巡回ルートを作成可能な巡回ルート作成装置を提供できるようになる。特に、巡回ルートの作成方法の異なる複数種類の巡回ルート作成機能と、一つの巡回ルート作成機能による巡回ルートの作成を選択できる選択手段と、を備えた構成としたので、状況に応じて、巡回ルート作成方法を選択できるようになり、巡回ルート作成対象に応じて適切な巡回ルートを効率的に作成することができるようになった。
【図面の簡単な説明】
【０００６】
移動対象領域及び障害物領域の作成処理（ｐｈａｓｅ１）の説明図。
障害物グループ分け処理（ｐｈａｓｅ２）の説明図。
障害物角認識処理（ｐｈａｓｅ３）の説明図。
障害物間境界線作成処理（ｐｈａｓｅ４）の説明図。
分割領域区分け処理（ｐｈａｓｅ５）の説明図。
分割領域区分け処理（ｐｈａｓｅ５）の説明図。
分割領域認識処理（ｐｈａｓｅ６）の説明図。
分割領域認識処理（ｐｈａｓｅ６）の説明図。
等間隔直線経路作成処理（ｐｈａｓｅ７）の説明図。
交点座標抽出処理（ｐｈａｓｅ８）の説明図。
エリア毎交点座標抽出処理（ｐｈａｓｅ９）及び分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）の説明図。
分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）及び分割領域間移動予定ルート作成処理（ｐｈａｓｅ１１）の説明図。
移動対象領域及び障害物領域の作成処理（ｐｈａｓｅ１）の手順を示すフローチャート。
障害物グループ分け処理（ｐｈａｓｅ２）の手順を示すフローチャート。
障害物角認識処理（ｐｈａｓｅ３）の手順を示すフローチャート。
障害物間境界線作成処理（ｐｈａｓｅ４）の手順を示すフローチャート。
分割領域区分け処理（ｐｈａｓｅ５）の手順を示すフローチャート。
分割領域認識処理（ｐｈａｓｅ６）の手順を示すフローチャート。
等間隔直線経路作成処理（ｐｈａｓｅ７）及び交点座標抽出処理（ｐｈａｓｅ８）の手順を示すフローチャート。
エリア毎交点座標抽出処理（ｐｈａｓｅ９）の手順を示すフローチャート。
分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）の手順を示すフローチャート。
移動コスト計算処理（ｐｈａｓｅ１１）の手順を示すフローチャート。
別ルート作成処理（ｐｈａｓｅ１２～１６）の手順を示すフローチャート。
ルート選択処理（ｐｈａｓｅ１７）の手順を示すフローチャート。
分割領域間移動予定ルート作成処理（ｐｈａｓｅ１８）の手順を示すフローチャート。
分割領域認識処理（ｐｈａｓｅ６）の説明図。
分割領域認識処理（ｐｈａｓｅ６）の説明図。
分割領域認識処理（ｐｈａｓｅ６）の説明図。
エリア毎交点座標抽出処理（ｐｈａｓｅ９）及び分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）の説明図。
分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）の説明図。
移動体の一例を示す斜視図。
巡回パターンを例示した図。
ＳＡ処理の概略フローチャート。
初期巡回ループ作成処理を示すフローチャート。
初期温度設定処理、巡回ルートコスト計算処理、及び改変受入可否判定処理を示すフローチャート。
エリア間ルートの改変処理、及び、巡回パターンの改変処理を示すフローチャート。
エリア間ルートの改変処理の説明図。
エリア間ルートの改変処理の説明図。
エリア間ルートの改変処理の説明図。
エリア間ルートの改変処理の説明図。
エリア間ルートの改変処理の説明図。
エリア間ルートの改変処理の説明図。
焼きなまし法（ＳＡ）の概念説明図。
初期巡回情報配列及び初期巡回ループを示す図。
巡回情報配列の一例を示す。
エリア間ルートの改変処理の説明図。
遺伝的アルゴリズム法（ＧＡ）の概略フローチャート。
初期世代個体生成処理を示すフローチャート。
個体評価処理を示すフローチャート。
交叉処理を示すフローチャート。
突然変異処理を示すフローチャート。
致死的遺伝情報を持つ個体の説明図。
致死的遺伝情報を持つ個体の説明図。
基本の交叉処理の説明図。
例外的交叉処理の説明図。
例外的交叉処理の説明図。
例外的交叉処理の説明図。
各エリア毎の重心Ｇを例示した図。
各エリアの重心同士を繋ぐ重心間経路を例示した図。
巡回ループ経路候補を例示した図。
巡回パターン決定の手順を示す図。
巡回ルート作成装置による処理の流れを示したフローチャート。
重心間経路作成手法の他例を示す図。
重心間経路作成手法の他例を示す図。
各エリアに設定可能な複数の巡回パターンの始点及び終点として想定可能な地点を、各エリア毎に設定した例を示した図。
全ての始点及び終点の組み合わせによって決まる各二点間の直線経路を設定した例を示した図。
評価値の高い上位α％の二点間の直線経路を抽出した例を示した図。
出発経路を、エリア毎に、上位Ｍ個までに絞った例を示した図。
巡回ルート作成装置による処理の流れを示したフローチャート。
表示手段の画面上に設定される処理選択画面を示す図。
表示手段の画面上に設定される処理選択画面の詳細を示す図。
巡回ルート作成装置の使用方法を示すフローチャート。
区画分け処理の説明図。
「区画の生成」ボタン３０をクリックした場合の処理フローチャート。
「巡回パターンの生成」ボタン３１をクリックした場合の処理フローチャート。
[区画・巡回パターンの生成]の「高度な設定」ボタン３２をクリックした場合の処理フローチャート。
「デフォルトに戻す」ボタン３４、「反映して終了」ボタン３５をクリックした場合の処理フローチャート。
［地図・巡回ルートを開く］の「新規で開く」ボタン１をクリックした場合の処理フローチャート。
［地図・巡回ルートを開く］の「探索済又は探索中の地図を開く」ボタン２をクリックした場合の処理フローチャート。
［地図・巡回ルートを保存］の「新規の工事名で保存」ボタン３をクリックした場合の処理フローチャート。
［地図・巡回ルートを保存］の「上書き保存」ボタン４をクリックした場合の処理フローチャート。
［ショートパスで巡回ルートを探索開始」ボタン５をクリックした場合の処理フローチャート。
ショートパスでの「処理を中止」ボタン７をクリックした場合の処理フローチャート。
ショートパスでの「高度な設定」ボタン６をクリックした場合の処理フローチャート。
［ドロネーで巡回ルートを探索開始」ボタン８をクリックした場合の処理フローチャート。
ドロネーでの「処理を中止」ボタン１０をクリックした場合の処理フローチャート。
ドロネーでの「高度な設定」ボタン９をクリックした場合の処理フローチャート。
［ＧＡで巡回ルートを探索］の「新規で巡回ルートを探索開始」ボタン１１をクリックした場合の処理フローチャート。
ＧＡでの「処理を中止」ボタン１３をクリックした場合の処理フローチャート。
ＧＡでの「高度な設定」ボタン１２、「デフォルトに戻す」ボタン４０、「反映して終了」ボタン４１をクリックした場合の処理フローチャート。
［ＳＡで巡回ルートを探索開始］ボタン１４をクリックした場合の処理フローチャート。
ＳＡでの「処理を中止」ボタン１６をクリックした場合の処理フローチャート。
ＳＡでの「高度な設定」ボタン１５、「デフォルトに戻す」ボタン４２、「反映して終了」ボタン４３をクリックした場合の処理フローチャート。
手動で巡回ルートを設定する場合、「元に戻す」ボタン２３－１、「やり直し」ボタン２３－２をクリックした場合の処理フローチャート。
ボタン２３－３～２３－１０の何れかをクリックした場合の処理フローチャート。
「巡回順を設定」ボタン２３－１１、「巡回順を削除」ボタン２３－１２、「このエリアを無効化」ボタン２３－１３、「このエリアを有効化」ボタン２３－１４をクリックした場合の処理フローチャート。
コストログ表示欄Ｃのいずれかの行２４が強調表示されている状態でクリックした場合の処理フローチャート。
「現在の巡回ルートをアニメーションで表示する」ボタン２５をクリックした場合の処理フローチャート。
「障害物を避ける巡回ルートを再計算」ボタン２６をクリックした場合の処理フローチャート。
終了ボタン２９をクリックした場合の処理フローチャート。
【発明を実施するための形態】
【０００７】
前提技術
まず、本発明に係る巡回ルート作成装置の実施形態を説明する前に、本発明に係る巡回ルート作成装置の前提装置（前提技術）となる移動予定ルート作成装置を、段落０００７乃至段落００５３、図１乃至図３１に基づいて説明する。
本発明に係る巡回ルート作成装置の前提装置となる移動予定ルート作成装置は、移動体を移動対象領域内の障害物を避けて移動させるための移動体の移動予定ルート、即ち、当該移動対象領域内を移動させる移動体の障害物回避移動予定ルートを作成する装置である。
当該移動体の移動予定ルート作成装置は、移動対象領域作成手段と、障害物領域作成手段と、移動可能領域分割手段と、分割領域内移動予定ルート作成手段と、分割領域間移動予定ルート作成手段とを備える。
即ち、移動対象領域作成手段は、移動対象領域の位置を示す移動対象領域のＸＹ座標情報（即ち、移動対象領域の平面座標情報）に基づいて移動対象領域を区画する移動対象領域境界線で囲まれた移動対象領域を作成する手段である。
障害物領域作成手段は、移動対象領域内の障害物の位置を示すＸＹ座標情報に基づいて移動対象領域内に存在する障害物を区画する障害物領域境界線で囲まれた障害物領域を作成する手段である。
移動可能領域分割手段は、移動対象領域の位置を示すＸＹ座標情報及び移動対象領域内の障害物の位置を示すＸＹ座標情報を利用して障害物を避けた移動可能領域内を複数の分割領域に分割する手段である。
分割領域内移動予定ルート作成手段は、複数の各分割領域内での移動体の移動予定ルートを作成する手段である。
分割領域間移動予定ルート作成手段は、分割領域間での移動体の移動予定ルートを作成する手段である。
【０００８】
そして、移動可能領域分割手段は、分割領域作成手段と、分割領域認識手段とを備える。
当該分割領域作成手段は、障害物同士を繋ぐ第１の境界線、障害物と移動対象領域境界線とを繋ぐ第２の境界線、障害物と第１の境界線又は第２の境界線とを繋ぐ第３の境界線を作成して、移動対象領域内をこれら境界線で区画することにより、これら境界線、障害物領域境界線、移動対象領域境界線で形成された分割領域境界線で囲まれた分割領域を作成する手段である。
分割領域認識手段は、複数の各分割領域及び各障害物領域にそれぞれ識別情報を付与して複数の各分割領域を認識する手段である。
また、分割領域内移動予定ルート作成手段は、横直線作成手段と、縦直線作成手段と、第１の交点認識手段と、第２の交点認識手段と、第１のルート作成手段と、第２のルート作成手段と、第１の移動効率算出手段と、ルート選択手段とを備える。
横直線作成手段は、移動対象領域をＹ軸に沿って等間隔に区切るＸ軸と平行な複数の横直線を作成する手段である。
縦直線作成手段は、移動対象領域をＸ軸に沿って等間隔に区切るＹ軸と平行な複数の縦直線を作成する手段である。
第１の交点認識手段は、分割領域境界線と横直線との交点を認識する手段である。
第２の交点認識手段は、分割領域境界線と縦直線との交点を認識する手段である。
第１のルート作成手段は、各分割領域境界線上の交点を横直線で繋いで形成されたＹ軸に沿って進む分割領域毎のジグザグな第１のルートを作成する手段である。
第２のルート作成手段は、各分割領域境界線上の交点を縦直線で繋いで形成されたＸ軸に沿って進む分割領域毎のジグザグな第２のルートを作成する手段である。
第１の移動効率算出手段は、分割領域毎の第１のルートに沿って移動する場合の移動効率を算出する手段である。
第２の移動効率算出手段は、分割領域毎の第２のルートに沿って移動する場合の移動効率を算出する手段である。
ルート選択手段は、同じ分割領域内を第１のルートに沿って移動する場合の移動効率と第２のルートに沿って移動する場合の移動効率とを比較して、第１のルート及び第２のルートのうち移動効率の良いルートを当該分割領域内での移動予定ルートとして選択する手段である。
そして、上記分割領域作成手段は、より具体的には、移動対象領域内に存在する複数の障害物を、Ｘ座標情報の近いもの同士、Ｙ座標情報の近いもの同士に、グループ分けする障害物グループ分け手段と、各障害物の複数の角にそれぞれ識別情報を付与して障害物の角を認識する障害物角認識手段と、Ｘ座標情報の近いもの同士としてグループ分けされた一方の障害物の角と他方の障害物の角とを接続する第１の接続線、及び、Ｙ座標情報の近いもの同士としてグループ分けされた一方の障害物の角と他方の障害物の角とを接続する第１の接続線を作成する第１の接続線作成手段と、障害物のうち第１の接続線が接続されていない角と移動対象領域境界線とを接続する第２の接続線を作成する第２の接続線作成手段と、障害物のうち第１の接続線及び第２の接続線が接続されていない角と既に作成した第１の接続線又は第２の接続線とを接続する第３の接続線を作成する第３の接続線作成手段とを備えた構成とした。
また、上記分割領域間移動予定ルート作成手段は、より具体的には、一方の分割領域の分割領域内移動予定ルートの終点と他方の分割領域の分割領域内移動予定ルートの始点とを直線で繋いだ分割領域間移動予定ルートを作成する分割領域間直線移動予定ルート作成手段と、分割領域間直線移動予定ルート作成手段で作成した分割領域間直線移動予定ルートと移動対象領域境界線又は障害物領域境界線とが接触した場合に、移動対象領域境界線又は障害物領域境界線と接触しない分割領域間移動予定ルートである分割領域間迂回移動予定ルートを作成する分割領域間迂回移動予定ルート作成手段とを備えた構成とした。
【０００９】
本発明による巡回ルート作成装置の前提装置となる移動予定ルート作成装置を構成する、移動対象領域作成手段、障害物領域作成手段、障害物グループ分け手段、障害物角認識手段、第１の接続線作成手段、第２の接続線作成手段、第３の接続線作成手段、分割領域認識手段、横直線作成手段、縦直線作成手段、第１の交点認識手段、第２の交点認識手段、第１のルート作成手段、第２のルート作成手段、第１の移動効率算出手段、第２の移動効率算出手段、ルート選択手段、分割領域間移動予定ルート作成手段は、制御手段により実現され、当該各手段を実行する制御手段は、各手段が実行する処理の手順を示す処理プログラムと、当該処理プログラムによる情報処理を実現するコンピュータ等のハードウエア資源とにより構成される。
換言すれば、前提装置の移動予定ルート作成処理プログラムは、コンピュータを、上述した移動対象領域作成手段、障害物領域作成手段、障害物グループ分け手段、障害物角認識手段、第１の接続線作成手段、第２の接続線作成手段、第３の接続線作成手段、分割領域認識手段、横直線作成手段、縦直線作成手段、第１の交点認識手段、第２の交点認識手段、第１のルート作成手段、第２のルート作成手段、第１の移動効率算出手段、第２の移動効率算出手段、ルート選択手段、分割領域間移動予定ルート作成手段として機能させるプログラムである。
【００１０】
上述した移動対象領域作成手段及び障害物領域作成手段により、図１，図１３に示した移動対象領域及び障害物領域の作成処理（ｐｈａｓｅ１）が実行される。
障害物グループ分け手段により、図２，図１４に示した障害物グループ分け処理（ｐｈａｓｅ２）が実行される。
障害物角認識手段により、図３，図１５に示した障害物角認識処理（ｐｈａｓｅ３）が実行される。
第１の接続線作成手段により、図４，図１６に示した障害物間境界線作成処理（ｐｈａｓｅ４）が実行される。
第２の接続線作成手段及び第３の接続線作成手段により、図５，図６，図１７に示した分割領域区分け処理（ｐｈａｓｅ５）が実行される。
分割領域認識手段により、図７，図８，図１８，図２６乃至図２８に示した分割領域認識処理（ｐｈａｓｅ６）が実行される。
また、横直線作成手段により、図９，図１９に示した等間隔直線経路作成処理（ｐｈａｓｅ７）が実行される。
第１の交点認識手段により、図１０，図１９に示した交点座標抽出処理（ｐｈａｓｅ８）、及び、図１１，図２０，図２９に示したエリア毎交点座標抽出処理（ｐｈａｓｅ９）が実行される。
第１のルート作成手段により、図１２，図２１，図２９，図３０に示した分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）が実行される。
第１の移動効率算出手段により、分割領域毎の第１のルートに沿って移動する場合の図２２に示した移動コスト計算処理（ｐｈａｓｅ１１）が実行される。
縦直線作成手段により、等間隔直線経路作成処理（ｐｈａｓｅ７）を置き換えた処理である図２３のステップＳ２３０に示したｐｈａｓｅ１２が実行される。
第２の交点認識手段により、交点座標抽出処理（ｐｈａｓｅ８）を置き換えた処理である図２３のステップＳ２４０に示したｐｈａｓｅ１３、及び、エリア毎交点座標抽出処理（ｐｈａｓｅ９）と同じ処理である図２３のステップＳ２５０に示したｐｈａｓｅ１４が実行される。
第２のルート作成手段により、分割領域内ジグザグ移動予定ルート作成処理（ｐｈａｓｅ１０）を置き換えた処理である図２３のステップＳ２６０に示したｐｈａｓｅ１５が実行される。
第２の移動効率算出手段により、図２３のステップＳ２７０に示したｐｈａｓｅ１６が実行される。つまり、分割領域毎の第２のルートに沿って移動する場合において、図２２に示した移動コスト計算処理（ｐｈａｓｅ１１）と同じ移動コスト計算処理が実行される。
ルート選択手段により、図２４に示したルート選択処理（ｐｈａｓｅ１７）が実行される。
分割領域間移動予定ルート作成手段により、図１２，図２５に示した分割領域間移動予定ルート作成処理が実行される。
尚、分割領域間移動予定ルート作成手段の分割領域間直線移動予定ルート作成手段によって、分割領域間直線移動予定ルート作成処理（図２５の経路探索アルゴリズム部分以外の部分）が実行されるとともに、分割領域間移動予定ルート作成手段の分割領域間迂回移動予定ルート作成手段によって、分割領域間迂回移動予定ルート作成処理としての図２５の経路探索アルゴリズム部分の処理が実行される。
（【００１１】以降は省略されています）

関連特許