AI Expert Newsletter

AI - The art and science of making computers do interesting things that are not in their nature.

March 2003

• Quantum Information - A different way of looking at things
• ER1 Robot - A product review
• Links
• The Best of AI Expert

We have quantum information and a commercial robot product review this month. As always, feedback is welcome. dennis@ddj.com

Quantum Information

Whenever we learn some fundamental different way of looking at things, our views of the familiar change. What was once obvious truth, becomes just a specific example of a broader, larger truth.

The ideas of quantum mechanics are expanding our fundamental understandings of information. Take logic for example.

We tend to understand logic as an abstract truth, a system of relationships not dependent on the physical world. Yet we developed logic to better describe our reality. In other words, the constructs of logic are determined by the physics we perceive.

Logical concepts of truth and falsehood correspond to physical states. A thing is or it isn't. Similarly, the logical operations 'and', 'or' and 'not' make sense in our physical world.

Computationally, one can represent logic with physical bits that are either on or off, representing true and false. Logical computations are carried out on machines, whose behavior is dictated by the same physics that underlies the logic. So it all works.

But as bits and logical operations get closer to the atomic level, the very strange physics of quantum mechanics start to come into play. No longer does the physics of the computer correspond to the physics underlying our system of logic.

A quantum bit can be both 0 and 1 at the same time. In other words, it can be true-false. These are called qubits. There are transformations on qubits that are theoretically possible at the quantum level. These are called quantum gates, corresponding to logic gates. Just as qubits stretch our notions of truth, quantum gates stretch our notions of logical operations.

For example, because of the strange properties of quantum mechanics it is possible to create two identical quantum gates that each seem to randomize their input, but when linked together negate it. In other words, these particular quantum gates might be called the square root of 'not', because when linked they create 'not'.

So here we have a logic concept, the square root of 'not', that doesn't make any sense in the Newtonian world we think we inhabit, yet makes perfect sense in the quantum world.

Where do these ideas come from? From people who are looking at quantum information theory. They see the potential of looking at information in light of what is theoretically possible at the quantum level. They are like Turing, imagining machines that illuminate our understanding of mathematics and logic.

One of their flights of fancy led to the observation that you can perform quantum operations on strings of qubits and those operations are performed on all the bits in each of its two possible states. In other words, you can perform operations on all large integers of a certain size, simultaneously.

This means there is a class of calculation that, while intractable on a conventional computer, can be performed in a flash on a quantum computer.

One such calculation is finding factors of large integers. Factorization of large integers takes an unrealistically long time. Numbers of a hundred digits take billions of years to factor on a conventional computer, yet a quantum computer can theoretically do it in less than a second.

And what good is that? Modern cryptography is based entirely on that sort of mathematical problem. The whole idea of dual encryption keys is that one can create a public key, used to encode information and another private key, based on factors, that is used to decode the information.

Multiplying numbers is easy; finding the factors is hard. So a private key composed of large integers is created. They are multiplied to create the public encoding key. The factors of the private key are mathematically in the public key, but it is computationally impossible to get them out.

This means the information can be encoded and sent in a public forum, and only the original holder of the private key, the factors, can decode it. The security of the private key is based on the fact that, even if an eavesdropper gets the public key, it is impossible to factor it to learn the private key, which never needs to be transmitted.

But with a working quantum computer, it becomes trivial to find the private key. As soon as someone builds a quantum computer, encryption as we know it fails. This has captured attention and funding for what started as flights of fancy.

Curiously, quantum mechanics provides an alternative solution for cryptography. The problem with the keys is transporting them between sender and receiver. The dual keys currently being used solve that problem, as the private key never got transported.

Photons can be sent from one person to another, with quantum information representing encryption keys. The physics of quantum mechanics dictates that there can only be one receiver of the information. If someone else viewed the information, it would be corrupted and easily detected.

Theoretically then, a key can be safely transmitted so the encoded document can safely be sent by conventional means.

So can you build a quantum computer? They're trying and the first results are in. They've built a quantum computer that can tell, with a single look, whether a coin is fair, with two different sides, or unfair, with both sides the same. OK, its not much, but its still pretty amazing, and a start.

http://www.qubit.org/ - The Centre for Quantum Computation, an overview organization with a number of excellent tutorials.

http://heart-c704.uibk.ac.at/DeutschJozsa.htm - A slide show on the quantum computer that can tell if a coin is fair or not.

ER1 Robot Review

Evolution Robotic's ER1 is based on an interesting idea. It is sensors, locomotion and a brain for a laptop PC. In other words, it's everything that devious machine needs to become truly dangerous. In fact, the manual warns against leaving the ER1 turned on by itself.

