Pengenalan Intelegensi Buatan

Perkuliahan minggu ke-1

1.1 Pengertian Kecerdasan Buatan

Kecerdasan Buatan adalah salah satu cabang Ilmu pengetahuan berhubungan dengan pemanfaatan mesin untuk memecahkan persoalan yang rumit dengan cara yang lebih manusiawi. Hal Ini biasanya dilakukan dengan mengikuti/mencontoh karakteristik dan analogi berpikir dari kecerdasan/Inteligensia manusia, dan menerapkannya sebagai algoritma yang dikenal oleh komputer. Dengan suatu pendekatan yang kurang lebih fleksibel dan efisien dapat diambil tergantung dari keperluan, yang mempengaruhi bagaimana wujud dari perilaku kecerdasan buatan. Pengertian lain dari kecerdasan buatan adalah bagian ilmu komputer yang membuat agar mesin komputer dapat melakukan pekerjaan seperti dan sebaik yang dilakukan manusia. Pada awal diciptakannya, komputer hanya difungsikan sebagai alat hitung saja. Namun seiring dengan perkembangan jaman, maka peran komputer semakin mendominasi kehidupan manusia. Komputer tidak lagi hanya digunakan sebagai alat hitung, lebih dari itu, komputer diharapkan untuk dapat diberdayakan untuk mengerjakan segala sesuatu yang bisa dikerjakan oleh manusia.

1.2 Kecerdasan Buatan dan Kecerdasan Alami

A. KECERDASAN BUATAN

Lingkup utama kecerdasan buatan:

· Sustem pakar. Komputer digunakan sebagai saran untuk menyimpan pengetahuan para pakar. Dengan demikian komputer akan memiliki keahlian untuk menyelesaikan masalah dengan meniru keahlian yang dimiliki para pakar

· Pengolahan bahasa alami. Dengan pengolahan bahasa alami ini diharapkan user mampu berkomunikasi dengan komputer dengan menggunakan bahasa sehari-hari.

· Pengenalan ucapan. Melalui pengenalan ucapan diharapkan manusia mampu berkomunikasi dengan komputer dengan menggunakan suara.

· Robotika dan Sistem sensor

· Computer vision, mencoba untuk dapat mengintrepetasikan gambar atau objek-objek tampak melalui komputer

· Intelligent Computer aid Instruction. Komputer dapat digunakan sebagai tutor yang dapat melatih dan mengajar

Keuntungan Kecerdasan Buatan :

· Kecerdasan buatan lebih bersifat permanen. Kecerdasan alami akan cepat mengalami perubahan. Hal ini dimungkinkan karena sifat manusia yang pelupa. Kecerdasan buatan tidak akan berubah sepanjang sistem komputer dan program tidak mengubahnya.

· Kecerdasan buatan lebih mudah diduplikasi dan disebarkan. Mentransfer pengetahuan manusia dari satu orang ke orang lain butuh proses dan waktu lama. Disamping itu suatu keahlian tidak akan pernah bisa diduplikasi secara lengkap. Sedangkan jika pengetahuan terletak pada suatu sistem komputer, pengetahuan tersebuat dapat ditransfer atau disalin dengan mudah dan cepat dari satu komputer ke komputer lain

· Kecerdasan buatan lebih murah dibanding dengan kecerdasan alami. Menyediakan layanan komputer akan lebih mudah dan lebih murah dibanding dengan harus mendatangkan seseorang untuk mengerjakan sejumlah pekerjaan dalam jangka waktu yang sangat lama.

· Kecerdasan buatan bersifat konsisten. Hal ini disebabkan karena kecerdasan busatan adalah bagian dari teknologi komputer. Sedangkan kecerdasan alami senantiasa berubah-ubah.

· Kecerdasan buatan dapat didokumentasikan. Keputusan yang dibuat komputer dapat didokumentasikan dengan mudah dengan melacak setiap aktivitas dari sistem tersebut. Kecerdasan alami sangat sulit untuk direproduksi.

