Penerapan Pohon Pelacakan Dalam Mencari Lintasan Yang Dapat Dilalui Oleh Seekor Semut Pada Bidang Kartesian

Latar Belakang Pemilihan Judul

Pohon pelacakan adalah suatu pohon yang dapat diterapkan untuk menyelesaikan persoalan pada bidang ilmu Artificial Intelligence (AI), dimana akar dari pohon berupa keadaan awal dari permasalahan dan cabang (dahan) berupa keadaan-keadaan yang mungkin terjadi dari keadaan sebelumnya serta daun merupakan keadaan akhir dari permasalahan tersebut. Keadaan-keadaan akhir tersebut dapat merupakan solusi dari permasalahan ataupun mungkin saja tidak ada yang dapat dijadikan solusi dari permasalahan.

Salah satu contoh persoalan AI yang memerlukan penerapan pohon pelacakan adalah dalam mencari lintasan yang dapat dilalui oleh seekor semut pada bidang Kartesian. Persoalan ini dapat didekripsikan sebagai berikut, diketahui seekor semut akan bergerak dari titik pusat (0,0) ke titik A(m,n). Semut tersebut hanya boleh membelok pada titik-titik grid dan selalu melangkah sejajar dengan sumbu-x atau sumbu-y. Semut tersebut tidak boleh melintasi lintasan yang telah pernah dilaluinya dan tidak boleh melintasi titik yang telah pernah dilaluinya. Setelah itu, disediakan sederetan ketentuan yang membatasi pergerakan semut tersebut. Pertanyaannya adalah bagaimana bentuk lintasan-lintasan yang dapat dilalui oleh semut tersebut dengan menggunakan ketentuan-ketentuan yang telah ditetapkan di atas.

Penulis merasa bahwa persoalan ini sangat menantang dan sangat menarik untuk dipelajari. Oleh karena itu, penulis mengambil tugas akhir dengan judul “Penerapan Pohon Pelacakan dalam Mencari Lintasan yang Dapat Dilalui oleh Seekor Semut pada Bidang Kartesian”.

1.2       Deskripsi Sistem yang Diusulkan

           

            Pencarian lintasan yang dapat dilalui oleh seekor semut pada bidang kartesian dapat dilakukan dengan bantuan pohon pelacakan. Deskripsi dari permasalahan ini adalah sebagai berikut, diketahui seekor semut akan bergerak dari suatu titik (x,y) ke titik A(m,n). Semut hanya boleh membelok atau melintas pada titik-titik grid dan selalu melangkah sejajar dengan sumbu-x atau sumbu-y. Semut tidak boleh melintasi lintasan yang telah pernah dilaluinya atau melintasi titik yang telah pernah dilaluinya. Setelah itu, disediakan sederetan ketentuan yang membatasi pergerakan semut tersebut. Ketentuan yang membatasi adalah batas pergerakan maksimum semut yang diperbolehkan, posisi-posisi rintangan dimana semut tidak boleh melintas, posisi-posisi dimana semut harus melintas dan semut hanya melintasi kuadran yang diperbolehkan untuk melintas.

            Solusi dari permasalahan ini bisa lebih dari satu dan perangkat lunak dituntut untuk mampu menampilkan semua lintasan yang dapat dilalui semut dari posisi awal ke posisi tujuan dengan mematuhi ketentuan-ketentuan yang berlaku. Karena solusi yang didapatkan bisa lebih dari satu, maka metode pencarian yang digunakan untuk mencari solusi permasalahan ini adalah metode pencarian melebar pertama (breadth-first search / BFS).

            Dimulai dari posisi awal sebagai node akar, selanjutnya metode BFS mencari solusi dengan mengembangkan node akar ke level-level berikutnya, semua pergerakan yang mungkin, tidak melanggar ketentuan dan menghasilkan kondisi baru dikembangkan semaksimal mungkin. Pencarian berakhir apabila tidak ada lagi node atau kondisi baru yang dapat dikembangkan. Semua node yang merupakan posisi tujuan merupakan solusi. Adapun pergerakan semut yang diperbolehkan adalah:

