I. PENDAHULUAN 1.1 Latar Belakang
Rendezvous search adalah suatu kwrdinasi tanpa komunikasi dau mernpakan proses paralef. Masalah rendezvous search (Alpern, 1995) menjelaskan bagaimana para pemain yang ditempatkan secara acak dalam suatn daerah pencarian diketahui dapat bergerak dengan kecepatan maksimal 1 untuk saling bertemu dalam waktn harapan terkecil. Pada awal peuempatan dalam permainan, tiap pemain tahu posisinya masing-masing tapi tidak tahu posisi pemain lainnya. Masalah rendezvous search pertama kali secara formal didefinisikan oleh Alpern (1995). Untuk menyederhanakan masalah, apilih kasus pada garis lurns sebagai daerah pencarian. Cerita yang melatarbelakangi pennasalahan ini adalah sebagai berikut: Misalkan ada dua orang penejnn ingin. bertemu yang ditejunkan pada snatu lapangan luas dan terdapat lintasan kereta api yang melintasi daerah tersebut. Mereka telah menyepakati sebelumnya unhk bertemu, tetapi
belum tahu di mana letak yang sebenarnya pada lintasau kereta api tersebut. Masalahnya adalah bagaimana mereka hams bertindak agar memperoleh waktu harapan ya* minimum Cerita di atas tersebut kemudian dikembangkan untnk pemaiu yang terdiri atas tiga orang. Nilai randew dapat diperoleh dalam dua bentuk, yaitn benhlk simetrik dan b e n a asimetrik. Bentuk simetrik membatasi pemain untuk mengguuakan strategi pencarian yang Sam% sedangkan bentuk asimetrik memungkinkan pemain untuk memilih strategi yang berbeda. Pada tnlisan ini yang akan dipelajari adalah rendezvous search tiga pemain dengan bentuk asimetrik. 1.2 Tujnan
Tujuan penulisan karya ilmiah ini adalah: 1. mempelajari jaminan pertemuan antara tiga orang pemain, 2. mempelajari koudisi yang dibutuhkan untnk strategi optimal, dan 3. menentukan nilai randew asimetrik untuk tiga orang pemain.
II. MODEL FORMAL 2.1 Notasi dan Asnmsi
Permainan dimulai dengan menempatkan tiga orang pemain secara acak pada suatu daerah. Untnk menyederhanakan masalah, dipilih garis lurns sebagai daerah pencarian, setiap pemain tidak mengetahui posisi dari pemain lainnya, tetapijarak di antara 2 pemain terdekat diketahui, yaitn 1 satnan jarak. Mereka bergerak dengan kecepatan paling besar 1 satuan jaraklsatnan waktu untuk saling bertemu. Pertemuan yang tejadi lebih dahulu antara dua orang pemain akan mengakhiri permainan. Diasumsikan bahwa permainan ini asimetrik, artinya masing-masing pemain mengetahui sebelumnya strategi yang akan digunakan oleh pemain laiunya. Rangkaian permainan digambarkan dalam bidang Cartesius, dengan sumbn horizontal menyatakan waktn dan sumbu vertikal menyatakan posisi pemain pada garis lurns. Definisi 1 Orientasi awal w pada pemain adalah rangkap-3 (01,02.03) dengan
={
+
jika pemain i bergerak naik pa& awal permainan - jika pemain i bergerak t n m pada awal permainan
Definisi 2 Posisi awal p pada pemain adalah rangkap3 @I, p2, p3) dengan P adalah permumi himpunan {0, 1,2) danpl menyatakan posisi awal pemain i, i=l, 2,3. Definisi 3 Suatu permainan dengan tiga pemain dikatakan berakhirjika: a) pemain yang ditempatkan pada 0 bertemu dengan pemain yang ditempatkan pada 1, atau b) pemain yang ditempatkan pada 2 bertemu dengan pemain yang ditempatkan pada 1, atau c) ketiga pemain bertemu pada waMu yang Sam%
sedangkan pemain yang ditempatkan pada 0 bertemu dengan pemain yang ditempatkan pada 2 tidak dibahas karena sebelum kedua pemain tersebut bertemu, maka terlebih dahnlu saiah satu di antara mereka akan beitemu dengan pemain yang ditempatkan pada 1 sehingga menjadi bentuk a) atau b) pada pemyataan di atas. Misalkan himpunan C mempakan kumpulan semua anggota c = @, w ) yang menyatakan posisi dan arah saat permainan dimnlai. Perhatilotnbahwa suatu permainan yang dimnlai dengan @,,pz,p3, -,oz,w~)"berakl~irsama" dengan permainan yang dimulai dengan ( 2 - p ~ ,2-pz, 2-p3, +, -w2,-w3 ). Untuk menjelaskanhal ini, misalkandiambil contoh pl=O, ~ = lp3=2, , dengan arahpemain II danpemain 111 keduanya +. Contoh ini menghasilkan : ( P I .PZ,~ 3 . - . ma, a s ) = (0,1,2,-,+,+). Ddam bidang Cartesius dapat dilihat pada Gambar 1 . ( Z-PI, 2-pz, 2-p3, + ,*z, -m3 )= (2,1,0,+,-,-I. Dalam bidang Cartesius dapat dilihat pada Gambar 2.
Gatnbar 1. Posisi dan arah pemain untuk (0,1,2,-,+,+).
,l
0
III Gambar 2. Posisi dan arah pemain untuk (2,1,0,+,-,-).
Tanpa memperlliitikan a r d ~masing-masing pemain itu naik atau turun, dari kedua gambar tersebut terlihat bahwa pemain I1 dan pemain I11 sama-sama bergerak menjauhi pemain I, sehingga dapat dikatakan bahwa kedua permainan berakhir sama. Hal yang sama juga berlaku jika masingmasing nilai pl, n, p3, atau 02 dan 03 diubah. Ini berarti bal~waw, selalu dapat dibuat +. Jadi nntuk kasus ini diasumsikan bahwa wl = + sehingga himpunan C hanya mempunyai 24 anggota (=3!x2'). Semua anggota himpnnan C disebut kasus clan diperlihatkan pada Tabel 1.
pemain III), maka permainan akan berakhir jika pemain I dan I1 bertemu, ataujika pemain I1 dan 111 bertemu. Misalkan posisi awal pemain diberikan sebagai c, yang diperlihatkanpada bidang Cartesius dalam Gambar 3.
Misalkan (a,, a*) menyatakan pasangan tak teNNt dari pemain-pemain yang ditempatkan setelah pemain lain ditempatkan pada am1 permaiuan. Misalkan b, =-(al,a2,dl, d2), dengan di menyatakan arah relatif pemain a, terhadap pemain a,. (i#j), yaitu, to jika pemain a, bergerak kearah
pem$n a, pada awal permainan mujika @main a, bergerak menjauhi
pemain a) pada awal permainan dengan i, j = 1, 2 dan i # j. Misalkan B={b,l i=1, ...,12). Semua anggota B disebut tipe clan B mempunyai 12 anggota yang diperlihatkan pada Tabel 2.
Gambar 3. Permainan yang dimulai dengan kasus c,. Dalam Gamba~3 terlihat b a h m pemain I bergerak menuju pemain I1 sedangkan pemain II bergerak menjauhi pemain I dan pemain 11 bergerak menuju pemain 111 sedangkan pemain 111 bergerak menjauhi pemain 11, sehingga kasus cl &pat dihubungkan menjadi dua tipe, yaitu b2= (I, II, to, mu) dan blo = (II, III, to, mu). Suatu pertemuan antara dua pemain Cyang terjadi lebih dahulu) akan mengakhiri permainan.
Misalkan pemetaan 4 menyaantara kasus dan tipe, yaitu:
hubungan
4 : C-tBxB, Kc) = (b,, bJ),V c e C , i <j , maka himpnnan image dari 4 &pat dilihat dalam Tabel 3. 2 3 Ruang Strategi 2.2 Hubungau Antara Kasus dan Tipe
Sebelumnya telah diuraikan bahwa permainan berakhir jika dua pemain yang letaknya berdekatan pada awal permainan sudah bertemu. Misalkan suatu permainan dimulai dengan kasus cl ( pernain 11 terletak antara pemain I dan
.
Dalam pembahasan permainan ini, strategi adalah fungsi yang menyatakan arah dan jar& pergerakan pemain. Strategiyang digunakan hanya yang terdapat pada mang strategi yang didefinisikan sebagai berikut : P=~:w+ ~ ~ , P f o ~ = o . ~ P f t l ) - P f ~ 2-'21) )('~I
Contoh suatu strategi adalah: f(f) = t, t
E
[0,1/2].
Tabel 3. Himpunan image 4
kontinn b a d clan P adalah iumpunan kompak. (Alpern, 1995), maka nilai pa& ( 2 ) selalu dijamin ada (Goldberg, 1976). Misalkan p(fg,h) menyatakan waktu saat pemain dalam tipe b saling bertemu (6 E B). Untuk semua c E C, didefinisikan: T a g & = min plb~t;g,h) (3) bsrplc)
Diberikan tiga strategi Cfg,h) sembarang, dengan delapan garis lintasan berikut ini:
Definisi 4 Misalkan pemain I memilih strategi f; pemain I1 memilih srategi g dan pemain EI memilih strategi h, denganf; g, h E P. Misalkan TXf;g, h) menyatakan peamuan ~ a n gbetpadanan dengan kasus c, dengan c E C. Maka waktu pertemuan harapan ? a h ) dinyatakan sebagai :
dengan R:, adalah nilai randevu, yaihl waMu harapan pertemuan asimetrik dengan tiga pemain di mana dua pemain yang bertemu lebih dahulu akan mengakhiri permainan. Karena T" semi
Garis-garis di atas menyatakan lintasan masing-masing pemain. Lintasan Ll,,(f) menyatakan garis untuk pemain dengan strategif; lintasan &(t) menyatakan garis untuk pemain dengan strategi g, sedangkan lintasan LO,&) dan L3,,(f) menyatakan garis untuk pemain dengan strategi h. Untuk semua b E B, p(L g, h) &pat ditentukan dengan menggunakan garis Lk, dan L*+,,pdalam (4), sehingga p ~ ; g , h=) min { t : Lkdt) = L&l,p(f)}
(5)
dengan P = + I , k=0,1,2 dan k menyatakan letak pemain. Garis-garis untuk menentukan PV;g, h) dengan b E B diberikan dalam Tabel 4.
Tabel 4. Garis-garis untuk menentnkan mkh)
pemain I turun atau p =-I. Akhirnya diperoleh (k, a)=(0+1) dan (lctl,n = ( 1 ~ 1 )Demikianpula . dalam menentnkan garis-garis untuk bs, b? dan b, dilakukan dengan cara seperti untnk b5. 3) Untuk tipe bs, bla, b11 dan bl; Untuk tipe bg, ~ I O ,b11 dan b12 , garis yang diambil pemain 111 adalah L3,,karena garis tersebut letaknya lebih dekat terhadap garis strategi pemain 11 (L2,0)dibandingkan dengan Lo,,. Ilustrasi Diberikan contoh kasus berikut ini. Misalkan:
Penjelasan Tabel 4 1) Untnk tipe bl, b2, b3 dan b4 Contoh: Untuk tipe bl (I, 11, to, to), pemain I dan pemain I1 saling mendekat. Garis yang diambil adalah garis yang memuat strategi pemain I (f) dan pemain 11 (g), yaitn LI,, dan L%,.(jadi k 1 ) Letak pemain I berada di bawah pemain I1 (pemain I di 1 dan pemain I1 di 2), sehingga agar keduanya saling mendekat, maka pemain I naik atau a =+l dan pemain II tnrun atau p -1. Akhirnya diperoleh (k, a)=(l+l) dan (lctl, p) = (2;l). Demikian pula dalam menentukan garis-garis untuk b2, b3dan b4dilakukan dengan cara seperti untuk bl. 2) Untuk tipe b,, bs, b, dan b8 Contoh: Untuk tipe b5 (I, 111, to, to), pemain I clan pemain 111 saling mendekat, garis yang diambil adalah garis yang memuat strategi pemain I (f) dan pemain 111 (h). Garis yang memuat strategi pemain 111 ada dua yaitn Loaodan L,,,. Tetapi garis yang terdekat dengan garis untuk stmtegi pemain I (LIJ adalah Lo,, sehingga pada tipe b, ini, garis yang diambil pemain III adalah Lq, Dengan demikian , pemain 111 terletak di bawah pemain I (pemain 111 pada 0 sedaugkan pemain I pada 1) sehingga agar saling mendekat, pemain III naik atau a =+1 dan
dengan f,g, h berturut-turut merupakan strategi pemain I, pemain 11, dan pemain 111. B e r k k a n Tabel 4, untuk bl diambil garis L1.1 dan LZ-, Apabila strategi-strategi pemain I dan pemain U disubstitusikan ke (4) diperoleh : L1,1= f(t) +1 (ti-1, t€[O,l]
Jika digambarkan pa& bidang Cartesius dapat dilihat pada Gambar 4, yaitu:
Tabel 6. Nilai-nilai T, @,g,h) untuk ceC
Gambar 4. Garis 4-1 dan LZ.-, untuk bl Dari Gambar 4 diperoleh bahwa titik potong kedua garis peitama kali tejadi pada t-112 sehingga diperoleh Tbl @,g,h)=112. Untuk bZ,b3,b4,...,b12 bidang Cartesiusnya diperlihatkan pada Lampiran 1. ~ilai-nilaiTb@, g. F) untuk semua b e B dituliskan dalam Tabel 5. Tabel 5. Nilai-nilai T * @, b € B.
c,h) untuk 21
Dengan demikian diperoleh
Dengan menggunakan persamaan (3), Tabel 3, dan Tabel 5, maka &pat diperoleh nilai T, 6 , g,h) untuk semua c E C, yang dituliskan dalam Tabel 6.
47
T, @,g,h)= 2 f=1
Lema 1 47
Nilai randevu R12 memenuhi R12 5 48
Bukti KarenaR& = min
f .g.heP
T"( f , g , h )
Karena (dari persamaan
f,g,l;~P, maka R:, sT(f,g,h). 47 48
.
Terbukti bahwa R,4, 5 -
2), makaR& 2 T"(f,g.h), V f , g , h E P.
III. KELAS STRATEGI YANG BEREWGGA Misalkan pemain I memilih strategg pemain I1 memilih strategig, dan pemain In memilih strategi E Dengan menggunakan h, dengan I; persamaan (4), maka misalkan Ll,,(,, dinamakan lintasan agen-agen pemain I; L2,,0, dinamakan lintasan agen-agen pemain 11; Lo,,fl dan L3,,(,, dinamakan lintasan agen-agen pemain In; dengan
g,
>.
4,
tE[~,;l
a=+l.
Lema 2 Misalkan x g , h ) adalah strategi-strategi pemain. Misalkanti < t 2 < ... < tk(k58)adalah waktu pertemuan pemain i dengan beberapa agen pemain terdekat untuk pertama kalinya. Maka strategi pemain i &pat d i m m i sehingga untuk setiap j, agen pemain i dapat bergerak dengan kecepatan 1 menuju agen pemain terdekat (dengan waktu pertemuan t = $+I ) dalam selang waktu ( 9 . $1) dengan menggrinakan strategi baru tersebut untuk semua j E {O, 1, ...,k-1) (to = O), dan waktu pertemuan harapan paling besar adalah T"(f,g, h).
Misalkan diambil cl, yaitu (0,1,2,+,+,+) dengan a=1, jika digambarkan pada bidang Cartesius untuk L1,, clan L2,1 &pat dilihat pada Gambar 5 berikut ini:
Bukti (Lihat Lampiran 4) llustrasi Lema 2 Misalkan strategi pemain I dengan kecepatan kurang dari 1 akan bertemu dengan pemain terdekatnya pada waktu (misalkan) t4 . Maka strategi pemain I ini dapat d i m m i dengan kecepatan 1 sehingga waktu pertemuan dengan pemain terdekatnya bisa kurang dari t4. Sebagai contoh misalkan g g , h ) adalah strategi-strategi pemain denganf adalah strategi pemain I. Strategi a w l :
Gambar 5. Garis
dan LZ,I untuk c, dengan
a=I. Dad Garnbar 5 terlihat bahm ti* p p t o n g a n 2512 sehinga waktu pertemnannya >512. Jika saategi pemain I, yaitu I; diubah &ngan keceptm 1, sehinga diperoleh strategi baru ,yaitu :
