Global Graph と Local Graph の考察 - myamazum/private-tips GitHub Wiki

移動体の行動計画はトポロジーグラフの最適経路問題に帰結することが多い。
複数の移動体を効率的に管理する場合、共通のトポロジーグラフで演算する方法が一般的である。 一方、移動体の経路計画は各々が固有の地図（GridmapやWaypoint List）を保有している。

一般的に、共通のグラフを分割する方法か、異なるグラフで局所的な幾何構造を一致させるか、いずれかの手法がとられる。 前者は、量子化による情報学的な手法（すみません、用語の使い方は適当）であり、後者は多様体的な手法（こちらはあっていると思う）である。

  • ROS Navigation は 量子化ビット数が大きな情報空間（画像）から、量子化ビットが小さな情報空間（Gridmap）と中くらいの情報空間（Gridmap）を生成し、 前者を大域的経路探索に、後者を局所的経路探索に与えて最適化問題を解く。このとき、量子化された情報の座標系は同一である。 また、元の情報空間（画像）が異なる２つの情報空間（Gridmap）について、格子の座標系が一致する場合、２つの量子化ビット数を一致させることで情報空間を加法的に扱っても良い。
  • GPSなど自動車の地図は、トポロジーマップで情報を保存し、各ノードまたはエッジに局所的な幾何情報が保存される。これらの情報で座標系が同一のものを部分グラフとして扱う。 地図は、前述した部分グラフを複数保有する。このとき、部分グラフ同士が重畳するノードが存在するが、このノードにおいて１つの座標系と他の１つの座標系で相互に変換が成立する。 複数の部分グラフを加法的に扱うことで全体グラフを構成したとき、ある基準の姿勢から各ノードを追跡することで全ての座標系を同一の座標系で扱うことができる。

今回、行動計画を扱うグラフとして、後者の方法を対象に設計を考察する。 ここで、各移動体は各々で行動計画に必要な部分グラフを保有し、各々の保有する部分グラフが重畳する場合に、2つを重ね合わせて過渡的な全体グラフとする、ことを検討する。 すなわち、2つの異なるグラフ構造を連結し、さらに分割する仕組みを検討する。

問題を簡単にするため、Global Graph と Local Graph と呼称する。 このとき、Global Graphのノードの要素を v, ノードの集合をVとし、エッジの要素をe，エッジの集合をEとする。 また、Local Graph のノードの要素を u, ノードの集合をUとし、エッジの要素をd，エッジの集合をDとする。

Global Graph はグラフ構造を持つため、fg : E -> V x V となる写像をもち、Gg := (fg, V , E) で表す。 同様に、Local Graph はグラフ構造を持つため、fl : D -> U x U となる写像をもち、Gl := (fl, U , D) で表す。

次に、Global GraphからLocal Graphへの対応を考える。 以下の議論は、Local Graph のうち行動計画で対象となるノード、エッジを集めた部分グラフの要素、集合を対象とする。 Local Graphは上記部分グラフと異なる部分グラフを含めてもよいが、上記部分グラフとの積集合をもつ。

  1. Local Graph のノードは、Global Graph の ノードに単射する。 fv : U -> V
  2. Local Graph のエッジは、Global Graph の エッジに単射する。 fe : D -> E

ここで後述するLocal Graphに対する演算を成立させるため、以下の要請を新たに加える

  1. Global Graph の ノードの全体集合Mは、存在する全てのGlobal Graphのノードの和集合族 ∪ Vとする M := ∪ V
  2. Local Graph のノードの補集合は、Global Graph の ノードに単射する。すなわち、Local Graph のノードの全体集合Lは、Global Graphのノードと単射である。 fv : L\U -> V , L -> V
  3. Local Graph のノードの補集合は、Global Graph の ノードに単射する。すなわち、Local Graph のノードの全体集合Lは、Global Graphのノードと単射である。 fv : L\U -> V , L -> V

Global Graphの集合は、集合の代数学が成立する。

  1. 2つのGlobal Graph の ノードの和集合は以下で与えられる。 V1 ∪ V2 := {v | v ∈ V1 ∨ v ∈ V2}
  2. 2つのGlobal Graph の ノードの積集合は以下で与えられる。 V1 ∩ V2 := {v | v ∈ V1 ∧ v ∈ V2}
  3. 2つのGlobal Graph の ノードの差集合は以下で与えられる。 V1 \ V2 := {v | v ∈ V1 ∧ v ∉ V2}
  4. Global Graph の ノードの補集合は以下で与えられる。 M \ V1 := {v | v ∉ V1 ∧ v ∈　∪ V}
  5. 2つのGlobal Graph の エッジの和集合は以下で与えられる。 E1 ∪ E2 := {e | e ∈ E1 ∨ v ∈ E2}
  6. 2つのGlobal Graph の エッジの積集合は以下で与えられる。 E1 ∩ E2 := {e | e ∈ E1 ∧ v ∈ E2}
  7. 2つのGlobal Graph の エッジの差集合は以下で与えられる。 E1 \ E2 := {e | e ∈ E1 ∧ v ∉ E}
  8. Global Graph の エッジの補集合は以下で与えられる。 M \ E1 := {e | e ∉ E1 ∧ v ∈　∪ E}

一方、Local Graphの集合は、Global Graphに対する単射の要請から Global Graph の要素によって Local Graph の演算が成立する。