１２．６　未知環境において接触センサによるAGVの走行経路生成　　２００９−７−７

実行ファイル 3-12-6AGVpathsearch2exe

・未知環境において障害物回避しながら始点から目標点に到る経路を探索する問題である．

・走りながら障害物を認識して衝突回避する経路を探索する．

・探索法の１つとして次の手順で終点に到る経路を生成することを考える．

（１）「参照経路」を設定する．

（２）その上を走行する．

（３）障害物に接触したら障害物沿いに走行する．

（４）「参照経路」に戻ったらそれに沿って走行する．

・生成経路を改善したいときは，「参照経路」を変えて上記探索を繰り返す．

・「参照経路」とは，未知の障害物はないと仮定して作成した経路である．

（１）最初は自由空間経路とする．

（２）経路生成によって既知となった部分的な障害物情報を基に，12.5節で述べたように限界等高線間の共通接線からなる「参照経路」を作成する．

・これらの「参照経路」作成と走行による経路生成を繰り返すと，いずれは最適な経路が得られるはずである．

・しかし，複雑な環境で終点に到る経路が存在するとして，必ずこの方法で見つけられるとは断言できない．シミュレーションによって不可能なケースがあることが分かるかも知れない．

・障害物の認識には，AGVの周囲に備えた接触センサにより障害物の限界点に達して初めてその位置（及び障害物輪郭法線方向）を知ることができる場合と，TVカメラまたは走査型超音波センサにより前方に見える視角範囲内での障害物の形状とAGVからの距離が分かる場合とがある．

・ここでは接触センサを頼りに障害物を回避しながら走行し，経路を探索するシミュレーションを行う．

・試行を繰り返して障害物の全容を知り得る．障害物の全てが分かれば既知環境の経路探索問題となり，これは第12.5節のように人が関与して最適経路を決定できる．（言い換えれば既知環境でも自動的に最適経路を見出すのは非常に手間がかかる）

・ここでは限られた情報の基に，如何に経路長を短くするかその手法の効率をシミュレーションによって調べる．

・AGVは2DW1C型であり，旋回曲率を急に変えることができるとする．

・AGVの位置姿勢はDead Reckonig，またはGPS・灯台方式によって知り得るとする．

１．接触センサによる衝突回避走行と経路探索法の具体的な手順

・AGVの走行と経路探索を繰り返して，より良い経路を見出す．

・走行と経路生成は以下のようにする．

「参照経路」作成→［参照経路上走行→障害物接触・限界等高線上走行→参照経路に戻る］→（この繰り返し）→終点

・始点からは半径aの円弧に沿う経路であり，終点では半径aの円弧に沿う経路で終わる．

・第１回目の「参照経路」は自由空間経路であり，「参照経路」作成の必要はない．

・簡単のために，AGVの代表点が障害物からLだけ離れたときに接触するとする．

・Ｌ離れた衝突点は第12.5節で言う限界等高線上の点である．

・AGVは接触センサフィードバック制御によって限界等高線に沿う走行をすることができる．

・これらの仮定の基に以下のように経路探索する．

（１）第１回目の経路探索（図１）

（１−１）自由空間経路に沿って走行する．

（１−２）障害物に接触したら（限界等高線A点に達したら），接触後は限界等高線の左右どちらに向きを変えるかを指示し，その方向に限界等高線上を走行する．

（１−３）限界等高線上経路がの点Bに到ったら経路を辿る．

（１−４）(1-2)，(1-3)を繰り返し，最後はを辿って終点に到る．

（２）第２回目以降の経路の改善（図２，図３）

（２−１）限界等高線の輪郭が部分的に分かったので，分かった範囲内で始点円弧と限界等高線間，２つの限界等高線間，限界等高線と終点円間の共通接線を自由空間経路に換えて新しい参照経路を作成する．共通接線は第12.5節で述べたようにマニュアルの指示と計算で求めることができる．

　（２−２）新しい参照経路上を走行する．

（２−３）（１）と同じやり方で走行・障害物回避を行う．すなわち，図４のように新しい経路（共通接線）CDの途中で別の障害物４に接触したら（１）と同じ手続きで接触点から限界等高線に沿う経路を取る．このように第２回目の経路が生成される．

（２−４）走行経路が新しい障害物に接触しなくなったら，経路生成は終了する．

（２−５）但し，障害物に接触したとき左右どちらかに向かうか指示するが，その善し悪しは分からない．１度右に向かうとして参照経路・走行経路を生成し，後で改めて左に向かう経路を生成するとその方が距離が短いことも半々の確率であり得る．

（３）経路ループの可能性とその対策

