A robot that is able to map the environment in 3D using the built in sensors. It can be remote controlled using the keyboard, tracks It's own position and orientation and able to navigate through the environment.

85% of the models were made in Solid Edge. After we throw away the idea of the vacuum cleaner, we had to remodel the whole robot except the battery pack. Designing the frame was one of the hardest. It took more than two weeks to finalize the model. To make the chassis optimal for printing, I had to cut it into two pieces. The two sides are bound together with 3 screws back and one at the front. The front-wheel holder also keeps the two sides in one. The other problematic part was the top cover. It made of four separate pieces because of the 10-degrees angle design and required 8 screws to be held together. The print time of the whole body was 39 hours and 40 minutes. Here you can see the print-time/part diagram.

Material selection

For printing, we used two types of plastics. PLA (yellow) for the supports and PETG (black) for the frame and heavily stressed parts.

Other parts

The internal design was very tight. In the end, everything just fitted into its place. These are the following components that had to fit in:
- Battery pack (at the middle)
- 4 IR sensors (2 front, 2 back)
- 3 Ultrasonic sensors
- Modified SG90 servos and supports
- 2 HAL sensors and supports
- Planetary wheel
- Raspberry Pi with stands
- Gyroscope and H-Bridge (under Raspberry)
- 5V 5A DC-DC converter

A* pathfinding

We used the A* algorithm for pathfinding. It's the most widespread algorithm for pathfinding these days. The best thing in this algorithm, that it always finds the shortest path and runs faster than the Dijkstra algorithm.

Criteria of the selection

- Turn less
- Always find the path if it possible
- Make sure that the found path is the shortest

Choosing the best algorithm

Although there are several good algorithm on the internet, it didn't take long to reduce the list to two types of algorithms. Those were the A* and the Greedy Best First Search (GBFS). Both of them are successors of the Dijkstra algorithm. Whats makes them better, that they have Heuristics. Unlike Dijkstra's algorithm where you mostly brute force the search, these techniques apply weights on each individual node that tells you which way to go. The difference between the two, that A* follows a well restricted rule set meanwhile the GBFS pushes forward until it bumps into obstacle then starts seeking for a way to continue just like A*. In summary, if you want the shortest path and the runtime not matters the A* is the answer. If you need an algorithm that runs fast (even realtime) but a bit inaccurate, use GBFS. It is noteworthy that the GBFS makes more turn and can be mislead with promising dead-end mazes.

How A* works?

A* is an Informed Search Algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost in our situation the distance. It does this by maintaining a tree of paths originating at the start node and extending those paths one edge at a time until its reach the given goal. At each iteration, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* uses three weights G, H and F to select the path that minimizes the cost to the goal. G is the distance from the start. H is the distance to the goal. F is the sum of the previous two. When A* steps forward it always select the node with the lowes F value. If you are interested in
A* Algorithm and Path Smoothing , check out my article here! I recommend taking a look at my teammate's site for a more detailed explanation about 3D mapping and hardware control here!