《ランデブー探索》のソースを表示

'''【らんでぶーたんさく (rendezvous search)】'''

　夫と妻がデパートではぐれてしまったときのためにあらかじめ打ち合わせておくことにした．呼び出しサービスもなく，また２人のうち少なくとも一方が携帯電話を持っていないとしたとき２人ができるだけ早く遭遇するためにはどうしたらよいか．また，ハイカーがはぐれたときの用心のために移動方法を記したハンドブックを作成したい．再会するまでに要する時間が平均的に小さくなるような方法を求めよ．[[ランデブー探索]](rendezvous search) とは友好的な２人以上の探索者が早く遭遇するための方策を考える探索問題である．古くから文献で指摘されてきたが，ランデブー探索の数理的研究が盛んになったのは１９９０年前後以降である．探索者の行動領域が離散であるか連続であるか，またそれが有界であるかどうか，探索者がとり得る行動（戦略），探索者が得る情報，探索者の数，探索者の初期位置についての設定，その他によって種々のモデルが検討され研究が続けられている．ランデブー探索では探索者をplayer
と呼ぶことが多いが，一般にはランデブー探索はゲームではないことに注意すべきである．探索者が事前にお互いの役割について相談していない状況（上記ハイカーの例）を，すべての探索者が同じ戦略を用いるとしてモデル化し，この場合を(player-)symmetric という．一方探索者ごとに異なる戦略を用いることができるモデル（上記夫妻の例）をasymmetric という．他の条件が同じである場合，symmetric モデルの方がasymmetric モデルより数理的解析が困難である．探索者が2 人であるようなasymmetric モデルにおいて，探索者の一方は初期位置に留まって動かないような戦略に限定すると，他方による静止目標物の探索問題となる．探索者同士が探索領域についてどの程度の知識を共有しているか，（例えば，時計回り，方位等）もランデブー探索の重要な要素である．最小の期待再会時間をランデブー値（rendezvous value）と呼ぶ．


'''[直線上のランデブー探索：asymmetric モデル]'''  2 人の探索者（探索者I，II）が数直線上に位置している．2 人は時刻<math>0\,</math> においてお互いの初期位置間の距離<math>d\,</math> の確率分布<math>F\,</math> を知っているが，自分が数直線上のどこにいるのかわからない．相手が自分のどちら側にいるのか，またどちら向きに進んでいるのかを知らない．それぞれが自分の最初の向きを前進だと考える．最初に進む向きの組み合わせは4 通りあり，それぞれが確率<math>1/4\,</math> で起こる，とする． 2人は速さ<math>1\,</math> で進むことができて，できるだけ早く遭遇することを望んでいる．2 人が同時刻に同じ点にいるとき出会うことができると仮定する．期待再会時間を最小にするには2 人は直線上をどのように動けばよいか．

　この問題において，それぞれの戦略は次の集合から選ばれる，とする．

<center>
<math>
L= \{ f:[0,\infty) \rightarrow (-\infty, \infty): ~ f(0)=0,~ |f(s) - f(t)| \leq |s - t| \} .\,
</math>
</center>

<math>f \in L \,</math>に対し，<math> f(t)\,</math>は時刻<math>t\,</math> において，初期位置に対する探索者の相対的な位置を表す関数である，ただし探索者の最初の向きを正とする．例えば，初期位置が<math>w\,</math> で最初の向きが左であって<math>f(t)=5\,</math> であったとする．探索者<math>t\,</math>の時刻での位置は<math>x-5\,</math> である．一方，最初の向きが右であって<math>f(t)=-5\,</math> であっても時刻<math>t\,</math> での位置はやはり<math>x-5\,</math> となる．一般に，初期位置が点<math>x\,</math> であり戦略<math>f\,</math> を選んだならば，時刻<math>t\,</math> での位置は確率<math>1/2\,</math> ずつで，<math>x \pm f(t)\,</math> となる． <math>L\,</math>の部分集合で，傾きが<math>\pm1\,</math>（離散点を除いて）となる<math>f\,</math> の全体は<math>L\,</math> 内でdense である．2 人の戦略をそれぞれ<math>f,g\,</math> とする．探索者I，II の初期位置をそれぞれ点<math>0\,</math> および<math>d\,</math> とする．2 人の最初の向きが，探索者I は右，探索者II は左である，つまり <math> {I \atop \rightarrow} {II \atop \leftarrow} \,</math>とすれば， <math>f(t)+g(t)=d\,</math>となる最小の時刻<math>t\,</math> で2 人は出会うことになる．同様に考えて，探索者I，II の初期位置がそれぞれ点<math>0\,</math> および<math>\pm d\,</math> のときの2 人の期待再会時間は

