修士論文
ロボット工学に現れる配位空間のトポロジーについて

江本 安佳里奈良女子大学大学院 人間文化研究科 数学専攻

2007 年

目次
1序文

22

配位空間

43グラフの配位空間

64

簡約化された配位空間

115

完全グラフ・完全二部グラフの簡約化された配位空間

156

主結果

241

1

序文

工場のフロアなどで自動化されたロボットを使用することは，様々なコストを削減することにつながるはずである．ただし，そのロボット同士が作業中に衝突して転倒などしてしまえば意味が無い．自動化された複数のロボットを衝突させることなく自由に動かすためにはどうしたらいいだろうか．
考えられる一つの方法として，次のものがある．フロア内で考えられるロボットのすべての配置によって構成される空間を作り，そこから２台以上のロボットが同じ地点にいる配置を取り除くことで，ロボットの動きを安全にプログラム出来るような空間を得るという方法である．
本論文ではこれを，ロボットが動き回る場所を R2 内の部分集合，ロボットをその部分集合を動く点 (動点) とみなし，数学的な考察を行う．

X を位相空間，N を自然数とし，一瞬一瞬の N 台のロボットの安全な配置により生成される空間を配位空間と呼び，数学的にC N (X) = (X· · × X) − Δ
 × ·N 個と定める．ただし Δ = {(x1 , x2 , ...., xN ) ∈ X N ; i = j で，xi = xj となる i, j が存在する }．
まず障害物も何もない平面上で動くロボットの場合を考え，次にフロア内に埋め込まれたレール上を動くロボットの場合についても考えることにする．この場合は，レールをグラフとみなすことで同様に議論することが可能である．
しかし，配位空間では複数のロボットが同じ地点にいるとき，つまり衝突するその瞬間のロボットの配置を除いただけであり，まだまだ安全性は不十分である．より安全な空間を得るためには，次に予想される動きによって衝突する可能性のある配置も取り除くべきである．
そこで，この取り除いた空間を簡約化された配位空間と呼び，数学的にD N (X) = (X· · × X) − Δ̃
 × ·N 個と定める．ただし Δ̃ は X × · · · × X の中の Δ を含むセル全体から成る集合である．
導き出された主結果を以下に述べる．
定理 1．
Kn を n 個の点からなる完全グラフとする．
D N (Kn ) が閉曲面であるための必要十分条件は⎧⎧⎨N = 2⎨N = 3または⎩n = 5⎩n = 52である．更に D 2 (K5 ) は種数 6 の閉曲面，D 3 (K5 ) は種数 16 の閉曲面に同相である.
定理 2．
Km,n を２つの素な m 個の点の集合と n 個の点の集合からなる完全二部グラフとする．
D N (Km,n ) が閉曲面であるための必要十分条件は⎧⎧⎨N = 2⎨N = 4または⎩m = n = 3⎩m = n = 3である．更に D 2 (K3,3 ) は種数 4 の閉曲面，D 4 (K3,3 ) は種数 37 の閉曲面に同相である.
本論文の構成は以下の通りである．
第２章では，配位空間を定義する．第３章では，位相空間が特にグラフのときの配位空間をみる．第４章では，簡約化された配位空間を定義し，前章で取り挙げたグラフそれぞれの簡約化された配位空間をみる．第５章では，グラフの中でも特に完全グラフや完全二部グラフの簡約化された配位空間の例をみる．第６章では，前章までにみた様々な例から完全グラフや完全二部グラフの簡約化された配位空間が閉曲面と同相になるのはいつか，またそのときの種数を調べている．

最後にこの論文を作成するにあたり，ご多忙にも関わらず丁寧にご指導いただきました
片桐民陽先生，小林毅先生に深く御礼申し上げます．

32配位空間

工場のフロアなどで，自動化された何台ものロボットを衝突させることなく自由に動かすためにはどうしたらいいだろうか. 一つの方法として，フロア内で考えられるロボットのすべての配置によって構成される空間を考え，そこから２台以上のロボットが同じ点にいる配置を取り除き，ロボットが安全に動き回れるようプログラムが可能な空間を得る方法がある．
以下，フロアを R2 内の部分集合，ロボットをその空間内を動く点 (動点) とみなし，数学的な考察を行う．
定義 1. 配位空間の定義

