ABSTRAKSI: Salah satu teknik problem solving dalam Artificial Intelligence adalah planning. Planning adalah proses pemilihan aksi-aksi yang dapat digunakan untuk mengubah initial state menjadi goal state. Dalam menyelesaikan masalah planning, algoritma searching dapat digunakan. Simplified Memory-bounded A* (SMA) adalah salah satu algoritma searching yang menjanjikan solusi yang optimal jika memori yang tersedia setidaknya sebesar jumlah node pada jalur solusi optimal. Heuristic additive digunakan sebagai biaya perkiraan agar algoritma ini dapat diimplementasikan ke dalam planning. Ada dua strategi dalam Planning, yaitu Forward Planning dan Backward Planning. Pada Forward Planning, pencarian jalur solusi akan dilakukan dari initial state menuju goal state, sementara pada Backward Planning pencarian jalur solusi akan dilakukan terbalik dari goal state menuju initial state. Planning sebagai heuristic search adalah cara yang menggabungkan heuristic search dengan planning untuk menemukan jalur solusi.
Dalam tugas akhir ini algoritma SMA dengan menggunakan heuristic additive sebagai biaya estimasi digunakan untuk menyelesaikan permasalahan planning pada studi kasus dunia balok. Pembatasan memori pada algoritma ini aka disimulasikan dalam array of node. Sistem ini akan menampilkan output berupa aksi-aksi yang dilakukan oleh sistem untuk mencapai goal state, menampilkan jumlah aksi yang dilakukan, menghitung jumlah iterasi yang diperlukan, serta menampilkan waktu proses yang dibutuhkan sistem untuk menyelesaikan problem.
Dari penelitian tugas akhir ini terbukti bahwa implementasi algoritma SMA* dalam strategi Forward Planning dan Backward Planning mampu menyelesaikan segala permasalahan yang ada pada dunia balok selama ukuran memori yang tersedia setidaknya sebesar jumlah node pada jalur solusi optimal. Untuk permasalahan dengan sejumlah besar kemungkinan aksi pada initial state dan sejumlah kecil kemungkinan aksi dari goal state, Backward Planning terbukti lebih baik dibandingkan Forward Planning karena dapat menemukan solusi lebih cepat. Solusi yang didapat dari algoritma ini sudah optimal dibandingkan dengan solusi yang dihasilkan algoritma Graphplan.
Kata Kunci : SMA*, heuristic additive, artificial intelligence, planning, Forward Planning, Backward Planning, dunia balok, goal state, initial state, Graphplan.ABSTRACT: One of the problems solving technique in Artificial Intelligence is planning. Planning is a selection process of a sequence of action that can be used to change initial state into goal state. In solving planning problem, searching algorithm can be used. Simplified Memory-bounded A* is one of a searching algorithm which is guarantee to return an optimal solution if provided memory is at least as large as the number of nodes on the optimal solution path. Heuristic additive is used as estimate cost for this algorithm so it can be implemented into the planning. There are two methods in planning, Forward Planning and Backward Planning. In forward planning, the solution path search will be done from initial state to goal state, while in backward planning it will be done in reverse, from goal state to initial state. Planning as heuristic search is a method that implement heuristic search in planning.
In this final project, SMA* algorithm with heuristic additive as estimate cost is used to solve planning problem for case study blocks-world. Memory limitation on this algorithm will be simulated in an array of nodes. This system will show steps which has chosen by the system to reach goal state, figure out some acts that have been done, count the needed iteration, and shows timing process that is needed by system to finish the problem.
The result of this final project has proved that the implementation of SMA* in Forward Planning and Backward Planning can solve the problem that exist in the blocks-world. For problem with a large number of possible action from initial state and a small number of possible action from goal state, Backward Planning is better because it can found the solution path faster than Forward Planning. The results of this algorithm are optimal compared with Graphplan Algorithm.Keyword: SMA*, heuristic additive, artificial intelligence, planning, Forward Planning, Backward Planning, blocks-world, goal state, initial state, Graphplan.