Bagaimana Saya Menjelaskan REST kepada Istri (How I Explained REST to My Wife)

For the first time since this blog is created. I'm writing a post in two languages. I was impressed with an explanation from Ryan Tomayko which is based on his conversation with his non-techy wife about REST. You can read the original version here. Some people may think that the article is somewhat sexist. However, I do believe that he didn't do it on purpose ;) The rest of this post will be in Bahasa Indonesia.

--

Artikel di bawah ini adalah terjemahan dari artikel yang ditulis oleh Ryan Tomayko. Beberapa bagian tulisan di bawah ini mungkin tidak/kurang/belum akurat, namun akan saya coba untuk memperbaharuinya setiap kali saya menemukan kekurangan. Semoga bermanfaat.

Istri: Siapa itu Roy Fielding?

Ryan: Orang yang cerdas.

Istri: Oh, memangnya apa yang dia lakukan?

Ryan: Dia membantu menulis (mengkode) web server pertama dan melakukan banyak research untuk menjelaskan kenapa web bekerja seperti itu. Namanya ada di spesifikasi untuk protokol yang digunakan untuk menerima halaman web dari server ke browser.

Istri: Bagaimana cara kerjanya?

Ryan: Maksudnya, web?

Istri: Yup.

Ryan: Hmm. Semua itu sangat mengagumkan. Lucunya, orang tidak terlalu menghargai ini. Protokol yang sedang kubicarakan ini, HTTP, mampu melakukan banyak hal berguna yang diacuhkan orang dengan alasan-alasan tertentu.

Istri: Maksudnya HTTP seperti yang ada di awal teks yang aku ketik di browser?

Ryan: Ya. Itu menunjukkan browser tentang protokol apa yang digunakan. Yang kamu ketik itu adalah satu dari sekian terobosan penting dalam sejarah komputer.

Istri: Kok bisa?

Ryan: Karena itu mampu mendeskripsikan lokasi dari suatu hal dimanapun di dunia ini. Itu adalah fondasi dari web. Kamu bisa bayangkan itu seperti koordinat GPS untuk pengetahuan dan informasi.

Istri: Untuk halaman web?

Ryan: Tidak hanya untuk halaman web. Orang itu, Roy Fielding, dia banyak bercerita tentang apa yang ditunjukkan oleh HTTP dalam riset yang aku sebutkan tadi. Web dibangun dengan arsitektur "REST". REST memberikan definisi dari "resource" dimana "resource" ini ditunjuk oleh HTTP.

Istri: Halaman web itu sebuah resource?

Ryan: Kira-kira begitulah. Sebuah halaman web adalah representasi dari sebuah resource. Resource itu sendiri adalah sebuah konsep. URL-itulah yang diketikkan ke browser...

Istri: Aku tahu apa itu URL.

Ryan: Oh. URL dapat memberi tahu browser bahwa ada sebuah konsep di suatu tempat. Browser kemudian dapat menanyakan representasi spesifik dari konsep tersebut. Lebih spesifik lagi, browser tersebut bertanya tentang representasi halaman web dari konsep yang ada.

Istri: Apa ada jenis lain dari representasi?

Ryan: Sebetulnya, representasi adalah salah satu hal yang kurang termanfaatkan. Dalam banyak kasus, sebuah resource hanya memiliki satu representasi. Tapi kami berharap bahwa representasi akan digunakan lebih banyak di masa depan karena akan ada banyak format baru bermunculan.

Istri: Seperti apa?

Ryan: Hmm. Ada konsep yang disebut orang sebagai "Web Services". Itu bisa berarti macam-macam tapi konsep dasarnya ialah bahwa mesin juga dapat menggunakan web seperti manusia.

Istri: Maksudnya seperti robot begitu?

Ryan: Tidak, bukan begitu. Bukan maksudku bahwa robot akan duduk di kursi dan kemudian browsing halaman web. Tapi komputer dapat menggunakan protokol yang sama untuk mengirim message antar sesamanya. Kami sudah melakukan itu untuk waktu yang lama tapi tidak ada teknik yang dapat digunakan untuk berbicara dengan mesin di seluruh dunia pada saat ini.

Istri: Kenapa tidak?

Ryan: Karena mereka tidak didesain seperti itu. Ketika Fielding dan teman-temannya mulai membangun web, kemampuan untuk berkomunikasi antar mesin di seluruh dunia adalah perhatian utama mereka. Kebanyakan dari teknik yang digunakan untuk membuat komputer berkomunikasi dengan sesamanya tidak memiliki kebutuhan seperti itu. Kebanyakan hanya perlu untuk berkomunikasi dengan grup kecil saja.

Istri: Dan sekarang kamu perlu untuk berkomunikasi dengan semua mesin?

Ryan: Ya - bahkan lebih. Kami perlu untuk dapat berkomunikasi dengan semua mesin tentang semua hal yang ada di mesin-mesin tersebut. Jadi kamu membutuhkan sebuah cara untuk memungkinkan mesin berbagi informasi tentang resource yang mungkin belum ada pada mesin lain.

Istri: Apa?

Ryan: Misalkan kamu ngobrol dengan adikmu dan dia mau meminjam sapu atau apapun. Tapi kamu tidak punya - Ibumu yang punya. Jadi kamu bilang ke adikmu untuk meminjam dari Ibumu. Ini terjadi sepanjang waktu di dunia nyata dan ini juga akan terjadi ketika mesin mulai berkomunikasi satu sama lain.