X を位相空間，N を自然数とし，Δ = {(x1 , x2 , .... , xN ) ∈ X N ; i = j で，xi = xj となる i, j が存在する }
とおく．
このとき

C N (X) = (X· · × X) − Δ
 × ·
N 個を配位空間 (cof iguration space) と呼ぶ．
注意）C 1 (X) = X である．

例 2.1. C 2 (R) = (R × R) − Δ = {(x1 , x2 ) ∈ R × R ; x1 = x2 } は，R2 平面上から直線を除いた空間と同相である．

例 2.2. S 1 = {(x, y) ∈ R ; x2 + y 2 = 1} とする．C 2 (S 1 ) は，トーラスから円周を除いた空間と同相である．

4

例 2.3. C 2 (R2 ) は R2 × R2 − {(0, 0)} ，R3 × S 1 と同相である．
証明. f : C 2 (R2 ) → R2 × R2 − {(0, 0)} を f (x1 , x2 ) = (x1 , x1 − x2 ) と定めると
C 2 (R2 ) ∼= R2 × R2 − {(0, 0)} ．
また g : R2 × R2 −{(0, 0)} → R3 ×S 1 を g(α1 , α2 ), (β1 , β2 )= α1 , α2 , log

tan−1 ββ21 と定めると R2 × R2 − {(0, 0)} ∼= R3 × S 1 ．
これより，C 2 (R2 ) ∼= R2 × R2 − {(0, 0)} ∼= R3 × S 1 が示せた．

5

β1 2 + β2 2 ,3グラフの配位空間

第 2 章では障害物も何も無いフロア上でのロボットの動きについて考えた．次はフロア内に，ロボットがその上を動くように敷かれたレール上でのロボットの動きを考えることにする．これはレールをグラフとみなすことで，先と同様に数学的な考察が可能である．
以下に記号の説明をする．

n セルとは，B n = {(x1 , .... , xn ) ∈ Rn ; x1 2 + · · · + xn 2 < 1} と同相な位相空間である．
ただし，０セルは１点と同相な位相空間である．
Γ をグラフ，z1 , .... , zN を Γ の０セルまたは１セルとする．z1 × · · · × zN で Γ 上を移動する N 台のロボットのうち，すべての k ∈ {1, .... , N } に対して k 台目のロボットがzk にいる配位全体を表すこととする．
グラフ Γ の配位空間 C N (Γ) の位相的な性質をみるためには，まず C N (Γ) を構成する
N セル z1 × · · · × zN をすべて求める．そして，その各 N セルの境界である N − 1 セルのラベルをみて，同じものを向きもこめて貼り合わせるという操作が必要となる．
例 3.1. C 2 ()は，０セル a ∼ d と１セル A ∼ C からなるグラフ．C 2 (下の通りである．

6) を構成する２セルは以これらを同じラベルの１セル同士で向きを保ったまま張り合わせていくと，下のような配位空間となる．

例 3.2. C 2 ()は，０セル a ∼ c と１セル A ∼ C からなるグラフ．C 2 (下の通りである．

7) を構成する２セルは以これらを同じラベルの１セル同士で向きを保ったまま張り合わせていくと，次のパーツが出来上がる．

これらを更に貼り合わせていくと，下のような配位空間となる．

8

例 3.3. C 2 ()は，０セル a ∼ e と１セル A ∼ D からなるグラフ．C 2 (下の通りである．

9) を構成する２セルは以これらを同じラベルの１セル同士で向きを保ったまま張り合わせていくと，以下のようなパーツが出来上がるので，それを更に変形させる．

これらを更に貼り合わせていくと，下のような配位空間となる．

10

4

簡約化された配位空間

配位空間で取り除いた Δ は，ロボット同士がまさに衝突する瞬間を表すものであった．
より安全にロボットを動かすためには，ロボットが衝突する直前の配置を表すセルも取り除く必要がある．
定義 2. 簡約化された配位空間

Δ̃ を X × · · · × X の中の Δ に接するセル全体から成る集合とする．
D N (X) = (X· · × X) − Δ̃
 × ·
