'PEBBLE PICKING GAME' APPLICATION OF AI

The  science and engineering of making intelligent machines is AI. It is Task of using computers to understand human intelligence reasoning, knowledge, planning, learning, communication, perception and the ability to move and manipulate objects. Intelligence involves mechanisms, and AI research has discovered how to make computers carry out some of them. "Intelligence" which at present is an abstract and immeasurable quantity. We cannot yet characterize in general what kinds of computational procedures we want to call Intelligent. We understand some of the mechanisms of Intelligence. Intelligence helps in identifying the right piece of knowledge at the appropriate instances of decision making.


We understand some of the mechanisms of intelligence. Mechanisms that are well understood today, computer programs can give very impressive performances on these tasks. Such programs should be considered somewhat Intelligent.  "Artificial Intelligence" thus can be defined as the simulation of human intelligence on a machine, so make the machine efficient to identify and use the right place of "Knowledge" at a given step of solving a problem.


Intelligent  must be able to set goals and achieve them. Able to make choices that maximize the utility or "value" of the available choices. The field of robotics is closely related to AI. Intelligence is required for robots to be able to handle such tasks as object manipulation and navigation with sub-problems of knowing where you are,mapping (learning what is around ) and motion planing.


computer simulates the psychological learning process of animal, learning by correcting and not repeating the mistakes.In game of pebble picking a multidimensional array of elements is chosen as the instruction book for the computer to pick the pebbles. The instruction book contains  instructions to pick pebbles. This instructs to pick a single pebble, and then  instructs to pick 2 and  instructs to pick 3 pebbles. At the beginning, computer chooses a random page and a random line of instruction to pick the pebble.

When the game finishes, if computer looses the game, the last instruction is red-marked (erased) and the instruction will not be read in the future. After playing many games, all the instructions leading to a lost game will be red marked and there will be left only the instructions those lead to a win. last it finds all its mistakes and corrects them to become an unbeatable champion.So this is how we are increasing probability of wining the game. However when a human being learn from mistakes he just uses common observation and improve the strategy.

The subject of artificial intelligence has been enriched with a wide discipline of knowledge from Philosophy, Psychology, Cognitive Science, Computer Science, Mathematics and Engineering.The subject of artificial intelligence was originated with game-playing and theorem-proving programs and was gradually inserted  with theories from a number of parent disciplines. As a young discipline of science, the significance of the topics covered under the subject changes considerably with time. Among the application areas of AI, we have Expert systems, Game-playing, and Theorem-proving, Natural language processing, Image recognition, Robotics and many others.
references
1)http://delphi.about.com/od/gameprogramming/a/aigamesample.html
2)http://www-formal.stanford.edu/jmc/whatisai/node4.html
3)http://en.wikipedia.org/wiki/Artificial_intelligence
                                                                                                                                                                         praveen kumar 
                                                                                                                                                                         na09b019

KISMET Robot

Introduction:
Kismet is a robot made in the late 1990s at Massachusetts Institute of Technology with auditory, visual and expressive systems intended to participate in human social interaction and to demonstrate simulated human emotion and appearance. The name Kismet comes from the Arabic, Turkish, Urdu, Hindi and Punjabi word meaning "fate" or sometimes "luck"
Hardware design and construction:
In order for Kismet to properly interact with human beings, it contains input devices that give it auditory, visual, and proprioception abilities. Kismet simulates emotion through various facial expressions, vocalizations, and movement. Facial expressions are created through movements of the ears, eyebrows, eyelids, lips, jaw, and head. The cost of physical materials is an estimated US$25,000.
Four color CCD cameras mounted on a stereo active vision head and two wide field of view cameras allow Kismet to decide what to pay attention to and to estimate distances. A .5 inch CCD foveal camera with an 8 mm focal length lens is used for higher resolution post-attentional processing, such as eye detection.
By wearing a small microphone, a user can influence Kismet's behaviour. An auditory signal is carried into a 500 MHz PC running Linux, using software developed at MIT by the Spoken Language Systems Group that can process real-time, low-level speech patterns. A 450 MHz PC running NT processes these features in real-time to recognize the spoken affective intent of the caregiver.
In addition to the computers mentioned above, there are four Motorola 68332s, nine 400 MHz PCs, and another 500 MHz PC.
Maxon DC servo motors with high resolution optical encoders are positioned to give Kismet three degrees of eye movement, which allow it to control gaze direction and gives Kismet the ability to move and orient its eyes like a human. This allows Kismet to simulate human visual behaviors. It also allows humans to assign a communicative value to eye movements and to allow Kismet to focus on what it deems important in its field of vision. Software system
Kismet's social intelligence software system, or synthetic nervous system (SNS), was designed with human models of intelligent behaviour in mind. It contains six subsystems as follows.
Low-level feature extraction system:
This system processes raw visual and auditory information from cameras and microphones. Kismet's vision system can perform skin-color detection, eye detection, and motion detection. Whenever Kismet moves its head, it momentarily disables its motion detection system to avoid detecting self-motion. It also uses its stereo cameras to estimate the distance of an object in its visual field, for example to detect threats -- large, close objects with a lot of movement.