Istri: Jadi bagaimana mesin memberitahu satu sama lain tentang lokasi hal-hal tersebut?

Ryan: URL, pastinya. Kalau semua yang dibutuhkan mesin memiliki URL, berarti kamu sudah menciptakan sebuah equivalen dari kata benda. Kesepakatan antara kamu, aku, dan seisi dunia tentang kata benda dalam suatu cara pastinya penting kan?

Istri: Ya.

Ryan: Mesin tidak punya kata benda yang universal - makanya mereka payah. Setiap bahasa pemrograman, database, atau sistem lain punya cara yang berbeda-beda dalam mengkomunikasikan benda. Itulah kenapa URL itu sangat penting. URL memungkinkan semua sistem ini berkomunikasi tentang benda masing-masing.

Istri: Tapi ketika aku melihat halaman web, aku nggak berpikir seperti itu.

Ryan: Orang lain juga tidak. Kecuali Fielding dan sedikit orang lain. Itulah kenapa mesin masih payah.

Istri: Bagaimana dengan kata kerja, kata ganti, dan kata sifat?

Ryan: Lucu juga kamu tanya itu karena itu adalah hal penting lain dari REST. Eng, setidaknya kata kerja lah.

Istri: Aku cuma bercanda.

Ryan: Itu lucu, tapi sebenarnya bukan joke sama sekali. Kata kerja itu penting. Ada konsep yang sangat kuat dalam pemrograman yang siebut sebagai "polymorphism" dalam Computer Science. Itu adalah cara kami mengatakan bahwa benda yang berbeda bisa memiliki kata kerja yang sama yang dikenakan pada mereka.

Istri: Aku tak mengerti.

Ryan: Wel... Kita lihat meja kopi. Kata benda apa saja yang ada? Gelas, baki, koran, remote. Sekarang, apa saja yang bisa kamu lakukan terhadap benda-benda itu?

Istri: Aku tak mengerti.

Ryan: Kamu bisa mengambil mereka, kan? Kamu bisa mengangkat mereka. Kamu bisa menjatuhkan mereka. Kamu bisa membakar mereka. Kamu bisa menggunakan kata kerja yang sama untuk objek manapun yang ada di sana.

Istri: Oke... jadi?

Ryan: Nah, itu yang penting. Bagaimana jika kita tidak bisa mengatakan, "ambil gelas", atau "ambil koran", atau "ambil remote"; Bagaimana jika untuk itu kita harus menggunakan kata kerja yang berbeda untuk setiap kata benda? Kita tidak bisa menggunakan kata "ambil" secara unversal, tapi harus menggunakan kata baru untuk setiap kombinasi kata kerja/kata benda.

Istri: Wow! Itu aneh.

Ryan: Ya, itu aneh. Otak kita cukup cerdas untuk mengetahui bahwa kata kerja yang sama dapat digunakan untuk benda-benda yang berbeda. Sebagian kata kerja memang lebih spesifik dan hanya bisa digunakan pada kata benda tertentu. Misalnya, aku tidak bisa "mengendarai gelas" atau "minum mobil". Tapi sebagian kata kerja sangat universal seperti ambil (GET), taruh (PUT), dan hapus (DELETE).

Istri: Kamu tidak bisa menghapus gelas.

Ryan: Oke, tapi kamu bisa membuang gelas. Tapi itu cuma joke kan?

Istri: Yeah.

Ryan: Jadi, HTTP -protokol yang dibuat Fielding dan teman-temannya ini- adalah tentang penggunaan kata kerja ke kata benda. Contohnya, ketika kamu mengunjungi sebuah halaman web, browser akan menggunakan HTTP GET ke URL yang kamu ketikkan dan halaman web akan kamu peroleh.

Halaman web biasanya mengandung gambar kan? Gambar adalah resource yang berbeda. Halaman web hanya menyebutkan URL ke gambar dan browser akan memanggil HTTP GET ke semua URL gambar tersebut hingga semua resource yang dibutuhkan untuk menampilkan halaman web itu diperoleh. Tapi yang penting disini ialah bahwa hal-hal yang berbeda dapat diperlakukan dengan cara yang sama. Apakah kata benda itu adalah gambar, teks, video, mp3, slideshow, atau apapun. Aku bisa melakukan instruksi GET untuk semua hal tersebut selama mereka memiliki URL.

Istri: Sepertinya GET itu kata kerja yang penting.

Ryan: Memang. Terutama bila kamu menggunakan browser karena browser biasanya hanya digunakan untuk mengambil sesuatu. Browser tidak terlalu banyak berinteraksi dengan resource. Ini jadi masalah karena orang jadi berpikir bahwa HTTP itu hanya untuk mengambil sesuatu. Padahal sebenarnya HTTP itu adalah protokol umum untuk mengaplikasikan kata kerja pada kata benda.

Istri: Keren. Tapi aku tidak paham kenapa ini bisa mengubah apapun. Kata benda dan kata kerja apa saja yang kamu mau?

Ryan: Kata benda sudah ada tapi tidak dalam format yang benar.

Coba bayangkan ketika kamu sedang browsing di amazon.com untuk mencari hadiah natal. Bayangkan setiap produk adalah kata benda. Sekarang, ketika mereka tersedia dalam bentuk yang dapat dimengerti mesin, kamu bisa melakukan banyak hal yang menarik.

Istri: Mengapa mesin tidak bisa mengeri halaman web biasa?

