知能システム論１（１３－２）移動ロボットのナビゲーション経路計画補足２００７．７．３経路計画 • 局所的経路計画ポテンシャル法などローカルミニマム等の不都合の可能性 • 大域的経路計画コンフィギュレーション空間探索法など必ず解が求まるが計算量膨大の可能性実空間からコンフィギュレーション（Ｃ）空間への写像 (Configuration) Θ３ Θ２ Θ４ Θ１ Θ 障害物Ｘロボット状態の実空間表現実空間に占めるロボットの部分空間記述ロボット状態のＣ空間表現ロボットの自由度変数による空間記述Ｙロボットの腕のＣ障害物 Θ２１２０ Θ2 ＧＳ Θ１Ｓ障害物Ｃ障害物 × ９０ Θ１実空間Ｇコンフィギュレーション空間移動ロボットのＣ空間障害物記述姿勢一定の場合のＣ障害物障害物に接触しながらロボットが一周したときの代表点の軌跡がＣ障害物の輪郭となる。量子化による近似表現 1台の移動ロボットのＣ空間自由空間と障害物空間を記述する空間 θ ＹＸ練習問題図に示す全方向移動ロボットのＣ障害物を求めよ。円の中心を代表点とせよ。・障害物ロボット経路探索・巾優先探索(Breadth-first seach) 波が伝播するように障害物を避け、自由領域を調べていく・深さ優先探索(Depth-first search) 巾優先探索による経路計画探索がゴールまで到達したらポインタを逆にたどり経路を求める。９８７６９８７９８９９５５５５５５５５５５５６７８９６４４４４４４４４４５６７８９７７４３３３３３３３４５６７８９８８８４３２２２２２４５６７８９９９９４３２１１１２５５６７８９４３２１Ｓ１２５５６７８９４３２１１１２４５６７８９４３２２２２２３４５６７８９Ｇ９８７６５４３３３３３３３４５６７８９９８７６５４４４４４４４４４５６７８９９８７６５５５５５５５５５５５６７８９練習問題左右、上下の隣接セルを優先探索し、最後に斜め隣のセルを探索し経路計画を行え。ＧＳ８７６練習問題左右、上下の隣接セルを優先探索し、最後に斜め隣のセルを探索し経路計画を行え。１２５３４ＧＳ一般的な経路探索(ダイクストラ法）１）累積コストが最小の前線セル（スタートセル）の隣接セルの累積コストを計算 f(m)=f(n)+COST(n,m) f(m) m(隣接セル）の累積コスト、n:前線セルＧ 0.3 0.1 0.2 0.1 0.1 0.2 0.1 0.2 0.3 0.2 0.2 0.1 0.1 0.3 Ｓ 0.3 0.4 0.1 0.2 0.2 ２）すでに累積コストが存在したら小さいほうを残す３）１）に戻ってゴールに達するまで繰り返すセル間コスト累積コストＡ＊探索累積コスト計算に現時点からゴールまでの推定コストを算入する。ｆ（ｍ）=ｇ（ｍ）+ｈ（ｍ）ｆ（ｍ）=（ｆ(n)－ｈ（ｎ））+ｈ（ｍ）＋COST(n,m) ｆ（ｍ）：スタートからゴールまでのコスト（ｍセル通過）ｇ（ｍ）：スタートからｍセルまでのコストｈ（ｍ）：ｍセルからゴールまでの推定コストーヒューリスティックー複数台移動ロボットのナビゲーション複数台のロボットがそれぞれのゴールまで他のロボットや障害物と衝突することなく到達するための操作 R2 G3 G2 Ｇ１ R1 R3 多数台移動ロボットのデッドロックフリーナビゲーション • ナビゲーションアルゴリズム（１）作業環境中の全てのロボットの位置姿勢を計測する。（２）1台のロボットのゴールまでの大域的経路計画を行う。このとき他のロボットは障害物とみなす。（３）ゴールまでの経路が存在したら、そのロボットをその経路に沿って一定距離移動させる。経路が存在しなかったり、すでにゴールに到達している場合、その場に留まる。（４）次のロボット（最後になったら1番目に戻る）に処理を進めるため（１）に戻る。全てのロボットがゴールに到着したら処理を終える。・静的デッドロックフリー条件０条件1 条件2 条件3 全てのロボットのゴールまでの経路は存在する。初期状態において、静的なデッドロック状態にない。ゴールに到達したロボットは他のロボットの邪魔にならず無視できる。静的障害物の位置姿勢は変化しない。定理１全てのロボットがゴールに到達するまでの間、少なくとも 1台のロボットは、ゴールに向かって移動可能である。証明ゴールに到達していないロボットが全て移動不可能になったと仮定する。条件1から、移動不可能になったロボットのうち少なくとも１台は過去に移動している。このとき、移動不可能となったロボットの中で最後に移動したロボットＡから見ると、他の全ての移動不可能になったロボットの位置姿勢はロボットＡの経路計画を行ったときと同じであり、また条件２よりゴールに到達したロボットは無視でき、条件３より静的障害物の位置姿勢は変化していない。よって、ロボットＡがゴールに向かって移動可能であるという状況は変化していない。したがってロボットＡは続けて移動可能である。これは仮定に反している。故に少なくとも1台のロボットは常にゴールに向かって移動可能である。動的デッドロック静的にはデッドロックはないにもかかわらず、行ったり来たりの振動状態が続く。Ｇ１Ｒ２Ｒ２Ｒ１Ｒ１Ｇ２多数台移動ロボットの動的デッドロックフリーナビゲーション • ナビゲーションアルゴリズム（１）作業環境中の全てのロボットの位置姿勢を計測する。（２）1台のロボットのゴールまでの大域的経路計画を行う。このとき他のロボットは障害物とみなす。（３）ゴールまでの経路が存在し、その経路が過去に探索したものと同じか少ない到達時間を要する場合、そのロボットをその経路に沿って一定距離移動させる。そのような経路が存在しなかったり、すでにゴールに到達している場合、その場に留まる。（４）次のロボット（最後になったら1番目に戻る）に処理を進めるため（１）に戻る。全てのロボットがゴールに到着したら処理を終える。・動的デッドロックフリー条件０条件1 条件2 条件3 条件４全てのロボットのゴールまでの経路は存在する。初期状態において、静的なデッドロック状態にない。ゴールに到達したロボットは他のロボットの邪魔にならず無視できる。静的障害物の位置姿勢は変化しない。ある時刻における各ロボットの経路探索の結果、予定経路が過去に探索した予定経路よりも長い到達時間を要する場合は動かない。条件５各ロボットｉが最初に経路計画を行ったときの所要時間をＴｉとする。 n 定理２全ｎ台のロボットは、遅くとも T i 1 i でゴールに到達する。証明条件４と５により、ロボットｉの停止時間を除いた移動所要時間はＴｉ以下である。また、定理１から、常に１台以上のロボットが移動している n ので、最悪でも T i 1 i で全てのロボットがゴールに到達する。多数台移動ロボットのデッドロックフリーナビゲーション(実装） • ナビゲーションアルゴリズム（１）作業環境中の全てのロボットの位置姿勢を計測する。（２）1台のロボットのゴールまでの大域的経路計画を行う。このとき他のロボットとその移動予約領域は障害物とみなす。（３）ゴールまでの経路が存在したら、そのロボットをその経路に沿って一定距離の移動を予約する。経路が存在しなかったり、すでにゴールに到達している場合、その場に留まる。移動予約領域に沿った移動は並行プロセスで管理する。（４）次の移動予約をとっていないロボットに処理を進めるため（１）に戻る。全てのロボットがゴールに到着したら処理を終える。シミュレーション４２３３２１１４５５シミュレーションー１シミュレーションー２ • Simulator へのショートカット • Simulator1 へのショートカット • Simulator2 へのショートカット Summary of Research • The multi-robot navigation system based on iGPS was proposed. • The experiment of delivery task was carried out in the time-varying environment. • The system could successfully navigate multiple robots reliably and robustly, suggesting the practical usefulness. Concluding Remarks • • • • Importance of robots for social application History of R/D on robot technology reviewed Social robots not realized by conventional R/D Intelligent Environment Supported Robot is proposed aiming at breakthrough in robotics • Mobile robot system for delivery in a building developed, demonstrating the feasibility and effectiveness of the proposed approach Future work • Introduce more effective sensor-based navigation scheme • Use “passive” marks like stealth barcode instead of IR LED unit. 知能システム論 I レポート課題複数台移動ロボットに関して、ナビゲーションアルゴリズムを１つ考案し、それによる下のロボット群の動きを検証せよ。提出期限：８月２０日Ｐ棟４階事務室まで R2 G2 Ｇ１ R1