Embedded Files
The main of this project was design three different graph based path planning algorithms in order to evaluate their performance.
Dijkstra
The dijkstra algorithm written for this project plans paths through a 2D map. The map is given as a logical array where 0 represent free cells while 1s represent obstacles. the nature of the algorithm written here follows a pseudo code as such:
• For each node n in the graph
• n.distance = Infinity
• Create an empty list. •
• start.distance = 0, add start to list.
• While list not empty • Let current = node in the list with the smallest distance, remove current from list
• For each node, n that is adjacent to current
• If n.distance > current.distance + length of edge from n to current
• n.distance = current.distance + length of edge from n to current
• n.parent = current • add n to list if it isn’t there already
The results of this algorithm written in Matlab (Click on the image to see animation)
A* algorithm
The A* algorithm written follows a very similar process to the dijkstra algorithm. The main difference in this case is that the path cells are selected based on an elected heuristic function for example either manhattan distance or euclidean distance. in this case euclidian distance was used:
The A* algorithm used in this case closely follows:
• For each node n in the graph
• n.f = Infinity, n.g = Infinity
• Create an empty list. • start.g = 0, start.f = H(start) add start to list.
• While list not empty
• Let current = node in the list with the smallest f value, remove current from list
• If (current == goal node) report success
• For each node, n that is adjacent to current
• If (n.g > (current.g + cost of edge from n to current))
• n.g = current.g + cost of edge from n to current
• n.f = n.g + H(n)
• n.parent = current
• add n to list if it isn’t there already
The results of this algorithm written in Matlab (Click on the image to see animation)
As we can see the A* algorithm visits fewer cells to reach goal.
Artificial potential fields
A different method to avoid obstacles to reach goal state. In this method the map is updated in such way that a repulsive field surrounds all obstacles and an attractive field is present in each cell that increase position gets closer to the end goal. The repulsive field is defined by:
Where d0 is a threshold value which for any distance above it the repulsive function is 0. p is the distance of each position in the map to the obstacles. The attractive function is also directly proportional to the euclidian distance of each position to the obstacle.
To direct the the path towards the goal gradient descent algorithm is used. This means that at each point on the map the next position is a unit step in both x and y direction towards the lower gradient position. It is important to mention that this algorithm is not robust towards local minimas. (Click on the image to see animation)
Page updated
Google Sites
Report abuse