Multi-Agent Grid Navigation

Overview

This has been our most complex project to date. Four Wixels (one for each m3pi and one for the PC, which coordinates the communications) and three m3pis are used. The grid sensing itself relies on concepts from the earlier single-agent grid navigation.

The agents navigate using A* pathfinding. The user controls the destinations of the m3pis using a C# .NET utility. The sped-up portions of the video (denoted by "8x") indicate times where the user is entering destination commands. These commands may be provided to each robot individually, or all together at once, which is what you see in this video.

How Communications Work

Since the PC and the three robots share the same medium, we needed a form of scheduling to ensure that communications took place in an ordered and predictable fashion. Each robot waits for a signal from the PC, which may or may not contain additional commands (such as setting a destination or the locations of other robots). Once the computer indicates it has completed its message, the robot transmits any relevant information such as its position. The PC then moves on to the next robot.

Each robot Wixel operates on its own radio channel, and the PC Wixel changes its channel dynamically to communicate with each robot. We use a modified version of the Wireless Serial App to accomplish this. We've also made additions to the Wixel radio_link library. All of the modified source code is available. The robots themselves use channels of 100, 110 and 120. The (arbitrary) formula for determining the proper channel of each robot is 100 + (10 * i), where i is the unique ID of the robot, initially configured by the user.

Building the Course

Running three robots on a grid meant we needed more room; the single poster board sheet we used for single-agent grid navigation would be too small. Additionally, we required more space between the squares so the robots wouldn't scrape or touch each other. We joined two sheets of poster board width-wise, and used electrical tape to form an eight-by-five grid (seven-by-four squares), with each square having inner dimensions of roughly 13x13cm.

Multi-agent grid arena

Starting the System

To begin, you'll need to follow these instructions.

  1. Flash the wireless_serial_channel.wxl app onto the four Wixels. Ensure that the PC's Wixel's radio channel is initially set to a value that will not be used. In the video above, we used a channel of 50. The default value of 128 is acceptable for the robot Wixels.
  2. Place the robots on the course. Each robot should be placed along the y = 0 axis, with the x-coordinate equal to the ID of the robot.
  3. Turn on the m3pis, and activate the MultiGrd program. Assign the IDs to the robot according to their initial positions. Press B to start each program, and wait until they have fully started.
  4. Plug the PC Wixel into your computer, and then start the MultiAgentGridNav application. The log should instantly begin recording communications data from each robot. If communications are functioning properly (see below), then you can begin sending commands to the robots.

Note: In some cases that we haven't fully determined, a robot may sometimes not establish communications properly with the PC when the system is initially activated. This is indicated by a slow blinking of an m3pi's Wixel, or a pause in the communications at the offending robot, indicated by the log in the MultiAgentGridNav application. If this happens, simply press any button on the m3pi to stop the program, and then immediately start it again (without powering off the robot).

Sending Commands

Instructions on how to use the MultiAgentGridNav C# .NET utility are available here.

Caveats and Warnings

Some things to be aware of when using this system:

  • While our implementation does a good job of preventing crashes, it is not overly difficult to intentionally (and in some cases, accidentally) cause collisions. Please use care when assigning destination information to the robots to avoid damaging them.
  • In cases where collisions or other undesired behaviours occur, click the Halt all button in the MultiAgentGridNav program to immediately stop all robots in their tracks.
  • If collisions occur, it is likely that the positions of some of the robots have changed (they may have pushed each other around a little), and it is nearly impossible to recover from these problems. At this point, you will have to restart the system.

Downloading

The Project Tabletop download includes all files relevant to this project.