ランデブー探索

出典: ORWiki

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

概要

友好的な2人以上の探索者が早く遭遇するための方策を 考える探索問題である． 探索者の行動領域が離散であるか連続であるか， またそれが有界であるかどうか，探索者がとり得る行動， 探索者が得る情報，探索者の数，探 索者の初期位置についての設定，探索基準等によって種々のモデルが考えられる．

詳説

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


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

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

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

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

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) \,


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


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


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

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

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

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\} \,

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

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


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


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

参考文献

[1] S. Alpern and S. Gal, The Theory of Search Games and Rendezvous, Kluwer’s International Series, 2003.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%83%A9%E3%83%B3%E3%83%87%E3%83%96%E3%83%BC%E6%8E%A2%E7%B4%A2" より作成