AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT
AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT
This paper introduces the Architecturally Admissible Compressor (AAC), a method that adapts landmark-based A* heuristics to query demand within a fixed memory budget. The authors provide two continuous relaxations of the ALT algorithm, proving that relaxed and discrete optima coincide under exact landmark distances. AAC-CG, utilizing fractional relaxation and entropy regularization, achieves an approximation guarantee with a limiting factor of 1-1/e. Experiments on six road networks and two synthetic graphs show that AAC-CG reduces A* expansions by 1.9% to 22.7% compared to farthest-point ALT across 19 tested combinations of graph and memory budget, while achieving 99.6% of canonical greedy's mean heuristic value.
The authors present a theoretical framework and experimental evaluation of AAC, demonstrating reductions in A* expansions across multiple graph configurations while maintaining heuristic admissibility.
Source: arXiv Robotics — research abstracts · Read original article ↗
Loading article text…
What the source reports
Publisher-reported claims, with original evidence. These results have not been independently verified by RoboSignal.
Reported numbers
percent reduction in A expansions
1.9
View original evidence
e selection. For expected heuristic value, we prove an approximation guarantee with finite-step, oracle-error, and finite-sample terms. The limiting $1-1/e$ factor is optimal for arbitrary supplied pools and query distributions unless P${=}$NP. At matched label memory, AAC-CG reduces A* expansions by $1.9$-$22.7$% relative to farthest-point ALT (FPS-ALT) in all $19$ tested combinations of graph and memory budget acro
Open source S4percent reduction in A expansions
22.7
View original evidence
e selection. For expected heuristic value, we prove an approximation guarantee with finite-step, oracle-error, and finite-sample terms. The limiting $1-1/e$ factor is optimal for arbitrary supplied pools and query distributions unless P${=}$NP. At matched label memory, AAC-CG reduces A* expansions by $1.9$-$22.7$% relative to farthest-point ALT (FPS-ALT) in all $19$ tested combinations of graph and memory budget acro
Open source S4percent of canonical greedy mean heuristic value
99.6
View original evidence
ss six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, whil
Open source S5number of road networks tested
6
View original evidence
ss six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, whil
Open source S5number of synthetic graphs tested
2
View original evidence
ss six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, whil
Open source S5number of graph-budget pairs tested
19
View original evidence
e selection. For expected heuristic value, we prove an approximation guarantee with finite-step, oracle-error, and finite-sample terms. The limiting $1-1/e$ factor is optimal for arbitrary supplied pools and query distributions unless P${=}$NP. At matched label memory, AAC-CG reduces A* expansions by $1.9$-$22.7$% relative to farthest-point ALT (FPS-ALT) in all $19$ tested combinations of graph and memory budget acro
Open source S4number of graph-budget pairs tested
19
View original evidence
ss six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, whil
Open source S5number of query test splits per combination
1
View original evidence
ss six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, whil
Open source S5
- paper: not_reported
Source excerpts and review record
Automatically extracted; no manual editorial approval recorded.
e selection. For expected heuristic value, we prove an approximation guarantee with finite-step, oracle-error, and finite-sample terms. The limiting $1-1/e$ factor is optimal for arbitrary supplied pools and query distributions unless P${=}$NP. At matched label memory, AAC-CG reduces A* expansions by $1.9$-$22.7$% relative to farthest-point ALT (FPS-ALT) in all $19$ tested combinations of graph and memory budget acro
Open source S4
ss six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, whil
Open source S5
Source：arXiv Robotics — research abstracts · arxiv.org