4 Teknik Pemecahan Masalah Artificial Intelegence serta Penerapan Metode A* dalam Menentukan Rute Tercepat

Menurut (Suyanto, 2014) terdapat empat teknik pemecahan masalah dalam Artificial Intelegence, diantaranya adalah sebagai berikut ini.

1.     Searching

Searching atau pencarian merupakan teknik pemecahan masalah dengan cara pencarian solusi yaitu mempresentasikan masalah ke dalam ruang keadaan (state) dan secara sistematis melakukan pembangkitan dan pengujian state-state dari initial state sampai ditemukan suatu goal state. Teknik searching terbagi menjadi dua yaitu Blind Searching, dan Heuristic Searching. (Suyanto, 2014; Yusrizal, 2011)

• Blind Searching merupakan model pencarian buta atau pencarian yang tidak memiliki informasi awal, model pencarian ini memiliki tiga ciri – ciri utama, yaitu: (1) Membangkitkan simpul berdasarkan urutan, (2) Jika ada solusi maka solusi akan ditemukan, (3) Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui). Contoh Blind Searching: BFS (Breadth First Search), DFS (Depth-first Search), UCS (Uniform Cost Search).

• Heuristic Searching merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Contoh Heuristic Searching: Generate and Test, Hill Climbing, Best First Search.

Contoh Searching: Digunakan dalam pencarian rute optimum untuk memandu seseorang di perjalanan, misal di swedia setiap taksi dilengkapi dengan GPS (Global Positioning System). Contoh lainnya digunakan dalam kamus dan web browser.

2.     Reasoning

Reasoning atau penalaran merupakan teknik pemecahan masalah dengan cara merepresentasikan masalah kedalam basis pengetahuan menggunakan logic (mathematics tools yang digunakan untuk merepresentasikan dan memanipulasi fakta dan aturan) atau bahasa formal (bahasa yang dipahami komputer). Tujuan dari penalaran adalah untuk menentukan secara logis dan objektif, apakah suatu pernyataan valid (benar atau salah) sehingga pantas untuk diyakini atau dianut. (Suyanto, 2014; Huda, 2017)

Lima Jenis Logic Pengetahuan Untuk Penalaran

Jenis Logic	Apa yang ada di dunia nyata	Apa yang dipercaya agent tentang fakta
Proposotional Logic	Fakta	Benar/salah/tidak diketahui
First-order logic	Fakta, objek, relasi	Benar/salah/tidak diketahui
Temporal logic	Fakta, objek, relasi, waktu	Benar/salah/tidak diketahui
Probability theory	Fakta	Derajat kepercayaan [0,1]
Fuzzy Logic	Derajat kebenaran	Derajat kepercayaan [0,1]

 

Contoh Reasoning: Software permainan catur HITECH adalah sistem AI pertama yang berhasil mengalahkan grandmaster dunia Arnold Danker.

 

3.     Planning

Planning atau perencanaan merupakan teknik pemecahan masalah dengan cara memecah masalah dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang terdapat pada sub-sub masalah tersebut. (Suyanto, 2014)

Pengujian keberhasilan suatu metode planning dapat dilakukan pada suatu domain yang dinamakan Dunia Balok (Blocks-World). Dua metode planning yang cukup populer dan sudah pernah diuji pada Dunia Balok adalah Goal-Stack-Planning (GSP) dan Constraint-Posting (CP). GSP dan CP memiliki kelemahan dan kelebihan masing-masing. Dari segi kemudahan implementasi dan biaya komputasi, GSP lebih unggul dibandingkan CP. Sedangkan, dari segi efisiensi Rencana Penyelesaian yang dihasilkan, CP pada umumnya lebih unggul dibanding GSP. (lfirmansya, 2012)

Contoh Planning: Dalam dunia manufaktur dan robotik. Software Optimum – AIV adalah suatu planner yang digunakan oleh European Space Agency untuk perakitan pesawat terbang. Selain itu juga penyelesaian permainan Hanoi Tower merupakan salah satu contoh Planning.

4.     Learning

Learning atau pembelajaran merupakan teknik pemecahan masalah secara otomatis dengan menemukan atuan yang diharapkan bisa berlaku umum untuk data-data yang belum pernah kita ketahui. Atau lebih sederhananya, teknik learning memungkinkan komputer mampu belajar sendiri hanya dengan diberi pengetahuan tertentu. (Suyanto, 2014)

Contoh Learning: Digunakan dalam bidang transportasi. Software ALVINN digunakan pada sebuah mobil tanpa dikemudikan manusia dengan menggunakan JST yg dilatih dengan berbagai gambar kondisi jalan ray yang ditangkap kamera pada mobil. Contoh lainnya diterapkan dalam mesin penerjemah.