Kismet's audio system is mainly tuned towards identifying affect in infant-directed speech. In particular, it can detect five different types of affective speech: approval, prohibition, attention, comfort, and neutral. The affective intent classifier was created as follows. Low-level features such as pitch mean and energy (volume) variance were extracted from samples of recorded speech. The classes of affective intent were then modeled as a gaussian mixture model and trained with these samples using the expectation-maximization algorithm. Classification is done with multiple stages, first classifying an utterance into one of two general groups (e.g. soothing/neutral vs. prohibition/attention/approval) and then doing more detailed classification. This architecture significantly improved performance for hard-to-distinguish classes, like approval ("You're a clever robot") versus attention ("Hey Kismet over here").

Attention system:
Kismet's attention system selects stimuli in its environment to direct the robot's attention and gaze to, for example if something suddenly appears. The system has two stages: pre-attentive, which uses the low-level visual feature detectors to detect colors and motions, and a limited capacity stage which processes a certain region in the visual field. For example, facial expression recognition or object detection is done in the limited capacity stage. This attention system is influenced not only by external factors, but by Kismet's current task at hand (seek-people vs. seek-toys) or habituation (its limited attention span).
High-level perceptual system:
Kismet's perceptual system translates low-level features into meaningful events. This is done through releasers. A releaser is a kind of checklist, which assesses a combination of low-level features to decide what kind of event it is. For example, "big, fast motion, and close" will indicate a threat.
Motivation system:
The motivation system coordinates Kismet's drives and emotions. The drive subsystem regulates Kismet's social, stimulation and fatigue related needs. Like in an animal that has a level of hunger, each drive becomes more intense until it is satiated. These drives affect Kismet's emotion system, which contains the 6 basic emotions as described by Paul Ekman: anger, disgust, fear, joy, sorrow, surprise. In addition, it contains three arousal states: boredom, interest, and calm. These emotional states can activate behaviors. For example, the fear emotion can induce the escape behavior.
At any given moment, Kismet can only be in one emotional state at a time. However, Breazeal states that Kismet is not conscious, so it does not have feelings.
Behavior system:
Kismet's behavior system decides what behavior to carry out. Behaviors include play with toy, greet person, sleep, and so on. Each behavior receives input from the emotion system, drive system, and various releasers. The values from these modules are combined to produce an activation level value for each behavior. If the activation level of the behavior reaches a certain threshold, Kismet performs the associated behavior.

Motor system:
The motor system controls Kismet's body posture, facial expressions, speech and lip synchronization, and gaze direction. The robot has 9 basis postures, or expressions: fear, accepting, tired, content, stern, disgust, anger, surprise and unhappy. However, Kismet's emotion space is continuous, not discrete. For example, if Kismet shows an unhappy posture and the observer start speaking in a soothing voice, Kismet's expression can smoothly transition to accepting. In addition to facial features such as eyebrows and mouth shape, Kismet can also change the orientation of its ears. For instance, arousal is conveyed by pointing its ears upward.
Kismet speaks a proto-language with a variety of phonemes, similar to baby's babbling. It uses the DECtalk voice synthesizer, and changes pitch, timing, articulation, etc. to express various emotions. Intonation is used to vary between question and statement-like utterances. Lip synchronization was important for realism, and the developers used a strategy from animation: simplicity is the secret to successful lip animation. Thus, they did not try to imitate lip motions perfectly, but instead create a visual short hand that passes unchallenged by the viewer.
In the media:
Kismet has been featured on NBC as well as Discover magazine and is the project of Cynthia Breazeal. It also played a small role in the Steve Reich opera Three Tales, as a symbol of the development of artificial intelligence, and also a voice of traditional ethics.
A replica of Kismet is part of a traveling exhibit along with Breazeal (in a pre-recorded segment) in the Star Wars: Where Science Meets Imagination exhibition.

Computer Chess as an Artificial Intelligence

