Posted by ljmacphee on January 30, 2008 under artificial intelligence in the news, bots, robotics | 
The zoologist and his colleagues discovered that when a swarm contains between 25 and 74 locusts per square metre, the locusts are almost always aligned but exhibit rapid and spontaneous changes in direction. There were almost no directional changes above that range of densities. [read more Sychronising the swarm]
So what does this mean for software and robotic swarms? Are there densities of particles in the swarm that will drastically change the behavior? Are swarm systems chaotic and if so what does that mean for designers of swarms? Many of the same simple rules we are using to program our swarms are based on insect swarms. So it isn’t a far reach to think that perhaps some of the odder previously thought to be unexplained behavior of insect swarms may show up in our software and our robot swarms at specific densities.
Swarms are being used in more real world applications. What happens if the swarm balancing network traffic on your server all aligns and sends all the traffic to one machine? Or more troubling what happens when US Military swarm based robots suddenly evolve new unexpected behaviors?
This is clearly an area that needs serious research in the very near future.
All is not bad, we can also use studies like this to predict crowd behavior in crowded situations using swarm models. Knowing at what crowd density the behavior changes can help us better design buildings and infrastructure preventing tragedies like the Rhode Island night club fire a few years back.
More information:
Boids ( Flocks, Herds and Schools: a Distributed Behavior Model )
The Application of Computational Models for the Simulation of Large-Scale Evacuations following Infrastructure Failures and Terrorists Events
Swarm-bots project
Posted by ljmacphee on January 28, 2008 under topics in artificial intelligence |
All games and all competitions can be represented by trees. Each node represents a place to make a decision, each edge represents a decision that can be made from that node. One of the simplest games we all know is tic-tac-toe. The game tree for tic-tac-toe has an root node with 9 edges. Each edge represents one of the 9 positions you can play if you are player one. The second level of nodes each have 8 edges. Each edge represents one of the remaining 8 positions open to player 2. The paths through the game tree for tic-tac-toe = 9! or 362,880 possible ways to play the game through to completion. So while tic-tac-toe is with in the realm of games the computer can fully solve while playing most games are not. One method used in artificially intelligent games to solve this problem is backward induction.
For example: You get a job transfer to Mars for 10 years. There are two possible jobs on Mars open to your spouse. One job pays $60/year, one job pays $100/year. You know that at the end of 10 years you will both be shipped back to Earth.
A lottery is held every year for the job openings, 1/2 are for the $60/year job, half are for the $100 a year job. Once you commit, that is your job until the trip home. At which point in time should your spouse stop holding out for the $100/year job and take the $60/job?
In year 10 the possibilities are $100/$60/$0 so the $60 job should be accepted.
In year 9 the possibilities are $200 for the $100/year job; $120 for the $60 year job. But if the spouse holds out there is a 50% chance of either. So 50%( $100 + $60 ) = $80. We have then $200/$120/$80. Take the bad job.
In year 8 we have possible earnings of $300/$180 or ( 50% * ($200 + $120 ) = $160 ). The bad job is a better choice than holding out.
In year 7 we have possible earnings of $400/$240 or ( 50% ( $300 + $180 ) = $320 ). Since the $320 is higher than the $240 we should hold out.
In year 6 and earlier it will be better to hold out and hope to do better in next years job lottery, in year 8 on it is better to take either job.
Now there are some big assumptions here. One is that everyone has all the information needed to make the decision. And two that your spouse won’t go stir crazy sitting on Mars with nothing to do. Another assumption which can lead to trouble is that backward induction assumes the players do not collude with each other.
In games you would use the final payoffs for each player to do your backward induction. In business backward induction is commonly used to guess what the competition will do in response to your moves in the market. While backward induction has been very successful in AI and in politics it won’t solve all game tree problems because we don’t always have all the information and there’s more to life than a paycheck.
Papers:
Is good algorithm for computer players also good for human players?
Posted by ljmacphee on January 25, 2008 under artificial intelligence in the news |
It’s getting near the end of the month and there were several news stories that caught my eye but that I didn’t have time to dig into and write a proper entry about. So I’m posting just some quick takes here.
A very cool project from the Shape Retrieval and Analysis group at Princeton involves the creation of a 3D-model search engine; queries to the engine can be keywords but also a hand drawn outline of the object to search for. The researchers have constructed a database of 36000 3D models and have developed a JAVA application that allows users to try out the system over the web. The image below shows an example query and the results returned for a 2D outline of a car. . . [ read more Artificial Intelligence and Robotics: 3D search engine ]
To protect your small or midsize company’s network against bots, you’ve first got to understand what bots do and how they do it. Cisco’s Jimmy Ray Purser unveils the dark side of network bots . . . [ read more ]
Details are still light on this one, but Sega Toys (makers of freaky robots) and the brain-reading folks at NeuroSky have announced that they’ve teamed up in an effort to develop what they’re only describing as “mind-controlled tech toys,” which they say will “take ‘play’ to the next level.” Those unspecified toys will apparently make use of NeuroSky’s ThinkGear bio-sensor technology which, according to the company, uses “dry active sensors” that eliminate the need for contact gels while also maintaining a small form factor. . . [ read more Sega Toys, NeuroSky Team up for "mind-controlled" toys ]
The way water striders walk on water was discovered years ago. The insect uses its long legs to help evenly distribute its tiny body weight. The weight is distributed over a large area so that the fragile skin formed by surface tension supports the bug on the water. However, the ability of water striders to jump onto water without sinking has baffled scientists, until now. [ read more Scientists Discover How to Make Robots Bounce on Water]
A scientist who successfully connected a moth’s brain to a robot predicts that “hybrid” computers running a combination of technology and living organic tissue will be available in 10 to 15 years.[ read more Moth Based Robot May Lead to Hybrid Computers ]
Posted by ljmacphee on January 23, 2008 under artificial intelligence in the news |
When the 2008 Olympic Games kick off in Beijing next year, organizers will be using a sophisticated computer system to scan video images of city streets looking for everything from troublemakers to terrorists.The IBM system, called the Smart Surveillance System, or S3, uses analytic tools to index digital video recordings and then issue real-time alerts when certain patterns are detected. It can be used to warn security guards when someone has entered a secure area or keep track of cars coming in and out of a parking lot. [ read more IBM System to Scan Streets at Beijing Olympics]
IBM’s system has a camera watching a scene, the video is analyzed in real time and behavior that is outside the statistical norm sends a warning to whoever needs it. Data is also analyzed and tagged with xml as it is read for easier retrieval.
Big Blue is far from the only company working on such software. BRS Labs is developing surveillance software which adaptively learns what is right and wrong in a scene.
We’ve had camera appearing and multiplying faster than any of us can keep track. But there are more cameras than watchers. In order for the cameras to be useful we need software like the red-light camera software that can act on its own. But there lies a whole new set of problems. How far should the camera software be allowed to act? And how far outside the norm does your behavior need to be to raise alarms and what should be done with people who set off these alarms?
More information:
IBM Smart Surveillance System ( Home page for the project including several papers, press releases and more information. )
Papers:
Automatic Video Surveillance
Automatic Annotation of Humans in Surveillance Video Recordings
Posted by ljmacphee on January 21, 2008 under source code, topics in artificial intelligence |
Synthetic psychology is a field where biological behavior is synthesized rather than analyzed. The father of such behavior Valentino Braitenberg ( home page ) did some interesting work with toy vehicles in the 1986 book “Vehicles: Experiments in Synthetic Psychology
“.
The Braitenberg vehicles were simple toy cars with light sensors as headlights. In some cars the wire for each headlight went to the real wheel directly behind it, in some the wires went to the opposite back wheel. The headlight receptors were aimed slightly off to the outside. The more light received by a receptor the faster the wheel wired to that receptor would turn.
Each vehicle exhibited realistic behavior when placed in a plane with several randomly placed light sources. A vehicle wired straight back when placed near a light source will then rush towards the light veering off as it gets closer to the light. As it gets more distant from the light sources the vehicle slows down. The reason is the wheel receiving the most light spins fastest turning the car away from the light source.
The vehicle with the crossed wires will turn and drive towards the brightest light in its field of view. The closer it gets, the faster it goes eventually running into the light.
Pretty interesting behavior from a very simple machine. But what if we add in a neurode to each wire and instead of a plain wire we use a wire that inhibits signals? Neurodes are set to only fire if they receive signals over a certain threshold. In this case zero is to be our threshold. So now our cars send signals to the wheels if there is no light, and do not send a signal if there is a light. Now the vehicle with the wires straight back moves toward a light and slows as it approaches, facing the light. The second vehicle now avoids light sources, speeding off to the darkest corner it can find.
So what has this all to do with current artificial intelligence? Some of our best stuff right now came from earlier work that was done and stopped. Some of our best mathematical algorithms come from extremely early math. And to remind you ( and me ) that simple rules can create very complex behavior in game characters and artificial life forms.
Four neurode versions of these vehicles have been built and they will exhibit more complex, non-linear behavior. “The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” (Edsger Dijkstra) At what point does the behavior become realist enough to be considered a life form?
Source Code:
Java simulation of Braitenberg Vehicles
More information:
Braitenberg Vehicles ( Java and Lisp simulators here )
Another simulation and pseudocode code here
Papers:
Robotics as an educational tool ( CiteSeer )
Swarm modelling. The use of Swarm Intelligence to generate architectural form. ( pdf)