<center>
<math>
T(f,g)=  \int_{0}^{\infty} \frac{1}{4} \left[ \min \left\{ t: f(t)=d+g(t) \right\} + \min \left\{ t: f(t)=d- g(t) \right\} 
 + \min \left\{ t:f(t)= - d+g(t) \right\} + \min \left\{t:f(t)=-d -g(t) \right\} \right] d F(d)

\,</math>
</center>


となる．目的はasymmetric ランデブー値<math>R(F)\equiv \inf_{f,g\in L}T(f,g)\,</math> を求めること，またそれを与える戦略を見つけることである．確率分布<math>F\,</math> が有界で平均が<math>\lambda\,</math>，最大値が<math>D\,</math>，つまり<math>F(D)=1\,</math>であるとする．次のような戦略の組<math>(f^{*},g^{*})\,</math> を考える．<math>f^{*}\,</math> は初期位置から<math>D\,</math> だけ進み，その後折り返して<math>2D\,</math>だけ進む. <math>g^{*}\,</math>は <math>D/2\,</math>だけ進み，折り返して初期位置に戻る．次に任意の方向へ確率<math>1/2\,</math> で<math>D\,</math>だけ進み折り返して初期位置に戻る，というものである．すると<math>T(f^{*},g^{*})=(9D+4\lambda)/8\,</math>となりランデブー値<math>R(F)\,</math> の上界が得られる．特に，初期位置間の距離<math>d\,</math> が既知の場合は<math>d = D = \lambda\,</math> となり，ランデブー値は<math>13d/8\,</math> となる．このとき唯一の最適な戦略は上記<math>(f^{*},g^{*})\,</math> であることが知られている．


'''[直線上のランデブー探索：symmetric モデル]''' この場合は初期位置間の距離が既知であるような基本的なモデルであってもランデブー値の上界が得られているにすぎない．初期位置間の距離の分布<math>F\,</math> が有界であり最大値が<math>D\,</math> 平均が<math>\lambda\,</math> であるとする．2 人の探索者それぞれが速さ<math>1\,</math> で動き， <math>D/2\,</math> の整数倍の時刻のみに方向を変えるような戦略を次のように表現する．<math>\eta_1 F \eta_2 B \eta_3 F \eta_4 B \ldots\,</math>. これの意味は，まず <math>\eta_1 D/2\,</math>の間前進，<math>\eta_2 D/2\,</math> 後進，...．このような表現の戦略あるいはそれの組み合わせでしかもできるだけ期待再会時間を小さくするような特定の戦略を考えることが研究の現状である．例えば，<math>d = D = \lambda=2\,</math>とする． 2人が<math>1F2B\,</math>，つまり，まず確率<math>1/2\,</math> で進む向きを決め，その向きに<math>1 \times D/2 =1\,</math> だけ進み<math>2\,</math> だけ戻る．再び確率<math>1/2\,</math>  で向きを決め，同じ行動を繰り返す．この戦略での期待再会時間は<math>5\,</math> になる．より複雑な戦略を考えることにより， <math>F\,</math>の最大値が<math>D\,</math>，平均が<math>\lambda\,</math> のとき現在得られている最小の上界は，<math>1.701D+0.5\lambda\,</math>である．特に，初期位置間の距離<math>d\,</math> が既知の場合は<math>d = D = \lambda\,</math> となり，ランデブー値の上界<math>2.201d\,</math> が得られる．