1. Bergerak ke kanan (x + 1).
2. Bergerak ke kiri (x – 1).
3. Bergerak ke atas (y + 1).
4. Bergerak ke bawah (y – 1).
5. Semua pergerakan semut di atas legal apabila mematuhi ketentuan-ketentuan sebagai berikut:
1. Tidak melintasi posisi titik rintangan.
2. Tidak melintasi posisi titik yang sudah pernah dilalui sebelumnya.
3. Tidak melebihi batas pergerakan maksimum semut (x atau y).
4. Tidak melintasi kuadran yang tidak diperbolehkan untuk melintas. Kuadran yang dimaksud adalah kuadran I (dimana x bernilai positif dan y bernilai positif), kuadran II (dimana x bernilai negatif dan y bernilai positif), kuadran III (dimana x bernilai negatif dan y bernilai negatif) dan kuadran IV (dimana x bernilai positif dan y bernilai positif).

Contoh struktur pohon pelacakan yang dikembangkan berdasarkan metode pencarian BFS dapat dilihat pada gambar 3.1.

Gambar 3.1 Contoh struktur pohon pelacakan dengan metode BFS

Dari solusi-solusi yang ditemukan, terdapat solusi yang optimum. Dalam implementasinya, solusi optimum merupakan langkah penyelesaian terpendek (shortest path) yang ditemukan dengan menggunakan pohon pelacakan. Dalam kasus pergerakan semut, solusi paling optimum (pergerakan terpendek tanpa halangan) dapat  ditentukan kriterianya. Simak contoh berikut, apabila posisi awal semut adalah (x₁, y₁) dan posisi tujuan semut adalah (x₂, y₂) maka solusi paling optimum (langkah terpendek) menuju posisi tujuan dapat dihitung dengan rumus: (abs(x₂ – x₁), abs(y₂ – y₁)). Ini artinya, pergerakan sepanjang sumbu x (horizontal) adalah sebesar abs(x₂ – x₁) langkah dan pergerakan sepanjang sumbu y (vertikal) adalah sebesar abs(y₂ – y₁). Misalkan posisi awal semut adalah (-1, -2) dan posisi tujuan semut adalah (4, 5), maka solusi yang paling optimum adalah solusi yang memiliki kriteria sebagai berikut:

1.      Pergerakan sepanjang sumbu x (horizontal) adalah abs(4 - (- 1)) = 5 langkah.

2.      Pergerakan sepanjang sumbu y (vertikal) adalah abs(5 - (- 2)) = 7 langkah.

 

Kriteria solusi paling optimum dapat dilihat pada gambar 3.2 berikut.

 

Namun apabila, terdapat halangan pada pergerakan semut (yang menyebabkan semua solusi paling optimum tidak dapat dilewati, perhatikan gambar 3.3), maka kriteria untuk solusi optimum tersebut tidak berlaku. Oleh karena itu, solusi optimum adalah solusi terpendek yang ditemukan oleh pohon pelacakan dan tidak ada kriteria yang dapat merumuskan bahwa suatu solusi merupakan solusi yang paling optimum.

Di dalam perangkat lunak, untuk mencari atau mendapatkan solusi yang paling optimum, maka pergerakan maksimum semut dibatasi dengan rumus di atas dan tidak terdapat halangan yang membatasi semua pergerakan semut yang ada.

1.4       Screenshot Sistem

Form tampilan awal (splash) Form ini akan tampil ketika program dijalankan. Form ini berisi nama perangkat lunak, nama kampus dan nama penyusun tugas akhir

Form cari

Form ini berfungsi untuk mencari dan menampilkan banyak solusi yang telah ditemukan. Apabila user ingin membatalkan proses pencarian, user dapat menekan tombol ‘Batal’.

Form input :

Form ini berfungsi untuk memasukkan input ke dalam perangkat lunak. Input dapat disimpan atau dibuka kembali apabila diperlukan.

    Form solusi

Form ini berfungsi untuk menampilkan solusi-solusi yang telah ditemukan

 

Tujuan dan Manfaat

            Tujuan penyusunan tugas akhir (skripsi) ini adalah untuk merancang suatu perangkat lunak yang dapat menyelesaikan persoalan pencarian lintasan yang dapat dilalui oleh seekor semut pada bidang Kartesian.

Manfaat dari penyusunan proposal ini, yaitu :

1.      Untuk membantu pemahaman mata kuliah Artificial Intelligence, terutama mengenai penerapan pohon pelacakan.

2.      Perangkat lunak dapat digunakan sebagai fasilitas pendukung dalam proses belajar mengajar.