(57)【要約】【課題】より安全で、より動作計画が破綻しづらい自律移動ロボットの動作計画を行う。【解決手段】衝突判定部４が、互いに異なる複数の一時的な流れが生じた場合に、各状態にある上記自律移動ロボットが各行動に基づいて移動した場合に障害物に衝突するかどうかを判定する。衝突確率計算部６が、衝突すると判定された一時的な流れが生じる確率の総和である衝突確率を計算する。報酬決定部７が、衝突確率を考慮して報酬を決定する。動的計画部２が、報酬に基づいて動的計画を行う。【選択図】図１
2010165050.tif 000002
【特許請求の範囲】
【請求項１】
不定の流速の流れがある流体で満たされ障害物が配置された空間の中で行動単位時間ごとに行動を決定してその行動に基づいて上記行動単位時間だけ移動する動作を繰り返す自律移動ロボットを出発位置から到達位置へ到達させるための動作計画を行う自律移動ロボットの動作計画装置において、
上記空間は、自律移動ロボットの二次元座標（ｘ，ｙ）、方位角ψ及び旋回速度ψ’の４つ次元で構成されるマルコフ遷移状態モデルにより離散的にモデル化されるとして、
予め定められた流れの中で、各状態にある上記自律移動ロボットが各行動を取り上記行動単位時間だけ移動した場合に各状態に遷移する確率である状態遷移確率を計算する状態遷移確率計算部と、
互いに異なる複数の一時的な流れが生じる確率が記憶される流れ発生確率記憶部と、
上記予め定められた流れ、及び、各上記一時的な流れの下で、上記各状態にある上記自律移動ロボットが上記各行動に基づいて移動した場合に、障害物に衝突するか判定する衝突判定部と、
障害物に衝突すると判定された一時的な流れが生じる確率を上記流れ発生確率記憶部から読み込んで加算することにより、上記各状態にある上記自律移動ロボットが上記各行動に基づいて移動した場合に障害物に衝突する衝突確率を計算する衝突確率計算部と、
遷移先の状態が上記到達位置を含む場合の報酬が最も高く、遷移先の状態が上記到達位置を含まない場合には上記衝突確率が小さいほど報酬が高くなるように、各状態にある上記自律移動ロボットが各行動を取り各状態に遷移する場合に得られる報酬を決定する報酬決定部と、
上記状態遷移確率及び上記報酬を用いて、マルコフ決定過程における動的計画法に基づき、上記自律移動ロボットの上記到達位置への到達しやすさを表す指標を状態ごとに求める動的計画部と、
を含む自律移動ロボットの動作計画装置。
【請求項２】
請求項１に記載の自律移動ロボットの動作計画装置において、
上記衝突判定部は、ある一時的な流れについて障害物に衝突すると判定された場合に、その一時的な流れと方向が同じで速さが速い一時的な流れについても障害物に衝突する一時的な流れであると判定することを特徴とすることを特徴とする自律移動ロボットの動作計画装置。
【請求項３】
請求項１又は２に記載の自律移動ロボットの動作計画装置で決まった動作計画に基づき、
不定の流速の流れがある流体で満たされ障害物が配置された空間の中で行動単位時間ごとに行動を決定してその行動に基づいて上記行動単位時間だけ移動する動作を繰り返す自律移動ロボットを出発位置から到達位置へ到達させるように制御する自律移動ロボットの動作制御装置において、
上記予め定められた流れと、流速の実測値との差である流速差を求める流速差取得部と、
上記自律移動ロボットが各行動を取った場合の遷移先の状態を、上記自律移動ロボットの位置を上記流速差の分だけ移動させることにより求める遷移先予測部と、
上記遷移先予測部が求めた遷移先の状態についての上記指標を互いに比較して、上記到達位置に最も到達しやすい行動を決定する行動決定部と、
上記自律移動ロボットが上記決定された行動に従って移動するように、上記自律移動ロボットを制御する制御部と、
を含む自律移動ロボットの動作制御装置。
【請求項４】
不定の流速の流れがある流体で満たされ障害物が配置された空間の中で行動単位時間ごとに行動を決定してその行動に基づいて上記行動単位時間だけ移動する動作を繰り返す自律移動ロボットを出発位置から到達位置へ到達させるための動作計画を行う自律移動ロボットの動作計画方法において、
上記空間は、自律移動ロボットの二次元座標（ｘ，ｙ）、方位角ψ及び旋回速度ψ’の４つ次元で構成されるマルコフ遷移状態モデルにより離散的にモデル化されており、
流れ発生確率記憶部には、互いに異なる複数の一時的な流れが生じる確率が記憶されており、
状態遷移確率計算部が、予め定められた流れの中で、各状態にある上記自律移動ロボットが各行動を取り上記行動単位時間だけ移動した場合に各状態に遷移する確率である状態遷移確率を計算する状態遷移確率計算ステップと、
衝突判定部が、上記予め定められた流れ、及び、各上記一時的な流れの下で、上記各状態にある上記自律移動ロボットが上記各行動に基づいて移動した場合に、障害物に衝突するか判定する衝突判定ステップと、
衝突確率計算部が、障害物に衝突すると判定された一時的な流れが生じる確率を上記流れ発生確率記憶部から読み込んで加算することにより、上記各状態にある上記自律移動ロボットが上記各行動に基づいて移動した場合に障害物に衝突する衝突確率を計算する衝突確率計算ステップと、
報酬決定部が、遷移先の状態が上記到達位置を含む場合の報酬が最も高く、遷移先の状態が上記到達位置を含まない場合には上記衝突確率が小さいほど報酬が高くなるように、各状態にある上記自律移動ロボットが各行動を取り各状態に遷移する場合に得られる報酬を決定する報酬決定ステップと、
動的計画部が、上記状態遷移確率及び上記報酬を用いて、マルコフ決定過程における動的計画法に基づき、上記自律移動ロボットの上記到達位置への到達しやすさを表す指標を状態ごとに求める動的計画ステップと、
を含む自律移動ロボットの動作計画方法。
【請求項５】
請求項４に記載の自律移動ロボットの動作計画方法において、
上記衝突判定ステップは、ある一時的な流れについて障害物に衝突すると判定された場合に、その一時的な流れと方向が同じで速さが速い一時的な流れについても障害物に衝突する一時的な流れであると判定することを特徴とすることを特徴とする自律移動ロボットの動作計画方法。
【請求項６】
請求項４又は５に記載の自律移動ロボットの動作計画方法で決まった動作計画に基づき、不定の流速の流れがある流体で満たされ障害物が配置された空間の中で行動単位時間ごとに行動を決定してその行動に基づいて上記行動単位時間だけ移動する動作を繰り返す自律移動ロボットを出発位置から到達位置へ到達させるように制御する自律移動ロボットの動作制御方法において、
流速差取得部が、上記予め定められた流れと、流速の実測値との差である流速差を求める流速差取得ステップと、
遷移先予測部が、上記自律移動ロボットが各行動を取った場合の遷移先の状態を、上記自律移動ロボットの位置を上記流速差の分だけ移動させることにより求める遷移先予測ステップと、
行動決定部が、上記遷移先予測部が求めた遷移先の状態についての上記指標を互いに比較して、上記到達位置に最も到達しやすい行動を決定する行動決定ステップと、
制御部が、上記自律移動ロボットが上記決定された行動に従って移動するように、上記自律移動ロボットを制御する制御ステップと、
を含む自律移動ロボットの動作制御方法。
【請求項７】
請求項１又は２に記載の自律移動ロボットの動作計画装置をコンピュータに実行させるための自律移動ロボットの動作計画プログラム。
【請求項８】
請求項７に記載の自律移動ロボットの動作計画プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば飛行船、潜水艦等の自律移動ロボットの動作計画を行う技術に関する。特に自律移動ロボットに障害物を回避させる動作計画を行う技術に関する。
【背景技術】
【０００２】
イナーシャ（慣性）が高い劣駆動型の自律移動ロボットの動作計画を行う技術として、マルコフ決定過程における動作計画法を利用した技術が知られている（例えば、特許文献１及び非特許文献１参照。）。
【０００３】
この技術においては、想定される流速の下、各状態ｓ∈｛ｓ１，…，ｓＮ｝にある自律移動ロボットが各行動ａ∈｛ａ１，…，ａＭ｝を取った場合に各状態ｓ’∈｛ｓ１，…，ｓＮ｝に遷移する状態遷移確率Ｐａｓｓ’と、そのときに得られる報酬Ｒａｓｓ’とをまず求める。報酬Ｒａｓｓ’については、例えば到達点を含む状態ｓ’に遷移するときに与えられる報酬Ｒａｓｓ’を１、障害物を含む状態ｓ’に遷移するときに与えられる報酬Ｒａｓｓ’を−１、障害物を含まない状態ｓ’に遷移するときに与えられる報酬Ｒａｓｓ’を０とする。
【０００４】
そして、状態遷移確率Ｐａｓｓ’及び報酬Ｒａｓｓ’を用いて、マルコフ決定過程における動的計画法に基づき、状態価値関数Ｖπ（ｓ）を求める。そして、想定される流速と実際の流速の流速差を考慮しつつ、状態価値関数Ｖπ（ｓ）を最大にする行動ａを選択し、その選択された行動ａに従って自律移動ロボットを制御する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−３１７１６５号公報
【非特許文献】
【０００６】
【非特許文献１】H.Kawano, “Three Dimensional Obstacle Avoidance of Autonomous Blimp Flying in Unknown Disturbance”, Proceeding of 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp.123-130, October, 2006
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１及び特許文献１に記載された技術おいては、自律移動ロボットが行動する環境で生じ得る想定外の一時的な流れを考慮して報酬を定めてはいない。
【０００８】
したがって、自律移動ロボットが行動する環境で想定外の一時的な流れが生じた場合に、動作計画が破綻しやすいという課題がある。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、互いに異なる複数の一時的な流れが生じた場合に、各状態にある上記自律移動ロボットが各行動に基づいて移動した場合に障害物に衝突するかどうかを判定し、衝突すると判定された一時的な流れが生じる確率の総和である衝突確率を計算し、衝突確率を考慮して報酬を決定し、その報酬に基づいて動的計画を行う。
【発明の効果】
【００１０】
この発明は、想定外の一時的な流れを考慮して報酬を決定するため、動作計画はより破綻しづらくなるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】自律移動ロボットの動作計画装置の例の機能ブロック図。
【図２】状態遷移確率計算部の例のブロック図。
【図３】自律移動ロボットの動作制御装置の例の機能ブロック図。
【図４】自律移動ロボットの模式図であり、（ａ）は正面図、（ｂ）は側面図。
【図５】水平方向の位置の変位量を説明するための図。
【図６】状態遷移確率の計算を説明するための図。
【図７】衝突の判定及びその省略を説明するための概念図。
【図８】衝突が起こる一時的な流れの集合Ｓｇの連続的な概念図。
【図９】衝突が起こる一時的な流れの集合Ｓｇの離散的な概念図。
【図１０】自律移動ロボットの動作制御方法の例を示す流れ図。
【図１１】衝突判定部の処理を説明するための図。
【図１２】自律移動ロボットの動作制御方法の例を示す流れ図。
【発明を実施するための形態】
【００１２】
［マルコフ決定過程］
まず、この発明を把握するための基礎知識である強化学習（Reinforcement Learning）におけるマルコフ決定過程（Markov decision Process）の概略を説明する。
【００１３】
環境を構成する離散的な状態の集合をＳ＝｛ｓ１，ｓ２，…，ｓＮ｝、行動主体が取り得る行動の集合をＡ＝｛ａ１，ａ２，…，ａＭ｝と表す。環境中のある状態ｓ∈Ｓにおいて、行動主体がある行動ａ∈Ａを実行すると、環境は確率的に状態ｓ’∈Ｓへ遷移する。その遷移確率（状態遷移確率とも呼ぶ）を
Ｐａｓｓ’＝Ｐｒ｛ｓｔ＋１＝ｓ’｜ｓｔ＝ｓ，ａｔ＝ａ｝
により表す。このとき環境から行動主体へ報酬ｒが確率的に与えられるが、その期待値を
Ｒａｓｓ’＝Ｅ｛ｒｔ｜ｓｔ＝ｓ，ａｔ＝ａ，ｓｔ＋１＝ｓ’｝
とする。
【００１４】
なお、状態ｓ’に附されている記号’は、状態ｓとの識別を図るための記号である。時間微分を表す記号として記号’を用いることがあるが、記号’が附された対象がマルコフ状態遷移モデルの状態であるか否かで記号’の意味を容易に識別できるので、以降の説明でもこの記法に従うとする。
【００１５】
ある時間ステップｔで行った行動が、その後の報酬獲得にどの程度貢献したのかを評価するため、その後得られる報酬の時系列を考える。報酬の時系列評価は価値と呼ばれる。行動主体の目標は、価値を最大化すること、又は、価値を最大にする方策π（ｓ，ａ）を求めることである。方策π（ｓ，ａ）は、状態ｓにおいて行動ａを取ることを意味し、状態ｓ及び行動ａの複数の組のそれぞれについて定義される。価値は、時間の経過とともに報酬を割引率γ（０≦γ＜１）で割引いて合計される。すなわち、ある方策πの下での状態ｓの価値である状態価値関数Ｖπ（ｓ）は、以下のように定義される。Ｅπは期待値を求める関数である。
【００１６】
【数１】
2010165050.tif 000003
【００１７】
ここでは価値関数として方策πの下での状態ｓの価値である状態価値関数Ｖπ（ｓ）を採用したが、方策πの下で状態ｓにおいて行動ａを採ることの価値である行動価値関数Ｑπ（ｓ，ａ）を採用することもできる。
【００１８】
【数２】
2010165050.tif 000004
【００１９】
行動主体の目標は、最適な方策πを求めること、つまり任意の状態ｓについて価値関数（上記の例では状態価値関数Ｖπ（ｓ）である。）が他の方策πを採った場合よりも劣るものではない方策πを求めることである。この方策πの探求は、Ｂｅｌｌｍａｎ方程式で表され、状態ｓと行動ａと遷移先の状態ｓ’との各組み合わせについての状態遷移確率Ｐａｓｓ’及び報酬Ｒａｓｓ’の値が定まっていれば、動的計画法（ダイナミックプログラミング法）により、最適な、状態価値関数Ｖπ（ｓ）、行動価値関数Ｑπ（ｓ，ａ）及び方策πを計算することができる（例えば、三上  貞芳、皆川  雅章  共訳、R.S.Sutton、A.G.Barto  原著「強化学習」森北出版、1998、pp.94-118参照。）。動的計画法の処理は、周知技術であるため説明は省略する。
【００２０】
［自律移動ロボットの動作計画装置及び方法］
自律移動ロボットの動作計画装置及び方法の実施形態について説明する。
【００２１】
行動主体である自律移動ロボットの例を、図４（ａ）（ｂ）を参照して説明する。自律移動ロボットは、主推進器１０１、上下方向推進器１０２、舵１０３、ゴンドラ１０４、流速差取得部２１、位置計測部２５を有する。この自律移動ロボットは、真横方向に直接移動することができない。搭載アクチュエータである主推進器１０１、上下方向推進器１０２、舵１０３が制御可能な運動自由度よりも自律移動ロボットの運動自由度は高いので、この自律移動ロボットは劣駆動ロボットである。この実施形態では、自律移動ロボットとして飛行船タイプのものを採用しているが、水中無人探索機のような水中ロボット等の任意の自律移動ロボットを採用してもよい。自律移動ロボットには、搭載アクチュエータに応じて、行動単位時間Ｔごとに取り得る行動が定められる。
【００２２】
自律移動ロボットは、不定の流速の流れがある流体で満たされた空間を航行する。その空間はマルコフ遷移状態モデルにより離散的にモデル化されており、自律移動ロボットの二次元座標（ｘ，ｙ）、方位角ψ及び旋回速度ψ’の４つ次元から構成される。各次元は、その次元の物理量を測定するセンサの分解能に応じて離散化されている。この空間には、自律移動ロボットの出発位置及び到着位置が予め定められ、また障害物が配置される。
【００２３】
出発位置を含む状態ｓに位置する自律移動ロボットは、予め定められた行動の集合の中から１つの行動ａを選択する。そして、予め定められた行動単位時間Ｔだけその行動ａに従って移動して、遷移先の状態ｓ’に移動する。この遷移先の状態ｓ’において、再び、予め定められた行動の集合の中から１つの行動ａを選択して、行動単位時間Ｔだけその行動に従って移動して、遷移先の状態ｓ’’に移動する。この行動の選択と状態の遷移を繰り返すことにより、初めは出発地点を含む状態にある自律移動ロボットは、空間に配置された予め定められた到達地点を含む状態に移動しようとする。自律移動ロボットの動作計画装置は、そのための動作計画を行う。
【００２４】
＜ステップＳ１（図１０）＞
状態遷移確率計算部１（図１）は、予め定められた流れの下で、各状態ｓにある自律移動ロボットが各行動ａを取った場合に各状態ｓに遷移する状態遷移確率Ｐａｓｓ’を計算する（ステップＳ１）。すなわち、状態ｓ、行動ａ及び遷移先の状態ｓ’の各組合せについての状態遷移確率Ｐａｓｓ’を計算する。計算された状態遷移確率Ｐａｓｓ’は、動的計画部２に送られる。
【００２５】
状態遷移確率Ｐａｓｓ’の計算方法の例について説明する。この例では、状態遷移確率計算部１は、図２に例示するように、目標速度計算部１１、変位量計算部１２及び確率計算部１３を含む。
【００２６】
≪ステップＳ１１≫
状態遷移確率計算部１の目標速度計算部１１（図２）は、自律移動ロボットが各状態ｓにおいてある各行動ａを取ったときの目標速度を決定する（ステップＳ１１）。目標速度は、変位量計算部１２に送られる。例えば、各行動ａについて、下記の式に従って自律移動ロボットの旋回速度ψ’τ（ｔ）と前後方向の速度ｖｘｗτ（ｔ）を自律移動ロボットの目標速度として定める。（ｂ１，ｂ２）はマルコフ状態遷移モデルの各状態ｓにおける行動ａに対応する二次元ベクトル、αは予め定められた旋回加速度であり、βは予め定められた前後方向の加速度であり、τは各行動ａの開始時からの経過時間、ψ’τ０は行動ａの開始時における自律移動ロボットの旋回速度、ｖｘ０は行動ａの開始時における自律移動ロボットの前後方向の速度である。
【００２７】
【数３】
2010165050.tif 000005
【００２８】
ここで、旋回加速度α及び前後方向の加速度βは、自律移動ロボットの性能の限界を超えないように設定される。また、前後方向の速度ｖｘ０（ｔ）及び前後方向の加速度βは、それぞれ対流体機体速度及び対流体機体加速度として記述される。
【００２９】
≪ステップＳ１２≫
変位量計算部１２は、各状態ｓにある自律移動ロボットが、予め定められた流れの下において、各行動ａに従って移動した場合の、自律移動ロボットの世界座標系における水平面内位置のＸ座標，Ｙ座標，方位角ψ及び旋回速度ψ’がそれぞれどれくらい変位するのか計算する（ステップＳ１２）。計算された変位量は確率計算部１３に送られる。
【００３０】
予め定められた流れとは、例えば、想定される流れ、想定される流れよりも速い流れである。［自律移動ロボットの動作制御装置及び方法］の欄で後述するように予め定められた流れと流速の実測値とが異なる場合には適宜補正されるため、おおよその流れでよい。予め定められた流れを０としてもよい。もっとも、想定される流れが流速の実測値と近いほど、この動作計画及びこれに基づく動作制御の精度が増す。したがって、予め定められた流れを想定される流れとすることにより、この動作計画及びこれに基づく動作制御の精度が増す。また、自律移動ロボットの出発位置から到達位置に向かう方向と同じ向きで想定される流れよりも速い流れの下で計算を行う場合、後ろから流れを受けるロボットは旋回半径が大きくなるので、現実よりも厳しい条件で動作計画をしていることになるから、より安全な動作計画を行うことができる。
【００３１】
自律移動ロボットの水平面内位置のＸ座標の変位量をＤＸ（ψ０，ａ）、Ｙ座標の変位量をＤＹ（ψ０，ａ）、方位角ψの変位量をＤψ（ψ０，ａ）、旋回速度ψ’の変位量をＤψ’（ψ０，ａ）とすると、それぞれの変位量は、次式にように与えられる（図５を参照のこと）。
【００３２】
【数４】
2010165050.tif 000006
【００３３】
ここで、ψ０は各状態ｓの開始時の方位角、Ｔは状態ｓから次の状態ｓ’に遷移するまでの行動単位時間、ｆｍｘは予め定められた流れのＸ座標の成分、ｆｍｙは予め定められた流れのＹ座標の成分である。なお、方位角ψの変位量Ｄψ（ψ０，ａ）と、旋回速度ψ’の変位量Ｄψ’（ψ０，ａ）については、旋回速度ψ’の制御を行うことになるため、風の影響による補正は行わない。行動単位時間は例えば１５秒とすることができる。
【００３４】
≪ステップＳ１３≫
確率計算部１３は、自律移動ロボットの水平面内位置のＸ座標の変位量ＤＸ（ψ０，ａ）、Ｙ座標の変位量ＤＹ（ψ０，ａ）、方位角ψの変位量Ｄψ（ψ０，ａ）及び旋回速度ψ’の変位量Ｄψ’（ψ０，ａ）に基づいて、状態遷移確率Ｐａｓｓ’を計算する（ステップＳ１３）。
【００３５】
まず、状態ｓが、自律移動ロボットの水平面内位置のＸ座標、Ｙ座標、方位角ψ及び旋回速度ψ’の４つの次元で構成される格子で示されるとし、その格子をＲ（ｓ）と定義する（図６を参照のこと）。そして、その格子Ｒ（ｓ）を、上記各変位量から構成される変位量ベクトル（ＤＸ（ψ０，ａ），ＤＹ（ψ０，ａ），Ｄψ（ψ０，ａ），Ｄψ’（ψ０，ａ））で、平行移動したものをＲｔ（ｓ）と定義する。
【００３６】
ここで、自律移動ロボットが状態ｓにあるときは、自律移動ロボットは、その状態ｓを表わす４次元の格子Ｒ（ｓ）の各点の何れかに、等しい確率で存在するものと仮定する。この仮定の下では、状態遷移確率Ｐａｓｓ’は、Ｒｔ（ｓ）と各Ｒ（ｓ’）の重なった部分の体積に比例してそれぞれ求めることができる。ここで、Ｒ（ｓ’）は、Ｒｔ（ｓ）と重なった格子である。すなわち、Ｒ（ｓ’）は、状態ｓにおいてある行動ａを取ったときの遷移先の候補の状態ｓ’に対応した４次元の格子である。Ｒｔ（ｓ）は最大で８つのＲ（ｓ’）と重なる可能性がある。
【００３７】
状態遷移確率Ｐａｓｓ’は、Ｒｔ（ｓ）とあるＲ（ｓ’）の重なった部分の体積をＶ０（ｓ，ｓ’，ａ）、Ｒｔ（ｓ）とすべてのＲ（ｓ’）との重なった部分の体積をΣｓ’Ｖ０（ｓ，ｓ’，ａ）とすると、次式により求めることができる。
【００３８】
【数５】
2010165050.tif 000007
【００３９】
ステップＳ１１からステップＳ１３の処理を適宜繰り返すことにより、状態ｓ、行動ａ及び遷移先の状態ｓ’の各組合せについての状態遷移確率Ｐａｓｓ’を求める（ステップＳ１の説明は以上）。
【００４０】
次に流れ発生確率記憶部３に格納されるデータについて説明をする。流れ発生確率記憶部３（図１）には、互いに異なる複数の一時的な流れ（ｆｇ，ψｇ）と、各一時的な流れ（ｆｇ，ψｇ）が生じる確率とが記憶される。一時的な流れは、極座標系、直交座標系、斜光座標系の何れの座標系で記述してもよいが、この例では極座標系で一時的な流れを記述することにする。ｆｇは一時的な流れの速さ、ψｇは一時的な流れの方向を意味する。一時的な流れは、速さｆｇ及び方向ψｇの組で特定される。速さｆｇ及び方向ψｇの一時的な流れを（ｆｇ，ψｇ）とも表記する。起こり得る一時的な流れの範囲は、ｆｇ−ψｇ平面の集合Ｓで定義される。
【００４１】
例えば、自律移動ロボットの行動環境で過去に起こった最大流速をｆｇｍａｘとして、集合Ｓを次のように定義する。
【００４２】
Ｓ＝｛（ｆｇ，ψｇ）｜０≦ｆｇ≦ｆｇｍａｘ，０≦ψｇ≦３６０°｝
ｐｇ（ｆｇ，ψｇ）は一時的な流れの確率分布であり、計算機で扱う場合には離散的な確率となるが、ｐｇ（ｆｇ，ψｇ）を概念的な説明のために確率密度関数と呼ぶこともある。一時的な流れを連続的に考えた場合には、一時的な流れの確率分布は確率密度関数ｐｇ（ｆｇ，ψｇ）で表現することができる。定義により確率密度関数ｐｇ（ｆｇ，ψｇ）を集合Ｓで積分すると１となる。
【００４３】
１＝∫ｐｇ（ｆｇ，ψｇ）ｄｆｇｄψｇ
実際に発生し得る一時的な流れの方向ψｇは予想することができないので、確率密度関数ｐｇ（ｆｇ，ψｇ）は、速さｆｇについてのみ正規分布に従うとして、例えば下記式のように定義される。σは分散、μは平均値である。
【００４４】
【数６】
2010165050.tif 000008
【００４５】
μ＝０として、速さｆｇの定義域をｆｇ＞０としてもよい。この場合、１＝∫ｐｇ（ｆｇ，ψｇ）ｄｆｇｄψｇとするために、確率密度関数ｐｇ（ｆｇ，ψｇ）を次のように定義する。
【００４６】
【数７】
2010165050.tif 000009
【００４７】
自律移動ロボットの行動環境で過去に測定された流速についての統計データを用いて、確率密度関数ｐｇ（ｆｇ，ψｇ）を定義してもよい。
【００４８】
流れ発生確率記憶部３には、これらの確率密度関数ｐｇ（ｆｇ，ψｇ）を表現するためのデータが格納される。例えば、ｆｇ−ψｇ平面をΔｆｇ，Δψｇの幅の格子で分割することにより離散的に表現し、各格子の代表点（例えば格子の中心点）の値ｆｇ，ψｇごとに、一時的な流れの確率ｐｇ（ｆｇ，ψｇ）の値を定義する。このとき、ｐｇ（ｆｇ,ψｇ）の総和は１となる。すなわち、ΣＳｐｇ（ｆｇ,ψｇ）＝１である。
【００４９】
＜ステップＳ２＞
衝突判定部４は、予め定められた流れ（ｆｘ，ｆｙ）、及び、各一時的な流れ（ｆｇ，ψｇ）の下で、各状態ｓにある自律移動ロボットが各行動ａに基づいて移動した場合に、障害物に衝突するか判定する（ステップＳ１）。障害物に衝突すると判定された一時的な流れ（ｆｇ，ψｇ）についての情報は、衝突流れ記憶部５に格納される。例えば、後述するように、障害物に衝突すると判定された一時的な流れ（ｆｇ，ψｇ）の格子の集合Ｓｇについての情報が、衝突流れ記憶部５に格納される。
【００５０】
【数８】
2010165050.tif 000010
【００５１】
ステップＳ１の処理の具体例を、図１１を参照して説明する。まず、衝突判定部４は、ｆｇ−ψｇ空間の集合Ｓから、速さｆｇ及び方向ψｇともに最小値となる格子を選択する（ステップＳ２１）。τ＝０とする（ステップＳ２２）。上記式により定義されるＤＸｇ（ｓ，ａ，ｆｇ，ψｇ）、ＤＹｇ（ｓ，ａ，ｆｇ，ψｇ）の値を計算して、状態ｓにおけるＸ，Ｙの値をそれぞれ加算する（ステップＳ２３）。すなわち、ＤＸｇ（ｓ，ａ，ｆｇ，ψｇ）＋Ｘ、ＤＹｇ（ｓ，ａ，ｆｇ，ψｇ）＋Ｙの値を計算する。ＤＸｇ（ｓ，ａ，ｆｇ，ψｇ）＋Ｘ、ＤＹｇ（ｓ，ａ，ｆｇ，ψｇ）＋Ｙで示す位置が障害物であるかどうかを判定する（ステップＳ２４）。障害物でないと判定された場合には、τ＜Ｔであるかを判定する（ステップＳ２５）。τ＜Ｔである場合には、τを予め定められた値だけインクリメントし（ステップＳ２６）、その後ステップＳ２３に進む。τ＜Ｔでない場合には、速さｆｇが速さｆｇの最大値ｆｇｍａｘであるかどうか、すなわちｆｇ＜ｆｇｍａｘであるかを判定する（ステップＳ２７）。ｆｇ＜ｆｇｍａｘである場合には、速さｆｇをインクリメントして（ステップＳ２８）、ステップＳ２２に進む。ｆｇ＜ｆｇｍａｘでない場合には、ステップＳ２１０に進む。
【００５２】
ステップＳ２４において、障害物であると判定された場合には、自律移動ロボットの行動環境で想定される流れ（ｆｘ，ｆｙ）、及び、現在選択されている格子の一時的な流れ（ｆｇ，ψｇ）の下で、現在選択されている状態ｓにある自律移動ロボットが現在選択されている行動ａに基づいて移動した場合に、障害物に衝突すると判定して、現在選択されている一時的な流れ（ｆｇ，ψｇ）の格子を、衝突が起こる一時的な流れの集合Ｓｇに加える（ステップＳ２９）。また、必要に応じて、現在選択されている一時的な流れ（ｆｇ，ψｇ）の格子だけではなく、現在選択されている一時的な流れ（ｆｇ，ψｇ）と方向ψｇが同じでよりも速さが速い一時的な流れの格子を、衝突が起こる一時的な流れの集合Ｓｇに加えてもよい（ステップＳ２９’）。
【００５３】
例えば、図７の速さｆｇ２の一時的な流れにおいて衝突が起こると判定された場合には、速さｆｇ２と方向が同じで速さがｆｇ２よりも速い速さｆｇ４の一時的な流れにおいても衝突が起こることは計算をしなくてもわかる。したがって、ｆｇ４の一時的な流れについての衝突が起こるかどうかの計算を省略することができるのである。このようにして、一時的な流れについて衝突するかどうかの判定を省略することにより、計算量を削減することができる。図７の状況における、衝突が起こる一時的な流れの集合Ｓｇの連続的な概念図を図８に、衝突が起こる一時的な流れの集合Ｓｇの離散的な概念図を図９に示す。
【００５４】
ステップＳ２１０において、方向ψｇ＞３６０°であるか判定する（ステップＳ２１０）。方向ψｇ＞３６０°でないと判定された場合には、方向ψｇを予め定められた値だけインクリメントし、速さｆｇを０とし（ステップＳ２１１）、ステップＳ２２に進む。方向ψｇ＞３６０度であると判定された場合には、処理を終える。この処理を状態ｓと行動ａの各組について行う。
【００５５】
＜ステップＳ３＞
衝突確率計算部６は、障害物に衝突すると判定された一時的な流れが生じる確率を流れ発生確率記憶部３から読み込んで加算することにより、各状態にある上記自律移動ロボットが各行動に基づいて移動した場合に障害物に衝突する衝突確率Ｐｃ（ｓ，ａ）を計算する（ステップＳ３）。例えば、集合Ｓｇに含まれる衝突が起こる一時的な流れ（ｆｇ，ψｇ）のそれぞれが生じる確率ｐｇ（ｆｇ，ψｇ）の総和を計算することにより、衝突確率Ｐｃ（ｓ，ａ）を計算する。
【００５６】
【数９】
2010165050.tif 000011
【００５７】
障害物に衝突すると判定された一時的な流れについての情報（例えば、集合Ｓｇについての情報）は、衝突流れ記憶部５から読み出す。計算された衝突確率Ｐｃ（ｓ，ａ）は、報酬決定部７に送られる。
【００５８】
＜ステップＳ４＞
報酬決定部７は、遷移先の状態ｓ’が到達位置を含む場合の報酬が最も高く、遷移先の状態ｓ’が到達位置を含まない場合には衝突確率Ｐｃ（ｓ，ａ）が小さいほど報酬が高くなるように、各状態ｓにある自律移動ロボットが各行動ａを取り各状態ｓ’に遷移する場合に得られる報酬ｒ（ｓ，ａ）を決定する（ステップＳ４）。決定された報酬ｒ（ｓ，ａ）は、動的計画部２に送られる。
【００５９】
関数Ｆを、単調減少関数とする。単調減少関数とは、任意のｘ１，ｘ２（ただし、ｘ１＜ｘ２）に対して、ｆ（ｘ１）≧ｆ（ｘ２）となる関数ｆのことを意味する。Ｐｃ（ｓ，ａ）の定義によりＰｃ（ｓ，ａ）の最小値は０であり最大値は１であるから、関数Ｆの最大値はＦ（０）最小値はＦ（１）である。また、任意の定数Ｒｍａｘを、Ｒｍａｘ＞Ｆ（０）とする。例えば、Ｆ（ｘ）＝−ｘとし、Ｒｍａｘ＝１とする。このとき、報酬Ｒａｓｓ’を例えば次のように決定する。
【００６０】
遷移先の状態ｓ’が到達位置を含む場合⇒Ｒａｓｓ’＝Ｒｍａｘ
それ以外の場合⇒Ｒａｓｓ’＝Ｆ（Ｐｃ（ｓ，ａ））
＜ステップＳ５＞
動的計画部２は、状態遷移確率及び報酬を用いて、マルコフ決定過程における動的計画法に基づき、自律移動ロボットの上記到達位置への到達しやすさを表す指標を状態ごとに求める（ステップＳ５）。到達しやすさを表す指標としては、状態価値関数Ｖπ（ｓ）、行動価値関数Ｑπ（ｓ，ａ）及び方策πの何れかを例えば用いることができる。計算された指標は、指標記憶部１７に格納される。
【００６１】
［マルコフ決定過程］の欄で説明をしたように、状態ｓ、行動ａ及び遷移先の状態ｓ’の各組合せについての状態遷移確率Ｐａｓｓ’及び報酬Ｒａｓｓ’が計算されていれば、動的計画法に基づいて、状態価値関数Ｖπ（ｓ）、行動価値関数Ｑπ（ｓ，ａ）及び方策πを計算することができる。
【００６２】
このように想定外の一時的な流れ（ｆｇ，ψｇ）を考慮して報酬Ｒａｓｓ’を決定し、この報酬Ｒａｓｓ’に基づいて動的計画を行うことにより、生成された動的計画はより破綻しづらくなる。
【００６３】
以上が、自律移動ロボットの動作計画装置及び方法の実施形態について説明である。
【００６４】
［自律移動ロボットの動作制御装置及び方法］
以下、図３及び図１２を参照して、生成された動的計画（＝指標）を用いて自律移動ロボットの動作を制御する自律移動ロボットの動作制御装置及び方法の実施形態について説明する。
【００６５】
＜ステップＡ１（図１２）＞
流速差取得部２１（図３）は、動作計画時に予想した予め定められた流れと、流速の実測値との差である流速差を求める（ステップＡ１）。求まった流速差は、遷移先予測部２２に送られる。予め定められた流れのＸ成分をｆｘ、Ｙ成分をｆｙとし、実際の流速のＸ成分をｆｘａ、Ｙ成分をｆｙａとすると、流速差ｄｆｘ，ｄｆｙは、それぞれ下記のように表される。
【００６６】
ｄｆｘ＝ｆｘ−ｆｘａ
ｄｆｙ＝ｆｙ−ｆｙａ
動作計画時に予想した予め定められた流れを０とした場合には、流速差取得部２１は現在の流速の実測値を流速差として求めることができる。
【００６７】
＜ステップＡ２＞
遷移先予測部２２は、自律移動ロボットが各行動を取った場合の遷移先の状態ｓ’を、自律移動ロボットの位置を流速差ｄｆｘ，ｄｆｙの分だけ移動させることにより求める（ステップＡ２）。求まった遷移先の状態ｓ’は、行動決定部２３に送られる。
【００６８】
遷移先の状態ｓ’の求め方の例を述べる。
流速差ｄｆｘを考慮したときの自律移動ロボットのＸ軸方向の位置の変位量ＤＸａ（ψ０，ａ）と、流速差ｄｆｙを考慮したときの自律移動ロボットのＹ軸方向の位置の変位量ＤＹａ（ψ０，ａ）とは、それぞれ以下のように示される。
【００６９】
【数１０】
2010165050.tif 000012
【００７０】
遷移先予測部２２は、まず、上記式により、すなわち自律移動ロボットの位置を流速差ｄｆｘ，ｄｆｙの分だけ移動させることにより、実際のＸ軸方向の位置の変位量ＤＸａ（ψ０，ａ）及び実際のＹ軸方向の位置の変位量ＤＹａ（ψ０，ａ）を求める。
【００７１】
遷移先予測部２２は、次に、下記式により、行動ａを取った場合の遷移先の状態ｓ’を求める。具体的には、行動ａの開始時における、Ｘ軸方向の位置Ｘ（ｓ）に、Ｙ軸方向の位置Ｙ（ｓ）、方位角ψ０（ｓ）及び旋回速度ψ’０（ｓ）に、それぞれ実際のＸ軸方向の位置の変位量ＤＸａ（ψ０，ａ）、実際のＹ軸方向の位置の変位量ＤＹａ（ψ０，ａ）、方位角の変位量Ｄψ（ψ０，ａ）及び旋回速度ψ’の変位量Ｄψ’（ψ０，ａ）を加算することにより遷移先の状態ｓ’を求める。
【００７２】
【数１１】
2010165050.tif 000013
【００７３】
Ｘ軸方向の位置Ｘ（ｓ）に、Ｙ軸方向の位置Ｙ（ｓ）、方位角ψ０（ｓ）及び旋回速度ψ’０（ｓ）については、位置計測部２５が測定したものを用いる。ＤＸ（ψ０，ａ）及びＤＹ（ψ０，ａ）については、動作計画時に計算したＤＸ（ψ０，ａ）及びＤＹ（ψ０，ａ）を再利用してもよい。この場合、図示していない記憶部にＤＸ（ψ０，ａ）及びＤＹ（ψ０，ａ）が記憶され、遷移先予測部２２が適宜これらを読み込む。もちろん、遷移先予測部２２がこれらを再度計算してもよい。
【００７４】
＜ステップＡ３＞
行動決定部２３は、遷移先予測部２２が求めた、状態ｓにおいて取り得る各行動ａに従って移動した場合の遷移先の状態ｓ’についての指標を比較して、到達点に最も到達しやすい行動ａを決定する（ステップＡ３）。決定された行動ａは、制御部２４に送られる。
【００７５】
指標として状態価値関数Ｖπ（ｓ）を用いた場合には、到達点を含む状態に遷移する場合に得られる報酬が最も高くなるように報酬が決定されているため、状態価値関数Ｖπ（ｓ）の値を最も大きくする行動ａが、到達点に最も到達しやすい行動となる。
【００７６】
したがって、行動決定部２３は、指標記憶部１７を参照して、状態ｓにおいて取り得る各行動ａに従って移動した場合の遷移先の状態ｓ’における状態価値関数Ｖπ（ｓ’）をそれぞれ求め、比較することにより、状態価値関数Ｖπ（ｓ’）の値を最も大きくする行動ａを決定する。
【００７７】
＜ステップＡ４＞
制御部２４は、決定された行動ａに従って移動するように、自律移動ロボットを制御する（ステップＡ４）。具体的には、行動ａに対応する目標速度を維持することができるように、自律移動ロボットの主推進器１０１及び舵１０３を制御する。
【００７８】
［変形例等］
指標として、上記したように行動価値関数Ｑπ（ｓ，ａ）又は方策πを用いてもよい。例えば、行動価値関数Ｑπ（ｓ，ａ）を指標として用いた場合、動的計画部２は、状態ｓ、行動ａ及び遷移先の状態ｓ’の各組合せについての状態遷移確率Ｐａｓｓ’及び第一報酬Ｒａｓｓ’を用いて、動的計画法に基づいて、行動価値関数Ｑπ（ｓ，ａ）を計算する。そして、行動決定部２３（図３）は指標である行動価値関数Ｑπ（ｓ，ａ）を比較して、到達点に最も到達しやすい行動を決定する。具体的には、行動価値関数Ｑπ（ｓ，ａ）がその値が大きい程到達点に到達しやすいことを表すように定められている場合には、遷移前の状態ｓにおいて取り得る行動を行動ａ、遷移先の状態ｓ’において取り得る行動を行動ａ’として、ｍａｘａ’Ｑπ（ｓ’，ａ’）を比較して、ｍａｘａ’Ｑπ（ｓ’，ａ’）を最大にする行動ａを選択する。
【００７９】
上記自律移動ロボットの動作計画装置及び上記自律移動ロボットの動作制御装置における処理機能は、コンピュータによって実現することができる。この場合、これらの装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００８０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００８１】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００８２】
１     状態遷移確率計算部
１１   目標速度計算部
１２   変位量計算部
１３   確率計算部
２     動的計画部
３     発生確率記憶部
４     衝突判定部
５     記憶部
６     衝突確率計算部
７     報酬決定部
１７   指標記憶部
２１   流速差取得部
２２   遷移先予測部
２３   行動決定部
２４   制御部
２５   位置計測部
【図１】
2010165050.tif 000014
【図２】
2010165050.tif 000015
【図３】
2010165050.tif 000016
【図４】
2010165050.tif 000017
【図５】
2010165050.tif 000018
【図６】
2010165050.tif 000019
【図７】
2010165050.tif 000020
【図８】
2010165050.tif 000021
【図９】
2010165050.tif 000022
【図１０】
2010165050.tif 000023
【図１１】
2010165050.tif 000024
【図１２】
2010165050.tif 000025