I'm trying to apply A* search on orienteering to get the optimal route to take. The inputs are two files - one image file which explains the terrains and one text file to define elevations. I calculate the terrain difficulty based on pre-set values to define how fast the terrain can be traversed. I've also defined the elevation difficulty based on slope (downward slope gives faster speeds and vice versa).
The terrain and elevation data is stored in matrices (list of lists). The inputs are therefore indices which is the same as points on the map. Two inputs are provided - eg:
start = [230,327]
end = [241,347]
The problem is that my code keeps re-visiting the nodes that are already present in the visited Queue. The node is defined as follows:
class Node:
def __init__(self,value,parent,start=[],goal=[]):
self.children = []
self.parent = parent
self.value = value
self.timeToGoal = 0.0000
self.timeTravelled = 0.0000
if parent:
timeToParent = self.parent.timeTravelled
[parentX, parentY] = parent.value
[currentX, currentY] = self.value
xDiff = abs(currentX - parentX)
yDiff = abs(currentX - parentX)
distance = 12.7627
if xDiff == 0 and yDiff != 0:
distance = 10.29
elif xDiff != 0 and yDiff == 0:
distance = 7.55
# distanceFromParent = math.sqrt(((currentX - parentX) ** 2) - (currentY - parentY) ** 2)
speedFromParent = 1.388 * calculateTerrainDifficulty( terrainMap[currentX][currentY]) * calculateElevationDifficulty(elevationMap[parentX][parentY], elevationMap[currentX][currentY], distance)
timeTravelledFromParent = 0
if speedFromParent != 0:
timeTravelledFromParent = distance / speedFromParent
else:
"Error: Speed from Parent Cannot Be Zero"
self.timeTravelled = timeToParent + timeTravelledFromParent
self.path = parent.path[:]
self.path.append(value)
self.start = parent.start
self.goal = parent.goal
else:
self.path = [value]
self.start = start
self.goal = goal
def GetTime(self):
pass
def CreateChildren(self):
pass
I also used a SubNode class for defining the functions, with time being defined as the time to self + pythagorean hypotenuse distance to goal:
class SubNode(Node):
def __init__(self, value, parent, start=[], goal=[]):
super(SubNode, self).__init__(value, parent, start, goal)
self.timeToGoal = self.GetTime()
def GetTime(self):
if self.value == self.goal:
return 0
[currentX, currentY] = self.value
[targetX, targetY] = self.goal
parentTime = 0
if self.parent:
parentTime = self.timeTravelled
heuristicTime = 99999.99
# Pythagorean Hypotenuse - Straight-line Distance
distance = math.sqrt(((int(currentX) - int(targetX)) ** 2) + (int(currentY)- int(targetY)) ** 2)
speed = 1.38 * calculateTerrainDifficulty(terrainMap[currentX][currentY])
if speed != 0:
heuristicTime = distance / speed
heuristicTime=heuristicTime+parentTime
return heuristicTime
def CreateChildren(self):
if not self.children:
dirs = [-1, 0, 1]
[xVal, yVal] = self.value
for xDir in dirs:
newXVal = xVal + xDir
if newXVal < 0 or newXVal > 394: continue
for yDir in dirs:
newYVal = yVal + yDir
if ((xVal == newXVal) and (yVal == newYVal)) or (newYVal < 0 or newYVal > 499) or (
calculateTerrainDifficulty(terrainMap[newXVal][newYVal]) == 0):
continue
child = SubNode([newXVal, newYVal], self)
self.children.append(child)
The A* search class was defined as follows. You can see that I have put the condition in there to make sure nodes are not revisited, and when I put a print in there I can see that the condition is met multiple times.
class AStarSearch:
def __init__(self, start, goal):
self.path = []
self.visitedQueue = []
self.priorityQueue = PriorityQueue()
self.start = start
self.goal = goal
def Search(self):
startNode = SubNode(self.start, 0, self.start, self.goal)
count = 0
self.priorityQueue.put((0, count, startNode))
while (not self.path and self.priorityQueue.qsize()):
closestChild = self.priorityQueue.get()[2]e
closestChild.CreateChildren()
self.visitedQueue.append(closestChild.value)
for child in closestChild.children:
if child.value not in self.visitedQueue:
count += 1
if not child.timeToGoal:
self.path = child.path
break
self.priorityQueue.put((child.timeToGoal, child.value, child))
if not self.path:
print("Not possible to reach goal")
return self.path
Due to some reason, my program keeps re-visiting some nodes (as I can see from the output when I print the visited queue. How can i avoid this?
[[230, 327], [231, 326], [229, 326], [231, 325], [231, 328], [229, 328], [231, 327], [229, 327], [231, 327], [229, 327], [229, 325], [231, 324], [230, 323], [231, 329], [229, 329], [231, 327], [229, 327], [229, 324], [231, 330], [231, 323], [229, 330], [229, 331]]
Another problem I'm facing is this one:
TypeError: unorderable types: SubNode() < SubNode()
Is there a way to overcome this one also without changing the use of python's Priority Queue?
You need to add a test on closestChild instead of its children:
closestChild = self.priorityQueue.get()[2]e
if closesChild.value not in self.visitedQueue:
closestChild.CreateChildren()
self.visitedQueue.append(closestChild.value)
Otherwise, you can say you visit n1 and then n2, both linking to node n3. n3 is added twice in the priorityqueue, so it is popped twice, then added twice to visitedQueue.
The condition if child.value not in self.visitedQueue: is then useful to speed up things (by keeping a smaller priority queue), but not necessary (since unnecessary objects in priorityQueue will be thrown away when unpiling them).
About the error you're getting: PriorityQueue does not support custom ordering, which is what you need for your priority queue, so you'll have to make a custom one. There is an example here. Obviously your _get_priority function would need to return timeTravelled instead of item[1]
EDIT 3: We (tobias_k and I) first said you need to implement the __eq__ function for SubNode so that python knows when two of them are equal, but it is actually not the case since you're storing only the values in self.visitedQueue.