Implementation

Hardware

The Robots

We used Zumy robots, which were provided.

The Grid

The grid was drawn onto two large poster boards, resulting in a 10x7 grid. As previously mentioned, the obstacles were made of commonly available 4”x4”x4” black boxes.

The Global Camera

The global camera is mounted on a wooden boom pole, which is attached to a tripod. This allows the global camera to have a nice, straight-down view of the playing field.

The AR Tags

AR tags 0 and 1 are used for the origin and reference markers, put into the bottom left and top right grid squares, respectively. They Each zumy has a single tag mounted to the top for the global camera, and the player zumy has four additional tags on its sides for the patrol zumys to see. All of the tags on the zumys are taken as inputs to our programs, so they can be any tag besides 0 and 1.


Software (note: many files in GitHub repo unused, relevant files listed below)

zumy_controller2.py contains the class ZumyController, which is a generic class (not specific to any in-game role) that implements the actuation of some particular Zumy. It contains the function go_to_waypoint() for navigating a Zumy to some given point on the map, with the precondition that the point is in a straight vertical or horizontal line from the Zumy (naturally, the actuation doesn’t have built-in pathfinding - that’s for planning!). It also contains methods that return the Zumy’s position and orientation using util methods.

zumy_player2.py implements the class Player, which is the code representation of the player zumy. This class contains all the state information for the player, such as current coordinates, the goal coordinates, the game map, the location and orientation of the patrols, and whether or not somebody has won the game. It contains a method, get_next_step(), which utilizes A* search to find a path to the goal and return the next step in that path. If the goal is unreachable, it instead tries to make itself harder to see by the patrols. It also instantiates a ZumyController for actuation. In its act() function, which represents one in-game “turn” or “tick”, this class will update the map, find the next step to go to, and tell its controller to send instructions to the Zumy to execute the command.

zumy_patrol3.py implements the Patrol class, the patrol counterpart to the Player class. Similarly, this class contains state information for a patrol: the current position and orientation (because the direction it’s facing is relevant), the last known player location, and the map as far as the patrol currently has explored (this is initialized to a blank canvas to begin with). It likewise has a get_next_step() function which also utilizes A* to navigate towards where it thinks the player is, and also has an explore() function that adds the patrol’s immediate surroundings to the map. In its update() function, like the player’s act() function, the patrol will find the next step and send the command to the controller for execution. It will also call ping() every five seconds, which updates the last known location of the player.

grid_broadcaster.py is a ROS node that broadcasts the relative step sizes of the grid in the x and y direction by finding the transform between two corners of the grid and dividing the translation by the number of grid squares in each direction. Given the unreliability of computer vision and ar_tracking, rather than publish the raw step-size at each time interval, grid_broadcaster instead computes a running average of the step-size to publish.

util.py was developed for the Pacman AI project in CS188, belongs to UC Berkeley, and is used with permission and has the proper attribution notice given. More information at http://ai.berkeley.edu. It contains some custom built data structures used in A* search.

search.py implements A* search with a Manhattan heuristic.

game2.py contains functions for loading in the map and its dimensions from a file.



How the Zumy Controller Works

  • There are 3 frames: frame a is the zumy, frame b is the origin, and frame c is the target square
  • Using the AR tags, the transformation gab and gba is calculated
  • The translation component of gbc is constructed using the target coordinate and the grid step-size
  • Using the translation components of gba and gbc, we determine the vector from the zumy to the target
  • We construct gbc with the previously computed translation component, along with the calculated angle of the zumy-to-target vector
  • Multiplying gab and gbc together gives us gac, the rigid body transform from the zumy to the target
  • Calculating the twist of gac, we get values we can publish to the zumyxx/cmd_vel topic
  • Feeding just the rotational component, we rotate the zumy to face the target until it is within a reasonable threshold
  • Then we give the zumy both translational and rotational components. The zumy moves forward while continuing to point towards the target (which helps correct for drift) until the zumy is within a reasonable threshold of the target location

How the Zumys Communicate

In order to tell each other when important events have happened, such as winning or losing the game, the Zumy Patrols and the Zumy Player communicate with each other through a number of rostopics. Seeing as subscriptions in ROS are handled asynchronously, much of this communication needs to be synchronized through threading procedures. Without these Zumys take their own sweet time in responding to changes in game state.