OMSPP - Mission Cancellation

Performance Experiments on Early Goal Cancellation

Setup

Motivation

  1. New information arrives.
  2. The budget runs out.

Let’s see how mission cancellation affects the algorithms’ performance.

Experiments

  1. 25 MovingAI maps across 5 domains.
  2. We fix the number of goals to k=200k=200.
  3. rr is the number of goals reached before cancellation.
  4. rr is swept over {1,50,100,150,199}\{1, 50, 100, 150, 199\}.
  5. The remaining (k−rk-r) goals are cancelled goals.
  6. 5 domains ×\times 5 maps ×\times 5 pairs ×\times 5 values of rr = 625 measurements.
Figure 1: Mission Cancellation at rr.
Metrics

Algorithms

  1. INC: Incremental kA*.
  2. AGG: kA*-MIN (lazy and optimized).
  3. ORA: AGG searches only the rr nearest goals (instead of all kk).
  4. BFS: kk-BFS (goals pop in true cost order).

Metrics

  1. Expansion
  2. Memory
  3. Runtime

Defined in Goal Geometry › Metrics.
Measured from launch to the rr-th goal.

Results
Expansion
Figure 2: Expanded Nodes by rr.
Nodes Ratio to INC
r INC BFS ORA AGG BFS ORA AGG
1 36.3K 148K 36.3K 34.2K 4.1× 1.00× 0.94×
50 40.4K 152K 40.5K 39.2K 3.8× 1.00× 0.97×
100 42.1K 155K 42.2K 41.5K 3.7× 1.00× 0.98×
150 42.9K 158K 42.9K 42.5K 3.7× 1.00× 0.99×
199 43.3K 161K 43.3K 43.3K 3.7× 1.00× 1.00×
Table 1: Expanded Nodes by rr.
Insights | Expansion:
  1. Mission cancellation does not significantly affect expanded nodes.
    By definition, AGG and INC expand the same nodes (up to borderline).
  2. INC’s expansion edge over BFS shrinks slightly as kk (here rr) grows.
    Higher rr ⇒\Rightarrow higher goal dispersion ⇒\Rightarrow less reuse between goals for INC.
Memory
Figure 3: Peak Memory by rr.
Slots Ratio to INC
r INC BFS ORA AGG BFS ORA AGG
1 36.9K 148K 37.4K 163K 4.0× 1.0× 4.4×
50 41.2K 152K 75.9K 212K 3.7× 1.8× 5.1×
100 42.9K 155K 119K 212K 3.6× 2.8× 4.9×
150 43.7K 158K 166K 212K 3.6× 3.8× 4.9×
199 44.2K 162K 211K 212K 3.7× 4.8× 4.8×
Table 2: Peak Memory by rr.
Insights | Memory:
  1. Mission cancellation further increases INC’s memory advantage over AGG.
    AGG stores an h-vector for all kk goals, including the (k−rk-r) cancelled goals.
  2. INC’s memory advantage over AGG is relatively stable (∼\sim 5×) at every rr.
    AGG peaks early (by r=50r=50); INC’s memory grows only slowly after.
  3. BFS’s memory overhead over INC is relatively stable (∼\sim 4×) at every rr.
    BFS and INC memory follow expansions; clustered goals add few expansions after the first.
Runtime
Figure 4: Runtime by rr.
Seconds Ratio to INC
r INC BFS ORA AGG BFS ORA AGG
1 2.01 4.65 2.73 28.01 2.3× 1.4× 14.0×
50 2.51 4.78 11.13 32.94 1.9× 4.4× 13.1×
100 2.89 4.88 20.06 35.20 1.7× 6.9× 12.2×
150 3.23 4.98 29.38 36.46 1.5× 9.1× 11.3×
199 3.58 5.13 37.94 37.52 1.4× 10.6× 10.5×
Table 3: Runtime by rr.
Insights | Runtime:
  1. INC beats AGG even when AGG knows the cancelled goals (ORA).
    ORA behaves like regular AGG with k=rk=r (no mission cancellation).
  2. INC’s advantage grows when the cancelled goals are unknown (AGG).
    AGG computes h-values for the (k−r)(k-r) cancelled goals that INC and ORA do not.
  3. Earlier cancellation raises AGG’s runtime ratio to INC.
    rr low ⇒\Rightarrow (k−rk-r) high.
  4. BFS’s runtime ratio to INC falls as rr grows (2.3× → 1.4×).
    Unrelated to cancellation: INC’s edge over BFS shrinks as kk (here rr) grows.
Summary
Takeaways:
  1. Mission cancellation further favors INC in runtime and memory.
    AGG treats (k−rk-r) cancelled goals the same as active goals, while INC ignores them.
  2. Earlier cancellation raises AGG’s runtime ratio to INC.
    rr low ⇒\Rightarrow (k−rk-r) high.
  3. There is no significant effect on expanded nodes.
    By definition, AGG and INC expand the same nodes (up to borderline).