NAO robot plays Connect 4 - Robotic advanced behavior

NAO plays... Connect 4

Click on the image to launch the NAO plays... Connect4 presentation video
We are robotics enthusiasts who believe that one day robots will be our companions in the privacy of our home or our workplace. The advent of advanced robots such as NAO from Aldebaran Robotics reinforces our idea.

We are robotics enthusiasts who believe that one day robots will be our companions in the privacy of our home or our workplace. The advent of advanced robots such as NAO from Aldebaran Robotics reinforces our idea.

Our first behavior is a game behavior where NAO plays Connect 4.We invite you to browse this site and send us your feedback and comments, so do not hesitate!

Our Vision: Robots rather than automata.

As presented above, we believe in the feasibility of a robot companion. However, the development of advanced behaviors where a robot interacts in a natural and appropriate way in an unknown environment remains an important challenge.

In this behavior, in addition to the specific difficulties of the game (recognition of the board, positioning, movement, token insertion, error detection), we have been attentive to any interaction between the robot and its human partner. These "social" behaviors are available through:
- - The detection of the presence of the human partner with a hand gesture similar to the movements mad using a Kinect (There is no Kinect in our Behavior).
- - Face Recognition of the human partner
- - Voice Interaction
- - Detection of cheating ... :)
- - Model of Emotional Robot involving behavior modification
According to us, the human-robot interaction is as important as the actual ability of the robot to play the game, thus distinguishing it from an automata.

What distinguishes the robot from the machine is its ability to interact credibly with humans.
Main steps of the behavior "Nao plays...Connect 4"
Starting the game
- Detection of the human partner
- Recognition of the partner
- Social interaction: game suggestion
Steps
- Board sensing
- Movement toward the board
- Moves selection
- Movement toward the board
- Checking of the positioning and correction
- Request and grip of a token
- Put the token in the right column of the board
- Step back and analyze the success
- Solicitation of partner
Ending the game
- Victory dance (or not:))
- Recording the game
Key constraints imposed on the program "Nao plays... Connect 4":

The main constraint was to use only the embedded resources of NAO. All calculations (including vision algorithm) use the embedded processor of NAO and no external computer or device or cameras or other sensors are used. All steps of the algorithm are optimized to operate in "real time"
More Videos from our development team

The following videos have been realized by our team during the development process.

NAO Connect4 algorithm demonstration

NAOGUI, our Visualization interface

Skintracking algorithm. NAO follows your face and your hands.
The videos available on this page describe the whole behavior as well as some specific game sequences.

The behavior "NAO plays... Connect 4" is more than just a simple Connect4 game solver. Such algorithms used to play Connect 4 are almost as old as computer programming.

The challenge overcome by the R&D team of HumaRobotics was to enable Nao recognizing the game board and its close environment and evolve in a consistant and effective way during the game process, interacting with his opponent and performing independently the insertion of the token into the board (the only external help the robot needs so far is to grasp a token).

The development of this robotic behavior required the implementation and combination of several algorithms related to the following areas:
- - Human-computer interaction
- - Presence detection
- - Facial recognition
- - Haptic interaction
- - Genetic Algorithm
- - Machine Learning
- - Artificial vision
- - Fast SLAM
The game sequence begins with the recognition of the human partner. For this we have developed a small "skin tracking" algorithm which is based on a "Kinect" type movement. The user places his hand in front of the eyes of NAO and brings his hand over his face. NAO follows the hand smoothly and easily and thus detects the location of the opponents face in its surrounding.

Then, a facial recognition is initiated (this is done using the algorithm of Aldebaran Robotics). NAO acknowledges the person if he or she has been met before and proposes to play Connect 4. The user accepts or not via voice recognition or by touching the head of Nao.

DThen the game starts. NAO finds and centers the board in its surroundings and detects the position of the holes of the board. NAO uses particulate Bayesian filters generated through learning. This algorithm is an in house development that is a trade-off between quality and speed, based on the performance available on the robot. Similarly, the analysis of the state of the game is based on color filters built using a genetic algorithm.

Widget displaying the board position seen by NAO

Then NAO determines the next step move. He uses a minimax algorithm with alpha / beta pruning to assign a weight to each column and then chooses the most favorable column. The performance of the game moves can be adjusted by changing the depth of the minimax algorithm or "temperature" selection, i.e. the probability to choose a move which apparently is not the best.

When the move is decided by NAO, the robot gets up and walks toward the selected column of the board. An important point is that NAO cannot play staying close to the board, he must step back to see the board entirely and choose which move to play (imagine a board of 1.60 m high, you should also step back to see the entire board). To determine the distance between its initial position and the board, we use trigonometric calculations based on the assumption of the size of the board and transformed matrices calculated from the position of the robot's motors.

