Tuesday, June 22, 2010

Artificial intelligence


M
ost of us are familiar with the term Artificial intelligence or AI, which has been around since the 1940s. It's not to uncommon in Hollywood when it comes to doomsday films as The Terminator, AI(the movie), I Robot or Eagle Eye. So is AI going to doom us all? Well, no I don't think so ... the human race can handle that all by them selves. The area artificial intelligence is not strictly emergent, but emergent behavior underlays AI so I'm going to have it as a topic anyway because it's such widespread and basicly tries to emulate nature and the human brain.

Some techniques are strictly bruteforce, as many calculations as possible under an estimated time. For example - Deep Blue, the first computer to beat the reigning world champion in chess Garry Kasparov in 1997. The "AI" used for this task was mainly to foresee an amount of moves to a certain depth and make the most logical choise. This is not the kind of AI we will be focusing on, however emergent behavior underlays computational intelligence in a way.

As I've stated before, this blog if you may is for exploring thoughts around life and the emergent behaivor that sourrounds it.

However, AI is about making choises which best fits the situation. Wether it's playing chess, walking down stairs, or using abstract objects the AI makes choises based on what it "knows" about its environment. How it gathers that information can be done through numerous methods, or often in combination of methods.

Hold on to your hats or brifes, the following will contain many field buzzwords that may be confusing. I'm going to cheat a little bit and actually use the wiki approach dividing AI into three describing areas because we get a good preview of the subject, but avoid diving to deep into it.

Problems

Yes, every area has its sets of problems and AI has many. Why? Well for starters - we don't know how the object works that we are trygin to simulate. I'm talking about the worlds most advanced super computer which is replicated into about 6 billion copies. You guessed it - The brain.
Early AI researchers developed algorithms that imitated the step-by-step reasoning that humans were often assumed to use when they solve puzzles, play board games or make logical deductions
But we humans are far more complex and use our emotions and intuitive judgment as variables in the equation when we are faced with a problem or task. Our brain is not a statemachine which itterates through possible answer, its more of a quantum machine which calculates millions of options simultaneously, and into that mix also apply our personal experienc ande emotions. There is no chance of simulating that(yet). AI however has several fields to coup with these issues and tries to handle the same input that we humans get from our surroundings to make adjustments to it.

The Planning methology is to set a goal and reaching it. As we humans do when wee need to get from point A to point B. Here we can apply emergent behaivor as a model through Evolutionary algorithm and Swarm intelligence, much like the Boids approach we've been discussing. The natural next step is Learning, which has been the central research in AI from the very beginning. Without going into it we here apply Unsupervised learning, Supervised learning and reinforcement learning which are different approaches to solve the same problem in different situations. We have Natural language processing to deal with communications between digital system and humans through regular language. We've actually come quite far on this one! The last thing I'm going to list as a AI problem in Perception, input from our surroundings through our five sences. This is a big one in robotics where of course the visual perception has most focus. We are talking facial recognition and object recognition to build a internal representation of the world.

Approach

There are several different approaches where not all play well with eachother. AI is not a defined researcharea which relies on theorems like mathematics. What "AI" stands for can't be explained in a single sentence. First of all it depends on the angle you are looking at it - is it from a psykological view, or something else. Is the term AI and the result it produces of the same value by all standards? Well the quick answer is - No. Here are some examples how to approach AI. You will notice that most research are based around the 1970s or earlier so this is something that's been around before we got computerized.

In the 1940s and 50s research was made for exploring the possibilty of reducing human AI to symbolic representation. There were Cognitive simulation where psycological experiments were used for developing programs that simulated human problem solving techniques. This laid the foundation for Cognitive science which later formalized the research. Others claimed that simulating the human brain wasn't enough, and abstract reasoning och problem solving were more fitting - Logical based intelligence. Using formal logic later came to be the backbone in logical programming which evolved to programming languauges as Prolog. In later years when computers were more advanced a different type of AI emerged. It is now known as Knowledge based intelligence. Having more system memory the researchers were able to construct programs that held more information, and therefor beeing able to access more data than just split second input. From here the first "real" successfull AI programs were deployed and they are formaly know as expert systems. For example a doctor could use symptoms on a patient as input and get a list on possible diagnoses as a result. Though expert systems should never be an absolut factor when making decisions. It should rather be a support system taken under advice. An exceptional scenario is when subscribing medication for a patient. A expert system could instantly prevent a doctor from subscribing drugs which should not be mixed with eachother, or hinder a obvious wrong dosage.

The sub-symbolic approach came to be of greater interest in the 1980s when little faith was shown to regular symbolic AI when focusing on seriuous perception, pattern recognition and robotics. We now touch the area which this site focus on - Computional intelligence. Using more non-symbolic methods as neural network, fuzzy systems and evolutionary computing researcher were able to embody the AI more according to the embodied mind thesis, a related field in cognitive science. Roughly speaking it sais that the AI is determined by it's form of "human" body. This makes sence looking a the Boid system, an abstract method with a set of rules which is embodied by an agent or avatar.

Now it's time to stop ... you should now have a good idea of the foundation of AI in genreal terms. AI is what we do here on this site, but we only focus on selected parts ... the interesting ones =) But never the less, one should know the hole picture rather than a small corner.

- Tobias
Wednesday, June 16, 2010

Cellular Automata


I
think this one deserves an own topic. Cellular Automata, a model one might say strongly supported by Stephen Wolfram (author of A New Kind of Science). The technique first saw the light of day the 1940s by the hands of Stanisław Ulam who was studeing the growth of crystals and at the same time collaborating with John von Neumann who was working on a problem with self-replicating systems, the cellular automata was born.