· Kecerdasan buatan dapat mengerjakan pekerjaan lebih cepat dibanding dengan kecerdasan alami

· Kecerdasan buatan dapat mengerjakan pekerjaan lebih baik dibanding dengan kecerdasan alami.

B. KECERDASAN ALAMI

Kecerdasan Alami adalah sifat pikiran yang mencakup sejumlah kemampuan, seperti kemampuan menalar, merencanakan, memecahkan masalah, berpikir abstrak, memahami gagasan, menggunakan bahasa, dan belajar yang terbentuk secara alami atau biasa disebut bakat. Kecerdasan alami memungkinkan orang untuk menggunakan pengalaman secara langsung.

Keuntungan kecerdasan alami:

· Kreatif. Kemampuan untuk menambah ataupun memenuhi pengetahuan itu sangat melekat pada jiwa manusia. Pada kecerdasan buatan, untuk menambah pengetahuan harus dilakukan melalui sistem yang dibangun

· Kecerdasan alami memungkinkan orang untuk menggunakan pengalaman secara langsung. Sedangkan pada kecerdasan buatan harus bekerja dengan input-input simbolik

· Pemikiran manusia dapat digunakan secara luas, sedangkan kecerdasan buatan sangat terbatas.

1.3 Komputasi Intelegensi Buatan dan Komputasi Konvensional

Aritifficial Intelligence merupakan software yang memungkinkan komputer digital bisa meniru beberapa fungsi otak manusia yang terbatas. walaupun hardware artifficial intelligence khusus dapat dibuat, tetapi ternyata hampir semua software AI bisa dilaksanakan pada semua jenis komputer, mulai dari komputer mikro sampai komputer besar.

Program AI dapat ditulis dalam semua bahasa komputer dan telah ditulis dalam bahasa Assembler, BASIC, Fortran,Pascal,C dan sebaliknya. Namun, bahasa pemrograman khusus aplikasi AI mulai dikembangkan pula.Dua bahasa pemrograman AI yang sangat populer adalah LISP dan Prolog.

KOMPUTASI KONVENSIONAL

Teknik pembuatan Program AI sangat berbeda dengan teknik pemrograman menggunakan bahasa konvensional. Dalam software konvensional,kita memerintah komputer bagaimana menyelesaikan suatu masalah. Sebaliknya, dalam AI kita tidak memerintah komputer untuk menyelesaikan masalah, tetapi memeberitahu komputer tentang adanya masalah. Dalam komputasi konvensional, kita memberikan data kepada komputer dan program yang telah kita susun terlebih dahulu dengan langkah demi langkah memspesifikasikan cara data digunakan sampai komputer bisa memberikan solusi. Dalam komputasi AI, komputer mendapatkan pengetahuan tentang suatu wilayah subyek masalah tertentu dengan ditambah kemampuan inferensi. kita tidak memerintahkan komputer untukmemecahkan masalah tetapi sebaliknya komputer dan software-nya yang menentukan metode untuk mencapai suatu solusi.
program komputer konvensional didasarkan pada suatu algoritma yang disusun dengan jelas, rinci, serta langkah sampai pada hasil yang sudah ditentukan sebelumnya. program bisa berupa rumus matematika atau prosedur berurutan yang tersusun dengan jelas yang mengarah ke suatu solusi. algoritma tersebut kemudian dipindahkan ke dalam program komputer. daftar instruksi disusun berurutan untuk mengarahkan komputer agar bisa sampai pada hasil yang didinginkan. selanjutnya, algoritma bisa digunakan untuk mengolah data bilangan, huruf, atau kata lainnya.

KOMPUTASI AI

