How can I implement tremaux algo in arduino line follower to navigate and create map?

Question

The Map1

The task is divided into 2 runs, In first run, We have to navigate through whole map and reach the end mark taking all checkpoints. In second run, using the mapping from first run we have to follow the shortest path.

I am reading Algos and codes from days, I know the steps that should be taken, Navigate the maze using Tremaux algo and turning right at each possble junction. then Save that map in memory and use djikstra algo or A* algo to find the shortest path. But how to implement it practically?

Also since all the dictances and angles are known and also the wheel dia, motor rpm, bot width then Can I skip wheel encoders and use calculation instead?

Answer 1

I would highly recommend using the encoders over estimating travel distance by rpm + time. Estimating motor velocity is notoriously tricky. Especially at slow speeds.

A direct measurement is always better.

Answer 2

A good starting point is to solve the problem first in simulation. If the algorithm not work on a 2D map on screen it will never work on a real arduino. For inspiration github is a good ressource. There are many implementions available [1] [2]. After analyzing the sourcecode of somebody else it is time for writing the code from bottom up. In most programming languages the concept of "creating a library" is well suited for iterative development. The first methods in the library deals with pathplanning and obstacle avoidance and later additional features like "motor rotation per minute" will be added. The development cycle is testdriven, that means that after programming a small function, the code will be tried out in simulation and on a real robot. In most cases the development cycle is very slow, it is possible that even after one month of work no substantial progress is visible. Sometimes the code will result in a working robot, and sometimes not. It depends on the experience, the team and the invested workhours.

Answer 3

A good way to work once you have your map : turn your map in a weighted graph, were where the vertices are only at crosses and the weight is the length beetween the points represented by the vertices. Then running an A* or a djikstra will be simple.