Ryan: Karena halaman web didesain untuk dimengerti oleh manusia. Mesin tidak peduli terhadap layout dan style. Mesin hanya butuh data. Idealnya, setiap URL punya representasi yang dapat dimenerti manusia dan representasi yang dapat dimengerti mesin. Ketika sebuah mesin melakukan GET terhadap resource, maka dia akan meminta representasi yang dapat dimengerti mesin. Ketika sebuah browser melakukan GET terhadap resource atas permintaan manusia, maka yang diperoleh adalah representasi yang dapat dimengerti oleh manusia.

Istri: Jadi semua orang harus membuat format yang dapat dimengerti oleh mesin ke semua halaman web mereka?

Ryan: Kalau itu memang bermanfaat.

Kita sudah banyak ngobrol dengan abstraksi. Bagaimana kalau ita ambil contoh yang nyata. Kamu adalah seorang guru -di sekolah aku yakin kamu punya sistem komputer yang besar, atau tiga atau empat komputer, yang memungkinkanmu untuk mengelola murid: di kelas mana mereka berada, berapa nilai mereka, kontak darurat, informasi mengenai buku yang kamu ajarkan, dan laib sebagainya. Jika sistem ini web-based, maka kemungkinan ada URL untuk setiap benda yang terlibat disini: murid, guru, kelas, buku, ruangan, dll. Saat ini, memasukkan URL lewat browser akan memberikanmu sebuah ahalaman web. Jika ada representasi yang dapat dimengerti oleh mesin untuk setiap URL, maka mudah saja untuk menelurkan sebuah aplikasi ke dalam sistem karena semua infomasi tersebut dapat dikonsumsi dengan cara yang standar. Itu juga akan memungkinan semua sistem untuk berkomunikasi satu sama lain dengan mudah. Atau, kamu bisa membuat sistem untuk propinsi atau negara yang bisa berkomunikasi dengan masing-masing sekolah untuk mengumpulkan nilai ujian. Kemungkinan yang ada bisa tanpa batas.

Setiap sistem akan memperoleh informasi dari yang lain dengan menggunakan instruksi HTTP GET yang sederhana. Jika sebuah sistem perlu menambahkan sesuatu ke sistem lain, maka dia akan menggunakan HTTP POST. Jika sebuah sistem ingin memutakhirkan sesuatu ke sistem lain, dia akan menggunakan HTTP PUT. Satu-satunya yang perlu didiskusikan adalah dalam bentuk apa data itu seharusnya.

Istri: Jadi ini yang kamu dan semua orang komputer lakukan sekarang? Mendiskusikan bagaimana data itu seharusnya?

Ryan: Sedihnya, tidak. Malah kebanyakan sibuk menulis spesifikasi kopleks untuk melakukan hal ini dengan cara yang berbeda dan tidak terlalu bermanfaat. Benda tidak universal dan kata kerja tidak polimorphic. Kita membuang puluhan tahun pengalaman dari penggunaan di dunia nyata dan teknik yang telah terbukti dan memulai kembali dengan sesuatu yang kelihatannya sangat mirip dengan sistem lain yang telah gagal di masa lalu. Kami menggunakan HTTP tapi hanya karena itu membantu kita untuk menghindari pembicaraan dengan administrator jaringan. Kami mengorbankan kemudahan dengan aplikasi yang terlihat keren dan aplikasi wizard.

Istri: Kenapa?

Ryan: Aku tidak tahu.

Istri: Kenapa kamu tidak bilang apa-apa?

Ryan: Mungkin nanti.

Read More

The Limit of Artificial Intelligence (AI)

I always crazy about sci-fi futuristic movies. Humanoid robots, machines vs men (with the help of Arnold) wars, or robots taking over the whole earth and keeping men as batteries. Simply love them. Most of those movies introduced the existence of highly-intelligent machines. Sometimes they are shown as having a human-level intelligent, in other case they are even better. Well now the question is: is it even possible? To what extent the development of so called Artificial Intelligence (AI) will be?

Back in 1960 something, experts predicted that in 20 years machine would be capable of doing everything human capable of, which is often called as "Strong AI". With respect for those AI experts, we are now in 2008 and it's not even close. Strong AI is proven to be much more difficult and complicated to achieve. This misprediction has caused AI experts being addressed as a “liar”, and consequently being forced to changes the direction of AI research from “Strong AI” into a more short-term, specific domain of problem, which is called "Applied AI" or "Weak AI". However, the dream of “human level AI” will never cease, and debate about it is always interesting to follow.

There has been a great discussion about whether human level AI is likely to be achieved by a mere symbol processing like what most weak AI commonly use. By applying a huge collection of formal rules and in addition, scaling up processing capabilities and storage capacity, and there we are. This opinion is greatly opposed by some experts. As current system lacks of something that is called “understanding”, “minds”, “conscience”, or other things which is related to mental states. The argument based on the idea that there is something more than just behavior to call a machine have an intelligent comparable to human. For example, let say that a machine capable of translating English to French. Even if the machine did it correctly, it is arguably incorrect to say that the machine actually “understand” English (or French).

But who need minds anyway? Intelligent is all about behavior, and it alone is enough. To see it from a different perspective, I (and my ignorance) have a trouble to imagine what “minds” and “conscience” are. Are they just some terms used to express something unexplainable? Or perhaps it just simply does not exists from the very beginning?