Definition: Artificial intelligence is defined as intelligence exhibited by artificial(man made, non natural ) entity. AI forms a vital branch of computer science, dealing with intelligent behavior in machines. The field was founded on the claim that a central property of humans, intelligence—the sapience of Homo sapiens—can be so precisely described that it can be simulated by a machine.

                   The central problems of AI include such traits as reasoning, knowledge, planning, learning, communication,perception and the ability to move and manipulate objects. General intelligence (or "strong AI") is still among the field's long term goals. One major limitation is that AI does not have common sense knowledge. In AI such as computer chess, emotion and social skills play two roles for an intelligent agent. First, it must be able to predict the actions of others, by understanding their motives and emotional states. A sub-field of AI addresses creativity both theoretically (from a philosophical and psychological perspective) and practically (via specific implementations of systems that generate outputs that can be considered creative, or systems that identify and assess creativity).

Chess :The game of chess has fascinated human thinkers and strategists for thousands of years. Relentlessly complex, yet accessible to amateurs, it remains both the definitive strategic board game (with a nod to Go) and the board game most studied, by far,  by computer scientists and game theorists.

                  So exactly why did chess AI explode in the 1970’s?  First, the game has massive appeal to gamers of a strategic mindset who are capable of abstract thinking, and for those of us who enjoy complexity. Since this pretty much defines a “computer scientist”, we can see that chess is, simply put, the perfect environment for artificial intelligence. After all, chess is a game of perfect information. The environment is totally observable, and there are a finite, though astonishingly high, amount of valid positions: about 10^50 estimated unique legal positions. For the shock value, we’ll write it out:

10000000000000000000000000000000000000000000000000. (give or take a billion)

                Some physicists have estimated the number of particles on earth to be around the same number.  This level of complexity demands AI exploration. The chess AI explosion began in the 1970’s and quickly ramped up – the first chess agents used exhaustive brute force searches, but limits on  memory and CPU speed forced programmers to adopt more clever methods to “prune” the number of positions considered by the computer, and adopt them they did. The chess AI scene culminated with the famous Gary Kasparov vs. Deep Blue (IBM) match in 1997. Deep Blue beat Kasparov in a six game exhibition match.  Kasparov’s notes were telling:

“The decisive game of the match was match 2, which left a scar in my memory…we saw something that went beyond our wildest expectations of how well a computer would be able to foresee the long-term positional consequences of its decisions. The machine refused to move to a position that a decisive short-term advantage – showing a very human sense of danger"

               AI began as an attempt to answer some of the most fundamental questions about human existence by understanding the nature of intelligence, but it has grown into a scientific and technological field affecting many aspects of commerce and society.Even as AI technology becomes integrated into the fabric of everyday life, AI researchers remain focused on the grand challenges of automating intelligence. Work is progressing on developing systems that converse in natural language, that perceive and respond to their surroundings, and that encode and provide useful access to all of human knowledge and expertise. The pursuit of the ultimate goals of AI -- the design of intelligent artifacts; understanding of human intelligence; abstract understanding of intelligence (possibly superhuman) -- continues to have practical consequences in the form of new industries, enhanced functionality for existing systems, increased productivity in general, and improvements in the quality of life. But the ultimate promises of AI are still decades away, and the necessary advances in knowledge and technology will require a sustained fundamental research effort.

References: http://en.wikipedia.org/wiki/Computer_chess

                        http://en.wikipedia.org/wiki/Artificial_intelligence

-

Sunaina D

EE09B037 
 

                         

“The history of AI is a history of fantasies, possibilities, demonstrations, and promise” - AI in T9 (Predictive Text)

I find the most outstanding feature of the T9 text to have been its ability to make predictions (Planning) and to find patterns in a stream of input (Learning).

Firstly, what is AI?

Artificial intelligence (AI) is the intelligence of machines and the branch of computer science that aims to create it. It is the study and design of an intelligent agent that perceives its environment and takes actions that maximize its chances of success.

The field was founded on the claim that a central property of humans, intelligence—the sapience of Homo sapiens—can be so precisely described that it can be simulated by a machine. Artificial intelligence has been the subject of optimism, but has also suffered setbacks and, today, has become an essential part of the technology industry, providing the heavy lifting for many of the most difficult problems in computer science.

What is T9 (Predictive Text)?

T9, which stands for Text on 9 keys, is a patented predictive text technology for mobile phones, originally developed by Tegic Communications, now part of Nuance Communications.

Design

