ランデブー探索とは何？わかりやすく解説 Weblio辞書

ランデブー探索

概要

友好的な 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\} \,$