I have a nice discussion with one of my friend about this matter, and his view is somewhat different from what I expect, but nevertheless very fascinating to be followed. His first thought is that, even if human are capable of doing it, creating a machine with human level intelligent is unnecessary. Life is difficult enough, why would you like to increase the competition among human by introducing some humanoids? Other thing he expressed is that there is no way human will be able to do such a thing. An inventor would not be able to invent anything equal or beyond itself, as human is not God.

p.s: I am not an AI researcher nor expert in this field. Just someone who has an interest in it.

Read More

Wireless Sensor Network and Intelligent Transportation System

This is the third article related to Intelligent Transportation System. You can see the first and second article first if you like to.

It is widely known that knowing the position and speed of the vehicles on the road network in real-time is one of the major challenges that vehicle control and traffic management applications are facing [2]. Wireless Sensor Network (WSN) is considered as a potential technology that might be useful as an infrastructure component of an ITS since it received significant attention in the last decade and successful research put them in the forefront to answer this challenge [2].

A wireless sensor network is a collection of nodes organized into a cooperative network. Each node consists of processing capability (one or more microcontrollers, CPUs or DSP chips), may contain multiple types of memory (program, data and flash memories), have a RF transceiver (usually with a single omni-directional antenna), have a power source (e.g., batteries, solar cells), and accommodate various sensors and actuators. The nodes communicate wirelessly and often self-organize after being deployed in an ad hoc fashion [1]. It is an infrastructure comprised of sensing(measuring), computing, and communication elements that gives the user the ability to instrument, observe, and react to events and phenomena in specified environment. The environment can be the physical world, or a biological system [3].

Currently, wireless sensor networks are beginning to be deployed at an accelerated pace. It is not unreasonable to expect that in 10-15 years that the world will be covered with wireless sensor networks with access to them via the Internet. This can be considered as the Internet becoming a physical network. This new technology is exciting with unlimited potential for numerous application areas including environmental, medical, military, transportation, entertainment, crisis management, homeland defense, and smart spaces [1].

Some typical applications of Wireless Sensor Network are tracking, monitoring, and controlling. In a typical application, a WSN is scattered in a region where it is meant to collect data through its sensor nodes. Existing and potential applications of sensor networks include, among others, military sensing, physical security, air traffic control, traffic surveillance, video surveillance, industrial and manufacturing automation, process control, inventory management, distributed robotics, weather sensing, environment monitoring, national border monitoring, and building and structures monitoring [3].

Key Technology

The basic functionalities for WSN depends on the application, which in this case is ITS. There are several type of sensor parameters, including: physical measurements, chemical and biological measurements, and event measurements. In ITS, the most important features are the vehicle states, which includes position, speed, direction. Other possibility of feature is classification, for example: is a vehicle in traffic a car, a truck, or a bus? Some possible sensors for ITS includes magnetoresistive, light, pressure, and video (visible or infrared).

As for the transmission part, there are several wireless transmission technologies available. WSN can use some wireless technologies such as Bluetooth, ZigBee, Wireless LAN, WiMax, and 3G. The requirements of communication are related to the implementation of ITS. Some properties that have to be put into considerations are: range of communication, data throughput, and power consumption. In term of range, 3G covers the longest range, continue by WiMax, Wireless LAN, Bluetooth and Zigbee. Theoretically all those technologies are useful for ITS, however it is all depend on the topology and implementation of the system.

ITS typically does not involved a high data rate communication, however if the system requires a responsive, real-time communication then using ZigBee is arguably not very suitable since it data rates is as low as 20 kbps. However, it is designed to run several years on a single set of batteries [3]. Bluetooth offers approximately 1 to 3 Mbps and Wireless LAN have a maximum data transmission rate of 54 Mbps, but none of them as energy-efficient as ZigBee.

Each sensor node needs an operating system which capable of controlling hardware, provides hardware abstraction, and fill in the gap between application and hardware. TinyOS is one of the de facto standards of operating system designed specifically for WSN. It component library includes network protocols, distributed services, sensor drivers, and data acquisition tools. TinyOS’s event-driven execution model enables fine-grained power management, yet allows the scheduling flexibility made necessary by the unpredictable nature of wireless communication and physical world interfaces [3]. Some of its advantages are [3]:

• It requires very little code and a small amount of data
• Events are propagated quickly and the rate of posting a task and switching the corresponding context is very high
• It enjoys efficient modularity

[1] California PATH. Vehicle Platooning and Automated Highways.
[2] J. Sijs, Z. Papp, P.P.J. van den Bosch. Vehicle Motion-State-Estimation Using Distributed Sensing. 2007
[3] Kazem Sohraby, Daniel Minoli. Wireless Sensor Network. 2007

Related Posts

• Brainstorming: Designing an Intelligent Transportation System (ITS)
• Automated Highway System (AHS)

Read More

Automated Highway System (AHS)

One of the most exciting part of Intelligent Transportation System (ITS) is Automated Highway System (AHS). AHS is a way to reduce the congestion in highways. The idea is improving traffic flow and safeties by applying intelligent and automation in driving system. Autonomous control of driving tasks was considered to substantially improve the traffic flow.

The most interesting feature of AHS is a concept of group of vehicles arranged in a relatively small-fixed distance called “platoon”. Platooning is possible when every vehicle is equipped with intelligent and automation which allows smooth merging, lane changing and splitting maneuvers in a way that is advantageous to the highway performance.

platooning (taken from: www.its.go.jp)

Since platooning enables vehicles to operate much closer together than is possible under manual driving conditions, each lane can carry at least twice as much traffic as it can today. This should make it possible to greatly reduce highway congestion. Also, at close spacing aerodynamic drag is significantly reduced, which can lead to major reductions in fuel consumption and exhaust emissions. The high-performance vehicle control system also increases the safety of highway travel, reduces driving stress and tedium, and provides a very smooth ride [California PATH].

