Motivation
- Goal Remoteness: How far the goals are from the start.
- Goal Dispersion: How far the goals are from each other.
How do they affect INC vs AGG?
Experiments
- Maps: 25 MovingAI maps, 5 domains.
- Remoteness band: Manhattan distance .
- Dispersion radius: goals drawn within of .
- Problems: 25 maps 5 bands 5 radii .
Max-length = rows + cols (≈ corner to corner).
Rare corner-to-corner pairs are left out (no room for dispersion).
Algorithms
- INC: Incremental kA*.
- AGG: kA*-MIN (lazy and optimized).
- BFS: -BFS (goals pop in true cost order).
Informed (guided by ): INC, AGG. Uninformed: BFS.
Metrics
- H-Calcs: number of evaluations.
INC: in search and at each retarget ( re-aimed at the next goal).
AGG: one per active goal, when a node is first generated.
BFS: none. - Runtime
: cumulative wall-clock in seconds.
- Memory: peak number of slots.
INC, BFS: .
AGG: .
Each OPEN node also stores an -vector, one value per active goal. - Expansion: number of expanded nodes.
Legend:
CLOSED
OPEN
Legend:
CLOSED
OPEN
h-vectors
| H-Calcs | Ratio to INC | ||
|---|---|---|---|
| Remoteness | INC | AGG | AGG |
| 116 | 145K | 1.3M | 8.6× |
| 204 | 199K | 4.5M | 22.7× |
| 307 | 269K | 6.5M | 24.2× |
| 400 | 271K | 9.1M | 33.8× |
| 487 | 307K | 11M | 36.1× |
Reasons
error: from to a goal (: the optimal cost; mean over the goals).
With goal remoteness, the error grows (57 → 280 steps).
ignores obstacles Each obstacle in the way adds a detour A farther goal has more of them.
Real A* runs on a toy grid, one goal each.
(*) Crossover by linear interpolation.
| Seconds | Ratio to INC | ||||
|---|---|---|---|---|---|
| Remoteness | INC | BFS | AGG | BFS | AGG |
| 116 | 1.18 | 0.81 | 6.18 | 0.69× | 5.2× |
| 204 | 2.08 | 1.94 | 16.24 | 0.93× | 7.8× |
| 307 | 2.94 | 2.77 | 24.19 | 0.94× | 8.2× |
| 400 | 3.35 | 3.39 | 30.98 | 1.01× | 9.2× |
| 487 | 4.02 | 4.67 | 37.25 | 1.16× | 9.3× |
Reasons
AGG
High remoteness Wider H-Calcs ratio Wider runtime ratio.
BFS
High remoteness Fewer h-calcs per INC node INC overtakes BFS.
| Slots | Ratio to INC | ||||
|---|---|---|---|---|---|
| Remoteness | INC | BFS | AGG | BFS | AGG |
| 116 | 11K | 38K | 92K | 3.4× | 8.2× |
| 204 | 30K | 90K | 133K | 3.0× | 4.5× |
| 307 | 42K | 127K | 188K | 3.0× | 4.5× |
| 400 | 56K | 155K | 205K | 2.8× | 3.7× |
| 487 | 69K | 209K | 245K | 3.1× | 3.6× |
Reasons
AGG
High remoteness CLOSED (equal in both) ≫ OPEN.
BFS
High remoteness BFS fills the map (37% → 99% of its free cells) INC catches up.
Real runs on a toy grid, = 3 (AGG at its memory peak; the wall makes err, as obstacles do on real maps).
| Slots | Ratios | ||||
|---|---|---|---|---|---|
| Remoteness | CLOSED | OPEN | h-vectors | CLOSED / OPEN | h-vectors / CLOSED |
| 116 | 4.05K | 744 | 86.9K | 5.4× | 21.5× |
| 204 | 17.9K | 899 | 114K | 19.9× | 6.4× |
| 307 | 25.9K | 1.10K | 161K | 23.6× | 6.2× |
| 400 | 36.2K | 1.12K | 168K | 32.3× | 4.6× |
| 487 | 42.5K | 1.23K | 201K | 34.4× | 4.7× |
| Nodes | Ratio to INC | ||||
|---|---|---|---|---|---|
| Remoteness | INC | BFS | AGG | BFS | AGG |
| 116 | 9.9K | 37K | 9.9K | 3.8× | 0.99× |
| 204 | 28K | 89K | 28K | 3.2× | 1.00× |
| 307 | 40K | 127K | 40K | 3.2× | 1.00× |
| 400 | 54K | 155K | 54K | 2.9× | 1.00× |
| 487 | 67K | 209K | 67K | 3.1× | 1.00× |
Reasons
AGG
Both expand the same nodes by design (up to ties).
BFS
High remoteness BFS fills the map (29% → 97% of its free cells) INC catches up.
Real runs on a toy grid, = 3 (the wall makes err, as obstacles do on real maps).
| H-Calcs | Ratio to INC | ||
|---|---|---|---|
| Dispersion | INC | AGG | AGG |
| 17 | 142K | 5.4M | 37.8× |
| 45 | 203K | 6.1M | 30.2× |
| 72 | 246K | 6.6M | 26.6× |
| 96 | 282K | 7.0M | 24.9× |
| 120 | 318K | 7.4M | 23.3× |
Reasons
AGG
High dispersion Fewer nodes before the first goal Smaller per AGG node.
Both generate nearly the same nodes: per-node h-calcs set the gap.
AGG: earlier generation more active goals more h-calcs.
INC: more goal switches survived in OPEN more h-calcs.
, and remoteness are fixed.
moves along the diagonal: only dispersion changes.
Before the first goal, INC leads clearly.
After it, the gap narrows as dispersion grows.
AGG never overtakes INC.
(*) Crossover by linear interpolation.
| Seconds | Ratio to INC | ||||
|---|---|---|---|---|---|
| Dispersion | INC | BFS | AGG | BFS | AGG |
| 17 | 1.70 | 2.18 | 16.31 | 1.28× | 9.6× |
| 45 | 2.27 | 2.45 | 20.64 | 1.08× | 9.1× |
| 72 | 2.72 | 2.72 | 23.38 | 1.00× | 8.6× |
| 96 | 3.19 | 2.99 | 25.97 | 0.94× | 8.1× |
| 120 | 3.69 | 3.24 | 28.54 | 0.88× | 7.7× |
Reasons
AGG
High dispersion Narrower H-Calcs ratio Narrower runtime ratio.
BFS
High dispersion Narrower expansions ratio INC’s h-calcs no longer pay off.
| Slots | Ratio to INC | ||||
|---|---|---|---|---|---|
| Dispersion | INC | BFS | AGG | BFS | AGG |
| 17 | 29K | 100K | 139K | 3.5× | 4.9× |
| 45 | 35K | 112K | 153K | 3.2× | 4.3× |
| 72 | 41K | 124K | 171K | 3.0× | 4.2× |
| 96 | 47K | 136K | 191K | 2.9× | 4.0× |
| 120 | 55K | 147K | 210K | 2.7× | 3.8× |
Reasons
AGG
High dispersion Smaller at AGG’s peak Narrower memory ratio.
BFS
High dispersion Narrower expansions ratio Narrower memory ratio.
| Nodes | Ratio to INC | ||||
|---|---|---|---|---|---|
| Dispersion | INC | BFS | AGG | BFS | AGG |
| 17 | 28K | 100K | 28K | 3.6× | 1.00× |
| 45 | 34K | 111K | 34K | 3.3× | 1.00× |
| 72 | 39K | 123K | 39K | 3.1× | 1.00× |
| 96 | 45K | 135K | 45K | 3.0× | 1.00× |
| 120 | 53K | 147K | 53K | 2.8× | 1.00× |
Reasons
BFS
High dispersion Less reuse between goals Informed search grows faster than BFS.
Real runs on an open toy grid, = 3.