The main goal of the project is to create a software and algorithmic infrastructure for holding competitions between two physical robots moving simultaneously among static and dynamic obstacles. The competition includes two teams, with each team controlling a single robot. Each robot has its own start position and target position. The goal of each team is to reach its target position before the other team does.
The project was designed and implemented with continuity in mind. The project itself can be divided to two parts – the implementation of the software infrastructure used for controlling the robot and holding the competition, and the implementation of the motion planning algorithm. It is expected that the software infrastructure will be used in future workshops, where students will replace the motion planning algorithm with their own algorithms.
The following objectives were achieved as part of the project:
- Controlling the iRobot Create – we created a software library for controlling the iRobot Create and retrieving information from its sensors. In addition, we have also performed some hardware modifications in order to add an additional distance sensor to the robot.
- Creating a software foundation for the competition – we created software that can be used in order to either hold a competition between two robots, or run a single robot through the maze. The software is built in a way that will allow extending it so that different motion planning algorithms can be used in the future.
- Implementing an algorithm for motion planning among dynamic and static obstacles – we have implemented an algorithm based on the PRM (Probabilistic Roadmap) algorithm for motion planning among static and dynamic obstacles.
The iRobot Create
The physical robot that was used in the project is the iRobot Create. The iRobot Create is a complete robot development kit that allows you to control the robot’s behavior programmatically. In order to communicate with the robot we have used an additional device called BAM. The BAM adds Bluetooth ability to the robot, thus allowing to control it from a remote computer.
The iRobot Create conforms to a protocol called Create Open Interface. As part of the project we have implemented a software library that implements the Create Open Interface protocol. The library allows to control the robot over Bluetooth and to retrieve information from its sensors.
Due to the poor quality of the internal iRobot Create’s distance sensor, we have decided to add an additional distance sensor. For that purpose we have used the MaxSonar-EZ0 ultrasonic distance sensor, which provides high quality distance readings for up to 6 meters.
The following image shows the iRobot Create with the attached distance sensor:
The Software
As part of the project we provide a GUI application that can be used to either hold a competition between two robots or run a single robot through a maze.
In single-player mode the application loads a scene file that contains the start position of the robot, the end position of the robot and the static obstacles. The application displays the position of the robot as it moves through the maze. The application can display the roadmap, the Minkowski sum calculation and dynamic obstacles that are detected using the distance sensor.
In competition mode the application works over TCP/IP with one instance acting as a referee and two other instances acting as competitors, with each of them controlling a single robot. The two robots are displayed at the same time on the referee instance.
The following image shows the GUI in single player mode:
The Algorithm
As part of the project we have modified and implemented the PRM algorithm so that it could handle dynamic obstacles. The algorithm uses the Minkowski sum of the obstacles and the robot in order to obtain the free and forbidden spaces. It then samples random configurations in the free space, and attempts to connect them to their k nearest neighbors, thus obtaining a roadmap. The roadmap is then used in order to plot a path between the start and target configurations with respect to the static obstacles.
The robot moves across edges of the static path. When a dynamic obstacle that would collide with the robot is detected, the edge that the robot is currently moving on is temporarily removed from the roadmap. The algorithm then looks for a new path on the roadmap, and when such a path is found the algorithm checks whether the new path collides with the dynamic obstacle. In case a collision does occur, the algorithm temporarily removes the colliding edges from the roadmap and performs another query. This process repeats itself until a non-colliding path is found.
In addition, due to the low rotation speed of the robot, we perform smoothing over the chosen paths. The smoothing is used in order to remove the number of vertices in the path, thus reducing the number of rotations that are required by the robot.
Videos of the Competition
The videos show two iRobot Creates in competition mode, with a remote-controlled Roomba acting as a dynamic obstacle.