Sebaliknya, software AI tidak didasarkan pada algoritma, tetapi didadasarkan pada representasi dan manipulasi simbol. Didalam AI, sebuah simbol bisa merupakan huruf, kata, atau bilangan yang digunakan untuk menggambarkan objek, proses, dan hubungannya. sumber bisa merupakan cetakan atau elektronik. objek bisa berupa orang, benda, ide, pikiran, peristiwa, atau pernyataan suatu fakta. Dengan menggunakan simbol, komputer bisa menciptakan suatu basis pengetahuan yang menyatakan fakta, pikiran, dan hubungannya satu sama lain. berbagai proses digunakan unutk memanipulasi simbol agar mampu memecahkan masalah. Pengolahannya bersifat kuantitatif, bukan kulaitatif seperti halnya komputasi yang didasarkan pada algoritma.

1.4 Sejarah Intelegensi Buatan

Perkembangan dan Aplikasinya

· Jaman “batu” (1943-1956)

· Awal kerja JST dan logika

· Teori Logika (Alan Newell and Herbert Simon)

· Kelahiran AI: Dartmouth workshop - summer 1956

· John McCarthy’s memberi nama bidang: artificial intelligence

· Awal antusias, harapan besar (1952-1969)

· McCarthy (1958)

- mendefinisikan Lisp

- menemukan time-sharing

- Advice Taker

· Pembelajaran tanpa pengetahuan

· Pemodelan JST

· Pembelajaran Evolusioner

· Samuel’s checkers player: pembelajaran

· Metode resolusi Robinson.

· Minsky: the microworlds (e.g. the block’s world).

· Banyak demonstrasi kecil ttg perilaku “intelligent”

· Prediksi over-optimistic Simon

· Masa Gelap (1966-1973)

· AI tidak mengalami perkembangan: ledakan perkembangan combinatorial

· Fakta bahwa suatu program bisa mendapatkan suatu solusi secara prinsip tidak berarti bahwa program memuat beberapa mekanisme yang dibutuhkan untuk mendapatkannya secara praktis.

· Kegagalan dari pendekatan terjemahan bahasa alami berbasis pada grammars sederhana dan kamus kata.

· Penterjemahan kembali yang populer English->Russian->English

· Penemuan untuk pemrosesan bahasa natural dihentikan.

· Kegagalan perceptron untuk belajar dari fungsi sederhana sebagaimana disjunctive/eksclusive OR.

· Penelitian pada JST dihentikan.

· Realisasi dari kesukaran dalam proses learning dan keterbatasan dari metode yang dieksplorasi

· Konsep pembelajaran simbolik (Winston’s influential thesis, 1972)

· Renaissance (1969-1979)

· Perubahan pada paradigma penyelesaian:

· Dari penyelesaian masalah berbasis “search-based” menjadi penyelesaian masalah berbasis pengetahuan.

· Sistem pakar pertama

· Dendral: menginferensi struktur molecular dari informasi yang disediakan oleh spektrometer massa.

· Mycin: diagnoses blood infections

· Prospector: merekomendasikan eksplorasi pengeboran pada lokasi geologi yang menyediakan suatu deposit mineral molybdenum.

· Era Industrial
(1980-sekarang)

· Sukses pertama Sistem Pakar secara komersial.The.

· Many AI companies.

· Eksplorasi dari strategi pembelajarqan yqang bermacam-macam (Explanation-based learning, Case-based Reasoning, Genetic algorithms, Neural networks, etc.)

· Kembalinya neural networks
(1986-sekarang)

· Penggalian kembali algoritma learning back propagation untuk neural networks yang pertama dikenalkan dalam tahun 1969 oleh Bryson and Ho.

· Banyak aplikasi sukses dari Neural Networks.

· Kehilangan respek terhadap sulitnya membangun sistem pakar (macetnya knowledge acquisition).

· Kematangan
(1987-sekarang)

· Perubahan dalam cakupan dan metodologi penelitian bidang Kecerdasan Buatan:

· Membangun di atas teori yang ada, bukan cuma mengusulkan teori baru;

· berbasis klaim pada theorema dan eksperimen, bukan pada intuisi;