As mentioned above, an AHS requires every vehicle to be both intelligent and to some extent, automatic. This is where the Intelligent Vehicle (IV) takes its role in AHS.

IV is considered as a new technology for obtaining a more efficient driver-vehicle operation. It is meant to improve safety, operational efficiency, and convenience while driving. An IV system senses the environment around the vehicle by using sensors and strives to achieve more efficient vehicle operation by assisting the driver or by taking full control of the vehicle. Obviously, the ideal system for AHS is where the IV has fully autonomous system. In other words, the systems should remove human intervention from the control and therefore take the entire control functionalities of vehicle operations.

Related Posts

• Brainstorming: Designing an Intelligent Transportation System (ITS)
• Wireless Sensor Network and Intelligent Transportation System
  

Read More

Brainstorming: Designing an Intelligent Transportation System (ITS)

Growth in congestion, as well as the difficulties in constructing new infrastructures has lead into a research in Intelligent Transportation System (ITS). The advances in sensing technologies, computer hardware and software, etc are also become additional motivation in this field of research. Automatic Highway System (AHS) is one of the most interesting topic. Its main idea: platooning is believed to be able to improve highway throughput without having to ignore the safety but instead improving it.

It is widely known that knowing the position and speed of the vehicles on the road network in real-time is one of the major challenges that vehicle control and traffic management applications are facing. Wireless Sensor Network (WSN) is considered as a potential technology that might be useful as an infrastructure component of an ITS since it received significant attention in the last decade and successful research put them in the forefront to answer this challenge. WSN itself is an exciting technology with unlimited potential for numerous application, including tracking, monitoring, and controlling.

A distributed paradigm is the most suited approach to implements an ITS. While it is naturally distributed (spatially) and consisted of various components, which may range from several to thousands number of components (scalability issue), it is also relatively complex. Not to mention that by distribute the implementation accordingly, a certain level of reliability could be achieved more easily. Dynamic components in ITS are implemented as agents. Instead of rely heavily in modeling the process, agent-oriented paradigm offers a higher abstraction compared to the object-oriented paradigm. Agent is an autonomous entity that behaves according to its perception of the environment and its knowledge. In most cases, one agent is not enough to form the expected system. Therefore, a Multi-Agent System (MAS) is required.

Since there is no formal method to test a distributed system, the only way to do it is by using a simulation. An engine that capable of simulating any dynamic behaviors is required. Using multi-agent approach as it concept, a researches is allowed to decomposed a big system into intelligent entities with specified behaviors. In a traffic system problem domain, some entities could be considered as agents: car, driver, traffic controller, etc depending on the modelers themselves.

The simulation of an ITS system might not be complete without the introduction of human behaviors. However, human behaviors may vary for each individual or culture. Investigating the difference in culture might be interesting not only in describing the human part of the system but also to parameterize some characteristics of controllers.

Related Posts

• Automatic Highway System (AHS)
• Wireless Sensor Network and Intelligent Transportation System

Read More

Computer Technology, Now and Twenty Years Ago

With or without us realizing, the technology has been improving significantly over the past 20 years. One of the most significant changes can be spotted in the improvement of computer technology. Computer nowadays has better performance, smaller size, and bigger capacity. On top of that, the improvements of computer technology make it possible to lower the cost of computers. All of those lead to many unimaginable capabilities of computer.

Before 1980, the idea of “computer for everyone” was considered as a very unlikely, if not an absurd idea. However, keep in mind that most of the advanced technology we have today started from a mere dream. It was IBM who made it possible by introducing the first computer intended for home usage, called “IBM PC (Personal Computer)” in the early 1980s. It is true that before IBM, several companies had already attempted to release a personal computer, but none of them shared the similar popularity as IBM PC. Since that time, the computer technology started to grow immensely.

In 1987, Intel introduced the first 32-bit processor 80386 which is the third generation of processor. During the next 20 years, the development of processor has been quite outstanding and nowadays we are quite familiar with the multi-core processor known as the 8th generation of processor. To practically compare the third generation processor and the 8th generation processor is virtually impossible, however, it is still possible to compare those two using a measurement of performance in MIPS (Million Instruction per Second) scale. The 80386 processor had the processing capability of 8.5 MIPS while the high-end processor introduced in 2006, Intel Core 2 Extreme is working at 57,063 MIPS, which is 6713 times faster. It is not even necessary to mention that there exists a prototype called “Intel Polaris” capable on working in 1,800,000 MIPS just to show that there is significant improvement in processor’s performance.

The capacity of computer has also been increasing rapidly. In approximately 20 years, hard drives (common non-volatile storages for computers) has evolved from a fifty two-foot diameter disks holding only five MB (5,000,000 bytes) of data to today’s drives at the size of 3.5 inches wide capable of storing one TB (1,000,000,000,000 bytes) or more. Moreover, the development of “flash memory” made it possible to have an even smaller device with decent storage capability. The smallest flash memory available commercially called microSD is only at 15mm x 11mm x 0.7mm, or about the size of a fingernail. Despite its physical size, it can store up to 8GB of data (around 1600 MP3 or 13 movies in VCD’s format!).