N 個を簡約化された配位空間 (discretized conf igurationspace) と呼ぶ．
注意）位相空間 X がグラフでないとき D N (X) は常に空集合である．よってこの後の議論では X がグラフのときについて考えていく．ただし N = 1 のとき，D 1 (Γ) = C 1 (Γ) = Γである．
定義に従って考えてみると，D 2 ( ) は，例 3.1 の C 2 ( ) から２セルをすべて取り除くことで得られる．つまり D 2 ( ) は次のような空間となる．

同様に D 2 (), D 2 ( ) を考えると，次のような空間となる．

11

ここで，命題を一つ述べる．
命題 1. E N (Γ) を，Γ 上の任意の動点２個とそれらをつなぐ任意の道が少なくとも１本の完全な１セルを含む配位全体の集合とする．
このとき D N (Γ) = E N (Γ) が成り立つ．
証明. (Γ × · · · × Γ) − E N (Γ) = Δ̃ を示せばよい．
(Γ × · · · × Γ) − E N (Γ) は，Γ 上のある２個の動点をつなぐ道が１本の完全な１セルを含まない配位全体の集合なので，これは Δ̃ に等しい．
この命題より，グラフ上の動点の配置から直接 D 2 (Γ) を構成するセルを数え上げることも可能である．
以下この方法で，各グラフの簡約化された配位空間が先に見た図と一致するかを確かめる．
例 4.1. D 2 ( )は，０セル a ∼ d と１セル A ∼ C からなるグラフ．D 2 (下の通りである．

) を構成する１セルは以これらを同じラベルの０セル同士で張り合わせていくと，下のような簡約化された配位空間となる．

12

例 4.2. D 2 ( )は，０セル a ∼ c と１セル A ∼ C からなるグラフ．D 2 (下の通りである．

) を構成する１セルは以これらを同じラベルの０セル同士で張り合わせていくと，下のような簡約化された配位空間となる．

例 4.3. D 2 ( )は，０セル a ∼ e と１セル A ∼ D からなるグラフ．D 2 (下の通りである．

13) を構成する１セルは以これらを同じラベルの０セル同士で張り合わせていくと，下のような簡約化された配位空間となる．

14

5完全グラフ・完全二部グラフの簡約化された配位空間

グラフの中でも，相異なる２つの点がすべて隣接している単純グラフを完全グラフと呼び，n 個の点をもつ完全グラフを Kn と書く．
また，グラフの点集合が２つの素な集合 A と B に分割でき，グラフのすべての辺が Aの点と B の点を結ぶようにできているとき，このグラフを二部グラフと呼ぶ．更に中でも，A の各点が B の各点とちょうど一本の辺で結ばれている二部グラフを完全二部グラフと呼び，m 個の点の集合と n 個の点の集合からなる完全二部グラフを Km,n と書く．
この章以降は，完全グラフ Kn や完全二部グラフ Km,n の簡約化された配位空間についてみていくことにする．
例 5.1. D 2 (K5 )K5 は，０セル a 〜 e と１セル A 〜 J からなる完全グラフ．D 2 (K5 ) を構成する２セルは以下の通りである．

1516これらを貼り合わせ変形させると，D 2 (K5 ) は下のような位相空間と同相になる．

実際に D 2 (K5 ) を構成する各セルを数えると，０セルは 20 個，１セルは 60 個，２セルは 30 個である．
よってオイラー数は X D 2 (K5 ) = 30 − 60 + 20 = −10．種数は g = 1 − 12 × (−10) = 6．
この結果からも，D 2 (K5 ) は上のような閉曲面であることが確かめられる．
例 5.2. D 2 (K3,3 )K3,3 は，０セル a 〜 f と１セル A 〜 I からなる完全グラフ．D 2 (K3,3 ) を構成する２セルは以下の通りである．

1718これらを貼り合わせ変形させると，D 2 (K3,3 ) は下のような位相空間と同相になる．

