論文メモ - BEIKE blog

概要
読んだ論文
- 要点ピックアップ
読んだ論文
- 要点ピックアップ
読んだ論文
- 要点ピックアップ
読んだ論文
- 要点ピックアップ

概要

調べたりしたことを、ズラズラとりあえず書いていきます。

読んだ論文

AMDPについて

CoastalNavigationwithMobileRobots

要点ピックアップ

従来の運動計画アルゴリズムは、移動ロボットが確実に位置を追跡できることを前提としていることが多い。
しかし、実世界の状況では、信頼性の高い定位が必ずしも実現可能とは限らない。
部分的に観測可能なマルコフ決定過程（POMDP）は、ゴール状態に到達する確実性を最大化する方法の一つであるが、大きな状態空間では計算が困難であるという代償を伴う。
AMDPとはロボットの位置の不確実性を状態変数として明示的にモデル化し、拡張された位置不確実性空間を介して軌道を生成します。
目標地点での位置不確かさを最小化することで，ロボットが迷子になる可能性を低減します
POMDPポリシーは、従来の最適性の考慮と目標状態を達成する確実性との間で、正確に正しい種類の妥協を行います。
大規模な状態システムでは、POMDP解を計算することは困難です
POMDPの計算複雑性クラスは、PSPACE困難。
状態の拡張ロボットの状態を3次元の姿勢空間から姿勢不確かさを拡張した空間に拡張することができます．ロボットの位置分布の不確かさをエントロピーとして表現します。

読んだ論文

[]

要点ピックアップ

リアルタイム意思決定手法へのアプローチは、以下のような問題に対応しています。

ーロボットの運動と観測におけるモデル化の不確実性

ー運動計画に動的計画法(DP) を採用

ー不確実性パラメータを含むように計画の状態空間を拡大する

ーベクトル量子化によるオフライン計算情報の圧縮

DPの過程では、ロボットの運動モデルと観測モデルをそれぞれ考慮し、最適性を保証する。状態空間を不確実性パラメータを含むように拡張することで、DPの枠組みの中で観測コストを計算することができます。
第2節では、脚付きロボットリーグにおけるタスクを特定した。第3節では、提案するリアルタイム運動決定法の概要を述べる。第4節、第5節、第6節では、提案手法のタスクへの実装について述べる。第7節では、提案手法をシミュレーションと実験で評価する。
ロボットの仕事は、自分のゴールを攻撃しないように、適切な方向からボールにアプローチすることである。
The robot’s task

ー8つの離散的な歩行動作と1つの観察動作があります。

ー歩行動作は大きなオドメトリーエラーを発生させる。

ー6つのユニークなランドマークがフィールドの周りに配置されています。

ーランドマークまでの距離の測定には大きな誤差がある。

ーボールに向かって歩きながら目をそらさない

ーロボットは観測動作で自己位置推定のために頭を水平に振っている

ーロボットとボールの状態は、次の 5 つの変数（x, y, θ, r, φ）で表され、図 5 に示すようになる。(x, y, θ)はフィールド上でのロボットのポーズ、r, φはロボットからのボールの距離と向きである。

本論文では、不確実性と観測コストの側面が重要である。
不確実性は状態空間の変数として考えることができます[7]
ここで、P ss は行動 a a a をとったときの状態 s から s への遷移確率、R ss は行動 a をとったときの s から s への状態遷移の即時評価を表す。このようにして、状態の変化に対応して、状態を変化させていくことができます。本稿では、このπ ∗ を状態行動マップと呼ぶことにします。
動作を計画する際には，姿勢推定のばらつきと観測コストを考慮する必要があります．
図1はロボットが歩行動作を行うと姿勢推定のばらつきが大きくなる例を示しています．図2はロボットが観測を行うと分散が小さくなる例を示しています。
（ｘ，ｙ，θ，φ）の他に、ロボットが高確率で存在する領域の形状を表すパラメータψをもう一つ加えています。
ψは、ｘｙθ空間内の立方体であるいくつかの s pi x i y i θ s の組み合わせで表される（図６）
ψの数は計算量を節約するために、多くの組み合わせの中で 811 個に制限しています。
i ψが大きくなればなるほど、ψの数が多くなると定義しています。
ロボットの位置は三次元グリッドに、ボールの位置は二次元グリッドに分割されています。
量子化されたψは、(x, y, θ)空間内の三次元的な立方体で構成されています。ロボットの位置が正確に推定されている場合には、ψの数は少なくなります。
値の反復アルゴリズム[4]を用いて、(3)式を用いて最適なポリシー π ∗ を求める。
DPとVQの計算は、Pentium III 866MHzのPCで3日間かけて行う。
オンライン部では，ロボットの現在の状態を認識し，圧縮されたマップから最適な動作を探索することを課題としています．
自己局在化とランドマーク観測動作に伴う状態遷移のモデル化には、ユニフォームモンテカルロローカライゼーション(Uniform Monte Carlo Localization: Uniform MCL) [1]を用いています。
本研究では、シミュレーションにより本手法の効率性を検証した。自己局在化の不確実性を考慮した場合の有効性を検証するために、以下の2つの手法の結果を比較する。

