DESIGN
DESIGN CRITERIA
-
Robustness to noise in the input image and the computer vision algorithm can detect the correct board matrix
-
Robustness of the cheating detection system which includes all possible situations on and can handle each situation properly.
-
High quality of drawing and erasing. A drawing should be neat and can be detected by Computer Vision algorithm. Erasing should be clean and would not affect other places
-
Speed of process
INTEGRATION
The skeleton of our system was straightforward. We designed two nodes: one for the publisher and one for the subscriber. The publisher could use a webcam to capture the image of the chessboard and then the computer vision algorithm computed the state matrix of the chessboard based on the image and then Gomoku AI engine could generate the next step instructions to the robot based on the state matrix and finally published the next step message to the subscriber. Once the subscriber received the next step message, it would control the Baxter to do the proper things according to the message. In order to let two nodes communicate via topic, we also designed the customized message type which would be two arrays: one contained points to erase and one contained points to draw.
Initially, we designed to make four nodes (cv node, AI node, motion node, draw and erase node) for the whole system because each teammate could work on one node separately and each node can communicate via separate topics. However, we found out the four node schema was not efficient since there was latency between nodes’ communication and we noticed each person can also work on different part once we defined a proper APIs for each part. Hence, we chose to use two node schema above as the final skeleton.
COMPUTER VISION
The computer vision part of this project is basically making the robot be able to detect the state of the chessboard. We use a webcam to take a picture of the chessboard and the program will be able to transform the image into a 2D numpy array which represents the state of the chessboard.
The accuracy is the priority of the part. It starts at determining the intersection of the grid then crop the image of chessboard into pieces for each grid which helps to increase the accuracy of detection dramatically. The trade-off is all focus on the accuracy as well. We do making improvements in codes such as the linear transformation of image and corp grid into pieces, as well as making improvements on the physical chessboard such as making a neat chessboard and increasing the thickness of the grid. We do trade-off on making physical improvements and coding improvements.
All the work towards a good CV part is to make it robust. Since it's the eye of the project, if any error occurred when detecting the state of the chessboard, all the work following are meaningless. In the end, the program ended up with the linear transformation for the chessboard image (tolerance for slightly moving the chessboard) and cropping the grids into pieces. It turns out that the accuracy of the result is fairly good. For the efficiency, most of the pixels in the grid are not detected, a fraction of pixels in the grid are randomly selected for detection. In the end, it takes about half a second to generate a 2D array representing the state of the chessboard by the image taken by the webcam.
GOMOKU AI (GAME ENGIN)
With knowledge of chessboard state, robot will know what it should do in this turn. If robot receives a valid chessboard state after player’s operation, robot will check if player has won the game. If player wins, robot will announce the end of the game, otherwise, robot will rationally think where it should put next chess piece to make it more likely to win. We use the Expectimax Algorithm implemented by Zitong Mao (https://github.com/ZitongMao/gomoku-ai). However, if robot receives a invalid chessboard state (may produced by invalid operations of player), robot will know where it should erase or draw in order to recover the chessboard to latest valid state.
We mainly focused on designing algorithm that make robot has ability to recover the chessboard when it receives invalid chessboard state. Initially, we want to record all valid state matrices so that robot know all the valid chessboard states in the game. However, we soon find this approach is not only redundant for robot to ensure the validity of the game, but also inefficient to memorize all the data. We decide to change the whole algorithm and only memorize the latest valid state. Robot can recover the state to latest valid state to ensure the validity if it receives an invalid state, though we cannot recover to the further previous states.
MOTION
The left arm of the Baxter robot is to control the marker and the right arm of the Baxter is to control the eraser. The positions of the right-lower and left-upper grids of the chessboard are measured and used to calculate the position of all other grids on the chessboard. Once receiving the coordinate of the target position, the arm will move to it and slightly lowering the marker until it touches the board just at the target. The gripper will rotate to draw on that grid and the arm will return to origin after the drawing process. The process of action is similar to the other arm holding eraser to “pick up stones” (that is, to erase the mark on board).