'''[ランデブー探索に同値な探索問題] '''　[直線上のランデブー探索：asymmetric モデル] において，<math>F\,</math> が有限の平均をもつと仮定する． 2人の戦略<math>f,g\,</math> に対し，<math>x,y\,</math>を

<center>
<math>
x(t)=f(t)+g(t),  ~~ y(t)=-f(t)+g(t), ~~  |x^{'}(t)| + |y^{'}(t)| \le 2
\,
</math>
</center>

と定義する．例えば2 人の最初の向きが<math> {I \atop \rightarrow} {II \atop \leftarrow} </math> の場合，時刻<math>s\,</math> までに2 人が出会えるのは<math>d \le \max_{0 \le t \le s} \left[ f(t)+g(t) \right] \,</math> となる場合で，その確率は，<math>F( \max_{0 \le t \le s} \left[f(t)+g(t) \right])\,</math>, つまり<math>F(\max_{0 \le t \le s}x(t))\,</math>である．他の3 つの場合も同様に考えて，結局2 人が時刻<math>s\,</math> までに出会う確率は

<center>
<math>
P_{f,g}(s)= \frac{1}{4} \left\{ F(\max_{0 \leq t \leq s} x(t))+F( \max_{0 \leq t \leq s} -x(t))+ F(\max_{0 \leq t \leq s} y(t))+F(\max_{0 \leq t \leq s} -y(t)) \right\}
\,
</math>
</center>

となる．一方，直線上のランデブー探索が次に述べる探索問題において戦略を上述の<math>x,y\,</math> としたものに同値であることが知られている．

　
　1 つの静止目標物が2 本の数直線<math>l_I, l_{II}\,</math>, のうちのいずれかに存在する．存在確率は<math>F\,</math> で与えられる．探索者I,II の初期位置はそれぞれ数直線,<math>l_I, l_{II}\,</math> の原点である．2 人の探索者は，合計の速さが<math>2\,</math> であるようにして数直線上を移動しながら目標物を探索する．2 人のうちの1 人が目標物を発見するまでの期待時間が最小になるような行動を求めよ．このとき，2 人のうちのどちらかが時刻<math>s\,</math> までに目標を発見する確率が<math>P_{f,g}(s)</math> で与えられる．


'''[3 人以上のランデブー探索]'''   (i) 長さが<math>n\,</math> である円周上に等距離<math>1\,</math> だけ離れて<math>n\,</math> 人の探索者がいる．円周上には位置を特定できる目印はなく，また<math>n\,</math> 人のすべてにとって，どちらが時計回りかの共通の認識がない．<math>n\,</math> 人が円周上で一同に会すには探索者はどのように動けばよいか．この問題のランデブー値は漸近的に<math>n/2\,</math> であることが知られている．(ii)  <math>n\,</math>人が数直線上の連続する整数点上に位置している．それぞれが確率<math>1/2\,</math> で自分の向きを決める．すべてが一同に会すことができることを確実にするのに必要な時間を最小にするにはどのように動けばよいか．この最小時間を<math>\min\max\,</math> ランデブー値という．これは漸近的に<math>n/2\,</math> に近づくこと，さらに<math>n=3\,</math> の場合は <math>\min\max\,</math>ランデブー値が<math>3.5\,</math> であることが知られている．


　ここで紹介したモデル以外にも，例えば探索領域が2 次元以上の場合のランデブー探索，ネットワーク（あるいはグラフ）上でのランデブー探索等について論文が散見されるが，多くの問題が残されており今後の研究が待たれる状況である．ここで紹介した分析を記述した原論文についての情報も含めて，詳しくは参考文献[1] を参照されたい．

---
'''参考文献'''
[1] S. Alpern and S. Gal, ''The Theory of Search Games and Rendezvous'', Kluwer’s International Series, 2003.

[[category:探索理論|らんでぶーたんさく]]