The organizers provide a heightmap of the marsyard. This heightmap can then be interpreted and provide insights into where the rover can drive and where an obstacle or terrain that is too steep is located. Figure 1 below indicates how the interpreted map looks like in order to mark terrain as traversable or intraversable.
Fig.1 - Behavior Tree structure
Finding the shortest path in an environment is a common and well studied problem. One of the most famous algorithms is Dijkstra's algorithm. It always finds the shortest path to every node in a weighted graph. However, it's exhaustive and doesn't assume any knowledge about the graph and therefore not the most efficient algorithm for the project. A* (A-star) uses the estimated distance to another node as a heuristic to guide the alogrithm. It was used in the previous iteration. However, A* is not designed for dynamic routing, which would be a benefit in a possibly changing environment. Therefore, we chose D* Lite (D-Star Lite) which is an improved version of A* that saves it's state and allows for fast recalculation of the shortest path in case obstacles are detected. D* is very complex, which is why we chose D* Lite because it is similar but much simpler.
The concept of Behavior Trees is widely used in robotics and especially in autonomous systems. They allow for a modular design as every key aspect of controlling behavior is implemented in a separate node of the tree. Later on, the behavior can easily be both adjusted but also extended to suit further needs. In this project, another benefit is that the code is more readable and can be interpreted and adjusted more easily by future team members.
Fig.2 - Behavior Tree structure
This year's rover can rotate each wheel independently and thus allows for different movement than previous iterations or perhaps a car. In the current implementation, crab steering is used which is when all wheels are rotated to match their angles. Although the rover could also drive curves, thanks to crab steering, the autonomous system can reach every point in space by driving a straight line from the current location. It just needs to adjust the wheels and either turn the wheels forwards or backwards.
Fig.3 - Crab steering concept