実際に D 2 (K3,3 ) を構成する各セルを数えると，０セルは 30 個，１セルは 72 個，２セルは 36 個である．
よってオイラー数は X D 2 (K3,3 ) = 36 − 72 + 30 = −6．種数は g = 1 − 12 × (−6) = 4．
この結果からも，D 2 (K3,3 ) は上のような閉曲面であることが確かめられる．
例 5.3. D 3 (K5 )まず，D 3 (K5 ) が閉曲面と同相になることを示す．
１個の動点が点 a 上にあるとする．このとき２セルを作るための残り２個の動点の配置は(a) 辺 B と辺 D(b) 辺 C と辺 J(c) 辺 G と辺 Hのいずれかである．

19

(a) の場合
この動点の配置によって作られるのは，次の２セルである．

この境界の１セル B × d × a は B × E × d という２セルの境界でもある．更に，この１セルを境界として持つ２セルはこの二つのみである．
同様に，B × e × a を境界としてもつ２セルは B × I × e ，b × D × a を境界としてもつ２セルは D × F × b ，c × D × a を境界としてもつ２セルは D × A × c である．

(b) の場合
この動点の配置によって作られるのは，次の２セルである．

この境界の１セル C × b × a は C × E × b という２セルの境界でもある．更に，この１セルを境界として持つ２セルはこの二つのみである．
同様に，C × e × a を境界としてもつ２セルは C × A × e ，c × J × a を境界としてもつ２セルは I × J × c ，d × J × a を境界としてもつ２セルは F × J × d である．

(c) の場合
この動点の配置によって作られるのは，次の２セルである．

20

この境界の１セル G × c × a は G × E × c という２セルの境界でもある．更に，この１セルを境界として持つ２セルはこの二つのみである．
同様に，G × e × a を境界としてもつ２セルは G × F × e ，b × H × a を境界としてもつ２セルは I × H × b ，d × H × a を境界としてもつ２セルは A × H × d である．

(a) 〜 (c) よりどの２セルも必ず他の２セルと貼り合わせることができ, K5 の対称性から，D 3 (K5 ) は閉曲面となることが示せた．
また，この空間を構成する各セルの数は以下の通りである．

(ア) ２セルの数

1
10 × 3 ×2
× 3! = 90.

(イ) １セルの数(10 × 3 C2 ) × 3! = 180.
(ウ) ０セルの数
5 P3 = 60.

よって D 3 (K3 ) のオイラー数は X (D 3 (K5 )) = 90 − 180 + 60 = −30．
種数は g = 1 − 12 × (−30) = 16．
D 3 (K3 ) は種数 16 の閉曲面と同相となることがわかる．

例 5.4. D 4 (K3,3 )まず，D 4 (K3,3 ) が閉曲面と同相になることを示す．
２個の動点がそれぞれ点 a と点 d 上にあるとする．このとき２セルを作るための残り２個の動点の配置は(a) 辺 E と辺 I(b) 辺 F と辺 H

21

のいずれかである．

(a) の場合
この動点の配置によって作られるのは，次の２セルである．

この境界の１セル E × c × a × d は C × E × c × d という２セルの境界でもある．更に，この１セルを境界として持つ２セルはこの二つのみである．
同様に，E × f × a × d を境界としてもつ２セルは E × G × a × f ，b × I × a × d を境界としてもつ２セルは B × I × b × d ，e × I × a × d を境界としてもつ２セルは D × I × a × eである．

(b) の場合
この動点の配置によって作られるのは，次の２セルである．

この境界の１セル F × c × a × d は B × F × c × d という２セルの境界でもある．更に，この１セルを境界として持つ２セルはこの二つのみである．
同様に，F × e × a × d を境界としてもつ２セルは G × F × a × e ，b × H × a × dを境界としてもつ２セルは C × H × b × d ，f × H × a × d を境界としてもつ２セルはD × H × a × f である．

(a), (b) よりどの２セルも必ず他の２セルと貼り合わせることができ, K3,3 の対象性から，D 4 (K3,3 ) は閉曲面となることが示せた．
また，この空間を構成する各セルの数は以下の通りである．

(ア) ２セルの数

1
9×4×222
× 4! = 432.

(イ) １セルの数(9 × 4 C3 ) × 4! = 864.
(ウ) ０セルの数
6 P4 = 360.

よって D 4 (K3,3 ) のオイラー数は X (D 4 (K3,3 )) = 432 − 864 + 360 = −72．
1
種数は g = 1 − × (−72) = 37．
2
D 4 (K3,3 ) は種数 37 の閉曲面と同相となることがわかる．

