Tag Archives: Algorithms

Learning Graffiti.

Knowing for the sake of knowing: algorithm developed to hardwire curiosity into robots

To better flesh out artificial intelligence (AI), computer scientists have put together an algorithm that makes machine curious to explore and learn simply for the sake of learning. In the long run, such programs could even take bots out of the factories and put them side-by-side with researchers.

Learning Graffiti.

Sage advice.
Image credits Gerd Altmann.

The concepts of intelligence and curiosity feel so deeply entwined to us that it’s almost impossible to imagine one going very far without the other. And yet even the most powerful machine brains we’ve built up to now have had to make do without any kind of curiosity — computing and returning an answer when instructed to, going to the screensaver in the absence of input.

It’s not like we’re only figuring this out now. Scientists have been working on various ways to imbue our silicone friends with curiosity for quite some time now, but their efforts have always fallen far under the benchmark set by our innate inquisitiveness. One important limitation, for example, is that most curiosity algorithms can’t determine whether something will be interesting or not — because, unlike us, they can’t assess the sum of data the machine has in store to see potential gaps in knowledge. By comparison, you could tell with a fairly high confidence if a book will be interesting or not without reading it first.

Judging books by their cover

But Todd Hester, a computer scientist currently working with Google DeepMind in London, thinks that robots should actually be able to go against this morsel of folk wisdom. To that end, he teamed up with Peter Stone, a computer scientist at the University of Texas at Austin to create the Targeted Exploration with Variance-And-Novelty-Intrinsic-Rewards / TEXPLORE-VENIR algorithm.

“I was looking for ways to make computers learn more intelligently, and explore as a human would,” he says. “Don’t explore everything, and don’t explore randomly, but try to do something a little smarter.”

The way they did so was to base TEXPLORE-VENIR on a technique called reinforcement learning. It’s one of the main ways humans learn, too, and works through small increments towards an end goal. Basically, the machine or human in question tries something, and if the outcome brings is closer to a certain goal (such as clearing all the board in Minesweeper) it receives a reward (for us it’s dopamine) to promote that action or behavior in the future.

Reinforcement learning works for us — by making stuff like eating feel good so we don’t forget to eat — and it works for machines, too — it’s reinforcement learning that allowed DeepMind to master ATARI games and Go, for example. But that was achieved through random experimentation, and furthermore, the program was instructed to learn the game. TEXPLORE-VENIR, on the other hand, acts similarly to the reward circuits in our brains by giving the program an internal reward for understanding something new, even if the knowledge doesn’t get it closer to the ultimate goal.

Robot reading Mythical Man.

Image credits Troy Straszheim / Wikimedia.

As the machine learns about the world around it, TEXPLORE-VENIR rewards it for uncovering new information that’s unlike what it’s seen before — exploring a novel patch of forest, or finding a new way to perform a certain task. But it also rewards the machine for reducing uncertainty i.e. for getting a deeper understanding of things it already ‘knows’. So overall, the algorithm works more closely to what we understand as curiosity than previous programs.

“They’re fundamentally different types of learning and exploration,” says Konidaris. “Balancing them is really important. And I like that this paper did both of those.”

Testing points

The researchers put TEXPLORE-VENIR to the test in two different scenarios. First, the program was presented with a virtual maze constructed of four rooms connected by locked doors. Its task was to find a key, pick it up, and then use this key to unlock a door. To score the algorithm’s efficiency, each time the simulated bot passed a door it earned 10 points and had a 3000 step cap during which to achieve the highest score possible. The bot was first allowed a 1000-step exploration phase to familiarize with the maze.

When this warm-up period was done under the direction of TEXPLORE-VENIR, the bot averaged 55 door point in the 3000-step phase. For other curiosity algorithms, it averaged anywhere between 0-35 points, with the exception of R-Max, a program which also scored 55 points. When the program had to explore and pass through doors simultaneously, TEXPLORE-VENIR averaged around 70 points, R-Max around 35, while the others clocked in at under 5 points, the researchers report.

