Brainstormers Tribots path planning

While the robot strategy decides on a higher level what action the robot should take, e.g. going to the ball or dribbling the ball towards the opponent goal, the motor controller expects to get driving command like “drive forward with 1.7m/s” or “drive sidewards with 0.5m/s while turning with -2.1rad/s”. The step between the higher level strategy and the low level driving commands must be filled by a path planning and path following method.

Path planning approaches have to calculate a possible trajectory towards the final destination and control the velocity of the robot. They must take into account obstacles that might block the direct way towards the goal and the physical properties of the robot that do not allow to change the movement suddenly. Moreover, in RoboCup the obstacles are moving themselves and there might be some obstacles that are not detected by the vision system due to occlusion or due to the limited range of the omnidirectional sensor.

The trajectory planning approach of the Brainstormers Tribots is based on a geometric analysis of the configuration on the field and a physical model of the dynamic properties of the robot. It does not generate whole trajectories but only way-points, maximal velocities at way-points, and virtual passages which should never be left to guide the robot to its destination.

The trajectory is replanned every 33 milliseconds with the previous trajectory being the starting point for the new calculation. If the direct way towards the destination is feasible it is preferred. Otherwise, way-points are generated and for each one it is checked whether it can be directly reached and whether it provides a possibility to continue the way towards the final destination.

Among all possible way-points the algorithm chooses the one that yields the shortest way towards the goal, that has a small risk of collision with obstacles and that is likely to provide a better position to reach the final destination than the current robot position. To avoid getting stuck, elements of Tabu-search are added.

The image shows the executed trajectory of the robot (cyan). The final destination is depicted with the magenta spot, the current way-point by the yellow spot. The obstacles are depicted in black. Not all obstacles are visible at this point in time. In the beginning, the robot tried to reach its destination by passing the obstacles on the left until it realized that there is no passage between the field boundary and the obstacles. Then, it changed its plan and passed the obstacles on the right.