Introduction and Background
Swarm robotics is a field in robotics in which two or more robots are programmed to work together to achieve a desired and collective outcome. It has become a major area of study because it has been realized that usually, the coordination of different specialized robots for a task tends to be more productive and easier to accomplish than using a single general robot. Pilolo is a project that applies the principles of swarm robotics to solve a problem commonly experienced by the military and law enforcement agencies. Pilolo uses two robots, a scout (Figure 1) and a collector (Figure 2), to find treasures in a terrain populated with obstacles. In the military, this problem usually arises during rescue missions. People to be rescued are usually confined in dangerous zones. Scouts, in the forms of helicopters, drones and satellites are used to reconnoiter a location before ground forces are sent to retrieve the identified targets safely. Likewise, the scout and collector robots in Pilolo play the roles of drones and ground forces respectively. The scout robot, with its color sensor, examines the whole terrain to identify positions of treasures and obstacles. This information is reported back to the collector, which goes into the terrain and safely retrieves the obstacles. Both robots use a path-planning algorithm to move from a start position to a target position.
To begin, a grid was used to represent the terrain. Obstacles and treasures were represented with blue and yellow cardboards respectively.
For successful implementation of the project, the following objectives had to be met:
- Implement Bluetooth communication between the scout and collector robots
- Use scout to detect and report obstacles and treasures in terrain to the collector robot
- Safely collect all identified treasures in terrain using the collector
Implementing Bluetooth communication
In order for the robots to work cooperatively, the scout and collector must be capable of communicating with each other, using a protocol understood by both robots. In the Pilolo project, Bluetooth was chosen as the medium for communication. This is because of its ease of implementation and the fact that the NXT bricks come equipped with Bluetooth capability. The protocol used was of the form:
OBJECT_TYPE, X_COORDINATE OF OBJECT, Y_COORDINATE OF OBJECT
OBJECT_TYPE can be 1 or 2 indicating that the identified object is an obstacle or a treasure.
Implementing the scout robot
The role of the scout robot is to search the whole grid to identify the location of any treasure or obstacle using a color sensor. The particular color read by the color sensor is checked every time the scout moves to a new cell. Whenever, an object is detected, its coordinates are sent via Bluetooth to the collector robot using the protocol mentioned earlier. Because the whole grid had to be searched, the path-planning algorithm implemented was a simple one (Figure 3). From the scout’s start position, the robot moves vertically down a column. Upon reaching the end of a column, the scout turns onto the next column and repeats the process. This continues until the whole grid has been explored. After that, the scout uses the wavefront path-planning algorithm to get back to its start position.
The wavefront algorithm is used to find the safest and shortest path from a start location to an end location. In the wavefront algorithm (Figure 4), coordinates of obstacles in a grid are marked with a unique number, in this case, 1. The destination cell is then marked with another number, in this case, 2. Next, the number marked at the destination cell is taken and incremented by 1. All neighbouring cells (top, left, bottom and right) of the destination cell are marked with the result. The values of the newly marked cells are then taken, one at a time, and incremented by 1. The result is stored in the neighbouring cells of the cell under consideration. This process is repeated until the whole grid has been processed or the cell with the start location has been examined. The shortest path is the path from the start location along the cells with marked values decreasing by 1 from the previous cell. The scout uses the wavefront path-planning algorithm to find the shortest path from wherever the grid ends to its start point.
Implementing the collector robot
The role of the collector is to safely retrieve the identified treasures within the grid. The collector has no color sensor and so depends on the information transmitted by the scout to function properly. When the Pilolo system is initialized, the collector robot waits in its home while it listens to the messages being transmitted by the scout. It only moves after the scout has finished exploring the whole grid and returned home. Two versions of the collector robot were designed: version 1 and version 2. Version 1 retrieved treasures in the order in which the information was received from the scout. As a result, the total path taken by the robot was not optimized. Again, the wavefront path-planning algorithm was used by the collector, to safely get to the location of the treasure, using the shortest distance. After receiving the coordinates of all the obstacles and treasures, Version 1 marks all cells containing obstacles with the value 1. Afterwards, the destination cell, the first cell received containing a treasure, is marked with the value 2. The wavefront algorithm is then run. With the collector’s home location as the start location, the safest and shortest path is traced to the destination cell. The robot follows this path. After that, the marked grid is cleared of all values except those of the obstacle cells. The process is repeated using the next treasure cell received and the robot’s current position as the start location. Version 2 retrieved treasures using the travelling salesman algorithm. With this algorithm, the object closest to the robot was first retrieved, and subsequently, the next object closest to the robot’s current position was retrieved. This was repeated until all the treasures had been collected. Again, the wavefront algorithm was used. After the collector has finished receiving the coordinates of all the obstacles and treasures, it marks the obstacle cells and sets the destination cell to its home cell. The wavefront algorithm is then run to populate the grid with values. Afterwards, each treasure cell’s location is checked against the populated grid for a corresponding value. The value from the grid indicates its distance from the current destination cell. This is done using all the locations of the treasure cells. The treasure cell with the least value is closest to the destination cell and so, it is the first one retrieved by the collector. After retrieval, this treasure cell is removed from the list of treasures. The entire process is repeated but using the current position of the collector as the destination cell. After all the treasures have been collected, the robot sets its home cell as a destination cell and uses wavefront to trace the shortest path from its last position to its home. There was one major challenge encountered with version 2. After designing the algorithm, the collector failed to do the expected when the algorithm was implemented on the robot. The algorithm seemed right however, we looked at it, but the robot did not acquire treasures in expected manner. After a series of debugging with the RobotC debugger, it was realized that the wavefront algorithm did not populate the entire grid as assumed. There was a terminating condition of the algorithm to end when the start location had been marked. As a result, the shortest distances of the treasures were not accurately been calculated. After correcting this error, the robot finally worked as expected.
Results and Conclusion
During the demonstration, the expected results were achieved. See Figure 3 for an example of a successful demonstration. A grid was filled with a number of blue and yellow cards. The scout robot was able to comb the whole grid while detecting all the obstacles and treasures. After it had finished exploring the grid, the collector robot began to move and went to all the cells identified as containing treasures. This was done using the optimal path. After retrieving all the treasures, the collector was able to get back to its home.
This was indeed a challenging and exciting task. Throughout the semester, we have been working with single robots, and so for one to be able to combine more than one is thrilling. Additionally, working with two robots taught us a few lessons. For instance, one thing could work on one robot but not work on the other. For instance, we had to use two separate movement routines for the robots although, they were similar in appearance and build. Another important lesson was to develop a common and understandable medium for communication. Communication between the robots was possible because of the protocol we developed. Without that, messages being transmitted by the scout would have been meaningless to the collector.
In conclusion, this project can be extended for use in various fields. For instance, it can be extended for use in the mines. A number of situations arise annually, where we have people trapped underground in mines. Scout robots can be sent with chemical and other sensors to explore an area, and then later retrieval robots can be sent to rescue people.