The second round of testing was performed with a physical robot, the Nao. It included three separate tasks, during which the machine earned points for hitting a cymbal, for holding a pink tape (which was fixed on his hand) in front of his eyes, and finally for pressing a button on its foot. For each task, it was allowed 200 steps to earn points but was given an initial 400-step period to explore — either randomly or using TEXPLORE-VENIR.

Each method of exploration was used 13 times. Overall, Nao found the pink tape on his hand much faster using TEXPLORE-VENIR than the random approach. It pressed the button on 7 out of the 13 trials after using TEXPLORE-VENIR, compared to zero times after exploring randomly. Lastly, it hit the cymbal in one of five trials after using TEXPLORE-VENIR, but not once after exploring randomly. TEXPLORE-VENIR allowed the robot to better understand the basics about how its body, the environment, and the task at hand worked — so it was well prepared for the trials after the exploration period.

As the team notes, striking a balance between internal and external rewards is the most important thing when it comes to learning. Too much curiosity could actually impede the robot. If the intrinsic reward for learning something is too great, the robot may ignore extrinsic rewards (i.e. those from performing its given tasks) altogether. R-Max, for example, scored fewer points in the simultaneous exploration and door-unlocking phase because its curiosity distracted it from its task, which I guess you could chalk up as AI ADHD. Too little curiosity, on the other hand, can diminish the bot’s capacity for learning. We’ve probably all had that one test where the grade was more important than actually learning anything — so you memorize, take the test, and then your mind wipes everything clean.

Hester says the next step in their research is to better tailor the algorithm after our brain architecture and use deep neural networks to make bots “learn like a child would.”

The full paper “Intrinsically motivated model learning for developing curious robots” has been published in the journal Artificial Intelligence.

sorting algorithms

What sorting algorithms look and sound like

sorting algorithms

Credit: Timo Bingmann

Sorting algorithms are fundamental to computer science for the same reason sorting is important in your day to day life. It’s a lot easier to find things when they’re in order, which saves time and energy. Depending on how you need an array sorted, there are many sorting algorithms that you can use. Timo Bingmann made a software called Sound of Sorting which “both visualizes the algorithms internals and their operations, and generates sound effects from the values being compared.”

You can get a glimpse of how it works in this video produced by Bingmann.

The white bars represent the value of the array position corresponding to the x-axis. When an array item is set, the white bar turns red. A swap operation is two bars turning red which represents their values is being exchanged.

The sound’s frequency is calculated for each set of compared values. The sound wave is triangular and modulated to sound like an “8-bit game”, which is either very fitting or excruciatingly annoying.

You can download the software program here and then make your own sounds and videos.


Poor grammar makes for good passwords

As computing power grows and becomes ever more accessible, passwords become easier to crack day by day. If you want to make it really easy for hackers and automated crawlers to retrieve your secure information then input passwords like common names, pets, sequences of numbers and symbols or birthdays. Yup, they’ll gobble these right up.


These are too easy though. For instance, Ashwini Rao and colleagues at the Carnegie Mellon University in Pittsburgh, Pennsylvania  have developed a smart passsword cracking algorithm that not only looks for common password sequences, but also makes long keyword guesses that actually form a grammatically correct sentence. For instance some relatively advanced algorithms combine the same word in multiple varied instances, like “catscats” or the reversed “catsstac”. These algorithms however don’t know how to combine words to form sentences like “ilovebigcats”. Rao’s alogrithm, however, does.

The keywords are all retrieved from a password cracking database where common terms are listed. These are then combined by the algorithm in such an effective way that 10% of the total passwords cracked by Rao and her team  were retrieved exclusively using their grammar-sensitive methods.

With this in mind, choosing grammatically incorrect passwords is a better bet. Also, in their research paper due for presentation at the upcoming  Conference on Data and Application Security and Privacy in San Antonio, Texas, next month, the scientists warn that t other types of familiar structures like postal addresses, email addresses and URLs are very vulnerable passwords as well, despite being long or seemingly safe.