凹型の障害物（限界等高線）に接触して限界等高線の左右を決定したとき，図５のように生成経路がループから出られないことがある．ループをなすことが分かった段階で，C点に戻って図の右でなく左方向に換えて輪郭を辿る．

（４）袋小路対策

　障害物が接近して存在するとその間を通り抜けることができない．図６(a)の場合は経路生成を続行できるが，(b)の場合はループをなすのでC点に戻って向きを変えて輪郭を辿る．

　

・上記の経路生成手順と特異状態対処によって障害物回避経路が存在する限り経路生成が可能な筈である．

・しかし，最適の（最短の）経路となるとは限らない．最適経路を見出すには，（１）の手続きで限界等高線に達したとき輪郭線の左右両方に試行して全ての経路を探索してその最短経路を選ぶ必要がある．輪郭形状がある程度分かったら対話的に人が関与して決定できるが，自動では試行数が多く（：nは障害物数），時間がかかり過ぎる．

［シミュレーションの使い方］

（１）使用フォルダ名：3-12-6AGVPathsearch2

（２）全て描画画面上で操作する．（始めは文字画面，任意キーによって描画画面へ移る）

（３）操作順序は次の４段階からなる．

　　（１）AGVの始点と終点の位置姿勢P0，Pf設定

　　（２）室内に障害物I1，I2，．．．配置

　　（３−１）参照経路生成：既知限界等高線について，マニュアルによる等高線間の共通接線からなる参照経路生成

　　（３−２）走行による経路生成：参照経路上を走行し，障害物に接触したら限界等高線上走行，その繰り返し

（４）操作の具体的な手順（描画画面上で）

　（１）’P’ → (始点終点位置姿勢設定モード)

(1-1)　始点AGV表示 → ’x’,’X’,’y’,’Y’,’r’,’R’によりAGVの左右上下回転 → RTキーで決定 → 終点設定へ

(1-2)　終点AGV表示 → ’x’,’X’,’y’,’Y’,’r’,’R’によりAGVの左右上下回転 → RTキーで決定 → （２）or（３）へ

　・これで始点終点のAGV位置・向き始点終点を含むCCW円・CW円が描画される．

・経路生成（参照経路・走行経路）において，始点円は最初に辿る円弧，終点円は最後に辿る円弧となる．

（２）’O’ → (障害物室内配置モード)：２通りの配置法がある．

　（ａ）’a’入力 → (a-1)サンプル障害物から障害物番号(IとRTキー)を入力 → ’x’,’X’,’y’,’Y’,’r’,’R’により障害物の左右上下回転 → RTキーで位置姿勢決定 → ‘c’：次の障害物配置続ける → (a-1)へ

→ ‘T’ or ‘A’：障害物配置終了し（１）or（３）へ

　　（ｂ）予め設定した障害物配置があるので，その中から選ぶ．

‘b’入力 → ‘1’, ‘2’, ‘3’, ‘4’ のどれかを入力　　［註］’Z’を入力しない限り，配置は描画しない．

→ ‘T’ or ‘A’：障害物配置終了し（１）or（３）へ

　・（１）と（２）はどちらが先でも構わない．

　（３）’T’ → (経路生成モード：参照経路生成と参照経路上走行・障害物回避による走行経路生成)

　・最初は自由空間経路を参照経路とし，先ずその参照経路上走行を行う．

　（３−１）参照経路上走行と障害物回避・限界等高線上走行

　　　(3-1-1)‘s’キーを押し続けることにより走行 → 障害物接触の表示（AGVが赤から白に変わる） → ‘r’ or ‘l’ により左右進行方向を決定 → 進路を限界等高線上に変える → (3-1-1)へ → （繰り返し） → 終点

　　　［註1］限界等高線から参照経路への復帰は自動的に行われる．

［註2］走行途中で’0’キーを押すとそれまでの走行データをリセットしAGVは始点に戻る．

　（３−２）新しい参照経路作成：12.5節の経路生成と同じ．

　　　(3-2-1)　‘S I1’（SPを挟むコンマ無しの２文字）→ （始点円とI1番目障害物選択）→ (始点円I1等高線間の複数共通接線表示) → 訂正したければ ’i’ → (3-2-1)へ

(3-2-2)　SPキーにより複数共通接線(青)から希望の接線(赤)を選択 → ‘y’キーにより接線決定

　　　　　　訂正したければ ’i’ → (3-2-2)へ

　　　(3-2-3)　‘I1 I2’（SPを挟むコンマ無しの２文字）→ （I1，I2番目障害物選択）→ (I1，I2等高線間の複数共通接線表示) → 訂正したければ ’i’ → (3-2-2)へ

