【代数的トポロジー】「n次元トーラス上のお掃除ロボットと経路計画(path planning)」【LSカテゴリー特別編】

みなさんトーラスを掃除しようと思ったことはありませんか？

トーラスは結構掃除しにくそうですね。

そこで今回はお掃除ロボットを使って数学的に考察しようと思います。

前提知識・参考文献と関連記事
導入
経路計画(path planning)
Topological complexity
様々な空間のお掃除ロボットの経路計画
まとめ

前提知識・参考文献と関連記事

※本記事の命題や定理の多くの証明を省略しています。参考文献の[Far]や過去記事をご参照ください。

※こちらは読み飛ばしていただいても大丈夫です。

【前提知識】

集合と位相(連続写像やコンパクトの意味や周辺知識を知っているくらいでも。)

代数的トポロジー(ホモトピー同値をなんとなく知っているくらいでも。)

【参考文献】

[Far] Michael Farber, Topological complexity of motion planning, In: Discrete Comput. Geom. 29.2 (2003), pp. 211–221.

[CLOT] O. Cornea, G. Lupton, J. Oprea, and D. Tanr´e, Lusternik-Schnirelmann category,
vol. 103 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2003.

【関連記事】

math-topology.hatenablog.com

リンク

導入

お掃除ロボットは掃除中何度も選択を迫られます。

まずは可縮な部屋のお掃除ロボットです。

図1のような状況でお掃除ロボットの2つの経路を考えます。

これらの経路は互いに連続的に移り変わります。大きな違いはありません。

次に可縮ではない部屋を考えます。

図2のような状況ではどうでしょうか？

この場合は真ん中に穴が開いている状態ですので、2つの経路は時計回りか反時計回りで分類ができます。そのためお掃除ロボットは選択が必要になります。

さらに言えば、あらかじめどちらを選択するか計画してあげる必要があります。

今回はこの経路計画(path planning)の考え方を数学的に定義し、分類する方法を紹介します。

経路計画(path planning)

さて経路(path)は次のように定義できます。

定義1(path space)

単位区間 $I$ と弧状連結な空間 $X$ について $I$ から $X$ への連続写像の集合 $X^{I}$ にコンパクト開位相(compact open topology)を入れた空間を $PX$ と書き、これを $X$ の path space と呼ぶ。

$PX$ の任意の元 $p$ を $X$ の経路(path)と呼ぶ。

このとき $X$ の経路 $p$ に関して $p(0)\in X$ は始点、 $p(1) \in X$ は終点を表します。

写像 $\pi : X^{I}\longrightarrow X\times X$ を $\pi(p)=(p(0),p(1))$ により経路から始点、終点の情報を取り出すことができます。

コンパクト開位相の定義(開基のとり方)により、この $\pi$ は連続写像であることが容易に示されます。

次に「始点」と「終点」から経路を構成することを考えます。

すなわち $s: X\times X \longrightarrow X^{I}$ で $\pi s=\textrm{id}$ を満たす写像を考えます。

$s$ に連続性を仮定しない場合、空間 $X$ が弧状連結であることから、このような $s$ は必ず存在します。

さらに $s$ が連続写像であるとき、 $s$ を $\pi$ の(大域的な)経路計画(motion planning)と呼びます。

経路計画 $s$ はどのような空間であれば存在するのでしょうか。

補題2(経路計画の存在条件)

$s: X\times X \longrightarrow X^{I}$ で $\pi s =\textrm{id}$ となる連続写像 $s$ が存在するための必要十分条件は $X$ は可縮であること。

この補題2は「始点と終点から経路を構成し、始点や終点をずらしたときに経路も”連続的に”変形される『経路計画』があるのは可縮であるときに限る」ということを示しています。

最初の「お掃除ロボット」の図に戻りましょう。

図1(再掲)の場合は、可縮な空間のため、始点・終点に対して、連続的に経路を変形させることができます。

しかし図2(再掲)の場合はどうでしょう。

この場合、1次元球面 $S^{1}$ とホモトピー同値で、可縮な空間とは言えません。そのため視点・終点に対して、連続的に経路を変形させることは出来ません。

実際、以下の図3のように、反時計回りに経路を作ると、自己交差をもったときに連続性が"崩れ"ます。

Topological complexity

さて、可縮ではない空間では大域的な経路計画 $s$ は存在しませんが、局所的には構成できる可能性があります。

そこで以下の topological complexity (位相的複雑さ)を考えます。

定義3(topological complexity)

弧状連結な位相空間 $X$ について、 $X\times X$ の有限開被覆 $U_{i}$ ( $i=0,1,…,n$ ) で、各 $i$ に対して局所的な経路計画 $s_{i}:U_{i}\longrightarrow X^{I}$ すなわち $\pi s_{i}=\textrm{id}$ となるとき、

$\textrm{TC}(X)\le n$ と定義する。

特に、このような整数 $n$ で最小であるものを $n_{0}$ として

$\textrm{TC}(X)=n_{0}$

と書く。

(ただし、 $\textrm{TC}(X)$ のとりうる値は0以上の整数もしくは $\infty$ *1として定める。)

$X\times X$ つまり始点と終点の取り方を経路計画ができる部分に分割するには何分割で足りるかを考える量と言えます。

"位相的複雑さ"という名前からも分かるように空間の複雑さを表す指標です。

そのため、同様の指標である「LSカテゴリー」と密接な関係があります。

Remark(LSカテゴリーの定義)

位相空間 $X$ について、 $X$ の有限開被覆 $U_{i}$ ( $i=0,1,…,n$ ) で、各 $i$ に対して $U_{i}$ が $X$ において可縮、すなわち包含写像 $U_{i} \hookrightarrow X$ が null-homotopic (定値写像とホモトピック) であるとき、