via New Scientist / image source

A quadrirotor, where EPFL scientists test their new technology.

Moving closer to 100% autopilot airplanes. A reality?

In Philip K. Dick’s novels, a common denominator is the complete autonomy of the surrounding technology. The human characters often interact with their toaster which knows what kind of grill cheese they prefer and even makes small talk, to the extent of exasperation from the human counterpart. A more palpable side to reality is the transportation – most of the time in Dick’s novels, the characters prance from one corner of the globe to another by an aerial vehicle, which simply gets you to your destination fast and easy without any kind of human intervention – you just need to sit tight, and maybe put up with your aerovehicle’s chattering.

A quadrirotor, where EPFL scientists test their new technology.

A quadrirotor, where EPFL scientists test their new technology.

Now, three EPFL laboratories are working closely together as part of a joint effort to design a completely autonomous flight system for airplanes that is safe and reliable, and happy to put pilots out of work. Now, you might say that this has already been implemented for UAVs; hold your horses though. When carrying people, you’re in a whole different ball game.

For one, this is an immense technological challenge which requires interdisciplinary expertise, which is why three extremely well staffed laboratories from one of the best tech schools in the world have been enlisted for the project. These are the Real-Time Coordination and Distributed Interaction Systems Group (REACT), which is working on predicting trajectories and in-flight collision avoidance; the Computer Vision Laboratory (CVLab), which has the job of outfitting the aircraft with a veritable visual intelligence system; the Distributed Intelligent Systems and Algorithms Laboratory (DISAL), which will test algorithms on small, lightweight flying robots.

Yes, all available resources will be called out for this one, and, again, this is a lot harder than it may seem. The REACT team, for instance, which has a long history with unmanned vehicles will try to develop a system which makes use of any positioning and sensing device inside an airplane, whether it’s GPS, ground-based radar, cameras, infrared cameras etc, and develop a position and trajectory algorithm based on the data fed by these devices.

This will came in handy for DISAL which in charge of developing an algorithm that will help communicate between airplanes. “We will work on integrating trajectory prediction, avoidance, stability, vision, and data-exchange algorithms developed by various laboratories, and see how to get them working together in real time,” explains laboratory director Alcherio Martinoli.

CVLab will work with high definition cameras, designed to recognize objects. “What seems to be a simple task for the human eye is incredibly complex to reproduce technically,” explains CVLab scientist Vincent Lepetit . “The main difficulty lies in the enormous amount of information that has to be processed; each image is made up of several hundred thousand pixels.”

Apparently, all the three labs have been called upon for the project by Honeywell, a huge industry player in the oil and mechanical engineering scene, but also in the aerospace sector.

“These new technologies will not only help us improve general flight safety, for example by providing better autopilot systems, but they will certainly also have other uses in automating everyday life,” says George Papageorgiou, director of the Aerospace Advanced Technology Europe System Engineering & Applications Department at Honeywell.

In the first instance, according to Honeywell officials, such a system will be first used for small airplanes or drones in non-military applications, such as forest fire surveillance or monitoring access to industrial sites and borders.

Would you fly on complete autopilot? Discuss below in the comment section. 


Sorting algorithms illustrated through folk dances

Various simulations of algorithms can be seen everywhere, especially in nature, but a recent project from the Sapientia University, Romania is definitely one of the most imaginative and novel initiatives of illustrating algorithms. The folks at Sapientia University demonstrate how different sorting algorithms work with numbered people dancing traditional Central European folk songs and arranging themselves from least to greatest.

The result is hypnotic to say the least. Just look at the Bubble Sort method applied to a traditional Hungarian dance below.

Adjacent partners swap if they are in the wrong slot until the algorithm is complete. They have to do a final pass before they can decide that it really is “all sorted”. Here’s the Shell Sort as well.

And the simpler Insert Sort.

Finally, the Select Sort.