３．１２．５　既知環境における経路生成　　　　　　　　　　　　　　　２００９−４−８

補足説明：3-12-5C AGVPathSearchC

実行ファイル3-12-5AGVpathsearchSource

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

１．ポテンシアル法と限界等高線法

・静的な経路探索には「ポテンシアル法」，動的な探索には「インピーダンス法」が提案されている．

・ポテンシアル法は始点と障害物を山と見，目標点を谷と見て，いくつかの山の麓を通り抜ける経路を探す方法である．

・もう１つの静的な探索法は，AGVが衝突しない「限界等高線」を描き，限界等高線とそれを繋ぐ線（２等高線の共通接線）に沿う経路を探す方法である．

・ポテンシアル法では窪みに陥る恐れがあること，経路長が長くなる可能性があることなどの欠点があり，後者の方が優れている．

・ここでは「限界等高線」法によって障害物のある環境で経路を生成するシミュレーションを行う．

２．限界等高線法による経路探索の具体的な方法

・以下の方針で探索する．

（１）AGVが障害物に衝突しない程度に近づいてもよいとする．

（２）できるだけ短い経路を試みる．

（３）経路曲線の曲率に制限を設けない．

（４）角ができないようにできる限り小さな曲率（多いな半径）の緩和曲線（丸め）を試みる．しかし場合によっては尖ることもあり得る．

（５）経路の選択（どの障害物の限界等高線を辿るか，どの共通接線を選ぶか）は，対話形式に人間が行う．

　　（コンピュータによって最適経路を生成することは可能であるが，場合の数が多すぎて処理が大変なのでここでは人間が決める）

（６）参考のために，最適経路に拘らず，複数の経路生成を行う．

・具体的には以下のような手順で行う．

（１）始点から終点へ3.12.02PTP運動の経路生成（ファイル名 3-12-02AGVpath ）に従って障害物を考えずに経路（自由空間経路）R0(s)を描く．

（２）始点・終点からは一定半径の円弧（始点円・終点円,，）上を辿るとする．

（３）各障害物から一定距離（AGVがどのような姿勢でも衝突しない距離）離れた「限界等高線」Bk(x,y)=0(k=1,2,…)を描く．

（４）視察により，経路の一部となる円弧と等高線を順番に（B0→Bs1→Bs2･･･→Bf，s1,s2･･･：1,2,･･･のどれか）選ぶ．

（５）各等高線間の複数共通接線から適当なものを選ぶ．

［註］

・限界等高線は一般的には関数形でなく点列で表される．２限界等高線間の全ての共通接線はコンピュータが計算する．．この詳細は3.12.5C点列から接線の計算法に譲る．

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

（１）使用フォルダ名：3-12-5AGVPathsearch

（２）全て描画画面上で操作する．

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

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

　　（２）室内に障害物B1，B2，．．．配置

　　（３）経路生成：順番に２つの障害物とその等高線間の共通接線の生成

　　（４）AGVの走行アニメーション

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

　（１）’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’ → (障害物室内配置モード)

　　サンプル障害物から障害物番号(IとRTキー)を入力 → ’x’,’X’,’y’,’Y’,’r’,’R’により障害物の左右上下回転

→ RTキーで位置姿勢決定 → ‘c’：次の障害物配置続ける → (2-1)の始めへ

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

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

　（３）’T’ → (経路生成モード＝順番に２障害物とその間の共通接線選択)

　・始点円・終点円，全ての配置した障害物（等高線）が表示されている．

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

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

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

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

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

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

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

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

　　　　　　　　　 → （よければ１つの経路生成終了）→ ‘c’（次の経路生成）→ (3-1)へ

　　　　　　　　　　　　　　　　　　　　　　　　　　→ ‘f’’（全ての経路生成終了）→ （４）へ

　・生成した経路（緑），生成中の経路（赤）が操作中に表示される．

（４）’A’ →（AGV走行モード）

・始点円・終点円，全ての配置した障害物，生成した全ての経路（緑）が表示される．

　　(4-1)　‘h’により経路選択（赤）

　　(4-2)　‘s’を押し続けることによりAGVが進行する．

　　(4-3)　‘0’によりAGVは始点に戻る．

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

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

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

［経路生成の例］

（１）始点終点の設定モード

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

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

（２）障害物配置モード

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

(2-2)　第１の障害物配置：RTキーによって位置確定 → 配置継続するなら’c’，終了なら’f’

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

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

(3-0)　‘T’ によって経路生成の準備

(3-1)　‘S 1’ によって始点円と第１障害物の選択，SPキーによって共通接線選択

(3-2)　RTキーによって経路となる共通接線の決定

(3-3)　障害物I1=1,I2=3を選びSP, RTキーによって共通接線を選定したが，不適当と判断して ’i,’ によって元に戻し接線を選定し直す．

(3-4)　‘3 3’ により第３障害物（等高線）を選び，SP，RTキーによって同一等高線内の接線の選択

(3-5)　２障害物選定のやり直し：‘i’ により3,3障害物間接線確定を取り消し，更に’i’ によって3,3障害物を取り消す．

　　　接線確定前なら後者の ’i’ だけで3,3障害物を取り消す．

(3-6)　第１経路生成終了．’c’ で次の経路生成，’f’ または’A’ で全経路生成終り

（４）AGV走行モード

(4-1)　‘h’ によって経路変更，’s’によって走行アニメーション，’0’によってAGV始点へ