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

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

Minimax Pseudocode

Last year I wrote a post about AI in reversi using minimax algorithm with alpha beta pruning. However, it said nothing about the implementation. So, for you guys who already grabbed the idea of minimax but still having some troubles in implementing it, here's a pseudocode that might help you with. It's not something that I wrote by myself, but the idea is somewhat similar.

minimax(in game board, in best_opposing_score, out score chosen_score, out move chosen_move)
begin
best_score = -infinity;
Gt_generate_moves(current_mimx_data,moves_list);
for (i = 0 to moves_list.num_moves-1) do
new_board = board;
Gt_move(board, moves_list[i],the_unmove);
minimax(board, the_score,the_move);
Gt_unmove(board,the_unmove);
if (the_score > best_score) then
best_score = the_score;
best_move = moves_list[i];
if (best_score > best_opposing_score) then
cut;/* the opponent will not allow you to reach this node*/
endif
endif
enddo
chosen_move = best_move;
Gt_evaluate(current_mimx_data,chosen_score,best_score);
end.

Related post

• http://www.cs.caltech.edu/~petrovic/games/archex/othellodir/node2.html (external)

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

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