The most popular Operating System (OS) in the world, Microsoft Windows had only started in 1985. The first two unsuccessful versions of Windows were nowhere near the Windows we know today. They were barely called Operating System because they were merely extensions to the console-based MS-DOS and inherit the latter’s flaws and problems. The later version of Windows called the Microsoft Windows 3.0 scored a significant success. It was capable of running multi-task applications thanks to its new memory management. Another significant improvement was its user-friendly GUI (Graphical User Interface), making it possible for the PC users to enjoy better interface that previously only be enjoyed by the more exclusive Apple Macintosh users. The latest version of Microsoft Windows is called Vista that was released in 2006 as a replacement for Microsoft Windows XP. However, despite many new exciting features introduced in Vista, many people still reluctant to upgrade their system.

Computer technology may have changed a lot, however, the same thing may not necessarily true for human. Since 20 years ago, some programmers have been keeping on developing a certain useless and troublesome programs called computer virus. It is a program that can copy itself and infect a computer without permission or knowledge of the user. If anything different about developing virus 20 years ago and now, then it should be the motives. "The most significant change has been the evolution of virus writing hobbyists into criminally operated gangs bent on financial gain" said F-Secure's chief research officer Mikko Hypponen. Unfortunately, “This trend is showing no signs of stopping".

Read More

Cyclic Coordinate Descent (CCD)

As I mentioned on previous post. This post will describe more about CCD in relation to Inverse Kinematics and Human Body Animation.

The basic idea of Cyclic Coordinate Descent (CCD) Method is performing iterative heuristic search for each joint angle, so at the end, the end-effector could reach a desired location in space. By doing iterative heuristic search, we try to find the best location of an articulated structure given its joint angles. This would result in the best (closest) distance of the end-effectors and the desired end points. The calculation is done one joint at a time, and in backward fashion, until we reached the parent joint. For calculating the joint angle, we also give certain limitation for the angle, just like the angle of a human. We implement this, so the animation wouldn’t do any strange movement. The first thing to do in CCD method is to determine the desired location of the end-effector (X). After that, we try to minimize the distance (ΔX) between end-effector position (X^) and the desired destination (X) as low as possible. We do this by increasing/decreasing the current joint angle of the end-effector. When the distance of the end-effector is as low as possible, it means that the current joint angle (Θ) has reached its maximum point, given the current position. Then we move backwards to the upper joint, where we then try again to minimize the distance between end-effector and destination point, but this time only altering the current upper joint. We do this until we reached the parent joint. An example can be seen in the following figure.

Cyclic Coordinate Descent Method for: a) Rotational Joint and b) Prismatic Joint

For example, we can imagine when we try to move the whole hand. The first thing that we do is to calculate the minimum distance that could be reached by our hand only using the wrist joint. After that, we then move backwards and try manipulate the elbow joint and again calculate the minimum distance that could be reached by our hand. We do this until the last joint is manipulated, for instance, the shoulder joint, or even our backbone joint. Each human body joint are capable to rotate in one to three different axis (3-Dimension). This ability to rotate is called Degree of Freedom of a joint. So each joint could have 1 to 3 Degree of Freedom (DOF). Using CCD method, we try to find the best joint angle for x-axis, y-axis and z-axis for a joint given the coordinate of the destination point (i.e. the best joint angle of each axis that could make the end-effector closer to the destination point). Suppose a joint cannot move in an axis, the best joint angle for that axis is zero. After calculating both three joint angles for each axis, we then calculate the rotation matrix for each axis, using the following rotation matrix:

Where RotX is the rotation matrix for x-axis, RotY is for y-axis and RotZ is for z-axis. We then combine these rotation matrixes into a single rotation matrix:

R = RotZ*RotY*RotX

Where R matrix is the rotation matrix of a joint. Applying rotation matrix of Joint(i) towards the end-effector will cause all the part from Joint(i) up to the end-effector to rotate. After that, the calculation will move backwards to Joint(i-1) and again we calculate the joint angle for Joint(i-1) and calculate the rotation matrix. In order to move end-effector given the rotation of Joint(i-1), besides rotation matrix of the current joint, we also need rotation matrix of the previous joint and the translation matrix of the previous link. The following is the translation matrix:

Where dX, dY, dZ is the length of the link (i.e. the distance between two joints). For transforming the end-effector given the rotation of Joint(i-1), we need the matrix of R(i-1)*T(i)*R(i), where T(i) is the translation matrix from the current joint to the previous joint (i.e. length of the link) and R(i) is the rotation matrix from the previous joint. Keep in mind that the calculation is done backwards starting from the end-effector towards the parent joint.This calculation will continue until we reached the parent joint where there will be no more joints that could rotate after this joint. After reaching the parent joint, the calculated distance between current end-effector location and the desired location should be as minimum as possible.

Related post

• Human Motion Animation with Inverse Kinematics
  

Read More

Modeling a Tree using L-System

An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms. [wikipedia]

When using this model, we have to define a set of grammar rules that will be used to describe the growth of the branches of a tree. The rules that we define will later be implemented as the growth of the tree in an iterative fashion. In this system, we define these following alphabets that will be used in the production rules:

f : create branch
l : create leaf
[ and ] : define a set of local area/branch. The definitions of the area are put inside the [ and ]
+ and - : rotate the branch right/left in x-axis
^ and v : rotate the branch up/down in y-axis
<> : twist the branch left/right in z-axis

By using the symbols above, we can begin to create a tree with our system. But before that, we also have to define several properties that are also important in generating the tree, which are:

• The number of production rules iterations, for determining the level of the branches,
• The angle, for determining branch curves, and
• The radius of the branches and the decreasing value of it, in an iterative way The length of the branches