ー参照地図方式：観測の判断を含めた全ての意思決定に圧縮地図を利用します。

ー閾値法：分散のない圧縮マップを用いて歩行動作の選択を行う．確率分布の幅が一定の閾値(x th , y th , θ th ) = (600[mm], 500[mm], 60[deg])を超えたとき、ロボットはランドマークを観測します。

その他の条件は以下のように定められています。

ー表４に初期条件を示す．ロボットは初期位置を把握しています。

ーロボットの実際のポーズはランダムな誤差で更新される．ロボットは遷移確率に応じて推定状態を更新する．

ーロボットは、ランドマークに対する相対位置をランダムな誤差で取得します。

ーマップケースを参照する場合、ロボットの推定状態が終端状態に属する場合にタスクを終了する。閾値ケースを使用する場合は、ロボットの推定ポーズが終端状態に属する場合にタスクを終了する。

ー成功事例としては、実際にロボットが目標位置に到達した場合です。

状態空間を拡張することでロボットの姿勢の不確実性を考慮し、オフライン計算によりDPを用いた状態行動マップを設計しました。
ミュレーションと実験により，固定閾値の場合よりも効率的にランドマークを観測できることを確認した．

読んだ論文

FindingApproximatePOMDPsolutionsThroughBeliefCompression

要点ピックアップ

POMDPは、現在知覚されている世界の状態に基づいて意思決定を行うのではなく、世界の可能性のある状態に対する信念（確率分布）を維持し、現在の信念に基づいて意思決定を行います。
POMDPは残念ながら、信念空間での計画には計算が圧倒的に複雑になるため、ほとんどの実世界の問題には役に立たないのです。
完全な信念状態の圧縮表現を用いることで、最適なPOMDPポリシーを近似する方法を提案する。この表現、拡張MDPは、基本的に信念状態をパラメータ化したものである。
本研究で例示した領域では、信念空間が最も可能性の高い状態としてパラメータ化され、信念状態のエントロピーがパラメータ化される。
パラメータを適切に離散化することで、従来の値の反復のためのMDP手法を使用して、信念空間の中にある方針を見つけることができる。
世界の大部分は，現在の状態がわかりやすい状況と，現在の状態を追いかけるのが難しい状況が重なって構成されています1．世界をセンシングすることは、行動した後の事後状態を特定するために行われなければならないが、センサーは常にその状態を特定するのに良い仕事をしているとは限らないということがポイントである。
最も信頼性の高い軌道は、オープンスペースの端に近い環境構造に近づきながら、その端を迂回することになります。このような経路は距離と時間の点では最適ではありませんが、ゴールに到達するための最良の保証を提供します。
部分的に観察可能なマルコフ決定プロセス(POMDP)は、センシングと行動の確率論的モデルを維持している(Sondik, 1971)。
単純なマルコフ決定プロセス(MDP)が、行動の結果として世界がどのように変化するかという予測不可能性の問題をモデル化しているのに対し、POMDPは、状態が何であるかを決定することさえできないという問題をモデル化している。
パラメータを適切に離散化することで、従来の値の反復のためのMDP手法を用いて、信念空間上のポリシーを見つけることができる。
値関数は、ベルマンの式(Bellman, 1957)を使用して発見されます。
この方程式は再帰的に定義され、値関数がある固定点に収束するまで、すべての状態を繰り返し繰り返すことで発見されます。
マルコフ決定過程(MDP)は，マルコフ世界でどのように行動するかを記述する計画メカニズムである．
マルコフ決定過程は，次のように与えられる．