· menunjukkan relevansi ke aplikasi nyata, bukan pada contoh “mainan”.

· Agent Cerdas (1995-sekarang)

· Realisasi yang pada mulanya dipisahkan dalam sub dari Kecerdasan Buatan (speech recognition, problem solving and planning, robotics, computer vision, machine learning, knowledge representation, etc.) perlu direorganisasi bilamana hasil-hasilnya diikat bersama-sama kedalam suatu desain agent tunggal.

· Suatu proses reintegrasi dari sub-area yang berbeda dari KB untuk membentuk “whole agent”:

· “agent perspective” of AI

· agent architectures (e.g. SOAR, Disciple);

· multi-agent systems;

· agent untuk aplikasi tipe-tipe yang berbeda, web agents.

1.5 Lingkup Intelegensi Buatan

Makin pesatnya perkembangan teknologi menyebabkan adanya perkembangan dan perluasan lingkup yang membutuhkan kehadiran kecerdasan buatan. Karakteristik ‘cerdas’ sudah mulai dibutuhkan di berbagai disiplin ilmu dan teknologi. Kecerdasan buatan tidak hanya dominan di bidang ilmu komputer saja, namun juga sudah merambah di berbagai disiplin ilmu yang lain.

Irisan antara psikologi dan kecerdasan buatan meahirkan sebuah area yang dikenal dengan nama cognition dan psycolinguistic. Irisan antara teknik elektro dengan kecerdasan buatan melahirkan berbagai ilmu seperti, pengolahan citra, teori kendali, pengenalan pola, dan robotika.

Dewasa ini, kecerdasan buatan juga memberikan konstribusi yang cukup besar di bidang manajemen. Adanya sistem pendukung keputusan dan sistem informasi manajemen juga tidak terlepas dari andil kecerdasan buatan.

Adanya irisan penggunaan kecerdasan buatan di berbagai disiplin ilmu tersebut menyebabkan cukup rumitnya untuk mengklasifikasikan kecerdasan buatan menurut disiplin ilmu yang menggunakannya. Untuk memudahkan hal tersebut, maka pengklasifikasian lingkungan kecerdasan buatan didasarkan pada output yang diberikan yaitu pada aplikasi komersial (meskipun sebenarnya kecerdasan buatan itu sendiri bukan merupakan medan komersial).

Lingkup utama kecerdasan buatan :

1. Pengolahan bahasa alami (natural language processing) : Diman user dapat berkomunikasi dengan komputer menggunakan bahasa sehari-hari, misal bahasa Inggris, bahasa Indonesia, bahasa Jawa, dan lain-lain, contoh :

a. Pengguna sistem dapat memberikan perintah dengan bahasa sehari-hari, misalnya, untuk menghapus semua file, pengguna cukup memberikan perintah ”komputer, tolong hapus semua file !” maka sistem akan mentranslasikan perintah bahasa alami tersebut menjadi perintah bahasa formal yang dipahami oleh komputer, yaitu”delete *.* <ENTER>”.

b. Translator bahasa Inggris ke bahasa Indonesia begitu juga sebaliknya dan lain-lain, tetapi sistem ini tidak hanya sekedar kamus yang menerjemahkan kata per kata, tetapi juga mentranslasikan sintaks dari bahasa asal ke bahasa tujuan

c. Text summarization : Suatu sistem yang dapat membuat ringkasan hal-hal penting dari suatu wacana yang diberikan.

2. Sistem pakar (expert system) : Komputer sebagai sarana untuk menyimpan pengetahuan para pakar sehingga komputer memiliki keahlian menyelesaikan permasalahan dengan meniru keahlian yang dimiliki pakar.

3. Pengenalan ucapan (speech recognition): Manusia dapat berkomunikasi dengankomputer menggunakan suara. Contoh:

a. Memberikan instruksi ke komputer dengan suara.

