Team A: Connect Four Loko

The goal is to construct a mechatronic device -- a robot -- that plays games of Connect Four autonomously, intelligently, and creatively. Our specific implementation exists as a combination of materials, subsystems, and features that not only function in unison most efficiently, but also facilitate additional device features that are as utilitarian as they impressive.

Figure #1: System Overview

The checker collection hopper system -- into which checkers are initially dumped -- is a tri-phase checker management system, for easy collection,
stacking, and indexing

The main playing arm -- used to deposit checkers into the desired game board column -- features a pulley-driven actuation system, for speed and precision.

Accordingly, these systems will be energized by a combination of embedded electronics, IR/contact/limit sensory inputs, and carefully calibrated
actuators that implement snappy, seamless gameplay.

Team Members & Responsibilities

· Jonathan Francis - Electrical & Computer Engineering | Schedule ›
Embedded, electronics, system integration, and testing lead

· Hong Jai Cho - Electrical & Computer Engineering | Schedule ›
Software engineering lead (game AI / best move computation)

· Anil Dhurjaty - Mechanical Engineering
Mechanical fabrication and assembly co-lead

· Joel Pazhayampallil - Mechanical Engineering
Mechanical fabrication and assembly co-lead

Since the goal of this project is to construct a robotic device that will autonomously play games of
Connect Four™ -- versus a human or another robot -- and win, or at least play with a reasonably high degree of intelligence, our group addressed various tasks:

(1) Efficient checker-collection and priming
The checker feeding mechanism is the subsystem that transports checkers from some initial location (i.e. a staging location, hopper, etc) to the “player head”, which holds individually primed checkers until it is required to release them into one of the seven columns of the Connect Four™ game construct. Another possibility would be to have the “player head” itself be a checker hopper, carrying all of the checkers with it, dispensing only one when it is prompted. With this second scenario, complications in the filtering phase (to allow for only one checker to be primed at a time, without getting stuck) would arise. It seems highly possible that checkers would get wedged in the hopper, such that no checkers would be dispensed when the player head is called to do so. Thus, feeding checkers from the base was found to be preferable, since dispensing only one checker on the moving platform is more complicated than just opening a door and letting the only checker fall out. Feeding the checkers into the “player head” is done by depositing the checkers into a hopper which will sort and load the checkers into the feeding mechanism. From there, The Device will be able to fetch the full stack of checkers and load them (quite conveniently) into the “player body”. At the beginning of the game, and subsequently
after each turn, one checker will be poked out of the stack and into the “player head”.

(2) Efficient movement of the 'player body/head' (the actuated player arm; the subsystem which indexes a game piece to the desired column slot)
In order to place the checker in the desired slot, the dropper (or “player head”) must be able to move
with a fair degree of accuracy (±1.5 mm for ideal, drop with no interference from column walls) to the desired slot, drop the checker and return to the home position (to load the next checker, if necessary). Our group came up with several ways by which the player head could be propelled: lead screw, rack & pinion, or clothes-line pulley mechanisms. Our group eventually decided to implement a pulley-driven actuation mechanism, to move the player head across the board; a lead screw mechanism requires more torque to actuation that could be reasonably furnished, while the rack & pinion design
is much too likely to have introduced crippling error in position control.

  (3) Gameplay artificial intelligence and move prediction
The "player" AI is constructed with a recursive algorithm that will calculate a dynamic rating of the “next game state”, as a function of the Connect Four™ checker configurations that currently exist. This rating will be assigned as varying degrees of 'relatively positive' or 'relatively negative' measures. For example, if The Device is poised to win or make significant progress in the next (few) turn(s), the result of the AI computation for that round will show a highly positive game state; conversely, if the opponent is poised to win on the next (few) turn(s), the analysis results will be highly negative. The program will then look six probable game states ahead and pick the move that would result in the highest game state.

(4) (Utilitarian) Coolness Factors
As part of the design specification, our group was required to implement 'coolness factors' -- additional
device features that rise above the robot's base functionality and further differentiate our robot from those of other groups with the same overall project. More specifically, however, our group's intention had always been to implement coolness factor(s) that displayed our skills and creativity,
while significantly augmenting the robot's utility. We believe we have achieved this goal with the following additions:
  • Bluetooth Serial Port Protocol
    • Control Mode -- use this mode to control the robot's actions, using the Connect Four Loko Java Blackberry application
    • Communication Mode -- use this mode to communicate game moves that the robot's opponent implements
  • Interrupt-driven Events
    • Button-initiated hopper emptying cycle
    • Button-initiated reset function

Subsystem Breakdown

Hopper Mechanism

The overall goal of this subsystem is to accept Connect Four game checkers, to organize or queue them, and to index or deploy them individually. To satisfy each of these three higher-level requirements, we implemented three corresponding mechanical stages of checker manipulation, which -- together -- comprise our 'hopper mechanism'.

Figure 2: Tri-Stage Hopper System

The first hopper stage -- 'collection / sorting' -- is the checker containment chamber, constructed from a 0.06-inch thick acrylic sheet that has been wrapped into a cylinder (5 inches in diameter, 8 inches in height). At the base of the cylinder is a
size 3/8-inch lasercut acrylic disk, with five holes (aligned in a six-hole symmetry) that each fit size 1-1/4-inch PVC pipe. A geared Jameco DC drive motor is mounted below the surface of the cylinder, in the center -- its shaft is inserted through a lasercut hole and therefore extends up into the checker container. With the use of a shaft coupling attachment, a thick ziptie is affixed to the motor shaft as an 'agitator', sweeping stray checkers into one of the five PVC pipe holes after they are dumped in.