ー状態の集合 S{s 1 , s 2 , ... s n }

ー行動の集合 A{a 1 , a 2 , ... , a m }

ー遷移確率の集合 T (s 0 , a, s = p(s 0 |s, s)

ー報酬の集合 R : S × A 7→ <

ー割引率γ[0, 1] 初期状態 s o S

部分観測可能マルコフ決定プロセス(POMDP)は、部分観測可能な世界での計画立案のためのフレームワークである(Sondik, 1971; Cassandra et al., 1994)。
部分マルコフ決定過程は，次のように与えられる．

ー状態の集合 S{s 1 , s 2 , ... s n }

ー行動の集合 A{a 1 , a 2 , ... , a l }

ー遷移確率の集合 T (s 0 , a, s = p(s 0 |s, a)

ー観測の集合 Z{z 1 , z 2 , ... ... , a l }

ー観測確率の集合 O(z, s, . , z m }

ー初期信念 p 0 (s : s S)

ー報酬の集合 R : S × A × Z 7→ <

POMDPは、初期状態の代わりに、初期信念、つまり状態空間上の確率分布で初期化されていることに注意してください。
MDPポリシーがすべての状態に対してアクションを指示するのに対し、POMDPでは、可能なすべての信念に対してアクションを指示します。
部分的に観測可能な世界で動作するポリシーのファミリーがありますが、貪欲なヒューリスティックを使用することで、最適解を見つけるという計算上の難解さを回避することができます。
エントロピーが高いほど、システムが世界の状態を知らないかのように行動することの重みが高くなります。
最初の2つのヒューリスティック（最尤状態と投票法）は、基本的にMDPの値関数に依存しています。
これまで見てきたように、欲張りなヒューリスティックの主な失敗は、信念を洗練させるために計画を立てるという考えを取り込めないことである。しかし、信念を明示的に表現すると、完全なPOMDPを解くのに高い計算コストがかかる。
最尤状態(MLS) argmax s p(s)と分布エントロピーが共同で十分な統計量の集合を形成していると仮定する。信念状態表現の一部にエントロピーを用いるのは、ある意味で信念状態の不確実性を捉えることができるので、合理的な選択である。
値関数の凸性により、期待される報酬は信念空間の中心に向かって低くなることを思い出す。
信念状態のエントロピーは、信念空間の辺からの距離に相当する。エントロピーが高いほど、システムは信念空間の中央に近く、その後の期待報酬は低くなる。
この不確実性をエントロピーで明示的にモデル化することで、プランナーは不確実性が高すぎることを容易に検出し、情報収集行動を取り、信念状態を信念空間の端に押し戻すことができるようになる。
MLS-エントロピーのペアは、真の共同十分統計量ではないが、我々が取り組んでいる問題領域にとっては合理的な選択であることを示す。
これがこの状態表現、つまりMLSをエントロピーで補強したものであり、これを拡張MDPと呼ぶ。次に、任意のPOMDPを取り、拡張された表現を用いてMDP技法を用いて解く方法を示します。
我々は、MDPソルバーで使用できるような従来の状態表現に近づいています。しかし、まだ連続的な状態因子があります。
基礎となる状態表現が離散的でない場合は離散化し、可能なエントロピーレベルH(p(s))を離散化することで、完全に離散的で有限な状態空間2を実現します。
この離散的で有限な表現により、式(1)のMDPを解くときに行ったのとまったく同じように、信念状態に対する値の反復を使用することができます。
ずっと簡単なのは、信念を前方に伝搬させて、可能性のある事後状態とその遷移確率を同時に特定することである。
初期信念 b i 、行動 a 、観測 z が与えられると、まず、次のようにして事後信念 b j を生成する。
事後信念は行動だけでなく観測にも依存し、観測は確率的に放出されるので、事後信念には観測の関数としての確率分布があり、それは遷移関数 T H (b i , a, b j )によって捕捉されなければならない。
報酬を拡張MDP形式に拡張するために、期待される即時報酬を適用する。
空間内のあらゆる点でのセンシングの影響、特に局所的な環境構造と局所的な群衆の両方の定位プロセスへの影響をモデル化することで、拡張MDP機械を使用して、よりロバストな軌道を生成することができました。
これらのよりロバストな軌道は、群衆や情報に乏しいセンサーデータのために見失う可能性を最小限に抑えました。
エントロピーで不確実性を測定し、定位推定値を改善するために行動するという問題は新しいものではなく、能動的定位の文献にも見られる(Fox et al., 1998)。
同様に、POMDPスタイルのプランナーは、定位の失敗から回復するために使用されてきた(Nourbakhsh et al., 1995; Koenig and Simmons, 1996; Takeda et al., 1994)が、これらのプランナーが使用するヒューリスティックの貪欲な性質は、拡張MDPが生成するグローバルなスタイルの計画を妨げるものである。
トポロジカル環境では、完全なPOMDPプランナーが使用され、ある程度の成功を収めている(Mahadevan, 1998)。
信念状態を次のように表現する。 gyazo.com
記述されているようなマルコフ定位には、動的障害物や人の概念がなく、それらがセンシングとそれに続く事後の信念に与える影響もない。
この破損モデルを説明するためには、個々のセンサの測定値が持つ効果を変える必要があります。
実際には、速度を上げるために、信念状態が式(11)で与えられた拡張表現に圧縮された後にのみ、平均化を実行する。

*圧縮表現から完全な信念状態を再構築する。

ー式(21)からp(x i |a j )を計算する。

ー式(26)から潜在的な観測z kを生成する。

ー式(25)から新しい事後処理p(x 0 i |z k , a j )を生成する式(28)から遷移確率T H (p(x 0 i ), a j , p(x i ))を計算する。

ーすべての9つのサンプルされたオブザベーションについて繰り返す

より高い位置情報は、ディスプレイケースの壁に近づくことで得られるもので、より多くの環境構造が見えているため、位置を特定する能力が高まり、また、センサーからの情報が人ごみによって破損する可能性が低くなります。
ロボットはゴールに向かって移動し、障害物を通過し、障害物のセンサー範囲内に入ったら再配置し、ゴールに戻ります。これらの定期的な再配置は、ロボットが最小の位置不確実性と最大の信頼性でゴールに到着するために不可欠です。
拡張MDPが本当にナビゲーションの信頼性を向上させていることを示すために、センサの最大射程距離を減少させましたが、これはロボットの情報収集能力と正確な位置特定能力を大幅に阻害しました。
航法の信頼性の指標として、博物館環境でシミュレートされた一連の軌道上で、ゴールでの最終的な信念状態のエントロピーを調べました。信念状態のエントロピーが低ければ低いほど、ロボットの位置知識が優れており、結果としてゴール達成の信頼性が高いことがわかりました。
沿岸プランナーは、レーザセンサの全範囲で不確かさが低く、短距離では実質的に低くなっており、局在が最悪の場合には拡張MDPが最も効果的であることが確認されました。
さらに良いことに、オーグメンテッドMDPは、局在が最悪の場合には実質的に劣化していないように見えます。
もしロボットの最終的な位置が従来のプランナーよりも正確でない場合、ロボットの位置に対する確信が現実を反映していないため、拡張MDPは実際にはより悪いプランナーになる可能性があります。

読んだ論文

Uncertainty-Aware Path Planning for Navigation on Road Networks Using Augmented MDPs

要点ピックアップ

ほとんどのロボットは状態推定問題を解決するために確率的アルゴリズムを使用しますが、経路計画はロボットの位置に関する不確実性を考慮せずに実行されることが多いです。
しかし，不確実性は計画を立てる上で重要であるが，不確実性を考慮すると計算量の多いアルゴリズムになってしまうことが多い．
ロボットの世界に対する信念、認識、行動実行の不確実性を考慮した経路計画の問題を検討する。
我々は、部分的に観測可能なマルコフ決定過程を近似するために、不確実性を拡張したマルコフ決定過程の使用を提案し、ロボットの位置に関する信念がどのように環境を伝搬するかを推定するために、局在化事前処理を採用する。
これにより、不確実性の程度に応じた意思決定が可能でありながら、計算が容易であるナビゲーションポリシーを生成するプランニングアプローチを実現しました。
本研究では、このアプローチを実装し、さまざまなナビゲーション問題について徹底的に評価しました。
実験の結果、不確実性を無視するアプローチよりも効果的な政策を計算できること、また、常に最も安全な行動をとる政策よりも優れた政策を計算できることが示唆された。
ほとんどの計画システムはロボットの位置が既知であると仮定して経路を計算します。
ロボットが正確に定位している場合には、計画中の位置の不確実性を無視しても良いかもしれませんが、不確実性が大きい場合には、最適ではないナビゲーションの決定につながる可能性があります。
不確実性を考慮した経路計画は、位置の不確実性が大きい場合に誤って迂回するリスクを減らすことができる。
図１の場合、ロボットは周囲に特徴があり、正確な定位が期待できる交差点Ｃに向かって航行することができます。そこでは、ロボットは安全にゴールに向かって旋回することができ、長い遠回りをするリスクを減らすことができます（緑）。
このような問題の一般的な形式化として、部分観測可能マルコフ決定プロセス(POMDP)があります。
しかし、POMDPは実世界での応用ではすぐに困難になる。
計算効率が高く、かつ定位の不確実性を考慮できる近似法を検討する。
本論文の主な貢献は，ロボットの位置や行動実行の不確実性を考慮した道路ネットワーク上での経路計画に向けた一歩を踏み出すための新しいアプローチである．
我々のアプローチは、不確実性を状態の一部としてモデル化することでPOMDPを近似する拡張マルコフ決定プロセス(A-MDP) [24]に依存している。
我々の計画アプローチは、第一に、不確実性の程度に応じて異なる行動を選択することができ、第二に、複雑な状況では、不確実性の下で動作するが不確実性を無視した最短経路政策よりも平均的に短い計画を導く。
我々は本研究でもこれらの地図を使用している．（トポロジカルマップ）
マルコフ決定プロセス（MDP）は、状態は完全に観測可能だが行動がノイズの多い計画問題を最適に解くことを可能にする。
MDPを解くためのアルゴリズムは、政策の反復処理など、広く研究されているものが多い。
状態が観測可能でない場合、問題は部分的に観測可能なMDP、すなわちPOMDPに変わる。POMDPの計算複雑度はしばしば高すぎて、実世界の問題に有用な結果を提供することができません[21]。
いくつかのアプローチは、POMDPを局所的に解くためにサンプリング法を使用しています。
Royら[24]は、POMDPを近似するために拡張マルコフ決定プロセス(A-MDP)を提案した。
A-MDPは、POMDPを不確実性を含む拡張された状態表現を持つMDPとして形式化する。
本論文では，ロボットの位置の不確実性を考慮した道路網上の経路計画にA-MDPを用いる．
このように不確実性を計画プロセスに組み込むアプローチは、通常、信念空間での計画と呼ばれている。
信念ロードマップ[23]は、線形ガウス系のために信念空間で計画する確率的ロードマップアルゴリズムの変形である。
Plattら[22]は、最尤オブザベーションを仮定し、線形二次規則を用いてポリシーを生成する。LQG-MP [2]は、パスに沿ってロボットの状態を推定するために、LQGコントローラとカルマンフィルタを組み合わせ、最適な候補パスを選択する。
これらのアプローチは，実行中にセンサやプロセスノイズを考慮せずにオフラインで経路を計算します．
FIRM [1]は確率的ロードマップを信念空間上で一般化したもので、将来起こりうるすべての観測を考慮して各ノードに一意の信念を割り当てる。しかし、FIRMは、異なる信念を持つノードに到達することを考慮していない。
対照的に、我々のアプローチでは、異なる程度の不確実性を扱うポリシーをオフラインで生成し、現在のロボットの信念を与えられた最適な行動をオンラインで選択する。
我々は離散空間表現を考え、Bopardikarら[5]に似たロボットの信念のコンパクトな表現を使用して、より大きな環境に取り組み、実世界への応用に向けた一歩を踏み出す。
ロボット定位のためのいくつかの確率論的アプローチは占有グリッドマップに依存しているが，トポロジーグラフは計画を立てるための有効な表現である．
マルコフ定位は，スキャンとオドメトリを用いて離散ベイズフィルタを用いてロボットの位置を推定します．
ロボットの位置に関する信念は，X の全セルを対象としたヒストグラムの形をした確率分布で表され，確率が特定の分布クラスに限定される必要はありません．
OSM データから得られた建物の足跡とレーザー距離計のセンサモデルがあれば、特定の場所で発射されたスキャンが定位にどのような影響を与えるかを事前に推定することができる。
この事前推定は、Vysotska and Stachniss [27]によって提案された方法を用いて計算する。この方法では、地図をレイキャストすることで、各場所で仮想スキャンをシミュレートする。
仮想センサを平行移動・回転させ、スキャンと地図との誤差を推定する。
観測尤度の減衰を考慮して、位置不確かさの下でスキャンがどれだけ地図と一致しているかを推定する共分散行列を計算する。周囲の環境が特徴的な形状を持つ場所では、共分散は小さく、周囲の環境が情報的でなかったり、曖昧な場合には大きくなります。
我々は、Ｘ内の各トラバース可能なセルについてこの優先順位を計算し、これを局在性マップＺと呼ぶ（例えば、図２ｄを参照）。
遷移関数は、道路によって接続された交差点間の遷移を可能にし、報酬は道路の長さに対応する。
このMDPを解くことで、最短経路に沿ってロボットをゴールに導くナビゲーションポリシーが生成される。
MDPはロボットの正確な位置が常に知られていることを前提としており、実際にはそうでないことが多い。そのため、位置の不確実性が大きい状況でMDPポリシーに従うと、ロボットは間違った道を通って長い遠回りをしてしまう可能性があります。
本研究では，ロボットの位置に関する不確実性を計画プロセスに統合することで，交差点での意思決定を改善することを提案する．この問題の一般的な定式化はPOMDPである。しかし、POMDPは一般的に解くのが難しい。
我々は、道路ネットワーク上の経路計画のために、従来のMDP状態をロボットの位置の不確実性で拡張する拡張MDP（A-MDP）[24]を設計することでPOMDPを近似している。
状態表現が拡張されているため、遷移関数や報酬関数が複雑になっている。しかし、A-MDPは最終的な定式化では、状態の数が増えることを除けば、MDPと似たような表現になります。
したがって、A-MDPはMDPと同じアルゴリズムを用いて解くことができる。
我々は、ロボットの位置の不確かさを表す統計量でMDP定式化の状態を補強することで、我々のA-MDPの状態空間を定義します。
不確かさを表現するために異なる統計量を使用することができますが、一般的には、よりコンパクトな表現であればあるほど、プランナはより効率的になります。
我々の定位システムはあらゆる種類の信念を生成する可能性がありますが、我々は計画中に信念を等方的な共分散を持つガウス分布で近似することができると仮定し、対応する分散を不確かさを表現するために使用しています。
この表現は、状態空間を1次元だけ拡張するので、計画の複雑さが爆発的に増大することを避けることができる。
我々のA-MDPでは，MDPと同様に，道路の交差点で方向を取ることを行動としている．ここでは，交差点は，基数方向に対応する最大4つの道路の分岐点であると仮定する．したがって、A = {↑,↓,←, →}がアクションの集合となる。必要であれば、より多くのアクションを簡単に追加することができる。
A-MDP遷移関数T (s 0 | s, a)は、拡張された状態s∈Sとアクションa∈Aを入力とし、それをA-MDP終了状態s 0 ∈Sの確率分布に写像します。我々は3つのステップでTを定義します。

1) すべてのv∈V、a∈Aについて、入力位置の不確実性を考慮せずに、交点から始まるロボットの位置事後処理p(x | v, a)を計算する。

2) 交差点から始まる可能性のある全ての事後処理を、sに対応する信念に従って積分することで、状態sから始まる事後処理を計算する p(x | s, a)。