Once close to the board, NAO can still move aside to be in the best position to insert the token. This position estimation is based on a visual estimate of the position of the top corners of the board.

NAO positioning himself near the Connect 4 board

NAO requests a token from his opponent and then starts the insertion phase of the token. The controller used for this action is a linear multivariable controller (whose parameters are determined by learning) with a Kalman filter. This is a feedback loop based on the visual estimate of the size and position of the chip compared to the column. To date, with version 0.4 of our behavior, we achieve 80% success in a known environment (background, light and ground material). To be efficient in every environment is one of the milestones of our roadmap.

NAO analyses his final gesture to insert the token into the board

NAO steps back and analyses the board to determine if it managed to insert the token. If so, he asks his partner to play. If he detects that it has failed, a little irritated (discussed later on the emotional engine), he asks his partner to insert the token. It is useless to cheat because NAO notices it and can get angry!
Version 0.4 (November 2011)

The version 0.4 of the behavior "NAO plays... Connect 4" is the first version made public and contains the following steps:
- - Complete "Connect 4" behavior
- - PC Widget:
- - NAO emotional state visualization during the game
- - Visualization of the board and it localization estimated by NAO's SLAM
  algorithm
- - Verbal mode. When activated, NAO explains (in French) everything he is doing
  while playing
- - Auto calibration mode so that NAO automatically tune its vision parameters
  to optimize its performance (1rst version)
- - Errors detection (Cheating, mistake or failure when putting the token on
  the board
Widget to display the way NAO see the Connect 4 board
Roadmap
Here is some information about the roadmap of the robotic behavior NAO plays Connect 4. Before the final release, the following improvements are scheduled:
- - Making the movements and gestures more natural and more fluid
- - Improving the Widgets to better analyse and to ease the customization of the behavior
- - Implementing the behavior on the version 4 of NAO
- - Decreasing the time needed by NAO to play
- - Improving the robustness of the vision algorithms
- - Improving the human-machine interaction sequences during the game to improve the game play
- - Making the behavior multilingual
- - Recording the different games
- - ...
We have a lot of new features in mind (lot of surprises!) so check this page regularly to know the evolutions of this robotic behavior. !

A few words about our "emotion engine"

As previously explained in our vision, we do think that the quality and the richness of the interaction with the human is the key factor of the success of a companion robot. In every behavior, NAO should express and understand emotions to get a better social relationship. We must be clear on that point. We make a clear distinction between expressing emotions and feel really these emotions. We do not pretend to achieve such a capability (at least not right away :) ) .

Our emotion engine is a system based on a PAD structure. In this system, 3 variables are modified by NAO's actions, when NAO manages or not to correctly insert the token into the board, when he wins or loses, when its partner cheat or not, by the historical relationship with its partner, by the partner emotions (when the human partner is happy, he strokes his head slightly and when he is not happy, he gives a small blow to the head of NAO). All these events modify the 3 parameters P,A, and D which results in changes in the emotional state of NAO and therefore changes in its particular behaviors and words.

In the future, we will continue to improve this emotion engine so that it will be used on every behavior that we will develop.
NAO... and NAO

Hello! Im NAO and Im a last generation humanoid robot. I was born at Aldebaran Robotics in Paris but I have been living at Génération Robots , in the Bordeaux Area since 2008. I like to play games, and dance too. Since January 2011, I work every single day with another NAO and two humans, Manon and Philippe who program us in order to allow us to play to Connect4. Our humans are nice and everything is going fine with them.

Home sweet home

Generation Robots is a company that was founded by Jérôme. It sells a lot of programmable robots to passionate hobbyists and for the Education and Research. We love our humans for the simple reason that they also love robotics. You have to see them spending time programming their robots, looking for new sensors and accessories. We have a lot of robot friends and thats great!

Humarobotics ?

But why HumaRobotics you will ask me. It is very simple. For one year, the team at Generation Robots decided to dive deeper and to start doing real R&D and creating innovative hardware and software. The HumaRobotics covers all the consulting, training and new sensors activities (It is Yassine at Génération Robots who is in charge of developing new sensors. Just take a look at the website humarobotics.com). Generation Robots remains a quite cool webstore where you can find robots, sensors, accessories, in short, many things to build and program your very own special robot. With discussed this point with NAO (the other one) and we think that it is a good strategy. So we gave our green light to our humans.

I feel that you are very curious so we made a family picture. I think that we look great!
Human after all

You like or you hate what we have done, you want to know more about our work, you want to make an interview, work with us, meet us, offer a coffee or just chat about robotics: JUST DROP US A LINE

There is only one (good) address:

contact@humarobotics.com
You can also follow us on social networks (see on top of this page), we will publish all the new stuff we do.