The following are several examples of the production rules that are used using the system:

Tree A

Angle : 25
# Iterations: 6
Branch radius: 0.02
Branch radius reduction: 0.0015
Branch length (height): 0.15
Initial value : fffffA
Production rules : A = f[++Al][--Al]>>>A



Tree B

Angle : 30
# Iterations: 10
Branch radius: 0.01
Branch radius reduction: 0.001
Branch length (height): 0.16
Initial value : fA
Production rules : A = f[^Bl]>>[^Bl]>>A, B = f[-Bl]B


Tree C

Angle : 15
# Iterations: 13
Branch radius: 0.02
Branch radius reduction: 0.0015
Branch length (height): 0.15
Initial value : fA
Production rules : A = ^fB>>>B>>>>>B, B = [^^f>>>>>>A]

Read More

A Negotiation Agent

Introduction

Sometimes there will be a problem between two parties where everyone has a different self-interest regarding the issues that they are arguing. In order to solve the problem, both parties (and maybe even more) have to sit and discuss about the issues that they are arguing and decide which issues that is best for them all. This is what negotiation is all about.

Each party will have its own utility value for every issue and every item in it. These values determine the importance of each issue for them. Off course, the best result is to get everything on our side and perhaps zero for the opponent. But in a negotiation, that is highly impossible because each party wants something for themselves. So the best thing to do is to reach an agreement for both parties of what issue that they will keep for themselves and will give to the other.

An Italian economist named Vilfredo Pareto (1848-1923) once introduced a concept called Pareto Efficiency. Pareto Efficiency is the outcome of a negotiation when there are no other outcomes where both parties will do better, but rather one party will do better, but the other will do worse. In a negotiation, there could be more than one outcome where the outcome is Pareto optimal. These outcomes are located in a Pareto frontier which is the boundaries between available and unavailable outcomes.

Designing a Negotiation Agent

We constructed an agent that is capable of negotiating problems with the other agent in order to achieve a result that is acceptable enough for both agents. The following diagram is the flowchart of our agent.

The basic procedure of how our agent works is that first, it always generates an offer that consists of the issues that is most important for the agent. It does this because it wants to tell to the opponent, at the first time, which issues are the most important for the agent. After sending the offer, the agent will later on receive a message from the opponent as a reaction. The opponent could accepts our offer, breaks the negotiations or proposes a counter offer. Both acceptance and breaking off from the opponent will result in ending the negotiations, but if the message is a counter offer, then our agent will try to calculate the next offer that it will give to the opponent

Since the agent doesn’t know any information regarding the opponent’s preferences, it has to try to create a model of opponent utility values in order to make an offer that is acceptable to the opponent, while still maintaining the agent acceptance value. An acceptance value is the value where the agent limits itself for which offer that it could accept. This value will decrease in time, since there is a limited time in negotiation. But the acceptance value will never be less than the agent’s reservation value.

The reservation value is the lowest utility value where the agent still possibly accept the offer from the opponent, but it will accept it only if both agent still haven’t decide anything while approaching the end of the negotiation time. Our reservation value is decided without any formalization. We just choose from the scale 0-100 and choose which one that seems reasonable. The following formula is the connection between acceptance value and reservation value.

The decision algorithm whether the agent will receive the offer from the opponent or not is quite simple:

As has been previously mentioned, the agent has to create a model of opponent utility values to calculate the offer that is acceptable for both parties. This model is evaluated every time the opponent gives an offer to our agent. In order to model the utility values of the opponent, our agent use a Bayesian learning method. First, our agent will form two matrices for every issue in the negotiation:

Where matrix A is the weight hypothesis and matrix B is the probability of the weight hypothesis. The values inside the matrix A are constant, where it ranges from 0-9 (in default, it could be easily change though) for each column and the values will be the same for each row.

The values inside the matrix B will be always in total of 1 for each column. At the initial condition, we will assume that the value for each column element is the same which is 1/n. The value m represent the number of choices in every issue and the value n represents the number of hypothesis that we use in this agent which is 10. Every time the opponent proposes an offer, the value of matrix B will also change. To calculate the values inside matrix B, we use the Bayesian learning equation:

From these two matrices, the agent will then try to model the opponent utility values for every issue by finding the product of matrix A and B. the result will be the model of opponent utility values for every choice in every issues. This production will always be calculated ever time the opponent gives an offer.

The matrix C will also changes every time the opponent gives an offer to the agent and each time our agent get an offer from the opponent, this model will update the values of matrix C in order to get a better representation of the opponent utility values.

After modeling the opponent’s utility values, our agent will try to calculate the best offer that it could give to the opponent. By using its utility values and the model of opponent’s utility values, the agent will try to come up with an offer which has a good utility value for the opponent while still trying to maintain the utility values for the agent itself which is greater than the acceptance value.

For calculating the offer will be given to the opponent, it is allowed to choose one of two methods available in the agent. The first method is a random method where the agent calculate every possible offer configurations that it could come up (for this assignment, we limit it for 500 configurations). The agent will compare the first offer that it come up with the next offer and keep the one that has highest utility value and it is not less than the acceptance value, and it will do this every time until the 500^th offer. For the second method, the agent will try to calculate the Pareto frontier outcomes based on both utility values (the agent’s and the opponent’s model) and later on, the agent will choose the outcome that has the highest utility for the opponent and later will propose that offer to the opponent.

