sedikit pengetahuan tentang algoritma dalam robotika, selamat menikmati..
Algoritma Dead Reckoning:
Dead Reckoning adalah sebuah proses dalam memperkirakan posisi berdasarkan posisi sebelumnya yang telah diketahui kecepatan, waktu dan jarak yang telah diketahui. Dead Reckoning banyak digunakan oleh binatang sebagai suatu cara navigasi untuk mengetahui posisinya berdasarkan pergerakan yang telah mereka buat sejak lokasi terakhir yang diketahui mereka. Dengan Dead Reckoning, kita juga bisa memprediksi posisi kita berikutnya melalui perhitungan kecepatan dan jarak saat ini. Di dalam dunia networking, dead reckoning adalah sebuah metode yang digunakan untuk mengurangi lag yang disebabkan oleh network latency dan masalah bandwidth. Program melakukan hal ini dengan memprediksi state berikutnya dari sebuah entitas berdasarkan state saat ini.
Pseudocode:ada dua jenis Dead Reckoning,
zero-order convergence dan
first-order convergence.Zero-order convergence: (source: http://www.it.uu.se/edu)
For each shared object
{
PredictedPathVector = Last_KnownPos - Last_Last_KnownPos
DeltaTime = Last_KnownTime - Last_Last_KnownTime
DeltaVelocity = PredictedPathVector / DeltaTime
NewDeltaTime = CurrentTime - LastLastKnownTime
NewPos = LastKnownPos + NewDeltaTime * DeltaVelocity
}
first-order convergence: (source: http://www.it.uu.se/edu)
For each shared object{
PrevPredictedPathVector = Last_KnownPos[1]-
Last_KnownPos[2]
PrevDeltaTime = Last_KnownTime[1] - Last_KnownTime[2]
StartDeltaTime = Last_KnownTime[0] - Last_KnownTime[2]
PrevVelocity = PrevPredictedPathVector / PrevDeltaTime
StartPos = Last_KnownPos[2] + StartDeltaTime *
PrevVelocity
CurrentDeltaTime = Now - Last_KnownTime[0]
PredictedPathVector = Last_KnownPos[0] -
Last_KnownPos[1]
DeltaTime = Last_KnownTime[0] - Last_KnownTime[1]
EndPos = Last_KnownPos[0] + CurrentDeltaTime *
PredictedPathVector / DeltaTime
LinearConvergenceVector = EndPos - StartPos
Velocity = LinearConvergenceVector / DeltaTime
NewPos = StartPos + CurrentDeltaTime * Velocity
}
Follow LineAlgoritma ini digunakan oleh sebuah objek untuk tetap pada garis yang tercetak pada lantai. Biasa digunakan pada robot yang dilombakan pada berbagai kompetisi dimana sang robot harus berjalan mengikuti garis yang tercetak pada lantai sampai tujuan.
Follow WallAlgoritma ini digunakan oleh sebuah objek untuk dapat mengikuti arah dimana tembok berada. algoritma ini banyak digunakan pada maze solving (keluar dari labirin). Kesesuaian arah disesuaikan dengan yang diminta. Algoritma yang terkenal adalah algoritma prinsip tangan kanan. algoritma ini sederhana: taruh tangan kanan anda pada tembok, lalu jalanlah sesuai dengan tembok yang menempel pada tangan anda. maka, anda akan menemukan jalan keluar dari maze. Algoritma ini dapat digambarkan sebagai berikut:
pastikan posisi tempat kita berada saat ini adalah posisi start
untuk mencari jalan keluar dari labirin, periksa tembok-tembok dimulai dari kanan, atas, kiri, bawah.
- Periksa kanan: jika ada tembok, periksa atas. Jika tidak ada tembok, belok kanan.
- Periksa atas: jika ada tembok, periksa kiri. Jika tidak ada tembok, jalan lurus.
- Periksa kiri, jika ada tembok, periksa bawah. Jika tidak ada tembok, belok kiri.
- Periksa bawah, jika ada tembok, kembali periksa atas. Jika tidak ada tembok, jalan mundur.
- Begitu seterusnya hingga menemukan jalan keluar.
pseudocode:function maze(kanan, atas, kiri, bawah){
set array[#][#] as maze
start[x][y] = array[0][0] // start dimulai dari titik (0,0)
if(start[x+1][y])==null //kanan
turn right;
maze(bawah, kanan, atas, kiri);
if(start[x][y+1])==null //atas
turn ahead;
maze(kanan, atas, kiri, bawah);
if(start[x-1][y])==null//kiri
turn left;
maze(atas, kiri, bawah, kanan);
if(start[x][y-1])==null//bawah
turn down;
maze(kiri, bawah, kanan, atas);
}
potongan program:void maze(){
string finishY, finishX, startY, startX;
string y1 = startY;
string y2 = startX;
while(!(yl == finishY && xl == finishX)){
if(trace[yl][xl+1] ==”tembok”)
else if(trace[yl+1][xl] ==”tembok”)
else if(trace[yl][xl-1] ==”tembok”)
else trace[yl-1][xl]= “jalan”;
...dst...
}
Fuzzy LogicFuzzy Logic menggantikan kebenaran konsep logika Boolean (yang menyatakan bahwa segala hal dapat direpresentasikan dengan 0 atau 1) dengan konsep “tingkat kebenaran”. Fuzzy Logic memungkinkan nilai keanggotaan antara 0 dan 1, abu-abu, hitam atau putih, “sedikit”, “lumayan”, “sangat”, atau “paling”. Fuzzy logic sangat berhubungan dengan teori kemungkinan.
pseudocodeSebagai contoh, dalam kasus mengontrol temperatur. Daripada kita harus selalu bergelut dengan permasalahan:
if (Tz>100C && Z==”Cair”)//Tz adalah temperatur Z, Z adalah logam
then “buat pedang”;
lebih baik kita ganti dengan alternatif baru yang tidak perlu menggunakan kompleksnya angka:
if(Tz sudah sangat panas && Z telah mencair)
maka kita buat pedang;
Di dalam Fuzzy Logic, tidak ada pernyataan seperti “tingginya 1.2 m” atau “tingginya 1.67 m”. tetapi, nilai tinggi diberikan dalam suatu batasan range.
Laki-laki pendek sekali = [0, 1.3] m
laki-laki pendek = [1.3, 1.5] m
laki-laki sedang = [1.5, 1.8] m
laki-laki tinggi = [1.8, 2.0] m
laki-laki raksasa > 2.0 m
konsekuensinya, 2 nilai(true atau false) saja tidak cukup. Dibutuhkan nilai yang lebih banyak. Misal:
tidak setuju = 0
agak setuju = 1
setuju = 2
sangat setuju = 3
Maze Mappingmerupakan algoritma yang digunakan untuk mapping, yakni mencari dan menggambarkan peta jalan keluar dari labirin (maze).
Algoritma Neural NetworksNeural Networks Algorithm, atau disebut juga algoritma jaringan saraf, merupakan sebuah algoritma yang meniru sistem kerja jaringan saraf manusia. Algoritma ini meniru sistem kerja otak manusia dalam menerjemahkan kompleksnya input untuk kemudian dijadikan output. Algoritma ini terdistribusi secara paralel dan memunyai kecenderngan untuk menyimpan pengetahuan yang didapatkannya dari pengalaman. Oleh karena itu, algoritma akan selalu merubah strukturnya untuk memecahkan masalah berdasarkan informasi eksternal maupun internal yang telah didapatkannya.
Shortest PathShortest Path, atau biasa dikenal dengan istilah Algoritma Djikstra, merupakan sebuah cara pencarian yang dilakukan pada graph dimana hanya dibutuhkan jalur yang paling pendek untuk sebuah graph. Algoritma ini menemukan jalur pencapaian tujuan dengan biaya yang paling rendah.
Algoritma Djikstra menghitung jarak semua verteks pada sebuah graf dari current verteks. Algoritma ini hanya berlaku pada kondisi: graf terhubung, edge yang tidak berarah, bobot edge(distance) tidak bernilai negatif.
Algoritma:- buat list untuk jarak, verteks sebelumnya, verteks yang telah dikunjungi, dan verteks saat ini.
- Set semua verteks dengan nilai tak hingga, kecuali pada verteks awal-yang diset dengan nol.
- Semua nilai pada list verteks yang telah dikunjungi, diset dengan false.
- Set semua nilai pada list verteks sebelumnya dengan nilai yang spesial yang menandakan bahwa mereka belum didefinisikan, seperti null.
- Set verteks saat ini dengan verkteks awal.
- Tandai verteks saat ini bahwa telah dikunjungi.
- Update jarak dan list sebelumnya berdasarkan verteks yang bisa secara langsung dicapai dari verteks saat ini.
- Update verteks saat ini dengan verteks yang belum dikunjungi yang bisa dicapai dengan jalur terpendek (shortest path) dari verteks awal.
- ulang sampai langkah 6 hingga semua node dikunjungi
pseudocode:function Dijkstra(Graph, source): (source: wikipedia)
for each vertex v in Graph: // Inisialisasi
dist[v] := infinity // jarak yang belum diketahui
previous[v] := undefined // node sebelumnya
dist[source] := 0 // jarak dari source ke source
Q := the set of all nodes in Graph
while Q is not empty: // main loop
u := node in Q with smallest dist[] // jarak terpendek
remove u from Q // ambil u
for each neighbor v of u:
alt := dist[u] + dist_between(u, v)
if alt
