The ultimate goal of the sensing portion of this project is for Baxter to know the (x, y, z) coordinates of all 24 checkers pieces with respect to its base frame. There are multiple approaches we could have taken involving computer vision, but we chose to start with a simpler AR Tag system in order to get the full system in place. We also chose this method because it allows us to more easily localize the board. However, this came with its own set of challenges. Initially, we wished to use Baxter's head camera since it would be stationary and thus the sensing would not come in the way of moving. This proved to be infeasible because the field of view of the head camera did not include directly in front of Baxter: the only place the arms can reach. Thus we were limited to using the right hand camera to sense the board.

Localizing the Board

• We placed AR Tags on the upper left and lower right corners of the board, allowing us to split it into an 8x8 grid for (x, y, z) coordinates of every square

Tracking Opponent's Pieces

• We needed AR Tags on all 12 of the opponent's pieces, which meant that the tags themselves needed to be small enough to fit in the checkers pieces themselves: less than 4cm across
  • This meant we could not move the camera very far above the board, otherwise none of the AR Tags would be tracked properly, which results in only being able to sense half the board at a time
  • This limited Baxter's ability to fully autonomous as we had desired, since it is difficult to keep track of so many AR Tags all the time, sometimes we must manually move the arm in order for it to sense some AR Tags

Tracking Baxter's Pieces

• In order to make our system more robust to failure of AR Tag tracking, we decided that it was unnecessary to keep tags on Baxter's pieces
  • Since it makes decisions on which moves to make for itself, it is possible to keep track of which locations on the board have pieces without the need for direct tracking
  • This, however, assumes that the picking and placing of pieces succeeds when Baxter attempts to move its pieces, which is a tradeoff we were willing to make because it is rare for this type of failure to occur
  • The legal places on the board are numbered 1-32 as shown below, allowing for a compact representation of moves and piece locations

The algorithm module of the project provided the back-end for the Baxter checkers moves, allowing the Baxter robot to make intelligent plays. This allowed it to play without user input moves, giving the feel of playing against a smart robot agent. For the implementation of this module, we used Arthur Samuel’s historic checkers algorithm. The algorithm uses a mini-max structure, where it expands future moves and takes most optimal move. We also use Alpha-Beta pruning to speed up the program. Due to processing constraints, we chose to expand up to five future moves only. For more optimal performance, larger number of future moves may be expanded.

Tree Expansion

• At each layer of the tree represents one step into the future
  • Every other layer is the players move (layers 1, 3, ...)
  • Baxter starts with layer 0, its current position
• Uses Alpha-Beta pruning to improve code efficiency
  • Assumes human opponent will want to minimize its score, while it is trying to make moves that maximize its own score
  • Prunes moves that are trivially worse

Code Incorporation

• Limit looking into the future of at most 5 steps for computation time constraints. It takes about 5 seconds for 5 steps into the future.
• Makes moves with the other module, Planning, after calculating a move. Detects opponent position and updates algorithm with Sensing module