OMSPP - 3D Grids

What Changes When the Grid Gains Height

Motivation

Why 3D Grids

  1. Many agents move in 3D: aerial, underwater, virtual.
  2. Their tasks are often OMSPP: one start → many goals.
    • Delivery drones: one depot → many drop-offs.
    • Warehouse drones: one dock → many rack slots.
    • Underwater vehicles: one ship → many sampling sites.
    • Video games: one flying unit → many targets.

Let’s see how 3D grids affect INC and AGG performance.

Figure 1: A 3D OMSPP Toy Instance.
3 × 3 × 3 voxels.
Drag to rotate.

Definition

  1. 3D grid: space split into voxels, each free or an obstacle.
    Voxel: a volume pixel (a 3D cell), the usual name in 3D pathfinding.
  2. Up to 26 successors per node, vs 8 on an 8-conn 2D grid.
    6 face moves (cost 1), 12 edge diagonals (√2), 8 corner diagonals (√3).
Figure 2: Moves in 3D.
Face, edge and corner neighbors of the center voxel.
Drag to rotate.
  1. No corner cutting (as on 8-conn 2D grids).
Figure 3: No Corner Cutting in 3D.
Drag to rotate.
  1. h: 3D-Octile
    1. face = number of face moves.
    2. edge = number of edge diagonals.
    3. corner = number of corner diagonals.
    4. h = face + √2 edge + √3 corner.
Figure 4: The 3D-Octile h: Two Examples.
Drag to rotate.
  1. The search space grows cubically with distance.

Legend:
4-conn 2D
8-conn 2D
26-conn 3D

Figure 5: Expanded Nodes within d Moves.
BFS on an open grid (no obstacles).
Maps

4 Domains, 3 Maps Each

Canonization: for simplicity and consistency, we search only each map’s biggest reachable region.
Every other free voxel becomes an obstacle (random nodes in small sealed regions would give many unreachable pairs).

  1. Plants: real chemical plant layouts, with large and narrow voids around equipment (inside it: unreachable).

    plant03 · 84M voxels

    plant04 · 155M voxels

    plant05 · 175M voxels

  2. Sandstone: rock pores from CT scans, made for flow simulations.

    Parker · 64M voxels

    Leopard · 64M voxels

    Bentheimer · 64M voxels

  3. Warframe: levels of a space combat game: asteroids in open space.

    BC1 · 67M voxels

    A2 · 89M voxels

    FB1 · 168M voxels

  4. Descent: levels of a flying game: rooms and branching tunnels (outside them: unreachable).

    levels2 · 106M voxels

    level01 · 131M voxels

    level11 · 170M voxels

Figure 6: The Study Maps.
After canonization: the biggest reachable region only.
Dimensions Size Branch­ing Factor Heur­istic Quality
Map L W H Voxels Reach­able % Reach­able
Plants plant03 560 331 453 84M 77M 92.2% 25.8 0.93
Plants plant04 731 445 477 155M 147M 94.8% 25.8 0.95
Plants plant05 1257 457 304 175M 167M 95.7% 25.9 0.95
Sandstone Parker 400 400 400 64M 9M 13.3% 20.8 0.73
Sandstone Leopard 400 400 400 64M 13M 19.8% 23.1 0.80
Sandstone Bentheimer 400 400 400 64M 17M 26.8% 23.3 0.89
Warframe BC1 853 245 321 67M 67M 99.5% 25.8 0.98
Warframe A2 896 390 255 89M 89M 99.8% 25.8 0.99
Warframe FB1 812 358 578 168M 168M 99.7% 25.9 0.99
Descent levels2 794 541 247 106M 6M 5.8% 24.9 0.87
Descent level01 767 668 256 131M 4M 3.3% 24.6 0.63
Descent level11 676 542 463 170M 5M 2.8% 24.5 0.43
Table 1: Map Size, Branching and Heuristic Quality.
Setup

Instances

  1. Maps: the 12 study maps.
  2. Pair: SS and G0G_0, a random free voxel pair.
    Goal remoteness: h(S,G0)h(S, G_0) ∈ {100, 125, 150, 175, 200} (± 5).
  3. Goals: 200 random free voxels within 20 face moves of G0G_0.
  4. Count: 300 instances (12 maps × 5 remoteness bands × 5 pairs).

Algorithms

  1. INC: Incremental kA*.
  2. AGG: kA*-MIN (lazy and optimized).
  3. DIJ: k-Dijkstra.

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

Metrics

  1. Expansion
  2. Memory
  3. H-Calcs
  4. Runtime

Defined in Goal Geometry › Metrics.

Results
Expansion

By Goal Remoteness

Figure 7: Expanded Nodes by Goal Remoteness.
Labels: DIJ/INC expansion ratios.
Nodes Ratio to INC
Remoteness INC AGG DIJ AGG DIJ
100 35K 35K 2.2M 1.00× 62×
125 127K 127K 3.8M 1.00× 30×
150 142K 142K 5.7M 1.00× 40×
175 180K 180K 7.7M 1.00× 43×
200 150K 150K 11M 1.00× 70×
Table 2: Expanded Nodes by Goal Remoteness.

Reasons

Informed search
h guides the search ⇒ the expanded nodes form a thin tube to the goals, growing in length only.

Uninformed search
No h ⇒ the expanded nodes form a ball around SS, growing in all 3 dimensions.

Figure 8: How DIJ and INC Expand (schematic).
Drag to rotate.

DIJ / INC (not monotonic)
3 of a band’s 60 instances (mostly Descent; h / c* 0.10–0.97, the rest 0.94) ⇒ 43–66% of its INC expansions ⇒ the ratio jumps from band to band.

