Introduction
The goal of Among Bots was to create a simulation of the hit multiplayer video game “Among Us” using simple robots in STDR Simulator. In this game, one large team of crewmates aims to complete a set number of tasks while a smaller team aims to sabotage and kill crewmates. The game ends when either all tasks are completed or no crewmates are left in the environment. The real game of “Among Us” involves more complex methods of play such as sabotage and voting, but our goal was to replicate the basic functionality of the game.
In replicating the game, we hoped to learn more about robotic simulations of dynamic environments. In the lab material for this course, we worked mostly with single robot systems. However, we were interested in learning more about multi robot systems and how those may play out. Given some goal, what is the best way to delegate and assign tasks to different robots? Given the idea of chasing other robots, what strategies will work in assigning targets and planning toward them? How efficient will we be able to make our impostor team? These are all questions we hoped to find answers to in our journey of recreating the game of “Among Us.”
Implementation
1. Map Setup
The first step was creating a game environment. We based our map on the general layout of The Skeld map in Among Us. The map we created is a simplified version of The Skeld map. Our intention was to create a map that the robots would be able to move around easily in. Hence, we decided to create a simple black and white version of the floor plan through binarizing The Skeld map image, which would only contain empty rooms and hallways for the robots to move around in. In addition to having empty rooms and hallways, we added concave and convex grooves in Adobe Illustrator to the walls in some rooms that represent the task locations that the crewmate robots have to get to. To add this to STDR, we call our map png in the among_us.yaml file in the edited stdr_simulator package.
2. Robot Set-up
Robot set-up was rather simple, as we gave the same features to both crewmates and impostors. We based our robots on a very simple unicycle model of the TurtleBots. The details are described in among_us1.yaml and specifies robot footprint and laser specifications in the stdr_resources/robots directory.
3. Initialization
To start the Among Us simulation, we run our run.sh bash script in the root directory of our Git. We launch our environment by loading the map into STDR simulator and initializing the parameters through our among_us.launch file. The parameters are:
- Positions for each robot-(X,Y) coordinates on the map
- List of alive crewmates
- Impostor #1 target – crewmate name that the impostor #1 is trying to kill
- Impostor #2 target – crewmate name that the impostor #2 is trying to kill
- List of crewmates with tasks
- Paths of each robot
All of our launch files are described below:
We then spawn the eight robots with 360 degree laser sensors into STDR simulator using spawn_robots.bash. Each robot is initially placed in the center top room as is typically done in Among Us. Next we launch RVIZ, which we will use to visualize the game play. We also initialize an RVIZ robot tracking script and continuously publish task locations in RVIZ by using yellow markers on the map.
And lastly we initialize all of the rest with the below scripts:
The above description is a loose representation of how things are initialized, with slight alteration in chronology. The below operations diagram gives a more exact representation of when what is initialized.
3. How is it Integrated?
Now that we’ve initalized everything, how do things communicate? Below is the Systems Diagram for the system.
As can be seen, the central aspects for functionality are the taskmaster and the parameter server. The parameter server keeps track of all essential parameters that any aspect of the system may want to access. This includes parameters ranging from robot position to which robots still have tasks. The taskmaster constantly calls on some these parameters to coordinate path planning of the robots. For crewmates, the taskmaster consistently calls for their positions from the parameter server and then sets a path with specified waypoints for the robot to follow to get to their task. For impostors, the taskmaster calls for their positions from the parameter server, searches for the nearest robot, and generates a path to that robot. Since generating A* can be expensive, it is only regenerated once robots have completed their previous dictated path or (for impostors) when the robot they are chasing is killed.
As can be seen in the Systems Diagram, the taskmaster sends waypoints to the controller, which sends velocity commands to the robots’ odometry nodes. The robots then report their odometry information to the odometry node, which is reflected back in the parameter server and robot position visualizer. In addition, 360 degree lasers are attached to the robots, which take laser scanner data to update the world occupancy grid. Since path planning is generated off of this occupancy grid (and not some static map png), it is necessary to initialize it by running a robot manually through the environment beforehand. We’ve done this just once with our map and initialize it in occupancy_grid_2d.py. While this is not ideal, as mentioned in the Design section of this report, this allows us to generalize game logic to any map as long as there is a human operator. In the future, we would like to further explore RRT solutions to random exploration of an unknown map to build the occupancy grid to avoid the need for the manual operator. The taskmaster calls the path planner to generate new paths, which are also fed to the parameter server for visualization.
Lastly, on the right side of the Systems Diagrams, there are several scripts that call values from the parameter server. The purpose for the kill checker and game end checker are for game logic while the path visualizer and robot position updater both serve the purpose of updating objects in RVIZ to display what is happening in the game. A terminal output is also used to display robots who complete tasks and a few other diagnostics of the system.
4. Game Play
After initialization, the game starts, and we start publishing waypoints and commands to the robots. Impostors are depicted by the brown and pink robots (for our example), whereas the crewmates are depicted by the other colored robots. The impostors have a sixty second delay to give the crewmates a head start to get to their first task. Using the initialized occupancy grid, the map used for path planning is updated and ready for the A* star algorithm to generate the most optimal path that the robots can use to get to their target.
For crewmates, their targets are the tasks and for impostors, their targets are the alive crewmates. Each crewmate is given two tasks in our example. The crewmates start by planning a path to their task given to them by Taskmaster after performing A* on the occupancy grid. Once a robot reaches a waypoint given by the Taskmaster, it sends an update to a task named ‘<robot_name>/taskUpdate.’ By continuously checking for task updates at that topic, the Taskmaster is able to determine whether it needs to give the robots another task update. Essentially, it is the Taskmaster’s job to ensure robots continuously follow its next waypoint. Once a robot has reached one waypoint, it needs to go to the next. From the path publisher, we can see the paths generated for the robots upon which these waypoints lie.
Once the sixty second delay is over for the impostors, each impostor searches for the nearest alive crewmate to kill by referencing all of the robot position parameters. Using that information, it plans a path to get to that crewmate. Initially, all crewmates are alive. The ROS parameter “alive_crewmates” is a list that keeps track of which crewmates are alive. After an impostor kills a crewmate, Taskmaster assigns the impostor to the next nearest alive crewmate to kill and publishes a path update to get to that crewmate. If an impostor is chasing down a crewmate and that crewmate is killed, it will generate a path to the next closest crewmate. The two impostors will never chase the same crewmate unless there is only one crewmate left alive.
If an impostor kills a crewmate, that crewmate turns into a ghost and is depicted by the robot marker turning grey through the robot position visualizer. As a ghost, crewmates are still expected to complete all tasks and the crewmates can still win the game if every crewmate, ghost and alive crewmates, complete their tasks. It is important to note that crewmates do not know which robots are the impostors. Their only goal to complete all their tasks before the impostors kill all the them, so crewmates do not avoid impostors.
At waypoints, Taskmaster sends path updates to the robots. The robots are able to get to their target through velocity updates that the robot controller publishes. The robot uses a simple proportional controller with slight modification. Since the robots are non-holomic, they must correct for angular error before correcting for translational error. As a result of the varying performance of a simple proportional controller, we change our strategy to include a decaying factor for the angular error. Initially, we correct for angular error aggressively; however, if the robot is unable to stabilize along its path, we use a decaying factor to reduce that proportional constant that corrects for error up until a certain minimum value. This strategy allows us to correct for error much more quickly while not needing to rely on a more complicated controller.
After receiving commands to go to a task, when a crewmate gets to their target location, they have to complete a task. The tasks requires that the crewmates correctly sense if the wall near the task is concave or convex. They do this by subscribing to its laser scanner data. If the crewmate correctly senses the wall, they can move on to their next task. In the terminal, the robots will output “This task is concave!” if the wall near the task is concave or “This task is convex!” if the wall near the task is convex. Once the task is finished, Taskmaster will assign the crewmate to another task if the crewmate has not completed all their tasks yet. Taskmaster uses a list to store which robots have tasks left. If a crewmate has completed all their tasks, they will remain stationary at the task they just completed and wait for the game to end, and Taskmaster will update the ROS parameter “robots_with_tasks” to remove the crewmate that completed all their tasks.
The game will continue until the crewmates win by completing all their tasks or the impostors kill all the crewmates before the crewmates finish theirs tasks. Kill Checker continuously runs throughout the game to check if an impostor is within killing range of a crewmate. If the impostor is within range, then the impostor kills the crewmate. The terminal will output “CREWMATE WAS KILLED.” Kill Checker will also update the ROS parameter “alive_crewmates” to remove the crewmate that was killed.
To end the game, Game Ending Checker runs at all times to check if the game is finished. Game Ending Checker checks which ROS parameter, “alive_crewmates” or “robots_with_tasks”, is empty first. If “alive_crewmates” is empty before “robot_with_tasks”, this means that the impostors have killed all the crewmates and have therefore won the game. Green text will display in RVIZ to indicate that the game has ended and will state “IMPOSTORS HAVE KILLED EVERYONE!” On the other hand, if “robot_with_tasks” is None first, then the crewmates have won the game because they completed all their tasks. In RVIZ, the text will display “CREWMATES HAVE WON BY TASKS.”
Design
The design criteria our project intended to cover were to incorporate planning, actuation, and sensing. We chose to use TurtleBots as our robot of choice, having 8 of them (2 being imposters and 6 being crewmates).
- Planning: To incorporate the planning aspect, we used an A-Star algorithm to help the robots plan their paths, from their current location to their next assigned task if they were a crewmate or from their current location to the nearest crewmate (to kill them 😢 ) if they were an imposter. In this A-Star algorithm, we considered having minimal turns (as the robot is nonholonomic and too many turns would be costly) and also considered staying away from walls when traversing hallways. We developed a cost function that heavily penalized excessive turns and paths close to the walls, leading us to have straighter and more centered paths. Planning had to be heavily integrated with taskmaster-controller communication as the taskmaster commanded waypoints for the robots to travel to.
- Actuation: Having robots along the planned A-Star paths incorporated actuation, since this required these nonholonomic robots to drive in a specific fashion such that the paths did not require them to move diagonally or suddenly change direction without turning. To achieve this, we incorporated a simple proportional controller that focused on first turning the robot in the direction of its next waypoint and then sending it along that path. We used a decaying factor on the angular correction factor to allow for robots to aggressively correct for angular errors initially and then less aggressively settle itself to exactly aim along that path. This aided in lowering the amount of time it took for robots to travel a desired path.
- Sensing: Our primary motivation for sensing was to perform A* path planning on a continuously updating occupancy grid with data from all 8 robot laser scanners. We generated an initial rough estimate of the occupancy grid by using STDR keyboard tele-op and manually driving one of the robots around the unknown map, generating an occupancy grid in the process. This initial occupancy grid allowed us to perform A* for each of the robots’ first tasks (so the robots wouldn’t run into walls); however, in the future, we would hope to replace this with random exploration. As all eight robots went to their tasks, they further used their laser scanner data to update the occupancy grid to be more precise from which further A* would be conducted on. Apart from the updating occupancy grid, we also implemented sensing into our tasks. Once the crewmates successfully travelled their path, we had them do a task at that location incorporating sensing. Since STDR is rather limited in sensing, we had to make further use of the laser scanner to get them to sense surroundings. At each task on the map, there is either a convex or concave wall. The crewmate’s job is then to use their laser scanner data to determine whether that wall is convex or concave.
Choices we made:
- Should each robot have its own node for core functionality or combine everything?: We decided to opt for each robot having its own node for the taskmaster, controller, and parameter server.
- Pros: Kept implementation simpler, in that each taskmaster node and robot controller node only had to account for one robot each. No need to differentiate which message comes from which robot and which direction goes to which robot. (The alternative would require us to make different message types to keep track of the robot number and have an immense amount of conditional statements, which would be messy.)
- Cons: Many more nodes to manage, we have 8 robots! Slower runtime since we have many more nodes and topics communicating with one another. We think this may be the reason we run into TCP/IP connection errors (where a publisher or subscriber is unsuccessful in accessing a task)
- What should be the tasks for the crewmates?: As discussed in the Sensing section, the task requires a crewmate to use laser scan data to determine if a wall is convex or concave.
- Pros: Allowed us to incorporate sensing into our project, which we previously had a lot of trouble figuring out how to incorporate.
- Cons: Required some small modifications to the map to add these concave/convex walls.
- Should the map be known or unknown?: Initially, we wanted to perform random exploration of the unknown map to generate our occupancy grid that A* would be performed on. However, after running into many difficulties on that side, we opted to go for a more manual approach that allowed us to focus on other functionality of the project. By manually controlling a robot to run around the map with STDR keyboard tele-op before starting the game, we are able to initialize a map in which A* can successfully generate paths without running into walls. There were things we wanted to experiment with (RRT Star) but the tradeoff was difficulty and choosing whether to use our time towards implementing RRT Star versus something else.
- Pros: Allows us to run A-Star on the initial map more easily. As long as there is a manual controller, the game (and path planning) can be run on any map!
- Cons: Less realistic (maps are not always previously known and full exploration of a map in the real world is sometimes impossible).Our choices impacted:
- Robustness: Mentioned in the last bullet point, deciding to have a known map made the project less robust to real world applications, such as when we cannot fully discover the map ahead of time with a human operator.
- Durability: Having the robots make less turns and avoid walls (a choice we made in our A* algorithm implementation) means it easier on the robot’s wheels as well as prevents robots from crashing into walls. Excessive turning over time would raise time for game completion, and crashing can potentially damage the robot as well. By limiting turns and keeping robots away from the walls, we are able to keep the robots physically in shape which makes our design durable.
- Efficiency: Deciding to give each robot an independent node for taskmaster, controller, and parameter server made communication more efficient (since no checks are needed to see which robot a message is from), but it made the system slower (since we need to account for many nodes). In the real world, this slowness may not exist if we have a more powerful computer or perhaps not use ROS and opt for something faster.
