Finite State Machines

Finite State Machines (FSM) adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan Action (aksi). Pada satu saat dalam periode waktu yang cukup signifikan, sistem akan berada pada salah satu state yang aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan masukan atau event tertentu, baik yang berasal dari perangkat luar atau komponen dalam sistemnya itu sendiri (misal interupsi timer). Transisi keadaan ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi yang sederhana atau melibatkan rangkaian proses yang relative kompleks. Berdasarkan sifatnya, metode FSM ini sangat cocok digunakan sebagai basis perancangan perangkat lunak pengendalian yang bersifat reaktif dan real time. Salah satu keuntungan nyata penggunaan FSM adalah kemampuannya dalam mendekomposisi aplikasi yang relative besar dengan hanya menggunakan sejumlah kecil item state. Selain untuk bidang kontrol, Penggunaan metode ini pada kenyataannya juga umum digunakan sebagai basis untuk perancangan protokol-protokol komunikasi, perancangan perangkat lunak game, aplikasi WEB dan sebagainya.
Dalam bahasa pemrograman prosedural seperti bahasa C, FSM ini umumnya direalisasikan dengan menggunakan statemen kontrol switch case atau/dan if..then. Dengan menggunakan statemen-statemen kontrol ini, aliran program secara praktis akan mudah dipahami dan dilacak jika terjadi kesalahan logika.

 Finite State Machine di dunia AI Game Programming, merupakan salah satu teknik yang paling sering digunakan. Alasannya yaitu:

1. Implementasinya mudah dan cepat

2. Memudahkan proses debugging. Karena telah dipecah menjadi kepingan yang lebih kecil, proses debugging kalau terjadi behavoiur yang tidak semestinya, menjadi lebih mudah

3. Proses komputasi yg minimal, karena sejatinya FSM hanyalah conditional statement yang dikemas dalam bentuk yang lebih elegan.

4. Fleksibel, dapat dikombinasikan dengan teknik AI lain misalnya fuzzy logic dan neural network

Kekurangannya:

1. Behaviour dari agen mudah diprediksi, karena tidak ada searching dan atau learning di dalam agen tersebut

2. Karena mudah diimplementasi, kadang programmer langsung tembak di eksekusi tanpa melakukan desain FSM terlbih dahulu. Biasanya akan terjadi FSM yang terfragmentasi

3. Timbul apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua buah state terlalu tipis:

Bentuk Implementasi

Ada beberapa bentuk FSM, diantaranya:

1. Naive Approach

Menggunakan conditional statement (if-else atau switch-case) tanpa memecah object menjadi object2x yang lebih kecil sesuai state nya.

Untuk agen yang cuma punya state yang sedikit, metode ini masih memungkinkan. Tapi kalau sudah kompleks, penggunaan metode ini jelas tidak dianjurkan, karena akan membentuk ‘spaghetti code’ dan monolithic conditional statement. Selain itu juga tidak scalable, tidak fleksibel, dan proses debugging menjadir lebih rumit.

2. State Transition Table

Bentuk ini sudah mengimplementasikan State Pattern, dengan menempatkan transition logic di context (untuk lebih jelasnya tentang State Pattern, baca ini dulu). Bentuk ini juga sering disebut sebagai Classic FSM.

Dengan metode ini dibuat sebuah tabel yang dikenal dengan State Transition Table, bentuknya seperti ini:

Agen akan melakukan query dari tabel tersebut berdasarkan input yang diterima dari environmentnya. Kemudian ketika salah satu kondisi terpenuhi, dia akan mengubah current state menjadi state yang baru sesuai kondisinya.

Dengan begini, maka tentunya akan mempunyai fleksibilitas dan skalabilitas yang jauh lebih baik daripada jika menggunakan naive approach. Dengan drawback akan terbentuk monolithic conditional statements.

3. Embedded Rules

Bentuk ini adalah kebalikan dari bentuk Classical Approach, yang berarti state transition didefinisikan di state itu sendiri. Dan sama dengan Classical Approach, bentuk ini juga akan menawarkan fleksibilitas dan skalabilitas yang baik, namun dengan efek samping agak sulit untuk di-mantain karena aturan2x transisi diletakkan di state sehingga ketika terjadi penambahan atau pengurangan state, maka harus dilakukan update juga terhadap state2x yang terkait.

DIAGRAM KEADAAN
Diagram keadaan pada dasarnya merupakan salah satu bentuk representasi dari FSM. Diagram ini secara visual menggambarkan tingkah laku yang dimiliki oleh sistem kontrol yang kompleks kedalam bentuk yang lebih sederhana dan relative mudah dipahami.
Dalam diagram ini, state-state yang terdapat pada sebuah sistem digambarkan sebagai lingkaran yang diberi label unik, sedangkan transisi state yang diakibatkan oleh event tertentu direpresentasikan sebagai anak panah yang berasal dari state yang ditinggalkan menuju state yang aktif. Setiap transisi yang terjadi umumnya juga diikuti oleh aksi yang dilakukan oleh sistem yang dirancang. Secara praktis setiap diagram state yang dirancang akan selalu memiliki sebuah transisi awal (inisial) yang menuju salah satu state sejak sistem kontrol tersebut mulai dihidupkan. Gambar berikut memperlihatkan contoh penggambaran diagram state:

Diagram tersebut memperlihatkan FSM dengan dua buah state (S0 dan S1) dan dua buah input (e1 dan e2) serta dua buah aksi (a1 dan a2) output yang berbeda : seperti terlihat pada gambar, ketika sistem mulai dihidupkan, sistem akan bertransisi menuju state0, pada keadaan ini sistem akan menghasilkan Action2 jika terjadi masukan Event2, sedangkan jika terjadi Event1 maka Action1 akan dieksekusi kemudian sistem selanjutnya bertransisi ke keadaan State1 dan seterusnya.
Berikut adalah potongan program untuk gambar tersebut

//program gambar diatas

….

#define TRUE 1

enum {state0,state1}

……

unsigned char state;

void Action1(void);

void Action2(void);

…..

main()

{

//init

………

While(TRUE)

{

switch(state)

{

case state0: If(input==Event2)

{Action2();

state=state0;}

break;

case state1: If(input==Event1)

{Action1()

state=State1;}

break;

}

}

…….

}