I am trying to build a very simple A* Search Algorithm in Python 3. Given the following distances for each node (considering S is the starting node and G the end one)
further_cost = {'s': 11.2, 'a': 9, 'b': 9.3, 'd': 6.2, 'c': 6.7, 'e': 4.2, 'f': 2.1, 'g': 0} previous_cost = {'s': 0, 'a': 2, 'b': 2.5, 'c': 4, 'd': 3, 'e': 3, 'f': 2.5, 'g': 2}
I want to write a function that finds the best path based on total cost (i.e., f(n) for those familiar with the terminology) for the following search space:
sp = {'s': ['a', 'b'], 'a': ['b', 'd', 's'], 'b': ['a', 'e', 'c'], 'c': ['b'], 'd': ['s', 'a', 'e'], 'e': ['d', 'b', 'f'], 'f': ['e', 'g']}
This is what I have written so far. The issue is that I cannot seem to implement dynamic programming. In other words, I cannot make it so that the algorithm selects the path having the lower f(n).
def extend(queue, state_space): current_path = queue[0] current_state = current_path[-1] extensions = state_space[current_state] newpaths = [] for ext in extensions: if not ext in current_path: # check for and don't add loops newpaths.append(current_path + ext) return newpaths def a_search(goal, state_space=sp, heuristic=further_cost, a = previous_cost, strategy='best', queue=['s']): print (queue) if not queue: print('Search failed') return False elif queue[0][-1] == 'g': print('Goal found with path {}'.format(queue[0])) return True else: new_paths = extend(queue, state_space) cost = {} for path in new_paths: cost[path] = 0 for node in path: if node == path[-1]: cost[path] += further_cost.get(node) + previous_cost.get(node) else: cost[path] += previous_cost.get(node) if strategy == 'best': #new_queue = sorted(new_paths + queue[1:], key=lambda x: cost[x[-1]]) new_queue = new_paths + queue[1:] new_queue = sorted(new_queue, key=cost.get) print(new_queue, cost) else: print('Unknown search algorithm') return False a_search(goal, state_space, heuristic, a, strategy, new_queue)
The function returns the following error:
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-105-dfe3fabe38db> in <module> ----> 1 a_search(['g'], sp, further_cost, previous_cost, 'best', ['s']) <ipython-input-104-f872f8359edc> in a_search(goal, state_space, heuristic, a, strategy, queue) 40 return False 41 ---> 42 a_search(goal, state_space, heuristic, a, strategy, new_queue) <ipython-input-104-f872f8359edc> in a_search(goal, state_space, heuristic, a, strategy, queue) 32 #new_queue = sorted(new_paths + queue[1:], key=lambda x: cost[x[-1]]) 33 new_queue = new_paths + queue[1:] ---> 34 new_queue = sorted(new_queue, key=cost.get) 35 36 print(new_queue, cost) TypeError: '<' not supported between instances of 'NoneType' and 'float'
I suspect I may be making some conceptual mistake here. Ay help would be appreciated!
Advertisement
Answer
Apparently you have some values in your cost dictionary that are of type None
. Perhaps the previous_cost.get
call returned None
for some early value.
I might suggest a different approach. Rather than having separate collections for each piece of data used by A*, you should group them into objects. Make a node object that overrides __lt__
and pass in your f and g scores and your parent to its constructor.