A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired.
Well, that sais it all doesn't it? No I thought so. Cellular Automata does not have its foundation in mathematics or physics, it's more of a model based on rules and movements. A visual representation of calculations if you may, and the result is really not just a answer to lets say - an equation, it's more like a display colors, patterns and states for the eye to judge.

The most famous cellular automata is probably Game of Life, created by John H. Conway. Every cell in the grid applies three sets of rules which follows.
  1. Death: if the count is less than 2 or greater than 3, the current cell is switched off
  2. Survival: if (a) the count is exactly 2, or (b) the count is exactly 3 and the current cell is on, the current cell is left unchanged
  3. Birth: if the current cell is off and the count is exactly 3, the current cell is switched on
The result will look something like this, and no it's not a demo of a videogame from the 1970s.



Every cell only knows its closest neighbours, no predefined paths or patterns are followed. The result is totalt emergent, same as for the Boids model.

Amazingly, life is a universal cellular automaton, in the sense that it is effectively capable of emulating any cellular automaton, Turing machine, or any other system that can be translated into a system known to be universal
This basicly means that a cellular automata can reproduce any system which by definition is universal. This is pretty powerfull stuff, and I recall reading about cellular automata beeing used for reproducing fungus growth on a microscopic level. Though I've failed to find a reference for this, but I will add it as soon as I do find it.

If we take a step into the 2100 century a demonstration of the cellular automata looks like this.



If you ask me, this looks like life under a microscope. Well, parts of it anyway. I will return to the cellular automata, but for now I will leave it to you for further reading.

- Tobias
Tuesday, June 15, 2010

The Computational Beauty of Nature


A
nother good reading that I recommend is "The Computational Beauty of Nature" by Gary William Flake.


A very illustrative book which covers the most fundamental parts of emergent behaivor. Not at all as heavy as A New Kind of Science, with consideration to the body and mind.

- Tobias

A New Kind of Science


F
or some heavy reading, and I mean both physically and psychologically I recommend "A New Kind of Science" by Stephen Wolfram, the founder of Mathematica and a driving force behind Cellular Automata.

This thing consists of 1197 pages(!) and is not something you want to fall asleep under when laying in bed. However, the chanses of that are slim when you most likely won't be able to hold it for a longer period of time(yes, it's heavy).

- Tobias

Fractals


F
irst of all, fractals are a bloody huge area which we are going to come back to several times, but for now I will settle with a brief introduction. The short description is - A fractal is natures answer to lego. Well, not quite but to some extent.

A fractal is a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole, a property called self-similarity.
This is a fairly fitting description, but I will try to level it out even more. Note that I do not intend that readers must have a M.Sc degree in physics, mathematics or computing science to understand what I'm talking about. This blog is for everyone with an interest nomatter background. I may at times digg deeper in certain areas, applying theories with programming which WILL be hard to understand if you lack certain knowledge. But, I will do my best explaining it in simpler form.

So, back to fractals. They can take many forms and shapes, litteraly and the applicible areas are numerous. But as I said from the begining fractals can roughly be described as natures lego. By applying fractal design you can generate objects taken from real life and the varity is huge. From mountains and landscapes down to trees, bushed and plants. Fractals, when combined produce patterns and the most famous must be the Mandelbrot Set displayed to the left in the picture below.

Notice the pattern, you see it? Now look att the second picture to the right. Do you see it? Same pattern and doesn't that remind you of a snowflake? I'm not going into the mandelbrot fractal further, it's to complex for me to describe on this blog and there are several mathematical aspects of it so I'm just going to leave it up to you.

Moving on - life will find a way. Or God found a way, the lazy bastard , to generate land, mountains, trees and plants using "only" one key element. Building fractal mountains is fairly simple and a quick way of illustrating this is done in here. The site contains code for all you programmers out there, and at the end of the article the owner has posted links and compiled code for you none-programmers.

Download the Win32 binary, unzip it and execute the exe file and play around to get an idea how fractal mountains are generated. The more iterations you make, the more detailed mountains you get. If you were to add texture to this model you would get something like the picture to the right. Of course this mountain has been generate in a more complex way, but the same theory is applied.

If we take it down a notch or two, we get trees and plants. If generating mountains and landscapes were fun, this will surely twist your eyes.

To the left we have beautiful corals and to the right every kids favorite - Broccoli. See the twists and re-appearing patterns, fractals in its most exquisite form.

- Tobias
Monday, June 14, 2010

Boids


The most famous technique, if there is one, must be Craig Reynolds "Boids". Developed in 1986 Craig Reynolds made a computer model of coordinated animal motion such as bird flocks and fish schools. Speaking for myself, this model is the foundation of emergent behaivor ... it was this model that got me interested, and got me thinking in other directions. It's quite simple really, but the result is far more complex ...

(from the left)
Alignment: steer towards the average heading of local flockmates
Cohesion: steer to move toward the average position of local flockmates
Separation: steer to avoid crowding local flockmates

I told you, simple ... but look at the result when the rules interact with eachother.







Calculations between birds(boids - agents in the simulation) are made in realtime. The result is quite amazing. Hence, the clip above also have an extra rule which can be called Avoidance - Stay clear of a specifik object. As you now may have realized - yes, you can add more rules to the simulation. Giving each agent a new behaivor which combined with the existing rules may result in something completely unexpected. That's the tricky thing with emergent systems, simple alterations may have a bigger impact in the full aspect than one may come to expect.

This technique has come to be VERY popular in games and movies, we have all seen the Lord of the Ring trilogy where it's adapted in several scenes. But not just new films, remember "The Lion King" from 1994 where Simba is chased in the ravin by herd av gnus?

I'm going to leave the subject for now and stay clear of the hard core tech parts, but I will return to it later. Don't forget to visit Craig Reynolds to take part of his work in the area. Did I mention that he nowdays work at Sony Entertainment, I wonder why =)

-Tobias