We propose a new parallel search algorithm – A! – based on cooperating A* search agents, concurrency and a secondary tiebreaking heuristic. The search agents in A! share information asynchronously and trade some of their independence for additional search focus and a more global view of the search task. A! is inherently nondeterministic due to the implicit randomness of instruction scheduling, but given a consistent primary heuristic, it still finds optimal solutions for the single-source shortest path problem (SSSP). A! combines into a single cooperative search algorithm the breadth available in parallel execution and the depth-first orientation of both locally and globally informed search.

We experimentally show that A! outperforms both vanilla A* and an explicitly randomized, noncooperative parallel A* variant. We present an empirical study on cooperation benefits and scalability in the classic 15-puzzle context. The results imply that cooperation and concurrency can successfully be harnessed in algorithm design, inviting further inquiry into algorithms of this kind.