ANALISIS KINERJA BACKWARD PLANNING MENGGUNAKAN ITERATIVE DEEPENING A* (IDA*) DENGAN STOCHASTIC NODE CACHING (SNC) PADA STUDI KASUS DUNIA BALOK

Ali Faiz

Informasi Umum

Kode

113060048

Klasifikasi

005.1 - Computer programming

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Informatika Teori Dan Pemrograman

Dilihat

8 kali

Informasi Lainnya

Abstraksi

ABSTRAKSI: Salah satu teknik problem solving dalam Artificial Intelligence adalah planning. Dalam menyelesaikan masalah planning, algoritma searching dapat digunakan. Iterative Deepening A* (IDA) adalah salah satu algoritma searching yang menjanjikan solusi yang complete dan optimal. Pada kenyataannya Algoritma IDA memerlukan waktu pemrosesan yang lama akibat dari pengunjungan node yang sama berulang kali. Untuk itu disini juga akan dibahas sebuah Algoritma pengembangan dari IDA* yaitu IDASNC yang menjanjikan pengurangan ekspansi node terhadap IDA. Dalam tugas akhir ini algoritma IDA* dan IDASNC dengan menggunakan heuristic additive sebagai biaya estimasi digunakan dalam Backward Planning untuk menyelesaikan permasalahan planning pada studi kasus dunia balok. Dari penelitian tugas akhir ini terbukti bahwa implementasi algoritma IDA dan IDASNC dalam strategi Backward Planning mampu menyelesaikan segala permasalahan yang ada pada dunia balok. Penggunaan Algoritma IDASNC terbukti dapat mengurangi proses ekspansi node terhadap Algoritma IDA* walaupun tidak secara signifikan. Solusi yang didapat dari algoritma ini, begitu juga dengan Algoritma IDA* juga terbukti selalu optimal saat dibandingkan dengan solusi yang dihasilkan algoritma Graphplan.Kata Kunci : IDA*, IDASNC, additive heuristic, artificial intelligence, planning, Backward Planning, dunia balok, ekspansi node, goal state, initial state, Graphplan.ABSTRACT: One of Artificial Intelligence problem solving technique is known as planning. In solving problems of planning, search algorithms can be used. Iterative Deepening A (IDA) is one of the search algorithms that promises a complete and optimal solution. Unfortunately, IDA Algorithm needs a longer processing time because of nodes-revisit problems that occurs in the Algorithm. Seeing that, here we will propose one of IDA* Algorithm‟s expansion known as IDASNC that in principle have a vision of decreasing the node expansion compared to IDA Algorithm. In this final project, IDA* and IDASNC Algorithms in Backward Planning with the use of additive heuristic as a cost-estimate to be used to solve planning problems in the Blocks World domain. From this final project research, it is proved that implementing IDA and IDASNC Algorithms in the Backward Planning strategy can solve any problems in the Blocks World domain. The use of IDASNC Algorithm proved to reduce node expansion processes towards IDA* Algorithm despite the insignificancy. The solutions obtained from algorithms IDA* and IDASNC are optimal when compared to the solutions obtained using Graphplan.Keyword: IDA, IDA*SNC, additive heuristic, artificial intelligence, planning, Backward Planning, blocks world, node expansion, goal state, initial state, Graphplan.