The second stage -- 'stacking / storage' -- is comprised of 5-element array of 8-foot long, size 1-1/4 inch PVC pipes; this design affords significant speed/ease (< 3 seconds, no jams) in checker stacking and storage. The base of each pipe is force fit into one of five holes in a 1/4-inch lasercut acrylic plate (in the same manner as in the lasercut acrylic disk above the array).

The third and final hopper stage -- 'checker indexing' -- consists of two 1/4-inch lasercut acrylic plates that sandwich a free-moving 1/4-inch lasercut acrylic disk. The top plate also forms the base of hopper stage #2 (above), into which the five PVC pipes are force-fitted. In this manner, any checkers that are stacked in the five columns will rest on top of the acrylic disk. This disk, which has one checker-sized slot lasercut at the edge, is actuated at the center by an HS755HB quarter-scale servo motor (which has been modified for continuous rotation) and thereby fetches a checker from a PVC pipe stack and deposits it through a checker-sized hole that has been lasercut into the bottom plate. Once out of the hopper, a ramp transports the checker into the main robotic arm that will ultimately release it into one of the seven Connect Four gameboard columns.

Actuation and Position Control

Given the purpose of this robot, the most important mechanical action (arguably) is that of placing a checker in one of seven Connect Four gameboard columns. This involves moving some aspect of the device over top of the game board, then subsequently retreating to an initial or 'home' position. Specifically, our device reatures a robotic arm -- crafted primarily out of lasercut acrylic, which moves in only one degree of freedom (laterally, over the top plane of the game board), in order to minimize the mechanical complexity.

Figure 3: Pulley-driven Actuation System 

This arm ('player body/arm') is actuated by a urethane timing belt (0.200-inch pitch, 3/8-inch width), driving and guide pulleys, and a 1.8 degree/step 30VDC@0.7A Step-Syn stepper motor and rests on top of two 1/4-inch guide rails, with linear bearings. Built into the arm is an (i) HS325HB servo motor, with a horn that guards or clears the opening of the checker fixture (for priming or releasing a checker, as necessary) and (ii) an IR photosensor (to sense the events wherein a checker is primed or released)

Embedded Electronics, Sensing, and Power Distribution

The elements of this subsystem include the embedded microcontroller (Arduino Mega 2560, built around an Atmega2560 microprocessor), the motor driver circuit (Adafruit Integrated Stepper/DC/Servo Motor Driver Shield for Arduino), bluetooth module, PC power supply (modified; 3.3/5/12/24-VDC power lines) with stacked high-voltage terminal blocks, and sensory electronics (Fairchild QRB1134 IR Photosensor, limit switches, pushbutton switches).

Figure 4: Embedded and Sensory Electronics

The overall purpose of this subsystem is to provide operating intelligence to the robot, to implement the game AI and best-move computation, and to regulate the robot's mechanical behavior throughout runtime. These elements energize and control the robot in such ways as:

(i) powering the agitator driving motor (hopper, stage #1) at the beginning of every game of connect four

(ii) actuating the hopper servo motor (hopper stage #3), in order to deployed a checker from the hopper and into the 'player head' (where it then blocks the IR Photosensor, triggering the microcontroller to turn the servo off)

(iii) performing a game move -- actuating the stepper motor by the pre-computed number of steps to move 'player head/body' to the desired game column, signaling the 'player head' servo motor to release the primed checker, and actuating the stepper motor once again to
move the 'player head/body' back to the home position

(iv) Powering the 12VDC power supply fans for cooling

(v) Enabling RS-232 communication with a wired external device, for control and communication of game moves and state data

(vi) Controling the bluetooth module for implementing Bluetooth Serial Port Protocol COMM connections with a remote device, for remote control and communication of game moves and state data


A plethora of software applications and libraries were written to govern the functionality and additional features of our device. Our software 'package' consists of the central embedded control software (AVR, C), dynamics / sensory / computation libraries (C++), our game artificial intelligence (C, C++), and our Bluetooth Serial Port Protocol COMM mobile application (Java, XML).

The central control application primarily governs the mid-level gameplay functionality, powered by the functional libraries, especially as it concerns communication with an external device (wired or not) to convey/receive commands and game state, staging motor control event, or catching software interrupts. Built on top of this layer -- although included in this designation -- are the Bluetooth interface subroutines. These methods are intended to extend the communication environment to accommodate the mobile Bluetooth application that runs on mobile devices, externally. Finally, the higher-level AI software involves dynamic computation of best-move possibilities, which is used to dictate the manner in which the robot will utilize the aforementioned lower-level routines in implementing its moves during runtime gameplay.

The AI uses an efficient tree-search algorithm (using alpha-beta cutoff decisions) to ensure that the process plays as quickly as possible. A unique feature about the AI is that it uses a state stack. Using the state stack, it
is unnecessary to do a back move after each of the simulated moves (for Alpha-Beta pruning). Instead, states are pushed to and popped from the stack; this makes the overall computation fast because state pops are mere memory address shifts. The AI maintains an array of the number of winnable positions, and it uses the
array to evaluate the score for the best move depending on the numbers. The score is assigned the highest number in a win case.

Figure 5: Control Circuit (click for larger image)

Figure 6: Functional Flowchart (click for larger image)

     - Design Proposal: [ pdf ]
     - Mid-semester presentation: [ pptx ]
     - Final Poster / Quad Chart: [ pptx ]
     - Final Presentation Video: [ (YouTube) ]

No comments:

Post a Comment