Setup
Motivation
- New orders arrive after the vehicle has left.
- 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
- 25 MovingAI maps across 5 domains.
- The full mission has goals.
- Only the nearest goals are known at launch.
- is swept over .
- The remaining () goals are added goals.
- They are added once the known goals are reached.
- 5 domains 5 maps 5 pairs 5 values of = 625 measurements.
Metrics
Algorithms
- INC: Incremental kA*.
- AGG: kA*-MIN (lazy and optimized).
- ORA: AGG knows all goals at launch (instead of only ).
- BFS: -BFS (goals pop in true cost order).
Metrics
- Expansion
- Memory
- Runtime
Defined in Goal Geometry › Metrics.
Measured over the whole mission (all goals).
Results
Expansion
| Nodes | Ratio to INC | ||||||
|---|---|---|---|---|---|---|---|
| INC | BFS | ORA | AGG | BFS | ORA | AGG | |
| every r | 43K | 161K | 43K | 43K | 3.7× | 1.00× | 1.00× |
Insights | Expansion:
- Mission addition does not affect expanded nodes.
By definition, AGG and INC expand the same nodes (up to borderline). - BFS/INC = 3.7× at every .
Both expand the same nodes for all goals, whatever is.
Memory
| 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× |
Insights | Memory:
- AGG’s memory is U-shaped in (lowest at ).
Each OPEN node stores h-values memory grows with .
Small many added goals large after the addition.
Large many known goals large before the addition.
lowest peak (AGG never tracks over 100 goals at once). - INC and BFS are addition-immune (stable at any ).
BFS and INC memory follows expansions, which do not depend on .
Runtime
| 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× |
Insights | Runtime:
- The less AGG knows at launch, the faster it runs.
Smaller fewer h-calcs per node. - INC and BFS are addition-immune (stable at any ).
INC solves goals one by one; BFS expands regardless of the goals.
Summary
Takeaways:
- Late goal arrival helps AGG, but INC still wins at every .
- INC and BFS are immune to mission addition in all metrics.
INC solves goals one by one; BFS expands regardless of the goals.