• T9's objective is to make it easier to type text messages. It allows words to be entered by a single keypress for each letter, as opposed to the multi-tap approach used in the older generation of mobile phones in which several letters are associated with each key, and selecting one letter often requires multiple keypresses.
• It combines the groups of letters on each phone key with a fast-access dictionary of words. It looks up in the dictionary all words corresponding to the sequence of keypresses and orders them by frequency of use.
• Learning: It determines what category(frequently or rarely used) the word belongs in, after seeing a number of word texts. As it gains familiarity with the words and phrases the user commonly uses, it speeds up the process by offering the most frequently used words first and then lets the user access other choices with one or more presses of a predefined Next key.
• New Word additions: The dictionary can be expanded by adding missing words, enabling them to be recognized in the future. After introducing a new word, the next time the user tries to produce that word T9 will add it to the predictive dictionary.
• Replacing Text
• Replacing TextReordering of New Words
• Prioritizing: The prioritizing function is used to manage the number of user defined words. These words are prioritized according to the frequency of usage. When not used frequently, the words can be deleted, thus maintaining the size of the List. The permanent words have NULL priority.
• Word Editing: When an already typed word is modified, the dictionary pointer location is moved to the most probable complete word present in the dictionary. If it exists, the word is replaced by the modified extended word. If it does not exist, the word is considered as a new word and then NewWord addition procedure is followed.

The graphs in Fig.1 give the relation between the Skip Number and Total Count. Skip Number denotes the number by which the pointer moves in one attempt during the searching of the word in the dictionary. The Total number of moves by the pointer in the process is given by Total Count. Based on the graphs for a few sample words, the optimum Skip Number can be obtained.

                          

                          

 


                               Fig. 1(a...e).  Skip Number vs. Total Count

The graph in Fig.2 gives the number Graph showing number of movements of Dictionary Position before reaching the Word.

Features

• Some T9 implementations feature smart punctuation. This feature allows the user to insert sentence and word punctuation using the '1'-key. Depending on the context, smart punctuation inserts sentence punctuation (period) or embedded punctuation (period or hyphen) or word punctuation (apostrophe in can't, won't, isn't as well as the possessive 's). Depending on the language, T9 also supports word breaking after punctuation to support clitics such as l' and n' in French and 's in English.
• The UDB is an optional feature which allows words that were explicitly entered by the user to be stored for future reference. The number of words stored depends on the implementation as well as the language.
• In later versions of T9, the order of the words presented adapts to the usage pattern. For instance, in English, 4663 matches "good", "home", "gone", "hood", etc. Such combinations are known astextonyms; e.g., "home" is referred to as an textonym of "good". When the user uses "home" more often than "good", eventually the two words will switch position. Information about common word combinations can also be learned from the user and stored for future predictions.
• For words entered by the user, word completion can be enabled. When the user enters matching key-presses, in addition to words and stems, the system will also provide completions.
• In later versions of T9, the user can select a primary and secondary language and matches from both languages are presented. This enables users to write messages in their native as well as a foreign language.
• Some implementations also learn commonly used word pairs and provide word prediction (e.g. if you often write "eat food", after entering "eat" the phone will suggest "food" and it can be confirmed by simply pressing next).
• Auto correction: Another powerful feature is its ability to automatically recognise and correct typing/texting errors, by looking at neighbouring keys on the keypad to ascertain an incorrect keypress. For example, the word "testing" would be entered with the key combination "8378464". Entering the same number but with two incorrect keypresses of neighbouring keys, e.g., "8278494" still results in T9 suggesting the words "tasting" (8278464), "testing" (8378464), and "tapping" (8277464).

The data structure used in T9 Dictionary

A trie for keys "A", "to", "tea", "ted", "ten", "i", "in", and "inn". In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings.

Algorithm

In order to achieve compression ratios of close to 1 byte per word, T9 uses an optimized algorithm which maintains the order of words, and partial words (also known as stems) but because of this compression, it over-generates words which are sometimes visible to the user as 'junk words'.
http://www.acadjournal.com/2003/v10/part1/p1/   - The algorithm has three modules, Dictionary Module, Temporary File Module, Window Module

Intelligence

• Deduction, reasoning, problem solving: Algorithm imitates the step-by-step reasoning that humans were often assumed to use when they solve puzzles, play board games or make logical deductions. Highly successful methods for dealing with uncertain or incomplete information; concepts from probability and economics are employed.
• Knowledge representation: The algorithm will require extensive knowledge about the world. 
  

  “Knowledge about knowledge (what we know about what other people know)”

• Planning: It periodically checks if the word matches its predictions and changes its plan as this becomes necessary, requiring the agent to reason under uncertainty.
• Natural language processing: Gives machines the ability to read and understand the languages that humans speak.
• Social intelligence: For good human-computer interaction, an intelligent machine also needs to display emotions; smileys ( J L K ) are used here.

Relationship with Users

