New way of doing the A* Algorithm

Question

I wrote a Python script for implementing an A* algorithm. Map, Start and Goal are given.

The code works well as far as I tested it but I want to get feedback from the best out there too. So I am sharing the code here. Map is given to you as pickle file.

In the code M is:

class Map:
    def __init__(self, G):
        self._graph = G
        self.intersections = networkx.get_node_attributes(G, "pos")
        self.roads = [list(G[node]) for node in G.nodes()]

Graph = pickle.load(pickleFile)    
M = Map(Graph)

Start/Goal are two integers representing nodes.

def shortest_path(M, start, goal):
    explored = set([start])
    frontier = dict([(i,[start]) for i in M.roads[start]]) if start!=goal else {start:[]}
    while frontier:
        explore = g_h(frontier,goal,M)
        for i in [i for i in M.roads[explore] if i not in frontier.keys()|explored]:
            frontier[i]=frontier[explore]+[explore]
        frontier = cleanse_frontier(frontier,M)
        if explore==goal:return frontier[explore]+[explore]#break when goal is explored.               
        explored.add(explore)
        del frontier[explore]#once explored remove it from frontier. 

def g_h(frontier,goal,M):
    g_h = dict([(path_cost(frontier[node]+[node],M)+heuristic(node,goal,M),node) for node in frontier])  
    return g_h[min(g_h)]

def heuristic(p1,p2,M):#Euclidean Heuristic from the node to the goal node
    M=M.intersections 
    return ((M[p1][0]-M[p2][0])**2+(M[p1][1]-M[p2][1])**2)**0.5

def path_cost(path,M,cost=0):#Euclidean distance for the path
    M=M.intersections 
    for i in range(len(path)-1):
        cost += ((M[path[i]][0]-M[path[i+1]][0])**2+(M[path[i]][1]-M[path[i+1]][1])**2)**0.5
    return cost

def cleanse_frontier(frontier,M):
    """If any node can be removed from the frontier if that can be reached 
    through a shorter path from another node of the frontier, remove it 
    from frontier"""
    for node in list(frontier):
        for i in [i for i in frontier if i!=node]:
            if node not in frontier:continue                
            if frontier[i]==frontier[node]:continue
            if i not in M.roads[node]:continue
            if path_cost(frontier[node]+[node]+[i],M)<path_cost(frontier[i]+[i],M):
                del frontier[i]
    return frontier

Answer 1

A suggestion I have is to use a heap data structure to store the costs, so that min can be calculated in logarithmic time.

Answer 2

I don't use Python very often - so my broader knowledge is lacking - but I think this deserves a proper answer none-the-less!

Efficiency

You haven't explicitly asked about efficiency, but if you need A* then you probably care about it, and there is plenty to be said. I'm starting with it because it influences some decisions I'll make later on about other stuff

Frontier search

As Rejith Raghavan indicates, you currently keeping the frontier nodes in a data-structure without any information about their cost, and the g_h method is expected to find the node with the smallest heuristic, which is does by effectively flattening it. There are a couple of inefficiencies here:

• You are recalculating the path-cost and heuristic cost of each frontier node every time step. Your path_cost method is a very expensive non-constant time operation! As a simple rule of thumb, sqrt is slow, and any trig function requires a sqrt. If you are deep into the search, the path lengths will become steadily longer. Recommendation: store the path cost and its sum with the heuristic cost in a data-structure, so you only have to compute it once. An added benefit is that when you create/update a node with the next segment, you need only compute the cost of that segment, and add it to the existing cost (and then add on the new heuristic).

• Finding the 'smallest' element in an unsorted list is a linear-time cost (if the list has n elements, you have to look at all n of them to find the smallest). Using a priority queue of some sort (e.g. a Heap) will reduce this to a logarithmic lookup. This would require rethinking how you store the frontier, and implementing the above suggestion of storing the costs. More advanced priority queues (with update methods) will allows you to effectively preserve your system of keeping the best route to each known node, but I'm afraid I don't know if there are any options built into Python. Unless memory is severely limited, you will probably benefit even by having a growing heap of 'dead' nodes (which can be detected by re-purposing your explored set to check if explore is in explored at the start of the while loop).

• g_h (which is a terrible name) itself isn't very efficient, as it constructs a whole new dictionary, and then interrogates that, rather than performing a simple enumeration and pulling out the smallest entry. This won't, however, significantly effect your time-complexity (unless you are unlikely with your hash functions, in which case it could), so perhaps go for readability rather than racing speed here (hopefully some of the changes below will make it more readable).

cleanse_frontier

