(57)【要約】【課題】自律移動のための経路生成装置及び該装置を用いた自律移動装置において、最適経路の生成、走行中における走行経路の最適化を図る。【解決手段】自律移動装置１は、地図や複数のノード、走行パラメータを記憶する記憶手段２と、ノードから自律移動用の経路を生成する経路生成手段３とを備える。記憶手段２と経路生成手段３は経路生成装置４を構成する。経路生成装置４は、始点終点ノードの選択、アルゴリズムＡ＊による両ノード間の経路の探索、及び始点終点ノードの見直しによって走行コスト最小の経路を生成する。自律移動装置１は、環境認識手段６で得られた情報と地図で自己位置を認識し、障害物を回避しながら経路生成装置４が生成した経路に基き、又はノードを追加して障害物回避の経路を生成しながら目的位置まで移動する。【選択図】図１
2005050105.tif 000002
【特許請求の範囲】
【請求項１】
自律移動装置を現在位置から目的位置まで自律的に移動させるための経路を生成する経路生成装置であって、
自律移動装置の走行領域の地図や走行経路を構成するための複数のノードの位置を含む走行パラメータを記憶する記憶手段と、
前記記憶手段に記憶されたノードから自律移動用の経路を構成するノードを選択し、その選択したノードを用いて経路を生成する経路生成手段と、を備え、
前記経路生成手段は、現在位置からノードに到達するためのコストが一番小さなノードを、現在位置から最初に到達すべきノードである始点ノードとして選択して経路を生成し、
さらに前記経路生成手段は、前記生成した経路において現在位置から前記始点ノードを経由することなく前記始点ノードの次の経路上のノードに向かうコストが、前記始点ノードを経由するときのコストよりも小さい場合、前記選択した始点ノードの替わりにその始点ノードの次のノードを新たな始点ノードとして選択することを特徴とする自律移動のための経路生成装置。
【請求項２】
前記経路生成手段は、目的位置がノードでない場合、目的位置に到達するためにコストが一番小さなノードを、目的位置に向かう経路上の最後のノードである終点ノードとして選択して経路を生成し、
さらに前記経路生成手段は、前記生成した経路において終点ノードの手前のノードから終点ノードを経由することなく目的位置に向かうコストが、前記終点ノードを経由するときのコストよりも小さい場合、前記選択した終点ノードの替わりにその終点ノードの手前のノードを新たな終点ノードとして選択する請求項１に記載の自律移動のための経路生成装置。
【請求項３】
前記経路生成手段は、始点ノード又は終点ノードとするために選択したノードと自律移動装置の現在位置又は目的位置との間に予め設定した通行不可能なエリアがある場合に、その間のコストを無限大とする請求項１又は請求項２に記載の自律移動のための経路生成装置。
【請求項４】
前記経路生成手段は、始点ノードとするために選択したノードと自律移動装置の現在位置との間に自律移動装置に備えた環境認識手段で障害物が検出された場合に、その間のコストを無限大とする請求項１乃至請求項３のいずれかに記載の自律移動のための経路生成装置。
【請求項５】
前記経路生成手段は、自律移動装置の現在位置から次のノードに向かう経路において、自律移動装置とそのノードとの間に自律移動装置に備えた環境認識手段で障害物が検出された場合に、その障害物を避ける位置に新たにノードを設定して、そのノードを始点ノードとして経路を再生成する請求項１乃至請求項４のいずれかに記載の自律移動のための経路生成装置。
【請求項６】
前記経路生成手段は、自律移動装置の現在位置から次のノードに向かう経路において、自律移動装置とそのノードとの間に自律移動装置に備えた環境認識手段で障害物が検出された場合に、その障害物を避ける位置に新たにノードを設定して、一旦そのノードに到達してから経路を再生成する請求項１乃至請求項５のいずれかに記載の自律移動のための経路生成装置。
【請求項７】
前記経路生成手段は、前記新たに設定したノードを、前記障害物を避け、かつ、予め地図情報に設定された通行禁止エリアを避けた位置に設定する請求項５又は請求項６に記載の自律移動のための経路生成装置。
【請求項８】
請求項１乃至請求項７のいずれかに記載の経路生成装置を用いて自律移動のための経路を生成し、その経路に基づいて移動する自律移動装置であって、
目的位置や操作指令を与えるためのインターフェースと、
障害物や自己位置を認識するための環境認識手段と、
走行を行うための走行手段と、
環境認識手段で得られた情報を元に地図上で自己の位置を認識し、かつ、障害物を回避しながら前記経路生成装置で生成された経路に基づいて目的位置まで前記走行手段を制御する走行制御手段と、を備え、
前記経路生成装置の記憶手段は、予め他の移動する物体を回避するために停留できる領域を記憶し、
前記走行制御手段は、前記停留開始信号検出手段が信号を検出したとき前記領域に停留するように前記走行手段を制御することを特徴とする自律移動装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自律移動のための経路生成装置及び該装置を用いた自律移動装置に関する。
【背景技術】
【０００２】
従来、省力化や無人化等のために屋内における自律移動装置（ロボット）による物品の運搬、情報伝達等を行う装置技術が知られている。このような自律移動装置は、その稼働領域の環境地図に基づいて生成した走行経路により稼働される。走行経路は環境地図上の特徴点からなる予め定められたノードを経由するように形成される。その経路の生成は、自律移動装置の稼働環境の変化に対応して生成する必要がある。稼働環境の変化にともなう目的地や経路の変更に柔軟に対応するため、稼働環境の通路の直線部、曲がり角、交差点、部屋をそれぞれブロックとし、各ブロックの種類と各ブロック間の接続情報、ブロック座標、ブロック座標間の変換パラメータを含むブロック情報のブロックの種類とブロック間の接続情報とに基づいて、走行経路を生成するものが知られている（例えば、特許文献１参照）。この方法によると、ロボットの走行対象の施設の配置等が変更されて、走行経路を変更する場合に簡単に変更した環境データを作成することができ、変更された条件での最適走行経路を簡単に求めることができるとされる。
【特許文献１】特開平１１−８５２７３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上述した特許文献１に示されるような経路生成方法や経路生成装置においては、環境地図や環境のモデルを効率的に変更して稼働環境の変化に対応することに力点が置かれている。自律移動装置の稼働においては、走行経路そのものの最適化や効率的で柔軟な走行経路の生成の観点から、なお一層の改善が望まれている。
【０００４】
本発明は、上記課題を解消するものであって、最適経路を生成でき、また走行中において走行経路の最適化を行いながら効率的に走行できる自律移動のための経路生成装置及び該装置を用いた自律移動装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記課題を達成するために、請求項１の発明は、自律移動装置を現在位置から目的位置まで自律的に移動させるための経路を生成する経路生成装置であって、自律移動装置の走行領域の地図や走行経路を構成するための複数のノードの位置を含む走行パラメータを記憶する記憶手段と、前記記憶手段に記憶されたノードから自律移動用の経路を構成するノードを選択し、その選択したノードを用いて経路を生成する経路生成手段と、を備え、前記経路生成手段は、現在位置からノードに到達するためのコストが一番小さなノードを、現在位置から最初に到達すべきノードである始点ノードとして選択して経路を生成し、さらに前記経路生成手段は、前記生成した経路において現在位置から前記始点ノードを経由することなく前記始点ノードの次の経路上のノードに向かうコストが、前記始点ノードを経由するときのコストよりも小さい場合、前記選択した始点ノードの替わりにその始点ノードの次のノードを新たな始点ノードとして選択する自律移動のための経路生成装置である。
【０００６】
請求項２の発明は、請求項１に記載の自律移動のための経路生成装置において、前記経路生成手段は、目的位置がノードでない場合、目的位置に到達するためにコストが一番小さなノードを、目的位置に向かう経路上の最後のノードである終点ノードとして選択して経路を生成し、さらに前記経路生成手段は、前記生成した経路において終点ノードの手前のノードから終点ノードを経由することなく目的位置に向かうコストが、前記終点ノードを経由するときのコストよりも小さい場合、前記選択した終点ノードの替わりにその終点ノードの手前のノードを新たな終点ノードとして選択するものである。
【０００７】
請求項３の発明は、請求項１又は請求項２に記載の自律移動のための経路生成装置において、前記経路生成手段は、始点ノード又は終点ノードとするために選択したノードと自律移動装置の現在位置又は目的位置との間に予め設定した通行不可能なエリアがある場合に、その間のコストを無限大とするものである。
【０００８】
請求項４の発明は、請求項１乃至請求項３のいずれかに記載の自律移動のための経路生成装置において、前記経路生成手段は、始点ノードとするために選択したノードと自律移動装置の現在位置との間に自律移動装置に備えた環境認識手段で障害物が検出された場合に、その間のコストを無限大とするものである。
【０００９】
請求項５の発明は、請求項１乃至請求項４のいずれかに記載の自律移動のための経路生成装置において、前記経路生成手段は、自律移動装置の現在位置から次のノードに向かう経路において、自律移動装置とそのノードとの間に自律移動装置に備えた環境認識手段で障害物が検出された場合に、その障害物を避ける位置に新たにノードを設定して、そのノードを始点ノードとして経路を再生成するものである。
【００１０】
請求項６の発明は、請求項１乃至請求項５のいずれかに記載の自律移動のための経路生成装置において、前記経路生成手段は、自律移動装置の現在位置から次のノードに向かう経路において、自律移動装置とそのノードとの間に自律移動装置に備えた環境認識手段で障害物が検出された場合に、その障害物を避ける位置に新たにノードを設定して、一旦そのノードに到達してから経路を再生成するのである。
【００１１】
請求項７の発明は、請求項５又は請求項６に記載の自律移動のための経路生成装置において、前記経路生成手段は、前記新たに設定したノードを、前記障害物を避け、かつ、予め地図情報に設定された通行禁止エリアを避けた位置に設定するのである。
【００１２】
請求項８の発明は、請求項１乃至請求項７のいずれかに記載の経路生成装置を用いて自律移動のための経路を生成し、その経路に基づいて移動する自律移動装置であって、目的位置や操作指令を与えるためのインターフェースと、障害物や自己位置を認識するための環境認識手段と、走行を行うための走行手段と、環境認識手段で得られた情報を元に地図上で自己の位置を認識し、かつ、障害物を回避しながら前記経路生成装置で生成された経路に基づいて目的位置まで前記走行手段を制御する走行制御手段と、を備え、前記経路生成装置の記憶手段は、予め他の移動する物体を回避するために停留できる領域を記憶し、前記走行制御手段は、前記停留開始信号検出手段が信号を検出したとき前記領域に停留するように走行手段を制御するものである。
【発明の効果】
【００１３】
請求項１の発明によれば、ノード上にない出発位置からも、移動のためのコストが最小となる適当なノードを選択して目的位置に至る経路を生成することができる。
【００１４】
請求項２の発明によれば、ノード上にない目的位置へも、移動のためのコストが最小となる適当なノードを経由した経路を生成することができる。
【００１５】
請求項３の発明によれば、予め設定した情報を用いて確実に到達可能なノードを選択して、経路を生成することができる。
【００１６】
請求項４の発明によれば、現在の環境情報を用いて、到達できないノードを避けて始点ノードを設定して、経路を生成することができる。
【００１７】
請求項５の発明によれば、障害物があるため直接向かうことができるノードがない場合でも、ノードを設定しながら経路を生成して目的位置に到達できる。
【００１８】
請求項６の発明によれば、走行中の状況に応じて障害物を避けて、障害物の陰になってそれまで得られていなかった環境情報も考慮して、柔軟に最適な経路を設定しながら走行することができる。
【００１９】
請求項７の発明によれば、接近不可能なエリアにノードを作成することがなく、効率的な経路生成ができる。
【００２０】
請求項８の発明によれば、最適経路にもとづいて走行できるとともに、走行中において、他の移動物体を回避しながら走行する、効率的な走行が可能な自律移動装置が実現される。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の一実施形態に係る自律移動のための経路生成装置及び該装置を用いた自律移動装置について、図面を参照して説明する。図１は本発明の一実施形態に係る自律移動装置１のブロック構成を示し、図２は同自律移動装置の走行状態を示す。自律移動装置１は、走行領域の地図や走行経路を構成するための複数のノードの位置及びノード間の接続関係を含む走行パラメータを記憶する記憶手段２と、記憶手段２に記憶されたノードから自律移動用の経路を構成するノードを選択しその選択したノードを用いて経路を生成する経路生成手段３とを備えている。また、これらの記憶手段２と経路生成手段３によって、経路生成装置４が構成される。自律移動装置１は、経路生成装置４を用いて自律移動のための経路を生成し、その経路に基づいて移動する。
【００２２】
また、自律移動装置１は、目的位置や操作指令を与えるためのインターフェース５と、障害物や自己位置を認識するための環境認識手段６と、電池１７を駆動源とするモータなどにより走行を行うための走行手段７と、環境認識手段６で得られた情報を元に地図上で自己の位置を認識し、かつ、障害物を回避しながら前記経路生成装置で生成された経路に基づいて目的位置まで前記走行手段を制御する走行制御手段８とを備えている。
【００２３】
また、自律移動装置１は、図２に示されるように、例えばレーザレーダや超音波センサによって構成される環境認識手段６によって、走行経路前方に存在する障害物Ｍを検出する。また、地図上の情報として記憶された壁Ｗなどの環境障害物の位置を考慮して、経路生成装置４によって最適経路が生成される。そして、自律移動装置１は、最適経路に従って、走行するとともに、走行中においても障害物Ｍを検出して、走行経路の最適化、及び走行経路の再生成を行いながら効率的、かつ柔軟に走行することができる。
【００２４】
自律移動のための経路生成装置４及びその装置を用いた自律移動装置１において、走行経路の最適化や走行効率の基本概念として、移動コストの概念が用いられている。移動コストは、２点間を移動するのに要する、時間やエネルギなどで見積もることができる。最も一般的なコストとして、２点間の直線距離、又は直線距離の和によってコストを定義でき、以下の説明においても直線距離がコストとして想定されている。また、斜面を自律移動する場合など、移動環境に応じて距離に重み付けしたコストを用いることもできる。
【００２５】
次に、自律移動装置１の走行移動中における走行制御手段８の動作を説明する。図３は走行制御手段８による経路生成制御フローを示す。自律移動装置１の走行中には、走行制御手段８において経路計画実行処理が行われる（Ｓ１）。経路計画実行処理においては、後述するように（図４参照）、経路生成装置４によって生成された経路を構成する経路上の１つのノードから次のノードに向けて移動する間の処理、例えば、障害物回避処理や経路の再生成に関する判断処理、が行われる。この経路計画実行処理に続いて、目的位置に到達したかどうかが調べられ、到着していれば経路生成制御処理は終了する（Ｓ２でＹ）。
【００２６】
また、自律移動装置１が目的位置に到達していない場合（Ｓ２でＮ）、経路生成の再計画を必要とするときにＯＮにする経路生成フラグが経路計画実行処理においてＯＮされていないかどうか調べられる。経路生成フラグがＯＮでない場合（Ｓ３でＮ）、経路計画実行処理（Ｓ１）に戻って処理が繰り返される。また、経路生成フラグがＯＮの場合（Ｓ３でＹ）、後述する経路生成処理（図５参照）が行われ（Ｓ４）、その後、経路計画実行処理（Ｓ１）に戻り、新たに生成された経路に従って処理が繰り返される。
【００２７】
次に、上述の経路計画実行処理について詳細説明する。図４は経路計画実行処理のフローを示す。自律移動装置１は、その環境認識手段６によって走行経路上の障害物の有無を探知しながら走行する。そして、障害物が検知されない場合（Ｓ１１でＮ）、経路計画を実行、すなわち次のノードに向かって走行を継続して（Ｓ１２）、経路計画実行処理を終了する。
【００２８】
また、障害物が検知された場合（Ｓ１１でＹ）、障害物回避ルートの探索が行われる（Ｓ１３）。障害物回避ルート探索は、環境認識手段６による障害物情報や、記憶手段２に記憶した環境地図情報などを参照しながら行われる。また、この探索の間に、障害物が経路上から移動して問題が解消されることもある。小規模な経路迂回による、障害物回避動作が所定の時間内に成功した場合（Ｓ１４でＹ）、障害物回避計画を実行、すなわち、障害物を回避して次のノードに向かう走行を継続して（Ｓ１５）、経路計画実行処理を終了する。
【００２９】
また、障害物回避動作が所定の時間内に成功しなかった場合（Ｓ１４でＮ）、ノード生成型障害物回避ルート探索が行われる（Ｓ１６）。この、ノード生成型障害物回避ルート探索は、現在の走行経路から外れることによってのみ障害物回避が可能な場合に行われるものである。経路外に新たにノードを生成し、一旦その経路を経由して、再度もとの経路に戻ることで、もとの走行計画の成就が図られる。そのようなノード生成型障害物回避ルート探索が成功した場合（Ｓ１７でＹ）、自律移動装置１は、障害物を回避するために新たに生成されたノードへの走行を開始して、障害物回避計画が実行され、本来の次のノードまで走行して（Ｓ１５）、経路計画実行処理が終了する。
【００３０】
また、ノード生成型障害物回避ルート探索が不成功の場合（Ｓ１７でＮ）、経路生成フラグがＯＮにされ（Ｓ１８）、経路計画実行処理が終了する。このフラグ情報は、前述のように、走行制御処理（図３）における経路生成開始要否の判断に用いられる。
【００３１】
次に、前述の経路生成処理について詳細説明する。図５は経路生成処理のフローを示す。経路生成処理は、始点ノード、終点ノードの選択処理（Ｓ４１）、選択された始点ノード、終点ノードを最小コストで結ぶ経路の探索（Ｓ４２）、経路探索によって生成された経路の見直しを行う始点ノード、終点ノードの再選択処理（Ｓ４３）、及び生成された経路の記憶（Ｓ４４）という手順で行われる。個々の詳細な処理について後述される。
【００３２】
ここで用語の説明をする。自律移動装置１は、インターフェイス５を介して入力して指定された出発位置Ｐｓから目的位置Ｐｇへと走行する。走行中に経路を見直しながら進む場合、各時点における現在位置は新たな出発位置であるため、出発位置と同じ符号を用いて現在位置Ｐｓと表すことにする。目的位置Ｐｇは移動計画中において変わることはない。経路生成手段３によって生成される経路は、記憶手段２に記憶された環境地図に予め定められた複数のノードを経由するように生成される。
【００３３】
ところで、出発位置（現在位置）Ｐｓと目的位置Ｐｇは、必ずしもノード上の点にあるとは限らず、自律移動装置１の柔軟な利用の面から、任意の位置を与えられる方が望ましい。そこで、現在位置Ｐｓと目的位置Ｐｇのそれぞれの位置から経路上の最初、又は最後のノードを、それぞれ、始点ノードＰｓ１、終点ノードＰｇｅと定義する。現在位置Ｐｓ又は目的位置Ｐｇがノード上にある場合、以下の説明においてそれらのノードは始点又は終点ノードとされる。また、現在位置Ｐｓは、各時点における生成された経路上における自律移動装１の出発点であり、その位置は、自律移動装置の有する自己位置認識機能（記憶手段に記憶された地図情報、及び環境認識手段、又は走行手段からの走行情報に基づく）によって決定される。
【００３４】
次に、上記の経路生成処理の各ステップＳ４１〜Ｓ４４について説明する。図６は経路生成を説明する走行領域を示し、図７は始点・終点ノード選択処理フローを示し、図８は始点・終点ノード再選択処理フローを示し、図９は生成された経路の基本構成を示す。
【００３５】
まず、具体的な始点ノードＰｓ１、終点ノードＰｇｅの選択方法について説明する。図６（ａ）に示されるように、走行路周辺の環境地図情報として、例えば、壁Ｗ１〜Ｗ３の情報、及び走行禁止エリア（不図示）情報、走行路を生成するために必要なノードＮ０〜Ｎ７情報が予め決められ、記憶手段２に記憶される。
【００３６】
ここで、記憶された環境地図情報、すなわち内部地図情報について説明する。図１３は内部地図情報の概念とデータファイル構成を示す。内部地図ＭＰ１には、図１３（ａ）に示すように、例えば、２つの直線状の壁Ｗ１，Ｗ２が記憶されている。内部地図ＭＰ１内では、壁が線分の集まりで表現され、壁の位置及び形状は、壁の構成線分の端点ＷＬ０，ＷＬ１，ＷＬ２のｘ、ｙ座標値で決定される。例えば、壁Ｗ１は、点ＷＬ０（５．０，０．０）と点ＷＬ１（５．０、３．０）で表される。このような壁のデータは、図１３（ｂ）に示すように、例えば、テキストデータファイルＭａｐＴｘｔとして、各行Ｌ１，Ｌ２毎に１つの壁を４つの実数値で表現して記憶されている。走行禁止エリアや厚みを有する壁についても、同様に線分によって表現され、記憶される。
【００３７】
図６（ａ）に戻って経路生成処理の説明を続ける。ノード情報として、例えば走行可能な走行路の曲がり角が接点（ノード）とされ、そのノードの座標情報、ノード間が一方通行なのか双方通行なのかなどの情報、さらにはノード間を走行するために必要なコスト（距離、時間、エネルギなどの評価値）情報が設定される。図６（ａ）において、矢印で接続されているノード間は、双方向走行可能なことを示している。
【００３８】
ここで、ノード情報のデータファイル構造について説明する。図１４はノードを含む内部地図情報の概念とノードデータファイル構成を示す。内部地図ＭＰ２には、図１４（ａ）に示すように、ノードＮＤ０，ＮＤ１，ＮＤ２の位置と各ノード間の接続関係が記憶されている。このようなノードに関するデータは、図１４（ｂ）に示すように、例えば、テキストデータファイルＮｏｄｅＴｘｔとして、記憶されている。ファイルの中身は、内部地図ＭＰ２の場合、１行目にノードの個数３が記載され、また、２〜４行目にはノード位置情報が、ノード名称Ｂ１，ノード番号Ｂ２，ノードＸＹ座標Ｂ３による第１グループとして記載されている。また、区切り用の空白行に続いて、ノード間の連結情報が、ノード名称Ｂ１，ノード番号Ｂ２，各ノード毎の連結数Ｂ４、連結されるノード番号Ｂ５による第２グループとして記載されている。例えば、ノード番号１のノードＮＤ２は、２とのノードＮＤ０、ＮＤ２に連結されている。また、ノードＮＤ０からノードＮＤ１への連結がないのでこの間は、一方通行であることが分かる。
【００３９】
再び図６に戻って経路生成処理の説明を続ける。始点ノードＰｓ１の選択について説明する。図６（ｂ）において、現在位置Ｐｓから直線距離の短い３つのノードＮ０，Ｎ１，Ｎ７に向かって矢印が示されている。これらの各ノードまでの距離の短い順に始点ノード候補がソート（並べ替え）され、環境地図情報又はセンサ（環境認識手段６）で検知された物体までの距離情報に基いて、到達出来ないノードを上位の候補から外すことによって得られる最上位（最短距離）のものが始点ノードに決定される。具体例では、まず現在位置Ｐｓから距離が短いノード順に通れるかどうか調べられる。
【００４０】
ここで、ノード間の通行可能性の判断処理について説明する。図１５はノードを含む内部地図情報の概念と通行可能性判断における場合分けを示す。内部地図ＭＰ３には、図１５（ａ）に示すように、現在位置Ｐｓ、ノードＮＤ０〜ＮＤ７、壁Ｗ１〜Ｗ３、及び各壁の構造を表す壁の端点の座標ＷＬ０〜ＷＬ４が記憶されている。これらの情報をもとに、例えば、現在位置ＰｓからノードＮＤ７へ通行可能かどうかが、以下のようにして判断される。すなわち、通行可能性は、壁を表す線分ＷＬ０−ＷＬ１と、直線走行経路を表す線分Ｐｓ−ＮＤ７との交点の有無を調べ、交点がなければ通行可能とされる。
【００４１】
２つの線分の交点の有無は、図１５（ｂ）（ｃ）に示すように、線分Ｐｓ−ＮＤ７を線分Ａ−Ｂ、その直線の式Ｙ＝α・Ｘ＋β、線分ＷＬ０−ＷＬ１を線分Ｃ−Ｄ、その直線の式Ｙ＝γ・Ｘ＋σとして、これらの直線の式を用いて調べられる。図１５（ｂ）（ｃ）に示すように、線分が交点を有する状態は、（Ｙａ−α・Ｘａ−β）（Ｙｂ−α・Ｘｂ−β）＜０、かつ（Ｙａ−γ・Ｘａ−σ）（Ｙｂ−γ・Ｘｂ−σ）＜０で表される。この場合、通行不可である。また、図１５（ｄ）に示す状態は、（Ｙａ−α・Ｘａ−β）（Ｙｂ−α・Ｘｂ−β）＜０、であるが（Ｙａ−γ・Ｘａ−σ）（Ｙｂ−γ・Ｘｂ−σ）＞０である。この場合、線分間に交点はなく、従って通行可となる。
【００４２】
再び図６に戻って経路生成処理の説明を続ける。一番近いノードＮ７が地図情報から通ることのできないことが分かるため、ノードＮ７が候補から除外される。次に近いノードであるＮ０へは到達することができるため、このノードＮ０が始点ノードＰｓ１として決定される。同様にして、目的位置Ｐｇに対する終点ノードＰｇｅとしてノードＮ３が決定される。
【００４３】
上述の始点ノードＰｓ１，終点ノードＰｇｅの選択処理について、図７のフローを参照して説明する。まず、地図上の（ｍ＋１）個のノード群Ｎｉ（ｉ＝０〜ｍ）、現在位置Ｐｓ、目的位置Ｐｇの位置情報（座標）が読み込まれる（Ｓ１０１）。続いて、現在位置Ｐｓに近い順にソートしたノード群Ｎｓｉ（ｉ＝０〜ｎ）が生成される（Ｓ１０２）。次に、引数ｉがｉ＝０と初期化され（Ｓ１０３）、ノードＮｓｉ、現在位置Ｐｓ間の走行可能性が調べられる。走行可能であれば（Ｓ１０４でＹ）、ノードＮｓｉが始点ノードＮｓ１として決定される（Ｓ１０５）。
【００４４】
また、ノードＮｓｉ、現在位置Ｐｓ間が走行不可能であれば（Ｓ１０４でＮ）、引数がインクリメントされ（Ｓ１０６）、他に調べるべきノードが残っていれば（Ｓ１０７でＹ）再度ステップＳ１０４が実行される。また、調べるべきノードがない場合（Ｓ１０７でＮ）、始点ノードＰｓ１として選択されるノードはないとされ（Ｓ１０８）、経路生成失敗とされて処理が終了する（Ｓ１１６）。
【００４５】
また、終点ノードＰｇｅの選択については、上記始点ノードＰｓ１の選択と同様の手順で、ステップＳ１０９〜Ｓ１１６において処理が行われてＰｇｅが選択され（Ｓ１１２）、又は終点ノードＰｇｅとして選択されるノードはないとされ（Ｓ１１５）、経路生成失敗とされて処理が終了する（Ｓ１１６）。
【００４６】
次に、選択された始点ノードＰｓ１、終点ノードＰｇｅを最小コストで結ぶ最適経路を選び出す経路の探索（図５におけるステップＳ４２の処理）について説明する。この経路探索に用いられるアルゴリズムは、公知のものであり、アルゴリズムＡ＊と呼ばれるものである（新世代工学シリーズ「ロボット工学」白井良明編著、ｐｐ．１２０−１２４参照）。アルゴリズムＡ＊は、自律移動装置の走行領域における設定されたノードＮのコストｆ（Ｎ）を計算しながら経路を探索する。このコストｆ（Ｎ）は、始点ノードＮｓ１から途中ノードＮを経由して終点ノードＮｇｅに至るときの最小コスト（例えば、最短距離）の推定値であり、ｆ（Ｎ）＝ｇ（Ｎ）＋ｈ（Ｎ）で計算される。ここで、ｇ（Ｎ）は始点ノードＮｓ１と途中ノードＮの間の現時点での最小コストであり、ｈ（Ｎ）は、途中ノードＮと終点ノードＮｇｅの間の最小コストの推定値である。
【００４７】
ここで、１つの用語「展開」と２つのリスト「開リスト」、「閉リスト」を導入する。「開リスト（ＯＰＥＮ）」は、経路生成の対象となる例えばノードＭをコストｆ（Ｍ）と共に登録して管理し、さらに、処理手順に従って、そのノードＭから直接到達できる全てのノードＭ’をそのコストｆ（Ｍ’）とともに登録して管理するリストである。このリストＯＰＥＮの中のノードＭ’はコストｆで昇順にソートして管理される。このように、ノードＭに関連するノードＭ’を登録する操作を「ノードＭを展開する」という。また、「閉リスト（ＣＬＯＳＥＤ）」は、既に展開されたノードを「開リスト（ＯＰＥＮ）」から取り出して、その展開されたノードを管理するリストである。
【００４８】
アルゴリズムＡ＊による経路探索の手続は以下［１］〜［６］のようなものである。［１］始点ノードＮｓ１をＯＰＥＮに登録する。［２］ＯＰＥＮが空なら、経路は存在しないのでアルゴリズムを終了する。［３］ＯＰＥＮから先頭の（コストｆが最小）ノードＮを取り出し、それをＣＬＯＳＥＤに移す。［４］もし、ノードＮが終点ノードＮｇｅであれば、通って来たノードを順々に後戻りする。そして、始点ノードＮｓ１に達したら、ここまでに辿ったノードにより経路が生成されたことになり、アルゴリズムを終了する。
【００４９】
［５］ノードＮが終点ノードＮｇｅでなければ、ノードＮを「展開」し、その子孫ノードＮ’がどこから来たか記録する（プログラム的にはノードＮへポインタを返す）。そして、全ての子孫ノードＮ’に対して以下の２つの操作を行う。
【００５０】
（操作１）ノードＮ’がＯＰＥＮ又はＣＬＯＳＥＤに存在しなければ、それは新たに探索されたノードである。そこで、ノードＮ’から終点ノードＮｇｅまでの最小コストの推定値ｈ（Ｎ’）、次に推定値ｆ（Ｎ’）＝ｇ（Ｎ’）＋ｈ（Ｎ’）を計算する。ここで、ｇ（Ｎ’）＝ｇ（Ｎ）＋ｃ（Ｎ，Ｎ’）、ｇ（Ｎｓ１）＝０であり、ｃ（Ｎ，Ｎ’）はノードＮとノードＮ’を直接結ぶコストである。そして、ノードＮ’を推定値ｆ（Ｎ’）とともにＯＰＥＮに登録する。
【００５１】
（操作２）ノードＮがＯＰＥＮ又はＣＬＯＳＥＤに存在すれば、それは既に探索されたノードである。そこで、最小値ｇ（Ｎ’）をもたらす経路に経路を変更する（ポインタを付け替える）。そしてこの変更が発生したときのみ、ノードＮ’がＣＬＯＳＥＤに存在したらそれをＯＰＥＮに戻した後、推定値ｆ（Ｎ’）＝ｇ（Ｎ’）＋ｈ（Ｎ’）を計算する。
【００５２】
［６］この後、前記［２］へ戻って経路探索手続を繰り返す。
【００５３】
上述のアルゴリズムは、全てのノードにおいて、推定値ｈがその真の値よりも小さいか等しいとき、アルゴリズムＡ＊と呼ばれる。このとき、最短経路上のノードは見過ごされることなく必ず調べられ、始点ノードＮｓ１から終点ノードＮｇｅへの経路として、満足経路（コストの合計が最小でない経路）ではなく、最適経路（コストの合計が最小の経路）が生成される。例えば、Ａ点からＢ点への特選距離を障害物を無視してコスト推定値ｈとすると、推定値ｈは、障害物を考慮した真のコスト値よりも常に小さいか等しくなる。
【００５４】
上述のアルゴリズムＡ＊を用いて探索して決定された経路が、前述の図６（ｃ）において、ノードＮ０，Ｎ１，Ｎ２，Ｎ３を結ぶ経路として示されている。ただし、このような最適経路探索については、アルゴリズムＡ＊によらずに、その他の経路探索方法を用いて行ってもよい。
【００５５】
次に、経路探索によって生成された経路を見直す処理である、始点ノードＰｓ１、終点ノードＰｇｅの再選択処理（図５におけるステップＳ４３の処理）について説明する。まず図６（ｄ）を参照して詳細説明し、その後、図８による始点・終点ノード再選択処理フローを説明する。図６（ｄ）に示される探索された経路において、ノードＮ０が始点ノードＰｓ１となっている。経路生成手段３は、生成した経路において現在位置Ｐｓから始点ノードＰｓ１を経由することなく始点ノードＰｓ１の次の経路上のノードＮ１に向かうコストが、始点ノードＰｓ１を経由するときのコストよりも小さい場合、最初に選択した始点ノードＰｓ１の替わりにその始点ノードＰｓ１の次のノードＮ１を新たな始点ノードＰｓ１として選択する。これは始点ノード再選択処理であり、同様に終点ノード再選択処理が行われる。
【００５６】
また、地図情報及びセンサ情報を用いて障害物が存在するかどうかがチェックされ、その結果、障害物が存在すれば、ノード間のコストは無限大とされる。そこで、図６（ｄ）に示される経路の場合、現在位置ＰｓとノードＮ１の間には壁Ｗ２が存在するため、この間のコストは無限大とされるので、始点ノードＰｓ１の見直し選択は行われない。
【００５７】
図６（ｄ）に示される終点ノートＰｇｅについて見ると、ノードＮ２から終点ノードＰｇｅを経由して目的位置Ｐｇに至るよりも、ノードＮ２からノードＰｇｅを経由せずに直接目的位置Ｐｇへ行く方がコストが少ない（走行距離が少ない）ことが分かる。従って、終点ノードＰｇｅについては、再選択処理が行われて、ノードＮ２が新たな終点ノードＰｇｅとして選択される。
【００５８】
上述の始点・終点ノード再選択処理について、図８のフロー、及び図９の経路の基本構成を参照して説明する。ここに説明する処理は、経路を構成するノードを減らし、コストを減らす処理である。まず、経路探索結果である経路を構成するノードＮｐｋ（ｋ＝１〜ｅ）、及び現在位置Ｐｓ、目的位置Ｐｇ、始点ノードＮｐ１、終点ノードＮｐｅが読み込まれる（Ｓ２０１）。さらに地図情報、センサ情報が読み込まれる。次に、経路探索結果Ｎｐｋにおいて同じ点が続いていないか調べられ、重複点が削除される（Ｓ２０２）。
【００５９】
続いて、図９（ａ）に示されるように、ｅ＝１の場合（Ｓ２０３でＹ）、現在位置Ｐｓと目的位置Ｐｇ間が、地図情報及びセンサ情報を用いて、障害物が存在するかどうかがチェックされ、走行可能であれば（Ｓ２０４でＹ）、経路上のノードＮｐ１が除外され、経路は現在位置Ｐｓから目的位置Ｐｇに２点間を直行する経路とされノード再選択処理が終了する。
【００６０】
また、現在位置Ｐｓと目的位置Ｐｇ間について、地図情報及びセンサ情報を用いて、その間に障害物が存在するかどうかがチェックされ、走行不可能であれば（Ｓ２０４でＮ）、経路上のノードＮｐ１はそのまま残され、経路は現在位置ＰｓからノードＮｐ１を経由して目的位置Ｐｇに至る経路のままとされノード再選択処理が終了する。
【００６１】
また、図９（ｂ）に示されるように、ｅ＝２の場合（Ｓ２０３でＮ、Ｓ２０６でＹ）、現在位置Ｐｓと目的位置Ｐｇ間について、地図情報及びセンサ情報を用いて、その間に障害物が存在するかどうかがチェックされ、走行可能であれば（Ｓ２０７でＹ）、経路上のノードＮｐ１、Ｎｐ２が除外され、経路は現在位置Ｐｓから目的位置Ｐｇに２点間を直行する経路とされノード再選択処理が終了する。
【００６２】
また、現在位置Ｐｓと目的位置Ｐｇ間が、走行不可能であれば（Ｓ２０７でＮ）、さらに、現在位置ＰｓとノードＮｐ２間が走行可能かどうか調べられ、走行不可能であれば（Ｓ２０９でＮ）、さらに、ノードＮｐ１と目的位置Ｐｇ間が走行可能かどうか調べられ、走行不可能であれば（Ｓ２１０でＮ）、経路上のノードＮｐ１、Ｎｐ２はそのまま残され、経路の見直しなしにノード再選択処理が終了する。
【００６３】
ノードＮｐ１と目的位置Ｐｇ間が走行可能であれば（Ｓ２１０でＹ）、経路上のノードＮｐ２が除去され（Ｓ２１１）、ノードＮｐ１を経由する３点間の経路とされノード再選択処理が終了する。
【００６４】
また、現在位置ＰｓとノードＮｐ２間が走行可能であれば（Ｓ２０９でＹ）、さらに、ノードＮｐ１と目的位置Ｐｇ間が走行可能かどうか調べられ、走行不可能であれば（Ｓ２１２でＮ）、経路上のノードＮｐ１が除去され（Ｓ２１３）、ノードＮｐ２を経由する３点間の経路とされノード再選択処理が終了する。
【００６５】
また、ノードＮｐ１と目的位置Ｐｇ間が走行可能であれば（Ｓ２１２でＹ）、ノードＮｐ１とノードＮｐ２のどちらを除去するか決めるために、ノードＮｐ１を経由する距離Ｌ１＝（Ｐｓ−Ｎｐ１−Ｐｇ間距離）と、ノードＮｐ２を経由する距離Ｌ２＝（Ｐｓ−Ｎｐ２−Ｐｇ間距離）とが計算され（Ｓ２１４）、その大小が比較される。距離Ｌ２が距離Ｌ１より短い場合（Ｓ２１４でＹ）、ノードＮｐ１が除外され（Ｓ２１３）、そうでない場合（Ｓ２１４でＮ）、ノードＮｐ２が除外される（Ｓ２１６）。この結果、３点間の経路とされノード再選択処理が終了する。
【００６６】
また、図９（ｃ）に示されるように、２＜ｅの場合（Ｓ２１７でＹ）、現在位置ＰｓとノードＮｐ２間が走行可能かどうか調べられ、走行不可能であればそのままとされ（Ｓ２１８でＮ）、走行可能であれば（Ｓ２１８でＹ）、ノードＮｐ１が除外され、ノードＮｐ２が新たな始点ノードとされる（Ｓ２１９）。さらに、終点ノードＮｐｅの１つ手前のノードＮｐ（ｅ−１）と目的位置Ｐｇ間が走行可能かどうか調べられ、走行不可能であれば（Ｓ２２０でＮ）、ノード再選択処理が終了する。
【００６７】
また、ノードＮｐ（ｅ−１）と目的位置Ｐｇ間が走行可能であれば（Ｓ２２０でＹ）、終点ノードＮｐｅが除外され、ノードＮｐ（ｅ−１）が新たな終点ノードとされ、ノード再選択処理が終了する。
【００６８】
上述の始点・終点ノード再選択処理が行われた後、決定された経路が、前述の図６（ｅ）に示されている。なお、上述の２＜ｅの場合におけるノード再選択処理は、得られた結果の経路に対して再度同様の処理を繰り返して行ってもよい。
【００６９】
次に、自律移動装置１が走行中に障害物を検知した場合における経路生成装置４による経路の再生成について説明する。経路生成手段３は、経路上に障害物が現れた場合、次のような対応を行う。経路生成手段３は、選択した始点ノード又は終点ノードと自律移動装置の現在位置との間に障害物が検出された場合に、その間のコストを無限大とすることにより、到達できないノードを避けて、経路を生成する。また、経路生成手段３は、その障害物を避ける位置に新たにノードを設定して、そのノードを始点ノードとして経路を再生成することで、直接向かう経路がないノードに到達できるようにする。
【００７０】
また、経路生成手段３は、その障害物を避ける位置に新たにノードを設定して、一旦そのノードに到達してから経路を再生成することで、走行中の状況に応じて障害物を避けて、柔軟に最適な経路を設定しながら走行する。これらの場合、経路生成手段３は、新たに設定したノードを、障害物を避け、かつ、予め地図情報として設定された通行禁止エリアを避けた位置に設定することで、接近不可能なエリアにノードを作成することがなく、効率的な経路生成を行う。
【００７１】
具体的な経路を参照して、障害物を検知した場合の経路の再生成について説明する。図１０は非固定障害物の存在する走行領域を示す。図１０（ａ）に示すように、自律移動装置１が経路生成装置を用いて経路生成を行って、経路Ｐｓ，Ｎ０，Ｎ１，Ｎ２，Ｐｇに沿って移動している場合について述べる。自律移動装置１は、図１０（ｂ）に示すように、非固定障害物Ｍ１が走行経路上に現れたことをセンサで検知した場合、既存の障害物回避アルゴリズムに従って、障害物回避ルート計算・動作が開始される。そして、経路上の進行方向前方に大きな障害物が位置するときなどのように、回避時間が大となる場合、予め定めた所定の制限時間内に、現在位置と向かっているノード又は目的位置との間における予め定めた距離以内に、障害物の検知がなくならない場合には回避動作が打ち切られる。
【００７２】
続いて、ノード生成型障害物回避ルート探索が行われる。経路生成装置は、地図情報とセンサ情報による空き空間、及び進行方向の環境情報などから、仮のノードＮＸを新たに生成する（仮のノードＮＸの生成方法については後述）。そして、経路生成装置は、この仮のノードＮＸから目的位置Ｐｇに至るまでの経路を、前出の図６及び図６に関連して説明した処理フロー（図７，図８）に従って生成する。その生成された経路と自律移動装置１の現在位置Ｐｓとを連結することにより、目的位置Ｐｇまでの経路が再生成される。このような経路の再生成の際には、既に作られている目的位置Ｐｇまでの経路の修正という方法をとってもよい。このようなノード生成型障害物回避ルートの探索方法を探索方法（１）とする。
【００７３】
また、図１０（ｃ）に示すように、出現した非固定障害物Ｍ２のようにその種類によっては、仮ノードＮＸから目的位置Ｐｇに至る経路の生成を、仮ノードＮＸに到着後に行う方が、視界が開けてセンサ情報が有効に利用できることなどから、回避ルート探索が容易となることがある。そこで、計算時間の観点で有利となる場合もあるため、自律移動装置１の走行領域を小エリアに区分して、エリア毎に回避ルート探索方法を切り替えることが有効となる。このようなノード生成型障害物回避ルートの探索方法を探索方法（２）とする。
【００７４】
上述の探索方法（１）と探索方法（２）について比較検討する。図１０（ｃ）において、自律移動装置１が現在位置Ｐｓの位置にいるときには、非固定障害物Ｍ２の奥行きまで分からないため、探索方法（１）の方法によると、前述の図１０（ｂ）に示される新たな経路と同じ結果の経路が得られる。ところが、図１０（ｃ）に示すように仮ノードＮＸに到着した後だと、非固定障害物Ｍ２の情報をより詳しく得ることができるので、経路生成のための計算時間のロスが少なくでき、また、生成される経路も移動コストの少ないものが得られる可能性がある。仮ノードＮＸに到着後に経路の再生成を行う場合でも、既に作られている目的位置Ｐｇまでの経路を再利用することができる。
【００７５】
上述のノード生成型障害物回避ルートの探索方法である探索方法（１）、及び探索方法（２）が利用できない場合について説明する。図１０（ｄ）に示されるように、非固定障害物Ｍ３によって経路が完全に塞がれているなどの理由で、非固定障害物Ｍ３の近傍において仮ノードＮＸの生成が不可能であると判断される場合、仮ノードＮＸの設定は行わずに、前出の図６及び図６に関連して説明した処理フロー（図７，図８）に従って経路の再生成が行われる。すなわち、ノードＮ１のところから大きく迂回する、新たにノードＮ１，Ｎ６，Ｎ５，Ｎ４，Ｎ３，Ｐｇを結ぶ経路が生成される。
【００７６】
次に、走行中の自律移動装置が障害物を検知した場合の、ノード生成型障害物回避ルートの探索方法（１）に基づく経路の再生成についてその全体を説明する。図１１は非固定障害物Ｍ４の存在する走行領域を示す。図１１（ａ）に示すように、自律移動装置１が経路生成装置を用いて経路生成を行って、ノードＰｓ，Ｎ０，Ｎ１，Ｎ２，Ｐｇを結ぶ経路に沿って移動している場合について述べる。
【００７７】
自律移動装置１は、図１１（ｂ）に示すように、非固定障害物Ｍ４が走行経路上に現れたことをセンサで検知した場合、走行経路上を自律移動しながら、まず、既存の障害物回避アルゴリズムによる障害物回避計算・動作を行う。
【００７８】
そして、障害物回避計算・動作が大であるとき（非固定障害物Ｍ４に接近しすぎる場合など）、経路生成装置は、地図情報、センサ情報による空き空間、及び進行方向の環境情報などから、図１１（ｃ）に示すように、仮のノードＮＸを新たに生成する。
【００７９】
続いて経路生成装置は、仮のノードＮＸから目的位置Ｐｇに至るまでの経路を新たに生成する。仮のノードＮＸから各ノードＮｉまでの距離の短い順に始点ノードの候補をソートし、地図情報又はセンサ情報に基いて、到達できないノードをソートして順位付けした上位の（距離の近い）候補から外すことによって、最後に得られたノードを（仮の）始点ノードＰｓ１に決定する。具体的には、図１１（ｄ）に示すように、まず仮のノードＮＸを現在位置として、この仮のノードＮＸから距離が近いノード順に通れるかどうかが調べられる。一番近いノードＮ０へは仮のノードＮＸから到達することができるため、ノードＮ０が（仮の）始点ノードＰＳ１として決定される。
【００８０】
目的位置Ｐｇにおける終点ノードＰｇｅについても、始点ノードＰｓ１の選択決定と同様の処理が行われ、ノードＮ３が終点ノードＰｇｅとされる。
【００８１】
上述において決定された始点ノードＰｓ１、終点ノードＰｇｅについて、経路生成手段によって、アルゴリズムＡ＊を用いて経路探索が行われる。経路探索の結果生成された経路は、図１１（ｅ）に示されるようになる。
【００８２】
続いて、生成された経路に基づいて、始点ノードＰｓ１、終点ノードＰｇｅの見直しが行われる。図１１（ｆ）に示されるように、探索された経路において、それぞれ仮ノードＮＸとそこから２番目のノードＮ１との間、及び目的位置Ｐｇとそこから経路を逆戻りする２番目のノードＮ２との間について、地図情報及びセンサ情報からそれらの間に障害物が存在するかどうかが調べられる。いずれか又は両方について障害物が存在しなければ、そのいずれか又は両方の２番目のノードがそれぞれ新たに始点ノードＰｓ１、終点ノードＰｇｅとされる。図１１に示す経路の場合、ノードＮ０が経路から除去され、新たにノードＮ１が始点ノードＰｓ１とされる。また、ノードＮ３が除去され、新たにノードＮ２が終点ノードＰｇｅとされる。このように経路からノードが除去されることにより、確実に走行コストが減少する方向に向かう（三角形の２辺の長さの和は他の１辺の長さより大きい）。
【００８３】
このようにして、経路上に出現した非固定障害物Ｍ４を回避するため、仮のノードＮＸが設定され、そのノードＮＸから目的位置Ｐｇまで新たに経路が生成された結果が、図１１（ｇ）に示されている。新たに生成された経路に、自律移動装置１の現在位置Ｐｓから仮のノードＮＸまでの経路を追加し、最終の経路が生成される。自律移動装置１は、この最終経路に従って移動し、障害物を回避して目的位置まで到達することが可能となる。
【００８４】
次に、上述した仮のノードＮＸの生成方法について説明する。図１２（ａ）（ｂ）は自律移動装置が障害物を検知し、仮のノードＮＸを生成する状況を示す。自律移動装置１は、環境認識手段６として、例えばレーザレーダを有し、進行方向前方を所定の一定角度間隔Δθで走査して障害物の方向と距離を検知する。レーザレーダの替わりに、複数の測距型超音波センサを、進行方向を中心として放射状の検知エリアとなるように配置したものを用いても、以下の方法を同様に適用できる。自律移動装置１が、次の目的のノードＮｎｅｘｔに向かって走行中に前方の障害物Ｍを検知し、その障害物Ｍの端部が、レーザビームＬＢ０により走査角φの位置に、距離Ｄとして見い出されたとする。その後、レーザビームの走査角を角度間隔Δθづつ増加させ、ビームをレーザビームＬＢ１，ＬＢ２、・・と走査した結果、ある角度まで、半径Ｄの円内に障害物が検知されなかったとする。
【００８５】
ところで、自律移動装置１は、装置本体の幅Ｗと長さＬに、所定の余裕を持たせて幅ＨＷ、長さＨＬとして、幅ＨＷ以上、奥行きＨＬ以上の空間があれば、その空間に移動することができるものとする。また、図１２（ｂ）に示すように、距離Ｄにおけるレーザビームのスキャン幅ｄは、ｄ≒Ｄ・ｓｉｎ（Δθ）である。そこで、ｋを整数として、ＨＷ＜ｋ×Ｄであれば、すなわち、少なくとも角度ｋ×Δθの間において、少なくとも距離Ｄ＋ＨＬの範囲に障害物が検知されなかったら、自律移動装置１は、障害物Ｍより前方に移動することができる。
【００８６】
そこで、図１２（ｂ）の場合、レーザビームＬＢ２とＬＢ３の間の角度であって、自律移動装置１（の環境認識手段６）からの距離Ｄ＋ＨＬの位置が、仮のノードＮＸの位置として決定される。障害物Ｍの左右に通行可能領域がある場合、仮のノードＮＸを障害物Ｍの左右いずれにも設けることができるが、現在の目的のノードＮｎｅｘｔへの最短距離となる位置、すなわち、正面方向からのふれ角度が小さい方に仮のノードＮＸを設けるものとする。
【００８７】
また、仮のノードＮＸの決定に際して、環境認識手段６で検知された情報だけでなく、地図情報に記憶された壁の情報を用いることによってより効率的な経路生成ができる。すなわち、壁の始点・終点情報から壁の式が得られ、自律移動装置１の自己位置・方向、及び、レーザレーダによる走査方向が既知であるから、自律移動装置１から壁までの距離と方向が容易に算出できる。また、計算の対象とする壁として、自律移動装置１から所定の距離に存在するもののみを選択することにより、計算効率を上げることができる。なお、本発明は、上記構成に限られることなく種々の変形が可能である。
【図面の簡単な説明】
【００８８】
【図１】本発明の一実施形態に係る自律移動装置のブロック構成図。
【図２】同上自律移動装置の走行状態を示す平面図。
【図３】同上自律移動装置の走行制御処理フロー図。
【図４】同上自律移動装置の経路計画実行処理フロー図。
【図５】本発明の一実施形態に係る自律移動のための経路生成装置における経路生成処理フロー図。
【図６】（ａ）〜（ｅ）は同上経路生成装置による経路生成を説明する走行領域の平面図。
【図７】同上経路生成装置による始点・終点ノード選択処理フロー図。
【図８】同上経路生成装置による始点・終点ノード再選択処理フロー図。
【図９】（ａ）〜（ｃ）は同上経路生成装置により生成された経路の図。
【図１０】（ａ）〜（ｄ）は同上経路生成装置による走行時の障害物検知時の経路再生成を説明する走行領域の平面図。
【図１１】（ａ）〜（ｇ）は同上経路生成装置による走行時の障害物検知時の他の経路再生成を説明する走行領域の平面図。
【図１２】（ａ）（ｂ）は同上経路生成装置による仮ノードの生成方法を説明する平面図。
【図１３】（ａ）は同上経路生成装置における内部地図情報の概念図、（ｂ）は（ａ）の内部地図情報のデータファイル構成図。
【図１４】（ａ）は同上経路生成装置におけるノードを含む内部地図情報の概念図、（ｂ）は（ａ）の内部地図情報におけるノードのデータファイル構成図。
【図１５】（ａ）は同上経路生成装置におけるノードを含む内部地図情報の概念図、（ｂ）〜（ｄ）は同上経路生成装置における通行可能性判断処理の説明図。
【符号の説明】
【００８９】
１    自律移動装置
２    記憶手段
３    経路生成手段
４    経路生成装置
５    インターフェイス
６    環境認識手段
７    走行手段
８    走行制御手段
Ｎｓ１、Ｎｐ１    始点ノード
Ｎｇｅ、Ｎｐｅ    終点ノード
Ｐｓ    現在位置
Ｐｇ    目的位置
【図１】
2005050105.tif 000003
【図２】
2005050105.tif 000004
【図３】
2005050105.tif 000005
【図４】
2005050105.tif 000006
【図５】
2005050105.tif 000007
【図６】
2005050105.tif 000008
【図７】
2005050105.tif 000009
【図８】
2005050105.tif 000010
【図９】
2005050105.tif 000011
【図１０】
2005050105.tif 000012
【図１１】
2005050105.tif 000013
【図１２】
2005050105.tif 000014
【図１３】
2005050105.tif 000015
【図１４】
2005050105.tif 000016
【図１５】
2005050105.tif 000017