6
II. TINJAUAN PUSTAKA 2.1. Autonomous Steering Behaviour Simulasi dengan menggunakan agent memiliki hubungan erat dengan Steering Behaviour. Dimana behaviour ini menentukan bagaimana para agent itu bergerak. Paper Reynolds membahas secara global macam-macam Steering Behaviour dan membuat simulasi untuk mempermudah memahaminya (Reynolds, 1999). Lebih dalam lagi tentang Steering Behaviour, Reese dan Stout meneliti tentang faktor-faktor yang menentukan pathfinding pada dinamika permainan game (Reese & Stout, 1999).Jared Go at al juga meneliti mengenai pergerakan sekumpulan kendaraan yang dianimasikan olehnya untuk mencegah agar tidak terjadi tabrakan antar kendaraan dengan kecepatan tinggi (Go, Vu, & Kuffner, 2004)dimana dia juga terinspirasi dari paper Reynolds yang salah satu simulasinya adalah BOIDS. Serta Shao & Terzopoulos yang membahas mengenai autonomous pedestriandimana dia berusaha mensimulasikan pergerakan dari pejalan kaki yang kompleks di lingkungan urban (Shao & Terzopoulos, 2007). Ketiganya membahas tentang bagaimana menggerakkan, mencegah tabrakan, dan mencari jalur pada autonomous charactersdimana kesemuanya akan dipakai untuk melakukan simulasi yang lebih kompleks, yaitu sepakbola. Browning & Tryzelaar melakukan penelitian untuk membuat simulasi Ubersim untuk mensimulasikan permainan sepakbola pada robot (Browning & Tryzelaar, 2000). Yang menjadi hal menarik, simulasi-simulasi sepakbola tersebut dijadikan ajang pertandingan internasional pada ROBOCUPdimana seperti yang dijelaskan pada paper Mayer at al yang membahas pembuatan 3D2Real, program simulasi
7
permainan sepakbola dalam 3D yang sedang dalam pengembangan, agar bisa diterapkan pada robot (Mayer, Boedecker, Guerra, Obst, & Asada, 2006). Boedecker at al menjelaskan dalam papernya bagaimana simulasi dan robot bisa saling mengambil keuntungan (Boedecker, Mayer, Ogino, Guerra, Kikuchi, & Asada, 2006). Hal ini menjadikan simulasi juga tidak kalah pentingnya dalam menerapkannya pada robot di dunia nyata.
2.2. RoboCup RoboCup™ (Robot World Cup Intitative) adalah research dan insiatif edukasi internasional. Ini merupakan upaya untuk mendorong AI dan penelitian intelligent robot dengan memberikan masalah standar dimana dapat diintegrasikan dengan teknologi untuk penerapannyadan dapat digunakan untuk pendidikan berorientasi project. Untuk tujuan ini, RoboCup memilih untuk menggunakan permainan sepakbola sebagai domain utama dan mengorganisasi RoboCup (yang sebelumnya dinamakan “The Robot World Cup Soccer Games dan Conferences”, sekarang dinamakan “RoboCup World Championship and Conference”). Agar para tim robot dapat melakukan soccer game secara baik, beberapa macam teknologi harus dimasukkan termasuk: design principles of autonomous agnets, multi-agent colaboration, strategy acquisition, real –time reasoning, robotics, dan sensorfusion. RoboCup juga menjadi tugas para tim untuk melakukan banyak gerakan cepat dalam dynamic environment. RoboCup juga menawarkan platform software untuk melakukan researchnya pada aspek software RoboCup.
8
Sementara soccer game digunakan sebagai masalah standar, kompetisinya itu sendiri hanyalah sebagian dari RoboCup. Aktivitas sekarang dari RoboCup terdiri dari: •
Technical Conferences
•
RoboCup International Competitions and Conferences
•
RoboCup Challenge Programs
•
Education Programs
•
Infrastructure Development Namun, RoboCup World Championship and Conferences menjadi pilar
utama dari aktivitas ini dimana para peneliti dapat berkumpul bersama dan mengevaluasi kemajuan mereka. RoboCup memiliki empat domain utama (The Robocup Federation, 2010):
• • • • •
RoboCupSoccer Simulation League -2D, 3D, 3D Development, Mixed Reality Small Size Robot League Middle Size Robot League Four-Legged Robot League (-2007) > Standard Platform (2008- ) Humanoid League (from 2002) - Kid-size, Teen-size
Exhibitions • RoboCup Commentator Exhibition RoboCupRescue • Rescue Simulation League • Rescue Robot League • • •
RoboCupJunior Soccer Challenge Dance Challenge Rescue Challenge
9
Seperti kita bisa lihat meriahnya RoboCup yang menjadi ajang para peneliti untuk saling berbagi ilmu.
Gambar 2. Diagram Partisipasi (Pagello, et al., 2003) Bisa dilihat dari diagram diatas ini bahwa peminatan di bidang simulasi sangatlah antusias dari tahun ke tahun. Peneliti dari berbagai penjuru dunia mengadu kemampuanya membuat algoritma untuk menciptakan soccer agent mereka yang pintar. Dari hasil tahun 2003, terdapat 46 team yang berpartisipasi dalam turnamen ini dan kita bisa melihat pemenang dari turnamen ini (Pagello, et al., 2003).
10
Gambar 3. Hasil turnamen (Pagello, et al., 2003)
2.3. Pembagian Level Skills Pemilihan keputusan dalam permainan sepakbola adalah masalah global yang sering kali dibahas dalam simulasi sepakbola, seperti pada jurnal Salmani at al (Salmani, Naghibzadeh, Seifi, & Taherinia, 2005) yang membahas tentang pengambilan keputusan dalam dua tahap (two phases) menunjukkan lebih efektif. Beberapa jurnal pun membagi action-action tersebut menjadi struktur berbasis layered agent. Seperti Peter Stone (Stone, 1998) yang memperkenalkan Layered Reinforcement Learning juga Kok dan Boer (Kok & Boer, 2002) yang mendeskripsikan urutan struktur Layered Agent seperti sebagai berikut: •
Atomic actions. Ini merupakan layer dasar dimana player mengirimkan commands ke server, seperti turn or dash.
•
Low-level skills seperti mencari bola
•
Intermediate-level skills seperti bergerak ke posisi terbaik
•
High-level skills seperti mencegat bola
11
Pada High-level skills, para peneliti banyak menggunakan Reinforcement Learningdimana berpusat pada membuat player yang agresif dan membuatnya mencegat dan merebut bola secara efektif. Thomas dan Martin melakukan penelitian pada proses Reinforcement Learningnya (Gabel & Riedmiller, Learning a Partial Behavior for a Competitive Robotic Soccer Agent, 2005) dan meneruskan hasil konkrit pada prosidingnya, yaitu tim BrainStormers yang berhasil masuk tim tiga besar pada World Champing RoboCup 2005 di Osaka (Riedmiller & Gabel, 2007). Lalu di tahun 2008, tim yang sama dengan ketambahan Trost, (Gabel, Riedmiller, & Trost, A Case Study on Improving Defense Behavior in Soccer Simulation 2D: The NeuroHassle Approach, 2008) melakukan case study yang menerapkan Reinforcement Learning yang lebih kearah hasil, yang dinamakannya pendekatan Neuro Hassle, karena nilai fungsinya berbasis neural-net. Sedangkan pada Intermediate-level, ada beberapa metode yang dipakai untuk menentukan posisi. Pada pertandingan FC Portugal melawan UVA Trilearn (Kok & Boer, 2002), disitu soccer agent melihat dan menghitung posisi yang diinginkan dengan mengambil posisi bola sekarang atau yang diprediksi terhadap posisi gawang. Setiap player menentukan tujuannya dengan menjumlahkan berat dari kedua poin tersebut. Dalam beberapa kasus, posisi dari pemain lawan juga diperhitungkan. Pendekatan lainnya, diterapkan pada tim robot CM-United (Stone, Riley, & Veloso, The CMUnited-99 Champion Simulator Team, 1999), membagi lapangan menjadi kotak-kotak kecil dan setiap kotak tersebut dievaluasi terhadap fungsi-fungsi tertentu. Pendekatan ini menggunakan evaluasi multicriteria yang mirip dengan metode simple weighting untuk masalah optimisasi
12
multicriteria. Metode yang terbaru dibahas saat ini adalah, Multi Criteria Decision Analysis untuk mengumpulkan Pareto Set dan didapatkan hasil optimalnya yaitu Pareto Optimal. Yang telah diterapkan dalam Offense pada RoboCup 2008(Kyrylov & Serguei, Pareto-Optimal Offensive Player Positioning in Simulated Soccer, 2008)dan Defense (Kyrylov & Hou, 2009)pada RoboCup 2009.
2.4. Tentang Sepakbola Sepak bola adalah permainanbola yang sangat populer dimainkan oleh dua tim, yang masing-masing beranggotakan sebelas orang. Sepakbola sudah dikenal sejak zaman sebelum masehi dulu. Orang-orang Mesir telah memainkan sejenis olahraga ini hanya saja dengan menggunakan buntalan kain linen. Di Yunani kuno juga ada permainan yang disebut Episcuro. Permainan ini menggunakan bola. Bukti adanya permainan ada di relief-relief dinding musium yang menggambarkan anak sedang membawa bola dan memainkannya dengan pahanya. Cina juga mencatat sejarah yang panjang tentang permainan bola ini. Pada zaman dinasti Chin,banyak orang yang memainkan permainan yang menggunakan bola yang disebut tsu chu. Jepang juga mencatat sejarah tentang sepakbola,pada abad ke delapan orang-orang Jepang sudah memainkan permainan yang disebut Kemari. Tentang sepakbola pada abad pertengahan ada sebuah cerita tentang sebuah desa yang memainkan sepakbola dengan menggunakan tengkorak sebagai bolanya. Para penduduk secara bergantian menendang bola dari satu orang ke orang lain hingga akhirnya bola tersebut sampai ke desa lain.(AnneAhira.com Content Team)
13
2.4.1. Aturan Sepakbola Sepakbola dimainkan dalam sebuah lapangan oleh sebelas pemain. Permainan biasanya dilakukan dalam waktu 2 X 45 menitdengan jeda istirahat lima belas menit yang dilakukan oleh para pemainnya. Kalau dalam waktu 2 X 45 menit masih seri maka akan ada perpanjangan waktu selama 2 X 15 menit. Setelah perpanjangan waktu masih terjadi draw maka akan diadakan adu penalti. Pemimpin pertandingan dalam sepakbola adalah wasit. Biasanya dia dibantu oleh dua orang hakim garis dan dua orang wasit cadangan yang bertugas ketika terjadi pergantian pemain.Ukuran lapangan sepakbola adalah 91,4 m dan 54,8 m dengan ukuran gawang 7,32 x 2, 44 meter. (AnneAhira.com Content Team)
14
Gambar 4. Lapangan Sepakbola (Michael & Alexi) Ada beberapa kondisi khusus dalam sepakbola yang umum terjadi, yaitu (Borden, 2009): •
Kickoff: Pada permulaan permainan dan setelah gol, tim melakukan kickoff dari tengan untuk memulai permainan.
15
•
Penalty Kick: Ketika pemain melakukan pelanggaran di area penaltinya sendiri, tim yang lawan mendapatkan tendangan penalti. Ini adalah tendangan berhadapan langsung dengan kiper yang berjarak 12 yard.
•
Throw-Ins: Jika bolakeluardaribatas garis sampingmakalemparan bebas ke dalamyang diberikan kepadatimyang terakhir tidakmenyentuhnya. Jika bolakeluar
dari
batas
garis
belakang,
tendangangoldiberikanjikatimpenyerangmenyentuhnyaterakhirdantendang ansudutdiberikanapabilatim bertahan yang menyentuhnya terakhir. •
Goal Kick: Ketikatimpenyerangmenendangbolakeluar dari garis gawang, tim
yang
bertahandiberikangoal
kick.
Boladapat
ditempatkan
di
manapundi dalamarea gawangdansetiappemain(termasuk kiper) dapat melakukantendangan. •
Corner
Kick:
Jikabolakeluar
melewatigarisgawangdanterakhirtersentuholehpemainditimbertahan, tendangansudutdiberikankepadatimpenyerang. Boladitempatkandisudutlingkarandisampingarea keluardanseperti
halnyatendangan
bebas,
gawangdimanabolaitu pemain
bertahanharus
berdirisetidaknya10meterdaribola. •
Offside: Pemain berada pada posisi offside jika, pada saat rekan satu tim memainkan bola, dia berada dekat dengan gawang daripada bola dan dua pemain
lawan.
Jika
pemain
melakukan
offside,
pemain
lawan
mendapatkan tendangan bebas dari tempat dimana offside tersebut terjadi. 2.4.2. Posisi Pemain Sepakbola
16
Setiap tim sepakbola memiliki 11 pemain yang terdiri dari 1 kiper dan 10 pemain. Tujuan dari permainan sepakbola adalah untuk memasukkan bola ke gawang lawan. Tim yang menang adalah tim yang paling banyak mencetak gol. Berikut ini dijabarkan peran setiap posisi (Michael & Alexi): •
Kiper: Hanya kiperyang diperbolehkan untuk menggunakan tangannya, selama dalam area18x44 yard yang disebut area penalti. Jika seorang penjaga gawang memegang bola di luar kotak dia akan mendapat kartu merah dan tim menyerang diberi tendangan bebas dari tempat itu.
•
Pemain Belakang (back): Mereka bermain di depan kiper dan tugas utama mereka adalah untuk menghentikan serangan lawan. Tugas mereka dan tanggung jawab dapat bervariasi dari jangkauan zona pertahanan mereka di mana mereka membela daerah tertentu. Pemain sayap belakang yang kiri dan kanan, umumnya jarang bergerak dari sisi mereka di lapangan, dan pemain belakang tengah bermain di tengah lapangan dan biasanya menjaga terhadap pencetak gol atau penyerang tengah.
•
Pemain Tengah (gelandang): Para pemain ini adalah penghubung antara pertahanan dan penyerang. Gelandang harus memiliki fisik yang baik karena diharapkan untuk menjalankan sebagian besar permainan. Mereka harus mampu menembus jauh di dalam wilayah musuh untuk menyerang dan membuat transisi ke pertahanan ketika lawan berhasil mengambil bola. Gelandang bisa mengkhususkan diri sebagai pemain gelandang menyerang atau bertahan.
•
Pemain Depan (penyerang): Tugas utama mereka adalah untuk mencetak gol sebanyak-banyaknya. Ada beberapa jenis penyerang, penyerang sayap
17
bermain di kedua sisi kiri atau kanan dan biasanya berlari dari atas ke bawah pada sisi lapangan. Mereka dapat membawa bola ke area penalti untuk menembak atau tetap di sisi dan mencoba untuk mengoper temannya di daerah tersebut. Penyerang tengah bermain di tengah lapangan, tapi mereka dibolehkan berkeliling jika ada ruang terbuka di sana. Penyerang tengah, juga dikenal sebagai striker, harus menjadi pemimpin tim dalam mencetak gol dan menjadi pemain paling berbahaya yang berada di depan. 2.4.3. Taktik Sepakbola Taktikadalahrencanajangkapendekuntukmencapaisuatu tujuandanmendukungstrategi.
Tujuannya
adalah
dapatmematahkanseranganlawanatauuntukmenembuspertahanan
agar
lawan.
Untuk
menyerang dan bertahan digunakan taktik yang berbeda. Dalam serangan, taktik yang biasa digunakanadalahsebagaiberikut: (Beim, 1977)(Vogelsinger, 1982) •
Space:
ruang
adalah
hal
yangpentingdalamserangan.
depanharusmemanfaatkanruangantaradandi
belakangpemain
Pemain belakang.
Jika seorang pemaintidak memilikiruangdiakemungkinan besartidak akandianggap
sebagaipengambil
potensialataumungkinkehilangankontrol Aspekkeduadariprinsipruang
operan bolaketika
yang mengoper.
kosongadalahmenjagaruangbebas
antarapemaindanteman satu timdengantujuanuntukdapatmenerimaoperan. •
Attack Depth and Support: penyerang yang sedang menyerang gawang lawan pasti akan dihadang oleh pemain belakang. Akan lebih mudah untuk pemain
belakang
memotong
bola
ketimbang
penyerang
mempertahankannya. Karena itu, pemain tengah harus membantu
18
penyerang dengan melakukan operan cepat dan pendek ke depan belakang untuk mengacau pemain belakang dan menciptakan peluang untuk menembus pertahanan. •
Penetrasi: prinsip dari penetrasi memerlukan pemain terutama pemain depan untuk bergerak sedalam mungkin ke area pertahanan lawan seperti bergerak mengarah untuk mengacaukan dan menghancurkan pertahanan lawan.
•
Menyebar: jika pemain depan hanya berkumpul pada satu titik di depan gawang, pemain belakang lawan dapat dengan mudah membuyarkan mereka. Dengan menyerang secara menyebar akan membuat pemain belakang lawan lebih terpecah dan bisa membuat kesempatan untuk penetrasi.
Tujuan dari pemain bertahan adalah untuk mencegah lawan dari mencetak angka, mendapatkan bola, dan melakukan serangan. Pemain bertahan dapat membuat beberapa formasi seperti man-to-man defence, zone defence,dan combined defence. Secara umum taktik dari bertahan dapat melibatkan: •
Delay: metode ini kebalikan dari penetrasi. Ketika pemain lawan memegang bola, tim membutuhkan waktu untuk membentuk kembali formasi untuk bertahan. Pemain bertahan harus memposisikan dirinya untuk dapat mengelimnasi sebanyak mungkin operan-operan ke depan untuk mencegah penetrasi terhadap pertahanan.
•
Support: ketika beberapa pemain langsung menghadapi lawan yang membawa bola, pemain bertahan lain harus memblok lawan lain untuk
19
mencegah kemungkinan mengoper bola. Teknik ini juga terkadang disebut sebagai marking. •
Balance: pemain bertahan harus dapat mendistribusikan pertahanan secara merata pada seluruh lapangan.
•
Pressuring:menekan (pressuring) adalah taktik bertahan aktifdan bisa juga disebut menyerang dalam bertahan. Tujuan dari menekan adalah untuk menyempitkan ruangan untuk lawan penyerang. Pemain yang menekan harus mempertahankan sedekat mungkin dengan lawan penyerang.
•
Control: pemain bertahan harus mempertahankan fungsinya pada keseluruhan struktur pertahanan.
•
Offside trap: ketika lawan bersiap untuk melakukan operan ke depan, pemain bertahan dapat bergerak sedemikian rupa sehingga satu atau beberapa pemain lawan akan mendapatkan posisi mereka offside. Metode ini membutuhkan konsentrasi penuh dan kordinasi yang kuat karena bila dilakukan tidak akurat malah dapat membuat lawan mencetak gol dengan mudah.
2.5. Memprediksi Posisi Mengoper pada posisi terbaik dalam permainan sepakbola merupakan hal yang kritikal terutama dalam proses menyerang. Memastikan bola sampai pada teman yang tepat sehingga dapat melakukan serangan dan tekanan yang lebih terhadap lawan. Oleh karena itu perlu dilakukan perhitungan resiko untuk menentukan arah mengoper yang paling baik.
20
Penelitian ini ingin mencoba menemukan titik optimalisasi dengan teknik normalized normal construction method pada single actors dalam posisi offense, jadi akan diurai lebih terperinci lagi terhadap jurnal-jurnal tersebut, dimulai dari jurnal Prof Vadim mengenai pemilihan mengoper bola (Kyrylov, Ball Passing: Balancing Rewards, Risks, Costs, and Real-Time Constraints, 2006) disinidibahas secara langkah demi langkah bagaimana menerapkan pareto optimal dan MultiCriteria Decision Analysisdalam mengoper bolaseperti halnya penelitian ini, namun penelitian ini menggunakan normalized normal constraint untuk membentuk pareto set. Berikutnya adalah jurnal Serguei & Vadim mengenai penerapan pareto optimal dalam defense (Kyrylov & Hou, Pareto-Optimal Collaborative Defensive Player Positioning in Simulated Soccer, 2009) dan juga jurnal Eddie Huo & Vadim mengenai penerapan pareto optimal dalam offensive(Kyrylov & Serguei, Pareto-Optimal Offensive Player Positioning in Simulated Soccer, 2008), keduanya menggunakan metode yang sama hanyacriteria factornya yang berbeda karena melihat adanya perbedaan tanggung jawab antara offense dan defense. Dengan objective function untuk menentukan posisipassing sebagai berikut (Kyrylov, Ball Passing: Balancing Rewards, Risks, Costs, and Real-Time Constraints, 2006): U(x, y) = −wGain(x, y) + (1− w)Risk(x, y) Dimanaw adalah faktor berat (0<w<1), (xhomei, yhomei) adalah posisi formasi kandang dan (xball, yball) adalah posisi bola berada. Jadi posisi ini akan berubah terus tergantung pada bola dan pemain akan tetap mempertahankan posisi
21
relatifnya terhadap formasi dimana dia bertanggung jawab dalam area tersebut. Dalam hal ini area yang jadi tanggung jawab pemain disebut feasible area dan untuk memprediksi posisi bola dipakai: P prediksi=P sekarang + V sekarang x T DimanaP adalah nilai vektor terhadap posisi pemain (x,y) dan T adalah time horison yg didefinisikan empiris yaitu kemungkinan lama pemain mendriblle bola.
Namun
ini
cara
lama
yang
didefinisikan
pada
jurnal
tentang
offensive(Kyrylov & Serguei, Pareto-Optimal Offensive Player Positioning in Simulated Soccer, 2008). Cara menentukan time horison yang baru telah dijabarkan pada jurnal berikutnya tentang defensive (Kyrylov & Hou, ParetoOptimal Collaborative Defensive Player Positioning in Simulated Soccer, 2009). Yaitu berupa radius lingkaran dimana area lingkaran tersebut adalah yang bisa dicapai dalam waktu T. Menentukan waktu T yang baik sangatlah kritikal, bila terlalu besar akan mengakibatkan prediksi yang terlalu jauh dan sia-sia, bila terlalu kecil akan membuat pemain kurang responsif terhadap gerakan lawan. Jadi dapat dirumuskan menentukan waktu yang tepat adalah: T=Tb+T Dimana Tb adalah waktu saat bola masih bergulir bebas dilapangan sebelum diambil oleh pemain.
2.6. Criteria Factors Karena setiap pemain memiliki tanggung jawab yang berbeda-beda, maka terdapat criteria factorsyang berbeda-beda untuk setiap kondisi.Berikut akan
22
dibahas secara singkat criteria factors yang pernah dikemukakan dalam penelitian-penelitian sebelumnya tentang Robotic Soccer. Masing-masing criteriafactors untuk offensive(Razykov, 2006): 1. Semua penyerang mempertahankan formasi mereka. Jadi pemain berusaha menjaga posisinya sedekat mungkin dengan titik recommended. X1i=PiPrec, semakin kecil nilainya semakin baik. 2. Semua penyerang harus terbuka untuk operan bola jadi harus berada dalam garis lurus dengan posisi yang diprediksi dari bola agar tidak di blok oleh lawan yang berada di dekatnya. X2i=Max(dtr-d(pipbola,plawan)). Dimana d adalah jarak dan dtr adalah threshold. Sebagai contoh, jika jarak dengan lawan terdekat adalah 5 meter jadi tidak masalah dijadikan 10 meter atau 50 meter dengan mengganggap lawan masih dapat menghalang operan dikarenakan jarak operan dan error dalam memilih arah tembakan. 3. Semua penyerang harus bisa mencari jarak sejauh mungkin dari lawan. X3i=Max(dtr-d(pi,plawan)) 4. Semua penyerang harus membuka jalur untuk ke gawang lawan sama seperti kriteria sebelumnya, namun ini digunakan untuk gawang: X4i=Max(dtr-d(pipgawang,plawan) 5. Semua penyerang tidak melewati garis offside. X5i=(Pi-Xoffside) Pemain bertahan yang baik memperhatikan gerakan bola terhadap lawan, berusaha menghadangnya terhadap gawang sendiri (Borden, 2009), oleh karena itupada kondisi bertahancriteria factor yang digunakan oleh Prof Vadim dan Eddie Huo (Kyrylov & Hou, Pareto-Optimal Collaborative
23
Defensivve Player Positioning P in Simulatted Soccer, 2009) yaittu melihat titikthrea at dengan ru umus:
Dimana:: •
adaalah sudut anngular dari gawang g sendiiri dengan laawan.
•
adalah jaarak posisi lawan dengann gawang.
•
adalah jarrak bola denggan posisi laawan.
Semakinn dekat pemaain dengan ttitik threat inni maka akaan semakin baik. b Sudut angular itu i sendiri adalah a diameeter visual dari suatu objjek yang diu ukur dalam Inc., 2010)). Berikut ruumus perhittungan dan sudut (W Wikimedia Foundation, F gambaraan sudut anguular itu senddiri:
G Gambar 5. Sudut S Angulaar (Wikimeddia Foundatiion, Inc., 20110) Pada saaat mengoperr bola untukk menyusun strategi, adaapun beberaapa criteria factors yang y dirang gkum dari jurnal j Prof. Vadim (K Kyrylov, Balll Passing: Balancin ng Rewards, Risks, Costs, and Real-T Time Constrraints, 2006)):
24
1.
Posisi pengoper tersebut lebih dekat dengan kawan. f1i=d(Pi-Pkawan)
2.
Posisi pengoper tersebut lebih jauh dengan lawan. f2i=d(Pi-Plawan)
3.
Sudutpengopermengarah pada area lawan. f3i=-0.5+(180’-(∠Pi/180’))
2.7. Pareto Optimality Pareto Optimality merupakan metode untuk menyelesaikan masalah multicriteriadi mana metode ini melihat suatu keputusan optimal adalah keputusan yang tidak didominasi oleh kriteria maupun entitas apapun. Nama pareto diambil dari Vilfredo Pareto, seorang ahli ekonomi asal Italia di tahun 1848-1923. Dia menciptakan suatu prinsip ekonomi dimana seseorang dapat memperoleh keuntungan maksimal tanpa perlu mengorbankan orang lain (Shor, 2006). Penggunaan prinsip pareto ini juga dapat diterapkan kedalam permasalahan multicriteria lainnya, bidang engineering, economy dan science (Stadler, 1988), seperti pada permasalah menentukan titik dalam simulasi sepakbola ini.Titik p1 dianggap anggota pareto optimal atau tidak didominasi p2 jika setidaknya satu kriterianya Ci(p) memenuhi Ci(p1) ≤ Ci(p2). Pada gambar 2, ditunjukkan pareto optimal set dari feasible set untuk masalah dengan dua kriteria yaitu titik-titik posisi yang berada pada garis depan (frontier).
25
Gambar 6. Pareto Optimal Set (Liu, Yang, & Whidborne, 2004) Masalah dalam pareto set ini adalah bagaimana menentukan pareto set yang baik dan membuat keputusan bahwa keputusan yang diambil memang sudah tidak didominasi dan memang menguntungkan beberapa pihak secara global.Ada banyak metode yang dipakai untuk pembentukan pareto set/pareto frontier, seperti weighted sum method, compromise programming, dan normalized normal constraint yang akan dijelaskan lebih detail. 2.7.1. Weighted Sum Method Teknik standar untuk membentuk
pareto
set
adalah
dengan
meminimalisasi masalah menggunakan weighted sum dari setiap criteria yang berbeda diberikan nilai weights yang berbeda. (Das & Dennis, A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, 1997). Sementara metode weighted sum itu sendiri meminimalisasi masalah multicriteria dengan mengubahnya menjadi perhitungan skalar dengan menjumlahkan total weight dari semua criteria factors yang dapat dirumuskan secara global (Liu, Yang, & Whidborne, 2004):
26
Dimana wk adalah koefisien berat (weight coefficient). Masalah ini kemudian dapat diselesaikan dengan algoritma optimisasi unconstrained standar. Inti utama dalam menyelesaikan masalah ini adalah memberikan koefisien berat pada setiap fungsi objektif/faktor kriteria, koefisien berat tidak perlu berhubungan relatif dengan kepentingan dari objektif atau memungkinkan pertukaran antara objektif yang akan diekspresikan. Lebih lagi, metode ini efektif untuk masalah yang dapat diminimisasi (convex) apabila masalah tersebut bersifat maksimalisasi ataupun gabungan keduanya (non-convex)maka metode ini tidak dapat digunakan. 2.7.2. Compromise Programming Compromise Programming adalah salah satu pendekatan yang mengambil paradigma berbeda dari teori utilitas. Ide dasar dari compromise programming adalah mengidentifikasi solusi sebagai sebuah poin dimana setiap atribut (criteria factors) dijadikan bahan pertimbangan untuk mendapatkan nilai optimalnya dan mencari solusi yang sedekat mungkin dengan poin ideal tersebut (Chen, Wiecek, & Zhang, 1999). Metode ini membutuhkan agen pengambil keputusan untuk menentukan kumpulan goals dari semua objektif yang ada. Jadi dianggap vektor goal adalah
…
…
. Maka perumusan untuk metode ini adalah:
27
Metode ini dibuktikan lebih baik daripada metode Weighted Sum (Steuer, 1989)karena lebih objektif dalam menentukan weight untuk setiap criteria functions yang ada dengan melihat terhadap goal yang ingin dicapai. Namun metode ini masih mewarisi sebagian kelemahan pada metode weighted sum jika pemilihan goal yang kurang tepat maka penyelesaian masalah akan jauh daripada optimal dan juga masalah yang diselesaikan oleh metode ini hanya bersifat convex saja. 2.7.3. Normalized Normal Constraint Method Messac et all (Messac, Yahaya, & Mattson, 2003) membandingkan beberapa teknik Multicriteria Optimization seperti Weighted Sum(Das & Dennis, A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, 1997), compromise programming(Chen, Wiecek, & Zhang, 1999), dan Normal Boundary Intersection (Das & Dennis, Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, 1998)denganhasil penelitiannya berupa sebuah tabel perbandingan efektifitas. Tabel 1. Efektifitas Metode Pareto Set (Messac, Yahaya, & Mattson, 2003)
28
Kesimpulan yang diambil oleh Messac et al bahwa metode Weighted Sum & Physical Programming merupakan metode yang paling mudah diterapkan dalam menentukan pareto set, namun apabila menentukan weight maupun algoritma tidak sesuai maka hasilnya dapat jauh dari yang diharapkan. Untuk Compromise Programming dapat diterapkan pada masalah convex dan nonconvex yaitu masalah yang dalam penggambaran grafik danpenyebaran titik-titik solusinya membentuk cembungan atau tidak. Namun metode compromise programming masih mewarisi kekurangan pada metode weighted sum. Penelitian Messac menerapkan metode-metode tersebut terhadap masalah matematika pengukuran:
Dimana hasil pareto set yang didapat oleh metode normalized normal constraint lebih merata dibandingkan metode lainnya (gambar 4)
29
Gambar 7. Grafik sebaran pareto set (a)Normalized Normal Constraint (b)Physical Programming (c)Compromise Programming (d) Weighted Sum (Messac, Yahaya, & Mattson, 2003)
Gambar 8. (kiri) bentuk awal dari feasible area;(kanan) normalisasi dan pembentukan utopia line (Martinez, Sanchis, & Blasco, 2007) Secara garis besar metode ini akan menormalisasi titik-titik optimal dari masingmasing kriteria dan membentangkan garis (utopia line) diantaranya untuk didapatkan kumpulan pareto set. Langkah-langkah perhitungannya adalah sebagai berikut (Messac, Yahaya, & Mattson, 2003):
30
1. Generate
titik-titik
pareto
setdari
utopia
line,
0dimana 2. Menentukan anchor points yaitu dengan mencari solusi titik paling optimal tersendiri dari F1 dan F2. Kita sebut ini x1* dan x2* 3. Normalisasi, sebelumnya kita mencari dulu jarak antara anchor points terhadap kriteria tersebut l1=F1(x1*)-F1(x2*) dan l2=F2(x1*)-F2(x2*),lalu normalisasi setiap titik dengan rumus: 4. Membentuk Utopia Line, adalah selisih dari anchor points yang sudah dinormalisasi. 5. Menentukan normalized increment, untuk membentuk garis dari vektor utopia line, dilakukan penambahan sebesar:
dimana m1 adalah
nilai pembagi yang sudah ditentukan sebelumnya. 6.
Generate Line,
titik-titik dimana∑
dari
Utopia
1
2.8. Tao of Soccer Tao of Soccer adalah salah satu tools open source untuk simulasi roboticsoccer yang digunakan dalam RoboCup, tools ini ditulis dengan menggunakan bahasa Java menggunakan arsitektur client-server(Zhang, 2005). Peran tools ini dalam penelitian ini adalah menjadi wadah untuk visualisasi simulasi dimanaTao of Soccer menyediakan lingkungan simulasi sepakbola, jadi penelitian ini membuat coding program untuk pemainnya (agen) dalam hal ini menerapkan metode Normalized Normal Constraint.
