Setup
Motivation
- New information arrives.
- The budget runs out.
Let’s see how mission cancellation affects the algorithms’ performance.
Experiments
- 25 MovingAI maps across 5 domains.
- We fix the number of goals to .
- is the number of goals reached before cancellation.
- is swept over .
- The remaining () goals are cancelled goals.
- 5 domains 5 maps 5 pairs 5 values of = 625 measurements.
Metrics
Algorithms
- INC: Incremental kA*.
- AGG: kA*-MIN (lazy and optimized).
- ORA: AGG searches only the nearest goals (instead of all ).
- BFS: -BFS (goals pop in true cost order).
Metrics
- Expansion
- Memory
- Runtime
Defined in Goal Geometry › Metrics.
Measured from launch to the -th goal.
Results
Expansion
| 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× |
Insights | Expansion:
- Mission cancellation does not significantly affect expanded nodes.
By definition, AGG and INC expand the same nodes (up to borderline). - INC’s expansion edge over BFS shrinks slightly as (here ) grows.
Higher higher goal dispersion less reuse between goals for INC.
Memory
| 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× |
Insights | Memory:
- Mission cancellation further increases INC’s memory advantage over AGG.
AGG stores an h-vector for all goals, including the () cancelled goals. - INC’s memory advantage over AGG is relatively stable ( 5×) at every .
AGG peaks early (by ); INC’s memory grows only slowly after. - BFS’s memory overhead over INC is relatively stable ( 4×) at every .
BFS and INC memory follow expansions; clustered goals add few expansions after the first.
Runtime
| 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× |
Insights | Runtime:
- INC beats AGG even when AGG knows the cancelled goals (ORA).
ORA behaves like regular AGG with (no mission cancellation). - INC’s advantage grows when the cancelled goals are unknown (AGG).
AGG computes h-values for the cancelled goals that INC and ORA do not. - Earlier cancellation raises AGG’s runtime ratio to INC.
low () high. - BFS’s runtime ratio to INC falls as grows (2.3× → 1.4×).
Unrelated to cancellation: INC’s edge over BFS shrinks as (here ) grows.
Summary
Takeaways:
- Mission cancellation further favors INC in runtime and memory.
AGG treats () cancelled goals the same as active goals, while INC ignores them. - Earlier cancellation raises AGG’s runtime ratio to INC.
low () high. - There is no significant effect on expanded nodes.
By definition, AGG and INC expand the same nodes (up to borderline).