Unlike 2D (Goal Geometry)
2D maps: high remoteness ⇒ BFS fills the map ⇒ INC catches up.
3D maps: far larger (4–168M reachable voxels) ⇒ their border caps DIJ’s ball less ⇒ INC does not catch up.

By Domain

Figure 9: Expanded Nodes by Domain (log scale).
Legend: INC, AGG, DIJ.
Nodes Ratio to INC Heur­istic Quality
Domain INC AGG DIJ AGG DIJ
Plants 11.9K 11.9K 10.3M 1.00× 861× 1.00
Sandstone 121K 121K 1.94M 1.00× 16× 0.86
Warframe 4.00K 4.00K 10.4M 1.00× 2,611× 1.00
Descent 370K 370K 1.29M 1.00× 3× 0.78
Table 3: Expanded Nodes by Domain.

Reasons

Informed search
Plants, Warframe domains: h ≈ c* ⇒ f rises off the paths ⇒ few nodes beyond them.
Descent domain: tunnels ⇒ h far below c* ⇒ many nodes with f below c*.

Uninformed search
No h ⇒ every node closer than the farthest goal ⇒ millions of nodes in open space.

By Domain and Goal Remoteness

Figure 10: DIJ / INC Expansion Ratio by Domain (log scale).
Each point: the median over the domain’s 15 instances in the band.
DIJ / INC
Domain 100 125 150 175 200
Plants 1,796× 3,064× 2,882× 4,547× 7,206×
Warframe 2,164× 3,347× 5,122× 3,012× 5,622×
Sandstone 24× 19× 20× 19× 15×
Descent 39× 10× 5× 7× 5×
Table 4: DIJ / INC by Domain and Goal Remoteness.

Reasons

DIJ
Plants, Warframe domains: open space far larger than its ball (≤ 36% of it at 200) ⇒ no border stops it ⇒ ×4.3–5.2 from 100 to 200.
Descent, Sandstone domains: tunnels and pores ⇒ its ball spreads along them only ⇒ ×3.5–4.7.

INC
Plants, Warframe domains: h ≈ c* ⇒ the paths and the goals only ⇒ ×1.3–1.7.
Descent, Sandstone domains: weak h ⇒ detours grow with remoteness ⇒ ×4.4–15.2.

As in 2D (Goal Geometry)
Descent, Sandstone domains: tunnels and pores cap DIJ’s ball, as a 2D map’s border does ⇒ INC catches up.

Memory

By Goal Remoteness

Figure 11: Peak Memory by Goal Remoteness (log scale).
Labels: AGG/INC and DIJ/INC memory ratios.
Slots Ratio to INC
Remoteness INC AGG DIJ AGG DIJ
100 48K 1.2M 2.2M 25× 47×
125 142K 1.6M 3.9M 11× 28×
150 159K 1.9M 5.9M 12× 37×
175 198K 2.3M 7.8M 12× 40×
200 170K 2.5M 11M 15× 63×
Table 5: Peak Memory by Goal Remoteness.

By Domain

Figure 12: Peak Memory by Domain (log scale).
Legend: INC, AGG, DIJ.
Slots Ratio to INC
Domain INC AGG DIJ AGG DIJ
Plants 29.6K 1.75M 10.5M 59× 355×
Sandstone 136K 1.90M 1.98M 14× 15×
Warframe 21.1K 1.67M 10.7M 79× 508×
Descent 387K 2.32M 1.31M 6× 3×
Table 6: Peak Memory by Domain.

Reasons

AGG
Every domain: about 11K nodes in OPEN ⇒ an h per active goal for each ⇒ 1.7–2.3M slots.

DIJ
Descent domain: tunnels ⇒ few nodes cheaper than the goals ⇒ fewer slots than AGG.

As in 2D (Goal Geometry)
OPEN’s h-vectors outweigh CLOSED ⇒ AGG’s memory follows its OPEN, not its expansions.

H-Calcs
Figure 13: H-Calcs by Goal Remoteness.
Labels: AGG/INC h-calc ratios.
H-Calcs Ratio to INC
Remoteness INC AGG AGG
100 1.9M 8.0M 4.2×
125 2.4M 26M 10.7×
150 2.9M 29M 10.3×
175 3.3M 37M 11.3×
200 3.6M 31M 8.6×
Table 7: H-Calcs by Goal Remoteness.
Runtime

By Goal Remoteness

Figure 14: Runtime by Goal Remoteness (log scale).
Labels: AGG/INC and DIJ/INC runtime ratios.
Seconds Ratio to INC
Remoteness INC AGG DIJ AGG DIJ
100 7.87 20.29 148.46 2.6× 19×
125 11.91 49.33 270.98 4.1× 23×
150 13.93 54.29 418.50 3.9× 30×
175 17.00 69.22 574.98 4.1× 34×
200 19.14 65.04 812.23 3.4× 42×
Table 8: Runtime by Goal Remoteness.

By Domain

Figure 15: Runtime by Domain (log scale).
Legend: INC, AGG, DIJ.
Seconds Ratio to INC
Domain INC AGG DIJ AGG DIJ
Plants 6.77 22.64 778.00 3.3× 115×
Sandstone 12.49 38.68 125.77 3.1× 10×
Warframe 5.76 19.60 793.12 3.4× 138×
Descent 30.87 125.61 83.22 4.1× 3×
Table 9: Runtime by Domain.

Reasons

AGG
Descent domain: weak h ⇒ only a few times fewer expansions than DIJ ⇒ up to 200 h-calcs per node cost more than they save.