OMSPP - Mission Addition

Performance Experiments on Late Goal Arrival

Setup

Motivation

  1. New orders arrive after the vehicle has left.
  2. New targets are found after the mission has started.

Let’s see how mission addition affects the algorithms’ performance.
Mirror of OMSPP - Mission Cancellation (same maps, problems and algorithms).

Experiments

  1. 25 MovingAI maps across 5 domains.
  2. The full mission has k=200k=200 goals.
  3. Only the rr nearest goals are known at launch.
  4. rr is swept over {1,50,100,150,199}\{1, 50, 100, 150, 199\}.
  5. The remaining (k−rk-r) goals are added goals.
  6. They are added once the rr known goals are reached.
  7. 5 domains ×\times 5 maps ×\times 5 pairs ×\times 5 values of rr = 625 measurements.
Figure 1: Mission Addition at rr.
Metrics

Algorithms

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

Metrics

  1. Expansion
  2. Memory
  3. Runtime

Defined in Goal Geometry › Metrics.
Measured over the whole mission (all kk goals).

Results
Expansion
Figure 2: Expanded Nodes by rr.
Nodes Ratio to INC
INC BFS ORA AGG BFS ORA AGG
every r 43K 161K 43K 43K 3.7× 1.00× 1.00×
Table 1: Expanded Nodes (same at every rr).
Insights | Expansion:
  1. Mission addition does not affect expanded nodes.
    By definition, AGG and INC expand the same nodes (up to borderline).
  2. BFS/INC = 3.7× at every rr.
    Both expand the same nodes for all kk goals, whatever rr is.
Memory
Figure 3: Peak Memory by rr.
Slots Ratio to INC
r INC BFS ORA AGG BFS ORA AGG
1 44K 162K 212K 194K 3.7× 4.8× 4.4×
50 44K 162K 212K 166K 3.7× 4.8× 3.8×
100 44K 162K 212K 135K 3.7× 4.8× 3.1×
150 44K 162K 212K 166K 3.7× 4.8× 3.7×
199 44K 162K 212K 211K 3.7× 4.8× 4.8×
Table 2: Peak Memory by rr.
Insights | Memory:
  1. AGG’s memory is U-shaped in rr (lowest at r=100r=100).
    Each OPEN node stores |A||A| h-values ⇒\Rightarrow memory grows with |A||A|.
    Small rr ⇒\Rightarrow many added goals ⇒\Rightarrow large |A||A| after the addition.
    Large rr ⇒\Rightarrow many known goals ⇒\Rightarrow large |A||A| before the addition.
    r=100r=100 ⇒\Rightarrow lowest peak (AGG never tracks over 100 goals at once).
  2. INC and BFS are addition-immune (stable at any rr).
    BFS and INC memory follows expansions, which do not depend on rr.
Runtime
Figure 4: Runtime by rr.
Seconds Ratio to INC
r INC BFS ORA AGG BFS ORA AGG
1 3.71 5.18 35.92 10.37 1.4× 9.7× 2.8×
50 3.72 5.18 35.92 14.67 1.4× 9.7× 3.9×
100 3.73 5.18 35.92 21.18 1.4× 9.6× 5.7×
150 3.70 5.18 35.92 28.66 1.4× 9.7× 7.7×
199 3.62 5.18 35.92 36.00 1.4× 9.9× 10.0×
Table 3: Runtime by rr.
Insights | Runtime:
  1. The less AGG knows at launch, the faster it runs.
    Smaller |A||A| ⇒\Rightarrow fewer h-calcs per node.
  2. INC and BFS are addition-immune (stable at any rr).
    INC solves goals one by one; BFS expands regardless of the goals.
Summary
Takeaways:
  1. Late goal arrival helps AGG, but INC still wins at every rr.
  2. INC and BFS are immune to mission addition in all metrics.
    INC solves goals one by one; BFS expands regardless of the goals.