> Map Preprocessing > ================= >
Differential Heuristics for A\* ------------------------------- While researching further, I came upon some hints of a concept called "differential heuristics". I tried to search further for this: * https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#approximate-heuristics * Slide 44: https://www.slideshare.net/StavrosVassos/interactive-objects-pathfindingpart3 * http://research.microsoft.com/pubs/154937/soda05.pdf <- this seems to be the original paper * https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4020/4340 In summary, differential heuristics involve an A\* `h(n)` function built from precomputed distances from multiple landmarks. The primary advantage of differential heuristics is that they make A\* search fewer nodes than e.g. Manhattan distance. Ideally, `h(n)` is the `distance(n, t)` where `t` is the destination. With differential heuristics, `h(n)` is then the maximum of `abs(distance(n, l) - distance(t, l))` among all landmarks `l`, where `t` is the destination. `distance(_, l)` for all landmarks is precomputed. Now of course in LN we cannot use heuristics like Manhattan distance anyway. But we can definitely use precomputed distances. I proposed a `getroutequick` which uses precomputed distances from the source in order to guide an algorithm towards the source. This is based on the observation that our source tends to be always a single location, our own node. However, we may still want to acquire a route that does not arise from our own node. For example, consider a variant of `permuteroute` that, if it cannot heal from the pivot to some postfix node within 3 hops, falls back to performing A\* from the pivot to the final destination. Presumably, the pivot is nearer to the destination and we are more likely to quickly reach the destination from the pivot rather than the actual payment source. Another example of creating a route not from our own node is generalized rebalancing. Rebalancing transfers funds from one of our local channels to another of our local channels. We can derive this path by finding a route from the counterparty of the source channel to the counterparty of the destination channel, exclude our own node from consideration in pathfinding. Then we just append the destination channel and prepend the source channel. (Admittedly a friend-of-friend limited subgraph like proposed by Rene will work almost as well and would still be much faster, but this can be a fallback in case we cannot find a rebalancing route when scanning the friend-of-friend.) Suppose we treat our own node as the single landmark in a differential heuristic system. When finding a route, the payee is actually the source and the payer (our own node) is the destination. The distance from the destination (the payer, our own node) to the landmark (again, our own node) --- i.e. `distance(t, l)` --- is 0, so the `abs(distance(n, l) - distance(t, l))` becomes `abs(distance(n, l) - 0)` becomes `distance(n, l)`. So differential heuristics is actually a generalization of the preprocessing I proposed earlier that enables us to use A\*, but only for routes arising from our own node. Thus, we can use this same preprocessed stored cost data of total-distance-from-our-own-node, not only to implement a `getroutequick` that works only for routes where our own node is one end of the route, but also for a `getroutequick` that can arise from any node. The speed benefit is much much greater for routes where we are one end of the route, but we still get the benefit of using A\* if neither end of the requested route is not our own node. As we would still want to store the preprocessed total-distance-from-our-own-node anyway to implement a `getroutequick` that uses A\* on an almost-exact heuristic, it means that we can implement a `getroutequick` from any node without increasing our memory usage, and with a relatively small tweak to the code. Specifically, we need to look up `distance(t, l)` where `t` is the start of the route, and to compute the heuristic, subtract this from `distance(n, l)` and get the absolute value. If the start of the route is our own node (which is the landmark `l`) then that distance is 0 and we automatically fall back to the A\* variant that uses an almost-exact heuristic to reach our own node. Further landmarks beyond our own node can be selected (preferably distant from our own node) to improve the speed of searching in the case where we need to find from an arbitrary node, at the cost of increasing the memory space needed. _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
