Adding cutoff to A* to allow early termination

[anders-rydbirk]

Hi,

We currently have a case where we build a graph with approx. 50_000 nodes and 230_000 edges. We do online search in the graph using nx.algorithms.shortest_paths.astar_path where we:

1. Search with a strict set of constraints using nx.subgraph_view
2. In case no result were found, relax the constraints

However, we experience that sometimes the target cannot be reached from the source during step 1, while the source is connected to fairly large subset of the graph. I.e. we end up exhausting most of the graph before defaulting to step 2. This can easily end up taking 2,5-3s of processing which exhausts our API.

Our idea was to introduce a cutoff to terminate the search early, similar to what already exists for the dijkstra implementations. For us, it would probably be set to X * heuristic(source, target).

Suggestion Ignore this below, it's incorrect, but we keep it for context in the discussion

@nx._dispatch(edge_attrs="weight", preserve_node_attrs="heuristic")
def astar_path(G, source, target, heuristic=None, weight="weight", cutoff=None):
...

        for neighbor, w in G_succ[curnode].items():
            cost = weight(curnode, neighbor, w)
            if cost is None:
                continue
            ncost = dist + cost
            if neighbor in enqueued:
                qcost, h = enqueued[neighbor]
                # if qcost <= ncost, a less costly path from the
                # neighbor to the source was already determined.
                # Therefore, we won't attempt to push this neighbor
                # to the queue
                if qcost <= ncost:
                    continue
            else:
                h = heuristic(neighbor, target)
            # SUGGESTION
            if cutoff and cutoff < dist + h:
                raise nx.NetworkXNoPath(f"Node {target} not reachable from {source} with cutoff {cutoff}")

...

Unless there's a big push against it, I wouldn't mind contributing this change as well.

[dschult]

I think a cutoff parameter is reasonable (though maybe tricky to get right) for the astar algorithm here.
Your suggestion looks to me like it would raise as soon as one attempted path is too long. This leaves other possibilities within the cutoff unexplored. Don't you want to explore all potential paths less than the cutoff? But maybe I am missing something.

[anders-rydbirk]

Wow, you're right. It shouldn't happen during the exploration of neighbours, it should happen after the check for whether it has reached the target. Then we would guarantee that we have explored all paths less than the cutoff given the priority queue. I've added the full while loop with the change below for completeness.

while queue:
        # Pop the smallest item from queue.
        # NOTE: I changed _ -> h_cur here
        h_cur, __, curnode, dist, parent = pop(queue)

        if curnode == target:
            path = [curnode]
            node = parent
            while node is not None:
                path.append(node)
                node = explored[node]
            path.reverse()
            return path
        # Suggestion: Add cuffof here: h_cur is ncost + h
        if cutoff and cutoff < h_cur:
            raise nx.NetworkXNoPath(f"Node {target} not reachable from {source} with cutoff {cutoff}")

        if curnode in explored:
            # Do not override the parent of starting node
            if explored[curnode] is None:
                continue

            # Skip bad paths that were enqueued before finding a better one
            qcost, h = enqueued[curnode]
            if qcost < dist:
                continue

        explored[curnode] = parent

        for neighbor, w in G_succ[curnode].items():
            cost = weight(curnode, neighbor, w)
            if cost is None:
                continue
            ncost = dist + cost
            if neighbor in enqueued:
                qcost, h = enqueued[neighbor]
                # if qcost <= ncost, a less costly path from the
                # neighbor to the source was already determined.
                # Therefore, we won't attempt to push this neighbor
                # to the queue
                if qcost <= ncost:
                    continue
            else:
                h = heuristic(neighbor, target)
            enqueued[neighbor] = ncost, h
            push(queue, (ncost + h, next(c), neighbor, ncost, curnode))

    raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}")

[dschult]

This is better -- but I'm still not convinced that we should make the cutoff based on the heuristic value. There is a choice there and I don't see a literature that uses either type of cutoff. Do you know of any papers or webpages that discuss how to make a cutoff for AStar? I could imagine that it applies the cutoff to ncost. That way a heuristic error doesn't affect the cutoff. But maybe I'm wrong and the way to go is to apply the cutoff to h_cur so that you stop searching when you expect to be over the cutoff. It'd be nice to have some outside advice rather than just making this up. :)

And of course, if this is implemented, we should include tests to make sure it works the way we expect.

[anders-rydbirk]

My general idea was that if we consider the heuristic admissible, we have the guarantee that h_cur is a lower bound for the total cost. In this case, you stop searching when you know you're over the cutoff.

Ofc, it depends on your heuristic implementation. I might also be biased by that the problem I'm trying to solve is geospatial and heuristics are easily admissible (birds eye distance for example).

I'll try to dig up papers.

@dschult I'll just like to call out I really appreciate that you take the time to explore the idea :)

[anders-rydbirk]

Okay, I've been trying to find papers, but to be honest, I think the original paper on A-star highlights it the best. Going by the definition of the evaluation function f:

$f(n) = g(n) + h(n)$

where $g(n)$ is the actual cost from source to $n$ and $h(n)$ is the actual cost of an optimal path from $n$ to the target.

It is then given for A* to be admissible that our heuristic $h'(n)$ must be $h'(n) <= h(n)$. I.e. when $g(n) + h'(n) > cutoff$, we are guaranteed that no path exists from $n$ to the target that satisfies the cutoff. Meaning, we could essentially add the cutoff check before enqueueing a node (and simply continue if it fails this check), or terminate the search when the algorithm explores a node $n$ that fails the cutoff check since $n$ would have the lowest $f(n)$ in the queue. In the example implementation I provided above, I technically allow for a path longer than the cutoff in the special case where curnode is the first node to surpass the cutoff, but at the same time is also the target.

Performance-wise, I would opt for not enqueueing a node we would not like to explore, but if we wanted to raise a specific exception like nx.NetworkXCutoffExceeded, we should opt for the latter approach which would allow for that.

I have time next week to give it a shot at implementation along with suitable tests.

[anders-rydbirk]

PR with implementation:
#7073