PathFinder - using heuristicWeight to implement fractional costs

SystemParadox

The effect of the heuristicWeight option was discussed previously. However, I believe there are some errors in that post, so I'll start by clarifying how I understand the heuristicWeight to work:

A-star uses f(n) = g(n) + weight × h(n), where g(n) is the actual cost from origin → node and h(n) is the estimated cost from node → goal. The important thing is that h(n) is admissible, which means that h(n) is always less than or equal to the real cost.
In the case of screeps, I expect h(n) = range(n, goal)
If weight = 0, A-star works exactly like Djikstra, expanding nodes in all directions equally. Guaranteed to find the shortest path, but very wasteful of CPU
If weight is very large, A-star works like greedy best-first search. It heads straight for the goal without ever backtracking. Fast, but the path is probably not optimal
If weight = 1 and h(n) is admissible then we are guaranteed to get the shortest path
If weight > 1 then we find a path more quickly, but not guaranteed to be absolutely optimal
Since h(n) is admissable I don't see any reason why you would ever use weight < 1

Now, the pathfinder only accepts integer cost values. What I'm trying to do is implement fractional costs.

For example, when planning roads you might use plainCost: 1, swampCost: 1. This will give the shortest possible road, but it doesn't take into account that roads on swamp tiles are more expensive to build and maintain than plains. If you could use plainCost: 1, swampCost: 1.01 then the pathfinder would always choose plains over swamp, but not at the expense of making the path longer.

So by my understanding we should be able to get the equivalent behaviour with { plainCost: 100, swampCost: 101, heuristicWeight: 100 }. However, I'm getting some really odd results. It's finding the right path, but for some reason increasing the heuristicWeight causes it to use more CPU:

global.testPath = function testPath(plainCost, swampCost, weight) {
    swampCost = swampCost || plainCost;
    weight = weight || plainCost;
    let origin = new RoomPosition(40, 38, 'W36S29');
    let goal = new RoomPosition(2, 21, 'W36S29');
    let result = PathFinder.search(origin, goal, {
        maxOps: 10000,
        plainCost: plainCost,
        swampCost: swampCost,
        heuristicWeight: weight,
    });
    let visual = new RoomVisual(origin.roomName);
    visual.poly(result.path, {fill: 'transparent', stroke: '#fff', lineStyle: 'dashed', strokeWidth: .15, opacity: .1});
    result.path = result.path.length;
    return JSON.stringify(result);
};

testPath(1)
{"path":38,"ops":14,"cost":38,"incomplete":false}
testPath(2)
{"path":38,"ops":14,"cost":76,"incomplete":false}
testPath(3)
{"path":38,"ops":14,"cost":114,"incomplete":false}
testPath(4)
{"path":38,"ops":14,"cost":152,"incomplete":false}
testPath(5)
{"path":38,"ops":14,"cost":190,"incomplete":false}
testPath(6)
{"path":38,"ops":14,"cost":228,"incomplete":false}
testPath(7)
{"path":38,"ops":14,"cost":266,"incomplete":false}
testPath(8)
{"path":38,"ops":14,"cost":304,"incomplete":false}
testPath(9)
{"path":38,"ops":14,"cost":342,"incomplete":false}
testPath(10)
{"path":38,"ops":89,"cost":380,"incomplete":false}
testPath(11)
{"path":38,"ops":129,"cost":418,"incomplete":false}
testPath(12)
{"path":38,"ops":155,"cost":456,"incomplete":false}
testPath(13)
{"path":38,"ops":178,"cost":494,"incomplete":false}
testPath(20)
{"path":38,"ops":392,"cost":760,"incomplete":false}
testPath(100)
{"path":38,"ops":928,"cost":3800,"incomplete":false}

The strange thing is, I've tried this with lots of different settings, different origin/goal, and it's always the same - if the heuristicWeight is less than 10 it works as expected, but increasing the heuristicWeight beyond that causes a proportional increase in CPU cost.

I've read through the pathfinder source code but I still can't work out why this is happening.

Does anyone have any ideas?

Thanks!

SemperRabbit

I feel like the devs should be able to give you an answer on the CPU issues... this is from the PathFinder.CostMatrix section of the API.

You should avoid using large values in your CostMatrix and terrain cost flags. For example, running PathFinder.search with { plainCost: 1, swampCost: 5 } is faster than running it with {plainCost: 2, swampCost: 10 } even though your paths will be the same.

I myself would also love to know the reason... If they can't, then perhaps you should reach out to The_General as he wrote the PathFinder C++ code.

SystemParadox

From my understanding the reason that { plainCost: 2, swampCost: 10 } takes more CPU is because the estimated cost h(n) assumes that all tiles have cost 1, so it branches out more trying to find something with a cost of 1. Obviously this is useful if you're using a costMatrix with a bunch of cells set to cost 1 (e.g. for roads), but if you don't have anything with cost 1 it's pointless.

But what I'm doing is compensating for this by setting the heuristicWeight. Since h(n) is assuming a cost of 1, but the base cost is actually 2, setting heuristicWeight: 2 should give the same behaviour as { plainCost: 1 }. My tests confirm that this is the case, but only up to heuristicWeight: 9. After that something else seems to come into play here.

