TIC-TAC-TOE ROBOT
During the fall of 2017 and summer of 2018, I completed a project with the Kavraki Lab at Rice University. At the time, the Kavraki lab worked on cutting-edge approaches to integrate AI task-planning methods with sampling-based motion planning algorithms. To demonstrate the power of this combined approach, I worked on building an interactive system capable of playing tic tac toe with a human.
Using the lab's existing software infrastructure, Vicon motion capture system, and library of registered objects for tracking, I created a C++ library capable of planning and executing pick and place commands for various robots. By building the library on top of these components, I made a much simpler interface that could plan motions for robots to execute in a single line.
planning to grab a block with a single line
In a game with relatively few moves, like tic-tac-toe, the space of possible actions is much smaller than in a game like chess. Each player places, at most, one X or O, and the game ends when a player achieves three in a row or if there are no more possible moves. Then, the first player has nine options to play, the second has eight possibilities, and so forth.
To compute the optimal move for the robot to make, I used a minimax algorithm that evaluated the value of each potential move. This algorithm assigns positive point values to game states where the player wins and negative values where the opponent wins. The algorithm descends the tree of possible game states by simulating each player's move and assuming that the opponent will play their best possible move.
During moves where it is the player's turn, points are the maximum scores for moves proceeding the current game state. For the opponent's moves, the value of game states is the minimum of proceeding game states. These alternating maximizing and minimizing behaviors give the algorithm its name: minimax.
example of minimax evaluating a game state’s value
After evaluating game states, I programmed the robot to take the best possible move. Then, I had to use the robot to move game pieces to their desired spot to change the actual game state. Moving pieces presented another issue: the more pieces placed on the game board, the harder it became to plan collision-free motions for the robot. I opted to phrase each game move as a task and motion planning problem where the robot could move other pieces as long as they returned to their original location.
To do so, I created a pipeline to extract the tic-tac-toe game state from the transform frames provided by the motion capture system. After doing so, I converted the game state into a STRIPS-style planning domain with actions that allowed game pieces to move to board or buffer locations. The task in this domain was to move the next piece to the desired location on the board, with existing game pieces placed precisely where they were initially.
I adapted from Neil Dantam's work titled "Incremental task and motion planning: A constraint-based approach," which appeared in Robotics: Science and Systems 2016. This task and motion planning approach uses a Satisfiability Modulo Theories (SMT) solver and incrementally adds constraints to the problem when we cannot plan a motion for a particular action. The result is a task and motion planning pipeline that produces a sequence of motions for the robot to execute, making the optimal tic tac toe move. Overall, this project was a huge success and continued to act as a demonstration of our lab's work for the next few years.