(3-2-4)　SPキーにより複数共通接線(青)から希望の接線(赤)を選択 → ‘y’キーにより接線決定

　　　　　　訂正したければ ’i’ → (3-2-4)へ

　　　(3-2-3)，(3-2-4)を終点前まで続ける．

　　　(3-2-5)　‘In F’（SPを挟むコンマ無しの２文字）→ （In番目障害物と終点円選択）→ In等高線−終点円間の複数共通接線表示) → 訂正したければ ’i’ → (3-2-5)へ

　　　　　　　　　　　 → （よければ１つの経路生成終了）→ ‘f’’（全ての経路生成終了）→ （４）へ

　・’i’は選択接線の変更，選択２障害物の変更を次々に遡って訂正できる．

・経路生成中，生成後，走行アニメーション中でも ’P’，’O’，’T’ により各設定モードに移行することができる．

・その場合全ての経路データは失われる．

・始点終点設定モードと障害物配置モードは独立であり，互いにデータを損なうことはない．

［AGV経路生成の手順例］

（０）スタート → 文字画面 → 任意キー → 描画画面へ

（１）’P’キー：始点終点の設定モード

(1-1, 2)　始点AGVを’x’,’X’,’y’,’Y’,’r’,’R’によって移動回転，RTキーによって確定．終点設定も同様

(1-3)　全てをやり直したければまた’P’ キーで元に戻す．

（２）’O’キー：障害物配置モード

(２−ａ) ‘a’キー：サンプル障害物から選択

(2-a-2)　障害物番号Iを入力して選択，’x’,’X’,’y’,’Y’,’r’,’R’によって移動回転，RTキーによって確定

→ 選択し直ししたければ ’i’ キー

→ 継続して障害物設定，または終了は(2-a-3)へ

(2-a-3)　‘c’ によって障害物配置継続，障害物配置終了なら ‘P’ or ‘T’ で次の設定モードへ

（２−ｂ）予め用意した複数の決まった障害物配置のサンプルから選択

(2-b-1)　‘b’ キー

(2-b-2) ‘1’, ‘2’, ‘3’, ‘4’ のどれかをキー入力 → 配置終了

(2-b-3)　‘P’ or ‘T’ で次の設定モードへ

このケースでは障害物配置はオペレータには知らされない．

知りたければ’Z’キーを押す．消すときは’z’キーを押す．

・全てやり直したければ ‘O’ キーによって障害物配置をリセットする．

・’P’と’T’はどちらが先でも構わない．

（３）’T’：経路生成モード＝２障害物とその間の共通接線選択，この繰り返し

(3-1)　最初は自由空間経路を参照経路とし，走行と経路生成から始める

(3-2) ‘s’で走行 → 障害物接触 → ‘r’,’l’で左右の向き決定 → 限界等高線上走行 → 参照経路へ復帰走行 ･･.･･→ 終点

(3-3)　走行終了 → 第２回参照経路作成へ

(3-REF)　第２回参照経路作成３腫

　’2’：新参照経路作成，’1’：今の参照経路使用，’0’：第１回目参照経路(自由空間経路)使用

　最初は’2’新参照経路作成の手順を示す．

(3-4)　参照経路作成−１：２障害物選択（最初は始点円と第１障害物�@：”S 1 RT”）（RTはリターンキー）

(3-5, 6)　共通接線選択　SPキーで赤接線を候補 → ‘y’で決定

(3-7, 8) ２障害物選択 → 共通接線選択の繰り返し → ････ → 障害物と終点円選択 → 共通接線選択決定 → ‘f’

（この例では最後は�Aと終点円（”2 F RT”）→ ‘f’）

(3-9, 10, 11, 12) 第２回参照経路上走行による経路生成

　　　　‘sで走行 → 障害物接触 → ‘r’ ‘l’で左右の向き決定 → 走行 → ･････ → 終点

　　　　‘0’で始点へ戻る（この経路のやり直し．既知となった限界等高線データは残る）

　　　　この繰り返しで幾通りもの経路が生成される．

(3-13, 14, 15)　参照経路作成−２　‘1’：今の参照経路を使う．

　‘0’：第１回参照経路（自由空間経路）を使う．

これらは左右の向きを変えて別のルートを探すために行う．

(3-16) ‘V’により全ての生成経路とその経路長を表示

・障害物は未知として普通は表示しない．

・障害物と限界等高線は’Z’によって表示され，’z’によって消える．

・生成経路は生成途中でも’V’によって表示され，’v’によって消える．

・’P’，’O’，’T’によっていつでもそのモードに転移する．その場合，生成経路データの全ては失われる．