AI - The art and science of making computers do interesting things that are not in their nature.
- Quantum Information - A different way of
looking at things
- ER1 Robot - A product review
- Links
We have quantum information and a commercial robot product review this month. As always, feedback is welcome.
[email protected]
Quantum Information
Whenever we learn some fundamentally 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 a flight 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 it's 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 a devious machine needs to become truly dangerous. In fact, the manual warns against leaving the ER1 turned on by itself.
The manual also clearly states 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 toward 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 the ball ahead. When it saw the goal it was to 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 toward the goal, and when it got close enough it 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 involving 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 tradeoff 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 toward 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 - Coming Soon
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.
Until next month,
Dennis Merritt
[email protected]
