OMSPP - Goal Geometry

Goal Remoteness and Goal Dispersion

Setup

Motivation

  1. Goal Remoteness: How far the goals are from the start.
  2. Goal Dispersion: How far the goals are from each other.

How do they affect INC vs AGG?

Experiments

  1. Maps: 25 MovingAI maps, 5 domains.
  2. Remoteness band: S→G0S \to G_0 Manhattan distance {100,200,300,400,500}\{100, 200, 300, 400, 500\}.
  3. Dispersion radius: k=200k = 200 goals drawn within {20,60,100,140,180}\{20, 60, 100, 140, 180\} of G0G_0.
  4. Problems: 25 maps ×\times 5 bands ×\times 5 radii =625= 625.
Figure 1: Goal Remoteness and Goal Dispersion.
Figure 2: Max Map-Length per Map.
Max-length = rows + cols (≈ corner to corner).
Figure 3: Share of Random SS–GG Pairs Within 500.
Rare corner-to-corner pairs are left out (no room for dispersion).
Metrics

Algorithms

  1. INC: Incremental kA*.
  2. AGG: kA*-MIN (lazy and optimized).
  3. BFS: kk-BFS (goals pop in true cost order).

Informed (guided by hh): INC, AGG. Uninformed: BFS.

Metrics

  1. H-Calcs: number of h(n,G)h(n, G) evaluations.
    INC: in search and at each retarget (hh re-aimed at the next goal).
    AGG: one per active goal, when a node is first generated.
    BFS: none.
  2. Runtime : cumulative wall-clock in seconds.
  3. Memory: peak number of slots.
    INC, BFS: |CLOSED|+|OPEN||\mathrm{CLOSED}| + |\mathrm{OPEN}|.
    AGG: |CLOSED|+|OPEN|⋅(1+|A|)|\mathrm{CLOSED}| + |\mathrm{OPEN}| \cdot (1 + |A|).
    Each OPEN node also stores an hh-vector, one value per active goal.
  4. Expansion: number of expanded nodes.

Legend:
CLOSED
OPEN

Figure 4: Expanded Nodes on a 4 × 4 Grid.

Legend:
CLOSED
OPEN
h-vectors

Figure 5: Peak Memory on a 4 × 4 Grid.
Remoteness
H-Calcs
Figure 6: Heuristic Calculations by Goal Remoteness.
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×
Table 1: Heuristic Calculations by Goal Remoteness.

Reasons

hh error: c*−hc^* - h from SS to a goal (c*c^*: the optimal cost; mean over the goals).

With goal remoteness, the hh error grows (57 → 280 steps).
hh ignores obstacles ⇒\Rightarrow Each obstacle in the way adds a detour ⇒\Rightarrow A farther goal has more of them.

Real A* runs on a toy grid, one goal each.

Runtime
Figure 7: Runtime by Goal Remoteness.
(*) 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×
Table 2: Runtime by Goal Remoteness.

Reasons

AGG
High remoteness ⇒\Rightarrow Wider H-Calcs ratio ⇒\Rightarrow Wider runtime ratio.

BFS
High remoteness ⇒\Rightarrow Fewer h-calcs per INC node ⇒\Rightarrow INC overtakes BFS.

Memory
Figure 8: Peak Memory by Goal Remoteness.
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×
Table 3: Peak Memory by Goal Remoteness.

Reasons

AGG
High remoteness ⇒\Rightarrow CLOSED (equal in both) ≫ OPEN.

BFS
High remoteness ⇒\Rightarrow BFS fills the map (37% → 99% of its free cells) ⇒\Rightarrow INC catches up.

Real runs on a toy grid, kk = 3 (AGG at its memory peak; the wall makes hh err, as obstacles do on real maps).

Figure 9: AGG Memory Components by Goal Remoteness.
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×
Table 4: AGG Memory Components by Goal Remoteness.
Expansion
Figure 10: Expanded Nodes by Goal Remoteness.
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×
Table 5: Expanded Nodes by Goal Remoteness.

Reasons

AGG
Both expand the same nodes by design (up to ties).

BFS
High remoteness ⇒\Rightarrow BFS fills the map (29% → 97% of its free cells) ⇒\Rightarrow INC catches up.

Real runs on a toy grid, kk = 3 (the wall makes hh err, as obstacles do on real maps).

Dispersion
H-Calcs
Figure 11: Heuristic Calculations by Goal Dispersion.
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×
Table 6: Heuristic Calculations by Goal Dispersion.

Reasons

AGG
High dispersion ⇒\Rightarrow Fewer nodes before the first goal ⇒\Rightarrow Smaller |A||A| per AGG node.

Figure 12: avg Heuristic Calculations per Generated Node.
Both generate nearly the same nodes: per-node h-calcs set the gap.
AGG: earlier generation ⇒\Rightarrow more active goals |A||A| ⇒\Rightarrow more h-calcs.
INC: more goal switches survived in OPEN ⇒\Rightarrow more h-calcs.
Figure 13: Toy Problem: Goal Dispersion Alone.
SS, G1G_1 and remoteness are fixed.
G2G_2 moves along the diagonal: only dispersion changes.
before the first goal, 1 h-calc before the first goal, 2 h-calcs after the first goal, 1 h-calc
Figure 14: Toy: H-Calcs by Goal Dispersion.
Before the first goal, INC leads clearly.
After it, the gap narrows as dispersion grows.
AGG never overtakes INC.
Runtime
Figure 15: Runtime by Goal Dispersion.
(*) 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×
Table 7: Runtime by Goal Dispersion.

Reasons

AGG
High dispersion ⇒\Rightarrow Narrower H-Calcs ratio ⇒\Rightarrow Narrower runtime ratio.

BFS
High dispersion ⇒\Rightarrow Narrower expansions ratio ⇒\Rightarrow INC’s h-calcs no longer pay off.

Memory
Figure 16: Peak Memory by Goal Dispersion.
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×
Table 8: Peak Memory by Goal Dispersion.

Reasons

AGG
High dispersion ⇒\Rightarrow Smaller |A||A| at AGG’s peak ⇒\Rightarrow Narrower memory ratio.

Figure 17: AGG Active Goals at Its Memory Peak.

BFS
High dispersion ⇒\Rightarrow Narrower expansions ratio ⇒\Rightarrow Narrower memory ratio.

Expansion
Figure 18: Expanded Nodes by Goal Dispersion.
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×
Table 9: Expanded Nodes by Goal Dispersion.

Reasons

BFS
High dispersion ⇒\Rightarrow Less reuse between goals ⇒\Rightarrow Informed search grows faster than BFS.

Real runs on an open toy grid, kk = 3.

Plane
Runtime
best INC ⇒
Figure 19: Runtime Ratios to INC.
Memory
best INC ⇒
Figure 20: Memory Ratios to INC.
Expansion
best INC ⇒
Figure 21: Expansion Ratios to INC.