23

6主結果

第 5 章では，完全グラフや完全二部グラフの簡約化された配位空間の例をいくつかみたが，それらは全て閉曲面と同相であった．ここで疑問となるのは，例以外に閉曲面となる
D N (Kn ) や D N (Km,n ) は存在するのかということである．
補題 1. D N (Γ) が閉曲面，αi を D N (Γ) の i セルの数とする．このとき 2α2 = α1 が成り立つ．
証明. 4α2 = 2α1 なので明らか．
まずは N = 2 のときに，D N (Kn ) や D N (Km,n ) が閉曲面となる Kn , Km,n を調べる．
命題 2. D 2 (Kn ) が閉曲面となるのは，n = 5 のときのみである．
証明. D 2 (Kn ) は n = 1 のとき空集合，n = 2 のとき単なる点なので，閉曲面とはならない．従って n ≥ 3 としてよい．
D 2 (Kn ) を構成する各セル数を数えると，0 セルの数は n(n − 1) 個，1 セルの数はn(n − 1)(n − 2) 個，2 セルの数は 14 n(n − 1)(n − 2)(n − 3) 個である．
これより D 2 (Kn ) のオイラー数はX (D 2 (Kn )) ===1n(n − 1)(n − 2)(n − 3) − n(n − 1)(n − 2) + n(n − 1)
41n(n − 1)(n2 − 5n + 6 − 4n + 8 + 4)
41n(n − 1)(n − 3)(n − 6)4となる．
補題より，D 2 (Kn ) が閉曲面となるのは 2 × 14 n(n − 1)(n − 2)(n − 3) = n(n − 1)(n − 2)が成り立つときである．
これを解くと，n ≥ 3 より n = 5 が得られる．
命題 3. D 2 (Km,n ) が閉曲面となるのは，(m, n) = (3, 3) のときのみである．
証明. m ≥ n としても一般性を失わないので，m ≥ n と仮定する．D 2 (Km,n ) は n = 1のとき 12 m(m + 1) 個の点からなる集合なので，閉曲面とはならない．従って n ≥ 2 としてよい．
D 2 (Km,n ) を構成する各セル数を数えると，0 セルの数は (m + n)(m + n − 1) 個，1 セルの数は 2mn(m + n − 2) 個，2 セルの数は mn(m − 1)(n − 1) 個である．
これより D 2 (Km,n ) のオイラー数はX (D 2 (Km,n )) = mn(m − 1)(n − 1) − 2mn(m + n − 2) + mn(mn − 1)
= mn(mn − n − m + 1 − 2m − 2n + 4 + mn − 1)
= mn(2mn − 3m − 3n + 4)
24

となる．
補題より，D 2 (Km,n ) が閉曲面となるのは 2 × mn(m − 1)(n − 1) = 2mn(m + n − 2) が成り立つときである．
これを解くと，n ≥ 2 より (m, n) = (3, 3) が得られる．
次に N ≥ 3 で，D N (Kn ) や D N (Km,n ) が閉曲面となるときの N と n，N と m, n の関係を調べる．
命題 4. N ≥ 3 とする．D N (Kn ) が閉曲面ならば N = n − 2 である．
証明. n = 1, 2 のときは明らかに閉曲面とはならない．従って，n ≥ 3 としてよい．
D N (Kn ) が閉曲面となるためには，その構成に少なくとも２セルをもたなければならな
い．つまり N 個のうち２個の動点はそれぞれ１セル上にある必要がある．まず１個の動点をおく１セルを選ぶ．そして Kn からその１セルとそれに隣接する１セルを取り除く．
この操作により，残ったグラフは Kn−2 ．同様に Kn−2 からもう１個の動点をおく１セルを選び，それとそれに隣接する１セルを取り除くと，残ったグラフは Kn−4 ．このグラフの０セル上における動点の数は，高々 n − 4 個である．
よって
N − 2 ≤ n − 4.
ただし，N < n − 2 のとき D N (Kn ) はその構成に３セルを含むので，閉曲面とはならない．
よって
N = n−2が成り立つ．
命題 5. N ≥ 3 とする．D N (Km,n ) が閉曲面ならば N = m + n − 2 である．
証明. m ≥ n としても一般性を失わないので，m ≥ n と仮定する．n = 1 のときは明らかに閉曲面とはならない．従って n ≥ 2 としてよい．
D N (Km,n ) が閉曲面となるためには，その構成に少なくとも２セルをもたなければならない．つまり N 個のうち２個の動点はそれぞれ１セル上にある必要がある．まず１個の動点をおく１セルを選ぶ．そして Km,n からその１セルとそれに隣接する１セルを取り除く．
この操作により，残ったグラフは Km−1,n−1 ．同様に Km−1,n−1 からもう１個の動点をおく１セルを選び，それとそれに隣接する１セルを取り除くと，残ったグラフは Km−2,n−2 ．
このグラフの０セル上における動点の数は，高々 (m − 2) + (n − 2) である．
よってN − 2 ≤ (m − 2) + (n − 2).
ただし，N < m + n − 2 のとき D N (Km,n ) はその構成に３セルを含むので，閉曲面とはならない．
よってN =m+n−2が成り立つ．

