Download - Proposal Disertasi Libre
-
USULAN PENELITIAN
FUNGSI HEURISTIK SEBAGAI STRATEGI PENCARIAN CERDAS PADA PENYELESAIAN SHORTEST PATH PROBLEM
Oleh:
ANDYSAH PUTERA UTAMA SIAHAAN
PROGRAM STUDI DOKTOR (S3) T. INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
UNIVERSITAS SUMATERA UTARA M E D A N
2015
-
BAB I
PENDAHULUAN
1.1. Latar Belakang Masalah
Rute optimum sangat dibutuhkan dalam melakukan perjalanan dalam mencapai suatu
titik tujuan. Sehingga dibutuhkan suatu cara bagaimana mencapai lokasi secara
maksimal. Kemudian lahirlah beberapa metode yang kemudian dirangkum dalam
suatu algoritma. Tetapi yang terjadi adalah banyaknya pemahaman tentang algoritma
sehingga menimbulkan pertanyaan, algoritma mana yang terbaik. Algoritma
merupakan istilah yang merujuk kepada aturan-aturan simetris yang berfungsi untuk
menyelesaikan serangkaian persoalan yang kemudian disusun secara sistematis dan
dapat dengan mudah dipahami. Langkah yang disusun dari awal sampai akhir dapat
dipecah dan diterjemahkan satu persatu sehingga dapat dimengerti maksud dan
tujuannya. Algoritma tercipta dikarenakan adanya suatu masalah yang timbul.
Masalah tersebut dapat berupa apapun dengan catatan untuk setiap masalah, memiliki
kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma.
Setiap suatu masalah bisa saja mempunyai lebih dari satu penyelesaian. Contohnya,
pada saat terjadi suatu pilihan terhadap suatu penyelesaian masalah, jalan alternatif
pasti akan selalu dapat diikutsertakan sehingga menimbulkan hasil yang lebih dari
satu, sehingga akan terjadi kebingunan dalam memilih jalan mana yang akan
ditempuh. Untuk menjawab pertanyaan seperti demikian, diperlukanlah beberapa
-
2
pertimbangan yang akan menentukan mengapa jalan tesebut yang lebih baik dipilih
untuk kasus tertentu.
Pada permasalahan pencarian rute optimum, setiap algoritma yang berhubungan
dengan pencarian rute akan menghasilkan nilai atau hasil global yang belum tentu
sama. Sehingga dibutuhkan beberapa kriteria penentu untuk memperkuat pemilihan
terhadap suatu algoritma. Secara umum, pencarian jalur optimum dapat dilakukan
dengan dua metode, yaitu: metode konvensional dan metode heuristik. Metode
konvensional adalah metode yang menggunakan perhitungan sederhana yang biasa
digunakan untuk menyelesaikan beberapa verteks saja. Sementara untuk verteks yang
lebih banyak, metode heuristik lebih variatif karena metode heuristik menggunakan
metode pendekatan dan melakukan pencarian terarah.
Timbulnya berbagai macam metode heuristik untuk menghitung jarak optimum dari
suatu lintasan, maka terjadi perbandingan dan perhitungan untuk menentukan metode
mana yang terbaik yang dapat digunakan untuk penentuan rute optimum. Maka
dengan ini, penulis tertarik untuk membahas tentang metode heuristik mana yang
terbaik dilakukan untuk mendapatkan nilai global yang optimum.
Metode heuristik dapat dibentuk dengan berbagai ketentuan, sehingga perhitungan
heuristik tersebut berpengaruh besar terhadap hasil yang dicapai. Biasanya ketentuan
pada fungsi heuristik akan melibatkan perhitungan jarak dari titik awal dan titik akhir,
-
3
ketentuan pada fungsi heuristik tersebut dapat dibentuk dari beberapa perhitungan.
Disini penulis akan mencoba menciptakan suatu fungsi heuristik yang akan
membandingkan hasil dengan fungsi heuristik lainnya. Pada kasus-kasus tertentu
heuristik yang satu akan lebih baik dibanding heuristik yang lain, sementara pada
kasus-kasus yang lain, heuristik yang lain akan lebih baik pula dari pada heuristik
yang sebelumnya. Sehingga perlu diadakan analisa terhadap fungsi-fungsi heuristik
tersebut dalam suatu penelitian.
1.2. Rumusan Masalah
Adapun masalah yang dibahas dalam Tugas Akhir ini adalah:
1. Bagaimana mendapatkan fungsi heuristik yang optimal.
2. Fungsi heuristik mana yang terbaik jika digunakan dalam pencarian rute
optimum.
3. Kriteria apa yang menjadi penentu fungsi heuristik yang akan digunakan
dalam suatu pencarian.
4. Bagaimana mengukur kompleksitas fungsi heuristik.
1.3. Batasan Masalah
Batasan masalah dalam Tugas Akhir ini adalah sebagai berikut:
1. Sistem akan menampilkan perbandingan fungsi heurisik secara visual.
2. Graph yang digunakan yang mempunyai bobot dan arah.
3. Mengambil beberapa landmark sebagai objek acuan sumber dan tujuan.
-
4
4. Menggunakan algoritma A*.
5. Menggunakan beberapa model fungsi heuristik.
1.4. Tujuan Penelitian
Adapun tujuan dari penelitian ini adalah sebagai berikut:
1. Menentukan fungsi heuristik terbaik untuk mendapatkan lintasan terpendek
agar dapat menghemat waktu perjalanan.
2. Menentukan efisiensi dari fungsi heuristik.
3. Mencari tahu fungsi heuristik mana yang lebih optimal dalam kasus-kasus
tertentu.
1.5. Manfaat Penelitian
Manfaat penelitian ini adalah sebagai berikut:
1. Memberikan perbandingan dari beberapa fungsi heuristik yang digunakan.
2. Memberikan fungsi heuristik kepada penerima informasi.
3. Memberikan acuan sebagai penentu bagi fungsi heuristik yang digunakan.
4. Memberi peluang untuk pengembangan ilmu pengetahuan dibidang ilmu
komputer.
-
BAB II
TINJAUAN PUSTAKA
2.1. Algoritma
Algoritma adalah suatu prosedur, terdiri dari langkah-langkah yang terbatas yang
akan menyelesaikan persoalan yang diberikan dalam waktu tertentu. Touring
Machine adalah salah satu contoh dari masalah yang diselesaikan oleh suatu
algoritma. (Hetland, 2010)
Secara informal, algoritma adalah prosedur komputasi yang mengambil beberapa
nilai atau seperangkat nilai sebagai masukan dan menghasilkan beberapa nilai, atau
seperangkat nilai sebagai output. Sebuah algoritma dengan demikian merupakan
urutan langkah komputasi yang mengubah input menjadi output. Kita juga dapat
melihat sebuah algoritma sebagai alat untuk memecahkan masalah komputasi.
Pernyataan sebuah masalah menentukan secara umum hubungan input / output yang
diinginkan. Algoritma ini menggambarkan langkah-langkah yang ditempuh untuk
mencapai hubungan input / output. (Cormen, 2009)
2.2. Graph
Graph adalah suatu alat bantu untuk merepresentasikan objek-objek diskrit dan
hubungan antara objek-objek tersebut. Graph G didefinisikan sebagai pasangan
himpunan (V, E), ditulis dengan notasi G = (V, E). V (vertex) merupakan merupakan
-
6
himpunan tidak kosong dari simpul. E (edge) merupakan himpunan sisi yang
menghubungkan sepasang simpul. Simpul pada graph umumnya diberi identitas
dengan huruf atau angka. Sedangkan sisi pada graph umumnya dinamai dengan
himpunan simpul yang dihubungkan oleh sisi tersebut. (West, 2005)
Gambar 2.1. : Contoh Graph
Sumber : (West, 2005)
Graph begitu terkenal karena mereka dipresentasikan secara grafis, yang
membuat kita mengerti kandungan-kandungan di dalam graph. Setiap verteks
diindikasikan sebagai titik, dan setiap edge diindikasikan sebagai garis penghubung
antara verteks. (Bondy et al., 2002)
-
7
Graph terdiri dari berbagai jenis diantaranya graph sederhana, graph tidak
sederhana, dan graph berarah. Graph sederhana adalah graph yang tidak memiliki
sisi ganda dan juga gelang. Sisi ganda merupakan kondisi ketika dua buah simpul
memiliki lebih dari satu sisi. Sisi gelang adalah ketika ada sisi yang berasal dari satu
simpul dan kembali pada simpul tersebut. Sedangkan graph tak sederhana adalah
graph yang memiliki sisi ganda dan atau gelang. Graph berarah merupakan graph
yang setiap sisinya memiliki orientasi arah dari suatu simpul ke simpul lainnya.
Graph berbobot adalah graph yang memiliki nilai pada setiap sisinya.
2.2.1. Graph Berarah
Graph berarah G terdiri dari suatu himpunan V dari verteks-verteks dan suatu
himpunan E(A) dari edge sedemikian rupa sehingga setiap edge a A menghubungkan pasangan verteks terurut. Jika terdapat sebuah edge a yang
menghubungkan pasangan terurut (v,w) dari verteks-verteks, maka dapat ditulis
dengan a=(v,w), yang menyatakan sebuah edge dari v ke w.
-
8
Gambar 2.2. : Graph Berarah
Sumber : (Bna, 2006)
2.2.2. Graph Tidak Berarah
Graph tidak berarah G terdiri dari suatu himpunan V dari verteks-verteks dan suatu
himpunan E dari edge-edge sedemikian rupa sehingga setiap sisi e E dikaitkan dengan pasangan verteks tak terurut. Jika terdapat sebuah edge e yang
menghubungkan verteks v dan w, maka dapat dituliskan dengan e = (v,w) atau e =
(w,v) yang menyatakan sebuah edge antara v dan w.
-
9
Gambar 2.3. : Graph Tidak Berarah
Sumber : (Bna, 2006)
2.2.3. Graph Berbobot
Dalam banyak aplikasi digunakan graph berbobot w(x, y) yang diasosiasikan dengan
edge(x, y). Contohnya, graph digunakan untuk sistem rute lalu lintas, bobot adalah
jarak dari dua buah landmark pada suatu kota. Dalam memodelkan suatu masalah ke
dalam graph, ada informasi yang ditambahkan pada graph. Misalnya pada graph
yang menggambarkan peta jalan raya antara kota-kota, dapat ditambahkan sebuah
bilangan pada setiap edge untuk menunjukkan jarak antara kedua kota yang
dihubungkan oleh edge tersebut. (Wallis, 2007)
-
10
Gambar 2.4. : Graph Berbobot
Sumber : (Bna, 2006)
2.3. Metode Pencarian
Ada banyak metode yang dapat digunakan untuk pencarian jalur terpendek pada suatu
graph. Metode pencarian tersebut dapat dikelompokkan ke dalam dua jenis, yaitu
pencarian buta atau tanpa informasi (blind atau un-informed search) dan pencarian
heuristik atau dengan informasi (heuristic atau informed search). Dikatakan
pencarian buta, karena pada pencarian ini tidak ada informasi awal. Sementara
heuristik adalah pencarian yang mempunyai informasi. Disini hanya akan dibahas dua
metode pencarian, yaitu Breadth First Search, Depth First Search.
2.3.1. Breadth First Search
Breadth First Search adalah algoritma yang sederhana untuk pencarian pada graph.
Algoritma Prim pada minimum spanning tree dan algoritma Dijkstras single shortest path adalah dua buah algoritma yang mengambil ide dari breadth-first-search.
Breadth-first-search sangat begitu terkenal karena algoritma ini mempunyai cara
-
11
memperluas perbatasan antara simpul ditemukan dan belum ditemukan di seluruh
tahap pencarian. Artinya, algoritma menemukan semua verteks pada jarak k sebelum
menemukan setiap verteks pada jarak k + 1.(Rivest, 2009)
Pencarian dilakukan pada semua verteks pada level n secara berurutan dari kiri ke
kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada
level berikutnya (n+1). Demikian seterusnya sampai ditemukan solusi. Dengan
strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling
baik (Optimal). Tetapi BFS harus menyimpan semua node yang pernah dibangkitkan,
hal ini harus dilakukan untuk penelusuran balik jika solusi sudah ditemukan, sehingga
membutuhkan memori yang cukup banyak.
-
12
Gambar 2.5. : Proses Breadth First Search
Sumber : (Cormen, 2009)
2.3.2. Depth First Search
Depth-first-search mengeksplorasi edge keluar dari verteks yang paling baru
ditemukan yang memiliki edge yang belum dijelajahi. Setelah semua edge telah
dieksplorasi, pencarian meninggalkan verteks dari yang ditemukan. Proses ini
berlanjut sampai kita telah menemukan semua simpul yang terjangkau dari verteks
sumbernya. Jika masih ada simpul yang belum ditemukan, maka depth-first-search
-
13
akan memilih salah satunya sebagai sumber baru, dan mengulangi pencarian dari
sumber tersebut. Algoritma ini akan mengulangi seluruh proses ini sampai telah
ditemukan setiap verteks. (Stein, 2009)
Pencarian dilakukan pada satu verteks dalam setiap level dari yang paling kiri. Jika
pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan
pada verteks sebelah kanan. Verteks yang kiri dapat dihapus dari memori. Jika pada
level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada
level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi
ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk
mendapatkan jalur yang dinginkan). Kelebihan dari algoritma ini adalah pemakaian
memori yang lebih sedikit, sedangkan kelemahannya adalah jika pohon yang
dibangkitkan memiliki level yang sangat dalam (tak terhingga), maka tidak ada
jaminan menemukan solusi. Artinya, DFS tidak complete (tidak ada jaminan
penemuan solusi).
-
14
Gambar 2.6. : Proses Depth First Search
Sumber : (Cormen, 2009)
Pada metode pencarian buta, tidak dimiliki pengetahuan khusus tentang permasalah
yang dihadapi sehingga metode tersebut tidak efisien untuk banyak kasus karena bisa
saja metode tersebut tidak complete dan atau tidak optimal dalam mendapatkan
solusi, optimal disini adalah tidak menjamin menemukan solusi yang terbaik jika
terdapat beberapa solusi yang berbeda. Menggunakan informasi khusus yang spesifik
untuk suatu masalah tertentu akan sangat memperbaiki kecepatan pencarian solusi,
karena teknik ini membantu memutuskan kemungkinan solusi mana yang pertama
kali perlu di evaluasi. Pencarian heuristik digunakan untuk mengeliminasi beberapa
kemungkinan solusi, tanpa harus mengeksplorasinya secara penuh.
-
15
2.4. Algoritma A*
Algoritma A* adalah algoritma pencarian yang merupakan pengembangan dari kelas
algoritma Greedy. Seperti halnya pada Greedy, untuk menemukan solusi, A* juga
dilakukan oleh fungsi heuristik, yang menentukan urutan titik mana yang akan
dikunjungi terlebih dahulu. Heuristik merupakan penilai yang memberi harga pada
tiap verteks yang memandu A* mendapatkan solusi yang diinginkan.
Algoritma A* menyelesaikan masalah yang menggunakan graph untuk perluasan
ruang statusnya. Dengan kata lain digunakan untuk menyelesaikan permasalah yang
bisa direpresentasikan dengan graph. Algoritma A* adalah sebuah algoritma yang
telah dikembangkan. Dengan menerapkan fungsi heuristik, algoritma ini membuang
langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang
dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang
diinginkan.
Secara informal, algoritma bekerja dalam banyak cara yang sama seperti pada
algoritma Dijkstra. Daripada selalu mempertimbangkan verteks terbuka dengan nilai
terendah, lebih baik memilih verteks yang paling mungkin untuk mengarahkan
pencarian ke arah tujuan dengan nilai terkecil. Semuanya dikendalikan oleh sebuah
fungsi heuristik. Jika fungsi tersebut akurat, maka algoritma akan efisien dan rute
terpendek akan segera ditemukan jika memang ada. (Millington, 2009)
-
16
Secara lebih rinci, A* bekerja dalam iterasi. Pada setiap iterasi dianggap satu proses
pencarian untuk verteks berikutnya. Pemilihan verteks menggunakan suatu algoritma
seleksi yang mirip pada algoritma Dijkstra, tetapi dengan perbedaan yang signifikan
dari fungsi heuristik.
Gambar 2.7. : Proses Pencarian Algoritma A*
Sumber : (Millington, 2009)
Nilai heuristik dipergunakan untuk mempersempit ruang pencarian. Metoda
pencarian A* mempunyai perlakuan yang sama seperti pada best-first-search tetapi
menggunakan satu metode untuk menentukan biaya perjalanannya. (Coppin, 2004)
-
17
Metode ini berdasarkan formula:
f(n) = g(n) + h(n)
Keterangan :
- h(n) = biaya estimasi dari verteks n ke tujuan.
- g(n) = biaya path / perjalanan
- f(n) = solusi biaya estimasi termurah verteks n untuk mencapai tujuan.
Penggunaan algoritma A* dengan fungsi heuristik yang tepat dapat memberikan hasil
yang optimal. Sebenarnya, depth-first search (DFS) dan breadth- first-search (BFS)
adalah dua kasus khusus dari algoritma A*. Algoritma Dijkstra, salah satu BFS,
adalah kasus khusus dari A* dimana h(x) = 0 untuk semua nilai x. Untuk DFS,
ciptakan suatu counter global C yang diinisialisasi dengan nilai yang sangat besar.
Pada setiap langkahnya, periksa sebuah titik, lalu berikan nilai C ke semua titik yang
bertetangga dengan titik tadi. Setelah tiap-tiap pemberian nilai, kurangi counter C
dengan 1. Jadi semakin awal sebuah titik diproses, semakin tinggi nilai h(x) yang
dimilikinya.
Beberapa terminologi dasar yang terdapat pada algoritma A* antara lain:
1. Starting point adalah sebuah terminologi untuk posisi awal sebuah benda.
2. A adalah simpul yang sedang dijalankan dalam algortima pencarian jalan
terpendek.
-
18
3. Simpul adalah petak-petak kecil sebagai representasi dari area pathfinding.
Bentuknya dapat berupa persegi, lingkaran, maupun segitiga.
4. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari
starting point maupun simpul yang sedang dijalankan.
5. Closed list adalah tempat menyimpan data simpul sebelum A yang juga
merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
6. Harga (F) adalah nilai yang diperoleh dari penjumlahan, nilai G merupakan
jumlah nilai tiap simpul dalam jalur terpendek darititik awal ke A, dan H
adalah jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan. Sehingga
dapat diformulasikan dengan f(x) = g(x)+h(x).
7. Simpul tujuan adalah simpul yang dituju.
8. Halangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak
dapat dilalui oleh A.
Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal
(starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.
Diawali dengan menempatkan A pada starting point, kemudian memasukkan seluruh
simpul yang bertetangga dan tidak memiliki atribut rintangan dengan A ke dalam
open list. Kemudian mencari nilai H terkecil dari simpul-simpul dalam open list
tersebut. Kemudian memindahkan A ke simpul yang memiliki nilai H terkecil.
Simpul sebelum A disimpan sebagai parent dari A dan dimasukkan ke dalam closed
list. Jika terdapat simpul lain yang bertetangga dengan A (yang sudah berpindah)
-
19
namun belum termasuk kedalam anggota open list, maka simpul-simpul tersebut akan
dimasukkan ke dalam open list. Setelah itu, membandingkan nilai G yang ada dengan
nilai G sebelumnya (pada langkah awal, tidak perlu dilakukan perbandingan nilai G).
Jika nilai G sebelumnya lebih kecil maka A kembali ke posisi awal. Simpul yang
pernah dicoba dimasukkan ke dalam closed list.
2.5. Fungsi Heuristik
Dalam metode pencarian heuristik, digunakan suatu metode yang digunakan untuk
mengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauh
hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Fungsi
heuristik berbeda untuk setiap tujuan, sehingga fungsi ini sering dijadikan sebagai
parameter penting dalam menyelesaikan permasalahan. Fungsi heuristik
diimplementasikan untuk mencari jarak dari dua buah verteks, yang biasanya
menggunakan euclidean dan manhattan distance. (Funge, 2009)
Suatu fungsi heuristik dapat dikatakan baik, apabila dapat memberikan biaya
perkiraan yang mendekati biaya sebenarnya. Semakin mendekati biaya sebenarnya,
fungsi heuristik tersebut semakin baik. Dalam masalah pencarian rute terpendek
dengan graph, fungsi heuristik yang dapat digunakan adalah Manhattan Distance.
-
20
2.5.1. Manhattan Distance
Manhattan Distance adalah salah satu fungsi heuristik yang paling sering digunakan
dalam menghitung jarak terdekat dari dua titik. Fungsi ini hanya menghitung selisih
koordinat posisi titik awal dan titik akhirnya saja. Awalnya model ini digunakan di
kota Manhattan, Amerika, karena di kota ini jarak dari dua lokasi dihitung dari blok-
blok jalan yang harus dilalui saja, sehingga tidak bisa dilewati secara diagonal.
Fungsi heuristik ini dapat dihitung berdasarkan selisih jarak koordinat yang diambil
dari dua buah titik, yang dapat diformulasikan menggunakan rumus :
Ha-b = abs (x2 x1) + (y2 y1) Keterangan:
- Ha-b : estimasi jarak a ke b
- x1 : koordinat x titik b
- y1 : koordinat y titik b
- x2 : koordinat x titik a
- y2 : koordinat y titik a
Fungsi dari abs di atas untuk mengubah nilai negatif menjadi nilai positif. Ini terjadi
apabila titik awal berada lebih jauh dari titik akhir (reverse), sehingga pengurangan
x2 x1 mempunyai hasil yang negatif.
-
21
2.5.2. Euclidean Distance
Euclidean adalah fungsi heuristik yang diperoleh berdasarkan jarak langsung bebas
hambatan seperti untuk mendapatkan nilai dari panjang garis diagonal pada segitiga.
Tetapi sebelum mendapatkan hasil kedua titik harus direpresentasikan ke dalam
koordinat 2 dimensi (x, y), sehingga dapat dihitung melalui rumus:
Ha-b = Keterangan:
- Ha-b : estimasi jarak a ke b
- x1 : koordinat x titik b
- y1 : koordinat y titik b
- x2 : koordinat x titik a
- y2 : koordinat y titik a
Dalam perhitungan matematika jarak Euclidean akan mempunyai jarak yang lebih
pendek dari pada jarak Manhattan, maka dapat dipastikan jarak Euclidean akan lebih
sering menemukan jarak yang lebih pendek daripada jarak Manhattan.
-
22
2.5.2. Euclidean Distance Kuadrat
Euclidean kuadrat adalah fungsi heuristik yang didapat dari perubahan fungsi yang
didapat dari hasil perhitungan jarak Euclidean, tetapi akar pemangkatan tidak
diperhitungkan dalam mendapatkan nilainya, sehingga rumusnya berubah menjadi:
Ha-b =
2.6. Kontribusi Penelitian
Penelitian ini memberikan kontribusi dalam hal pemberian metode baru untuk
mendapatkan hasil optimum yang baru. Berdasarkan penelitian-penelitian yang ada
yang sudah pernah dilakukan, diciptakanlah suatu perumusan dalam penentuan nilai
heuristik yang baru yang mempunyai hasil yang berbeda dengan fungsi heuristik
yang sudah pernah ada.
-
BAB III
METODOLOGI PENELITIAN
3.1. Tempat dan Waktu Penelitian
Tempat penelitian dilakukan didaerah tempat dimana penulis tinggal yaitu di kota
Medan, kecamatan Medan Baru. Waktu berlangsungnya penelitian ini diperhitungkan
lebih kurang sekitar 2 tahun.
3.2. Bahan-bahan
Untuk mempercepat penyelesaian penelitian, maka digunakan beberapa alat
pendukung, antara lain:
- Komputer (Hardware dan Software)
- Peta Digital
- Meja Gambar
- Alat Ukur untuk penskalaan
3.3. Rancangan
Penelitian akan menghasilkan data-data yang mentah (raw data) yang belum dapat
digunakan untuk menarik suatu kesimpulan ataupun hasil. Pada tahap ini dibutuhkan
perantara proses untuk mengolah data tersebut. Dengan demikian dirancanglah suatu
media pengolah data yang berbasis komputer untuk menyelesaikan permasalahan
-
yang terjadi melalui data-data yang telah dikumpulkan. Kemudian akan diambil
kesimpulan hasil dari proses yang telah dikerjakan.
3.4. Pelaksanaan Penelitian
Adapun beberapa tahap pelaksanaan penelitian ini, antara lain:
Persiapan:
- Pengumpulan data.
- Mengamati permasalahan dalam periode tertentu.
- Mencari dan mempertimbangkan gambaran solusi terbaik.
- Menetapkan desain penelitian.
- Menentukan instrumen atau alat uji dalam penelitian.
- Menyusun format pengumpulan data mentah.
Pengorganisasian dan pelaksanaan:
- Pengujian penelitian.
- Mempersiapkan dan menyediakan bahan dan peralatan penelitian.
- Menganalisis data secara keseluruhan.
- Menyimpulkan hasil analisis, membuat tafsiran.
- Kesimpulan hasil serta membahasnya.
-
Penyusunan laporan hasil penelitian:
- Menyusun draft laporan.
- Memeriksa secara keseluruhan isi dari laporan penelitian.
- Menyusun laporan akhir dan bahan untuk seminar.
- Penyelenggaraan seminar.
3.5. Variable Yang Diamati
Dalam penelitian ini ada bebearapa variable yang menjadi acuan hasil, antara lain:
- Titik koordinat antar landmark.
- Fungsi heuristik.
-
DAFTAR PUSTAKA
R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.
C. Anderson, D. Smith, D. Weld, Conditional effects in Graphplan, in: Proc. 4th International Conference on AI Planning Systems, AAAI Press, Menlo Park, CA, 1998, pp. 4453.
A. Blum, M. Furst, Fast planning through planning graph analysis, Artificial Intelligence 90 (12) (1997) 281300.
B. Bonet, H. Geffner, Planning as heuristic search: New results, in: Recent Advances in AI Planning: Proc. 5th European Conference on Planning, Lecture Notes in Artificial Intelligence, Vol. 1809, Springer, Berlin, 1999, pp. 359371.
F. Bacchus, F. Kabanza, Using temporal logics to express search control knowledge for planning, Artificial Intelligence 116 (12) (2000) 123191.
B. Bonet, G. Loerincs, H. Geffner, A robust fast action selection mechanism for planning, in: Proc. AAAI-97, Providence, RI, AAAI Press, Menlo Park, CA, 1997, pp. 714719.
J. Carlier, E. Pinson, An algorithm for solving the job shop problem, Management Sci. 35 (2) (1989) 164176.
J. Culberson, J. Schaeffer, Pattern databases, Comput. Intelligence 14 (3) (1998) 318334.
R. Fikes, N. Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence 2 (1971) 189208.
H. Geffner, Functional Strips: A more general language for planning and problem solving, Logic-based AI Workshop, Washington, DC, 1999.
A. Gerevini, L. Schubert, Inferring state constraints for domain-independent planning, in: Proc. AAAI-98, Madison, WI, AAAI Press, Menlo Park, CA, 1998, pp. 905912.
W. Harvey, M. Ginsberg, Limited discrepancy search, in: Proc. IJCAI-95, Montreal, Quebec, Morgan Kaufmann, San Francisco, CA, 1995, pp. 607613.
P. Haslum, H. Geffner, Admissible heuristics for optimal planning, in: Proc. 5th International Conference on AI Planning Systems, AAAI Press, Menlo Park, CA, 2000, pp. 7082.
R. Holte, I. Hernadvolgyi, A space-time tradeoff for memory-based heuristics, in: Proc. AAAI-99, Orlando, FL, AAAI Press, Menlo Park, CA, 1999, pp. 704709.
J. Hoffmann, A heuristic for domain independent planning, and its use in an enforced hill-climbing algorithm, in: Proc. 12th International Symposium on Methodologies for Intelligent Systems (ISMIS-00), Springer, Berlin, 2000, pp. 216227.
P. Van Hentenryck, H. Simonis, M. Dincbas, Constraint satisfaction using constraint logic programming, Artificial Intelligence 58 (13) (1992) 113159.
-
A. Junghanns, J. Schaeffer, Domain-dependent single-agent search enhancements, in: Proc. IJCAI-99, Stockholm, Sweden, Morgan Kaufmann, San Francisco, CA, 1999, pp. 570575.
S. Kambhampati, R. Sanchez Nigenda, Distance based goal ordering heuristics for Graphplan, in: Proc. 5th International Conference on Artificial Intelligence Planning and Scheduling, AAAI Press, Menlo Park, CA, 2000, pp. 315322.
J. Koehler, B. Nebel, J. Hoffman, Y. Dimopoulos, Extending planning graphs to an ADL subset, in: Recent Advances in AI Planning: Proc. 4th European Conference on Planning, Lecture Notes in Artificial Intelligence, Vol. 1348, Springer, Berlin, 1997, pp. 273285.
R. Korf, Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence 27 (1) (1985) 97109.
R. Korf, Real-time heuristic search, Artificial Intelligence 42 (23) (1990) 189211. H. Kautz, B. Selman, Pushing the envelope: Planning, propositional logic, and
stochastic search, in: Proc. AAAI-96, Portland, OR, AAAI Press, Menlo Park, CA, 1996, pp. 11941201.
H. Kautz, B. Selman, Unifying SAT-based and Graph-based planning, in: Proc. IJCAI-99, Stockholm, Sweden, Morgan Kaufmann, San Francisco, CA, 1999, pp. 318327.
R. Korf, L. Taylor, Finding optimal solutions to the Twenty-Four Puzzle, in: Proc. AAAI-96, Portland, OR, AAAI Press, Menlo Park, CA, 1996, pp. 12021207.
D. Long, M. Fox, The efficient implementation of the plan-graph in STAN, J. Artificial Intelligence Res. 10 (1999) 85115.
D. Long, M. Fox, Utilizing automatically inferred invariants in graph construction and search, in: Proc. 5th International Conference on AI Planning Systems, AAAI Press, Menlo Park, CA, 2000, pp. 102111.
P. Laborie, M. Ghallab, Planning with sharable resources constraints, in: Proc. IJCAI-95, Montreal, Quebec, Morgan Kaufmann, San Francisco, CA, 1995, pp. 16431649.