3) 状態遷移T (s 0 | s, a)を定義し、sから始まる事後処理をA-MDPの状態表現にマッピングする。

道路に沿って移動中のロボットの位置に関する信念はガウス分布で近似できると仮定し、拡張カルマンフィルタ（EKF）の予測ステップを用いてそれを推定します。
ここで、μ̂ t = g(μ t-1 , u t )、Σ̂ t = + M t、G tはgのヤコビアンです。その代わりに、位置不確かさマップZを計算し、EKF予測からの共分散Σ ̂ tと位置不確かさ共分散Σ μ ˆ t ,Z at μ̂ tを組み合わせることで、道路に沿ってどのように位置不確かさが伝播するかを推定するために使用します。
例えば，図 3 の場合，v i から右方向に移動しているときに，ロボットが v j を見逃して v k や v l に到達してしまう可能性がある．我々は，不確かさΣj|ia が小さいほど，ロボットが v j を検出する確率が高くなるように，ロボットが v j を検出する確率を計算する．
交差点vで行動aをとった場合、到達可能な交点のそれぞれに到達する確率を考慮して、事後的なp(x | v, a)を計算します。
ロボットの入力位置がA-MDP状態s∈Sに対応する信念で表現されていると考えます。入力位置は確率分布で記述されているので、行動を取ることの事後処理は、起こりうるすべての可能性のある遷移を表すべきです。したがって、ロボットの位置の事後確率 p(x | s, a) を計算します。
ここで、ηは正規化係数である。状態遷移。A-MDP状態sから別の状態s 0への行動aの遷移確率を定義するには、ロボットの位置がsから始まることに関する事後確信度p(x | s, a)と、s 0で表される確信度との対応を計算する必要があります。このために、同じドメイン上の2つの分布間のオーバーラップ量を測定するBhattacharyya距離D B [4]を使用します。
Bhattacharyya距離は分布間の類似性の対称的な尺度であるため、Kullback-Leiblerダイバージェンス[17]よりもBhattacharyya距離の方が好ましい。
我々は、結果として得られる政策が不確実性を考慮した決定を行うようなA-MDPの報酬関数を定義する。同様に、我々の報酬関数は負の時間を最大化します。遷移関数と同様に、まず、入力と終了位置の不確実性を考慮しない交点r間をナビゲートするための報酬を計算し、交点間の報酬を組み合わせてA-MDP報酬関数Rを定義します。
ここで ` は道路の長さを示し，ロボットは単位速度で移動すると仮定する．v k が v i から a を通って到達できない場合は，r に一定のペナルティを与える．
我々は、遷移の不確実性を反映するように、A-MDP状態sから別の状態s 0へ行動aを取ることの報酬R(s 0 , a, s)を、s, s 0∈Sで計算する。このために、入力状態と終了状態sとs 0に対応する信念に従って、交点r間の報酬を組み合わせる。
我々は、政策反復アルゴリズム[13]を用いてA-MPDを解く。
ポリシー反復は、固定の割引報酬を持つMDPを解くために、状態と行動の数に多項式的な制限を与えるが[20]、実際には、その方がはるかに効率的であることが多い。
上で定義した A-MDP を解くと、ロボットの位置に関する信念が与えられ、最適な行動を選択して実行するポリシー π ∗ が得られる。
航法中、ロボットの位置に関する X 上の推定値 bel(x) を連続的に計算する。ロボットが交差点に到達すると，bel(x)までの距離が最小となるA-MDP状態を計算する．
我々はこの問題を、完全なPOMDPを解くことなく、ロボットの位置の不確実性を状態空間に組み込む拡張マルコフ決定過程として定式化する。
定位事前分布を用いて、道路網に沿ったロボットの信念伝搬を推定することで、A-MDP遷移関数を定義する。
航法中、我々は定位システムから提供される信念をAMDPの状態表現と一致させ、最適な行動を選択する。実験の結果、不確実性が小さい場合には最短経路ポリシーと同様の性能を発揮するが、不確実性が大きく、最適でない決定を行うリスクが増大する場合には、我々のアプローチが優れていることが明らかになった。
我々のアプローチは、ロボットの不確実性に関する知識を利用することで、安全性と移動時間をトレードオフすることができます。
この実験では、我々のプランナーが、最短パスと安全パスの両方の世界のベストを選ぶことによって、状況と不確実性に適応する能力を示しています。
不確実性の程度に応じて、ロボットをゴールに導く行動を選択し、安全性と移動時間をトレードオフにします。
我々のアプローチは、不確実性が小さい場合には最短経路と同様の戦略に従うため、ミスはほとんどありません。
しかし、不確実性が大きくなるようなトリッキーな状況では、我々のアプローチは安全な経路と同様の決定を行い、それによって長い迂回路を避けることができる。そのため、不確実性の程度に応じて適切な航行行動をとることができ、全体的に最短経路や安全経路を凌駕しています。
位置の不確実性を考慮したルート計画のアプローチはPOMDPよりも効率的ですが、道路や交差点の数が非常に多い都市規模でのポリシーの計算は依然として複雑です。ただし、不確実性の下での計画は、実際にはローカルスケールでより関連性が高く、交差点でのミスが重大な迂回路につながる可能性があります。