---
title: "Approximate Heuristic Search for Semi-Decentralized Systems"
authors:
  - "Mahdi Al-Husseini"
  - "Kyle H. Wray"
  - "Isaac R. Ward"
  - "Mykel J. Kochenderfer"
doi: "10.24963/ijcai.2026/2"
url: "https://ijcai.org/proceedings/2026/2"
pdf: "https://ijcai.org/proceedings/2026/0002.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "12-19"
track: "Main Track"
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"
---

# Approximate Heuristic Search for Semi-Decentralized Systems

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

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 12-19. DOI: [10.24963/ijcai.2026/2](https://doi.org/10.24963/ijcai.2026/2)

## 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.