The default setting for the agent is using the random method. There are several reasons why we choose the random method. It is not because the second method generate worse offer than the first but because the second method tends to give the same offer in several message exchanging. The consequence of this behavior is that the opponent has less opportunity to learn about our agent and therefore reduce the effectiveness of the negotiation.

Read More

A Probability Quiz

Clap clap clap...

And here you are... in the final stage of the most popular quiz in the world: "Where is the key?" (I made up the name in 5 seconds).

Ok, here is the situation. You have beaten all other contenders. Now they put 3 boxes in the front of you. One of them contain a dream vehicle's key that you always wanted. The other two is empty. Here's the deal: If you can guess which box contain the key then the key is yours (I'm not sure about the car but that's not the point). First you choose box number one. The quiz guy smirks. He (with the knowledge of what inside every boxes) removes box number two and he said that there's nothing in it, and yes, he's quite honest guy. Furthermore, out of his generosity, he offers you another chance. Whether it's to choose the box number one or box number three. You, being in the front of ten thousand audience, have to choose. What will you do?

This is a game of probability. Perhaps most of you realized that from the beginning. However, not all of us capable of calculating the correct probability of getting the right box (including me).

1. A spectator in front line doing his mathematic: he said that it doesn't really matter which box you choose. Because box number one and box number three have the same probability, which is a half.
2. A smart looking kid has a different perspective. At first, the three boxes have the same probability: 1/3. It means that you have a third chance of winning and a two third chance of failing. One of the other box, which is said to be empty, is removed. Removing one of the the box doesn't really affect your probability of winning. However, by removing one of the box and giving you another chance then you will have a better probability of winning by changing your choice.

As you probably can guess, a smart looking kid is no ordinary kid. By changing decision you actually have a probability of 2/3 to get the key. You don't believe it? Why don't you try it by yourself?

Read More

Artificial Intelligence in Reversi/Othello Game

One of the most interesting field in Artificial Intelligence (AI) is the computer game -at least that's what I think-. While The AI is not yet capable of creating a human-level robot, it's already useful in many ways and game is just one of them. Most of the computer games we play right now uses AI since sometimes (or most of the time) we just couldn't find anyone to play with. Probably you don't even care how AI in computer games work, but if you do and you want to learn something... this post might worth some of your time.

Here I'm going to use a simple case: a reversi (othello) game. For those of you who don't know what is reversi you may click here to get some ideas. In the reversi game, the goal is to beat your opponent by outnumbering the number of opponent's discs. While this game looked simple and easy, actually it's quite difficult to master it, especially when you realized that there's actually a world-level competition for this game. In the other hand, the level of AI created to play this game is already incredible compared to the level of AI in another games such as chess or go. To be more specific, human doesn't stand a chance against AI in a reversi game. Surprised?

Designing the AI for Reversi

First, we need to see the properties of reversi game. Let see if I could describe some of it:
1. Full Information: no game information is hidden
2. Deterministic: action determines the change of game states, no random influence
3. Turn-based: makes life easier ;)
4. Time limited: obviously... who wants to wait an hour just for a small move in the game?

OK, now it's time for practical matters. Let's say that the AI reversi represents as a computer agent. The agent need to decide its movement for every turn in reversi game. It has to find a "best" movement possible from some legitimates movements possible. Simply said, it is a searching problem. In order to exploit the greatness of computer in conducting a huge number of process in a short amount of time, we can use a minimax algorithm. Minimax algorithm is a decision function that try to maximize the result within the search space by assuming that the opponent is rational (always choose the best movement possible).

Here a simple example of Minimax:



Assume that you're moving first, and the opponent will have a chance to move right after your turn. The picture consists of several circles that represent a state. The value/number in the circles represent your score after two movements (one movement from you and one from the opponent) in that state. Obviously you want it as high as possible, and the opponent want to do the opposite. Lines that connect states is actions that may be conducted, each lines connect two states, the initial state and the outcome states that will be activated once the action is executed. The question is: from action A, B, or C... which one would you prefer? According to Minimax algorithm, the opponent is assumed as a rational agent (or human, whatever). Therefore, given the values in every states at level 2, the opponent should choose the best movement for it which is the minimum value from three possible states. Then, from our point of view, we have three values for three possible states which is -3, 1 and 0.



As a conclusion, action B is the best option according to the Minimax algorithm.

The Strategy

Let's take a nice look again to the pictures. We have a diagram of states with 2 ply and some values at the ending states. Where are those values come from? We may say that in a reversi game, those values are the number of pieces that our agent has compared to the opponent's. This might be true however with some limitations: you want to make a stupid agent or every last states should be the ending states (the end of the game). In most cases, it's not possible to make a search until the end of the game especially in the first several movements because the search space that could be computed is limited due to computational limitation. Therefore we need to use another values to put at the last states: evaluation function. Evaluation function could be something very simple such as the number of our agent's pieces to something that is very complex. Here is where the strategy take places. Rather than naively attempt to get as high as score possible, there are several features that should be use in order to design a evaluation function:
- mobility (the number of possible movement)
- the number of pieces that couldn't be flipped by the opponent (eg: pieces in the corners)
- positions value

Some more features might be useful, but using only these 3 features will make your agent relatively strong enough.

Some Other Things

Other than adding some more features, it also possible to add another things that might improve the agent's AI. Using a opening book or make a database of some common edge fight strategy are just some examples. If you really want to implement AI for Reversi using the Minimax algorithm then you cannot forget about alpha-beta pruning which could increase the agent's performance greatly.

Read More