Design

Sensing

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

Planning

The goal for the planning module was simply to allow Baxter's left gripper to consistently pick up checkers pieces and to allow the right arm to sense the board properly. To do this, we the MoveIt! package to get the gripper and cameras to their desired positions. We, however, could not rely on MoveIt to plan entire paths simply because of the inconsistency of its RRT planner. This meant that we could not directly plan paths to (x, y, z) coordinates of markers and instead had to split the movement up.

Splitting the Pick-up Action

  • We split up the action of picking up a piece into two parts:
    • One to situate the gripper directly above the (x, y) coordinate of the piece we wish to pick up
    • One to lower the gripper onto the piece to allow for the suction cup to work properly

Adding Constraints

  • It was apparent quickly that the speed of the arm's movement lead to some inaccuracies because it was not able to stop its momentum fully or consistently, so we scaled the velocity of the movement down to 1/2 its normal speed
  • We also needed to make sure that the suction gripper would stay vertical as it moved down to pick up the checkers piece, so we added an orientation goal pose to the first part of the motion and used that as an orientation constraint for the second part of the pose
    • This, however, created some unforeseen problems: the orientation constraint was often too tight for MoveIt to plan paths with so it would often fail. To remedy this, we added a tolerance for the orientation of 0.1 radians, and it seems that making this tradeoff for more consistency over accuracy was worth it

Algorithm

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.


An illustration of the minimax tree, where Baxter assumes the human player will attempt to minimize its score.

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