Design

Design Criteria

  • The positions of the obstacles on the playing field are read in automatically
  • The zumys avoid running into the obstacles
  • The player zumy knows the exact position of every obstacle and patrol at all times
  • The player zumy should be smart about its path, choosing the shortest path while avoiding the patrols
  • The patrol zumy(s) only know about adjacent obstacles and remember the location of previously adjacent obstacles
  • The patrol zumy(s) gets periodic updates on the location of the player zumy, once every 5 seconds
  • The patrol zumy(s) should converge onto the position of the player zumy
  • The patrol zumy(s) can see the player zumy with an onboard camera
  • The game should be balanced - it should be possible for either the player or the patrol(s) to win
  • All the zumys should stop after the game ends

Design Choices

The Grid

We chose to use a discretely quantized grid for the playing field. This makes it easier to implement path-finding algorithms. However, it also significantly limits the possible movements and outcomes in the game. We chose 5.5”x5.5” to be the size of each square, since a zumy can rotate inside of such a square while staying fully within the square’s boundaries. For our obstacles, we use 4”x4”x4” black boxes. These boxes fit nicely in the grid squares, and can be distinctly be identified.

Global Camera

There is a camera that overlooks the entire playing field. This allows us to keep track of all the robot positions at all times. The motors and their encoders on the zumys are not always reliable enough to be sure that the robots will always stay aligned to the grid. This, however, is probably less interesting than if the zumys autonomous operation was stand-alone.

Grid Origin and Reference Tags

The grid has two AR tags on opposite corners. By computing the X and Y translation between these two tags, we can find the distance between squares on the grid by dividing through by the grid size.

One of these two tags is also used as the “origin” tag, and is used for rigid body transforms to command the zumys to specific squares on the grid.

Multiple Patrols

The number of patrol zumys we choose to use depends on the balance of the game, since of course more patrols would make the game much harder for the player. We have found one patrol to be sufficiently fair in the end.

Path Planning

Some of our group previously took CS 188, “Artificial Intelligence,” prior to taking this course. We decided to take advantage of this experience to implement the A* algorithm.

The Notion of Zumy Motion

The zumys moves are discrete, and they move from square to square along the planned path. The result is not the smoothest in terms of motion, but it is easier to implement than motion in smooth curves.

The moves of the different zumys are asynchronous - no zumy waits for another to finish its move before continuing. This gives us smoother overall motion in the game, in spite of the discrete moves of the individual robots.