Approximate Heuristic Search for Semi-Decentralized Systems

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

IJCAI 20260 citations

Approximate Heuristic Search for Semi-Decentralized Systems

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

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* finds near exact optimal solutions in less than 1% of the time required by exact algorithms. We show scalability in six labyrinth environments with 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.

Agent-based and Multi-agent Systems: Agent communicationAgent-based and Multi-agent Systems: Agent-based simulation and emergenceAgent-based and Multi-agent Systems: ApplicationsAgent-based and Multi-agent Systems: Coordination and cooperationAgent-based and Multi-agent Systems: Multi-agent planning

BibTeX

@inproceedings{ijcai2026_approximateheuri,
  title = {Approximate Heuristic Search for Semi-Decentralized Systems},
  author = {Mahdi Al-Husseini and Kyle H. Wray and Isaac R. Ward and Mykel J. Kochenderfer},
  booktitle = {IJCAI 2026},
  year = {2026}
}