The manual also clearly stated that the robot should only be run on pure battery power, with no cords to wall sockets. Well the first USB hub I got didn't work self-powered, so I needed to plug it in and figured I could start anyway.

The 'hello world' application for the ER1 is a behavior that recognizes the box it came in and moves towards it. I showed it the box and it rolled a foot forward. Perfect.

So I casually threw the box to the side. Big mistake. The ER1 wanted to know where it went and started a spinning behavior to look for it. It was very quickly tying itself up in the cord, and I quickly learned how difficult it is to work the mouse on a spinning laptop. Disaster was avoided by lifting the wheels off the ground with one hand and working the mouse to stop the behavior with the other.

In other words, dealing with a looping program is harder when the computer has wheels.

I vowed to pay better attention to the warnings and got the Adesso AUH-103 USB hub that Evolution recommends.

Back to the beginning. One part of the ESB is a chassis for a laptop, with wheels, a camera, and optionally a gripper arm and additional sensors. The kit comes with modular tubing that can be connected in a variety of ways. I followed the instructions, building the standard cradle for the PC.

The other part is the Robot Control Center software which is installed on the PC. This is where the major value of the ER1 is.

One of the major issues in robotics is getting the robot to sense and react to its surroudings. The ER1 can be shown a variety of objects and learn to recognize them. It can then easily be programmed with behaviors that take certain actions when a known object is recognized.

Inspired by RoboCup, described in last month's newsletter, I decided to start programming soccer playing behavior. I first showed it a beach ball, and then two stacks of child's blocks which were the goal.

The ER1 scoring a goal.

What the ER1 saw.

I added two behaviors. When it saw the ball, it was to move forward, driving it ahead. When it saw the goal it would say "gooooaaal gooooaaaal gooooaaaal". (It uses text to speech to communicate.)

I set the ball in front of the ER1, and started the behaviors. Sure enough, it rammed the ball towards the goal and when it got close enough said the "gooooaaaal"s, but said them fast, flat and stuttered the vowels. The ER1 is not going to replace soccer announcers anytime soon.

The ER1 has obstacle avoidance behaviors as well, but I didn't experiment with them, as they seemed to run against the grain of my soccer experiments. (As a kid, I used to crash my electric trains into piles of blocks as well.)

I experimented with face recognition. I had hoped it could distinguish between a scary face and a friendly face, and go backwards or fowards depending on which one it saw, but it couldn't distinguish the two faces very well. That is something they are working on for future releases. But it did definitely recognize me, it just couldn't tell whether I was scary or not.

While the vision capabilities are the most exciting feature of the ER1, it also can recognize sounds, voice and color and use them for triggers of behaviors as well.

It has other capabilities with e-mail, timers, recording pictures, and remote operation which I didn't experiment with.

I was interested in pushing on with the soccer experiments, but ran into the classic software trade off of ease-of-use versus expressive power. The user interface for the Robot Control Center (RCC) is a very visual and very intuitive way to create production rules of the form "if this condition then take that action". One doesn't need to have any programming experience to enjoy experimenting with the possible behaviors of the ER1.

But the RCC interface is limited in its ability to only program relatively simple sequences of behaviors. Something more complex, like having the robot know where the goal is, find the soccer ball, and compute where to go to push the ball towards the goal, requires more direct programming of the ER1, and that can only be done using the C++ SDK for the ER1.

The C++ SDK should be available in beta by the end of this month. In addition to providing full programatic control of the robot, it also exposes the full power of the underlying Evolution Robotics Software Platform (ERSP).

https://www.evolution.com/product/oem/ has a full description of the ERSP, with technical white papers on robotic vision, navigation and other topics. These describe some very powerfull stuff, making it clear the ER1's RCC is only exposing the tip of the iceberg.

For example, the RCC is trained to recognize an object by simply showing it a picture of the object. It works well, and the object can be recognized with two-dimensional rotations, like if it is upside down, and at a variety of distances, and in a variety of lighting conditions. But clearly one picture can't be used to recognize an irregular three-dimensional object from various perspectives. The full ERSP allows a collection of images to be used for training object recognition.

I'm looking forward to seeing the C++ SDK.

Links

The Best of AI Expert

Finding Decision Rules with Genetic Algorithms [Mar 94] - There are a variety of techniques for extracting decision rules from a table of data representing choices. Jim Oliver describes a particularly clever one that uses genetic algorithms to zero in on the best rules.

Intelligent Road Transit: The Next Generation [Apr 94] - Denny Rock, Doug Hoskins and Don Malkoff provide an overview of work done at the time for automatic handling of traffic. The problems they describe seem similar to the ones the RoboCup soccer robots are trying to solve, that is, automonous agents working together.

Artificial Intelligence in Wargames [May 94] - Steve Estvanik provides an overview of AI techniques used to create realistic war games.