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) 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:

A* search algorithm implementation in python

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!

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.

Advertisement

Answer