On a typical telephone keypad, groups of letters in alphabetical order are associated with numeric keys. The user sequentially presses the numeric keys which represent the letters in the numeric keypad (a key press per letter), thus building the words sequentially.  The algorithm also searches sequentially moving from one possibility to another in the added word list as and when the user presses the next numeric to represent the succeeding letter in the word. Since the user cannot type in more than three words a second, the program would appear to perform no steps at all because of its effective search. Moreover the program exploits human limitation of sequential text entry to perform a sequential search thereby going in par and even better than human typing speed. This is comparatively faster to the word guessing algorithm by which words are formed and cross checked with the words present in the word list. The word guessing algorithm also waits for the user to complete typing the entire word and then searches for the most probable combination.

By claiming to be able to recreate the capabilities of the human mind, the T9 Predictive Text proves to be a good AI project.

- MANEKA

  BT09B009

REFERENCES:

http://en.wikipedia.org/wiki/T9_(predictive_text)

Artificial Intelligence VS Natural Intelligence (Speech Recognition)

‘Artificial’, as the name suggests, refers to something which is man-made. Right from food flavoring to satellites, human beings have successfully created artificial versions of almost every natural thing. All these could be possible only because of one asset which human beings have endowed, ‘Intelligence’.


It has been well said that human imagination can travel faster that light. So fast that, it could even imagine the possibility of creating Artificial Intelligence (AI). Science fiction writers have used the possibility of intelligent machines to advance the fantasy of intelligent non-humans, as well as to make us think about our own human characteristics.


In the last half century, the AI community has been able to build experimental machines that test hypotheses about the mechanisms of thought and intelligent behavior and thereby demonstrate mechanisms that formerly existed only as theoretical possibilities. The history of AI is a history of fantasies, possibilities, demonstrations, and promise. Now let us start with an interesting question:

“What is the difference between human intelligence and artificial intelligence?”

From a random web search, I came across this:

“Natural is your brain and artificial is google.com, but google.com was made by natural intelligence, in fact, all artificial intelligence comes from natural intelligence but no natural intelligence is from artificial intelligence.”

The difference between Natural Intelligence (e.g human intelligence) and Artificial Intelligence is hard to define, as not much is known about natural intelligence (NI). AI can learn, just like NI. When programmed to, AI can sense changes in its environment and react accordingly. It can then refer to the ways it reacted to previous changes to help decide what to do the next time a similar change occurs.

One big difference between Artificial Intelligence and Natural Intelligence is the fact that NI can forget and lose information. AI could do this only if it was program to do so, but this would be counter-productive. Another big difference is accuracy. AI, when given the same information can be exact, every time with speed. When NI is given the same information, it cannot be as exact, and is slower.

I discovered a couple of very interesting things few years back when I came across the computer software, ‘Dragon Naturally Speaking’. Dragon NaturallySpeaking is software that allows us to speak into a microphone device, and the computer will type out everything we say.

Whenever we talk to a new person our brain grasps certain characteristic features of that person which helps us to recognize that person, his face, his voice, in the future. A small talk is enough for it. But unlike the human brain, the artificially intelligent computer cannot do it so easily. When running naturally speaking for the first time, we need to make a user profile for ourselves. Then, we must train our voice with the new software. In other words, making the computer familiar with our voice so that it recognizes it next time, along with all the custom words we might have saved. This is done simply by reading some text into the microphone.

The most important thing in any speech recognition software is to speak clearly. The human mind knows what words are and how they are used, but a computer does not know what a word means. It cannot use assumption based skills to figure out what we are trying to say. For example, when I dictate the sentence, “I want to eat an ice-cream”, the computer might as well type, “I want to eat an I Scream”. (Also words like "four" and "for", and "red" and "read"). A human being is smart enough to figure out that ‘…I Scream’ is irrelevant with the phrase ‘I want to eat an…’. So it understands that it has to be ‘Ice Cream’ which is edible.

Can we expect the same thing from the computer?

Well, to some extent, yes. With repeated use of certain kind of words with certain phrases, the computer does learn from its mistakes. So the golden rule of dictation is to not our hands (in other words type) while we are dictating. There are a couple reasons for this; one is that we are robbing the software of an opportunity to learn from its mistakes. As we use the software and correct it, it learns and improves. This information is stored in our profile.

Considering all the pros and cons, I am actually amazed at how well it knows my voice. Granted, it does make some mistakes, but it is merely types what we say. And it does a great job at that. Kudos to speech recognition and artificial intelligence!

Saptarshi Prakash,

EE09B076,

http://www.saptarshi.co.nr/

References:

http://www.nuance.com/dragon/index.htm

http://answers.yahoo.com/