# What is the most suitable AI technique to use for path planning?

I am making a firetruck using Arduino Uno with flame sensors and ultrasonic sensors to detect how to move and where to go. As this is a project for my university, I am asked to implement AI in it for path planning.

I am not sure whether to use something like A* technique or ID3 decision tree or if there is something better than both to implement path planning for my robot. Any suggestions?

• AVR-based Arduinos have very limited processing power. They do not have hardware floating-point support, for example. Many AI algorithms involve doing matrix math, which will be very slow on an AVR based Arduino. I suggest a higher powered processor like a Raspberry Pi would be a better choice. – Duncan C Dec 21 '19 at 18:17
• @DuncanC i would but i already have arduino and my project is due soon, we are asked for a simple way to implement the AI just to plan the path to the fire – mushter Dec 21 '19 at 18:43
• Can you give more details about how the path finding algorithm would work? .i.e. is the computation local or you have the chance to compute on a pc and send instructions to the Arduino? (The second approach seems the most promising to me). The ultrasonic sensor data is stored somewhere to map the environment? – Alvin Sartor Dec 22 '19 at 8:14
• @AlvinSartor I am not sure yet how I should work with it,I thought maybe I can code it in a way that while the robot is roaming around (before finding fire) it would store coordinates of obstacles it finds so that when it does detect flame it would use that info to find best path to flame, or i would just make up a dataset to use for an id3 decision tree – mushter Dec 24 '19 at 15:24
• Ok. The first step is being able to calculate your position. Maybe using the ultrasonic sensor or calculating the distance/direction each time the wheels spin. – Alvin Sartor Dec 24 '19 at 22:04

## 1 Answer

If I had to implement a path exploration/finding algorithm on a robot, I would follow these steps:

1. Make sure you can detect your position. You need to be able to record your position otherwise you have no reference for the exploration. You don't need a global positioning system (like GPS), a local one is more than enough in your case. This means that the robot must know that it has been switched on in position (0,0). If you go straight for 5 meters, you'll update it to (5,0) or something like that.
Knowing how much you moved and towards where is the difficult thing.

2. Once you can know where you are, it is time to record it. As you want to explore the environment, you might want to create a tree with states on the nodes. The node can be open if you can still explore around it, closed if the exploration has been done.
To get the path from a node to another, A* works more than enough.

3. To know what is around you, you can use the sensors to explore the surroundings and know the position of the obstacles.

This is the general idea:

Tree tree = new Tree()
Node first = new Node(Here)
tree.Add(first)

Node current = first

while(true) {
ExploreAround(current)
var nodes = CreateSurroundingNodes()
tree.Add(nodes)
current.State = closed
var next = PickNearestOpenNode()
MoveTo(next)
WaitUntilRobotIsOn(next)
current = next
}


In my bachelor thesis I was implementing a very similar algorithm on a drone on Unity3D. You can find the package here. You can get an idea out of it.

Here is a video of how it worked: https://youtu.be/Xrh9-4Bfcew

• This is super helpful! I will try to see how I can mark down coordinates as the robot roams around in the specified area, Thanks a lot! – mushter Dec 26 '19 at 14:08