25

定理 1. D N (Kn ) が閉曲面であるための必要十分条件は⎧⎧⎨N = 2⎨N = 3または⎩n = 5⎩n = 5である．更に D 2 (K5 ) は種数 6 の閉曲面，D 3 (K5 ) は種数 16 の閉曲面に同相である.
証明. (ア) 十分条件について調べる．

(a) N = 1 のとき
D 1 (Kn ) = Kn で，構成に２セルをもたないので不適．
(b) N = 2 のとき
命題 2 より n = 5 のときのみとなる．
(c) N ≥ 3 のとき
今 D N (Kn ) を閉曲面と仮定しているので，N = n − 2 である．
D n−2 (Kn ) を構成する２セルの数は，

11× (n − 2)! = n!(n − 2)(n − 3).
n C2 × n−2 C2 ×28(1)D n−2 (Kn ) を構成する１セルの数は，1(n C2 × n−2 C1 ) × (n − 2)! = n!(n − 2).
2(2)(1) , (2) より
1
12 × n!(n − 2)(n − 3) = n!(n − 2).
82
これを解くと n = 5 となる．
つまりこのとき N = 5 − 2 = 3 が成り立つ．
(イ) 必要条件について調べる．
これは，例 5.1 と例 5.3 で確かめられた．
(ア) , (イ) より定理は証明された．

定理 2. D N (Km,n ) が閉曲面であるための必要十分条件は⎧⎧⎨N = 2⎨N = 4または
⎩m = n = 3⎩m = n = 3である．更に D 2 (K3,3 ) は種数 4 の閉曲面，D 4 (K3,3 ) は種数 37 の閉曲面に同相である.
証明. (ア) 十分条件について調べる．

26

(a) N = 1 のとき
D 1 (Km,n ) = Km,n で，構成に２セルをもたないので不適．
(b) N = 2 のとき
命題 3 より (m, n) = (3, 3) のときのみとなる．
(c) N ≥ 3 のとき
今 D N (Km,n ) を閉曲面と仮定しているので，N = m + n − 2 である．
D m+n−2 (Km,n ) を構成する２セルの数は，

11×(m+n−2)! = mn(m−1)(n−1)(m+n−2)!.
mn C1 × (m−1)(n−1) C1 ×22(3)D m+n−2 (Km,n ) を構成する１セルの数は，(mn C1 × m+n−2 C1 ) × (m + n − 2)! = mn(m + n − 2)(m + n − 2)!.
(3) , (4) より
12 × mn(m − 1)(n − 1)(m + n − 2)! = mn(m + n − 2)(m + n − 2)!.
2
これを解くと (m, n) = (3, 3) となる．
つまりこのとき N = 3 + 3 − 2 = 4 が成り立つ．

(イ) 必要条件について調べる．
これは，例 5.2 と例 5.4 で確かめられた．
(ア) , (イ) より定理は証明された．

27

(4)

参考文献
[1] A.Abrams and R.Ghrist ; FINDING TOPOLOGY IN A FACTORY : CONFIGURATION SPACES , preprint[2] R.J. ウィルソン , 西関隆夫・西関裕子 共訳 ; グラフ理論入門 , 原書第４版

28