arXiv AI

FMT$^{\mathrm{X}}$: Lazy Wavefront Search for Dynamic Replanning

arXiv:2509. 08521v2 Announce Type: replace-cross Abstract: FMT$^{*}$ plans efficiently in static worlds by expanding a cost-ordered wavefront and collision-checking lazily, but its single-pass unvisited rule cannot revise paths when obstacles change.

arXiv AI
Sep 12

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

Probabilistic Focal Search (PFS) augments traditional Focal Search by probabilistically choosing between the standard heuristic-guided expansion and expanding the minimum‑f node in OPEN. This strategy advances the lower bound, enlarges the FOCAL frontier, and can dramatically reduce node expansions—up to 90% in some benchmarks such as N‑Puzzle and TSP—especially when long f_min plateaus delay useful FOCAL admissions. An anytime variant, APFS, outperforms other tested anytime algorithms on the Generalized Covering TSP, and the same probabilistic scheduler transfers to Dynamic Potential Search as Probabilistic Dynamic Potential Search (PDPS), though its effectiveness varies by domain and bound.

By Minh Vu Duc, Trung Le Huu, H\`a Minh Ho\`ang, Trung Thanh Nguyen, Phuong Khanh Nguyen, Huynh Thi Thanh Binh
arXiv Machine Learning
Sep 30

Local Search with Correlated Randomness

arXiv:2607.17469v2 Announce Type: replace-cross Abstract: How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer...

By Yunbei Xu
arXiv Machine Learning
Jun 11

Seeing Before Colliding: Anticipatory Safe RL with Frozen Vision-Language Models

arXiv:2606. 11266v1 Announce Type: new Abstract: The cost signal that constrained-RL algorithms optimize against is almost always reactive: the simulator emits a non-zero cost only after a collision has begun, and the Lagrange multiplier of PPO-Lagrangian grows only after the episode budget has been exceeded.

By Samuel Tetteh, Cody Fleming
arXiv AI
3d ago

Provably Optimal HBT Legalization in Seconds: Certified Optima Reveal Where the Headroom Really Lies

The paper presents GEO-Exact, an exact solver for Hybrid Bonding Terminal (HBT) legalization that achieves provably optimal assignments on 21 benchmark instances. It demonstrates that existing heuristics, including a reinforcement‑learning legalizer and sliding‑window approaches, are within 0.1% of optimal on most cases, while other density‑guided and greedy methods can be significantly worse. The authors release the code, optimal values, and dual certificates for these benchmarks.

By Kadhir Parani, Manjunath Bezawada, Divya M, Kesana Jathin, Kolli Sarath, Sm Zobaed
arXiv AI
Jul 22

Cost Accounting for Reactive Computational Graphs: Exhaustive Sweeps, Sequential Mutation, and the Backward-Locality Gap

arXiv:2607. 18323v1 Announce Type: cross Abstract: Exhaustive site-by-site interventions on a neural network's computational graph -- activation-patching sweeps, circuit-discovery searches, systematic ablation studies -- mutate the graph at every candidate site, and their cost is dominated by recomputation after each mutation.

By Abdallah Khemais (ISITCOM, University of Sousse)