ANALISIS KINERJA BACKWARD PLANNING MENGGUNAKAN ITERATIVE DEEPENING A* (IDA*) DENGAN STOCHASTIC NODE CACHING (SNC) PADA STUDI KASUS DUNIA BALOK
| Main Author: | Ali Faiz |
|---|---|
| Format: | Bachelors |
| Terbitan: |
Universitas Telkom
, 2012
|
| Subjects: | |
| Online Access: |
https://openlibrary.telkomuniversity.ac.id/pustaka/95077/analisis-kinerja-backward-planning-menggunakan-iterative-deepening-a-ida-dengan-stochastic-node-caching-snc-pada-studi-kasus-dunia-balok.html |
Daftar Isi:
- 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 IDA*SNC yang menjanjikan pengurangan ekspansi node terhadap IDA*.<br><br>Dalam tugas akhir ini algoritma IDA* dan IDA*SNC dengan menggunakan heuristic additive sebagai biaya estimasi digunakan dalam Backward Planning untuk menyelesaikan permasalahan planning pada studi kasus dunia balok.<br><br>Dari penelitian tugas akhir ini terbukti bahwa implementasi algoritma IDA* dan IDA*SNC dalam strategi Backward Planning mampu menyelesaikan segala permasalahan yang ada pada dunia balok. Penggunaan Algoritma IDA*SNC 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*, IDA*SNC, 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 IDA*SNC that in principle have a vision of decreasing the node expansion compared to IDA* Algorithm.<br><br>In this final project, IDA* and IDA*SNC 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.<br><br>From this final project research, it is proved that implementing IDA* and IDA*SNC Algorithms in the Backward Planning strategy can solve any problems in the Blocks World domain. The use of IDA*SNC Algorithm proved to reduce node expansion processes towards IDA* Algorithm despite the insignificancy. The solutions obtained from algorithms IDA* and IDA*SNC 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.