Approximate Heuristic Search for Semi-Decentralized Systems

Al-Husseini, Mahdi; Wray, Kyle H.; Ward, Isaac R.; Kochenderfer, Mykel J.

doi:10.24963/ijcai.2026/2

Approximate Heuristic Search for Semi-Decentralized Systems

Mahdi Al-Husseini, Kyle H. Wray, Isaac R. Ward, Mykel J. Kochenderfer

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 12-19.

https://doi.org/10.24963/ijcai.2026/2

Keywords

Agent-based and Multi-agent Systems: Applications
Agent-based and Multi-agent Systems: Agent communication
Agent-based and Multi-agent Systems: Coordination and cooperation
Agent-based and Multi-agent Systems: Multi-agent planning
Agent-based and Multi-agent Systems: Agent-based simulation and emergence

Abstract

Achieving optimal coordination in multiagent systems involves a trade-off between intractable centralized planning and suboptimal decentralized execution. We bridge this gap by introducing Approximate Recursive Small Step-Semi-Decentralized A* (RS-SDA*), a tree search algorithm that exploits time-varying centralization during periods of available communication conditioned on the environment or joint actions. By interleaving offline planning with online search and using relaxed heuristics, RS-SDA* achieves high solution quality with reduced computational overhead. SDec-POMDP benchmark experiments show that Approximate RS-SDA* often finds near exact optimal solutions in less than 1% of the time required by exact algorithms. We show scalability in six labyrinth environments both deterministic and stochastic state transitions, and demonstrate real-world feasibility with a multi-drone search-and-rescue simulation in the DARPA Subterranean Challenge cave system.

Mahdi Al-Husseini, Kyle H. Wray, Isaac R. Ward, and Mykel J. Kochenderfer. 2026. Approximate Heuristic Search for Semi-Decentralized Systems. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 12–19. https://doi.org/10.24963/ijcai.2026/2

@inproceedings{ijcai2026p2,
  title     = {Approximate Heuristic Search for Semi-Decentralized Systems},
  author    = {Al-Husseini, Mahdi and Wray, Kyle H. and Ward, Isaac R. and Kochenderfer, Mykel J.},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {12--19},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/2},
  url       = {https://doi.org/10.24963/ijcai.2026/2},
}

TY  - CPAPER
TI  - Approximate Heuristic Search for Semi-Decentralized Systems
AU  - Al-Husseini, Mahdi
AU  - Wray, Kyle H.
AU  - Ward, Isaac R.
AU  - Kochenderfer, Mykel J.
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 12
EP  - 19
DO  - 10.24963/ijcai.2026/2
UR  - https://doi.org/10.24963/ijcai.2026/2
ER  -