b. Alat bantu membaca untuk tunanetra, mempunyai masukan berupa teks tercetak (misalnya buku) dan mempunyai keluaran berupa ucapan dari teks tercetak yang diberikan.

c. Konversi dari SMS (Short Message System) ke ucapan sehingga pesan SMS dapat didengar. Dengan demikian memungkinkan untuk mendengar pesan SMS sambil melakukan aktivitas yang menyulitkan untuk membacanya, seperti mengendarai mobil.

4. Robotika & sistem sensor

a. Sistem sensor pada mesin cuci yaitu menggunakan sensor optik, mengeluarkan cahaya ke air dan mengukur bagaimana cahaya tersebut sampai ke ujung lainnya. Makin kotor, maka sinar yang sampai makin redup. Sistem juga mampu menentukan jenis kotoran tersebut daki/minyak.Sistem juga bisa menentukan putaran yang tepat secara otomatis berdasarkan jenis dan banyaknya kotoran serta jumlah yang akan dicuci.

b. Robotika

5. Computer vision : Menginterpretasikan gambar atau objek-objek tampak melalui komputer.

6. Intelligent computer-aided instruction : Komputer dapat digunakan sebagai tutor yang dapat melatih dan mengajar. Contoh : Learn to speak English.

7. Game playing: Pada tahun 1997, Deep Blue mengalahkan Garry Kasparov, the World Chess Champion. Deep Blue chess machine menggunakan komputer IBM, dibuat tahun 1990-an oleh Hsu, Campbell, Tan, Hoane, Brody, Benjamin. Deep Blue mampu mengevaluasi 200 juta posisi bidak catur per detik.

1.6 Soft Computing

Soft Computing (SC), sebuah pendekatan inovatif untuk konstruksi sistem inteligen secara komputasional, telah mengundang banyak perhatian. Sekarang terbukti bahwa permasalahan dunia nyata yang komplek membutuhkan sistem inteligen yang mengkombinasikan pengetahuan, teknik, dan metodologi dari berbagai sumber. Sistem inteligen ini diharapkan memiliki keahlian seperti manusia dalam domain yang spesifik, beradaptasi sendiri dan belajar untuk melakukan yang lebih baik dalam mengubah lingkungan, dan menjelaskan bagaimana mereka membuat keputusan atau mengambil tindakan. Dalam menghadapi permasalahan komputasi dunia nyata, seringkali keberhasilan menggunakan beberapa teknik komputasi secara sinergetis lebih baik dari cara yang eklusif, berhasil dalam konstruksi sistem inteligen hybrid yang saling melengkapi. Inti dari desain sistem inteligen jenis ini adalah neuro-fuzzy computing: neural network yang mengenal pola-pola dan beradaptasi sendiri terhadap perubahan lingkungan; fuzzy inference system yang menggabungkan pengetahuan manusia dan membuat kesimpulan (inferencing) serta membuat keputusan. Integrasi dari dua pendekatan yang saling melengkapi ini, bersama-sama dengan teknik-teknik optimisasi derivative-free tertentu, menghasilkan disiplin baru yang disebut neuro-fuzzy dan soft computing.

Sebagai pendahuluan, kami akan menyajikan pandangan tentang pendekatan sistem inteligen yang relevan, sedikit membahas teorinya, dan membahas fitur-fitur neuro-fuzzy dan soft computing.

· Soft Computing Constituents and Conventional Artificial Intelligence

Soft computing adalah pendekatan yang muncul untuk komputasi yang paralel dengan kemampuan yang bagus dari pikiran manusia untuk beralasan dan belajar dalam lingkungan yang tidak menentu dan ketidaktepatan. (Lotfi A. Zadeh, 1992 [12])

Figure 1.1 Neural character recognizer dan kerja sama berbasis pengetahuan dalam merespon tiga karakter tulis tangan yang membentuk kata “dog.”

Tabel 1.1 Soft computing constituents (tiga item pertama) dan kecerdasan buatan konvensional