Penerapan Metode A* dalam Menentukan Rute Tercepat

 

 

Gambar tersebut merupakan kondisi jalan raya dimana terdapat 8 simpul yang menyatakan persimpangan, dan busur yang memiliki 2 atribut (angka pertama merupakan jarak sebenarnya dalam km, dan angka kedua merupakan kecepatan maksimum dengan satuan km/jam). Disebutkan bahwa mobi pemadam kebakaran bermaksud memadamkan api di persimpangan G dari titik awal S dengan kecepatan maksimum 90 km/jam. Maka carilah rute tercepat untuk tiba di titik G dengan metode A*.

 

Notasi yang dipakai oleh Algoritma A* adalah sebagai berikut:

f(n) = g(n) + h(n)

f(n) = biaya estimasi terendah

g(n) = biaya dari simpul awal ke simpul n

h(n) = perkiraan biaya dari simpul n ke simpul akhir.

 

Tabel Heuristik

Fungsi heuristik yang digunakan adalah jarak garis lurus yang dapat dihitung menggunakan rumus:

Dengan keterangan:

n = simpul awal                                g = simpul akhir

y_g = titik y simpul akhir               y_n = titik y simpul awal

x_g = titik x simpul akhir               x_n = titik x simpul awal

   

Maka, hasil yang didapat dari perhitungan adalah sebagai berikut:

n	S	A	B	C	D	E	F	G
h(n)	18	15.5	15	15.5	5	3	5	0

 

Langkah Pertama

Karena di OPEN hanya terdapat satu simpul yaitu S, maka S terpilih sebagai BestNode (simpul terbaik), dan pindah ke CLOSED. Kemudian semua suksesor S, yaitu: A, B, C dimasukkan ke OPEN.

OPEN	CLOSED
A, B, C	S

 

 

 

Langkah Kedua

f(A) = g(S)+g(S ke A)+h(A)=0+5+15,5=20,5

f(B) = g(S)+g(S ke B)+h(B)=0+10+15=25

f(C) = g(S)+g(S ke C)+h(C)=0+5+15,5=20,5

A dan C dengan biaya terkecil (20,5) terpilih sebagai BestNode dan pindah ke CLOSED. Pertama-tama suksesor A yaitu B dan D dicek apakah sudah ada di OPEN atau belum, jika belum, maka dapat masuk ke OPEN, jika sudah, maka perlu di cek apakah parent harus diganti atau tidak. Selanjutnya suksesor C yaitu B dan F juga di cek dengan cara yang sama. Ternyata biaya S ke B melalui A dan C (5+4=9) lebih kecil dibanding biaya S ke B secara langsung (10). Maka dari itu nilai g dan f pada B pun harus diperbarui.

  

OPEN	CLOSED
A, B, D, F	S, A, C

 
 

 

Langkah Ketiga

f(D) = g(S)+g(S ke D)+h(D)=0+(5+14)+5=24

f(B) = g(S)+g(S ke B)+h(B)=0+(5+4)+15=24

f(F) = g(S)+g(S ke F)+h(F)=0+(5+12)+5=22

F dengan biaya terkecil (22) terpilih sebagai BestNode dan pindah ke CLOSED. Suksesor F yaitu E dan G dicek apakah sudah ada di OPEN atau belum, jika belum maka masukkan ke OPEN.

OPEN	CLOSED
A, B, D, E, G	S, A, C, F

 

 

Selanjutnya, karena G memiliki nilai terkecil (22), maka G terpilih sebagai BestNode. Karena BestNode sama dengan goal, berarti solusi sudah ditemukan. Penelurusan balik menghasilkan rute S-C-F-G dengan total jarak 22 kilometer. Rute ini merupakan rute terpendek dari graf tersebut.

 

Sumber:

Dalem, I. B. (2018). PENERAPAN ALGORITMA A* (STAR) MENGGUNAKAN GRAPH UNTUK. JURNAL RESISTOR, Vol. 1(No. 1), 41-47.

Huda, F. A. (2017). Artificial Intelligence – Reasoning. Retrieved November 10, 2020, from http://fatkhan.web.id/artificial-intelligence-reasoning/

lfirmansya. (2012). Apa itu Planning ? Retrieved November 10, 2020, from http://bursacode.blogspot.com/2012/01/apa-itu-planning.html

Suyanto. (2014). Artificial Intelligence : Searching, Reasoning, Planning, Learning. Bandung: Informatika.

Yusrizal. (2011). ANALISIS TEKNIK SEARCHING DALAM ARTIFICIAL INTELLIGENCE. Retrieved November 10, 2020, from https://lintasgenre.wordpress.com/2011/04/19/analisa-teknik-searching-dalam-artificial-intelligence/