deft-code

I want more data now. Can you run this again tracking actual CPU used as well (and print ops/cpu). Also add these tests:

testPath(1, 1, 9)
testPath(9, 9, 1)
testPath(9, 9, 10)
testPath(10, 10, 9)
testPath(20, 20, 9)
testPath(9, 9, 20)

Pathfinder does not use plain A*. Is uses JPS and A* derivative. Plain A* is guaranteed optimal (best path, fewest inspected) for any graph traversal. JPS beats A* when executing on a uniform cost grid. Many screeps rooms are pretty uniform.

My theory is that the ops calculation has a bug it uses a JumpPoint and PathFinder reports inflated ops count. Or a Jump Point allows PathFinder to inspect many nodes for minimal CPU cost, so PathFinder over inspects to avoid the heavier cpu cost of possibly A* inspecting those same nodes. In either case we'd see higher ops cost withou a corresponding jump in cpu cost.

My fear would be that JumpPoint has a hard coded value of 5 in it somewhere and 10 causes it get an elevated rate of out of room positions causing the search to thrash and waste CPU and ops. If this is case I want to know if h triggers this behavior or the cost matrix.

SystemParadox

testPath(1, 1, 1)       length: 38, ops:  14 CPU: 0.25 ops/CPU:  56.39
testPath(2, 2, 2)       length: 38, ops:  14 CPU: 0.19 ops/CPU:  74.97
testPath(3, 3, 3)       length: 38, ops:  14 CPU: 0.18 ops/CPU:  75.74
testPath(4, 4, 4)       length: 38, ops:  14 CPU: 0.17 ops/CPU:  83.72
testPath(5, 5, 5)       length: 38, ops:  14 CPU: 0.17 ops/CPU:  84.21
testPath(6, 6, 6)       length: 38, ops:  14 CPU: 0.17 ops/CPU:  84.48
testPath(7, 7, 7)       length: 38, ops:  14 CPU: 0.17 ops/CPU:  84.67
testPath(8, 8, 8)       length: 38, ops:  14 CPU: 0.17 ops/CPU:  83.78
testPath(9, 9, 9)       length: 38, ops:  14 CPU: 0.17 ops/CPU:  84.78
testPath(10, 10, 10)    length: 38, ops:  89 CPU: 0.39 ops/CPU: 225.65
testPath(11, 11, 11)    length: 38, ops: 129 CPU: 0.53 ops/CPU: 242.89
testPath(12, 12, 12)    length: 38, ops: 155 CPU: 0.54 ops/CPU: 285.10
testPath(13, 13, 13)    length: 38, ops: 178 CPU: 0.60 ops/CPU: 297.97
testPath(20, 20, 20)    length: 38, ops: 392 CPU: 1.06 ops/CPU: 369.83
testPath(100, 100, 100) length: 38, ops: 928 CPU: 2.60 ops/CPU: 356.97
testPath(1, 1, 9)       length: 38, ops:   9 CPU: 0.16 ops/CPU:  54.63
testPath(9, 9, 1)       length: 38, ops: 867 CPU: 2.39 ops/CPU: 362.32
testPath(9, 9, 10)      length: 38, ops:  14 CPU: 0.18 ops/CPU:  75.75
testPath(10, 10, 9)     length: 38, ops:  89 CPU: 0.22 ops/CPU: 402.19
testPath(20, 20, 9)     length: 38, ops: 392 CPU: 0.58 ops/CPU: 675.35
testPath(9, 9, 20)      length: 38, ops:  14 CPU: 0.09 ops/CPU: 152.13

deft-code

Those numbers looked pretty bad so I played with it a bit myself. I always set the swamp to 5x the plains and never used a plains cost of more than 40.

The CPU is bit noisy so I ran each test 3 times and looked at the median. I noted that first run of any query was noisier than the rest. If I were going to do this for real I'd run 4 discard the first and take the median.

With normalized cpu the numbers don't look as bad but there is a definite increase in CPU with the greater ops (it's not just an accounting error). I should have been more methodical to get solid numbers but here were my impressions. I played around with short, medium and long paths, both intra-room and inter-room (just 2 rooms).

There is a per room overhead that looks to be about 0.1. I suspect this is the CostMatrix callback. I didn't use a custom callback so the overhead might change.

CPU increased with ops, More complex paths took more ops and more CPU. Roughly I'd guess per op cpu is less than 0.005. For the configurations that blow up ops the CPU cost does increase, but not as much; e.g. the CPU cost of each op during a blow up is much less but non zero.

What I'd like to do craft 2 paths: one short and one long and configure the short one to blow up so that it's ops are equal(ish) to the long one. That should give some solid number on how expensive blow ups are. But ultimately the answer is going to be not much

Exxion

Sorry for the necropost, but it turns out the reason for the strange behavior at 10 is pretty simple: The heuristic weight is silently capped at 9. I don't know why. Additionally, the costs are capped at 254, and none of the three values can be set below 1.

SystemParadox

This has been bugging me all this time so thank you!

I wonder why they're doing that.