Metodologi	Kekuatan
Neural network	Belajar dan adaptasi
Fuzzy set theory	Representasi pengetahuan via aturan fuzzy if-then
Genetic algorithm and simulated annealing	Pencarian acak sistematis
Conventional AI	Manipulasi simbolik

Soft computing terdiri dari banyak paradigma komputasi, mencakup neural network, fuzzy set theory, approximate reasoning, dan metode derivative-free optimization seperti genetic algorithm dan simulated annealing. Masing-masing metodologi pokok ini memiliki kekuatannya, seperti yang diringkas pada tabel 1.1. Integrasi seamless dari bentuk-bentuk metodologi ini menjadi inti soft computing; sinergisme memungkinkan soft computing menggabungkan pengetahuan manusia secara efektif, berhubungan dengan ketidaktepatan dan ketidakpastian, dan belajar beradaptasi terhadap lingkungan yang tidak diketahui atau berubah-ubah menuju kinerja yang lebih baik. Untuk belajar dan adaptasi, soft computing membutuhkan komputasi ekstensif. Dalam pengertian ini, soft computing berbagi karakteristik yang sama sebagai kecerdasan komputasional.

Pada umumnya, soft computing tidak melakukan banyak manipulasi simbolik, maka kita dapat memandangnya sebagai disiplin baru yang melengkapi pendekatan kecerdasan buatan konvensional (AI), dan sebaliknya. Contohnya, Figure 1.1 mengilustrasikan situasi di mana neural character recognizer dan basis pengetahuan digunakan bersama-sama untuk menentukan arti dari kata yang ditulis tangan. Neural character recognizer menghasilkan dua jawaban yang mungkin “dog” dan “dag,” sejak karakter tengah bisa “o” atau “a.” Jika knowledge base menyediakan penggalan informasi ekstra yang mana kata itu dihubungkan dengan binatang, maka jawabannya “dog” dilakukan dengan tepat.

1.7 Definisi Masalah dan Ruang Masalah

MENDEFINISIKAN MASALAH SEBAGAI SUATU RUANG KEADAAN

Gb. Skema Sistem Yang Menggunakan Kecerdasan Buatan

Suatu sistem yang menggunakan konsep kecerdasan buatan akan memberikan output berupa solusi dari suatu masalah berdasarkan kumpulan pengetahuan yang ada.

Pada gambar diatas, input yang diberikan pada sistem kecerdasan buatan adalah berupa masalah. Sistem harus dilengkapi sekumpulan pengetahuan yang ditanamkan pada knowledge base (basis pengetahuan). Sistem juga harus memiliki Motor Inferensi agar mampu mengambil kesimpulan berdasarkan fakta atau pengetahuan. Output dari inferensi berupa solusi.

Secara umum ada 4 hal yang perlu diperhatikan untuk membangun Sistem Pakar atau Kecerdasan Buatan, diantaranya adalah;

Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup spesifikasi yang tepat mengenai keadaan awal dan solusi yang diharapkan.
Menganalisis masalah serta mencari beberapa teknik penyelesaian masalah yang sesuai.
Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut.
Memilih teknik penyelesaian masalah yang terbaik.

Pada materi ini, kita akan mengupas tuntas poin 1 terlebih dahulu.

PENGANTAR

Misalkan permasalahan yang dihadapi adalah permainan catur, maka harus ditentukan :

1. Posisi awal pada papan catur

Posisi awal setiap permainan catur selalu sama, yaitu semua bidak diletakkan di atas papan catur dalam 2 sisi, yaitu kubu putih dan kubu hitam.

2. Aturan – aturan untuk melakukan gerakan