$\textrm{cat}(X)\le n$ と定義する。

特に、このような整数 $n$ で最小であるものを $n_{0}$ として

$\textrm{cat}(X)=n_{0}$

と書く。

(ただし、 $\textrm{cat}(X)$ のとりうる値は0以上の整数もしくは $\infty$ *2として定める。)

上記のように定義が似ていることもありますが、加えて以下の不等式が成立します。

始点もしくは終点を固定して経路計画を考えることとLSカテゴリーを求めることは同値であることから証明は容易にできます。

命題4(LSカテゴリーとtopological complexity)

弧状連結なパラコンパクト位相空間 $X$ について次の不等式が成り立つ。

$\textrm{cat}(X) \le \textrm{TC}(X) \le 2\textrm{cat}(X)$

さらに、LSカテゴリーと同様に「不等式評価」が topological complexity の計算に役立ちます。

まず、LSカテゴリーの不等式評価の際に役立った cup length の topological complexity 版を考えます。

まず $X^{I}\simeq X$ によりホモトピーにおいては $\pi : X^{I}\longrightarrow X$ と対角写像 $\Delta : X\longrightarrow X\times X$ は自然に同一視ができます(ホモトピー類の同型があるとも言えます)。

定義5(zero-divisors cup length)

$R$ を単位元をもつ環とする。

次数つき環の準同型の核の cup length $\textrm{cup}(\textrm{Ker}H^{*}(\Delta;R))$ を zero-divisors cup length と呼ぶ。

この zero-divisors cup length と topological complexity の関係は以下のようになります。証明は省略しますが、証明においては topological complexity を sectional category や Schwarz genus の一つとして考えることでLSカテゴリーと同様に Whitehead category で表現できることが大きく活躍します。

定理6(zero-divisors cup lengthと topological complexity)

$X$ を弧状連結な CW複体とする*3。

このとき単位元をもつ任意の可換環 $R$ について以下の不等式が成立する。

$\textrm{cup}(\textrm{Ker}H^{*}(\Delta;R))\le \textrm{TC}(X)$

また、開被覆を具体的に構成することで積空間に関して以下の不等式が成立します。

定理7(積空間と topological complexity)

$X,Y$ を弧状連結な位相空間とする。

$\textrm{TC}(X\times Y)\le \textrm{TC}(X)+\textrm{TC}(Y)$

様々な空間のお掃除ロボットの経路計画

1次元球面(円)の場合

最初の例に出てきた部屋は円 $S^{1}$ とみなすことができます。

この場合は可縮でないことと具体的に局所的な経路計画を構成することで topological complexity を求められます。

$S^{1}\times S^{1}$ は2次元トーラスと同一視できます。トーラスに含まれる $S^{1}$ の一つに切り口を入れて開くと可縮な空間ができます。つまり $S^{1}\times S^{1}$ の開集合 $U_{1}$ を $(x,y)\in S^{1}\times S^{1}$ で $x \ne y$ を満たす元の集合、開集合 $U_{2}$ を $(x,y)\in S^{1}\times S^{1}$ で $x \ne -y$ を満たす元の集合とすると、それぞれが可縮となり、さらに $U_{1}\cup U_{2} =S^{1}\times S^{1}$ となります。

特に、補題2により $U_{1},U_{2}$ にはそれぞれ経路計画が存在することが分かります。

したがって $0\lt \textrm{TC}(S^{1}) \le 1$ から $\textrm{TC}(S^{1})=1$ と分かります。

2次元トーラスの場合

3次元空間内のドーナツ状の面上にくっつきながら動くお掃除ロボット(?)を考えます。

この場合は以前求めた2次元トーラスのLSカテゴリーと命題4や定理7を用いれば不等式評価により topological complexity を求められます。

まず2次元トーラス $T^{2}=S^{1}\times S^{1}$ についてLSカテゴリーは $\textrm{cat}(T^{2})=2$ となります。

よって命題4から $\textrm{TC}(T^{2}) \ge \textrm{cat}(T^{2})=2$ を得ます。

さらに定理7から $\textrm{TC}(T^{2})\le \textrm{TC}(S^{1})+\textrm{TC}(S^{1})=2$ を得ます。

したがって $\textrm{TC}(T^{2})=2$ となります。

今回、具体的な開被覆や経路計画は構成しませんでしたが、不等式評価により、topological complexity が計算できました。

n次元トーラスの場合

n次元トーラス上 $T^{n}=S^{1}\times S^{1}\times \cdots \times S^{1}$ のお掃除ロボット(??)でも経路計画が考えられます。

この場合は定理7に加えて定理6を用いることで不等式評価により topological complexity を求めてみましょう。

まず定理7を繰り返し用いることで以下の不等式を得ます。

$\textrm{TC}(T^{n})\le \textrm{TC}(S^{1})+\textrm{TC}(S^{1})+\cdots \textrm{TC}(S^{1})\le n$

次に有理数係数コホモロジー $H^{1}(S^{1};\mathbb{Q})$ の生成元のひとつを $\alpha$ とします。

第 $i$ 射影 $p_{i} : T^{n}\longrightarrow S^{1}$ $(i=1,2,\dots ,n)$ について、

$H^{*}(p_{i})(\alpha)=\beta _{i}$ とおきます。

$\beta _{i}\otimes 1 - 1\otimes \beta _{i}\in H^{*}(T^{n};\mathbb{Q})\otimes H^{*}(T^{n};\mathbb{Q})$ は明らかに zero-divisors つまり $\textrm{Ker}H^{*}(\Delta;\mathbb{Q})$ の元となります。