This method is quite horrifying... Basically, it looks for nodes which have already been expanded. Much better, would be to simply keep a dictionary that maps a node to a cost, and maintain this cost as the smallest recognised for that node (no entry implies it hasn't been seen yet). Then, when you add a node to a frontier, just check that the cost of the candidate is less than the recorded cost, and if it isn't, don't record the new candidate. This would replace the (broken) i not in frontier.keys()|explored check, which currently rejects candidates where a (potentially worse) candidate is already given: I've not run your code, but I don't think it is a correct implementation of A* for this reason.

Path List

I would be inclined to switch your lists of segments from a conventional list to an immutable linked list. Unless I have forgotten everything about Python, I think [stuff]+[stuff] will result in the allocation of a new contiguous list. This means that every time you create a new path, you are allocating more memory and performing a copy. An immutable linked list (e.g. as found in 'functional' languages) would allow you to more efficiently represent what is really an upside down 'tree' of paths, without the cost of copying the whole path for every new frontier path. I'm not sure what options you might have for this, and I wouldn't worry about this too much.

Points

You are currently storing the path to a frontier node as a list of indexes into a table of lists of coordinates.

You are currently storing your intersection locations as lists. Your code explicitly supports having exactly 2 coordinates (x, y), but this isn't conveyed anywhere in your code. I could try to feed your program 3 coordinates (x, y, z), and it would run just fine, only it wouldn't be using the third coordinate and I would be completely unaware. You expect a coordinate pair, so require a coordinate pair: use a class with explicit x and y attributes, and give it a sensible name:

class Point:
    def __init__(self, x, y):
        this.X = x
        this.Y = y

_(You'll have to forgive any syntax aberrations, or failure to adhere to conventions: I thankfully don't have to use Python much these days. If anyone feels like tidying my code up for the common good, I'd welcome it)

This will turn this line:

((M[path[i]][0]-M[path[i+1]][0])**2+(M[path[i]][1]-M[path[i+1]][1])**2)**0.5

Into this:

((M[path[i]].X-M[path[i+1]].X)**2+(M[path[i]].Y-M[path[i+1]].Y)**2)**0.5

Effectively the same piece of code appears twice (once in heuristic(,,) and once in path_cost(,,). It is a classic exploitation of Pythagoras's theorem, which everyone happens to know we use for computing line distances in Euclidean space. But your code doesn't say any of this (granted, there is a comment above expressing the intent, which is good), it is just some maths which we hope has brackets in the right places.

Now that we have a Point class, it doesn't seem unreasonable to add a method to compute the distance between two points.

    def DistanceTo(self, other):
        squareDistance = (self.X - other.X)**2 + (self.Y - other.Y)**2
        return quareDistance**0.5

This means we can rewrite heuristic(,,) thus:

# Euclidean Heuristic from the node to the goal node
def heuristic(node, goal, M):
    return M.intersections[node].DistanceTo(M.intersections[goal])

A similar change can be made in path_cost. You'll note that I have renamed your parameters, and removed the M=M.intersections call. Your function is mathematically symmetric, but anyone calling the method will have no clue what p1 and p2 mean (which is the goal?). You seem to do a lot of M=M.intersections, presumably to avoid cluttering code with long attribute names. Now that we have the DistanceTo method, the line is much easier to read, and there is no need for a shorter name. Even if a shorter name was warranted, reassigning M is misleading (it took me completely by surprise), and I would avoid doing this.

By using a Point class, you'd need to update the code to build the Map. I'm afraid I don't understand what it is currently doing, so I can't advise how to do that.

Paths

You are storing your paths as lists also. Above I suggested you record the costs of the path along with the path itself (in the interests of efficiency).

class Path: def init(self, pathSegments, pathCost, heuristicCost): this.PathSegments = pathSegments this.PathCost = pathCost this.HeuristicCost = pathCost + heuristicCost

This will make it much more obvious what your frontier dictionary is recording.

Misc

I won't discuss the exposed API, because I don't understand Python's module system, but some sort of documentation is warranted (e.g. to describe the shape of G (which needs a better name (graph?) before building a Map (what type is "pos"?)). Ideally only the shortest_path function and any public types (Map, Point, and perhaps Path) would be exposed, as the other methods are all implementation details.

You are inconsistent with your padding of function parameters with spaces (e.g. shortest_path(M, start, goal): vs. path_cost(path,M,cost=0):#). I don't know what the conventions are in Python, but you should be consistent. personally, I would always pad definitions and calls: it helps to break up the arguments, making the code easier to scan. I'd also put a space before any end-of-line comments, and I'd add a couple of line-breaks in to break up dense methods a bit. Some more spaces in dense expressions would also be appreciated.

I completely missed the return condition when skimming shortest_code. Move the return onto a new line. You don't have a return statement for when the search fails (there is no path). This might be OK, but I'd prefer an explicit acknowledgement. I would much prefer, also, an explicit if goal == start: statement. Currently that check is hidden off the right of the screen beside a nasty looking list-comprehension, uses the horrible ternary if, and it is less than clear how the check is meant to work, all of which makes it a maintenance concern.

The return in cleanse_frontier is redundant, because it modifies the dictionary passed to it. This creates a confusing API, as it implies that it will be returning a modified clone of the parameter.

I've mentioned naming throughout this, so I'll just say here that naming is really important if you want maintainability.