Aturan – aturan ini sangat berguna untuk menentukan gerakan suatu bidak, yaitu melangkah dari satu keadaan ke keadaan lain. Misalkan untuk mempermudah menunjukkan posisi bidak, setiap kotak ditunjukkan dalam huruf (a,b,c,d,e,f,g,h) untuk arah horisontal dan angka (1,2,3,4,5,6,7,8) untuk arah vertikal. Suatu aturan untuk menggerakkan bidak dari posisi (e,2) ke (e,4) dapat ditunjukkan dengan aturan :

if bidak putih pada kotak(e,2),

  and kotak(e,3) kosong,

  and kotak(e,4) kosong

then gerakan bidak dari (e,2) ke (e,4)

3. Tujuan (goal)

Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya. Kemenangan ini ditandai dengan posisi raja yang sudah tidak dapat bergerak lagi.

Contoh tersebut menunjukkan representasi masalah dalam Ruang Keadaan (State Space), yaitu suatu ruang yang berisi semua keadaan yang mungkin.

Kita dapat memulai bermain catur dengan menempatkan diri pada keadaan awal, kemudian bergerak dari satu keadaan ke keadaan yang lain sesuai dengan aturan yang ada, dan mengakhiri permainan jika salah satu telah mencapai tujuan.

Sehingga untuk Mendeskripsikan Masalah Dengan Baik harus :

Mendefinisikan suatu ruang keadaan (state space)
Menetapkan satu atau lebih keadaan awal (initial state)
Menetapkan satu atau lebih tujuan (goal state)
Menetapkan kumpulan aturan

Beberapa cara untuk merepresentasikan Ruang Keadaan, antara lain :

1. Graph Keadaan

Graph terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node-node dalam graph keadaan saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah dari suatu keadaan ke keadaan berikutnya.

Gb. Graph Keadaan

Graph keadaan dengan node M menunjukkan keadaan awal, node T adalah tujuan. Ada 4 lintasan dari M ke T :

M-A-B-C-E-T
M-A-B-C-E-H-T
M-D-C-E-T
M-D-C-E-H-T

2. Pohon Pelacakan / Pencarian

Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis. Node yg terletak pada level - 0 disebut "akar".

Node akar : menunjukkan keadaan awal & memiliki beberapa percabangan yang terdiri atas beberapa node yg disebut "anak".

Node-node yg tidak memiliki anak disebut "daun". menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).

Gambar berikut menunjukkan pohon pencarian untuk graph keadaan dengan 6 level.

Gb. Pohon Pelacakan

3. Pohon AND/OR

Masalah M dicari solusinya dengan 4 kemungkinan yaitu A OR B OR C OR D.

Gb. Pohon OR

Masalah M hanya dapat diselesaikan dengan A AND B AND C AND D.

Gb. Pohon AND

Contoh 1 :

Dengan menggunakan pohon AND/OR tujuan yang dicapai pada gambar sebelumnya (pohon pelacakan) bisa dipersingkat hanya sampai level-2 saja.

Gb. Pohon AND/OR

Contoh 2 :

Masalah PETANI, KAMBING, SERIGALA, SAYURAN, PERAHU.

Seorang petani akan menyeberangkan seekor kambing,seekor serigala,sayuran dengan sebuah perahu yg melalui sungai. Perahu hanya bisa memuat petani & satu penumpang yg lain (kambing, serigala, atau sayuran). Jika ditinggalkanpetani tersebut, maka sayuran dimakan kambing dan kambing akan dimakan serigala.

Penyelesaian :

1. Identifikasi ruang keadaan

Permasalahan ini dapat dilambangkan dengan (jumlah kambing,jumlah serigala,jumlah sayuran,jumlah perahu).

Contoh : daerah asal (0,1,1,1) = daerah asal tidak ada kambing,ada serigala, ada sayuran,ada perahu

2. Keadaan awal & tujuan

Keadaan awal, pada kedua daerah :

daerah asal = (1,1,1,1)

daerah seberang = (0,0,0,0)

Keadaan tujuan, pada kedua daerah :

daerah asal = (0,0,0,0)

daerah seberang = (1,1,1,1)

3. Aturan-aturan